计算机操作系统课件复习资料_第4章

1、课程主要内容课程主要内容操作系统引论（操作系统引论（1章）章）进程管理（进程管理（2-3章）章）进程控制、进程同步、进程通信、进程控制、进程同步、进程通信、进程调度进程调度存储管理（存储管理（4章）章）存储分配与回收存储分配与回收地址变换地址变换内存扩充内存扩充存储保护与共享存储保护与共享设备管理（设备管理（5章）章）文件管理（文件管理（6章）章）OSOS中的存储管理是指对中的存储管理是指对内存内存( (并涉及外存并涉及外存) )的管理，是的管理，是OSOS的重要功能之一。的重要功能之一。第第4 4章章 存储器管理存储器管理v存储器的层次结构存储器的层次结构第第4 4章章 存储器管理存储器管理

2、v任务任务*为多道程序的运行提供良好的环境为多道程序的运行提供良好的环境，提高存提高存储器的利用率储器的利用率并并从逻辑上扩充存储器从逻辑上扩充存储器。v功能功能 存储分配与回收存储分配与回收 地址变换地址变换 内存扩充内存扩充 存储保护与共享存储保护与共享第第4 4章章 存储器管理存储器管理1.1.程序的装入和链接程序的装入和链接2.2.连续分配连续分配存储管理存储管理3.3.基本分页基本分页存储管理存储管理4.4.基本分段基本分段存储管理存储管理5.虚拟存储器虚拟存储器的基本概念的基本概念6.请求分页请求分页存储管理存储管理7.页面置换算法页面置换算法8.请求分段请求分段存储管理存储管理9

3、.9.补充：补充：请求段页式请求段页式存储管理存储管理4.1 4.1 程序的链接和装入程序的链接和装入v从源程序到程序执行从源程序到程序执行编译：由编译程序将用户源程序编译成若干个目标模块。如编译：由编译程序将用户源程序编译成若干个目标模块。如VC+中的中的Ctrl+F7(Compile)链接：由链接程序将目标模块和相应的库函数链接成装入模块。如链接：由链接程序将目标模块和相应的库函数链接成装入模块。如VC+中的中的F7(Build)装入：由装入程序将装入模块装入内存。如装入：由装入程序将装入模块装入内存。如VC+中的中的Ctrl+F5(BuildExecute)4.1 4.1 程序的链接和装

4、入程序的链接和装入库库汇编汇编编译编译主主子子1 1子子2 2目标模块目标模块链接程序链接程序装入模块装入模块库库主主子子1 1子子2 2装入程序装入程序内存内存库库主主子子1 1子子2 24.1 4.1 程序的链接和装入程序的链接和装入v地址空间地址空间程序名字程序名字空间：空间：汇编或高级语言程序中通常用符号名(符号地址)访问数据和子程序。这些符号名集合所限定的空间称作程序名字空间。相对相对/逻辑逻辑/虚地址虚地址空间：空间：(汇编或编译程序将符汇编或编译程序将符号地址转换为相对地址号地址转换为相对地址)目标程序中的相对地址目标程序中的相对地址集合。集合。绝对绝对/物理物理/实地址实地址空

5、间：内存中实际存储空间：内存中实际存储单元的地址集合。单元的地址集合。4.1 4.1 程序的链接和装入程序的链接和装入物理地址物理地址 内存内存000000000000001000010000200002. . . .010000100001FFF01FFF主主子子1 1子子2 2主主子子1 1子子2 2相对地址相对地址 装入模块装入模块000000. . . .FFFFFF主主子子1 1子子2 2 相对地址相对地址单个目标模块单个目标模块0000005FF5FF0000003FF3FF0000003FF3FF4.1 4.1 程序的链接和装入程序的链接和装入v地址重定位地址重定位将程序中的逻辑

6、将程序中的逻辑/相对地址转换成物理相对地址转换成物理/绝对绝对地址的过程地址的过程(地址变换地址变换/映射过程映射过程)。 v重定位的类型重定位的类型静态重定位：程序执行前，一次性，链接静态重定位：程序执行前，一次性，链接装入程序。装入程序。动态重定位：处理机每次访问主存时，由动态重定位：处理机每次访问主存时，由动态地址变换机构（硬件）自动执行。动态地址变换机构（硬件）自动执行。4.1 4.1 程序的链接和装入程序的链接和装入静态重定位示意图静态重定位示意图 4.1 4.1 程序的链接和装入程序的链接和装入动态重定位示意图动态重定位示意图 4.2 4.2 连续分配存储管理连续分配存储管理v基本

7、思想基本思想：为为一个用户程序一个用户程序分配分配一片连续的一片连续的内存空间内存空间。单一连续分区单一连续分区固定分区固定分区动态分区动态分区动态可重定位分区动态可重定位分区一、单一连续分区一、单一连续分区( (单道作业固定分区单道作业固定分区) )v将内存分为将内存分为系统区系统区(常为内存低端，分配给常为内存低端，分配给OS用用)和和用户区用户区(内存高端，分配给用户用内存高端，分配给用户用)。J优点：优点：简单易实现简单易实现(算法简单、硬件开销小算法简单、硬件开销小)L缺点：缺点：主存利用率低主存利用率低*有内碎片，造成很大浪费有内碎片，造成很大浪费*不支持多道程序设计，资源利用率低

8、不支持多道程序设计，资源利用率低*不能实验存储扩充不能实验存储扩充v改进：多个分区改进：多个分区固定分区固定分区可变分区可变分区v基本原理基本原理*预先预先( (系统初始化时系统初始化时) )将主存储器空间分割成将主存储器空间分割成大小相等或不等的若干块，每块称为一个分大小相等或不等的若干块，每块称为一个分区。区。分区个数和每个分区的大小分区个数和每个分区的大小固定不变，固定不变，每个分区装一个且只能装一个作业每个分区装一个且只能装一个作业直到该作直到该作业完成后才释放该分区业完成后才释放该分区(一个作业占用连续一个作业占用连续的一片存储空间的一片存储空间)。二、固定分区二、固定分区( (多道

9、作业固定分区多道作业固定分区) )8 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M固定分区固定分区( (大小相同大小相同) )固定分区固定分区( (大小不同大小不同) )二、固定分区二、固定分区( (多道作业固定分区多道作业固定分区) )v数据结构数据结构-分区说明表分区说明表(MBT)（1）内存分配图）内存分配图二、固定分区二、固定分区( (多道作业固定分区多道作业固定分区) )区号大小起址状态18k20k已分配232k28k已分配364k60k已分配4132k124k未分配(2)分区说明表分区说明表

10、通常将分区按 大小进行排序内碎片内碎片内碎片v内存分配：内存分配：v内存回收内存回收：程序执行完毕：程序执行完毕后释放占用的分区，管理后释放占用的分区，管理程序修改说明表。程序修改说明表。v地址变换地址变换：静态重定位或：静态重定位或动态重定位动态重定位(需要一需要一对界地址寄存器对界地址寄存器)二、固定分区二、固定分区( (多道作业固定分区多道作业固定分区) )二、固定分区二、固定分区( (多道作业固定分区多道作业固定分区) )J优点：简单易实现优点：简单易实现(算法简单、硬件开销小算法简单、硬件开销小)L缺点：主存利用率低缺点：主存利用率低有内碎片，造成浪费有内碎片，造成浪费虽然支持多道程

11、序设计虽然支持多道程序设计，但限制道数，但限制道数不能实不能实现存储共享与现存储共享与扩充扩充v基本原理：基本原理：内存内存不预先划分好不预先划分好( (相当于开始时相当于开始时用户区是一个连续分区用户区是一个连续分区) )，当作业装入时，当作业装入时，按按照作业的大小动态地建立分区。照作业的大小动态地建立分区。三、动态三、动态( (可变可变) )分区分区三、动态分区三、动态分区v 数据结构数据结构空闲分区表：空闲分区表：记录空闲分区的情况记录空闲分区的情况(分区号、分区号、分区起始地址、分区大小及状态分区起始地址、分区大小及状态)。 缺点：表长不易确定，管理困难且查找效率低。缺点：表长不易确

12、定，管理困难且查找效率低。三、动态分区三、动态分区v 数据结构数据结构空闲分区链：空闲分区链：用用链头指针链头指针将空闲分区链接将空闲分区链接起来。每个空闲分区的起始部分存放起来。每个空闲分区的起始部分存放本块本块大小和指向下一空闲分区的指针大小和指向下一空闲分区的指针。头指针头指针动态分区动态分区内存分配流程图内存分配流程图三、动态分区三、动态分区v内存分配内存分配三、动态分区三、动态分区v 根据根据空闲分区的四种组织方式空闲分区的四种组织方式，可有四种分，可有四种分配算法：配算法：首次适应算法首次适应算法(按按起址升序起址升序排序，从表首找起排序，从表首找起)循环首次适应算法循环首次适应算

13、法(按按起址升序起址升序排序，排序，从上从上次找到的空闲分区的下一个空闲分区开始找起次找到的空闲分区的下一个空闲分区开始找起)最佳适应算法最佳适应算法(按按容量升序容量升序排序，从表首找起排序，从表首找起)最坏适应算法最坏适应算法(按按容量降序容量降序排序，从表首找起排序，从表首找起)四种算法各有优缺点，没有一种是最好的。四种算法各有优缺点，没有一种是最好的。三、动态分区三、动态分区 首次适应算法（最先适应算法）首次适应算法（最先适应算法） 空闲分区按起始地址递增空闲分区按起始地址递增的次序排列。的次序排列。在进行内存分配时，在进行内存分配时，从空闲分区表从空闲分区表(链链)首开首开始顺序查找

14、始顺序查找，直到，直到找到第一个满足作业要求找到第一个满足作业要求的空闲分区为止的空闲分区为止。(找不到则分配失败，返回找不到则分配失败，返回)然后再按作业大小从该分区中划出一块内存然后再按作业大小从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空间分配给请求者，余下的空闲分区仍留在空闲分区表空闲分区表(链链)中中(要修改相关数据要修改相关数据)。区号区号大小大小起址起址132k20k28k52k3120k60k4331k180k空闲分区表空闲分区表例例 ：空闲分区表如右，现空闲分区表如右，现有三个作业分配申请内存有三个作业分配申请内存空间空间100K、30K及及7K。给。给出按首

15、次适应算法分配后出按首次适应算法分配后的空闲分区表。的空闲分区表。解：解：首次适应算法首次适应算法(最先适应算法最先适应算法)区号大小起址12k50k21k59k320k160k4331k180kJ优点：优点：分配和释放时分配和释放时间性能较好，较大的间性能较好，较大的空闲分区得以保留空闲分区得以保留L缺点：缺点：随着低端分区随着低端分区不断划分而产生较多不断划分而产生较多小分区，每次分配时小分区，每次分配时查找时间开销会增大查找时间开销会增大循环首次适应算法循环首次适应算法( (下次适应算法下次适应算法) ) 由首次适应算法演变而来。由首次适应算法演变而来。 在为作业分配内存空间时，在为作业

16、分配内存空间时，从上次找到从上次找到的空闲分区的下一个空闲分区开始查找的空闲分区的下一个空闲分区开始查找（到（到最后分区时再回到开头）最后分区时再回到开头），直到找到第一个，直到找到第一个能满足其大小要求的空闲分区为止。能满足其大小要求的空闲分区为止。三、动态分区三、动态分区区号区号大小大小起址起址132k20k28k52k3120k60k4331k180k空闲分区表空闲分区表例例 ：系统中的空闲分区系统中的空闲分区表如下，现有三个作业表如下，现有三个作业分配申请内存空间分配申请内存空间100K、30K及及7K。给出按循环。给出按循环首次适应算法分配后的首次适应算法分配后的空闲分区表。空闲分区

17、表。解：解：循环首次适应算法循环首次适应算法( (下次适应算法下次适应算法) )区号区号大小大小起址起址132k20k28k52k320k160k4294k217kJ优点：优点：内内存利用更加存利用更加均衡，不会使低端形成均衡，不会使低端形成很多小分区很多小分区L缺点：缺点：但这会导致缺但这会导致缺乏大的空闲分区。乏大的空闲分区。三、动态分区三、动态分区最佳适应算法最佳适应算法 “最佳最佳”是指每次为作业分配内存时，是指每次为作业分配内存时，总是把既总是把既能能满足要求的满足要求的又是又是最小的最小的空闲分区空闲分区分配给作业，避免分配给作业，避免“大材小用大材小用”。 空闲分区按容量递增空闲

18、分区按容量递增的次序排列。在进的次序排列。在进行内存分配时，行内存分配时，从空闲分区表从空闲分区表(链链)首开始首开始顺顺序查找，直到找到第一个满足其大小要求的序查找，直到找到第一个满足其大小要求的空闲分区为止。空闲分区为止。 分配后，所有空闲分区要重新进行排序分配后，所有空闲分区要重新进行排序。例：例：系统中的空闲分区表系统中的空闲分区表如右，现有三个作业分配如右，现有三个作业分配申请内存空间申请内存空间100K、30K及及7K。给出按最佳适应算。给出按最佳适应算法分配后的空闲分区表。法分配后的空闲分区表。解：解：区号大小起址18k52k232k20k3120k60k4331k180k空闲分

19、区表空闲分区表最佳适应算法最佳适应算法区号大小起址11k59k22k50k320k160k4331k180kJ优点：用最小空间满足要求。优点：用最小空间满足要求。从个别来看，外部碎片较小从个别来看，外部碎片较小L但从整体来看，会形成较多但从整体来看，会形成较多外部碎片。外部碎片。最坏适应算法最坏适应算法 空闲分区空闲分区按容量递减按容量递减的次序排列。在进行的次序排列。在进行内存分配时，内存分配时，从空闲分区表从空闲分区表(链链)首开始首开始顺序顺序查找，直到找到第一个比之大的空闲分区为查找，直到找到第一个比之大的空闲分区为止。止。 分配后，所有空闲分区要重新进行排序。分配后，所有空闲分区要重

20、新进行排序。三、动态分区三、动态分区三、动态分区三、动态分区区号区号大小大小起址起址1331k180k2120k60k332k20k48k52k空闲分区表空闲分区表最坏适应算法最坏适应算法例：例：空闲分区表如右，空闲分区表如右，现有三个作业分配申请现有三个作业分配申请内存空间内存空间100K100K、30K30K及及7K7K。给出按最坏适应算。给出按最坏适应算法分配后的空闲分区表。法分配后的空闲分区表。解：解：区号大小起址1194k317k2120k60k332k20k48k52kJ优点：优点：分割后空闲块仍分割后空闲块仍为较大空块。基本不留为较大空块。基本不留下小空闲分区下小空闲分区L缺点：

21、缺点：但较大的空闲分但较大的空闲分区不被保留。区不被保留。三、动态分区三、动态分区v练习：软件设计师试题练习：软件设计师试题*假设某计算机系统的内存大小为假设某计算机系统的内存大小为256K，在，在某一时刻内存的使用情况如图某一时刻内存的使用情况如图A所示。此时，所示。此时，若若进程顺序请求进程顺序请求20K、10K和和5K的存储空的存储空间间，系统采用，系统采用_算法为进程依次分配内算法为进程依次分配内存，则分配后的内存情况如图存，则分配后的内存情况如图B所示。所示。 三、动态分区三、动态分区起始起始地址地址0K20K50K90K100K105K135K160K175K195K220K状态状

22、态已用已用未用未用已用已用已用已用未用未用已用已用未用未用已用已用未用未用未用未用已用已用容量容量20K30K40K10K5K30K25K15K20K25K36K图图A A 起始起始地址地址0K20K40K50K90K100K105K135K145K160K175K195K200K220K状态状态已用已用已用已用未用未用已用已用已用已用未用未用已用已用已用已用未用未用已用已用未用未用已用已用未用未用已用已用容量容量20K20K10K40K10K5K30K10K15K15K20K5K20K36K图图B B A A最佳适应最佳适应 B B最差适应最差适应 C.C.首次适应首次适应 D D循环首次适

23、循环首次适应应 分别画出四种算法分配前后的空闲分区表。三、动态分区三、动态分区v内存回收内存回收(四种情况四种情况)v地址变换：动态重定位地址变换：动态重定位(需要一对界限需要一对界限R)。v存储保护：基址存储保护：基址/限长保护法；保护键法。限长保护法；保护键法。 J优点优点分区的大小和数目可变分区的大小和数目可变没有内碎片，提高了主存利用率没有内碎片，提高了主存利用率支持多道程序设计且不限制道数支持多道程序设计且不限制道数L缺点：存在外碎片；不能实现存储共享与扩缺点：存在外碎片；不能实现存储共享与扩充。充。三、动态分区三、动态分区固定分区和可变分区的碎片问题固定分区和可变分区的碎片问题内碎

24、片示意图内碎片示意图外碎片示意图外碎片示意图内碎片内碎片内碎片外外碎片问题的解决方法之一碎片问题的解决方法之一v紧凑（拼接）技术紧凑（拼接）技术*将内存中的将内存中的所有作业移到内存一端所有作业移到内存一端，同时，同时修改每个作业的起始地址，使本来分散的修改每个作业的起始地址，使本来分散的多个小空闲分区连成一个大的空闲区。多个小空闲分区连成一个大的空闲区。外外碎片问题的解决方法之一碎片问题的解决方法之一v紧凑（拼接）技术紧凑（拼接）技术*在在动态分区存储管理动态分区存储管理中中增加拼接功能增加拼接功能，在找，在找不到足够大的空闲分区来满足作业要求、而不到足够大的空闲分区来满足作业要求、而系统中

25、空闲分区系统中空闲分区总总容量可以满足作业要求时容量可以满足作业要求时进行拼接。进行拼接。四、动态可重定位分区四、动态可重定位分区动态可重定位分区分配算法流程图动态可重定位分区分配算法流程图四、动态可重定位分区四、动态可重定位分区四、动态可重定位分区四、动态可重定位分区J优点优点*可以充分利用内存中的碎片，提高内存可以充分利用内存中的碎片，提高内存利用率。利用率。L缺点缺点动态重定位需要硬件支持。动态重定位需要硬件支持。紧凑处理增加系统开销。紧凑处理增加系统开销。不能实现内存共享不能实现内存共享和和扩充扩充。五、存储保护五、存储保护v固定分区、可变分区、动态可重定位分区的固定分区、可变分区、动

26、态可重定位分区的存储保护措施：存储保护措施：1.界限寄存器界限寄存器*上下界寄存器方法上下界寄存器方法：用这两个寄存器分别：用这两个寄存器分别存放作业的存放作业的起始地址和结束地址起始地址和结束地址。*基址、限长寄存器方法基址、限长寄存器方法：用这两个寄存器：用这两个寄存器分别存放作业的分别存放作业的起始地址和作业的地址空起始地址和作业的地址空间长度间长度。五、存储保护五、存储保护2.存储保护键存储保护键*给给每个存储块每个存储块（大小相同，一个分区是存（大小相同，一个分区是存储块的整数倍）分配储块的整数倍）分配一个单独的保护键一个单独的保护键，它相当于一把锁。系统中的它相当于一把锁。系统中的

27、每个进程也赋每个进程也赋予一个保护键予一个保护键，它相当于一把钥匙。，它相当于一把钥匙。*当进程运行时，当进程运行时，检查钥匙和锁是否匹配检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，如果不匹配，则系统发出保护性中断信号，停止作业运行。停止作业运行。连续分配存储管理方式连续分配存储管理方式 小结小结单一连续分区：单一连续分区：不支持多道不支持多道程序设计，资源程序设计，资源利用率低利用率低固定分区：支持多道但存在固定分区：支持多道但存在内碎片内碎片动态分区动态分区没有内碎片但存在没有内碎片但存在外碎片外碎片分配与回收慢分配与回收慢(分配时查找时间长，释放时要合并分配时查找时间长，

28、释放时要合并)动态可重定位分区：解决了外碎片问题，但动态可重定位分区：解决了外碎片问题，但存储紧缩费时存储紧缩费时，代价较高，代价较高v四种技术都是连续分配方式，不能实现存储四种技术都是连续分配方式，不能实现存储共享与扩充。共享与扩充。外外碎片问题的解决方法之二碎片问题的解决方法之二*离散分配：离散分配：允许将程序允许将程序离散离散放到多个放到多个不相邻不相邻接接的分区中，可以避免拼接。基于这一思想的分区中，可以避免拼接。基于这一思想产生了以下离散分配方式：产生了以下离散分配方式：基本分页存储管理基本分页存储管理基本分段存储管理基本分段存储管理基本段页式存储管理基本段页式存储管理1. 内存空间

29、分成若干个大小相等内存空间分成若干个大小相等的块的块(页框页框)，各块从，各块从0开始编号。开始编号。4.3 4.3 基本分页存储管理基本分页存储管理一、基本思想一、基本思想物理内存物理内存0123456701103. 以页面为单位，将进程中若干页以页面为单位，将进程中若干页装入到多个可能不相邻的页框中。装入到多个可能不相邻的页框中。2. 2. 逻辑空间划分成若干个大小与逻辑空间划分成若干个大小与块相等的页块相等的页( (页面页面) )，各页也从，各页也从0 0开开始编号。始编号。用户进程用户进程k4.3 4.3 基本分页存储管理基本分页存储管理二、数据结构二、数据结构系统为每个进程设一张页表

30、系统为每个进程设一张页表，描述描述该进该进程占用的物理程占用的物理块块号等信息号等信息，放在内存。放在内存。4.3 4.3 基本分页存储管理基本分页存储管理二、数据结构二、数据结构*页表：为便于在进程运行时准确地找到各个页表：为便于在进程运行时准确地找到各个物理块，系统用页表物理块，系统用页表(页面映像表页面映像表)记录进程记录进程逻辑页与内存物理块之间的对应关系及存取逻辑页与内存物理块之间的对应关系及存取控制位。控制位。*系统设系统设页表寄存器页表寄存器用于存储用于存储正在运行进程的正在运行进程的页表基址及长度。页表基址及长度。*访问访问 1B 数据数据/指令需访问内存二次指令需访问内存二次

31、(页表一页表一次，数据次，数据/指令一次指令一次)，故，故内存访问速度降低内存访问速度降低。4.3 4.3 基本分页存储管理基本分页存储管理三、地址结构三、地址结构*采用页式管理时，用户程序中的逻辑地址仍采用页式管理时，用户程序中的逻辑地址仍然是连续的、一维的。然是连续的、一维的。页号p页内地址dn-1 k+1 k 0(n位位)逻辑地址结构逻辑地址结构(p,d) ：假设我们的一页只假设我们的一页只能容纳能容纳1000行，请行，请问我们写的文章的问我们写的文章的第第5678行行(从从0开始开始)会分到第几页会分到第几页(从从0开始开始)的第几行的第几行(从从0开始开始) ？自然截断自然截断4.3

32、 4.3 基本分页存储管理基本分页存储管理三、地址结构三、地址结构*内存地址是连续的、一维的。内存地址是连续的、一维的。块号b块内地址dm-1 k+1 k 0(m位位)物理地址结构物理地址结构(b,d)：假设我们写的文章假设我们写的文章的第的第5678行行(从从0开开始始)被抄写在第被抄写在第8号号(从从0开始开始)纸上，请纸上，请问第问第5678行对应的行对应的物理行号是多少？物理行号是多少？自然拼接自然拼接4.3 4.3 基本分页存储管理基本分页存储管理三、地址结构三、地址结构v例：设有一页式存储管理系统，向用户提供的逻例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为辑地址空间最

33、大为16页，每页页，每页2048B，内存总共有，内存总共有8个存储块，个存储块，(1)逻辑地址逻辑地址至少应为多少位？至少应为多少位？(2)内存内存空间空间有多大？有多大？v(1)2048=211，所以页内地址为，所以页内地址为11位。位。16=24，页号为，页号为4位。故逻辑地址至少为位。故逻辑地址至少为15位。位。 v(2)块与页大小相等，所以块内地址也为块与页大小相等，所以块内地址也为11位。位。8=23，块号为，块号为3位。故内存空间应为位。故内存空间应为214 =16KB。4.3 4.3 基本分页存储管理基本分页存储管理三、地址结构三、地址结构*若给定一个若给定一个逻辑地址逻辑地址空

34、间中的地址为空间中的地址为A，页页面大小面大小为为L，则则页号页号p和页内地址和页内地址d的计算公的计算公式为：式为：MODLAdLAINTP4.3 4.3 基本分页存储管理基本分页存储管理三、地址结构三、地址结构v例例1：页大小为：页大小为1024B，逻辑地址，逻辑地址3456对应的对应的数对数对(p,d)为多少？为多少？*（3，384）*思考思考 页内地址占几位？页内地址占几位？10位位 (210=1024) 若逻辑地址最大为若逻辑地址最大为123456，则页号需几，则页号需几位？位？int(123456/1024)=120；27=1281214.3 4.3 基本分页存储管理基本分页存储管

35、理三、地址结构三、地址结构v例例2：页大小为：页大小为1024B，则逻辑地址，则逻辑地址(4101)d的页号和页内地址可按如下二种方法计算：的页号和页内地址可按如下二种方法计算：v方法一：方法一：p=int(4101/1024)=4d=4101-4*1024=5 所以所以4101对应的数对应的数对是对是：(4,5)v方法二：方法二：(4101)d=(1000000000101)b因为因为1024=210，所以页内地址需要，所以页内地址需要10位位结果结果4101对应的数对是对应的数对是：(4,5)。4.3 4.3 基本分页存储管理基本分页存储管理四、地址变换四、地址变换(p,db,d)基本的地

36、址变换机构示意图基本的地址变换机构示意图物理地址的计算也有两种方法：物理地址的计算也有两种方法：(1)b*L+d(2)拼接拼接思考：越界中断有可能思考：越界中断有可能是页内地址引起的吗？是页内地址引起的吗？4.3 4.3 基本分页存储管理基本分页存储管理四、地址变换四、地址变换(p,db,d)v例：例：在一分页存储管理系统中，某作业的在一分页存储管理系统中，某作业的页表如表所示，已知页面大小为页表如表所示，已知页面大小为1024B，试将十进制逻辑地址试将十进制逻辑地址1011、2148和和5012转转换为相应的物理地址。换为相应的物理地址。v逻辑地址逻辑地址1011对应的物理地址为对应的物理地

37、址为3059。逻辑地址逻辑地址2148对应的物理地址为对应的物理地址为1124。 逻辑地址逻辑地址5012产生产生越界中断越界中断。页号块号021321364.3 4.3 基本分页存储管理基本分页存储管理四、地址变换四、地址变换(p,db,d)快表快表(联想存储器联想存储器)：是一种特殊的高速缓冲存储器。是一种特殊的高速缓冲存储器。存放当前访问的那些页表项。先在快表中寻找页先在快表中寻找页对应的物理块；若对应的物理块；若未找未找到到(未命中未命中)，再到页表中找再到页表中找，并将该页表，并将该页表项复制到快表。项复制到快表。若快表若快表已已满，则按某种算法淘汰某些页表满，则按某种算法淘汰某些页

38、表项。项。4.3 4.3 基本分页存储管理基本分页存储管理四、地址变换四、地址变换( (p,dp,db,db,d) )具有快表的地址变换机构具有快表的地址变换机构4.3 4.3 基本分页存储管理基本分页存储管理五、页的共享五、页的共享4.3 4.3 基本分页存储管理基本分页存储管理五、页的共享与保护五、页的共享与保护*页的共享：页的共享：一般不能实现共享，因为页的划一般不能实现共享，因为页的划分没有逻辑意义分没有逻辑意义*页的保护页的保护 地址越界检查地址越界检查在页表中设置在页表中设置存取控制位进行越权检查存取控制位进行越权检查 (定义操作权限：只读、读写、执行等定义操作权限：只读、读写、执

39、行等)4.3 4.3 基本分页存储管理基本分页存储管理J优点优点离散存放、无外碎片；离散存放、无外碎片；内存分配和释放速度快。内存分配和释放速度快。L缺点缺点(页表、动态地址转换机构、快表等页表、动态地址转换机构、快表等)增加系增加系统开销；统开销；内存访问速度降低；内存访问速度降低；每个进程平均拥有半页内碎片；每个进程平均拥有半页内碎片；页面共享困难；页面共享困难；程序需全部装入内存，不能进行存储扩充程序需全部装入内存，不能进行存储扩充。4.4 基本分段存储管理基本分段存储管理v程序按逻辑关系划分为段，从程序按逻辑关系划分为段，从0编号，有名字编号，有名字和段长。逻辑地址由段号和段内地址确定

40、。和段长。逻辑地址由段号和段内地址确定。v引入原因：满足用户要求引入原因：满足用户要求便于编程和调试便于编程和调试便于共享便于共享便于保护便于保护动态链接动态链接动态增长：动态增长：某些段某些段(数据段数据段)会不断增长，会不断增长，前面的存储管理方法难以实现。前面的存储管理方法难以实现。4.4 基本分段存储管理基本分段存储管理一、基本原理一、基本原理逻辑地址空间：逻辑地址空间：分段分段*划分为若干大小不等的段（由用户根据逻划分为若干大小不等的段（由用户根据逻辑信息的相对完整来划分），辑信息的相对完整来划分）， 段号从段号从0开始，开始，每段内的逻辑地址空间都从每段内的逻辑地址空间都从0开始编

41、址开始编址(段段内地址内地址)。物理物理地地址空间：址空间：可变分区可变分区*在为作业分配内存时，在为作业分配内存时，以段为单位以段为单位，分配，分配一段一段连续连续的物理地址空间；的物理地址空间；段间不必连续段间不必连续。4.4 基本分段存储管理基本分段存储管理基本原理示意图基本原理示意图二、数据结构：段表二、数据结构：段表每个进程设置一个段表，每个进程设置一个段表，描描述述该进程占用的物理分区及该进程占用的物理分区及逻辑排列顺序，逻辑排列顺序，放在内存。放在内存。段表的基址及长度段表的基址及长度(段数段数)由由段表寄存器段表寄存器给出给出4.4 基本分段存储管理基本分段存储管理段号段号 段

42、长段长 基址基址0 030k30k40k40k1 120k20k80k80k2 215k15k120k120k3 310k10k150k150k 访问访问 1B 数据数据/指令需访问内存二次指令需访问内存二次(段表一段表一次，内存一次次，内存一次)，所以也出现内存访问速度，所以也出现内存访问速度降低的问题。降低的问题。4.4 基本分段存储管理基本分段存储管理三、逻辑地址结构三、逻辑地址结构子程序段X数据段Acall X (调用X段的入口E)call Y (调用Y段的入口E)load 1,A (调用数组段AE)主程序段E：E：子程序段YE：模块化程序设计的分段结构模块化程序设计的分段结构三、逻辑

43、地址结构三、逻辑地址结构*进程的地址空间分成多个段，因而其逻辑地址是二维的，由段号(段名)和段内地址（段内偏移量）组成。4.4 基本分段存储管理基本分段存储管理内存内存四、存储分配四、存储分配*以段为单位，每段分配一块连续的分区以段为单位，每段分配一块连续的分区，一次分配作业所需的所有分区，一个进一次分配作业所需的所有分区，一个进程的各段所分到的分区不必相邻。程的各段所分到的分区不必相邻。4.4 基本分段存储管理基本分段存储管理第第0 0段段第第1 1段段第第2 2段段第第3 3段段用户作业用户作业段表基址段长150K35K500K9K300K20K100K42K3210段号第第0 0段段第第

44、1 1段段第第2 2段段第第3 3段段4.4 基本分段存储管理基本分段存储管理五、地址变换五、地址变换注意：两种越界情况！注意：两种越界情况！4 44.4 基本分段存储管理基本分段存储管理五、地址转换五、地址转换 逻辑地址逻辑地址(S,W)-物理地址物理地址当进程要访问某个逻辑地址中的数据时，系统将段号S与段表寄存器中的段表长度TL进行比较。如STL，则访问越界，发生越界中断；否则，根据S读出该段的基址；若段内地址W段长，则访问越界，发生越界中断；否则，将段的基址与段内地址W相加，得到逻辑地址对应的物理地址；根据此物理地址访问内存。4.4 基本分段存储管理基本分段存储管理五、地址转换五、地址转

45、换 例：例：现有一作业，在段式存储管理系统中，已为主存分配建立了如表所示的段表，试回答：该作业访问(1，120)、(2，200)、(4，600)时的绝对地址。（第一个元素为段号，第二个为段内地址）段号段长基址068017601160100022001560389028004.4 基本分段存储管理基本分段存储管理六、六、 存储保护存储保护段表寄存器段表寄存器越界检查：段表长度与段号越界检查：段表长度与段号S比较；段比较；段长与段内位移量长与段内位移量W比较比较存取控制位存取控制位越权检查越权检查分段系统中共享分段系统中共享editoreditor的示意图的示意图 4.4 基本分段存储管理基本分段

46、存储管理七、存储共享七、存储共享4.4 基本分段存储管理基本分段存储管理J优点优点没有内碎片；外碎片有改善且可通过紧凑没有内碎片；外碎片有改善且可通过紧凑技本来消除；技本来消除；便于编程、动态链接、动态申请内存、动便于编程、动态链接、动态申请内存、动态增长、存储共享和保护。态增长、存储共享和保护。L缺点缺点仍有外碎片；仍有外碎片；进程需全部装入内存，不能进行存储扩充。进程需全部装入内存，不能进行存储扩充。基本分页和基本分段的比较基本分页和基本分段的比较页式存储管理页式存储管理段式存储管理段式存储管理目的目的解决碎片问题解决碎片问题更好满足用户需要更好满足用户需要信息单位信息单位页（物理单位）页

47、（物理单位）段（逻辑单位）段（逻辑单位）大小大小固定固定(由系统定由系统定)用户不可见用户不可见不定不定(由用户程序定由用户程序定)用户可见用户可见内存分配内存分配单位单位页页段段逻辑地址逻辑地址一维一维二维二维优点优点解决了碎片问题解决了碎片问题提高内存利用率提高内存利用率便于共享、保护便于共享、保护段可动态增长段可动态增长便于动态链接便于动态链接二者优点的结合二者优点的结合-段页式存储管理段页式存储管理( (本章最后补充本章最后补充) )基本存储管理方式基本存储管理方式单一连续分区单一连续分区固定分区固定分区动态分区动态分区动态可重定位分区动态可重定位分区基本分页基本分页基本分段基本分段非

48、请求非请求段页式段页式4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念一、虚拟存储器的引入一、虚拟存储器的引入1. 局部性原理：局部性原理：程序在执行时呈现出局部性规律，程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。相应地，它所访问的存储空间也局限于某个区域。时间局部性时间局部性( (程序的循环结构程序的循环结构) )：一条指令被执行一条指令被执行/ /一一个存储单元被访问个存储单元被访问，则在，则在不久不久的将来的将来它可能再次被它可能再次被执行执行/ /访问访问空间局

49、部性空间局部性( (程序的顺序结构程序的顺序结构) )：一条指令被执行一条指令被执行/ /一一个存储单元被访问个存储单元被访问，则在，则在不久不久的将来，其的将来，其附近的附近的指令指令/ /存存储单元也可能被储单元也可能被执行执行/ /访问访问4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念一、虚拟存储器的引入一、虚拟存储器的引入2.2. 虚拟存储管理的基本思想虚拟存储管理的基本思想在在程序装入程序装入时，只需将当前需要执行的时，只需将当前需要执行的部分页部分页/段段读入到内存，就可让程序读入到内存，就可让程序开始执行开始执行。在程序执行过程中，如果需执行的指令或访问的在程序执行过程

50、中，如果需执行的指令或访问的数据不在内存数据不在内存(缺页缺页/段段)，则由处理器通知，则由处理器通知OS将将相应的页相应的页/段调入内存段调入内存，然后继续，然后继续执行程序执行程序。另一方面，另一方面，OS将内存中将内存中暂时不用的页暂时不用的页/段调出内段调出内存存，腾出空间存放将要装入的程序及将要调入的，腾出空间存放将要装入的程序及将要调入的页页/段。段。4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念一、虚拟存储器的引入一、虚拟存储器的引入3.虚拟存储器：具有虚拟存储器：具有请求调入功能和页请求调入功能和页/段置换段置换功能功能，能从能从逻辑上逻辑上对内存容量进行对内存容量进

51、行扩充扩充的存的存储器系统。储器系统。逻辑容量逻辑容量=可寻址范围可寻址范围实际容量实际容量=内存内存+外存对换区外存对换区若若CPUCPU的有效地址长度为的有效地址长度为3232位，则程序可位，则程序可以寻址范围是以寻址范围是0 02 23232-1 -1 ，即虚存逻辑容量，即虚存逻辑容量为为4GB4GB。XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-2

52、4K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间实地址空间实地址空间 虚页虚页页框页框虚拟页式存储器示意图虚拟页式存储器示意图4.5 4.5 虚拟存储器的基本概念虚拟存储器的基本概念一、虚拟存储器的引入一、虚拟存储器的引入4.4. 实现虚拟存储器的代价实现虚拟存储器的代价页表、段表页表、段表等数据结构等数据结构缺页中断机构缺页中断机构动态地址变换机构动态地址变换机构缺页缺页/ /段时的请求调页段时的请求调页/ /段和段和页页/ /段置换段置换v以以CPUCPU时间和辅存空间换取内存空间。时间和辅存空间换取内存空间。4.5 4.5 虚拟存储器的基本概念虚

53、拟存储器的基本概念二、虚拟存储器的特征二、虚拟存储器的特征多次性多次性：是虚拟存储器是虚拟存储器最重要最重要的特征。指的特征。指一个作业被分成多次调入内存运行。一个作业被分成多次调入内存运行。对换性：对换性：指允许在作业运行过程中进行换指允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率进、换出。换进、换出可提高内存利用率。虚拟性：虚拟性：指能够从逻辑上扩充内存容量，指能够从逻辑上扩充内存容量，使用户看到的内存容量远大于实际内存容使用户看到的内存容量远大于实际内存容量。量。4.6 4.6 请求分页存储管理请求分页存储管理v在在基本分页基本分页存储管理系统的基础上，存储管理系统的基础

54、上，增加请增加请求调页和页面置换功能求调页和页面置换功能所形成的页式虚拟存所形成的页式虚拟存储器系统。储器系统。v基本思想基本思想地址空间的划分与基本分页相同。作业地址空间的划分与基本分页相同。作业装装入时，不装入全部页面，只入时，不装入全部页面，只装入装入作业的一作业的一部分部分( (运行所需运行所需) )页即可运行页即可运行，之后根据进，之后根据进程运行的需要，程运行的需要，动态装入其它页面。动态装入其它页面。当内存已满而又需要装入新页时，则根据当内存已满而又需要装入新页时，则根据某种算法某种算法淘汰某个页面淘汰某个页面，以，以装入新页装入新页。4.6 请求分页存储管理请求分页存储管理一、

55、一、硬件支持硬件支持1. 页表页表 状态位：指示该页是否在内存状态位：指示该页是否在内存。访问字段：记录本页在一段时间内被访问的次数访问字段：记录本页在一段时间内被访问的次数或最近未被访问的时间。或最近未被访问的时间。修改位：表示该页在调入内存后是否被修改过。修改位：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。若修改过，则换出时需重写至外存。外存地址：指出该页在外存上的地址。外存地址：指出该页在外存上的地址。页号页号块号块号状态位状态位访问字段访问字段修改位修改位外存地址外存地址4.6 4.6 请求分页存储管理请求分页存储管理一、一、硬件支持硬件支持2. 缺页中断机构缺页

56、中断机构 当要访问的页不在内存当要访问的页不在内存(即缺页即缺页)时，便产时，便产生一个缺页中断生一个缺页中断，请求，请求OS将所缺页调入内存将所缺页调入内存空闲块，若无空闲块，则需置换某一页，同时空闲块，若无空闲块，则需置换某一页，同时修改页表。修改页表。4.6 4.6 请求分页存储管理请求分页存储管理开始开始页号页号页表长度页表长度？CPU检索快表检索快表NNY页表项在快表中？页表项在快表中？访问页表访问页表页在内存？页在内存？修改访问位和修改位修改访问位和修改位修改修改快快表表形成物理地址形成物理地址地址变换结束地址变换结束越界中断越界中断程序请求访问程序请求访问一页一页YN缺页中断处理

57、缺页中断处理Y保留保留CPU现场现场内存满吗？内存满吗？将一页从外存换入内存将一页从外存换入内存OS命令命令CPU从外存读缺页从外存读缺页启动启动I/O硬件硬件Y从外存中找到缺页从外存中找到缺页选择一页换出选择一页换出该页被修改否？该页被修改否？将该页写回外存将该页写回外存修改修改页页表表NYN一一、硬件支持硬件支持3. 地地址址变变换换机机构构4.6 4.6 请求分页存储管理请求分页存储管理一一、硬件支持硬件支持 3. 地址变换机构地址变换机构地址变换示意图地址变换示意图第第4 4章章 请求分页请求分页地址转换地址转换. .swfswf4.6 4.6 请求分页存储管理请求分页存储管理v例：例

58、：某虚拟存储器的用户空间共有某虚拟存储器的用户空间共有32个页面，每个页面，每页页1KB，主存，主存16KB。假定某时刻系统为用户的第。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为页分别分配的物理块号为5、10、4、7，试将虚拟地址，试将虚拟地址0A5C和和093C变换为物理地址。变换为物理地址。v解：页内位移和块内位移为解：页内位移和块内位移为10bits（110=1024）虚拟地址虚拟地址OA5C对应的二进制为：对应的二进制为：00010 1001011100即虚拟地址即虚拟地址OA5C的页号为的页号为2，对应的物理块，对应的物理块号为号为4，所以对应的物理地址为：，所以对

59、应的物理地址为：0100 1001011100 即即125C4.6 4.6 请求分页存储管理请求分页存储管理二、二、页面调入过程页面调入过程保留保留CPU现场现场内存满吗？内存满吗？将一页从外存换入内存将一页从外存换入内存OS命令命令CPU从外存读缺页从外存读缺页启动启动I/O硬件硬件Y从外存中找到缺页从外存中找到缺页选择一页换出选择一页换出该页被修改否？该页被修改否？将该页写回外存将该页写回外存修改页表修改页表NYN内存空间有限，不能内存空间有限，不能装入进程申请的所有装入进程申请的所有页面。页面。在装入新的页面时，在装入新的页面时，如果内存满，需要淘如果内存满，需要淘汰已装入页面。汰已装入

60、页面。4.7 4.7 页面置换算法页面置换算法v也称页面淘汰算法，是也称页面淘汰算法，是决定选择淘汰哪一页的决定选择淘汰哪一页的规则规则。v算法算法衡量标准：衡量标准：缺页中断率缺页中断率 f=F/A; 其中，A：作业执行中访问页面的总次数 F：缺页中断次数v算法目标：降低缺页率算法目标：降低缺页率4.7 4.7 页面置换算法页面置换算法v常用算法常用算法最佳最佳置换算法置换算法OPT：淘汰永远不再需要的页淘汰永远不再需要的页面或面或最远的将来最远的将来才需要访问的页面。才需要访问的页面。先进先出先进先出置换算法置换算法FIFO：淘汰淘汰最先进入内最先进入内存存的页面的页面。最近最久未用最近最