操作系统_第四章 存储器管理

1、1第四章第四章 存储器管理存储器管理4.1 4.1 存储器的层次结构存储器的层次结构4.2 4.2 程序的装入和链接程序的装入和链接 4.3 4.3 连续分配方式连续分配方式 4.4 4.4 基本分页存储管理方式基本分页存储管理方式 4.5 4.5 基本分段存储管理方式基本分段存储管理方式 4.6 4.6 虚拟存储器的基本概念虚拟存储器的基本概念 4.7 4.7 请求请求分页存储管理方式分页存储管理方式 4.8 4.8 页面置换算法页面置换算法 4.9 4.9 请求分段存储管理方式请求分段存储管理方式 24.1 存储器的层次结构 4.1.1 多级存储器结构多级存储器结构 寄存器高速缓存主存磁盘

2、缓存磁盘可移动存储介质CPU寄存器主存辅存图41 计算机系统存储层次示意3 1 主存储器 2 寄存器4.1.2 主存储器与寄存器主存储器与寄存器 4 1 高速缓存 CPU产品中，一级缓存的容量基本在4KB到64KB之间，一级缓存容量各产品之间相差不大。二级缓存容量则是提高CPU性能的关键。二级缓存容量的提升是由CPU制造工艺所决定的，容量增大必然导致CPU内部晶体管数的增加，要在有限的CPU面积上集成更大的缓存，对制造工艺的要求也就越高 4.1.3 高速缓存与磁盘缓存高速缓存与磁盘缓存5 上溯到上个世纪80年代，由于处理器的运行速度越来越快，慢慢地，处理器需要从内存中读取数据的速度需求就越来越

3、高了。然而内存的速度提升速度却很缓慢，而能高速读写数据的内存价格又非常高昂，不能大量采用。从性能价格比的角度出发，英特尔等处理器设计生产公司想到一个办法，就是用少量的高速内存和大量的低速内存结合使用，共同为处理器提供数据。这样就兼顾了性能和使用成本的最优。而那些高速的内存因为是处于CPU和内存之间的位置，又是临时存放数据的地方，所以就叫做缓冲存储器了，简称“缓存”。 6它的作用就像仓库中临时堆放货物的地方一样，货物从运输车辆上放下时临时堆放在缓存区中，然后再搬到内部存储区中长时间存放。货物在这段区域中存放的时间很短，就是一个临时货场。现在，为了适应速度更快的处理器P4EE，已经出现了三级缓存了

4、，它的容量更大，速度相对二级缓存也要慢一些，但是比内存可快多了。 缓存的出现使得CPU处理器的运行效率得到了大幅度的提升，这个区域中存放的都是CPU频繁要使用的数据，所以缓存越大处理器效率就越高，同时由于缓存的物理结构比内存复杂很多，所以其成本也很高。 大量使用二级缓存带来的结果是处理器运行效率的提升和成本价格的大幅度不等比提升。举个例子，服务器上用的至强处理器和普通的P4处理器其内核基本上是一样的，就是二级缓存不同。至强的二级缓存是2MB16MB，P4的二级缓存是512KB，于是最便宜的至强也比最贵的P4贵，原因就在二级缓存不同。 7 Intel Core i7-980X Extreme E

5、dition 3.33GHz 12M L3Cache LGA1366 六核处理 厂商 Intel CPU名称 E6500 系列 Pentium Duo 接口类型 LGA 775 核心数量 双核 工作频率 2.93GHz 前端总线 1066MHz 一级缓存 2x(32k+32k) 二级缓存 2MB 是否支持64位运算 是 制造工艺 45nm 2 磁盘缓存84.2 程序的装入和链接 编辑编辑编译编译链接链接装入装入运行运行图图4-2 对用户程序的处理步骤对用户程序的处理步骤94.2.1 程序的装入 1 1、绝对装入：、绝对装入： 编译后，装入前已产生了绝对地址（内存地址），装编译后，装入前已产生了

6、绝对地址（内存地址），装入时不再作地址重定位入时不再作地址重定位, ,适用于单道系统。适用于单道系统。 绝对地址的产生：（绝对地址的产生：（1 1）由编译器完成，（）由编译器完成，（2 2）由程序）由程序员编程完成。员编程完成。 对（对（1 1）而言，编程用符号地址。）而言，编程用符号地址。2 2、可重定位装入；、可重定位装入； 静态重定位：装入时完成，主要工作是对相对地址中静态重定位：装入时完成，主要工作是对相对地址中的的指令指令和和数据地址数据地址的调整过程，例：图的调整过程，例：图4 43 310图图 4-3 4-3 作业装入内存时的情况作业装入内存时的情况 114.2.1 程序的装入

7、3.3.动态运行时装入动态运行时装入 可重定位装入方式在装入后不能移动程序可重定位装入方式在装入后不能移动程序 该情况一般在执行时才完成相对该情况一般在执行时才完成相对绝对地址的转换且绝对地址的转换且有硬件的支持有硬件的支持, ,能保证进程的可移动性。能保证进程的可移动性。 Routine is not loaded until it is calledRoutine is not loaded until it is called Better memory-space utilization; unused routine Better memory-space utilization;

8、unused routine is never loaded.is never loaded. Useful when large amounts of code are needed to Useful when large amounts of code are needed to handle infrequently occurring cases.handle infrequently occurring cases. No special support from the operating system is No special support from the operati

9、ng system is required implemented through program design.required implemented through program design.124.2.2 4.2.2 程序的链接程序的链接1 1、静态链接：事先连接、静态链接：事先连接a a对相对地址的修改对相对地址的修改b b变换外部调用符号变换外部调用符号2 2、装入时动态链接：边装入边连接、装入时动态链接：边装入边连接a.a.便于修改和更新便于修改和更新b.b.便于实现对目标模块的共享便于实现对目标模块的共享13(a)(a)目标模块目标模块模块模块A ACALL B;CALL

10、B;RETURNRETURN模块模块B BCALL C;CALL C;RETURNRETURN模块模块C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1模块模块A AJSR L;JSR L;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)装入模块装入模块图图 4-4 4-4 程序链接示意图程序链接示意图 143 3、运行时动态链接、运行时动态链接Dynamic LinkingDyna

11、mic Linking近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。154.3 连续分配方式 4.3.14.3.1单一连续分配单一连续分配 用于单用户，单任务中用于单用户，单任务中4.3.24.3.2分区式分配分区式分配 固定式固定式 动态分区分配动态分区分配 可重定位分区

12、分配可重定位分区分配164.3.1 单一连续分区 这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用。174.3.2 固定分区特点：有特点：有n n个分区，则可同时装入个分区，则可同时装入n n个作业个作业/ /任务。任务。一、分区大小：一、分区大小： 相等相等: : 不相等：不相等利用率更高。不相等：不相等利用率更高。二、内存分配：二、内存分配：数据结构数据结构 将分区按大小排序，建立将分区按大小排序，建立分区使用

13、表分区使用表，并将其地址、，并将其地址、分配标识作记录分配标识作记录三、特点：三、特点：简单，有碎片（内零头）简单，有碎片（内零头）, ,浪费。浪费。18图图 4-5 4-5 固定分区使用表固定分区使用表 194.3.3 动态分区分配一、数据结构一、数据结构1 1空闲分区表空闲分区表2 2空闲分区链空闲分区链图图 4-6 4-6 空闲链结构空闲链结构 20二、分配算法二、分配算法1 1首次适应算法首次适应算法FFFF。 要求：分区按低址要求：分区按低址高址链接高址链接 特点：找到第一个大小满足的分区，划分。有外零头，特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。低址内存使用

14、频繁。2 2循环首次适应算法。循环首次适应算法。 从从1 1中上次找到的空闲分区的下一个开始查找。中上次找到的空闲分区的下一个开始查找。 特点：空闲分区分布均匀，提高了查找速度；缺乏大特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。的空闲分区。3 3最佳适应算法最佳适应算法 分区按大小递增排序；分区释放时需插入到适当位置分区按大小递增排序；分区释放时需插入到适当位置 分割后留下小碎片，难以利用。分割后留下小碎片，难以利用。4.3.3 动态分区分配21二、分配算法二、分配算法4 4最坏适应算法最坏适应算法WFWF。 总是挑选最大的空闲分区分割给作业使用总是挑选最大的空闲分区分割给作业使

15、用 分区按大小递减排序；分区按大小递减排序； 优点：剩下碎片不至于太小优点：剩下碎片不至于太小 缺点：缺乏大的空闲分区缺点：缺乏大的空闲分区5. 5. 快速适应算法快速适应算法QFQF 分类搜索：将空闲分区根据容量大小分类分类搜索：将空闲分区根据容量大小分类 设立管理索引表设立管理索引表 优点：查找效率高；不要分割优点：查找效率高；不要分割 缺点：分区归还主存时复杂，开销大缺点：分区归还主存时复杂，开销大4.3.3 动态分区分配22三、分区分配操作三、分区分配操作1 1分配：图分配：图4-74-72 2回收：回收：（1 1）上邻空闲区：合并，改大小）上邻空闲区：合并，改大小（2 2）下邻空闲区

16、：合并，改大小，首址。）下邻空闲区：合并，改大小，首址。（3 3）上、下邻空闲区：合并，改大小。）上、下邻空闲区：合并，改大小。（4 4）不邻接，则建立一新表项。）不邻接，则建立一新表项。4.3.3 动态分区分配23图图 4-7 4-7 内存分配流程内存分配流程242) 回收内存 图图 4-8 内存回收时的情况内存回收时的情况 25例例1 某系统采用动态分区分配方式管理内存，内存某系统采用动态分区分配方式管理内存，内存空间为空间为640K640K，高端，高端40K40K用来存放操作系统。在内存用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列分配时，系统优先使用空闲区低端的空

17、间。对下列的请求序列：作业的请求序列：作业1 1申请申请130K130K、作业、作业2 2申请申请60K60K、作、作业业3 3申请申请100K100K、作业、作业2 2释放释放60K60K、作业、作业4 4申请申请200K200K、作、作业业3 3释放释放100K100K、作业、作业1 1释放释放130K130K、作业、作业5 5申请申请140K140K、作业作业6 6申请申请60K60K、作业、作业7 7申请申请50K50K、作业、作业6 6释放释放60K60K，请，请分别画图表示出使用首次适应算法和最佳适应算法分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用

18、情况。进行内存分配和回收后内存的实际使用情况。26首次适应算法最佳适应算法解解274.3.6 可重定位分区分配1.1.动态重定位的引入动态重定位的引入 连续式分配中，总量大于作业大小的多个小连续式分配中，总量大于作业大小的多个小分区不能容纳作业。分区不能容纳作业。 紧凑紧凑 通过作业通过作业移动移动将原来分散的小分区将原来分散的小分区拼接拼接成成一个大分区。一个大分区。 每次紧凑后，都必须对移动了的程序或数每次紧凑后，都必须对移动了的程序或数据进行据进行重定位重定位。28图图 4-9 4-9 紧凑的示意紧凑的示意 292、动态重定位的实现图图 4-10 动态重定位示意图动态重定位示意图 动态重

19、定位：相对地址动态重定位：相对地址物理地址是在程序执行时自动进行物理地址是在程序执行时自动进行303. 动态重定位分区分配算法动态重定位分区分配算法 图图 4-11 动态重定位分区分配算法流程图动态重定位分区分配算法流程图 31内存扩充内存扩充 实现内存扩充的三种技术： 覆盖技术(overlay) 交换技术(swapping) 虚拟存储器（virtual memory）32 覆盖覆盖(overlay)(overlay) 引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必

20、要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)33注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；覆盖技术覆盖技术344.3.7 4.3.7 对换（对换（SwappingSwapping）1 1 对换的引入对换的引入 将阻塞进程，暂时不用的程序，数据换出。将阻塞进程，暂时不用的程序，

21、数据换出。 将具备运行条件的进程换入。将具备运行条件的进程换入。 类型：类型： 整体对换：进程对换，解决内存紧张整体对换：进程对换，解决内存紧张 部分对换：页面对换部分对换：页面对换/ /分段对换：提供虚存支持分段对换：提供虚存支持2 2 对换空间的管理对换空间的管理 外存外存 对换区对换区比比文件区文件区侧重于对换侧重于对换速度速度。 因此，对换区一般采用因此，对换区一般采用连续连续分配。采用数据结构和分配。采用数据结构和分配回收类似于可变化分区分配。分配回收类似于可变化分区分配。354.3.7 4.3.7 对换对换3 3 换出与换入换出与换入（1 1）换出）换出 选出被换出进程：选出被换出

22、进程：因素：优先级，驻留时间，进程状态因素：优先级，驻留时间，进程状态 换出过程：换出过程：对于共享段：计数减对于共享段：计数减1 1， 是是0 0则换出，否则不换则换出，否则不换修改修改PCBPCB和内存分配表和内存分配表（2 2）换入：）换入： 选择换入进程：优先级，换出时间等。选择换入进程：优先级，换出时间等。 申请内存。申请内存。 换入换入364.44.4基本分页存储管理基本分页存储管理 连续分配引起连续分配引起: :碎片碎片 碎片问题的解决：碎片问题的解决：紧凑紧凑方式消耗系统开销。方式消耗系统开销。 离散分配离散分配 分页分页 不具备页面对换功能的称为基本分页存储管理方式不具备页面

23、对换功能的称为基本分页存储管理方式 分段分段 段页段页371.1.页面页面 页面和物理块：逻辑空间和内存空间，页面和物理块：逻辑空间和内存空间，页内碎片页内碎片 页面大小由机器的地址结构决定页面大小由机器的地址结构决定 页太大，页内碎片大。页太大，页内碎片大。 页太小：页表可能很长，换入页太小：页表可能很长，换入/ /出效率低出效率低2.2.地址结构地址结构3131 12 11 12 11 0 0 逻辑地址逻辑地址A A；页大小；页大小L(L(设为设为1024)1024)；页内偏移；页内偏移d d P= IntAP= IntA/L/Ld=A mod Ld=A mod L如：如： A A2170

24、B. 2170B. 则则P=2, d=122 P=2, d=122 4.4.1页面与页表页号页号P P 位移位移W W 383.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 50 01 12 23 34 45 56 67 78 89 9用户程序用户程序页表页表页号页号块号块号内存内存39Paging Example 40 例例1 1：某系统采用页式存储管理策略，拥有逻辑：某系统采用页式存储管理策略，拥有逻辑空间空间3232页，每页页，

25、每页2K2K，拥有物理空间，拥有物理空间1M1M 写出逻辑地址的格式写出逻辑地址的格式 若不考虑访问权限等，进程的页表有多少项？若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？每项至少有多少位？ 如果物理空间减少一半，页表结构应相应作如果物理空间减少一半，页表结构应相应作怎样的改变？怎样的改变？41 答：答： 该系统拥有逻辑空间该系统拥有逻辑空间3232页，故逻辑地址中页页，故逻辑地址中页号必须用号必须用5 5位描述；而每页为位描述；而每页为2K2K，因此，页内地，因此，页内地址必须用址必须用1111位描述，格式如下：位描述，格式如下： 151511 1011 10 0 0 每个进程

26、最多每个进程最多3232个页面，因此进程的页表项个页面，因此进程的页表项最多为最多为3232项；页表项只需给出页所对应的物理项；页表项只需给出页所对应的物理块块号，块块号，1M1M的物理空间可分为的物理空间可分为2 29 9个内存块，故个内存块，故每个页表项至少有每个页表项至少有9 9位。位。 如果物理空间减少一半，则页表中页表项数如果物理空间减少一半，则页表中页表项数不变，但每项的长度减少不变，但每项的长度减少1 1位。位。页号页号页内地址页内地址424.4.2 地址变换机构 基本任务基本任务：借助页表完成逻辑页号：借助页表完成逻辑页号- -物理块号的映射。物理块号的映射。1 1、基本地址变

27、换机构：、基本地址变换机构： 页表寄存器：页表寄存器：页表始址，页表长度页表始址，页表长度 平时每个进程未执行时将其信息（如页表长度、始址）平时每个进程未执行时将其信息（如页表长度、始址）放在放在PCBPCB中，执行时将它们装入中，执行时将它们装入页表寄存器页表寄存器。 地址变换机构自动将有效地址分为地址变换机构自动将有效地址分为页号页号和和页内地址页内地址 越界保护越界保护 检索页表检索页表 生成物理地址生成物理地址4344 例例2 2：已知某分页系统，主存容量为：已知某分页系统，主存容量为64K64K，页面大，页面大小为小为1K1K，对一个，对一个4 4页大的作业，其页大的作业，其0 0、

28、1 1、2 2、3 3页页分别被分配到主存的分别被分配到主存的2 2、4 4、6 6、7 7块中。块中。 （1 1）将十进制的逻辑地址）将十进制的逻辑地址10231023、25002500、35003500、45004500转换成物理地址？转换成物理地址？ （2 2）以十进制的逻辑地址）以十进制的逻辑地址10231023为例画出为例画出地址变地址变换过程图换过程图？45 答答：逻辑地址逻辑地址10231023：1023/1K1023/1K，得页号为，得页号为0 0，页内地址，页内地址为为10231023，查页表找到对应的物理块号为，查页表找到对应的物理块号为2 2，故物理地，故物理地址为址为2

29、 21K+1023=30711K+1023=3071 逻辑地址逻辑地址25002500：2500/1K2500/1K，得页号为，得页号为2 2，页内地址，页内地址为为452452，查页表找到对应的物理块号为，查页表找到对应的物理块号为6 6，故物理地，故物理地址为址为6 61K+452=65961K+452=6596 逻辑地址逻辑地址35003500：3500/1K3500/1K，得页号为，得页号为3 3，页内地址，页内地址为为428428，查页表找到对应的物理块号为，查页表找到对应的物理块号为7 7，故物理地，故物理地址为址为7 71K+428=75961K+428=7596 逻辑地址逻辑地

30、址45004500：4500/1K4500/1K，得页号为，得页号为4 4，页内地址，页内地址为为404404，因页号不小于页表长度，故产生，因页号不小于页表长度，故产生越界中断越界中断。46 （2）地址变换过程图地址变换过程图472.2.具有快表的地址变换机构具有快表的地址变换机构 Associative memory parallel search Address translation (A, A) If A is in associative register, get frame # out. Otherwise get frame # from page table in memo

31、ryPage #Frame #482.2.具有快表的地址变换机构具有快表的地址变换机构先查快表，若有则得出块号先查快表，若有则得出块号若无，则再查页表，得出块号，并重新修改快表若无，则再查页表，得出块号，并重新修改快表492.2.具有快表的地址变换机构具有快表的地址变换机构 不具快表，则需不具快表，则需两次两次访问内存。访问内存。（1 1）访页表，得到物理地址）访页表，得到物理地址（2 2）得到物理地址中的数据）得到物理地址中的数据 有快表，有快表，命中率高，命中率高，速度提高。速度提高。 快表贵，不能太多。快表贵，不能太多。50 例例3 3：有一页式系统，其页表存放在主存中：有一页式系统，其

32、页表存放在主存中： 如果对主存的一次存取需要如果对主存的一次存取需要1.5 1.5 s,s,试问实试问实现一次页面访问的存取时间是多少现一次页面访问的存取时间是多少? ? 如果系统加有快表如果系统加有快表, ,平均平均命中率命中率为为85%,85%,当页表当页表项在快表中时项在快表中时, ,其查找时间忽略为其查找时间忽略为0, 0, 试试问此时问此时的存取时间是多少的存取时间是多少? ?51答答：若页表存放在主存中，则要实现一次页面访问需：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第

33、二次才根据该地址存的物理地址（称为定位）。第二次才根据该地址存取页面数据。取页面数据。 页表在主存的存取访问时间页表在主存的存取访问时间 =1.5=1.5* *2=3(s)2=3(s) 增加增加快表快表后的存取访问时间后的存取访问时间 =0.85=0.85* *1.5+(1-0.85)1.5+(1-0.85)* *2 2* *1.5=1.725(s)1.5=1.725(s)524.4.3 4.4.3 两级和多级页表两级和多级页表 页表可能很大，将其离散存放在不同页块中。页表可能很大，将其离散存放在不同页块中。 建一建一“外外部部页表页表”来管理这些离散页表块。来管理这些离散页表块。 相当于单级

34、相当于单级页表中页表中的页表寄存器，一般应常驻内存。的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。每项记录页表始址，且增加存在位。 6464位机器页表一般位机器页表一般33级，最外层页表常驻。级，最外层页表常驻。 1. 两级页表两级页表(Two-Level Page Table) 逻辑地址结构可描述如下： 53图图 4-15 两级页表结构两级页表结构 5455例例4 4某虚拟存储器的用户编程空间共某虚拟存储器的用户编程空间共3232个页面，个页面，每页为每页为1KB1KB，内存为，内存为16KB16KB。假定某时刻一用户。假定某时刻一用户页表中已调入内存的页面对应的物理块号如页

35、表中已调入内存的页面对应的物理块号如下表：下表：页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址0A5C0A5C（H H）所对应的物理地址为多少？）所对应的物理地址为多少？56答 0A5C0A5C0000,100000,1010,0101,110010,0101,1100 页号为页号为2 2，对应块号为，对应块号为4 4，有：，有： 物理地址：物理地址：00010001，000010,0101,110010,0101,1100 即：即：125C125C（H H）574.54.5基本分段存储管理基本分段存储管理 引入分页存储管理方式的引入分页存储管理

36、方式的目的是提高内存利用率目的是提高内存利用率4.5.1 4.5.1 分段存储管理方式的引入分段存储管理方式的引入 满足用户和程序员的以下需求：满足用户和程序员的以下需求：（1 1）方便编程；）方便编程；（2 2）分段共享；）分段共享；（3 3）分段保护；）分段保护；（4 4）动态增长；（如数据段的增长）动态增长；（如数据段的增长）（5 5）动态链接；）动态链接；584.4.2 4.4.2 分段系统的基本原理分段系统的基本原理 1.1. 分段分段对用户而言，分段是对用户而言，分段是2 2维的。维的。段号段号+ +段内地址。段内地址。得到编译程序的支持得到编译程序的支持2.2. 段表段表：基址基

37、址+ +段长段长逻辑段逻辑段mapmap物理内存区物理内存区3.3. 地址变换机构：地址变换机构：图图4 41717，4 41818段表寄存器、段表寄存器、两种越界中断两种越界中断4.4. 分页与分段的主要区别：分页与分段的主要区别：（1 1）页是信息的物理单位，段是逻辑单位）页是信息的物理单位，段是逻辑单位（2 2）页长度固定，段长度不固定（由用户指定）页长度固定，段长度不固定（由用户指定）（3 3）一维与二维）一维与二维 59608 861例5对于下面的段表，请将逻辑地址（0,137），（1,4000），(2,3600)，(5,230)转换成物理地址。段号内存地址段长050K10K160K

38、3K270K5K3120K8K4150K4K62答1. 物理地址为：50K+137=513372. 段内地址超过段长3K，产生越界中断。3. 物理地址为：70K+3600=752804. 段号等于段表长，段号不合法，产生越界中断。634.5.3 4.5.3 信息共享信息共享 分段的分段的优点优点：段式系统易于共享：段式系统易于共享 例：图例：图4-194-19及及4-24-20 0 分页与分段共享比较分页与分段共享比较 可重入代码可重入代码（纯代码）（纯代码） 可重入代码是一种不允许任何进程对可重入代码是一种不允许任何进程对它进行修改的代码它进行修改的代码 各个进程应保留局部数据区各个进程应保

39、留局部数据区64ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表图图 4-19 分页系统中共享分页系统中共享editor的示意图的示意图65图 4-20 分段系统中共享editor的示意图 editor进程1data 1进程2editordata 2段表段长基址16080402401608040380editordata 1data 280240280380420664

40、.5.4 4.5.4 段页式存储管理段页式存储管理 分页优点：提高内存利用率分页优点：提高内存利用率 分段优点：方便用户，易于共享，保护，动态分段优点：方便用户，易于共享，保护，动态链接。链接。1 1、段页式系统基本原理、段页式系统基本原理 段号段号+ +段内页号段内页号+ +页内地址页内地址 注意：注意： 对用户而言，仍然是二维编址。对用户而言，仍然是二维编址。 对系统而言，则是三维编址对系统而言，则是三维编址 图图4-204-20 图图4-214-2167图 4-21 作业地址空间和地址结构 04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号

41、(P)段内地址(W)(b)主程序段68图 4-22 利用段表和页表实现地址映射 694.5.4 4.5.4 段页式存储管理段页式存储管理2 2、地址变换、地址变换 三次访内存操作三次访内存操作，为提高速度，在地址变换机，为提高速度，在地址变换机构中增设一高速缓冲寄存器（构中增设一高速缓冲寄存器（CacheCache）704.6 虚拟存储器 分页内存分配和分段内存分配方法可以解决程序在内存中离散存放的问题，但是，这两种方式都要求程序整个装入内存。事实上，很多时候，程序本身比内存要大得多，那么简单的分页和分段的内存方式就无法解决这个问题了。可以采用虚拟存储器的方法，使用请求分配和置换策略来实现存储

42、管理。4.6.虚拟存储器为什么需要虚拟存储器： 程序大于内存 程序暂时不执行或运行完是否还要占用内存 程序的局部性原理724.64.6虚拟存储器虚拟存储器4.6.1 4.6.1 引入引入1.1.常规存储管理的特征：常规存储管理的特征： 一次性（指全部装入）、一次性（指全部装入）、 驻留性（指驻留在内存不换出）驻留性（指驻留在内存不换出）2 2、局部性原理、局部性原理 时间局部性：如循环执行时间局部性：如循环执行 空间局部性：如顺序执行。空间局部性：如顺序执行。3 3、虚拟存贮器、虚拟存贮器 具有请求调入功能和置换功能，能从逻辑上对具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存

43、储系统。内存容量进行扩充的一种存储系统。 实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺牲不大。 虚存大小由虚存大小由_决定。决定。73 虚拟存储器技术需要解决的问题 ：地址映射 分配策略 置换策略 装载控制 744.6.2 4.6.2 虚拟存储器的实现方式虚拟存储器的实现方式需要需要动态重定位动态重定位1 1、请求分页系统、请求分页系统 以页为单位转换以页为单位转换 需硬件：需硬件：（1 1）请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构 需实现请求分页机制的软件（页面请调、置换软件等）需实现请求分页机制的软件（页面请

44、调、置换软件等）2 2、请求分段系统、请求分段系统 以段为单位转换以段为单位转换: :（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构 需实现请求分段机制的软件（段请调、置换软件等）需实现请求分段机制的软件（段请调、置换软件等）754.6.3 4.6.3 虚存特征虚存特征1 1多次性多次性：局部装入，多次装入。：局部装入，多次装入。2 2对换性对换性：换进、换出：换进、换出3 3虚拟性虚拟性：从逻辑上扩充内存：从逻辑上扩充内存离散分配离散分配：支持多次性和对换性，若连续：支持多次性和对换性，若连续则不可能提供虚存，无法支持大作业小

45、则不可能提供虚存，无法支持大作业小内存运行内存运行76请求分页概念请求分页概念 在进程开始运行之前，不是装入全部页面，而是装入几个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。774.7.1 4.7.1 请求分页中的数据结构及硬件支持请求分页中的数据结构及硬件支持1 1、页表机制、页表机制页表项：页表项：2 2、缺页中断机构、缺页中断机构：可在指令执行期间产生（如图：可在指令执行期间产生（如图4-244-24）转入缺页中断处理程序。转入缺页中断处理程序。3 3、地址变换机构、地址变换机构比较简单分页机制，增

46、加了中断处理，比较简单分页机制，增加了中断处理，图图4.254.254.7 4.7 请求分页存储管理方式请求分页存储管理方式页号页号物理块号物理块号状态位状态位P P 访问字段访问字段A A修改位修改位M M 外存地址外存地址78 图图4 42424涉及涉及6 6次缺页中断的指令次缺页中断的指令79图图 4-25 请求分页中的地址变换过程请求分页中的地址变换过程 MMU80例6 现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms；内存存取时间为1s，访问页表的时间可忽略不计。假定70%被替换

47、的页被修改过，为保证有效存取时间不超过2s，可接受的最大缺页率是多少？注：（缺页率=缺页次数/总的页面访问次数）81解：解： 如果用p表示缺页率，则有效存取时间不超过2s可表示为：(1-p)1s+p(0.720ms+0.38ms+1s) 2s因此可计算出：p 1/164000.00006824.7.2 4.7.2 内存分配策略和分配算法内存分配策略和分配算法1 1、最小物理块数：、最小物理块数：与计算机的硬件结构有关与计算机的硬件结构有关不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则至如：允许间接寻址：则至少要求少要求3 3个物理块。个物理块。MovMov A, B A, B 物

48、理块是否越大越好？83缺页次数缺页次数 Versus 物理页框数物理页框数临界点临界点844.7.2 4.7.2 内存分配策略和分配算法内存分配策略和分配算法2 2、页面分配和置换策略。、页面分配和置换策略。1 1）固定分配局部置换。）固定分配局部置换。 缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(.(少：置换少：置换率高率高 多：浪费多：浪费) )2 2）可变分配全局置换）可变分配全局置换3 3）可变分配局部置换）可变分配局部置换 根据进程的缺页率进行页面数调整，进程之根据进程的缺页率进行页面数调整，进程之间相互不会影响。间相互不会影响。853 3、分配算法、分配算法 1 1

49、）平均分配算法）平均分配算法2 2）按进程大小比例分配算法：）按进程大小比例分配算法：3 3）考虑优先权分配算法）考虑优先权分配算法 mssbiiniiss1864.7.3 4.7.3 页面调入策略页面调入策略 1.1.调入时机：调入时机： 预调：（根据空间局部性）预调：（根据空间局部性） 目前：成功率目前：成功率5050；适合于首次调入时；适合于首次调入时 请求调页：每次调入一页，较费系统开销请求调页：每次调入一页，较费系统开销 各有优劣各有优劣2 2从何处调页：从何处调页： 对换区：修改过的页被换出时入对换区，对换区：修改过的页被换出时入对换区， 快快 文件区：稍慢文件区：稍慢 UnixU

50、nix方式方式 对共享页，应判断其是否在内存区。对共享页，应判断其是否在内存区。3.3.页面调入过程页面调入过程87目的：减少对换量，提高系统性能目的：减少对换量，提高系统性能 4.8.1 4.8.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法1 1、最佳（、最佳（OptimalOptimal）置换算法（理论上的）置换算法（理论上的）4.8 4.8 页置换算法页置换算法 图图 4-26 利用最佳页面置换算法时的置换图利用最佳页面置换算法时的置换图 884.8 4.8 页面置换算法页面置换算法 2 2、先进先出（、先进先出（FIFOFIFO）页面置换算法）页面置换算法 图图 4-27

51、利用利用FIFO置换算法时的置换图置换算法时的置换图 是否页框数增加就一定会减少缺页数呢？是否页框数增加就一定会减少缺页数呢？892 2、先进先出（、先进先出（FIFOFIFO）页面置换算法（续）页面置换算法（续） Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomaly more frames less page faults1231234125349

52、 page faults10 page faults1231235124544390FIFO Illustrating Beladys Anomaly914.8.2 4.8.2 最近最久未用最近最久未用LRULRU置换置换1 1、算法描述、算法描述 将将“最近的过去最近的过去”，作为，作为“最近的将来最近的将来”。图图 4-28 LRU页面置换算法页面置换算法 922. LRU2. LRU置换算法的硬件支持置换算法的硬件支持 1) 1) 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 93图图

53、4-29 4-29 某进程具有某进程具有8 8个页面时的个页面时的LRULRU访问情况访问情况 942) 2) 栈栈 图图 4-30 用栈保存当前使用页面时栈的变化情况用栈保存当前使用页面时栈的变化情况 954.8.3 Clock4.8.3 Clock置换算法置换算法（一种LRU近似算法：硬件消耗少）1 1、简单的、简单的ClockClock算法：算法： 设一访问位：图设一访问位：图4-304-30；循环扫描，每次扫描时将访；循环扫描，每次扫描时将访问位复位。问位复位。图图 4-31 简单简单Clock置换算法的流程和示例置换算法的流程和示例 96页面页面12使用位使用位=1页面页面2使用位使用位=1页面页面36使用位使用位=0页面页面6使用位使用位=1页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0页面页面12使用位使用位=0页面页面2使用位使用位=1页面页面9使用位使用位=1页面页面6使用位使用位=0页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使