第四章 存储器管理

1、4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3 连续连续分配存储管理分配存储管理方式方式4.4 对换对换4.5基分页存储管理方式基分页存储管理方式4.6基本分段存储管理方式基本分段存储管理方式4.1 存储器的层次结构存储器的层次结构 4.1.1 4.1.1 多级存储器结构多级存储器结构辅存辅存主存主存CPU寄存器寄存器通用计算机存储层次通用计算机存储层次可执行存储器，在时钟周可执行存储器，在时钟周期内使用指令进行访问，期内使用指令进行访问，是电子动作。是电子动作。通过通过I/O设备实现访设备实现访问，是问，是I/O动作。动作。图图4-1 完整完整 计算

2、机系统存储层次示意计算机系统存储层次示意 寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存由由OS管理，管理，断电信断电信息丢失息丢失设备设备控制控制内内快快慢慢速度速度容量容量小小大大由由OS管理，管理，断电信断电信息丢失息丢失快快慢慢容量容量小小大大设备设备控制控制由由OS管理，管理，断电信断电信息丢失息丢失快快慢慢容量容量小小大大4.1.2 4.1.2 主存储器与寄存器主存储器与寄存器 1 1主存储器主存储器 内存内存 主存主存 可执行存储器可执行存储器 用于保存进程运行时的程序和数据。用于保存进程运行时的程序和数据。 微机系统一般为数百微机系统一般为数百MB到数到数GB

3、，嵌入式计算机，嵌入式计算机系统一般仅有几十系统一般仅有几十KB到几到几MB。 CPU只能从主存储器中取得指令和数据。只能从主存储器中取得指令和数据。 主存访问速度远低于主存访问速度远低于CPU执行指令的速度，为缓执行指令的速度，为缓和这一矛盾，引入了寄存器和高速缓存。和这一矛盾，引入了寄存器和高速缓存。 2 2寄存器（寄存器（CPUCPU寄存器）寄存器） 寄存器访问速度最快，完全能与寄存器访问速度最快，完全能与CPU同步，价格同步，价格十分昂贵，容量很小。十分昂贵，容量很小。 寄存器的长度一般以字寄存器的长度一般以字(word)为单位。为单位。 微机系统，寄存器可能有几十个甚至上百个；而微机

4、系统，寄存器可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。嵌入式计算机系统一般仅有几个到几十个。 寄存器用于加速存储器的访问速度，如用地址寄寄存器用于加速存储器的访问速度，如用地址寄存器加快地址转换速度等。存器加快地址转换速度等。 4.1.3 4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存 1 1高速缓存高速缓存 容量和访问速度都介于寄存器和内存之间。容量和访问速度都介于寄存器和内存之间。 程序执行的程序执行的局部性原理局部性原理：程序在执行时在一较短程序在执行时在一较短的时间内，程序的执行仅局限于某个部分的时间内，程序的执行仅局限于某个部分。 根据局部性原理可将主存中一些

5、经常访问的信息根据局部性原理可将主存中一些经常访问的信息存放在高速缓存中，从而减少访问主存储器的次数，存放在高速缓存中，从而减少访问主存储器的次数，提高程序执行速度。提高程序执行速度。 高速缓存分高速缓存分L1L1，L2L2，L3L3级。级。 思考：靠近思考：靠近CPUCPU的是哪一级的是哪一级? ?多级多级CACHECACHE的容量哪的容量哪个大、速度哪个快？个大、速度哪个快？ 2 2磁盘缓存磁盘缓存 磁盘访问速度远低于主存的访问速度，因此将频磁盘访问速度远低于主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁

6、盘的次数。缓存中，可减少访问磁盘的次数。 磁盘缓存本身并不是一种实际存在的存储介质磁盘缓存本身并不是一种实际存在的存储介质。 主存也可以看做是辅存的高速缓存主存也可以看做是辅存的高速缓存：辅存中的数辅存中的数据必须复制到主存方能使用；反之，数据也必须先据必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。存在主存中，才能输出到辅存。 思考：思考：1.磁盘缓存到底是硬盘的一部分还是内存磁盘缓存到底是硬盘的一部分还是内存的一部分？的一部分？ 2.判断对错：一个文件的数据可能出现在存储判断对错：一个文件的数据可能出现在存储器层次的不同级别中。器层次的不同级别中。4.2程序的装入和链

7、接程序的装入和链接 将用户源程序变成可执行程序，通常要经过：将用户源程序变成可执行程序，通常要经过： 1.1.编译：由编译程序编译：由编译程序(Compiler)将用户源代码编译将用户源代码编译成成若干个目标模块若干个目标模块(Object Module)； 2.2.链接链接：由链接程序：由链接程序(Linker)将编译后形成的一组将编译后形成的一组目标模块，以及它们所需要的目标模块，以及它们所需要的库函数库函数链接在一起，形链接在一起，形成一个完整的成一个完整的装入模块装入模块(Load Module)； 3.3.装入装入：由装入程序：由装入程序(Loader)将装入模块装入内存。将装入模块

8、装入内存。图图4-2对用户程序的处理步骤对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存4.2.14.2.1程序的装入程序的装入程序的装入程序的装入1绝对装入方式绝对装入方式2静态可重定位装入方式静态可重定位装入方式3动态运行时装入方式动态运行时装入方式将目标模块整体装入到内存中事先指定的将目标模块整体装入到内存中事先指定的位置。位置。可根据内存的情况将装入模块一次性整体装可根据内存的情况将装入模块一次性整体装入到适当位置。入到适当位置。 1绝对装入方式绝对装入方式(Absolute Loading Mode) 前提条件：知道程序将驻留在内存的什么位

9、置。前提条件：知道程序将驻留在内存的什么位置。 过程：编译程序直接产生过程：编译程序直接产生绝对地址绝对地址的目标代码的目标代码即程序中的逻辑地址与实际内存地址完全相同。即程序中的逻辑地址与实际内存地址完全相同。 思考：采用该方式还需要对程序和数据的地址进思考：采用该方式还需要对程序和数据的地址进行修改吗？行修改吗？ 程序中所使用的绝对地址，既可在编译或汇编时程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。给出，也可由程序员直接赋予。 绝对装入方式只适用于单绝对装入方式只适用于单道程序环境道程序环境。 2可重定位装入方式可重定位装入方式(Relocation Loadin

10、g Mode) 多道程序环境下，不可能预知目标模块应放在内存的多道程序环境下，不可能预知目标模块应放在内存的何处，因此目标模块的起始地址是从何处，因此目标模块的起始地址是从0开始的，程序中的开始的，程序中的其它地址也都是相对于起始地址。其它地址也都是相对于起始地址。 此时应根据内存的当前情况采用此时应根据内存的当前情况采用可重定位可重定位装入方式，装入方式，将装入模块装入到内存的适当位置。将装入模块装入到内存的适当位置。 重定位：装入时对目标程序中重定位：装入时对目标程序中指令和数据指令和数据的修改过程。的修改过程。 地址变换通常是在装入时一次完成的，以后不再改变。地址变换通常是在装入时一次完

11、成的，以后不再改变。 优点：可将装入模块装入到内存中任何允许的位置优点：可将装入模块装入到内存中任何允许的位置 缺点：一旦装入则不允许程序再移动位置。缺点：一旦装入则不允许程序再移动位置。图图4-3作业装入内存时的情况作业装入内存时的情况LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间思考：如何将相对地址思考：如何将相对地址改为绝对地址？改为绝对地址？例如，用户程例如，用户程序序05000，将该用户程序将该用户程序装入到内存的装入到内存的1000015000号单元。号单元。3.3.动态运行时动态运行时

12、装入装入方式方式(Dynamic Run-time Loading)(Dynamic Run-time Loading) 由于运行过程中目标模块在内存中的位置可能要由于运行过程中目标模块在内存中的位置可能要经常改变，此时就应采用动态运行时装入的方式。经常改变，此时就应采用动态运行时装入的方式。 装入时不转换地址而是在运行时才转换装入时不转换地址而是在运行时才转换。 硬件机制：硬件机制：重定位寄存器重定位寄存器。优点：优点：1.装入内存时地址不做任何修改，因而装入后装入内存时地址不做任何修改，因而装入后可以再搬迁。可以再搬迁。如进程挂起、激活如进程挂起、激活。 2.可实现多个目标模块存放在不连续

13、的内存中。可实现多个目标模块存放在不连续的内存中。 动态运行时装入动态运行时装入+动态运行时链接动态运行时链接 4.2.24.2.2程序的链接程序的链接程程序序的的链链接接静态链接静态链接:动态链接动态链接程序进入内存之前程序进入内存之前,将各目标模块及所将各目标模块及所需的库函数链接成一个完整的装配模需的库函数链接成一个完整的装配模块，不可再分。块，不可再分。装入时动装入时动态链接态链接:运行时动运行时动态链接态链接:将编译后的一组目标模将编译后的一组目标模块，在装入内存时边装块，在装入内存时边装入边链接。入边链接。在程序执行中需要某些目标在程序执行中需要某些目标模块时，才将其进行链接。模块

14、时，才将其进行链接。1 1静态链接方式静态链接方式(Static Linking)(Static Linking) (1) 修改相对地址。修改相对地址。 每个目标模块中使用的都是相对地址即其起始每个目标模块中使用的都是相对地址即其起始地址都为地址都为0。链接成一个装入模块时，原模块起始地。链接成一个装入模块时，原模块起始地址不再是址不再是0，须修改相对地址。须修改相对地址。 (2)变换外部调用符号。变换外部调用符号。 将每个模块的外部调用符号变换为相对地址将每个模块的外部调用符号变换为相对地址。 事先进行链接所形成的一个完整的装入模块，称事先进行链接所形成的一个完整的装入模块，称为为可执行文件

15、可执行文件。 装入模块不再拆开，要运行时一次性装入内存。装入模块不再拆开，要运行时一次性装入内存。图图 4-4程序链接示意图程序链接示意图 模块 ACALL B；Return；0L-1模块 BCALL C；Return；0M-1模块 CReturn；0N-10模块 AJSR“L”Return；L-1模块 BJSR“LM”Return；LL+M-1L+ML+M+N-1模块 CReturn；(a) 目标模块(b) 装入模块2.2.装入时动态链接装入时动态链接(Load-time Dynamic Linking)(Load-time Dynamic Linking) 目标模块装入内存时边装入边链接：

16、装入目标模目标模块装入内存时边装入边链接：装入目标模块时，若发生一个外部模块调用事件，将找出相应块时，若发生一个外部模块调用事件，将找出相应的外部目标模块装入内存，并修改相对地址。装入的外部目标模块装入内存，并修改相对地址。装入时动态链接方式有以下优点：时动态链接方式有以下优点： (1) 便于修改和更新。便于修改和更新。 未装入内存前，修改或更新目标模块较为容易。未装入内存前，修改或更新目标模块较为容易。 (2)便于实现对目标模块的共享。便于实现对目标模块的共享。 OSOS很容易将一个目标模块链接到几个应用模块很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。上，实现多

17、个应用程序对该模块的共享。 静态链接、装入时链接的缺点：静态链接、装入时链接的缺点：1)1)整个运行期间模块都不能改变，实际应用时希整个运行期间模块都不能改变，实际应用时希望当某个模块出错时可独立修改再装入模块。望当某个模块出错时可独立修改再装入模块。2)2)每次运行时装入模块都是相同的，实际运行时每次运行时装入模块都是相同的，实际运行时有些模块运行后期才用或者可能根本用不到，造有些模块运行后期才用或者可能根本用不到，造成内存空间浪费。成内存空间浪费。3 3运行时动态链接运行时动态链接(Run-time Dynamic Linking)(Run-time Dynamic Linking)将所有

18、可能要运行的模块都全部装入内存，并将所有可能要运行的模块都全部装入内存，并在装入时全部链接在一起是低效的。在装入时全部链接在一起是低效的。 比如：错误处理目标模块，如果程序在整个运行比如：错误处理目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。过程中都不出现错误，则显然就不会用到该模块。 对装入时链接方式改进即运行时动态链接方式对装入时链接方式改进即运行时动态链接方式。 执行过程中，调用哪个模块则由执行过程中，调用哪个模块则由OSOS找到该模块把找到该模块把它链接到调用者模块上并将之装入内存。它链接到调用者模块上并将之装入内存。 优点优点: :加快程序装入过程；节省大量

19、内存空间。加快程序装入过程；节省大量内存空间。 4.3连续分配方式连续分配方式 连连续续分分配配1.单一连续分配单一连续分配4.动态重定位分区分配动态重定位分区分配2.固定分区分配固定分区分配3.可变分区分配可变分区分配4.3.14.3.1单一连续分配单一连续分配最简单的一种存储管理方式。最简单的一种存储管理方式。只能用于只能用于单用户单用户、单任务单任务的操作系统中的操作系统中。内内存存系统区系统区：系统区仅提供给：系统区仅提供给OS使用，通常是放使用，通常是放在内存的低址部分在内存的低址部分用户区用户区：用户区是指除系统区以外的全部内存：用户区是指除系统区以外的全部内存空间，提供给用户使用

20、。空间，提供给用户使用。4.3.24.3.2固定分区固定分区分配分配 1 1划分分区的方法：划分分区的方法： 将用户区分成固定数量的几个分区将用户区分成固定数量的几个分区, ,每个分区存每个分区存放一个用户程序。放一个用户程序。 (1) 分区大小相等。分区大小相等。 缺点缺点: :不灵活，若程序太小造成内存空间浪费；不灵活，若程序太小造成内存空间浪费； 程序太大无法则装入。程序太大无法则装入。 适用范围：利用计算机去控制多个相同对象（所适用范围：利用计算机去控制多个相同对象（所需的内存空间相等）的场合。例如，冶炼炉炉温群需的内存空间相等）的场合。例如，冶炼炉炉温群控系统。控系统。 (2) (2

21、) 分区大小不等。分区大小不等。 把用户区划分成含有多个较小的分区、适量的把用户区划分成含有多个较小的分区、适量的中等分区及少量的大分区。根据程序的大小分配适中等分区及少量的大分区。根据程序的大小分配适当的分区。当的分区。 2 2内存分配内存分配 (1)(1)将分区按大小进行排队并建立分区使用表。将分区按大小进行排队并建立分区使用表。 (2)(2)要装入时由内存分配程序检索该表要装入时由内存分配程序检索该表: : 若找到能满足要求的、尚未分配的分区则分配若找到能满足要求的、尚未分配的分区则分配并修改状态置；并修改状态置； 若未找则拒绝分配内存。若未找则拒绝分配内存。图图 4-54-5固定分区使

22、用表固定分区使用表 操作系统作业A作业B作业C24 KB32 KB64 KB128 KB256 KB分区号 大小/KB 起址/KB 状态11220已分配23232已分配36464已分配4128128未分配(b) 存储空间分配情况(a) 分区说明表4.3.34.3.3动态分区动态分区( (可变分区可变分区) )分配分配 根据进程的实际需要为之分配内存空间。根据进程的实际需要为之分配内存空间。 实现过程需解决三个问题：实现过程需解决三个问题：1.1.分区分配中的数据结构；分区分配中的数据结构；2.2.分区分配算法分区分配算法；3.3.分区的分配与回收。分区的分配与回收。 1.1.分区分配中的数据结

23、构分区分配中的数据结构系统须配置相应的数据结构用来描述系统须配置相应的数据结构用来描述空闲分区空闲分区和和已分配分区已分配分区的情况，为分配提供依据。常用的有的情况，为分配提供依据。常用的有以下两种形式：以下两种形式： (1)(1)空闲分区表。空闲分区表。 每个空闲分区占一个表目，表目包括分区序号、每个空闲分区占一个表目，表目包括分区序号、分区始址及分区的大小等数据项。分区始址及分区的大小等数据项。(2)(2)空闲分区链。单向链表、空闲分区链。单向链表、双向链表双向链表。 在每个分区的首尾部重复设置状态位和分区大小；在每个分区的首尾部重复设置状态位和分区大小；首部设置前向指针；尾部设置后向指针

24、。首部设置前向指针；尾部设置后向指针。图图4-64-6空闲链结构空闲链结构 前向指针0N个字节可用后向指针0N+2N+2i结点结点3 3分区分配操作：分配、回收分区分配操作：分配、回收1)1)分配内存分配内存 假设假设u.size:u.size:请求的分区大小；请求的分区大小； m.size:m.size:表中每个空闲分区的大小；表中每个空闲分区的大小； size:size:是事先规定的不再切割的剩余分区的大小。是事先规定的不再切割的剩余分区的大小。 若若m.size-u.sizesize,m.size-u.sizesize,不再切割将整个分区不再切割将整个分区分配分配, , 分配区的首址返回

25、给调用者；分配区的首址返回给调用者； 否则，从该分区中按请求的大小划分出一块内否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下部分仍留在空闲分区链存空间分配出去，余下部分仍留在空闲分区链( (表表) )中。中。从头开始查表检索完否？m.sizeu.size?m.size-u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN2) 2) 回收内存回收内存 从空闲区链从空闲区链( (表表) )中找到相应的插入点，此时可能出中找到相应的插入点，此时可能出现以下四种情况之一：现以下四种情况之一：

26、 (1)(1)回收区与插入点的前一个空闲分区回收区与插入点的前一个空闲分区F1F1相邻接。相邻接。方法：将回收区与插入点的前一分区合并，修改其前方法：将回收区与插入点的前一分区合并，修改其前一分区一分区F1F1的大小。的大小。前向指针0N个字节可用后向指针0N+2N+2F1回收区回收区已分配已分配 (2) 回收分区与插入点的后一空闲分区回收分区与插入点的后一空闲分区F2相邻接。相邻接。方法：将两分区合并，用回收区的首址作为新空闲区的方法：将两分区合并，用回收区的首址作为新空闲区的首址，大小为两者之和。首址，大小为两者之和。前向指针0N个字节可用后向指针0N+2N+2F2回收区回收区已分配已分配

27、F2F2已分配已分配F2 (3) (3)回收区同时与插入点的前、后两个分区邻接。回收区同时与插入点的前、后两个分区邻接。方法：将三个分区合并使用方法：将三个分区合并使用F1F1表项和表项和F1F1首址，取消首址，取消F2F2的表项，新分区大小为三者之和。的表项，新分区大小为三者之和。前向指针0N个字节可用后向指针0N+2N+2F2回收区回收区已分配已分配F2F2F1F2F1 (4) 回收区既不与回收区既不与F1邻接，又不与邻接，又不与F2邻接。邻接。方法：为回收区单独建立一新表项，填写回收区的方法：为回收区单独建立一新表项，填写回收区的首址和大小，根据首址插入到空闲链中适当位置。首址和大小，根

28、据首址插入到空闲链中适当位置。前向指针0N个字节可用后向指针0N +2N +2回收区回收区已分配已分配F2已分配已分配已分配已分配分分区区分分配配算算法法2.分类分类搜索分搜索分配算法配算法1.顺序顺序搜索分搜索分配算法配算法NFFFWF：QF：链表按空闲区地址链表按空闲区地址从低到高排序从低到高排序BF：链表按空闲区容量从链表按空闲区容量从小到大排序小到大排序容量相等的空闲区容量相等的空闲区组成一个链表组成一个链表链表按空闲区容量从链表按空闲区容量从大到小排序大到小排序1 1. .首次首次适应算法适应算法(first fit) (first fit) FF FF 空闲分区链以地址递增的次序链

29、接。空闲分区链以地址递增的次序链接。 每次从链首开始顺序查找，若找到第一个大小合适的每次从链首开始顺序查找，若找到第一个大小合适的空闲分区，按作业的大小从该分区中划出相应内存空间，空闲分区，按作业的大小从该分区中划出相应内存空间，余下的空闲分区仍留在空闲链中。余下的空闲分区仍留在空闲链中。 若从链首直至链尾都不能找到一个能满足要求的分区，若从链首直至链尾都不能找到一个能满足要求的分区，则内存分配失败、则内存分配失败、返回链首返回链首。 优点：高址部分大空闲区较多。为以后到达的大作业预优点：高址部分大空闲区较多。为以后到达的大作业预留了空间。留了空间。 缺点：低址部分留下许多碎片；每次查找又都是

30、从低址缺点：低址部分留下许多碎片；每次查找又都是从低址部分开始，查找效率低；找到的不一定最合适。部分开始，查找效率低；找到的不一定最合适。 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法以空闲分区链为例以空闲分区链为例2.2.循环循环首次适应算法首次适应算法(next fit) (next fit) NFNF 分配内存空间时，从上次找到的空闲分区的下分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找。一个空闲分区开始查找。 实现方法：实现方法： 设置设置起始查寻指针：起始查寻指针：用于指示下一次起始查用于指示下一次起始查寻的空闲分区，找到后，调整起始查寻指针

31、；寻的空闲分区，找到后，调整起始查寻指针； 采用循环查找方式。采用循环查找方式。 优点：内存中的空闲分区分布得更均匀；减少优点：内存中的空闲分区分布得更均匀；减少了查找空闲分区时的开销。了查找空闲分区时的开销。 缺点：缺乏大的空闲分区。缺点：缺乏大的空闲分区。 3.3.最佳最佳适应算法适应算法(best fit) (best fit) BFBF 找能满足要求的最小的空闲分区分配。找能满足要求的最小的空闲分区分配。 空闲分区空闲分区按容量从小到大链接按容量从小到大链接。 第一次找到的满足要求的空闲区必然是最佳的。第一次找到的满足要求的空闲区必然是最佳的。 优点：对每个进程而言都是最合适的。优点：

32、对每个进程而言都是最合适的。 缺点：每次分配后所切割下来的剩余部分总是最缺点：每次分配后所切割下来的剩余部分总是最小的，存储器中碎片过多。小的，存储器中碎片过多。 4.4.最坏最坏适应算法适应算法(worst fit) (worst fit) WFWF 空闲分区按容量从大到小链接。空闲分区按容量从大到小链接。 分配时总是挑最大的空闲区分配。分配时总是挑最大的空闲区分配。 优点：产生碎片的几率最小，查找效率较高。优点：产生碎片的几率最小，查找效率较高。 缺点：存储器中缺乏大的空闲分区。缺点：存储器中缺乏大的空闲分区。 WFWF算法对中、小作业有利，算法对中、小作业有利，1.1.快速快速适应算法适

33、应算法(quick fit)(quick fit) 系统中有多个空闲分区链表，每个链表中分区容量相系统中有多个空闲分区链表，每个链表中分区容量相等。等。 没有相等容量的分区放在特殊空闲区链表中。没有相等容量的分区放在特殊空闲区链表中。 内存中设立索引表，每一个表项对应一种空闲分区类内存中设立索引表，每一个表项对应一种空闲分区类型，并记录该类型链表表头的指针。型，并记录该类型链表表头的指针。 空闲分区的分类是根据进程常用的空间大小进行划分，空闲分区的分类是根据进程常用的空间大小进行划分，如如2KB2KB、4KB4KB、8KB8KB等。等。 如如7KB7KB这样的空闲区，既可以放在这样的空闲区，既

34、可以放在8KB8KB的链表中，也可的链表中，也可以放在特殊空闲区链表中以放在特殊空闲区链表中4.3.54.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法 优点：查找效率高；分配时不对分区分割，优点：查找效率高；分配时不对分区分割，能保留大的分区，也不会产生内存碎片。能保留大的分区，也不会产生内存碎片。缺点：分区归还主存时算法复杂，系统开销缺点：分区归还主存时算法复杂，系统开销较大。为进程所分配的一个分区中，存在空间较大。为进程所分配的一个分区中，存在空间浪费。浪费。 是典型的以空间换时间的作法。是典型的以空间换时间的作法。2.2.伙伴系统伙伴系统 固定分区：限制了活动进程

35、的数目，当进程大小与固定分区：限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。空闲分区大小不匹配时，内存空间利用率很低。 动态分区：算法复杂，回收时需要进行分区合并，动态分区：算法复杂，回收时需要进行分区合并，系统开销较大。系统开销较大。 伙伴系统是对以上两种方式的折衷。伙伴系统是对以上两种方式的折衷。伙伴系统规定，伙伴系统规定，无论已分配分区或空闲分区，其大无论已分配分区或空闲分区，其大小均为小均为2 2的的k k次幂次幂，lkmlkm。 假设系统开始运行时，整个内存区是一个大小为假设系统开始运行时，整个内存区是一个大小为2 2m m的的空闲分区。空闲分区。 将空

36、闲分区根据大小进行分类，对每一类相同将空闲分区根据大小进行分类，对每一类相同大小的空闲分区设立一个双向链表。大小的空闲分区设立一个双向链表。1.1.分配：分配： 若需要大小为若需要大小为n n的空间，找的空间，找2 2i-1i-1n2=TLS=TL，表示访问越界，于是产生越，表示访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址存的起始地址; ; 2) 2)再检查段内地址再检查段内地址d d是否超过该段的段长是否超过该段的

37、段长SLSL。若超。若超过，发出越界中断信号；若未越界，则将该段的基址过，发出越界中断信号；若未越界，则将该段的基址d d与段内地址相加，即可得到要访问的内存物理地址。与段内地址相加，即可得到要访问的内存物理地址。图图4-184-18分段系统的地址变换过程分段系统的地址变换过程 控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址像分页系统一样，当段表放在内存中时，每要访问像分页系统一样，当段表放在内存中时，每要访问一个数据，一个数据，都须访问两次内存都须访问两次内存，从而极大

38、地降低了计算，从而极大地降低了计算机的速率。解决的方法也和分页系统类似，再增设一个机的速率。解决的方法也和分页系统类似，再增设一个联想存储器联想存储器，用于保存最近常用的段表项。由于一般情，用于保存最近常用的段表项。由于一般情况是段比页大，因而段表项的数目比页表项的数目少，况是段比页大，因而段表项的数目比页表项的数目少，其所需的联想存储器也相对较小，便可以显著地减少存其所需的联想存储器也相对较小，便可以显著地减少存取数据的时间，比起没有地址变换的常规存储器的存取取数据的时间，比起没有地址变换的常规存储器的存取速度来仅慢约速度来仅慢约10%10%15%15%。 4 4分页和分段的主要区别分页和分

39、段的主要区别由上所述不难看出，分页和分段系统有许多相似之由上所述不难看出，分页和分段系统有许多相似之处。比如，两者都采用离散分配方式，且都要通过地址处。比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面。主要表现在下述三个方面。(1) (1) 页是信息的页是信息的物理物理单位，单位，分页是为实现离散分配分页是为实现离散分配方式，以消减内存的外零头方式，以消减内存的外零头，提高内存的利用率。或者，提高内存的利用率。或者说，分页仅仅是由于说，分页仅仅是由于系统管理的需要系统管理的需要而不

40、是用户的需要。而不是用户的需要。段则是信息的段则是信息的逻辑逻辑单位，它含有一组其意义相对完整的单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。信息。分段的目的是为了能更好地满足用户的需要。 (2) (2) 页的页的大小固定且由系统决定大小固定且由系统决定，由系统把逻辑地，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由固定，决定于用户所编写的程序，通常由编译程序编译程

41、序在对在对源程序进行编译时，根据信息的性质来划分。源程序进行编译时，根据信息的性质来划分。(3) (3) 分页分页的作业地址空间是的作业地址空间是一维一维的，即单一的线性的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址空间，程序员只需利用一个记忆符，即可表示一个地址；而地址；而分段分段的作业地址空间则是的作业地址空间则是二维二维的，程序员在标的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。识一个地址时，既需给出段名，又需给出段内地址。 4.5.34.5.3信息共享信息共享分段系统的一个突出优点，是易于实现段的共享，。分段系统的一个突出优点，是易于实现段的共享，。

42、在分页系统中，远不如分段系统来得方便。在分页系统中，远不如分段系统来得方便。 例如，有一个多用户系统，可同时接纳例如，有一个多用户系统，可同时接纳4040个用户，个用户，他们都执行一个文本编辑程序他们都执行一个文本编辑程序(Text Editor)(Text Editor)。如果文。如果文本编辑程序有本编辑程序有160 KB160 KB的代码和另外的代码和另外40 KB40 KB的数据区，则的数据区，则总共需有总共需有 8 MB8 MB的内存空间来支持的内存空间来支持4040个用户。如果个用户。如果160 160 KBKB的代码是的代码是可重入可重入的的(Reentrant)(Reentran

43、t)，则无论是在分页系，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间需保留一份文本编辑程序的副本，此时所需的内存空间仅为仅为1760 KB(401760 KB(4040+160)40+160)，而不是，而不是8000 KB8000 KB。 假定每个页面的大小为假定每个页面的大小为4 KB4 KB，那么，那么，160 KB160 KB的代码的代码将占用将占用4040个页面，数据区占个页面，数据区占1010个页面。为实现代码的共个页面。为实现代码的共享，应在每个进程的页表中都建立享，

44、应在每个进程的页表中都建立4040个页表项，它们的个页表项，它们的物理块号都是物理块号都是21#21#60#60#。在每个进程的页表中，还须为。在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是自己的数据区建立页表项，它们的物理块号分别是61#61#70#70#、71#71#80#80#、81#81#90#90#，等等。图，等等。图4-194-19是是分页系统中共享分页系统中共享editoreditor的示意图。的示意图。 图图4-194-19分页系统中共享分页系统中共享editoreditor的示意图的示意图 ed 1ed 2ed 40data 1data 10进程121

45、22606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表在分段系统中，实现共享则容易得多，只需在每个在分段系统中，实现共享则容易得多，只需在每个进程的段表中为文本编辑程序设置一个段表项。图进程的段表中为文本编辑程序设置一个段表项。图4-204-20是分段系统中共享是分段系统中共享editoreditor的示意图。的示意图。 图 4-20分段系统中共享editor的示意图 editor进程1data 1进程2editordata 2段表段长

46、基址16080402401608040380editordata 1data 280240280380420可重入代码可重入代码(Reentrant Code)(Reentrant Code)又称为又称为“纯代纯代码码”(Pure Code)(Pure Code)，是一种允许多个进程同时访问的代码。，是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。入代码在执行中有任何改变。 可重入代码不允许任何进程对它进行修改。但事实上，可重入代码不允许任何进程对它进行修改。但事实上，大多数代码在执行时

47、都可能有些改变，例如，用于控制大多数代码在执行时都可能有些改变，例如，用于控制程序执行次数的变量以及指针、信号量及数组等。程序执行次数的变量以及指针、信号量及数组等。 为此，在每个进程中，都必须配以为此，在每个进程中，都必须配以局部数据区局部数据区，把在，把在执行中可能改变的部分拷贝到该数据区，这样，程序在执行中可能改变的部分拷贝到该数据区，这样，程序在执行时，只需对该数据区执行时，只需对该数据区( (属于该进程私有属于该进程私有) )中的内容进中的内容进行修改，并不去改变共享的代码，这时的可共享代码即行修改，并不去改变共享的代码，这时的可共享代码即成为可重入码。成为可重入码。 4.6.44.6.4段页式存储管理方式段页式存储管理方式