第四章存储器管理

1、东北农业大学东北农业大学王艳王艳操作系统原理操作系统原理第四章第四章 存储器管理存储器管理进程管理进程管理处理机分配处理机分配内存分配内存分配第四章第四章 存储器管理存储器管理1 1 存储器的多层结构存储器的多层结构CPUCPU寄存器寄存器4.1.1 4.1.1 多层结构的存储器系统多层结构的存储器系统主存主存 辅存辅存n 4.1 存储器的层次结构存储器的层次结构 高速缓存高速缓存主存主存磁盘缓存磁盘缓存可执行存储器，可执行存储器，OS管理管理可移动存储介质可移动存储介质磁盘磁盘设备管理设备管理第四章第四章 存储器管理存储器管理2 2 对比对比从上到下：从上到下：4.1.1 4.1.1 多级存

2、储器结构多级存储器结构n 4.1 存储器的层次结构存储器的层次结构 访问速度越来越慢访问速度越来越慢存储容量越来越大存储容量越来越大价格越来越低价格越来越低第四章第四章 存储器管理存储器管理1 1 主存储器主存储器主存（内存）主存（内存）4.1.2 4.1.2 主存储器与寄存器主存储器与寄存器n 4.1 存储器的层次结构存储器的层次结构 几十几十MBMB几几GBGB和和CPUCPU直接交换数据直接交换数据第四章第四章 存储器管理存储器管理2 2 寄存器寄存器4.1.2 4.1.2 主存储器和寄存器主存储器和寄存器n 4.1 存储器的层次结构存储器的层次结构 速度最快，价格最贵速度最快，价格最贵

3、几十个几十个几百个几百个第四章第四章 存储器管理存储器管理1 1 高速缓存高速缓存4.1.3 4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存n 4.1 存储器的层次结构存储器的层次结构 容量、速度介于主存和寄存器之间容量、速度介于主存和寄存器之间利用程序执行的局部性原理利用程序执行的局部性原理多级高速缓存多级高速缓存备份主存中较常用的数据，减少主存访问次数备份主存中较常用的数据，减少主存访问次数第四章第四章 存储器管理存储器管理2 2 磁盘缓存磁盘缓存缓和磁盘的缓和磁盘的I/O速度远低于对主存的访问速度速度远低于对主存的访问速度4.1.3 4.1.3 高速缓存和磁盘缓存高速缓存和磁盘缓存n

4、4.1 存储器的层次结构存储器的层次结构 内存的一部分内存的一部分目的是减少访问磁盘的次数目的是减少访问磁盘的次数第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 运行程序运行程序 创建进程创建进程 程序数据装入内存程序数据装入内存 源程序源程序 目标模块目标模块 装入模块装入模块 可执行程序可执行程序 编译编译链接链接装入装入库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 4.2.1 4.2.1 程序的装入程序的装入1 1 相对地址和绝对地址相对地址和绝对地址相

5、对相对地址：从地址：从0开始编号（逻辑地址）开始编号（逻辑地址）绝对绝对地址：内存中存储单元的物理地址（物理地地址：内存中存储单元的物理地址（物理地址）址）虚拟地址虚拟地址实际地址实际地址地址转换的时期不同决定装入方式的不同地址转换的时期不同决定装入方式的不同第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 2 2 程序中的地址程序中的地址（1）指令地址：程序本身所处的地址）指令地址：程序本身所处的地址4.2.1 4.2.1 程序的装入程序的装入（2 2）数据中的地址：程序中涉及的地址）数据中的地址：程序中涉及的地址（3 3）例子）例子1000Load 1,250

6、025003655000数据中的地址数据中的地址指令地址指令地址第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 3 3 装入方式装入方式（1）绝对装入方式）绝对装入方式4.2.1 4.2.1 程序的装入程序的装入前提：预先知道程序驻留内存的什么位置前提：预先知道程序驻留内存的什么位置过程：编译时直接产生绝对地址；过程：编译时直接产生绝对地址； 程序中所用的绝对地址可由程序员给出；程序中所用的绝对地址可由程序员给出； 或采用符号地址，编译时转换。或采用符号地址，编译时转换。优缺点：优缺点： 只适合于单道程序环境只适合于单道程序环境第四章第四章 存储器管理存储器管理

7、n 4.2 程序的装入和链接程序的装入和链接 （2）可重定位装入方式）可重定位装入方式4.2.1 4.2.1 程序的装入程序的装入适用于多道程序环境下适用于多道程序环境下过程：过程：特点：特点： 易实现，无需硬件支持易实现，无需硬件支持 重定位后不能移动重定位后不能移动 程序在存储空间中只能连续分配程序在存储空间中只能连续分配 用户很难共享同一程序，若共享，使用自己的副体用户很难共享同一程序，若共享，使用自己的副体LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间1第四章第四章 存储器管理存储器管理n

8、4.2 程序的装入和链接程序的装入和链接 （3）动态运行时装入方式）动态运行时装入方式4.2.1 4.2.1 程序的装入程序的装入适用于要求程序在内存空间移动适用于要求程序在内存空间移动过程：程序原封不动装入内存过程：程序原封不动装入内存 用寄存器记录偏移地址用寄存器记录偏移地址 在程序执行时再转换地址在程序执行时再转换地址例子例子 第四章第四章 存储器管理存储器管理（3）动态运行时装入方）动态运行时装入方式式4.2.1 4.2.1 程序的装入程序的装入327MOV AX, 100050100199100VR1000BR1100MR+327MOV AX, 1001000105011001199

9、200LR程序地址空间内存空间第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 1 静态链接静态链接4.2.2 4.2.2 程序的链接程序的链接（1）程序运行之前进行）程序运行之前进行（2）链接后，模块不再拆开）链接后，模块不再拆开（3）例子）例子 模块 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) 装入模块第四章第四章 存储器管理存储器管理n

10、4.2 程序的装入和链接程序的装入和链接 2 装入时链接装入时链接4.2.2 4.2.2 程序的链接程序的链接（1）边装入边链接）边装入边链接（2）便于修改）便于修改（3）便于对目标模块共享）便于对目标模块共享第四章第四章 存储器管理存储器管理n 4.2 程序的装入和链接程序的装入和链接 3 运行时动态链接运行时动态链接4.2.2 4.2.2 程序的链接程序的链接（1）无法了解用哪些模块，全加载则低效）无法了解用哪些模块，全加载则低效（2）运行时用哪个模块链接相应模块）运行时用哪个模块链接相应模块第四章第四章 存储器管理存储器管理CPUCPU寄存器寄存器主存主存 辅存辅存高速缓存高速缓存主存主

11、存磁盘缓存磁盘缓存可执行存储器，可执行存储器，OS管理管理可移动存储介质可移动存储介质磁盘磁盘设备管理设备管理程序的装入和链接程序的装入和链接第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 1 1 适用于单任务、单用户的操作系统适用于单任务、单用户的操作系统4.3.1 4.3.1 单一连续分配单一连续分配2 2作业操作系统未用32 KB64 KB160 KB分配给用户作业的空间3 3 特点：特点： 单道单道 浪费严重浪费严重第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 1 1 思想：内存划定固定大小分区，每个分区一道作思想：内存划定固定大小分区，每个分区一道作

12、 业，建立一张注册业，建立一张注册表4.3.2 4.3.2 固定分区分配固定分区分配2 2 分区划法分区划法（1 1）分区大小相等）分区大小相等太小，装不下，程序无法运行太小，装不下，程序无法运行太大，内存浪费太大，内存浪费适于操作同类的多个任务适于操作同类的多个任务第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.2 4.3.2 固定分区分配固定分区分配（2 2）分区大小不等）分区大小不等多个小分区，若干个中分区，少量大分区多个小分区，若干个中分区，少量大分区3 内存分配内存分配（1）分区按大小排队，建一张分区使用表）分区按大小排队，建一张分区使用表（2）有程序使用时，

13、检索表）有程序使用时，检索表（3）例子）例子Page 23第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 分区号分区号容量容量起始地址起始地址状态状态1816已分配已分配21624未分配未分配33240已分配已分配46472未分配未分配5120136未分配未分配4.3.2 4.3.2 固定分区分配固定分区分配作业名作业名ABCDE容量容量423204090分配情况分配情况已分配已分配已分配已分配未分配未分配未分配未分配未分配未分配OS区区 016244072136255分区分区1分区分区2分区分区3分区分区4分区分区5作业作业A4KB作业作业B9KB作业作业C44KB作业作业D

14、80KBE90未分配未分配内存使用率：内存使用率：87/256=0.34第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.2 4.3.2 固定分区分配固定分区分配4 4 特点特点（1）简单，实现了多道程序）简单，实现了多道程序（2）内存利用率低）内存利用率低 碎片多碎片多作业受分区大小限制作业受分区大小限制第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配根据进程实际需要，动态的为之分配内存根据进程实际需要，动态的为之分配内存1 分区分配所用的数据结构分区分配所用的数据结构 （1）空闲分区表）空闲分区表 分区号

15、、分区起始地址、分区大小分区号、分区起始地址、分区大小（2）空闲分区链）空闲分区链前向指针0N 个字节可用后向指针0N+2N+2第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配2 2 分区分配算法分区分配算法（1） 首次适应算法首次适应算法 （6 6） 伙伴系统伙伴系统（3 3） 最佳适应算法最佳适应算法（4 4） 最坏适应算法最坏适应算法（5 5） 快速适应算法快速适应算法（2 2） 循环首次适应算法循环首次适应算法（7 7） 哈希算法哈希算法基于顺序搜索基于顺序搜索基于索引搜索基于索引搜索第四章第四章 存储器管理存储器管理n

16、4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配3 3 分区分配操作分区分配操作（1） 分配内存分配内存从头开始查表检索完否？m.sizeu.size?m.size-u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配2 2 分区分配操作分区分配操作（2） 内存回收内存回收 回收区与插入点的前回收区与插入点的前一个空闲分区一个空闲分区F1相邻接，相邻接，见图见图

17、 (a)。此时应将回收。此时应将回收区与插入点的前一分区区与插入点的前一分区合并，不必为回收分区合并，不必为回收分区分配新表项，而只需修分配新表项，而只需修改其前一分区改其前一分区F1的大小。的大小。第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配2 2 分区分配操作分区分配操作（2） 内存回收内存回收 回收分区与插入点的回收分区与插入点的后一空闲分区后一空闲分区F2相邻接，相邻接，见图见图(b)。此时也可将两。此时也可将两分区合并，形成新的空分区合并，形成新的空闲分区，但用回收区的闲分区，但用回收区的首址作为新空闲区的首首址作为

18、新空闲区的首址，大小为两者之和。址，大小为两者之和。 第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配2 2 分区分配操作分区分配操作（2） 内存回收内存回收 回收区同时与插入点回收区同时与插入点的前、后两个分区邻接，的前、后两个分区邻接，见图见图(c)。此时将三个分。此时将三个分区合并，使用区合并，使用F1的表项的表项和和F1的首址，取消的首址，取消F2的的表项，大小为三者之和。表项，大小为三者之和。第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.3 4.3.3 动态分区分配动态分区分配2 2 分区分配操

19、作分区分配操作（2） 内存回收内存回收 回收区既不与回收区既不与F1邻接，又不与邻接，又不与F2邻接。这时应为邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。并根据其首址插入到空闲链中的适当位置。 第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法1 首次适应算法（首次适应算法（FF） 基本思想基本思想空闲分区链以地址递增的次序链接空闲分区链以地址递增的次序链接从链首开始顺序查找，直至找到一个大小能

20、满足要求从链首开始顺序查找，直至找到一个大小能满足要求 的空闲分区为止；的空闲分区为止；从该分区中划出一块内存空间分配给请求者，余下的从该分区中划出一块内存空间分配给请求者，余下的 空闲分区仍留在空闲链中空闲分区仍留在空闲链中若从链首直至链尾都不能找到一个能满足要求的分若从链首直至链尾都不能找到一个能满足要求的分 区，则此次内存分配失败区，则此次内存分配失败第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 1 首次适应算法（首次适应算法（first fit） 优点优点释放内存时，有相邻的就合并释放内存时，有相邻的就合并大部分时间在低址操作，高地址有较大空间大部分时间在低址操作，高

21、地址有较大空间低地址被反复划分，留下很多难以利用的小空闲区低地址被反复划分，留下很多难以利用的小空闲区搜索次数增加，工作效率低搜索次数增加，工作效率低缺点缺点4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 2 循环首次适应算法（循环首次适应算法（next fit） 基本思想基本思想从上次找到的空闲分区的下一个空闲分区开始查找从上次找到的空闲分区的下一个空闲分区开始查找若最后一个空闲区仍不能满足，返回第一个空闲区若最后一个空闲区仍不能满足，返回第一个空闲区4.3.4 4.3.4 基于顺序搜索的动态

22、分区分配算法基于顺序搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 2 循环首次适应算法（循环首次适应算法（next fit） 优点优点减少查找空闲分区的开销减少查找空闲分区的开销空闲分区分布均匀空闲分区分布均匀缺乏较大的空闲分区缺乏较大的空闲分区缺点缺点4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 3 最佳适应算法（最佳适应算法（best fit） 基本思想基本思想每次把满足需求，又是最小的空闲分区分给作业每次把满足需求，又是最小的空闲分区分给作业空闲分

23、区按从小到大排序空闲分区按从小到大排序4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 3 最佳适应算法（最佳适应算法（best fit） 优点优点平均而言，只要查找一半表格平均而言，只要查找一半表格若有正好满足空白区，则它必被选中若有正好满足空白区，则它必被选中剩余部分很小，以至于无法使用剩余部分很小，以至于无法使用缺点缺点较大空白被保留下来较大空白被保留下来4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配

24、连续分配 4 最坏适应算法（最坏适应算法（worst fit） 基本思想基本思想空白区从大到小排序，依次分配空白区空白区从大到小排序，依次分配空白区4.3.4 4.3.4 基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法优点优点速度快速度快一次分配后，剩余空间仍可能大，能满足一般要求一次分配后，剩余空间仍可能大，能满足一般要求不利于大作业不利于大作业缺点缺点第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法1 快速适应算法（快速适应算法（quick fit） 基本思想基本思想将空闲分区

25、按容量大小分类，每类形成一个分区链表将空闲分区按容量大小分类，每类形成一个分区链表设置一张管理索引表，每一记录对应一种空闲分区类设置一张管理索引表，每一记录对应一种空闲分区类 型及空闲分区链表的表头型及空闲分区链表的表头分类按分类按2K、4K、8K，其它的可就近归类或专门的特殊，其它的可就近归类或专门的特殊 空闲区链表中空闲区链表中第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 1 快速适应算法（快速适应算法（quick fit） 优点优点查找效率高查找效率高不会产生分割，能保留大分区不会产生分割，能保留大分区算法复杂，开销大算法复杂，开销大缺点缺点空间换时间空间换时间4.3.

26、5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 2 2 伙伴系统伙伴系统（1） 分区大小均为分区大小均为2的的k次幂，次幂，k为整数，为整数，lkm（2 2）不断的划分内存，形成若干个不连续的空不断的划分内存，形成若干个不连续的空闲分区，根据分区的大小进行分类，形成空闲闲分区，根据分区的大小进行分类，形成空闲分区双向链表分区双向链表（3 3）分配一个长度为分配一个长度为n的存储空间时，首先计的存储空间时，首先计算一个算一个i值，使值，使2i1n2i，然后在空闲分区大小，然后在空闲分区大小为为2i的空闲分

27、区链表中查找。若找到，即把该的空闲分区链表中查找。若找到，即把该空闲分区分配给进程空闲分区分配给进程4.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 （4 4）否则，表明长度为否则，表明长度为2i的空闲分区已经耗尽，的空闲分区已经耗尽，则在分区大小为则在分区大小为2i1的空闲分区链表中寻找。的空闲分区链表中寻找。若存在若存在2i1的一个空闲分区，则把该空闲分区的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而

28、把另一个加伴，其中的一个分区用于分配，而把另一个加入分区大小为入分区大小为2i的空闲分区链表中。的空闲分区链表中。2 2 伙伴系统伙伴系统4.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 设系统中初始内存空间大小为设系统中初始内存空间大小为1MB，进程请，进程请求释放存储空间的操作序列为：求释放存储空间的操作序列为：进程进程A申请申请200KB，B申请申请120KB，C申请申请240KB，D申请申请100KB进程进程B释放，释放，E申请申请60KB进程进程A，C释放释放进程进程D释放释放进程进程E

29、释放释放写出上述操作序列内存伙伴变化的情况写出上述操作序列内存伙伴变化的情况2 2 伙伴系统伙伴系统4.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法第四章第四章 存储器管理存储器管理 例子例子512K01M-10256K512K1M-1A0256K512K1M-1A384KB第四章第四章 存储器管理存储器管理 例子例子0256K512K768K1M-1A384KBC0256K512K768K1M-1A384KBCD0256K512K768K1M-1A384KCD第四章第四章 存储器管理存储器管理2 2 例子例子0256K512K768K1M-1A384KCD

30、E320K0256K512K1M-1384KDE320K0256K512K1M-1384KE320K第四章第四章 存储器管理存储器管理2 2 例子例子0256K512K1M-1384KE320K0256K512K1M-1384K0256K512K1M-1第四章第四章 存储器管理存储器管理 例子例子0512K1M-101M-1第四章第四章 存储器管理存储器管理 例子例子1MB512KB256KB128KB第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 优缺点优缺点（1） 空间性能优于分类算法空间性能优于分类算法（2 2）时间性能优于顺序搜索算法时间性能优于顺序搜索算法（3 3）回

31、收开销大回收开销大2 2 伙伴系统伙伴系统4.3.5 4.3.5 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.6 4.3.6 可重定位分区分配可重定位分区分配1 1 引入引入 零碎小分区的总和零碎小分区的总和大于作业大小，如何大于作业大小，如何装入装入2 2 解决方案解决方案 移动所有被分配的分移动所有被分配的分区，形成大的空白区域。区，形成大的空白区域。（以时间换空间）（以时间换空间）操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程

32、序6用户程序980 KB(a) 紧凑前(b) 紧凑后第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.6 4.3.6 可重定位分区分配可重定位分区分配3 3 实现实现相对地址转换为物理地址推迟到指令真正执行时相对地址转换为物理地址推迟到指令真正执行时重定位寄存器：存放程序（数据）在内存中的重定位寄存器：存放程序（数据）在内存中的 起始地址起始地址访问地址访问地址=相对地址相对地址+重定位寄存器中的地址重定位寄存器中的地址第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.6 4.3.6 可重定位分区分配可重定位分区分配4 4 例子例子LOAD1,250

33、03650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.6 4.3.6 可重定位分区分配可重定位分区分配5 5 靠拢时间靠拢时间某个分区作业完成某个分区作业完成没有足够大空白区时没有足够大空白区时6 优缺点优缺点解决了碎片问题解决了碎片问题需硬件支持需硬件支持降低计算机速度降低计算机速度第四章第四章 存储器管理存储器管理n 4.3 连续分配连续分配 4.3.6 4.3.6 可重定位分区分配可重定位分区分配请求分配

34、u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否第四章第四章 存储器管理存储器管理n 4.4 对换对换 4.4.14.4.1 多道程序环境下的对换技术多道程序环境下的对换技术1 1 引入引入一方面，某些进程占用内存却被阻塞一方面，某些进程占用内存却被阻塞另一方面，某些进程等待却无法占用内存另一方面，某些进程等待却无法占用内存整体对换：进程对换（分时系统）整体对换：进程对换（分时系统） 页面对换：页面对换：“页页”或或“段段”的对换（虚拟

35、存储）的对换（虚拟存储）进程对换：对换空间的管理，进程的换入、换出进程对换：对换空间的管理，进程的换入、换出2 2 对换类型对换类型第四章第四章 存储器管理存储器管理n 4.4 对换对换4.4.24.4.2 对换空间的管理对换空间的管理1 1 对换空间管理的主要目标对换空间管理的主要目标文件区文件区 用于存放文件，主要目标是提高文件存储用于存放文件，主要目标是提高文件存储空间的利用率。空间的利用率。对换区对换区 用于存放从内存换出的进程；用于存放从内存换出的进程； 由于进程在对换区驻留的时间是短暂的，而由于进程在对换区驻留的时间是短暂的，而其操作又较频繁，故对对换空间的管理的主要其操作又较频繁

36、，故对对换空间的管理的主要目标是提高进程换入和换出的速度。目标是提高进程换入和换出的速度。第四章第四章 存储器管理存储器管理n 4.4 对换对换 4.4.24.4.2 对换空间的管理对换空间的管理2 2 对换空间管理中的数据结构对换空间管理中的数据结构配以数据结构，记录外存对换区使用情况。空配以数据结构，记录外存对换区使用情况。空闲分区表或空闲分区链。闲分区表或空闲分区链。4.4.3 进程的换入与换出进程的换入与换出1 进程的换出进程的换出（1） 时机：当进程创建子进程而需要更多内存空间，但又时机：当进程创建子进程而需要更多内存空间，但又 无足够内存空间时。无足够内存空间时。（2） 过程：选择

37、处于阻塞且优先级最低的进程作为换出进过程：选择处于阻塞且优先级最低的进程作为换出进 程，然后启动磁盘，将进程的程序和数据传送到磁盘程，然后启动磁盘，将进程的程序和数据传送到磁盘 的对换区上。的对换区上。第四章第四章 存储器管理存储器管理n 4.4 对换对换 4.4.34.4.3 进程的换入与换出进程的换入与换出（3）结果：若传送过程中未出现错误，便可回收内存，并）结果：若传送过程中未出现错误，便可回收内存，并对对 进程的进程的PCB做相应修改。做相应修改。 2 进程的换入进程的换入 系统定时查看进程状态，从中找出系统定时查看进程状态，从中找出“就绪就绪”状态，但已状态，但已换出的进程，将其中换

38、出时间最长的作为换入进程。换出的进程，将其中换出时间最长的作为换入进程。第四章第四章 存储器管理存储器管理内存分配方法：内存分配方法：1 1 单一连续分配单一连续分配 2 2 固定分区分配固定分区分配3 动态分区分配动态分区分配4 伙伴系统伙伴系统5 可重定位分区分配可重定位分区分配离散分配离散分配连续分配连续分配碎片碎片 分页存储管理：分页存储管理： 分段存储管理分段存储管理 基本分页（纯分页）存储管理基本分页（纯分页）存储管理第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 1 1 页面与物理块页面与物理块4.5.1 4.5.1 分页存储管理的基本方法分页存储

39、管理的基本方法（1）逻辑地址空间分成若干大小相等的片，称为页或者页面）逻辑地址空间分成若干大小相等的片，称为页或者页面（2）内存空间划分成与页面大小相等的块，称为（物理）块）内存空间划分成与页面大小相等的块，称为（物理）块（3）进程的若干页，分别装入可以不相邻的物理块中，最后）进程的若干页，分别装入可以不相邻的物理块中，最后 一页中存在一页中存在“页内碎片页内碎片”第四章第四章 存储器管理存储器管理1 1 页面页面（4 4）页面大小）页面大小太小：碎片减少，页表过长太小：碎片减少，页表过长太大：页表短，碎片增大太大：页表短，碎片增大适应大小：适应大小：512B8KBn 4.5 分页存储管理方式

40、分页存储管理方式 4.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法第四章第四章 存储器管理存储器管理2 2 地址结构地址结构 图中的地址长度为图中的地址长度为3232位，其中位，其中0 - 110 - 11位为页内地位为页内地址，即每页的大小为址，即每页的大小为4 KB4 KB；12 - 3112 - 31位为页号，地址位为页号，地址空间最多允许有空间最多允许有1 M1 M页页n 4.5 分页存储管理方式分页存储管理方式 4.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法第四章第四章 存储器管理存储器管理2 2 地址结构地址结构 对于某特定机器，其地址结构

41、是一定的。若给对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为定一个逻辑地址空间中的地址为A A，页面的大小为，页面的大小为L L，则页号则页号P P和页内地址和页内地址d d可按下式求得：可按下式求得：AMODLdLAINTP例如，其系统的页面大小为例如，其系统的页面大小为1 KB，设，设A = 2170 B，则由上式可以求得则由上式可以求得P = 2，d = 122。n 4.5 分页存储管理方式分页存储管理方式 4.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法第四章第四章 存储器管理存储器管理3 3 页表页表用户程序0 页1 页2 页3 页4 页5

42、页n 页页表页号块号02132638495内存012345678910n 4.5 分页存储管理方式分页存储管理方式 4.5.1 4.5.1 分页存储管理的基本方法分页存储管理的基本方法第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.2 4.5.2 地址变换机构地址变换机构基本任务：基本任务： 实现从逻辑地址到物理地址的转换实现从逻辑地址到物理地址的转换1 1 基本的地址变换机构基本的地址变换机构页内地址与块内地址一一对应页内地址与块内地址一一对应页号转换为块号：借助于页表页号转换为块号：借助于页表 页表驻留内存，设置一个页表寄存器页表驻留内存，设置一个页

43、表寄存器PTR，存放页表在内存中的始址和页表长度，平时存在存放页表在内存中的始址和页表长度，平时存在PCB中，调度进程时才装入中，调度进程时才装入PTR。第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.2 4.5.2 地址变换机构地址变换机构页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.2 4.5.2 地址变换机构地址变换机构2 2 具有快表的地址变换机构具有快表的地址变换机构 成本的关系，快表一般很小，通常只存放成本的

44、关系，快表一般很小，通常只存放16 16 512 512个页表项个页表项页表在内存页表在内存两次访问内存两次访问内存联想寄存器（快表）：并行查询能力联想寄存器（快表）：并行查询能力快表虽然很小，但命中率可达快表虽然很小，但命中率可达90%以上，可将因以上，可将因地址变换机构而造成的速度损失减少到地址变换机构而造成的速度损失减少到10%以下以下第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.2 4.5.2 地址变换机构地址变换机构页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址第四章第四章 存储器管

45、理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.3 4.5.3 访问内存的有效时间访问内存的有效时间1 1 定义定义 从进程发出指定逻辑地址的访问请求，经过从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所花费的时间总和。单元并取出数据，所花费的时间总和。基本分页：基本分页：EAT=t+t=2t引入快表：引入快表：EAT=a +(t+ )(1-a)+t第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级页表两级和多级页表1 1

46、 引入引入页表离散分配页表离散分配页表庞大，需要占用相当大的连续内存空间页表庞大，需要占用相当大的连续内存空间2 解决方案解决方案将当前需要的页表调入内存，其余留在磁盘将当前需要的页表调入内存，其余留在磁盘第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级页表两级和多级页表3 3 两级页表两级页表将页表分页，离散存储将页表分页，离散存储 32位逻辑地址空间，页面大小为位逻辑地址空间，页面大小为4KB，页表占，页表占用用1MB。（1）离散分配）离散分配为页表页面建立页表，称为外层页表为页表页面建立页表，称为外层页表第四章第四章 存储

47、器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级页表两级和多级页表外层页号外层页内地址页内地址P1P2d31222112110第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级页表两级和多级页表101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页存空间第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级

48、页表两级和多级页表外部页号P1P2外部页内地址 页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址第四章第四章 存储器管理存储器管理n 4.5 分页存储管理方式分页存储管理方式 4.5.4 4.5.4 两级和多级页表两级和多级页表（2 2）分级调入）分级调入逻辑地址逻辑地址6464位，采用两级页表，页面大小位，采用两级页表，页面大小4KB4KB 运行的进程，外部页表调入内存。页表调入一运行的进程，外部页表调入内存。页表调入一页或几页即可。设置状态位页或几页即可。设置状态位S。4 多级页表多级页表页表分页大小页表分页大小4KB。外层页表大小。外层页表大小242（16384GB）第四章第

49、四章 存储器管理存储器管理固定分区固定分区动态分区动态分区分页管理分页管理提高内存利用率提高内存利用率分段存储管理分段存储管理满足用户编程和使用满足用户编程和使用第四章第四章 存储器管理存储器管理n 4.6 基本分段存储管理基本分段存储管理 1 1 分区分配：碎片分区分配：碎片4.6.1 4.6.1 分段管理方式的引入分段管理方式的引入 页式分配：连续虚页上的内容不是逻辑意义上的页式分配：连续虚页上的内容不是逻辑意义上的 完整信息单位完整信息单位2 优点优点方便编程方便编程信息共享信息共享信息保护信息保护动态增长动态增长动态链接动态链接第四章第四章 存储器管理存储器管理n 4.5 基本分段存储

50、管理基本分段存储管理 1 1 分段分段4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理 每个作业的地址空间按程序本身的自然逻辑关系每个作业的地址空间按程序本身的自然逻辑关系分成若干段。每个段有自己的段名，且都是从分成若干段。每个段有自己的段名，且都是从0 0开始，开始，长度任意。地址由段号长度任意。地址由段号S S和段内偏移量和段内偏移量WW构成，每个构成，每个段占一个分区。段占一个分区。第四章第四章 存储器管理存储器管理n 4.5 基本分段存储管理基本分段存储管理 2 2 段表段表4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理 系统为进程的每个分段分配一个连续分区，

51、而系统为进程的每个分段分配一个连续分区，而进程中的各个段可以离散地移入内存中不同的分区进程中的各个段可以离散地移入内存中不同的分区中。中。每个进程一张段表，用于实现从逻辑段到物理内存每个进程一张段表，用于实现从逻辑段到物理内存区的映射。区的映射。第四章第四章 存储器管理存储器管理n 4.5 基本分段存储管理基本分段存储管理 2 2 段表段表4.5.2 4.5.2 分段系统的基本原理分段系统的基本原理作业空间(MAIN)=0030 K(X)=1020 K(D)=2015 K(S)=3010 K30 K20 K15 K10 K40 K80 K段长基址段号(MAIN)=030 K(X)=120 K(

52、D)=215 K(S)=310 K040 K80 K120 K150 K段表内存空间0123120 K150 K第四章第四章 存储器管理存储器管理3 3 地址变换机构地址变换机构段表寄存器：存放段表始址和段表长度段表寄存器：存放段表始址和段表长度控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址第四章第四章 存储器管理存储器管理地址变换示例地址变换示例第0段第1段第2段段长段起始地址20KB50KB40KB110KB20KB75KB段号012作业第0段作业第2段作业第1段 50KB70KB75KB95KB110KB150KBSMT