第四章 存储管理

1、广州商学院计算机系广州商学院计算机系 kyykyy4.14.1 存储器工作原理存储器工作原理 4.2 4.2 连续存储空间管理连续存储空间管理 4.3 4.3 分页式存储管理分页式存储管理 4.4 4.4 分段式存储管理分段式存储管理 4.5 4.5 虚拟存储管理虚拟存储管理 第四章第四章 存储管理存储管理广州商学院计算机系广州商学院计算机系 kyykyy如何对存储器加以有效的管理，不仅直接影如何对存储器加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大响到存储器的利用率，而且还对系统性能有重大影响。存储器管理的主要对象是内存。影响。存储器管理的主要对象是内存。存储管理存储管

2、理的功能的功能: :分配和去配、抽象和映射、隔离与共享分配和去配、抽象和映射、隔离与共享、存储扩充。、存储扩充。广州商学院计算机系广州商学院计算机系 kyykyy4.1.1 存储器的层次存储器的层次寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质4.1 存储器存储器访问速度往上越高访问速度往上越高容量越往下越大容量越往下越大广州商学院计算机系广州商学院计算机系 kyykyyl如何将一个用户源程序变成一个可在内存中执行如何将一个用户源程序变成一个可在内存中执行的程序，通常要经过的程序，通常要经过3 3步骤：步骤： : :由编译程序（由编译程序（CompilerCompiler）将用户源代码编

3、译）将用户源代码编译成若个目标模块成若个目标模块 （Object ModuleObject Module）。）。: :由链接程序（由链接程序（LinkerLinker）将编译后形成的一组）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块，形成一个完整的装入模块 。: :由装入程序（由装入程序（LoaderLoader）将装入模块装入内存）将装入模块装入内存。 - -程序的装入和链接程序的装入和链接4.1.2 4.1.2 地址转换与存储保护地址转换与存储保护广州商学院计算机系广州商学院计算机系 kyykyy编辑编辑编译

4、编译链接链接装入装入运行运行广州商学院计算机系广州商学院计算机系 kyykyy1.1.程序编译程序编译n源程序经过编译程序或汇编程序的处理来获得源程序经过编译程序或汇编程序的处理来获得多个目标模块多个目标模块n处理时编译程序负责记录模块内引用的发生位处理时编译程序负责记录模块内引用的发生位置置 n目标模块附有供引用使用的内部符号表和外部目标模块附有供引用使用的内部符号表和外部符号表符号表n符号表给出了各个符号名及在本目标模块中的符号表给出了各个符号名及在本目标模块中的名字地址名字地址，在模块被链接时进行转换，在模块被链接时进行转换广州商学院计算机系广州商学院计算机系 kyykyy2. 2. 程

5、序链接程序链接l1)1)静态链接静态链接: :在程序装入之前，先将各目标模块及它们所在程序装入之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆需的库函数，链接成一个完整的装配模块，以后不再拆开。开。l2)2)装入时动态链接装入时动态链接: :这是指将用户源程序编译后所得到的这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链一组目标模块，在装入内存时，采用边装入边链接的链接方式接方式。la.a.便于修改和更新便于修改和更新lb.b.便于实现对目标模块的共享便于实现对目标模块的共享l3)3)运行时动态链接运行时动态链接: :这是指对某些目标

6、模块的链接，是在这是指对某些目标模块的链接，是在程序执行中需要该程序执行中需要该( (目标目标) )模块时，才对它进行的链接。模块时，才对它进行的链接。 广州商学院计算机系广州商学院计算机系 kyykyy模块模块A Aif x1if x1CALL B;CALL B;elseelseCALL C;CALL C;RETURNRETURN模块模块B BCALL C;CALL C;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1(a)(a)目标模块目标模块模块模块A Aif x1if x1JSR L;JSR L;elseelseJSR

7、 L+M;JSR L+M;RETURNRETURN模块模块B BJSR L+M;JSR L+M;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)装入模块装入模块广州商学院计算机系广州商学院计算机系 kyykyyl三种装入方式：绝对装载方式、可重定位装载方式三种装入方式：绝对装载方式、可重定位装载方式 、动、动态运行时转载方式。态运行时转载方式。1 1、绝对装载：、绝对装载：l编译后，装入前已产生了绝对地址（内存地址），装载时不编译后，装入前已产生了绝对地址（内存地址），装载时不再作地址

8、重定位。再作地址重定位。l绝对地址的产生：（绝对地址的产生：（1 1）由编译器完成，（）由编译器完成，（2 2）由程序员编程）由程序员编程完成。完成。l对（对（1 1）而言，编程用符号地址。）而言，编程用符号地址。 l程序每次必须装入同一内存区；程序员必须事先了解内存的程序每次必须装入同一内存区；程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；程序的修改使用情况，根据内存情况确定程序的逻辑地址；程序的修改将引起整个程序中指令地址的变动；程序所有的存储引用（将引起整个程序中指令地址的变动；程序所有的存储引用（函数调用），在装入之前都必须转换为物理地址，这不利于函数调用），在装入

9、之前都必须转换为物理地址，这不利于存储共享。存储共享。3. 3. 程序转载程序转载广州商学院计算机系广州商学院计算机系 kyykyy2、可重定位装载方式、可重定位装载方式 (静态地址重定位静态地址重定位) l目标模块的起始地址通常是从目标模块的起始地址通常是从0开始的，程序开始的，程序中的其它地址也都是相对于起始地址计算的。中的其它地址也都是相对于起始地址计算的。 l由装载程序将装载模块装入内存后，装载模块由装载程序将装载模块装入内存后，装载模块中程序所访问的所有逻辑地址与实际装载内存中程序所访问的所有逻辑地址与实际装载内存的物理地址不同的物理地址不同 ，必须进行地址映射，将逻，必须进行地址映

10、射，将逻辑地址转换为物理地址。辑地址转换为物理地址。l静态重定位技术静态重定位技术：地址映射在程序装载时进行：地址映射在程序装载时进行，以后不再更改程序地址。，以后不再更改程序地址。广州商学院计算机系广州商学院计算机系 kyykyy0100025005000LOAD 1,2500LOAD 1,1250036536510000110001250015000目标模块目标模块装入内存装入内存LOAD j365符号地址符号地址相对地址相对地址绝对地址绝对地址装入模块装入模块j广州商学院计算机系广州商学院计算机系 kyykyyl3.3. 动态重定位动态重定位l在程序运行时动态进行程序的地址转换。在程序运

11、行时动态进行程序的地址转换。l硬件的支持，即重定位寄存器，用于保存程序硬件的支持，即重定位寄存器，用于保存程序的在内存中的起始地址。的在内存中的起始地址。l能保证进程的可移动性，有效的提高内存的使能保证进程的可移动性，有效的提高内存的使用效率。用效率。l运行时重定位有利于多道程序环境下，进程的运行时重定位有利于多道程序环境下，进程的换进换进/ /换出及实现紧凑技术。换出及实现紧凑技术。广州商学院计算机系广州商学院计算机系 kyykyyload 1,2500load 1,2500365365load 1,load 1,250025003653650 01001002500250050005000

12、25002500500005000050000500005010050100+ +52500525005500055000作业作业J J处理机一侧处理机一侧存储器一侧存储器一侧重定位寄存器重定位寄存器( (分区首地址寄存器分区首地址寄存器) )相对地址相对地址广州商学院计算机系广州商学院计算机系 kyykyyn4.2.1 固定分区存储管理固定分区存储管理 n4.2.2 可变分区存储管理可变分区存储管理 n4.2.3 伙伴系统伙伴系统n4.2.4 主存不足的存储管理技术主存不足的存储管理技术4.2 4.2 连续存储管理连续存储管理广州商学院计算机系广州商学院计算机系 kyykyy4.2.1 固定

13、分区存储管理固定分区存储管理n分区管理：分区管理： 是一种简单使用的存贮管理方案，是一种简单使用的存贮管理方案，把内存空间静态的（动态的）分割把内存空间静态的（动态的）分割成若干大小可以不等的区域，每个成若干大小可以不等的区域，每个作业分配一片连续的存储空间，程作业分配一片连续的存储空间，程序一次整体装入序一次整体装入n固定式分区管理：将内存空间静态的固定式分区管理：将内存空间静态的分割成若干大小可以不等的区域，每分割成若干大小可以不等的区域，每个分区只能装入一道作业，分区的个个分区只能装入一道作业，分区的个数是内存中作业的最大道数数是内存中作业的最大道数操作系统区操作系统区用户分区用户分区1

14、用户分区用户分区2用户分区用户分区3广州商学院计算机系广州商学院计算机系 kyykyy固定分区存储管理固定分区存储管理( (续续) )n划分分区的方法：划分分区的方法：n分区大小相等：将内存分割成若干个大小相等的区（太分区大小相等：将内存分割成若干个大小相等的区（太大造成内存的浪费，太小不能装入进程运行，缺乏灵活大造成内存的浪费，太小不能装入进程运行，缺乏灵活性）性）n分区大小不等：一部分大的一部分小的，一部分适中的分区大小不等：一部分大的一部分小的，一部分适中的n注意注意：一个分区分配了一个作业后剩余空间便不能再：一个分区分配了一个作业后剩余空间便不能再用，这称为内碎片；当一个区域小于一个作

15、业时便整块用，这称为内碎片；当一个区域小于一个作业时便整块被丢弃，称为外碎片被丢弃，称为外碎片广州商学院计算机系广州商学院计算机系 kyykyyn为了记住哪些分区是空闲分区，哪些分区是已分配分区，为了记住哪些分区是空闲分区，哪些分区是已分配分区，系统可设置如下主存分配表：系统可设置如下主存分配表：分区分区号号大小大小(KB)起址起址(KB)状态状态1824已分配已分配21632已分配已分配33248已分配已分配46480未分配未分配5128144 已分配已分配操作系统操作系统作业作业A(7K)A(7K)作业作业B(13K)B(13K)作业作业C(23K)C(23K)空闲分区空闲分区作业作业D(

16、80K)D(80K)24K32K48K144K272K80K分区描述表分区描述表内存分配情况内存分配情况碎片碎片广州商学院计算机系广州商学院计算机系 kyykyy固定分区存储管理固定分区存储管理( (续续) )n缺点缺点：n固定分区存储管理限制了程序的大小固定分区存储管理限制了程序的大小, ,无法运行无法运行超过分区大小的程序超过分区大小的程序n内存空间利用率不高内存空间利用率不高n不便于程序动态扩充内存不便于程序动态扩充内存n限制了程序道数限制了程序道数n固定分区存储管理适合于程序大小和出现频率已固定分区存储管理适合于程序大小和出现频率已知的情形知的情形广州商学院计算机系广州商学院计算机系

17、kyykyy4.2.2 可变分区存储管理可变分区存储管理按照作业的大小来划分分区，划分的时间、大小和位置都是按照作业的大小来划分分区，划分的时间、大小和位置都是动态的。系统启动后用户作业装入内存之前，整个用户区是动态的。系统启动后用户作业装入内存之前，整个用户区是一个大的空闲分区，随着作业的装入和撤离，内存空间被分一个大的空闲分区，随着作业的装入和撤离，内存空间被分成许多大小不一的分区，有的分区正被作业占用，有的分区成许多大小不一的分区，有的分区正被作业占用，有的分区是空闲的。当一个新的作业要求装入时，必须找到一个足够是空闲的。当一个新的作业要求装入时，必须找到一个足够大的空闲区，如果找到的空

18、闲分区大于作业需要量，则把该大的空闲区，如果找到的空闲分区大于作业需要量，则把该空闲分区分成两部分，一部分分配给作业，另一部分作为一空闲分区分成两部分，一部分分配给作业，另一部分作为一个较小的空闲分区。当一个作业运行结束时，它归还的分区个较小的空闲分区。当一个作业运行结束时，它归还的分区如果与其它空闲分区相邻，则还要进行合并，形成一个大的如果与其它空闲分区相邻，则还要进行合并，形成一个大的空闲分区。空闲分区。广州商学院计算机系广州商学院计算机系 kyykyyl一、分区组织一、分区组织l1 1空闲分区表空闲分区表：在系统中设置一张空闲分区表，用于记录：在系统中设置一张空闲分区表，用于记录每个空闲

19、分区的情况。每个空闲分区的情况。l2 2空闲分区链：空闲分区链：为了实现对空闲分区的分配和链接，设置为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。闲分区链接成一个双向链。前向前向指针指针分区分区信息信息N N个字节可用个字节可用后向后向指针指针广州商学院计算机系广州商学院计算机系 kyykyy系统区系统区A(8K)B(16K)C(20K)D(28K)E(56K)F(2K)G(40K).024K32K48K68K96K152K154K194K256kA A、B B、C C、D D、E

20、 E、F F、G G任务陆续进入内存进任务陆续进入内存进行执行，行执行，T0T0时刻，时刻，A A、C C、E E、G G已经完成，请画出已经完成，请画出当前时刻空闲分区表。当前时刻空闲分区表。如果此时有来了一个如果此时有来了一个15K15K大小大小H H任务，会分在任务，会分在哪个空闲分区里面。哪个空闲分区里面。广州商学院计算机系广州商学院计算机系 kyykyy分区号分区号 大小大小(KB)起址起址(KB)状态状态1824未分配未分配22048未分配未分配35696未分配未分配440154未分配未分配562194未分配未分配空闲分区表空闲分区表广州商学院计算机系广州商学院计算机系 kyyky

21、yl1 1最先适应算法（首次适应算法）。最先适应算法（首次适应算法）。l每次都从头开始，寻找第一个满足需求的空闲分区。每次都从头开始，寻找第一个满足需求的空闲分区。l特点：找到第一个大小满足的分区，划分。有碎片（外零头）特点：找到第一个大小满足的分区，划分。有碎片（外零头），低址内存使用频繁。，低址内存使用频繁。l2 2下次首次适应算法（循环首次适应算法）。下次首次适应算法（循环首次适应算法）。l与与1 1类似，从上次找到的空闲分区的下一个开始查找。类似，从上次找到的空闲分区的下一个开始查找。l特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区特点：空闲分区分布均匀，提高了查找速度；缺乏

22、大的空闲分区l3 3最佳适应算法（最优适应算法）最佳适应算法（最优适应算法）l分区按大小递增排序；分区释放时需插入到适当位置。分区按大小递增排序；分区释放时需插入到适当位置。l特点：产生无法利用的小碎片。特点：产生无法利用的小碎片。l4. 4. 最坏适应算法最坏适应算法l扫描整个空闲分区表或空闲分区链扫描整个空闲分区表或空闲分区链, ,总是挑选一个最大的空闲总是挑选一个最大的空闲区分割给作业使用区分割给作业使用l特点：分割剩余的空闲区不至于太小特点：分割剩余的空闲区不至于太小二、分区分配二、分区分配广州商学院计算机系广州商学院计算机系 kyykyy当进程运行完毕释放内存时，需合并相邻的空当进程

23、运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区，称为合并技术。闲分区，形成大的分区，称为合并技术。（1 1）上邻空闲区：合并，改大小）上邻空闲区：合并，改大小（2 2）下邻空闲区：合并，改大小，首址。）下邻空闲区：合并，改大小，首址。（3 3）上、下邻空闲区：合并，改大小。）上、下邻空闲区：合并，改大小。（4 4）不邻接，则建立一新表项。）不邻接，则建立一新表项。三、分区回收三、分区回收进程进程1 1F1F1回收区回收区进程进程2 2进程进程3 3进程进程1 1进程进程2 2回收区回收区F2F2进程进程3 3进程进程1 1F1F1回收区回收区F2F2进程进程2 2内存回收时的情况内存回

24、收时的情况F1F1进程进程1 1回收区回收区进程进程2 2F2F2广州商学院计算机系广州商学院计算机系 kyykyy2.2.地址转换与存储保护地址转换与存储保护n可变分区方式采用动态重定位装入作业可变分区方式采用动态重定位装入作业, ,作业程序作业程序和数据的地址转换由硬件完成和数据的地址转换由硬件完成. .硬件设置两个控制硬件设置两个控制寄存器寄存器: :基址寄存器和限长寄存器基址寄存器和限长寄存器.基址寄存器存放基址寄存器存放分配给作业使用的分区的起始地址分配给作业使用的分区的起始地址,限长寄存器存放限长寄存器存放作业占用的连续存储空间的长度作业占用的连续存储空间的长度n当作业占有当作业占

25、有CPU运行时运行时,操作系统把作业所占分区操作系统把作业所占分区的始址和长度送入基址寄存器和限长寄存器的始址和长度送入基址寄存器和限长寄存器.随着逐随着逐条指令的执行和数据访问完成地址转换条指令的执行和数据访问完成地址转换n当逻辑地址小于限长值时，可获得绝对地址，大当逻辑地址小于限长值时，可获得绝对地址，大于时，不允许访问于时，不允许访问广州商学院计算机系广州商学院计算机系 kyykyy基址基址基址寄存器基址寄存器逻辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区空闲分区空闲分区1 1用户作业用户作业1 1空闲分区空闲分区2 2限长限长限长寄存器限长寄存器 限长限长越界中断越界

26、中断广州商学院计算机系广州商学院计算机系 kyykyy动态分区特点动态分区特点n系统初启时，整个内存只有一个自由块系统初启时，整个内存只有一个自由块n需调入一个作业时，查找所有的自由块直到找到一需调入一个作业时，查找所有的自由块直到找到一个满足要求的并把它分给该作业个满足要求的并把它分给该作业n当自由块较大以至满足一个作业的需求后仍有剩余当自由块较大以至满足一个作业的需求后仍有剩余则将剩余量构成一个新的自由块交给系统则将剩余量构成一个新的自由块交给系统n当一个作业运行完毕并释放了其所得到的空间时，当一个作业运行完毕并释放了其所得到的空间时，要考虑它上下是否邻接自由块，若有合并它们为一要考虑它上

27、下是否邻接自由块，若有合并它们为一个较大的自由块个较大的自由块n解决了内碎片的问题，但会产生很多较小的外碎片解决了内碎片的问题，但会产生很多较小的外碎片（相对的概念）（相对的概念）广州商学院计算机系广州商学院计算机系 kyykyy固定分区和动态分区方式都有不足之处。固定分区方式固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方闲分区时需要进

28、行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均伙伴系统规定，无论已分配分区或空闲分区，其大小均为为2 2的的k k次幂，次幂，k k为整数，为整数，lkm，其中：，其中：21表示分配的最小表示分配的最小分区的大小，分区的大小，2m表示分配的最大分区的大小，通常表示分配的最大分区的大小，通常2m是整个是整个可分配内存的大小。可分配内存的大小。4.2.4 4.2.4 动态分区的实例动态分区的实例伙伴系统伙伴系统广州商学院计算机系广州商学院计算机系 kyykyy当需要为进程分配一个长度

29、为当需要为进程分配一个长度为n的存储空间时，首先计算的存储空间时，首先计算一个一个i值，使值，使2i1n2i，然后在空闲分区大小为，然后在空闲分区大小为2i的空闲分区的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为表明长度为2i的空闲分区已经耗尽，则在分区大小为的空闲分区已经耗尽，则在分区大小为2i1的空的空闲分区链表中寻找。若存在闲分区链表中寻找。若存在2i1的一个空闲分区，则把该空闲的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一

30、个分区用于分配，而把另一个加入分区大小为的一个分区用于分配，而把另一个加入分区大小为2i的空闲分的空闲分区链表中。若大小为区链表中。若大小为2i1的空闲分区也不存在，则需要查找大的空闲分区也不存在，则需要查找大小为小为2i2的空闲分区，若找到则对其进行两次分割：第一次，的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为将其分割为大小为2i1的两个分区，一个用于分配，一个加入的两个分区，一个用于分配，一个加入到大小为到大小为2i1的空闲分区链表中；第二次，将第一次用于分配的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为的空闲区分割为2i的两个分区，一个用于分配，一个加入到大的

31、两个分区，一个用于分配，一个加入到大小为小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空闲分区，以此类推。由此可见，在最坏的情况下，可的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对能需要对2k的空闲分区进行的空闲分区进行k次分割才能得到所需分区。次分割才能得到所需分区。 广州商学院计算机系广州商学院计算机系 kyykyy与一次分配可能要进行多次分割一样，一次回收也可能要与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为进行多次合并，如回收大小为2i的空闲分区时，若事先已存的空闲分区时，若事先

32、已存在在2i的空闲分区时，则应将其与伙伴分区合并为大小为的空闲分区时，则应将其与伙伴分区合并为大小为2i1的空闲分区，若事先已存在的空闲分区，若事先已存在2i1的空闲分区时，又应继续与的空闲分区时，又应继续与其伙伴分区合并为大小为其伙伴分区合并为大小为2i2的空闲分区，依此类推。的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需所述的多种方法相比较，由于该算法在回收空闲分区

33、时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。前面所述的分类搜索法，比顺序搜索法略差。 广州商学院计算机系广州商学院计算机系 kyykyy广州商学院计算机系广州商学院计算机系 kyykyyn当一个新的作业要求装入当一个新的作业要求装入, ,没有一个空闲分区能够满没有一个空闲分区能够满足要求足要求, ,但所有空闲分区之和能够满足要求时但所有空闲分区之和能够满足要求时, ,可以移可以移动内存作

34、业动内存作业, ,合并这些小的空闲分区合并这些小的空闲分区, ,使之满足新来的使之满足新来的作业。作业移动后作业。作业移动后, ,要及时修改它们的基址。要及时修改它们的基址。操作系统作业1空闲区作业2空闲区作业3空闲区操作系统作业1作业2作业3空闲区操作系统作业1作业2作业3空闲区作业44.2.34.2.3主存不足的存储管理技术主存不足的存储管理技术- -移动技术移动技术广州商学院计算机系广州商学院计算机系 kyykyyl 对换的引入对换的引入l将阻塞进程，暂时不用的程序、数据换出。将阻塞进程，暂时不用的程序、数据换出。l将具备运行条件的进程换入。将具备运行条件的进程换入。l类型：类型：l整体

35、对换：进程对换，解决内存紧张整体对换：进程对换，解决内存紧张l部分对换：页面对换部分对换：页面对换/ /分段对换：提供虚存支持分段对换：提供虚存支持l 对换空间管理对换空间管理l外存外存 l对换区对换区比比文件区文件区侧重于对换速度。侧重于对换速度。l因此，对换区一般采用连续分配。采用数据结构和分配因此，对换区一般采用连续分配。采用数据结构和分配回收类似于动态分区分配。回收类似于动态分区分配。4.2.34.2.3主存不足的存储管理技术主存不足的存储管理技术- -对换技术对换技术广州商学院计算机系广州商学院计算机系 kyykyyl连续分配引起连续分配引起: :碎片碎片l离散分配方式离散分配方式l

36、分页存储管理分页存储管理l将一个进程的逻辑地址空间分成若干个大小相等的页面将一个进程的逻辑地址空间分成若干个大小相等的页面，把内存空间分成与页面相同大小的若干个存储块，称，把内存空间分成与页面相同大小的若干个存储块，称为页框，在为进程分配内存时，以块为单位将进程中的为页框，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的页框中。若干个页分别装入到多个可以不相邻接的页框中。l分段存储管理分段存储管理l作业的地址空间被划分为若干个段，每个段定义了一组作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字。逻辑信息。每个段都有自己的名字。 每个段都

37、从每个段都从0开始开始编址，并采用一段连续的地址空间。段的长度由相应的编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。逻辑信息组的长度决定，因而各段长度不等。 l段页存储管理段页存储管理l是分段和分页原理的结合，即先将用户程序分成若干个是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段，再把每个段分成若干个页，并为每一个段赋予一个段名。段名。广州商学院计算机系广州商学院计算机系 kyykyyn4.3.1 分页式存储管理的基本原理n4.3.2 快表n4.3.3 分页式存储空间的分配和去配n4.3.4 分页式存

38、储空间的页面共享和保护n4.3.5 多级页表4.3 4.3 分页存储管理分页存储管理广州商学院计算机系广州商学院计算机系 kyykyy4.3.1 分页式存储管理的基本原理分页式存储管理的基本原理l将一个进程的逻辑地址空间分成若干个大小相等的区，将一个进程的逻辑地址空间分成若干个大小相等的区，称为称为页面页面或页，相应地，也把内存空间分成与页面相同或页，相应地，也把内存空间分成与页面相同大小的若干个存储块，称为大小的若干个存储块，称为页框页框，在为进程分配内存时，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的页框中。不

39、相邻接的页框中。n对页框和页面都加以编号，从对页框和页面都加以编号，从0 0开始，如第开始，如第0 0号、第号、第1 1号等号等l由于进程的最后一页经常装不满一块而形成了不可利用由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为的碎片，称之为“页内碎片页内碎片”或称为或称为“内零头内零头”。 广州商学院计算机系广州商学院计算机系 kyykyyl1.1.页面页面l页面和页框：逻辑空间和内存空间页面和页框：逻辑空间和内存空间l由机器的地址结构决定由机器的地址结构决定l页太大，页内碎片大。页太大，页内碎片大。l页太小：页表可能很长，换入页太小：页表可能很长，换入/ /出效率低出效率低l2

40、.2.地址结构地址结构 31 31 12 1112 11 0 0逻辑地址逻辑地址A A；页大小；页大小L(L(设为设为4096)4096)；页内偏移；页内偏移d dP=(int)A/L d=A mod LP=(int)A/L d=A mod L如：如： A A8210B. 8210B. 则则P=2, d=18 P=2, d=18 分页存储管理分页存储管理页号页号P P 页内位移页内位移d d 广州商学院计算机系广州商学院计算机系 kyykyy3 3、页表、页表0 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页0 02 21 13 32 26 63 38 84 49 95 5

41、n n0 01 12 23 34 45 56 67 78 89 9用户程序用户程序页表页表页面号页面号 页框号页框号内存内存广州商学院计算机系广州商学院计算机系 kyykyy地址转换地址转换 l由页表完成逻辑页号由页表完成逻辑页号物理页框号的映射。物理页框号的映射。l一、基本地址变换机构：一、基本地址变换机构：l越界保护越界保护l每个进程对应一页表，其信息（如长度、始址）放在每个进程对应一页表，其信息（如长度、始址）放在PCBPCB中，执行时将其首地址装入中，执行时将其首地址装入页表寄存器页表寄存器。n二、地址转换的过程二、地址转换的过程n进程运行前系统把页表基址存入页表基址寄存器进程运行前系

42、统把页表基址存入页表基址寄存器n运行时硬件自动将逻辑地址分成两部分，页号运行时硬件自动将逻辑地址分成两部分，页号P和页内位和页内位移移dn找到页表基址后，按页号找到页表基址后，按页号P作为索引查页表，得到页框号，作为索引查页表，得到页框号，根据公式完成地址转换根据公式完成地址转换物理地址物理地址 = 页框号页框号块长块长 + 页内位移页内位移广州商学院计算机系广州商学院计算机系 kyykyy分页系统地址转换分页系统地址转换页表始址页表始址页表长度页表长度页号页号(3) 页内地址页内地址(342)(342)页表寄存器页表寄存器逻辑地址逻辑地址(12630)(12630)越界中断越界中断5页框号页

43、框号页表页表页号页号0123物理地址物理地址68155页号页号01236815广州商学院计算机系广州商学院计算机系 kyykyy4.3.2 快表快表n由于页表放在内存中，这样，由于页表放在内存中，这样，CPUCPU每存取一个数据时，每存取一个数据时，需要两次访问内存需要两次访问内存n一次访问页表取得物理块号以形成物理地址一次访问页表取得物理块号以形成物理地址n第二次根据物理地址存取数据第二次根据物理地址存取数据, ,速度降低了一倍速度降低了一倍n为了提高速度为了提高速度, ,在存储管理部件中增设一个专用的高在存储管理部件中增设一个专用的高速缓冲存储器速缓冲存储器, ,用来存放最近访问过的部分页

44、表用来存放最近访问过的部分页表, ,这种这种相联存储器称为快表；快表昂贵，不易过多。相联存储器称为快表；快表昂贵，不易过多。n如如Intel80486Intel80486的快表为的快表为3232个单元个单元广州商学院计算机系广州商学院计算机系 kyykyy具有快表的分页系统地址转换具有快表的分页系统地址转换页表始址页表始址页表长度页表长度页号页号(2) 页内地址页内地址(342)(342)页表寄存器页表寄存器逻辑地址逻辑地址越界中断越界中断5页框号页框号页表页表页号页号0123物理地址物理地址6815相相联联存存储储器器快表快表501268页框号页框号页号页号广州商学院计算机系广州商学院计算机

45、系 kyykyyn有了快表有了快表, ,根据页号查找对应的物理块号时：根据页号查找对应的物理块号时：n首先查找快表，若找到则将物理块号和页内地址（也是首先查找快表，若找到则将物理块号和页内地址（也是块内地址）拼接形成物理地址块内地址）拼接形成物理地址 n若在快表中未找到物理块号，则再查找内存页表，获取若在快表中未找到物理块号，则再查找内存页表，获取物理块号，一方面形成物理地址，另一方面将该表项抄到物理块号，一方面形成物理地址，另一方面将该表项抄到快表中，以备下次再次访问该页面快表中，以备下次再次访问该页面 n有的系统查快表和查内存页表是同时进行的，一旦从快有的系统查快表和查内存页表是同时进行的

46、，一旦从快表中找到了对应项，则立即停止对内存页表的查找表中找到了对应项，则立即停止对内存页表的查找n当快表已满且要登记新页时，需要淘汰旧快表项，最简当快表已满且要登记新页时，需要淘汰旧快表项，最简单的策略是单的策略是“先进先出先进先出”广州商学院计算机系广州商学院计算机系 kyykyy 例：有一分页式系统，其页表存放在主存中：例：有一分页式系统，其页表存放在主存中： 如果对主存的一次存取需要如果对主存的一次存取需要10ns,10ns,试问实现试问实现一次页面访问的存取时间是多少一次页面访问的存取时间是多少? ? 如果系统加有快表如果系统加有快表, ,平均命中率为平均命中率为85%,85%,当页

47、当页表项在快表中时表项在快表中时, ,其查找时间为其查找时间为2ns, 2ns, 试问此试问此时的存取时间是多少时的存取时间是多少? ?广州商学院计算机系广州商学院计算机系 kyykyy答：若页表存放在主存中，则要实现一次页面访问需两次答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。址（称为定位）。第二次才根据该地址存取页面数据。 页表在主存的存取访问时间页表在主存的存取访问时间 =10=10* *2=20(ns)2=20(ns) 增加快表后的存取访

48、问时间增加快表后的存取访问时间 =0.85=0.85* *12+(1-0.85)12+(1-0.85)* *（2+102+10* *2 2）=13.4(ns)=13.4(ns)广州商学院计算机系广州商学院计算机系 kyykyy4.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配n位示图由一些二进制位组成,每一位对应一个内存物理块,位值表示所对应的物理块是否已分配出去.分配和回收物理块时只需修改位值即可n链表方法111110001111111111001111110001110000000111111111110000001111111111100000011广州商学院计

49、算机系广州商学院计算机系 kyykyy4.3.4 分页式存储空间的共享与保护分页式存储空间的共享与保护n分页存储管理在实现共享时分页存储管理在实现共享时,必须区分数据共享和程序共享必须区分数据共享和程序共享,实实现数据共享时现数据共享时,允许不同的作业对共享的数据页使用不同的页允许不同的作业对共享的数据页使用不同的页号号,只要让各自页表中的有关表目指向共享的数据信息块就行只要让各自页表中的有关表目指向共享的数据信息块就行了了n实现程序共享时实现程序共享时,由于页式存储结构要求逻辑地址空间是连续由于页式存储结构要求逻辑地址空间是连续的的,所以程序运行前它们的页号就确定了所以程序运行前它们的页号就

50、确定了.对共享的程序必须规对共享的程序必须规定一个统一的页号定一个统一的页号.当共享程序的作业数增多时当共享程序的作业数增多时,要规定一个统要规定一个统一的页号是困难的一的页号是困难的n实现信息保护的办法是在页表中增加一些标志位实现信息保护的办法是在页表中增加一些标志位,用来指出该用来指出该页的信息可读页的信息可读/写写只读只读只可执行只可执行不可访问等不可访问等广州商学院计算机系广州商学院计算机系 kyykyy4.3.5 多级页表多级页表n现代的大多数计算机系统，都支持非常大的逻辑地址现代的大多数计算机系统，都支持非常大的逻辑地址空间空间(232264)。在这样的环境下，页表就变得非常大，。

51、在这样的环境下，页表就变得非常大，要占用相当大的内存空间。要占用相当大的内存空间。n例如，对于一个具有例如，对于一个具有32位逻辑地址空间的分页系统，位逻辑地址空间的分页系统，规定页面大小为规定页面大小为4 KB，则在每个进程页表中的页表项可，则在每个进程页表中的页表项可达达1兆个之多，又因为每个页表项占用兆个之多，又因为每个页表项占用4个字节，个字节， 故每故每个进程仅仅其页表就要占用个进程仅仅其页表就要占用4 MB的内存空间，而且还的内存空间，而且还要求是连续的。要求是连续的。广州商学院计算机系广州商学院计算机系 kyykyy多级页表（续）多级页表（续）n多级页表实现方法多级页表实现方法n

52、 （1）把整个页表进行分页，分成一张张小页表）把整个页表进行分页，分成一张张小页表(称为页表称为页表页或页目录表页或页目录表)，小页表的大小与页框相同，为进行索引查，小页表的大小与页框相同，为进行索引查找，为这些小页表建一张页目录表，其表项指出小页表所在找，为这些小页表建一张页目录表，其表项指出小页表所在页框号及相关信息页框号及相关信息n （2）系统为每个进程建一张页目录表，它的每个表项对应）系统为每个进程建一张页目录表，它的每个表项对应一个页表页，而页表页的每个表项给出了页面和页框的对应一个页表页，而页表页的每个表项给出了页面和页框的对应关系关系,页目录表是一级页表，页表页是二级页表页目录表

53、是一级页表，页表页是二级页表n （3）逻辑地址结构有三部分组成：页目录、页表页和位移）逻辑地址结构有三部分组成：页目录、页表页和位移 广州商学院计算机系广州商学院计算机系 kyykyy广州商学院计算机系广州商学院计算机系 kyykyy B offset目录位移 页表页位移 页内位移BF进程一级页表进程二级页表物理地址逻辑地址页目录表控制寄存器广州商学院计算机系广州商学院计算机系 kyykyyn4.4.1 程序分段结构程序分段结构n4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理n4.4.3 段的共享和保护段的共享和保护n4.4.4 分段和分页的比较分段和分页的比较4.4 分段式存储

54、管理分段式存储管理广州商学院计算机系广州商学院计算机系 kyykyyn基于模块化的程序设计，通常将一个大任务分成基于模块化的程序设计，通常将一个大任务分成若干个相对独立的子任务，对应于子任务编写子若干个相对独立的子任务，对应于子任务编写子程序，称为段。程序，称为段。n各个子程序可以独立的编辑、编译、链接和执行各个子程序可以独立的编辑、编译、链接和执行n各个子程序由实现的功能决定，长度各不相同。各个子程序由实现的功能决定，长度各不相同。执行时，根据实际需要将各个子程序链接成一个执行时，根据实际需要将各个子程序链接成一个大程序。大程序。4.4.1 程序分段结构程序分段结构- -分段存储管理的引入分

55、段存储管理的引入广州商学院计算机系广州商学院计算机系 kyykyy4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理 段号 段内偏移量l在分段存储管理方式中，作业的地址空间被划分为在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。若干个段，每个段定义了一组逻辑信息。 l每个段都有自己的名字。每个段都有自己的名字。 l每个段都从每个段都从0 0开始编址，并采用一段连续的地址空开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间，由于是分而各段长度不等。整个

56、作业的地址空间，由于是分成多个段，因而是二维的，亦即，其逻辑地址由段成多个段，因而是二维的，亦即，其逻辑地址由段号（段名）和段内地址所组成。号（段名）和段内地址所组成。l分段地址中的地址具有如下结构：分段地址中的地址具有如下结构：广州商学院计算机系广州商学院计算机系 kyykyy作业空间作业空间（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k内存空间内存空间30k 40k20k 80k 15k 120k 10k 150k 段长段长 段首址段首址段号段号0123段表段表段表：为每个分段分配一个连续的分区，而进程中的段表：为每个分段分配一个连续的分区，而进程中的各个段

57、可以离散地移入内存中不同的分区中。各个段可以离散地移入内存中不同的分区中。广州商学院计算机系广州商学院计算机系 kyykyy段表始址段表始址段表长度段表长度段号段号（2)100段表寄存器段表寄存器逻辑地址逻辑地址越界中断越界中断122980物理地址物理地址分段系统地址变换机构分段系统地址变换机构30k 40k20k 80k 15k 120k 10k 150k 段长段长 段首址段首址段号段号0123段表段表广州商学院计算机系广州商学院计算机系 kyykyy例题例题对以下段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230) 转换成物理地址.段号段号起始地址起始地址

58、段长段长050K10KB160K3KB2120K5KB370K8KB4150K4KB广州商学院计算机系广州商学院计算机系 kyykyy4.4.3 段的共享和保护段的共享和保护n段的共享是通过不同作业段表中的项指向同一个段基址来实现的n于是，几道作业共享的程序就可放在一个段中，只要让各道作业的共享部分有相同的基址/限长值就可以了n必须对共享段的信息进行存取控制和保护广州商学院计算机系广州商学院计算机系 kyykyyed1ed2ed40data1_1data1_10021122406041615070ed1ed2ed40data1_1data1_10data2_1data2_10进程进程1进程进程

59、2页表页表页表页表ed1ed2ed40data2_1data2_10主存分页系统中共享分页系统中共享editor02112240604161广州商学院计算机系广州商学院计算机系 kyykyy分段系统中共享分段系统中共享editoreditordata1editordata2段长段长基址基址1608040240段长段长基址基址1608040380editordata1data2在分段系统中，实现共享则容易得多，只需在每个进程在分段系统中，实现共享则容易得多，只需在每个进程的段表中为文本编辑程序设置一个段表项。的段表中为文本编辑程序设置一个段表项。进程进程1进程进程2段表段表广州商学院计算机系广州

60、商学院计算机系 kyykyy4.4.4 分段和分页的比较分段和分页的比较n分段是信息的逻辑单位，由源程序的逻辑结构所决分段是信息的逻辑单位，由源程序的逻辑结构所决定定,用户可见；分页是信息的物理单位，与源程序的用户可见；分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见。逻辑结构无关，用户不可见。n段长可根据用户需要来规定，段起始地址可从任何段长可根据用户需要来规定，段起始地址可从任何主存地址开始；页长由系统确定，页面只能以页大主存地址开始；页长由系统确定，页面只能以页大小的整倍数地址开始。小的整倍数地址开始。n分段方式中分段方式中,源程序源程序(段号段号,段内位移段内位移)经连结装配后