第4章存储器管理

课程主要内容操作系统引论（1章）进程管理（2-3章）

进程控制、进程同步、进程通信、进程调度存储管理（4章）存储分配与回收地址变换内存扩充存储保护与共享设备管理（5章）文件管理（6章）OS中的存储管理是指对内存(并涉及外存)的管理，是OS的重要功能之一。第4章存储器管理存储器的层次结构第4章存储器管理任务为多道程序的运行提供良好的环境，提高存储器的利用率并从逻辑上扩充存储器。功能存储分配与回收地址变换内存扩充存储保护与共享第4章存储器管理程序的装入和链接连续分配存储管理基本分页存储管理基本分段存储管理虚拟存储器的基本概念请求分页存储管理页面置换算法请求分段存储管理补充：请求段页式存储管理4.1程序的链接和装入从源程序到程序执行编译：由编译程序将用户源程序编译成若干个目标模块。如VC++中的Ctrl+F7(Compile)链接：由链接程序将目标模块和相应的库函数链接成装入模块。如VC++中的F7(Build)装入：由装入程序将装入模块装入内存。如VC++中的Ctrl+F5(BuildExecute)4.1程序的链接和装入库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子24.1程序的链接和装入地址空间程序名字空间：汇编或高级语言程序中通常用符号名(符号地址)访问数据和子程序。这些符号名集合所限定的空间称作程序名字空间。相对/逻辑/虚地址空间：(汇编或编译程序将符号地址转换为相对地址)目标程序中的相对地址集合。绝对/物理/实地址空间：内存中实际存储单元的地址集合。4.1程序的链接和装入物理地址

内存000000000100002...0100001FFF主子1子2主子1子2相对地址

装入模块000...FFF主子1子2相对地址单个目标模块0005FF0003FF0003FF4.1程序的链接和装入地址重定位将程序中的逻辑/相对地址转换成物理/绝对地址的过程(地址变换/映射过程)。重定位的类型静态重定位：程序执行前，一次性，链接装入程序。动态重定位：处理机每次访问主存时，由动态地址变换机构（硬件）自动执行。4.1程序的链接和装入静态重定位示意图4.1程序的链接和装入动态重定位示意图4.2连续分配存储管理基本思想：为一个用户程序分配一片连续的内存空间。单一连续分区固定分区动态分区动态可重定位分区一、单一连续分区(单道作业固定分区)将内存分为系统区(常为内存低端，分配给OS用)和用户区(内存高端，分配给用户用)。优点：简单易实现(算法简单、硬件开销小)缺点：主存利用率低有内碎片，造成很大浪费不支持多道程序设计，资源利用率低不能实验存储扩充改进：多个分区固定分区可变分区基本原理预先(系统初始化时)将主存储器空间分割成大小相等或不等的若干块，每块称为一个分区。分区个数和每个分区的大小固定不变，每个分区装一个且只能装一个作业直到该作业完成后才释放该分区(一个作业占用连续的一片存储空间)。二、固定分区(多道作业固定分区)固定分区(大小相同)固定分区(大小不同)二、固定分区(多道作业固定分区)数据结构--分区说明表(MBT)（1）内存分配图二、固定分区(多道作业固定分区)区号大小起址状态18k20k已分配232k28k已分配364k60k已分配4132k124k未分配(2)分区说明表

通常将分区按

大小进行排序内碎片内碎片内碎片内存分配：内存回收：程序执行完毕

后释放占用的分区，管理

程序修改说明表。地址变换：静态重定位或动态重定位(需要一对界地址寄存器)二、固定分区(多道作业固定分区)二、固定分区(多道作业固定分区)优点：简单易实现(算法简单、硬件开销小)缺点：主存利用率低有内碎片，造成浪费虽然支持多道程序设计，但限制道数不能实现存储共享与扩充基本原理：内存不预先划分好(相当于开始时用户区是一个连续分区)，当作业装入时，按照作业的大小动态地建立分区。三、动态(可变)分区三、动态分区数据结构空闲分区表：记录空闲分区的情况(分区号、分区起始地址、分区大小及状态)。缺点：表长不易确定，管理困难且查找效率低。三、动态分区数据结构空闲分区链：用链头指针将空闲分区链接起来。每个空闲分区的起始部分存放本块大小和指向下一空闲分区的指针。头指针动态分区内存分配流程图三、动态分区内存分配三、动态分区根据空闲分区的四种组织方式，可有四种分配算法：首次适应算法(按起址升序排序，从表首找起)循环首次适应算法(按起址升序排序，从上次找到的空闲分区的下一个空闲分区开始找起)最佳适应算法(按容量升序排序，从表首找起)最坏适应算法(按容量降序排序，从表首找起)四种算法各有优缺点，没有一种是最好的。三、动态分区首次适应算法（最先适应算法）

空闲分区按起始地址递增的次序排列。

在进行内存分配时，从空闲分区表(链)首开始顺序查找，直到找到第一个满足作业要求的空闲分区为止。(找不到则分配失败，返回)

然后再按作业大小从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表(链)中(要修改相关数据)。区号大小起址132k20k28k52k3120k60k4331k180k空闲分区表例：空闲分区表如右，现有三个作业分配申请内存空间100K、30K及7K。给出按首次适应算法分配后的空闲分区表。解：首次适应算法(最先适应算法)区号大小起址12k50k21k59k320k160k4331k180k优点：分配和释放时间性能较好，较大的空闲分区得以保留缺点：随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大循环首次适应算法(下次适应算法)由首次适应算法演变而来。在为作业分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找（到最后分区时再回到开头），直到找到第一个能满足其大小要求的空闲分区为止。三、动态分区区号大小起址132k20k28k52k3120k60k4331k180k空闲分区表例：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按循环首次适应算法分配后的空闲分区表。解：循环首次适应算法(下次适应算法)区号大小起址132k20k28k52k320k160k4294k217k优点：内存利用更加均衡，不会使低端形成很多小分区缺点：但这会导致缺乏大的空闲分区。三、动态分区最佳适应算法

“最佳”是指每次为作业分配内存时，总是把既能满足要求的又是最小的空闲分区分配给作业，避免“大材小用”。

空闲分区按容量递增的次序排列。在进行内存分配时，从空闲分区表(链)首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。

分配后，所有空闲分区要重新进行排序。例：系统中的空闲分区表如右，现有三个作业分配申请内存空间100K、30K及7K。给出按最佳适应算法分配后的空闲分区表。解：区号大小起址18k52k232k20k3120k60k4331k180k空闲分区表最佳适应算法区号大小起址11k59k22k50k320k160k4331k180k优点：用最小空间满足要求。从个别来看，外部碎片较小但从整体来看，会形成较多外部碎片。最坏适应算法空闲分区按容量递减的次序排列。在进行内存分配时，从空闲分区表(链)首开始顺序查找，直到找到第一个比之大的空闲分区为止。

分配后，所有空闲分区要重新进行排序。三、动态分区三、动态分区区号大小起址1331k180k2120k60k332k20k48k52k空闲分区表最坏适应算法例：空闲分区表如右，现有三个作业分配申请内存空间100K、30K及7K。给出按最坏适应算法分配后的空闲分区表。解：区号大小起址1194k317k2120k60k332k20k48k52k优点：分割后空闲块仍为较大空块。基本不留下小空闲分区缺点：但较大的空闲分区不被保留。三、动态分区练习：软件设计师试题假设某计算机系统的内存大小为256K，在某一时刻内存的使用情况如图A所示。此时，若进程顺序请求20K、10K和5K的存储空间，系统采用____算法为进程依次分配内存，则分配后的内存情况如图B所示。三、动态分区起始地址0K20K

50K90K100K105K135K160K175K195K220K状态已用未用已用已用未用已用未用已用未用未用已用容量20K30K40K10K5K30K25K15K20K25K36K图A起始地址0K20K40K50K90K100K105K135K145K160K175K195K200K220K状态已用已用未用已用已用未用已用已用未用已用未用已用未用已用容量20K20K10K40K10K5K30K10K15K15K20K5K20K36K图BA．最佳适应B．最差适应C.首次适应D．循环首次适应分别画出四种算法分配前后的空闲分区表。三、动态分区内存回收(四种情况)地址变换：动态重定位(需要一对界限R)。存储保护：基址/限长保护法；保护键法。优点分区的大小和数目可变没有内碎片，提高了主存利用率支持多道程序设计且不限制道数缺点：存在外碎片；不能实现存储共享与扩充。三、动态分区固定分区和可变分区的碎片问题内碎片示意图外碎片示意图内碎片内碎片内碎片外碎片问题的解决方法之一紧凑（拼接）技术将内存中的所有作业移到内存一端，同时修改每个作业的起始地址，使本来分散的多个小空闲分区连成一个大的空闲区。外碎片问题的解决方法之一紧凑（拼接）技术在动态分区存储管理中增加拼接功能，在找不到足够大的空闲分区来满足作业要求、而系统中空闲分区总容量可以满足作业要求时进行拼接。四、动态可重定位分区动态可重定位分区分配算法流程图四、动态可重定位分区四、动态可重定位分区优点可以充分利用内存中的碎片，提高内存利用率。缺点动态重定位需要硬件支持。紧凑处理增加系统开销。不能实现内存共享和扩充。五、存储保护固定分区、可变分区、动态可重定位分区的存储保护措施：界限寄存器上下界寄存器方法：用这两个寄存器分别存放作业的起始地址和结束地址。基址、限长寄存器方法：用这两个寄存器分别存放作业的起始地址和作业的地址空间长度。五、存储保护存储保护键给每个存储块（大小相同，一个分区是存储块的整数倍）分配一个单独的保护键，它相当于一把锁。系统中的每个进程也赋予一个保护键，它相当于一把钥匙。当进程运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行。连续分配存储管理方式小结单一连续分区：不支持多道程序设计，资源利用率低固定分区：支持多道但存在内碎片动态分区没有内碎片但存在外碎片分配与回收慢(分配时查找时间长，释放时要合并)动态可重定位分区：解决了外碎片问题，但存储紧缩费时，代价较高四种技术都是连续分配方式，不能实现存储共享与扩充。外碎片问题的解决方法之二离散分配：允许将程序离散放到多个不相邻接的分区中，可以避免拼接。基于这一思想产生了以下离散分配方式：基本分页存储管理基本分段存储管理基本段页式存储管理1.内存空间分成若干个大小相等的块(页框)，各块从0开始编号。4.3基本分页存储管理一、基本思想物理内存01234567…01103.以页面为单位，将进程中若干页装入到多个可能不相邻的页框中。2.逻辑空间划分成若干个大小与块相等的页(页面)，各页也从0开始编号。用户进程k4.3基本分页存储管理二、数据结构系统为每个进程设一张页表，描述该进程占用的物理块号等信息，放在内存。4.3基本分页存储管理二、数据结构页表：为便于在进程运行时准确地找到各个物理块，系统用页表(页面映像表)记录进程逻辑页与内存物理块之间的对应关系及存取控制位。系统设页表寄存器用于存储正在运行进程的页表基址及长度。访问1B数据/指令需访问内存二次(页表一次，数据/指令一次)，故内存访问速度降低。4.3基本分页存储管理三、地址结构采用页式管理时，用户程序中的逻辑地址仍然是连续的、一维的。页号p页内地址dn-1k+1k0(n位)逻辑地址结构(p,d)

：假设我们的一页只能容纳1000行，请问我们写的文章的第5678行(从0开始)会分到第几页(从0开始)的第几行(从0开始)？自然截断4.3基本分页存储管理三、地址结构内存地址是连续的、一维的。块号b块内地址dm-1k+1k0(m位)物理地址结构(b,d)：假设我们写的文章的第5678行(从0开始)被抄写在第8号(从0开始)纸上，请问第5678行对应的物理行号是多少？自然拼接4.3基本分页存储管理三、地址结构例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，(1)逻辑地址至少应为多少位？(2)内存空间有多大？(1)2048=211，所以页内地址为11位。

16=24，页号为4位。故逻辑地址至少为15位。(2)块与页大小相等，所以块内地址也为11位。

8=23，块号为3位。故内存空间应为214=16KB。4.3基本分页存储管理三、地址结构若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号p和页内地址d的计算公式为：4.3基本分页存储管理三、地址结构例1：页大小为1024B，逻辑地址3456对应的数对(p,d)为多少？（3，384）思考页内地址占几位？10位(210=1024)若逻辑地址最大为123456，则页号需几位？int(123456/1024)=120；27=128>1214.3基本分页存储管理三、地址结构例2：页大小为1024B，则逻辑地址(4101)d的页号和页内地址可按如下二种方法计算：方法一：p=int(4101/1024)=4

d=4101-4*1024=5所以4101对应的数对是：(4,5)方法二：

(4101)d=(1000000000101)b

因为1024=210，所以页内地址需要10位

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

逻辑地址2148对应的物理地址为1124。

逻辑地址5012产生越界中断。页号块号021321364.3基本分页存储管理四、地址变换(p,d→b,d)快表(联想存储器)：是一种特殊的高速缓冲存储器。存放当前访问的那些页表项。先在快表中寻找页对应的物理块；若未找到(未命中)，再到页表中找，并将该页表项复制到快表。若快表已满，则按某种算法淘汰某些页表项。4.3基本分页存储管理四、地址变换(p,d→b,d)≤具有快表的地址变换机构4.3基本分页存储管理五、页的共享4.3基本分页存储管理五、页的共享与保护页的共享：一般不能实现共享，因为页的划分没有逻辑意义页的保护

地址越界检查在页表中设置存取控制位进行越权检查(定义操作权限：只读、读写、执行等)4.3基本分页存储管理优点离散存放、无外碎片；内存分配和释放速度快。缺点(页表、动态地址转换机构、快表等)增加系统开销；内存访问速度降低；每个进程平均拥有半页内碎片；页面共享困难；程序需全部装入内存，不能进行存储扩充。4.4基本分段存储管理程序按逻辑关系划分为段，从0编号，有名字和段长。逻辑地址由段号和段内地址确定。引入原因：满足用户要求便于编程和调试便于共享便于保护动态链接动态增长：某些段(数据段)会不断增长，前面的存储管理方法难以实现。4.4基本分段存储管理一、基本原理逻辑地址空间：分段划分为若干大小不等的段（由用户根据逻辑信息的相对完整来划分），段号从0开始，每段内的逻辑地址空间都从0开始编址(段内地址)。物理地址空间：可变分区在为作业分配内存时，以段为单位，分配一段连续的物理地址空间；段间不必连续。4.4基本分段存储管理基本原理示意图二、数据结构：段表每个进程设置一个段表，描述该进程占用的物理分区及逻辑排列顺序，放在内存。段表的基址及长度(段数)由段表寄存器给出4.4基本分段存储管理段号段长基址030k40k120k80k215k120k310k150k访问1B数据/指令需访问内存二次(段表一次，内存一次)，所以也出现内存访问速度降低的问题。4.4基本分段存储管理三、逻辑地址结构子程序段X数据段A┇call[X]∣<E>(调用X段的入口E)┇call[Y]∣<E>(调用Y段的入口E)┇load1,[A]∣<E>

(调用数组段A[E])┇主程序段E：┅┅┅E：┅┅┅子程序段YE：┅┅┅模块化程序设计的分段结构三、逻辑地址结构进程的地址空间分成多个段，因而其逻辑地址是二维的，由段号(段名)和段内地址（段内偏移量）组成。4.4基本分段存储管理内存四、存储分配以段为单位，每段分配一块连续的分区，一次分配作业所需的所有分区，一个进程的各段所分到的分区不必相邻。4.4基本分段存储管理第0段第1段第2段第3段用户作业段表基址段长150K35K500K9K300K20K100K42K3210段号第0段第1段第2段第3段≤≤4.4基本分段存储管理五、地址变换注意：两种越界情况！①②③④44.4基本分段存储管理五、地址转换逻辑地址(S,W)-->物理地址当进程要访问某个逻辑地址中的数据时，系统将段号S与段表寄存器中的段表长度TL进行比较。如STL，则访问越界，发生越界中断；否则，根据S读出该段的基址；若段内地址W段长，则访问越界，发生越界中断；否则，将段的基址与段内地址W相加，得到逻辑地址对应的物理地址；根据此物理地址访问内存。4.4基本分段存储管理五、地址转换例：现有一作业，在段式存储管理系统中，已为主存分配建立了如表所示的段表，试回答：该作业访问(1，120)、(2，200)、(4，600)时的绝对地址。（第一个元素为段号，第二个为段内地址）段号段长基址068017601160100022001560389028004.4

基本分段存储管理六、存储保护段表寄存器越界检查：段表长度与段号S比较；段长与段内位移量W比较存取控制位越权检查分段系统中共享editor的示意图4.4

基本分段存储管理七、存储共享4.4

基本分段存储管理优点没有内碎片；外碎片有改善且可通过紧凑技本来消除；便于编程、动态链接、动态申请内存、动态增长、存储共享和保护。缺点仍有外碎片；进程需全部装入内存，不能进行存储扩充。基本分页和基本分段的比较页式存储管理段式存储管理目的解决碎片问题更好满足用户需要信息单位页（物理单位）段（逻辑单位）大小固定(由系统定)用户不可见不定(由用户程序定)用户可见内存分配单位页段逻辑地址一维二维优点解决了碎片问题提高内存利用率便于共享、保护段可动态增长便于动态链接二者优点的结合----段页式存储管理(本章最后补充)基本存储管理方式单一连续分区固定分区动态分区动态可重定位分区基本分页基本分段非请求段页式4.5虚拟存储器的基本概念一、虚拟存储器的引入局部性原理：程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。时间局部性(程序的循环结构)：一条指令被执行/一个存储单元被访问，则在不久的将来它可能再次被执行/访问空间局部性(程序的顺序结构)：一条指令被执行/一个存储单元被访问，则在不久的将来，其附近的指令/存储单元也可能被执行/访问4.5虚拟存储器的基本概念一、虚拟存储器的引入虚拟存储管理的基本思想在程序装入时，只需将当前需要执行的部分页/段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据不在内存(缺页/段)，则由处理器通知OS将相应的页/段调入内存，然后继续执行程序。另一方面，OS将内存中暂时不用的页/段调出内存，腾出空间存放将要装入的程序及将要调入的页/段。4.5虚拟存储器的基本概念一、虚拟存储器的引入虚拟存储器：具有请求调入功能和页/段置换功能，能从逻辑上对内存容量进行扩充的存储器系统。逻辑容量=可寻址范围实际容量=内存+外存对换区若CPU的有效地址长度为32位，则程序可以寻址范围是0～232-1，即虚存逻辑容量为4GB。XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K

8K-12K

4K-8K

0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K

8K-12K

4K-8K

0K-4K虚地址空间实地址空间}虚页页框虚拟页式存储器示意图4.5虚拟存储器的基本概念一、虚拟存储器的引入实现虚拟存储器的代价页表、段表等数据结构缺页中断机构动态地址变换机构缺页/段时的请求调页/段和页/段置换以CPU时间和辅存空间换取内存空间。4.5虚拟存储器的基本概念二、虚拟存储器的特征多次性：是虚拟存储器最重要的特征。指一个作业被分成多次调入内存运行。对换性：指允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率。虚拟性：指能够从逻辑上扩充内存容量，使用户看到的内存容量远大于实际内存容量。4.6请求分页存储管理在基本分页存储管理系统的基础上，增加请求调页和页面置换功能所形成的页式虚拟存储器系统。基本思想地址空间的划分与基本分页相同。作业装入时，不装入全部页面，只装入作业的一部分(运行所需)页即可运行，之后根据进程运行的需要，动态装入其它页面。当内存已满而又需要装入新页时，则根据某种算法淘汰某个页面，以装入新页。4.6请求分页存储管理一、硬件支持

1.页表

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

2.缺页中断机构

当要访问的页不在内存(即缺页)时，便产生一个缺页中断，请求OS将所缺页调入内存空闲块，若无空闲块，则需置换某一页，同时修改页表。4.6请求分页存储管理开始页号>页表长度？CPU检索快表NNY页表项在快表中？访问页表页在内存？修改访问位和修改位修改快表形成物理地址地址变换结束越界中断程序请求访问一页YN缺页中断处理Y保留CPU现场内存满吗？将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否？将该页写回外存修改页表NYN一、硬件支持3.地址变换机构≤4.6请求分页存储管理一、硬件支持

3.地址变换机构地址变换示意图≤第4章请求分页地址转换.swf4.6请求分页存储管理例：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。解：页内位移和块内位移为10bits（110=1024）虚拟地址OA5C对应的二进制为：

000101001011100即虚拟地址OA5C的页号为2，对应的物理块号为4，所以对应的物理地址为：

01001001011100即125C4.6请求分页存储管理二、页面调入过程保留CPU现场内存满吗？将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否？将该页写回外存修改页表NYN内存空间有限，不能装入进程申请的所有页面。在装入新的页面时，如果内存满，需要淘汰已装入页面。4.7页面置换算法也称页面淘汰算法，是决定选择淘汰哪一页的规则。算法衡量标准：缺页中断率f=F/A;其中，A：作业执行中访问页面的总次数

F：缺页中断次数算法目标：降低缺页率4.7页面置换算法常用算法最佳置换算法OPT：淘汰永远不再需要的页面或最远的将来才需要访问的页面。先进先出置换算法FIFO：淘汰最先进入内存的页面。最近最久未用置换算法LRU：淘汰最近一次访问发生在最远的过去的页面。4.7页面置换算法一、最佳置换算法OPT思想：Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或者是在最长(未来)时间内不再被访问的页面。简单地说，淘汰在最远的将来才需要访问的页面。4.7页面置换算法一、最佳置换算法OPT例：假定系统为某进程分配了3个页框。该进程的页面引用序列为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。开始时3个物理块均为空。6次页面置换，9次缺页中断，缺页率为9/20页面置换图为：4.7页面置换算法一、最佳置换算法OPT优点：理论上，性能最佳。缺点：实际上，无法实现，因为难以预知一个作业将来会用到哪些页面。通常只用在研究其它算法时做参考评价。4.7页面置换算法二、先进先出置换算法FIFO思想：淘汰在内存中驻留时间最长的页面。或者说是淘汰最早进入内存的页面。依据：最早调入内存的页面，其不再被访问的可能性会大一些。实现：进入主存的各页面按进入的时间次序用链指针链成队列，新进入的页面放在链尾，先进入的页面放在链头，总是从链头淘汰页面。4.7页面置换算法二、先进先出置换算法FIFO例：假定系统为某进程分配了3个页框。该进程的页面引用序列为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。开始时3个物理块均为空。页面置换图为：12次页面置换，15次缺页中断，缺页率为15/204.7页面置换算法二、先进先出置换算法FIFO优点：实现简单；对具有线性顺序访问的程序比较合适。缺点效率不高（因为经常被访问的页面，往往在内存中停留最久，结果这些常用的页面却因变老而被淘汰）存在Belady现象(即在某些情况下会出现分配给的进程物理块数增多，缺页次数有时增加、有时减少的现象)。4.7页面置换算法二、先进先出置换算法FIFOBelady现象示例。设程序访问页的顺序为1,2,3,4,1,2,5,1,2,3,4,5如果在内存中分配3个物理块，页面置换图如下所示(页号按FIFO排序)缺页率：9/124.7页面置换算法二、先进先出置换算法FIFOBelady现象示例。如果在内存中分配4个物理块，页面置换图如下所示(页号按FIFO排序)缺页率：10/124.7页面置换算法三、最近最久未用算法LRU思想：淘汰内存中到目前为止最长时间未被访问过的页面。依据：如果某页被访问了，它可能马上还要被访问；或者说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。优点：性能接近于OPT算法缺点：不易实现，系统开销大4.7页面置换算法三、最近最久未用算法LRU例：假定系统为某进程分配了3个页框。该进程的页面引用序列为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。开始时3个物理块均为空。页面置换图为：9次页面置换，12次缺页中断，缺页率12/204.7页面置换算法练习：某进程在内存中分配三个页框，初始均为空，页面走向为4,2,1,4,3,5,4,3,2,1,5。请分别用最佳置换、先进先出和最近最久未用算法计算该引用串共发生了多少次缺页，并分析先进先出算法是否会产生Belady现象？4.7页面置换算法444444442112222555555113333333OPT算法：421435432157次缺页，4次置换4.7页面置换算法444333222222555111114445FIFO算法：421435432159次缺页，6次置换4.7页面置换算法444444112233335115222LRU算法：421435432158次缺页，5次置换4.7页面置换算法假设为进程分配4个页框，FIFO算法：444221421435432158次缺页，5次置换4.8请求分段存储管理在基本分段存储管理系统的基础上，增加请求调段和段置换功能所形成的段式虚拟存储器系统。基本思想地址空间的划分与基本分段相同。在作业装入时，不装入全部段，只装入零或一段，之后根据进程运行的需要，动态装入其它段。当内存已满而又需要装入新段时，则根据某种算法淘汰某个段，以装入新段。4.8请求分段存储管理硬件支持

1.段表机制存取方式：存取属性（执行、只读、允许读/写）访问字段：记录该段被访问的频繁程度修改位：该段在进入内存后，是否被修改过。存在位：该段是否在内存中。增补位：在运行过程中，该段是否做过动态增长。外存地址：该段在外存中的起始地址。段长段的基址存取方式访问字段修改位存在位增补位外存地址4.8请求分段存储管理硬件支持

2.缺段中断机构当要访问的段不在内存中（即缺段）时，将产生缺段中断信号，请求OS将所缺段调入内存空闲块，若无空闲块，则需置换某一段，同时修改段表。4.8请求分段存储管理开始返回w≤段长？修改访问字段形成内存地址分段越界中断处理NYY段S在内存？符合存取方式？分段保护中断处理缺段中断处理YNN硬件支持

3.地址变换机构请求分段地址转换.swf

Cl

Cb+段号S段内地址w≤≤b+w段表快表物理地址段表寄存器段表长度寄存器逻辑地址lb...Slb地址越界地址越界地址越界≤具有快表的请求分段地址变换机构示意图第4章请求分段地址转换.swf补充：(请求)段页式存储管理一、基本原理：段式与页式结合将主存划分为若干页框将进程的地址空间先分段，每段再分页主存以页框为单位分配逻辑地址结构：

(段号s,段内页号p,页内地址d)段号段内地址w段内页号p页内地址d补充：(请求)段页式存储管理一、基本原理一个程序首先被划分成若干程序段，每段一个分段标识符。然后，将每一分段分成若干固定大小的页面。主程序段数据段子程序段补充：(请求)段页式存储管理二、数据结构段表：每个进程一个段表(表目包括段号、页表基址、页表长度、存取控制位)页表：每段建立一个(段内)页表(表目包括页号、物理块号、状态位、外存地址、访问位、修改位、存取控制位等)段表寄存器：标识当前正在运行进程的段表基址和长度。补充：(请求)段页式存储管理段表、页表之间的关系……段表始址段表长度段表13021110页表始址页表长度状态段号段表寄存器页表03121110存储块号状态页号页表1110存储块号状态页号补充：(请求)段页式存储管理二、地址变换从段表地址寄存器中读取段表基址，找到段表；由段号＋段表基址得到段描述子地址；从段描述子读取页表基址，找到页表；由页号＋页表基址得到页描述子地址；从页描述子读取页框(物理块)号；页框号