计算机操作系统第4章

1、1 1第四章 存 储 器 管 理第四章第四章 存存 储储 器器 管管 理理4.1 存储器的层次结构4.2 程序的装入和链接4.3 连续分配存储管理方式4.4 对换(Swapping)4.5 分页存储管理方式4.6 分段存储管理方式2 2第四章 存 储 器 管 理4.1 存储器的层次结构在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟得上处理机的运行速度。或者说，存储器的速度必须非常快，能与处理机的速度相匹配，否则会明显地影响到处理机的运行。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。 3 3第四章 存 储 器 管 理4.1.1 多层结构的存储

2、器系统1. 存储器的多层结构 对于通用计算机而言，存储层次至少应具有三级：最高最高层为层为CPU寄存器，中间为主存，最底层是辅存寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示。 4 4第四章 存 储 器 管 理图4-1 计算机系统存储层次示意主存辅存5 5第四章 存 储 器 管 理2. 可执行存储器在计算机系统的存储层次中，寄存器和主存储器又被称寄存器和主存储器又被称为可执行存储器为可执行存储器。对于存放于其中的信息，与存放于辅存中的信息相比较而言，计算机所采用的访问机制是不同

3、的，所需耗费的时间也是不同的。进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问。但对辅存的访问则需要通过I/O设备实现，因此，在访问中将涉及到中断、设备驱动程序以及物理设备的运行，所需耗费的时间远远高于访问可执行存储器的时间，一般相差3个数量级甚至更多。6 6第四章 存 储 器 管 理4.1.2 主存储器与寄存器1. 主存储器主存储器简称内存或主存内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。2. 寄存器寄存器具有与处理机相同的速度，故对寄存器的访问速寄存器的访问速度最快度最快，完全能与CPU协调工作，但价格却十分昂贵，

4、因此容量不可能做得很大。 7 7第四章 存 储 器 管 理4.1.3 高速缓存和磁盘缓存1. 高速缓存高速缓存是现代计算机结构中的一个重要部件，它是介介于寄存器和存储器之间的存储器于寄存器和存储器之间的存储器，主要用于备份主存中较常备份主存中较常用的数据，以用的数据，以减少处理机对主存储器的访问次数减少处理机对主存储器的访问次数，这样可大，这样可大幅度地提高程序执行速度幅度地提高程序执行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 8 8第四章 存 储 器 管 理2. 磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和

5、两者之间在速度上的不匹配，而设置了磁盘缓存，主磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少以减少访问磁盘的次数访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。9 9第四章 存 储 器 管 理4.2 程序的装入和链接用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：(

6、1) 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module)；(2) 链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；(3) 装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。10 10第四章 存 储 器 管 理图4-2对用户程序的处理步骤11 11第四章 存 储 器 管 理4.2.1 程序的装入1. 绝对装入方式(Absolute Loading Mode)编译时，若知道程序将驻留在内存的某位置，则编译程序将产生绝对

7、地址的目标代码，绝对装入程序按照装入模块的地址，将程序和数据直接装入指定内存。该地址既可在编译和汇编时给出，也可以由程序员直接赋予。程序员直接给程序员直接给出绝对地址，使得程序修改时很可能要修改所有地址。因此出绝对地址，使得程序修改时很可能要修改所有地址。因此宁可在程序中采用符号地址，在编译时再去转换成绝对地址宁可在程序中采用符号地址，在编译时再去转换成绝对地址。单道程序环境下，可用此种方式。 而在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址，都相对于起始地址计算。这样的模块称为相对装入模块。12 12第四章 存 储 器 管 理程序程序JUMP iLOAD jDATAJUM

8、P 400LOAD 1200JUMP 1424LOAD 2224符号地址绝对地址相对地址ij10241424222404001200绝对和可重定位装入模块绝对和可重定位装入模块（a）目标模块（b）绝对装入模块（c）相对装入模块13 13第四章 存 储 器 管 理2. 可重定位装入方式(Relocation Loading Mode)把在装入时对目标程序中的指令和数据地址的修改过程称为重定位重定位。 对于相对装入模块，应采用可重定位装入方式来把装入模块装入内存。 装入相对装入模块时，装入程序要将模块的起始地址与装入程序要将模块的起始地址与内存某位置的地址相加，才能将模块定位到正确的物理地址内存某

9、位置的地址相加，才能将模块定位到正确的物理地址，同样，模块中的指令地址和数据地址都要相应修改。 因地址变换只是在装入时一次完成，以后不再改变，故称为静态重定位。14 14第四章 存 储 器 管 理LOAD 1,2500365 0 1000 2500 5000作业地址空间LOAD 1,12500365 11000 12500 15000内存空间图4-3 作业装入内存时的情况 1000015 15第四章 存 储 器 管 理3. 动态运行时的装入方式(Dynamic Run-time Loading)多道程序环境下，程序在内存的位置可能要经常改变，如进程的换入换出，每次换入到内存的位置一般是不同的，

10、这样，就应采用动态运行时的装入方式。 动态运行时的装入程序，把装入模块装入内存后，并不把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是等到程立即把装入模块中的相对地址转换为绝对地址，而是等到程序真正要执行时才进行地址转换序真正要执行时才进行地址转换(转换时机的把握转换时机的把握)。因此，装入内存后的所有地址仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一定的特殊硬件的支持。16 16第四章 存 储 器 管 理4.2.2 程序的链接 实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。1、静态链接：模块模块A CALL B:RETURN模块模块B

11、 CALL C:RETURN模块模块C RETURN模块模块A JSR “L”RETURN模块模块B JSR “L+M”RETURN模块模块C RETURN0L-10M-10N-10L-1LL+M-1L+ML+M+N-1需要解决的需要解决的两个问题：两个问题：1、对相对地、对相对地址进行修改址进行修改2、变换外部、变换外部调用符号调用符号目标模块目标模块装入模块装入模块图4-4程序链接示意图17 17第四章 存 储 器 管 理2. 装入时动态链接(Load-time Dynamic Linking)这是指将用户源程序编译后所得到的一组目标模块，在在装入内存时，采用边装入边链接的链接方式装入内存

12、时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式修改目标模块中的相对地址。装入时动态链接方式有以下优点：(1) 便于修改和更新。(2) 便于实现对目标模块的共享。 18 18第四章 存 储 器 管 理3. 运行时动态链接(Run-time Dynamic Linking)这种链接方式，可将某些目标模块的链接，推迟到执行可将某些目标模块的链接，推迟到执行时才进行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上

13、。 前述的动态装入方式，可将装入模块装入到内存的任何位置。但装入模块的结构是静态的，这里的静态是指：一，在进程的整个执行期间，模块是不改变的；二，每次运行时的装入模块都是相同的。而实际上，每次要运行的模块可能是不同的，但装入时只能将所有可能要运行的模块全部链接在一起，使每次执行时的装入模块是相同的。19 19第四章 存 储 器 管 理4.3 连续分配存储管理方式4.3.1 单一连续分配在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配

14、方式被称为单一连续分配方式。2020第四章 存 储 器 管 理4.3.2 固定分区分配1. 划分分区的方法(1) 分区大小相等(指所有的内存分区大小相等)。(2) 分区大小不等。将内存划分出多个较小的分区，适量的中等分区和少量的大分区。 2. 内存分配为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，如图4-5所示。 21 21第四章 存 储 器 管 理图4-5 固定分区使用表2222第四章 存 储 器 管 理4.3.3 动态分区分配1. 动态分区分配中的数据结构 常用的数据结构有以下两种形式： 空闲分区表空闲分

15、区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项分区始址等数据项，如图4-6所示。 空闲分区链空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息控制分区分配的信息，以及用于链接各分区所用的前前向指针向指针，在分区尾部则设置一后向指针后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链双向链，如图4-7所示。 2323第四章 存 储 器 管 理3. 分区分配操作1) 分配内存系统应利用某种分配算法，从空闲分

16、区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。 2424第四章 存 储 器 管 理图4-8内存分配流程2525第四章 存 储 器 管 理2) 回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： (1) 回收区与插入点的前一个空闲分区F1相邻接。(2) 回收分区与插入点的后一空闲分区F2相邻接。(3) 回收区同时与插入点的前、后两个分区邻接。(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项单独建立一个新表项，填写回收区的首址和大小，

17、并根据其首址插入到空闲链中的适当位置。图4-10示出了内存回收时的流程。2626第四章 存 储 器 管 理图4-10 内存回收流程2727第四章 存 储 器 管 理4.3.4 基于顺序搜索的动态分区分配算法1. 首次适应(first fit，FF)算法该算法要求分区链以地址递增的次序链接。内存分配时，内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空从链首开始顺序查找，直至找到一个能满足其大小要求的空闲区为止闲区为止。然后，再按照作业的大小，从该区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲链中。 该算法倾向于优先利用内存中低址部分的空闲区，高址倾向于优先利用内存中低址部

18、分的空闲区，高址部分的很少利用，从而保留了高址部分的大空闲区，为以后部分的很少利用，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件到达的大作业分配大的内存空间创造了条件。但低址部分留低址部分留下许多难以利用的很小的空闲区下许多难以利用的很小的空闲区 ，每次查找又都从低址部每次查找又都从低址部分开始，这样，增加了查找开销分开始，这样，增加了查找开销。2828第四章 存 储 器 管 理2. 循环首次适应(next fit，NF)算法由FF算法演变而来，分配内存时，不再每次从链首开始不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查查找，而是从上次找到

19、的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲分区找，直到找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间。 为实现该算法，应设置一起始查询指针，并采用循环查找方式。该算法能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销，但这会缺乏大的空闲分区。2929第四章 存 储 器 管 理3. 最佳适应(best fit，BF)算法 “最佳”的含义是指每次为作业分配内存时，总是把既能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为加速查询，该算法要求将所有的空闲区按其大小以该算法要求将所有的空闲区按其大小以递增的顺序链接成一空闲区链递增的顺序链接

20、成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。孤立地看，这似乎是最佳的，但从宏观上看却不一定。因为每次分配后所切割下的剩余部分，总是最小的，在存储器中会留下许多难以利用的小空闲区。3030第四章 存 储 器 管 理4. 最坏适应(worst fit，WF)算法由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。 该算法要求将所有空闲分区，按容量从大到小的顺序，该

21、算法要求将所有空闲分区，按容量从大到小的顺序，形成一空闲分区链，查找时，只要看第一个分区能否满足作形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。业要求即可。31 31第四章 存 储 器 管 理动态分区示例：请使用下动态分区示例：请使用下面的算法再分配一个面的算法再分配一个16M的内存空间？的内存空间？1.首次适应（First fit）2.循环首次适应（Next fit）3.最佳适应（Best fit）4.最坏适应（Worst fit）3232第四章 存 储 器 管 理最佳适应最佳适应首次适应首次适应循环首次适应循环首次适应最坏适应最坏适应3333第四章 存 储 器 管 理4.

22、3.5 基于索引搜索的动态分区分配算法1. 快速适应(quick fit)算法将空闲分区根据其容量大小进行分类。为每一类分区单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，每个表项对应一种空闲分区类型，并记录空闲分区链表的表头指针。空闲分区的分类是根据进程常用的空间大小进行划分。 该算法在搜索空闲分区时分二步：第一步是根据进程长度从索引表中找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配。3434第四章 存 储 器 管 理2. 伙伴系统(buddy system)该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，lkm)，其中2l表示分配的最小块的

23、尺寸，2m表示分配的最大的块的尺寸。通常， 2m是可供分配的整个内存的大小。 （1）开始时，可用于分配的整个空间被看成是一个大小为2m的块； （2）如果请求的大小s满足2m-1 s = 2m ，则分配整个空间；否则，该块被分成两个大小相等的伙伴，均为2m-1 ，如果有2m-2 s 2100段号S段长基址1K6K6004K5008K2009200段号0321+82928K82928692有效地址物理地址主存位移量段表寄存器越界7373第四章 存 储 器 管 理4. 分页和分段的主要区别 分页和分段系统有许多相似之处，但在概念上二者完全不同： （1）页是信息的物理单位，仅仅是出于系统管理的需要；段是信息的逻辑单位，其目的是满足用户的需要。 （2）页的大小固定且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户所编写的程序。 （3）分页的作业地址空间是一维的；分段的作业地址空间是二维的。7474第四章 存 储 器 管 理4.6.4 段页式存储管理方式1. 基本原理段页式系统的基本原理是分段和分页原理的结合，即先即先将用户程序分成若干个段，再把每个段分成若干个页，并为将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名每一个段赋予一个段名。在段页式系统