存储器管理

hilytong

第3章  存储器管理
本章教学目标     
熟悉存储管理的基本功能
掌握各种存储管理方式下主存分配与回收、地址转换与存储保护、管理特点
熟悉在各种存储管理方式下提高主存利用率的方法
本章主要内容
3.1 存储器管理概述
3.2 单用户连续存储管理方式
3.3 固定分区存储管理方式
3.4 可变分区存储管理方式
3.5 页式存储管理方式
3.6 段式存储管理方式
3.7 段页式存储管理方式
3.8 虚拟存储管理方式
3.1  存储器管理概述
3.1.1  存储器管理的主要任务
3.1.2  存储器管理的主要功能
3.1.3  程序的装入与链接
3.1.4  存储管理方式
3.1.1  存储器管理的主要任务
存储管理的主要任务是尽可能方便用户和提高主存储器的使用效率，使主存储器在成本、速度和规模之间获得较好的权衡。
3.1.2  存储器管理的主要功能
1．主存空间的分配和回收
2．地址转换
3．主存空间的共享与保护
4．主存空间的扩充
3.1.3  程序的装入与链接
1．源程序的执行过程
2．程序的链接
3．程序的装入
1．源程序的执行过程
通常要经过编译、链接和装入几个步骤，其控制示意如图3-1所示。
（1）编译。由编译程序将用户源代码编译成若干个目标模块。
（2）链接。由链接程序将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块。
（3）装入。由装入程序将装入模块装入主存的过程。
2．程序的链接
链接程序的功能是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。
实现链接的方法有三种
静态链接：事先进行链接，以后不再拆开的链接方式
装入时动态链接：用户源程序经编译后所得到的目标模块，是在装入主存时，边装入边链接的。
运行时动态链接：可将某些目标模块的链接，推迟到执行时才进行。
3．程序的装入
程序的装入就是把程序装入内存空间。
采用三种方式
（1）绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入主存。  
（2）可重定位方式 ：是由装入程序根据主存当前的实际使用情况，将装入模块装入到主存适当的地方。
（3）动态运行时装入方式：动态运行时的装入程序，在把装入模块装入主存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行。  
3.1.4  存储管理方式
单用户连续存储管理方式
固定分区存储管理方式
可变分区存储管理方式
页式存储管理方式
段式存储管理方式
段页式存储管理方式
虚拟存储管理方式
3.2 单用户连续存储管理方式
3.2.1  基本原理
3.2.2  主存空间的分配与回收
3.2.3  地址转换与存储保护
3.2.4  管理特点
3.2.1  基本原理
这是最早出现的一种存储管理方式。
在主存中仅驻留一道程序，整个用户区为一用户独占。当用户作业空间大于用户区时，该作业不能装入。
这种分配方式仅能用于单用户、单任务的操作系统中，不能用于多用户系统和单用户多任务系统中。
3.2.2  主存空间的分配与回收
1．主存空间的分配
采用这种存储管理方式时，主存分为两个分区（系统区 和用户区），如图3-4所示。
其分配过程是：首先，从作业队列中取出队首作业；判断作业的大小是否大于用户区的大小，若大于则作业不能装入，否则，可以把作业装入用户区。它一次只能装入一个作业。
其主存分配流程如图3-5所示。
2．主存空间的回收
作业一旦进入主存，就要等到它结束后才能释放主存，再装入第二个作业即可。
3.2.3  地址转换与存储保护
1．地址转换
2．存储保护
1．地址转换
它采用静态分配方式。
处理器设置两个寄存器：界限寄存器和重定位寄存器。界限寄存器用来存放主存用户区的长度，重定位寄存器用来存放用户区的起始地址。
地址转换过程是：CPU获得的逻辑地址首先与界限寄存器的值比较，若大于界限寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理；若不大于界限寄存器的值，就与重定位寄存器中的基址相加，得到物理地址，对应于主存中的一个存储单元。
其转换过程如图3-6所示。
2．存储保护
处理器在执行指令时，要检查其逻辑地址是否小于界限寄存器的值，
若小于，则与重定位寄存器中的基址相加，产生物理地址，到主存中去执行。
否则，产生一个“地址越界”中断信号，由操作系统进行处理，以达到存储保护的目的。
3.2.4  管理特点
（1）管理简单。它把主存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。它需要很少的软硬件支持，且便于用户了解和使用。
（2）在主存中的作业不必考虑移动的问题，并且主存的回收不需要任何操作。
（3）资源利用率低。不管用户区有多大，它一次只能装入一个作业，这样造成了存储空间的浪费，使系统整体资源利用率不高。
（4）这种分配方式不支持虚拟存储器的实现。
3.3 固定分区存储管理方式
3.3.1  基本原理
3.3.2  主存空间的分配与回收
3.3.3  地址转换与存储保护
3.3.4  管理特点
3.3.5   对固定分区存储管理方式的改进  
3.3.6  固定分区存储管理举例
3.3.1  基本原理
把主存中可分配的用户区域预先划分成若干个固定大小的区域，每一个区域称为一个分区，每个分区中可以装入一个作业，一个作业也只能装入一个分区中，这样可以装入多个作业，使它们并发执行。当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行完时，又可从后备队列中选择另一个作业装入该分区。
固定分区存储管理方式是最早使用的一种可运行多道程序的存储管理方式。
它仍然要求把作业全部装入主存，且装入一个连续的存储空间。
3.3.2  主存空间的分配与回收
1．采用的数据结构
2．主存空间的分配
3．主存空间的回收
1．采用的数据结构
为了记录各个分区的基本情况和使用情况，方便主存空间的分配与回收操作，设置了一张分区分配表。
分区分配表的内容包括：分区序号、起始地址、大小、状态。
状态栏的值为“0”表示分区空闲，可以装入作业；当装入作业后，其值改为作业名，表示这个分区被该作业占有。
如表3-1所示 。
2．主存空间的分配
在作业分配之前，根据主存分区的划分，在分区分配表填入每个分区的始址、大小，在状态栏中一律填入“0”，表示该分区可用，当作业装入时，填入作业名。
当有作业申请主存空间时，主存空间的分配步骤为：
从作业队列中取出队首作业，检查分区分配表，选择状态标志为“0”的分区，根据作业地址空间的大小与状态标志为“0”的分区的大小比较，当所有分区长度都不能容纳该作业时，则该作业暂时不能装入，显示主存不足的信息。
当某一个分区长度能容纳该作业时，则把作业装入该分区，且把作业名填到该分区的状态栏里。
然后，再分配下一个作业。
主存分配流程如图3-7所示。
3．主存空间的回收
当作业运行结束时，根据作业名到分区分配表中进行检查，从状态栏的记录可知该作业占用的分区，把该分区的状态标志置成“0”，表示该分区就空闲了，可以用来装入新的作业。
3.3.3  地址转换与存储保护
1．地址转换
2．存储保护
1．地址转换
采用静态重定位方式。
处理器设置两个寄存器：下限寄存器和上限寄存器。下限寄存器用来存放分区低地址，即起始地址；上限寄存器用来存放分区的高地址，即末址。
地址转换过程
CPU获得的逻辑地址首先与下限寄存器的值相加，产生物理地址；
然后与上限寄存器的值比较，若大于上限寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理；若不大于界限寄存器的值，得到物理地址就是合法地址，它对应于主存中的一个存储单元。
地址转换过程如图3-10所示。
2．存储保护
系统设置了一对寄存器，称为“下限寄存器”和“上限寄存器”记录当前在CPU中运行作业在主存储器中的下限和上限地址。
当处理机执行该作业的指令时必须核对表达式“下限地址<=绝对地址<=上限地址”是否成立。
若成立，就执行该指令，否则就产生“地址越界”中断事件，停止执行该指令。
运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和下限、上限寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。
3.3.4  管理特点
（1）一个作业只能装入一个分区，不能装入两个或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入。
（2）通过对“分区分配表”的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式。此方法易于实现，系统开销小。
（3）当分区较大作业较小时，仍然浪费许多主存空间。并且分区总数固定，限制了并发执行的作业数目。
3.3.5   对固定分区存储管理方式的改进
一个分区只装入一个作业，分区的其它部分闲置不用，降低了主存的利用率。可采用下列算法提高主存的利用率：
（1）根据经常出现的作业的大小和数量来划分分区，尽可能使各个分区充分利用。
（2）划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区。各分区按从小到大的顺序登记在分区表中。
（3）按作业对主存的需求量排成多个作业队列，一个作业队列对应一个分区，互不借用。
3.3.6  固定分区存储管理举例
【例3-1】
在某系统中采用固定分区分配管理方式，主存分区（单位字节）情况如图3-9（a）所示。现有大小为1KB、9KB、33KB、121KB的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明主存浪费有多大？
3.4 可变分区存储管理方式
3.4.1  基本原理
3.4.2  主存空间的分配与回收
3.4.3  地址转换与存储保护
3.4.4  管理特点
3.4.5  采用技术
3.4.6  可变分区存储管理举例
3.4.1  基本原理
可变分区存储管理方式是在作业要求装入主存时，根据作业的大小动态地划分分区，使分区的大小正好适应作业的要求。各分区的大小是不定的，主存中分区的数目也是不定的。
可变分区存储管理方式必须解决三个问题：
一是分区分配中所用的数据结构。
二是分区的分配算法。
三是分区的分配和回收。
3.4.2  主存空间的分配与回收
1．采用的数据结构
2．主存空间的分配
3．常用的主存分配算法
4．主存空间的回收
1．采用的数据结构
为了实现分区分配，系统中必须配置相应的数据结构，用来记录主存的使用情况，包括空闲分区的情况和使用分区的情况，为作业分配主存空间提供依据。为此，设置了两个表，即已分分区表和空闲分区表，如表3-2和表3-3所示。
① 已分分区表。记录主存中已分配作业分区的情况，包括分区序号、起始地址、大小和状态（作业名）。
② 空闲分区表。记录主存中空闲分区的情况，包括空闲分区序号、起始地址和大小。为了便于处理，一般情况下空闲分区表中的空闲分区记录以地址递增的顺序排列。
2．主存空间的分配
先从小地址分配，再分配大地址。空闲分区表中记录的排列也是从小地址向大地址排列的。
首次分配时，只有一个空闲区。分配的区被收回后，还可以分给其它的作业。再分给其它作业时，该分区被分成两部分，一部分被作业占据，另一部分又成为一个较小的分区。当小到一定程度时，全部分给该作业。
主存的分配过程如下：
首先初始化已分分区表（0个记录）和空闲分区表（1个记录），整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小。
其次，从作业队列中取出队首作业，在空闲分区表中找一个不小于作业的空闲区，装入作业，在已分分区表中增加一个记录，填上作业所占分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。
然后，再分配下一个作业，直到所有作业分配完毕。
主存空间的分配流程如图3-12 所示。
3．常用的主存分配算法
（1）最先适应分配算法（FF）
（2）最优适应分配算法(BF)
（3）最坏适应分配算法（WF）
三种分配算法的比较
（1）最先适应分配算法（FF）
原理
对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。
特点
一是分配算法简单；二是容易产生过多的小地址碎片；三是降低了主存空间利用率。
改进
采用循环首次适应算法。
（2）最优适应分配算法(BF)
原理
是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。
特点
一是解决了大作业的分配问题；二是容易产生不可利用的空闲区，降低了主存空间的利用率；三是收回主存时，要按长度递增顺序插入到空闲区表中。
（3）最坏适应分配算法（WF）
原理
每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用。为实现这种算法，把空闲区按长度递减次序登记在空闲区表中，分配时，顺序查找。
特点
一是不会产生过多的碎片；二是影响大作业的分配；三是收回主存时，要按长度递减的顺序插入到空闲区表中。
三种分配算法的比较
从搜索速度和回收过程上看：最先适应分配算法（FF）具有最佳性能；
从空间利用上看：最先适应分配算法（FF）比最优适应分配算法（BF）好，最优适应分配算法（BF）比最坏适应分配算法（WF）要好；最优适应分配算法（BF）找到的空闲区是最佳的，但在某些情况下，不一定能提高主存的利用率。
最先适应分配算法（FF）的另一个优点是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置较大的作业。
最坏适应分配算法（WF）由于过多的分割大的空闲区，当遇到较大作业申请时，无法满足其申请的可能性较大，该算法对中、小作业比较有利。因此，在实际系统中，最先适应分配算法（FF）法用得最多。
4．主存空间的回收
当一个作业运行结束后，在已分分区表中找到该作业，根据该作业所占主存的始址和大小，去修改空闲分区表相应的记录。其修改情况分4种，如图3-13所示（斜线部分为已被作业占有的主存区域）。
（1）回收的分区前后没有相邻的空闲分区。在空闲分区表中要增加一条记录，该记录的始址和大小，即为回收分区的始址和大小。如图3-13（a）所示。
（2）回收分区的前面有相邻的空闲区。在空闲分区表中找到这个空闲区（查找的方法是比较空闲分区的始址＋空闲分区的大小与回收分区的始址是否相等），修改这个空闲区的大小，即加上回收分区的大小，始址不变。如图3-13（b）所示。
（3）回收分区的后面有相邻的空闲分区。在空闲分区表中找到这个空闲区（查找的方法是回收分区的始址－回收分区的大小与空闲分区的始址比较是否相等），修改这个空闲区的始址和大小。始址为回收分区的始址，大小为回收分区的大小与空闲区的大小之和。如图3-13（c）所示。
（4）回收分区的前后都有相邻的空闲分区。在空闲分区表中找到这两个空闲区，修改前面相邻的空闲区的大小，其始址不变。大小改为相邻两个空闲区和回收分区的大小之和，然后从空闲分区表中，删除后一个相邻空闲分区的记录。如图3-13（d）所示。
最后，在已分分区表中删除该分区的记录。
3.4.3  地址转换与存储保护
1．地址转换
2．存储保护
1．地址转换
采用动态重定位方式装入作业。它需要设置硬件地址转换机构：两个专用寄存器，即基址寄存器和限长寄存器，以及一些加法、比较电路。地址转换步骤如下：
① 当作业占用处理器时，进程调度把该作业所占分区的起始地址送入基址寄存器，把作业所占分区的最大地址送入限长寄存器。
② 作业执行过程中，处理器每执行一条指令，都要由硬件的地址转换机构把逻辑地址转换成物理地址。
③ 当取出一条指令后，把该指令中的逻辑地址与基址寄存器内容相加得到物理地址，该物理地址必须满足：物理地址<=限长寄存器的值
基址寄存器和限长寄存器总是存放当前占用处理器的作业所占分区的始址和末址。一个作业让出处理器时，应先把这两个寄存器的内容保存到该作业所对应进程的PCB中，然后再把新作业所占分区的始址和末址存入这两个专用寄存器中。如图3-14所示。
2．存储保护
系统设置了一对寄存器，称为“基址寄存器”和“限长寄存器”记录当前在CPU中运行作业在主存中所占分区的始址和末址。
当处理机执行该作业的指令时必须核对表达式“始址<=绝对地址<=末址”是否成立。若成立，就执行该指令，否则就产生“地址越界”中断事件，停止执行该指令。
运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和基址寄存器、限长寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。