操作系统课件第4章.ppt

1、第四章存储器管理,4.1 存储器的层次结构 4.2程序的装入和链接 4.3连续分配方式 4.4基本分页存储管理方式 4.5基本分段存储管理方式 4.6虚拟存储器的基本概念 4.7请求分页存储管理方式 4.8页面置换算法 4.9请求分段存储管理方式,在多道程序设计技术出现后，对存储管理提出了更高的要求。 一方面，要使主存得到充分、有效地利用； 另一方面又要为用户提供方便的使用环境。,4.1 存储器的层次结构,4.1.1 多级存储器结构 对于通用计算机而言，存储层次至少应具有三级： 最高层为CPU寄存器 中间为主存 最底层是辅存 根据具体的功能分工细划为: 寄存器、高速缓存、主存储器、磁盘缓存、固

2、定磁盘、可移动存储介质等6层。,图4-1 计算机系统存储层次示意,快,慢,寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。 固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。,4.1.2 主存储器与寄存器 1主存储器 主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，其容量对于当前的微机系统和大中型机，可能一般为数十MB到数GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十KB到几MB。CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取

3、并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU与外围设备交换的信息一般也依托于主存储器地址空间。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。,2寄存器 寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。,4.1.3 高速缓存和磁盘缓存 1高速缓存 高速缓

4、存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。,2磁盘缓存 由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来

5、暂存从磁盘中读出(或写入)的信息。主存也可以看做是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。,4.1.4 地址映射,程序和数据必须装入内存，即要占用一定的内存空间才能执行和使用。 暂时不执行或不用的程序和数据可放在外存中。 CPU不能直接访问外存，需通过I/O设备实现内、外存信息交换。 内存空间一般分为两部分： 一部分是系统区，存放操作系统、标准子程序、例行程序和系统数据等； 另一部分是用户区，用于存放用户的程序和数据等。,存储管理主要是对用户区进行管理，其目的是充分利用内存，为多道程序并发执行提供存储基础，方便用户使用。,存储管理

6、的功能: 存储分配 地址映射（逻辑地址与物理地址的对应关系） 存储保护 内存扩充（虚拟存储器技术以及各种调度算法）,在多道程序设计的环境中: 当有作业进入计算机系统时，存储管理应能根据当时的内存分配状况，按作业要求分配给它适当的内存。 当某个作业完成不再使用内存时，应回收占用的内存空间，以便供其他用户使用。,物理地址和逻辑地址,1）内存空间 主存储器以字节为编址单位，容量为n的主存储器中，每个单元有唯一的编号，分别为：0，1，2，n1， 这个唯一的编号就是主存储器的物理地址（即绝对地址、实地址）。,内存地址的集合称为内存地址空间（或物理地址空间），简称内存空间（或物理空间），是一维线性空间。

7、例如，某个系统，有64kb内存，则其内存空间编号为： 0，1，2，3，65535。,2）逻辑空间 用汇编语言或高级语言编写程序时，常常用符号名来访问某一单元。把源程序中由符号名组成的程序空间称为符号名空间，简称名空间。 源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。 在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址（或相对地址、虚地址）。,一个编译好的程序存在于它自己的逻辑空间中，运行时，要把它装入内存空间， 如图4.2所

8、示,一个作业在编译前、编译后及装入内存后不同空间的情形。,符号地址,逻辑地址,物理地址,由图4.2可以看出：该作业经过编译后，大小为300字节，逻辑地址空间为0299。在作业的第100号单元处有指令 Mov Rl，200，即把200号单元内的数据6817送入寄存器Rl。 假如把作业装入到内存第10001299号单元处。由图4.2可以看出，若只是简单地装入第10001299号单元，执行Mov Rl，200指令时，会把内存中200号单元的内容送入Rl，显然这样会出错。只有把1200单元的内容送入Rl才是正确的。 所以作业装入内存时，需对指令和指令中相应的逻辑地址部分进行修改，才能使指令按照原有的逻

9、辑顺序正确运行。,4.2程序的装入和链接,在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；其次是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和

10、装入过程。,图4-2对用户程序的处理步骤,4.2.1程序的装入 1绝对装入方式(Absolute Loading Mode) 在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。例如，事先已知用户程序(进程)驻留在从R处开始的位置，则编译程序所产生的目标模块(即装入模块)便从R处开始向上扩展。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。,程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序

11、员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。,缺点： 绝对装入方式只能将目标模块装入到内存中事先指定的位置。 绝对装入方式只适用于单道程序环境。,2可重定位装入方式(Relocation Loading Mode)(静态重定位） 在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。,图4-3作业装入内存时的情况,例如，在用户程序的1000号

12、单元处有一条指令LOAD 1，2500，该指令的功能是将2500单元中的整数365取至寄存器1。但若将该用户程序装入到内存的1000015000号单元而不进行地址变换，则在执行11000号单元中的指令时，它将仍从2500号单元中把数据取至寄存器1而导致数据错误。由图4-3可见，正确的方法应该是将取数指令中的地址2500修改成12500，即把指令中的相对地址2500与本程序在内存中的起始地址10000相加，才得到正确的物理地址12500。除了数据地址应修改外，指令地址也须做同样的修改，即将指令的相对地址1000与起始地址10000相加，得到绝对地址11000。通常是把在装入时对目标程序中指令和数

13、据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。,缺点： 可重定位装入方式不允许程序运行时在内存中移动位置。,3动态运行时装入方式(Dynamic Run-time Loading) 因为，程序在内存中的移动，意味着它的物理位置发生了变化，这时必须对程序和数据的地址(是绝对地址)进行修改后方能运行。然而，实际情况是，在运行过程中它在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式。,4.2.2程序的链接 根据链接时间的不同，可把链接分成如下三种： (1) 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配

14、模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。 (2) 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 (3) 运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。,1静态链接方式(Static Linking) (1) 对相对地址进行修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。在链接成一个装入模块后，原模块B和C在装入模块的起始地址不再是0，而分别是L和L+M，所以此时须修改模块B和C中的相对

15、地址，即把原B中的所有相对地址都加上L，把原C中的所有相对地址都加上L+M。,(2) 变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如把B的起始地址变换为L，把C的起始地址变换为L+M，如图4-4(b)所示。这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。,图 4-4程序链接示意图,2装入时动态链接(Load-time Dynamic Linking) 用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模

16、块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式来修改目标模块中的相对地址。装入时动态链接方式有以下优点： (1) 便于修改和更新。对于经静态链接装配在一起的装入模块，如果要修改或更新其中的某个目标模块，则要求重新打开装入模块。这不仅是低效的，而且有时是不可能的。若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块是件非常容易的事。,(2) 便于实现对目标模块的共享。在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享。但采用装入时动态链接方式，OS则很容易将一个目标模块链接到几个应用模块上，

17、实现多个应用程序对该模块的共享。,3运行时动态链接(Run-time Dynamic Linking),这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,4.3连续分配方式,4.3.1单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS

18、使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。,4.3.2固定分区分配 1划分分区的方法 可用下述两种方法将内存的用户空间划分为若干个固定大小的分区： (1) 分区大小相等，即使所有的内存分区大小相等。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例如，炉温群控系统，就是利用一台计算机去控制多台相同的冶炼炉。,(2) 分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点

19、，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。,2内存分配 为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图4-5(a)所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图4-5(b)所示。,图 4-5固定分区使用表,20,固定分区存储管理的最大的优点是简单，要求的硬件支持少，

20、软件算法也简单； 缺点是容易产生内部碎片，即由于分区大小是事先固定的，因而可容纳作业的大小受到限制。而且当用户作业的地址空间小于分区的存储空间时，浪费了一些存储空间。,4.3.3动态分区(可变分区)分配,与固定分区法相比，动态分区法在作业执行前并不建立分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等 能有效解决固定式分区的内部碎片问题，是一种较为实用的存储管理方法 因为在系统运行过程中，内存中分区的数目和大小都是可变的，所以也叫可变分区,如图4.7所示，假设某系统采用可变式分区存储管理，在系统运行的开始，存储区被分为操作系统分区（40kb）和可分给用户的空闲区（21

21、6kb）。 当作业1（46k）进入内存后，分给作业1（46k），随着作业2、3、4的进入，分别分配32k，38k，40k， 经过一段时间的运行后，作业1、3运行完毕，释放所占内存。 此时，作业5进入系统，要求分配36k内存，如何为作业5分配内存呢？,如图4.7（c）所示，此时，有三种方法可给作业5分配内存： 从作业1释放的46k中，分36k给作业5，即分配空闲区1； 从作业3释放的38k中，分36k给作业5，即分配空闲区2； 从空闲的60k中，分36k给作业5，即分配空闲区3。,到底采用哪种分配方法呢? 这时，应考虑空闲分区的组织形式和采用的内存分配算法。,1. 空闲分区的数据结构,在可变式分

22、区存储管理中，常把空闲区组成空闲分区表或空闲分区链表的形式。 空闲分区表的组织类似于固定分区的分区说明表，包含空闲分区的起始位置和大小，因分区数目不定，故空闲分区表长度不定。 采用空闲分区表要占用一定数量的存储单元存放此表 增加了系统的开销。,空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。 系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。 因空闲分区链表组织时，空闲区的信息放在空闲区内，因此不会额外增加系统的开销。 所以使用比较广泛的是空闲分区的

23、链表组织形式。,（1） 首次适应算法,思想是: 把空闲分区按其所在存储空间中地址递增的顺序连接在一起。 当用户申请一内存存储空间时，从空闲区链表的头指针开始查找，选择第一个满足要求的空闲分区。 算法如图4.9所示。,2. 常用的分配算法,优点： 该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。 缺点： 低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。,(2) 循环首次适应算法 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再

24、是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。,优点： 该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销 缺点： 但这样会缺乏大的空闲分区。,（3）最佳适应算法,这种算法把空闲分区链表按分区大小由小到大进行组织。 当有作业申请内存时，总是首先找到满

25、足要求的最接近作业大小的空闲分区。 此算法最节约空间，因为它尽量不分割大的空闲区。,缺点： 孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区(外部碎片)。,（4）最坏适应算法,这种算法要求把空闲区按分区大小递减的顺序组织成空闲区链表。 当用户申请一个存储区时，总是检查空闲区链表的第一个空闲区是够满足要求， 若不满足，分配失败； 若满足，则将空闲区分配给用户，然后修改和调整空闲区链表。,该算法的优点是：可以避免形成碎片； 缺点是：它会使存储器中缺乏大的空闲分区，分割大的空闲区后，再遇到较大的申请时

26、，无法满足的可能性较大。,(5) 快速适应算法 该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。,优点： 查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配

27、即可。 另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。 缺点： 分区归还主存时算法复杂，系统开销较大。 该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此存在一定的浪费。,3分区分配操作 1) 分配内存 系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)

28、，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图4-7示出了分配流程。,2) 回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： (1) 回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 (2) 回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者

29、之和。,(3) 回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 (4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,图 4-8内存回收时的情况,动态分区存储管理的主要优缺点,优点： 有效地解决了固定式分区的内部碎片问题，较有效地利用主存空间，提高了多个作业或进程对内存的共享。,缺点： 容易产生外部碎片问题，为解决外部碎片问题，可采用紧凑技术，但花费大量处理机时间。,4.3.4伙伴系统 固定分区和动态分区方式都有不足

30、之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。 伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。,假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一

31、类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。,当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i1的空闲分区链表中寻找。若存在2i1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i1的空闲分区也不存在，则需要查找大小为2i2的空闲分区，若找到则对其进行两

32、次分割：第一次，将其分割为大小为2i1的两个分区，一个用于分配，一个加入到大小为2i1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。,与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i1的空闲分区，若事先已存在2i1的空闲分区时，又应继续与其伙伴分区合并为大小为2i2的空闲分

33、区，依此类推。 在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。,4.3.6可重定位分区分配 1动态重定位的引入 在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。例如，图4-9(a)中示出了在内存中现有四个互不邻接的小分

34、区，它们的容量分别为10 KB、30 KB、14 KB和26 KB，其总容量是80 KB。但如果现在有一作业到达，要求获得40 KB的内存空间，由于必须为它分配一连续空间，故此作业无法装入。这种不能被利用的小分区称为“零头”或“碎片”。,图4- 9 紧凑的示意,若想把作业装入，可采用“拼接”或“紧凑”技术： 将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区，即通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区。 由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，

35、则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。,2动态重定位的实现 在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。,图 4-10动态重定位示意图,程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。图4-10示出了动态重定位的实现原理。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，

36、故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。,3动态重定位分区分配算法 动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。图4-11示出了动态重定位分区分配算法。,图4-11动态分区分配算法流程图,4.3.7对换 1对换(Swapping)的引入 在多道程序环境下，会出现以下情况： 一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有

37、时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。 显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。为了解决这一问题，在系统中又增设了对换(也称交换)设施。,所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。,如果对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”。这种对换被广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存

38、的利用率。 如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。这种对换方法是实现后面要讲到的请求分页和请求分段式存储管理的基础，其目的是为了支持虚拟存储系统。 在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程的换出，以及进程的换入。,2对换空间的管理 在具有对换功能的OS中，通常把外存分为文件区和对换区： 文件区用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。 对换区用

39、于存放从内存换出的进程。进程在对换区中驻留的时间是短暂的，对换操作又较频繁，故对对换空间管理的主要目标，是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。,对对换区中的空闲盘块进行管理数据结构，其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，分别用盘块号和盘块数表示。,3进程的换出与换入 (1) 进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换

40、出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。 (2) 进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久(换出到磁盘上)的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,4.4 基本分页存储管理方式,目前已讨论了单道存储管理和分区式存储管理方法。 分区式管理方式尽管实现方式较为简单，但存在着严重的碎片问题，内存的利用率不高。 再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程

41、的大小仍受分区大小或内存可用空间的限制。 而且，分区式管理也不利于程序段和数据的共享。,分页存储管理正是为了减少碎片，以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放在外存待执行时调入，以提高内存利用率而提出来的。,4.4.1 基本原理1.内存划分,页式存储管理： 将内存空间划分成等长的若干区域，每个区域称为一个物理块，有时也称内存块或块。 内存的所有物理块从0开始编号，称作物理块号或内存块号。 每个物理块内单元亦从0开始依次编址，称为块内地址。,系统将用户程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面，有时也简称为页。 程序的各个逻

42、辑页面从0开始依次编号，称作逻辑页号或相对页号， 每个逻辑页面内单元也从0开始编址，称为页内地址。,2. 逻辑地址空间划分,对用户程序地址空间的分页是系统自动进行的，即对用户是透明的。 由于页面尺寸选为2的整数次幂，故系统可将地址的高位部分定义成页号，低位部分定义成页内地址。 例如，下图中，机器地址长为20位，若页面长度为210，则地址的 1019位表示页号，最多拥有210 =1024个逻辑页， 09位表示页内地址，即页长为210 =1K。,对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,其中，INT是整除函数，MOD

43、是取余函数。例如，其系统的页面大小为1 KB，设A = 2170 B，则由上式可以求得P = 2，d = 122。,页面大小直接影响地址转换和页式存储管理的性能: 如果页面太大，以至于和作业地址空间相差无几，这种方法就变成了可变分区方法的翻版； 反之，如果页面太小，则增加了系统的开销。,3. 页面大小,页面尺寸一般取2的整数次幂，如29，210，211等。,存储分配时，以块为单位，并按用户程序的页数多少进行分配，逻辑上相邻的页面在内存中不一定相邻，即: 分配给用户程序的内存块不一定连续。,4. 内存分配,如果把一个作业的所有页面一次全部装入到内存块中，就把这种分页称之为纯分页存储管理。 如果作

44、业的所有页面并不是一次全部装入，而是根据作业运行时的实际要求装入，则把这种分页称为虚拟页式存储管理。 本节先讨论纯分页存储管理。,4.4.2 实现方法1. 建立页表,系统为每个用户程序建立一张页面映像表（页表），用于记录用户程序逻辑页面与内存物理块之间的对应关系，实现从页号到物理块号的地址映射。 用户程序的地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列。 页表存放在内存系统区内。,图4-12页表的作用,2. 建立空闲页面表 系统中设立一张内存空闲页面表，记录内存物理页面空闲情况，用于内存分配和回收。,系统提供一对硬件寄存器：页表始址寄存器和页表长度寄存器。 （1）页表始址寄存器

45、用于保存正在运行进程的页表在内存的首地址。 当进程被调度程序选中投人运行时，系统将其页表首址从进程控制块中取出送入该寄存器。 （2）页表长度寄存器 用于保存正在运行进程的页表的长度。 当进程被选中运行时，系统将它从进程控制块中取出送入该寄存器。,3. 硬件支持,4. 地址映射,具体步骤说明如下： （1）地址映射机构把CPU给出的逻辑地址分为两部分，如执行指令LOAD 1，2500时，逻辑地址250021024452，因此页号p2，页内地址d452。这是假设页面大小为210情况下得到的结果； （2）将逻辑页号p与页表长度比较，如果p大于页表长度，则为越界，发生越界中断。,（3）根据页表始址得到页

46、表在内存的首地址，并根据逻辑页号p在页表中找到对应的物理页号。如果页号p2，则相应物理页号为8。 （4） 把物理页号与逻辑地址中的页内地址d拼在一起，形成访问内存的物理地址。在本例中， 物理地址102484528644。,4.4.3 快表,从地址映射过程中可以看出，共需两次访问内存： 第一次访问页表，得到数据的物理地址; 第二次才是存取数据。,增加了访问时间。,为了提高存取速度, 在分页地址变化机构中，加入一组高速缓冲存储器, 用来存放当前作业的最常用的页号和与之相对应的物理块号。 一般称这样的寄存器组为快表或联想存储器。,快表因硬件成本较高，个数不宜太多，一般以存放16512个页表项为宜，和

47、页表具有并行查找能力。,具有快表的地址映射过程： 当处理机给出逻辑地址（p，w）时，分页机构: 一方面取出页号p，并根据p从页表中查找相应的内存块号b； 另一方面自动把页号p送入快表，并和快表各单元进行比较，如与某单元页号相符，则,输出对应块号b，并与页内地址w形成物理地址进行访问，停止查找页表的工作， 由于快表采用的是高速缓存，其访问速度比访问页表要快得多。,如果在快表中查找不到， 仍继续在页表中查找， 并把查找到的页号p和块号b放到快表的空闲单元中，以备下次使用， 如无空闲单元，则通常把最先装入的那个页号淘汰，以腾出位置。,基本分页存储管理优点与缺点,优点：有效解决了碎片问题，主存利用率高

48、，内存分配与回收算法也比较简单。 缺点：采用动态地址变换机制，既增加硬件成本也降低了处理机速度。,4.5 基本分段式存储管理4.5.1 基本思想,通常情况下:一个作业=多个程序段+多个数据段， 这要求链接装配程序将它们按一维线性地址排列，从而给程序和数据的共享带来不便。 一般情况下，用户希望：按逻辑关系对作业分段，并能根据名字来访问程序段和数据段。,引入分段存储管理方式: 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接,1.基本原理,用户程序按逻辑上有完整意义的段来划分，称为逻辑段。 例如：主程序、子程序、数据等可各成一段，每段对应于一个过程、一个程序模块或一个

49、数据集合。 将一个用户程序的所有逻辑段从0开始编号，称为段号； 将一个逻辑段中的所有单元从0开始编址，称为段内地址。 整个地址空间就构成了二维地址空间。,用户程序的逻辑地址由段号和段内地址两部分组成：,2. 内存分配,系统以段为单位进行内存分配， 为每一个逻辑段分配一个连续的内存区（物理段）， 逻辑上连续的各个段在内存不一定连续存放。,4.5.2 实现方法1. 建立段表,系统为每个用户程序建立一张段表，用于记录用户程序的逻辑段与内存物理段之间的对应关系，包括逻辑段号，内存首地址和物理段长度三项内容。 用户程序有多少逻辑段，该段表里就登记多少行，且按逻辑段的顺序排列。 段表存放在内存系统区里。

50、段表如图所示。,图4.16 段表示意图,图4-17利用段表实现地址映射,系统中设立一张内存空闲区表，记录内存中空闲区域情况，用于为段分配和回收内存。,2. 建立空闲区表,系统提供一对寄存器：段表始址寄存器和段表长度寄存器。 （1）段表始址寄存器： 用于保存正在运行进程的段表在内存的首地址。 当进程被调度程序选中投入运行时，系统将其段表首址从进程控制块中取出送入该寄存器。 （2）段表长度寄存器： 用于保存正在运行进程的段表的长度。 当进程被选中运行时，系统将它从进程控制块中取出送入该寄存器。,3. 硬件支持,如图4.17所示。 先将逻辑地址中的段号与段表长度寄存器中的段表长度进行比较， 若段号超

51、过段表长度,则产生越界中断； 否则，系统将根据段号和段表始址寄存器中的段表起始地址计算出该段在段表中的位置， 从该位置中将获得该段存放在内存中的起始地址。 然后，检查段内位移是否超过该段的段长， 若超过则产生越界中断； 否则，将该段在内存的起始地址与逻辑地址的段内位移相加就可得到要访问的物理地址。,4. 地址映射过程,【例4 .1】在一个分段式存储管理系统中，其段表如表4.1所示。求如表4.2所示的逻辑地址对应的物理地址。（单位：B）,表4.1 段表,表4.2 逻辑地址,解： （1）由表4.1知，段号为0的段的内存起始地址为210，段长为500。由表4.2知，逻辑地址的段内位移为430。因为4

52、30500，所以该逻辑地址是合法的。其对应的物理地址为：210+430640 （2）由表4.1知，段号为1的段的内存起始地址为2350，段长为20。由表4.2知，逻辑地址的段内位移为10。因为1020，所以该逻辑地址是合法的。其对应的物理地址为：2350+10=2360,（3）由表4.1知，段号为2的段的内存起始地址为100，段长为90。由表4.2知，逻辑地址的段内位移为500。因为50090，即逻辑地址的段内位移500已超过了段长90，所以该逻辑地址是非法的，产生越界中断。,5. 分段与分页的区别,分页与分段存储管理系统虽然在很多地方相似，例如， 它们在内存中都是离散的， 都要通过地址映射机

53、构将逻辑地址映射到物理内存中。 但从概念上讲，两者是完全不同的。,它们之间的区别如下： （1）页是信息的物理单位。分页的目的是实现离散分配，消除内存的外碎片，提高内存利用率。段是信息的逻辑单位。每一段在逻辑上是一组相对完整的信息。 （2）页式存储管理的作业地址空间是一维的，而段式存储管理的作业地址空间是二维的。 （3）页的大小固定且由系统确定，是等长的。而段的长度不定，它是由具有相对完整意义的信息长度确定。 （4）分页的优点体现在内存空间的管理上，而分段的优点体现在地址空间的管理上。,在多道程序环境下，许多应用程序、子程序是被多个用户所使用的。随着多窗口及各种工具软件的流行，被共用的程序和数据

54、都在急剧增长。 如果用户所使用的程序和数据都保留一个运行副本，那么空间的浪费太大，最好的办法是，只保留一个副本，供多个用户使用，称为共享。 如果多个用户进程或作业需要共享某段程序或数据，可以使用不同的段名，在各自的段表中填入已在内存中的共享段的起始地址，并设置适当的读写控制权，就可以做到共享一个内存段的信息。,4.5.3 段的共享,在分段系统中，实现共享只需在每个进程的段表中为文本编辑程序设置一个段表项。图4-20是分段系统中共享editor的示意图。,图 4-20分段系统中共享editor的示意图,4.5.4 段页式存储管理1.基本思想,段页式存储管理的基本思想是： （1）用页式方法来分配和

55、管理内存空间，即：把内存分为若干大小相等的页面； （2）用段式方法对用户程序按照其内在的逻辑关系划分成若干段； （3）再按照划分的内存页面的大小，把每一段内划分成若干大小相等的页面；,（4）用户程序的逻辑地址由三部分组成，形式如下：,（5）内存是以页为基本单位分配给每个用户程序的，在逻辑上相邻的页面在内存不一定相邻。,2. 实现方法,（1）建立段表 系统为每个用户程序建立一张段表，用于记录各段的页表始址和页表长度。 （2）建立页表 系统为用户程序的每一段各建立一张页表，用于记录该段中各逻辑页号与物理块号之间的对应关系。 段表、页表和内存的关系如图4.26所示。,（3）建立内存空闲页面表 整个系

56、统建立一张内存空闲页面表，用于记录并管理内存空闲页面。 （4）硬件支持 为加快地址映射速度，硬件需要提供如下2个寄存器： 段表始址寄存器； 段表长度寄存器；,（5）地址映射过程 在段页式存储管理中，要访问内存的单元，则要经过如下地址转换步骤，才能得到最终的物理地址。 见图4.27所示。 根据逻辑地址中的段号查找快表。如果找到，则形成物理地址，否则进行后续步骤； 通过段表始址寄存器，查找段表在内存中的始址；,通过段表并根据段号，查找页表所在位置； 访问页表，根据逻辑页号查找该页所在的物理块号； 将物理块号和逻辑地址中的页内地址拼接，形成访问内存单元的物理地址； 将有关内容填入快表，如有必要，则根

57、据淘汰算法淘汰快表的一行，以填入新的内容。,前几节介绍的各种存储管理方案有一个共同的问题，即：当一个参与并发执行的进程运行时，其整个程序必须都在内存，因而存在如下缺点：,（1）若一个进程的程序比内存可用空间还大，则该程序无法运行； （2）由于程序运行的局部特性，一个进程在运行的任一阶段只需使用所占存储空间的一部分，因此，未用到的内存区域就被浪费，被占用的区域也不能提供给其他进程使用。,改进 虚拟存储管理,引进虚拟存储技术，其基本思想是： 利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，以便能够有效地支持多道程序系统的实现和大型作业运行的需要，从而增强系统的

58、处理能力。,4.6 虚拟存储器的基本概念,4.6.1 虚拟存储器的概念,1. 程序局部性原理 虚拟存储管理的效率与程序局部性程度有很大关系。 根据统计，进程运行时，在一段时间内，其程序的执行往往呈现出高度的局部性，包括时间局部性和空间局部性。,（1）时间局部性 时间局部性是指：若一条指令被执行，则在不久的将来，它可能再被执行。 在一段局部时间内，程序某一部分的数据或指令被重复性地访问，这对应于程序结构中的循环、子程序、常用到的变量及数据等。,（2）空间局部性 空间局部性是指：一旦一个存储单元被访问，那么它附近的单元也将很快被访问。 在一局部存储空间中，指令或数据被接连访问到，这对应于程序结构中

59、的顺序执行的指令、线性数据结构以及在相邻位置存放的数据或变量。,众所周知的一些事实： （1）进程的某些程序段在进程整个运行期间，可能根本不使用，如出错处理等。因而，没有必要先调入内存。 （2）互斥执行的程序段在进程运行时，根据条件只执行其中一段，如分支语句等。因而，各互斥段没有必要同时驻留内存。 （3）在进程的一次运行中，有些程序段执行完毕，从某一时刻起不再用到。因而，没有必要再占用内存区域。 根据以上分析，可以看出：程序局部性原理是虚拟存储技术引入的前提。,2. 虚拟存储器管理,对于采用实存管理的方案，要求进程执行代码一次性装入内存。而且，一旦装入内存便一直驻留到进程运行结束。 而采用虚拟存储技术，一个进程的程序可以多次分别装入内存；运行中，暂时不用部分可以换出内存，需用部分可以换进内存，且程序在内存中可以分散存放。,采用虚拟存储器，当进程要求运行时