第四~五章 存储器管理.ppt

1、第四章 存储器管理,4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 分页管理 4.5 分段存储管理 4.6 虚拟存储器 4.7 请求分页技术 4.8 页面置换算法 4.9 请求分段存储管理,本章学习内容,4.1 存储器的层次结构,在现代计算机系统中，存储器是信息处理的来源与归宿，占据重要位置。 理想的存储器：速度快，容量大，价格低 但是，在现有技术条件下，任何一种存储装置，都无法同时满足这三个条件。 因此，现代计算机系统的存储部件实际上采用了层次结构，组成了一个速度由快到慢，容量由小到大，价格由高到低的存储装置层次。,4.2 程序的装入和链接,关于内存和存储管

2、理 程序的装入 程序的链接,关于内存,内存是现代计算机系统的中心，是指CPU能直接存取指令和数据的存储器，CPU和I/O设备都要和内存打交道。 内存由很大的一组字或字节所组成，每个字或字节都有它们自己的编号，称为内存地址。 对内存的访问是通过一系列对指定地址单元进行读写来实现的。,存储管理的基本功能,1 存储空间的分配和回收 内存的分配与回收是内存管理的主要功能之一。用户程序通常以文件的形式保存在计算机外存上，为了执行用户程序，用户程序必须全部或部分装入内存，因此在内外存之间必须不断交换数据。能否把外存中的数据和程序调入内存，取决于能否在内存中为它们安排合适的位置。因此，存储管理模块要为每一个

3、并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。,存储管理的基本功能,2 地址转换（映射） 内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。 源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。,地址映射,第一步,第二步,第

4、三步,程序的装入,绝对装入方式 可重定位方式 动态运行时装入方式,绝对装入方式,逻辑地址与实际内存地址相同 由绝对装入程序装入 只能装入内存中事先指定的位置 只适用于单道程序环境,可重定位方式,我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。 地址映射的方式： 程序被装入内存时由操作系统的可重定位装入程序完成程序的逻辑地址到内存地址的转换。 地址变换在装入时一次完成，也称静态重定位。 假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 不允许程序运行时在内存中移动位置。,12500

5、,动态运行时装入方式,动态运行时装入方式，也称为动态地址重定位，是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。 动态重定位依靠硬件地址变换机构完成。地址重定位机构需要一个(或多个)基地址寄存器BR和一个(或多个)程序虚拟地址寄存器VR。指令或数据的内存地址MA与逻辑地址的关系为： MA=(BR)+ (VR) 这里，(BR)与(VR)分别表示寄存器BR与VR中的内容。 不在程序装入时立即将相对地址转换为绝对地址，而是把地址变换推迟到程序真正执行时，因此程序装入后，允许改变其在内存中的位置。,程序的链接,静态链接方式 装入时动态链接 运行时动态链接,静态链接方式,将多个

6、程序模块组成一个装入模块，必须处理的问题： 修改各个模块的相对地址 把外部调用符号转换为相对地址 静态链接方式： 事先进行链接，形成一个完整的装入模块(可执行文件)，可直接装入运行，以后不再拆开。,装入时动态链接,边装入边链接 装入时，若发生外部模块调用事件，将由装入程序找出相应外部模块，并装入内存和修改相对地址。 优点： 便于修改、更新 便于共享模块,运行时动态链接,不装入所有模块，加快装入，节省内存 执行过程中，如果发现一个被调用模块没有装入，再由OS找到该模块并装入内存，链接到调用者模块上。,4.3 连续分配方式,连续分配方式：为一个用户程序分配一个连续的存储空间。 单一连续分配 固定分

7、区分配 动态分区分配 动态重定位分区分配,单一连续分配,最简单，只适用于单用户、单任务系统 内存分为两部分： 系统区 内存的低址部分，仅供OS使用 用户区 系统区以外的全部内存空间，供用户程序使用,0,m,n,地址：0mn,固定分区分配,把内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业。 划分的原则由系统操作员或操作系统决定。 分区一旦划分结束，则系统运行期间，每个分区的长度和内存的总分区个数将保持不变。,固定分区分配,划分分区的两种方法： 分区大小相等 适用于控制多个相同对象的场合 缺乏灵活性，小程序浪费空间，大程序无法装入 分区大小不等 为了解决灵活性问题，将内存分为多个大

8、小不等的分区：小分区(较多)，中等分区(适量)，大分区(少量),固定分区分配,在固定分区管理方式下，每个用户作业占用一个连续的分区区域，作业的程序和数据一旦装入分区后就不能再移动，所以它通常采用静态地址重定位。 分区的管理和分配方法： 固定分区管理使用一个称为分区说明表的数据结构对用户作业进行存储分配。分区说明表中每一个表项对应一个分区，它记载着这个分区的序号、空间大小、起始地址和使用状况。 当用户作业要求装入系统时，操作系统通过分区说明表查找内存的空闲区域，然后根据作业的大小，按照一定的分配策略，选择一个空闲分区分配给该作业，并把分区说明表中该分区标明已占用。,固定分区分配,缺点： 分区数量

9、是固定的，每个分区只能装入一道作业，限制了系统能容纳的作业数。 分区大小是固定的，每个分区只能装入一道作业，剩余空间无法再利用，造成浪费。 优点：实现简单,固定分区分配,某系统的内存容量为256K，操作系统占用低地址的20K，其余空间划分成4个固定大小的分区。如下图：,固定分区分配,分区说明表,固定分区分配,例：在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如图所示，现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费多大？,（2）分区说明表,（2）分区说明表,(3) 主存浪费空间 = (8-1)+(32-9)+(12

10、0-33)+(331-121) = 7+23+87+210=327(k),解：根据分区说明表，将4个分区依次分配给4个作业，同时修改分区说明表，其内存分配和分区说明表如下所示：,1K,9K,33K,121K,动态分区分配,动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。 采用动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个空闲分区。随后，分配程序将该区依次划分给调度选中的作业或进程。,动态分区分配,动态分区分配,需配置相应

11、的数据结构，描述空闲分区和已分配分区的情况。 不同的系统采用不同的数据结构，常用形式包括： 空闲分区表 在系统中设置一张空闲区表，每个表目记录一个空闲区，主要参数包括分区号、长度和起始地址 空闲分区链 利用每个内存空闲区的头几个单元存放分区分配控制信息，在分区的头、尾设置指针，从而把所有的空闲区链接起来。,动态分区分配,动态分区分配,分区分配算法： 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法,首次适应算法(first fit, FF),要求按地址递增的次序组织空闲区表(链)。 申请和分配：从低地址找起，直至找到一个能可满足要求的空闲分区，根据作业大小划出一块给申请

12、者，剩余空间仍留在空闲链中，成为一个小的空闲分区。 优点：优先使用内存中低址部分的小空闲区， 从而保留了高址部分的大空闲区，有利于大作业。,首次适应算法,缺点： 低址部分不断被划分，形成许多难以利用的小空闲分区(碎片)，造成空间浪费 碎片聚集在低址区域，每次又从低址开始查找，增加时间开销,循环首次适应算法(next fit),是FF算法的演变和改进，每次分配不再从空闲分区链(表)的开始找起，而是从上次找到的空闲分区的下一个找起，找到一个能满足要求的空闲分区。 需增设一个起始查寻指针，指示下一次查找从那个空闲分区开始。 优点：使空闲分区分布均匀，减少查找开销 缺点：缺乏大空闲分区，不利于大作业,

13、最佳适应算法(best fit),“最佳”的含义：把能满足要求的最小空闲分区分配给作业，避免“大材小用”。 空闲分区链组织：按容量大小排列(从小到大) 优点：尽量使用小空闲区，保留大空闲区 真的最佳吗？ 孤立地看，对每个程序，分区大小是最合适的，浪费最小 宏观上看，每次分配切割下来的剩余部分最小，因此会形成许多难以利用的碎片,最坏适应算法(worst fit),总是挑选最大的空闲分区分割给作业使用 空闲分区链组织：按容量大小排列(从大到小) 优点： 防止产生碎片，空间浪费最少 有利于中、小作业 查找效率很高（只需查找第一块） 缺点：缺乏大的空闲分区,快速适应算法(quick fit),前四种统

14、称为顺序搜索法。 快速适应算法也称分类搜索法，特点： 将空闲分区按大小分类，每类具有相同容量，放入一个空闲分区链表 增设一张管理索引表，每个表项对应一个分类，并记录相应链表的表头指针 优点：查找效率高 缺点：算法复杂、开销大,练习题：某系统采用动态分区存储管理技术。某时刻在内存中有三个空闲区，它们的首地址和大小分别是：空闲区1（100KB，10KB）、空闲区2 （200KB，30KB）、空闲区3 （300KB，15KB）。现有如下作业序列：作业1要求15KB、作业2要求16KB、作业3要求10KB。要求： （1）画出该时刻内存分布图； （2）用首次适应算法和最佳适应算法画出此时的空闲分区链结构

15、； （3）哪种算法能将作业装入内存（给出简要的分配过程）。,动态分区的分配和回收,分配内存 回收内存,分配,回收内存,当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。 回收时的几种情况： （1）上邻空闲区：合并，改大小 （2）下邻空闲区：合并，改大小、首址。 （3）上、下邻空闲区：合并，改大小，取消下邻空闲区的表项。 （4）不邻接，则建立一新表项。,回收内存,图4-8 内存回收时的情况,F1, F2: 空闲区 作业

16、1，2：非空闲区,(1),(2),(3),(4),伙伴系统,固定分区方式限制了活动进程的数目，内存利用率低。 动态分区方式算法复杂，系统开销大。 伙伴系统方式是对上述两种方式的折衷方案。 伙伴系统规定： 无论已分配分区或空闲分区，大小为2的k次幂，k为整数，lkm 2l表示最小分区大小 2m表示最大分区大小，通常是整个可分配内存的大小,伙伴系统,空闲区组织 系统初启时，只有一块空闲区，大小为2m 一段时间后，可能形成若干空闲区，各个空闲区大小为2k ，0km 将空闲区按大小分类组织，每一类具有相同的大小，为每类设定一个双向分区链表,伙伴系统-分配,首先计算一个i值，使2i-1 2*2i+1 ,

17、一个用于分配，一个加入空闲链表(2i+1) 2i+1 - 2*2i ,一个用于分配，一个加入空闲链表(2i) 以此类推,伙伴系统,回收 回收时，与其伙伴分区合并 一次回收可能进行多次合并 性能 时间开销：查找、分割、合并空闲分区 时间性能：优于顺序搜索法，比分类搜索法差 空间性能：优于分类搜索法，比顺序搜索法略差,可重定位分区分配,1.动态重定位的引入 在连续内存分配中，必须把一个系统程序或用户程序装入一个连续的内存空间中。由于各个进程不断申请和释放内存，导致在内存中出现大量的分散的小空闲区。内存中这种容量太小、无法利用的小分区称做“碎片”或“零头”。 如图所示系统中有四个小空闲分区，不相邻，

18、但总容量为80KB，如果现有一作业要求分配40KB的内存空间，由于系统中所有空闲分区的容量均小于40KB，故此作业无法装入内存。,可重定位分区分配,os,用户程序,p4,p1,p2,0 k 20 k 56 k 65 k 125 k 135 k,内部碎片,内部碎片,内部碎片,内部碎片,外部碎片,内部碎片：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。 外部碎片：指系统中无法利用的小的空闲分区。如动态分区中存在的碎片。,将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换,即重定位），使本来分散的多个小空闲分区连成一个大的空闲区，如图所示。

19、这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑。 拼接时机： （1）分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。 （2）定时。,可重定位分区分配,可重定位分区分配,2. 动态重定位的实现 作业被装入内存后所有地址仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令真正执行时。 需要硬件地址变换机构的支持 重定位寄存器，保存作业在内存中的起始地址 “紧凑”之后，程序移动了位置，只需更改重定位寄存器的内容为新的起始地址,0,100,5000,2500,10000,10000,10100,+,12500,15000,作业J,处理机一侧

20、,存储器一侧,重定位寄存器,相对地址,图4-10 动态重定位示意图,动态重定位分区分配算法,4.4 对换,1. 对换(Swapping)的引入 问题：内存中被阻塞的进程占用大量空间，外存上却有许多作业因为内存不足而等待。 对换：把内存中暂时不能运行的进程或暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间。,4.4 对换,对换单位： 进程 “整体对换”,“进程对换”，常用于分时系统 “页”或“段” “页面对换”或“分段对换”，统称“部分对换”，用于支持虚拟存储系统,4.5 分页管理,连续分配方式的缺点： 会形成许多“碎片” “紧凑”产生较大开销 离散分配方式 允许将一个进程分散地装入多个

21、不相邻的分区，从而无需“紧凑”。 可按离散分配的基本单位，分为两种方式： 分页存储管理方式 分段存储管理方式,4.5 分页管理,4.4.1 页面与页表 把用户程序的地址空间划分成若干大小相等的区域，每个区域称作页面或页。每个页都有一个编号，叫做页号。页号一般从0开始编号，如0，1，2，等。 把内存空间划分成若干和页大小相同的物理块，这些物理块叫页框(frame)或(物理)块。同样，每个物理块也有一个编号，块号从0开始依次顺序排列。 以页为单位进行内存分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。 “页内碎片”：最后一页装不满而形成的碎片，不可利用。,页式分配示意图,装入,用

22、户程序x（5KB）,内存空间（8KB）,X的第0页,X的第1页,X的第2页,4.5 分页管理,页面大小 页太大，页内碎片大。 页太小：页表可能很长，换入/换出效率低 页面大小由硬件地址结构决定，机器确定，页面大小就确定了 一般来说，页面大小选择为2的若干次幂，根据计算机结构的不同，其大小从512B到16MB不等。,4.5 分页管理,示例 31 12 110,地址结构 地址包括两部分：页号、页内地址,4.5 分页管理,对于某台具体机器来说，其地址结构是一定的。如果给定的逻辑地址是A，页面的大小为L，则页号p和页内地址d可按下式求得： p=INTA/L，d=A MOD L 其中，INT是向下整除的

23、函数，MOD是取余函数。 例如，设系统的页面大小为1KB,A=2170,则p=INT(2170/1024)=2， d= 2170 MOD 1024=122。,4.5 分页管理,页表 在分页系统中，允许将进程的各页离散地装入内存的任何空闲块中，这样就出现进程页号连续，而块号不连续的情况。为了找到每个页面在内存中对应的物理块，系统为每个进程设立一张页面映射表，简称页表。 进程的所有页依次在页表中有一个页表项，其中记载了相应页面在内存中对应的物理块号。进程执行时，按照逻辑地址中的页号查找页表中对应的项，找到该页在内存中的物理块号。 页表的作用就是实现页号到物理块号的地址映射。,4.4 分页管理,页表

24、是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息，是OS进行分页管理的依据。,4.5 分页管理,页表的作用：页号到物理块号的地址映射,4.5 分页管理,4.4.2 地址变换机构 由于页内地址和物理地址是一一对应的，地址变换机构的任务实际上是将逻辑地址中的页号转换为内存中的物理块号。 基本的地址变换机构 具有快表的地址变换机构,4.5 分页管理,基本的地址变换机构 越界保护 页表寄存器 每个进程对应一个页表，页表驻留在内存中，页表始址和长度存放在PCB中，进程被调度时，这两个数据被装入页表寄存器,4.5 分页管理,具有快表的地址变换机构 对

25、于基本的地址变换机构(无快表)，每存取一个数据，需要访问两次内存 访问页表 =数据所在的块号，形成物理地址 访问数据所在的物理地址 = 数据 增设一个联想寄存器（快表） 具有并行查询能力的高速缓冲寄存器 存放当前访问的那些页表项 每次地址变换时，先在快表中查找页号 快表中找不到，再访问内存中的页表，并将页表项存入快表，若快表已满，应换出最老的页表项,使用快表可减少对内存的第一次访问（页表），因而能提高速度，但成本很高，容量通常只有16512个页表项，对中、小型作业，已有可能将页表全部放入。大作业虽然无法全部放入，但由于程序和数据访问的局部性，也可以取得较好的效果。据统计：命中率90%,4.5

26、分页管理,分页管理中的地址映射问题 【注意】将逻辑地址线性分割求出页号P和页内位移W： 1、逻辑地址以十进制数给出： 页号P=逻辑地址 / 页大小 页内位移W=逻辑地址 mod 页大小 2、逻辑地址以十六进制、八进制、二进制的形式给出： 将逻辑地址转换成二进制； 按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）； 将位移量直接复制到内存地址寄存器的低位部分； 以页号查页表，得到对应页装入内存的块号B，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,4.5 分页管理,练习题： 例1：设有8页的逻辑地址空间，每页有1024个字节，它们被映射到32块的物理存储区

27、，那么逻辑地址的有效位是多少，物理地址至少多少位？ 例2：在一分页系统中，逻辑地址的长度为16位，页面大小为4096字节，现有一逻辑地址2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址是多少？ 例3：在某分页系统，主存的容量为64K，页面的大小为1K，对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中，试将十进制的逻辑地址1023、2500、3500和4500转化成物理地址。,练习题 【例4】：有一页式系统，其页表存放在主存中 如果对主存的一次存取需要1.5s,试问实现一次页面访问的存取时间是多少? 如果系统加有快表,平均命中率为85%,

28、当页表项在快表中时,其查找时间忽略为0, 试问此时的存取时间是多少?,答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。 页表在主存的存取访问时间 =1.5*2=3(s) 增加快表后的存取访问时间 =0.85*1.5+(1-0.85)*2*1.5=1.725(s),4.5 分页管理,4.4.3 两级和多级页表 案例：CPU具有32位地址时 ,使用232逻辑地址空间的分页系统,规定页面4KB时,一个进程页表的表项可达1兆(220)个,若表项占用4个字节,则一个进程需要占用4MB连续内存空间存放页表。

29、多级页表概念：页表和页面一样也进行分页，内存仅存放当前使用的页表,暂时不用部分放在磁盘上,待用到时再行调进。 具体做法：把整个页表进行分页,分成一张张小页表(称为页表页) ,小页表的大小与页框相同，为进行索引查找,应该为这些小页表建一张页表（外层页表）,其表项指出小页表所在页框号及相关信息。,4.5 分页管理,两级页表结构,4.5 分页管理,在具有两级页表结构的系统中，地址转换的方法是：利用外层页号p1检索外层页表，从中找到指定页表分页的基址，再利用p2作为指定页表分页的索引，找到该页面在内存的块号，用该块号和页内地址d拼接起来形成访问的内存物理地址。,4.5 分页管理,对于正在执行的进程 必

30、须将其外层页表调入内存 对页表只需调入一页或几页 需要时再调入不在内存的页表 2. 多级页表 二级页表的扩展，对外层页表再分页,4.6 分段存储管理,4.5.1 分段存储管理方式的引入 分页主要是为了提高系统资源利用率，分段主要是为了满足用户(程序员) 的需求： 方便编程 信息共享 信息保护 动态增长 动态链接,4.6 分段存储管理,4.5.2 分段系统的基本原理 分段： 将程序按逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段段内也从0开始编址，段内地址是连续的。 逻辑地址结构：,内存划分： 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个

31、物理段由起始地址和长度确定。 内存分配： 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。,段表,利用段表实现地址映射,(MAIN)=0,(X)=1,(D)=2,(S)=3,2. 段表,3. 地址变换机构,如同分页系统, 访问一次数据,也需要访问两次内存,也可以通过增设联想寄存器来提高速度.,分页与分段的区别,4.6 分段存储管理,4.6.3 信息共享 分页系统和分段系统都可以支持信息共享. 设想一下这样的系统，有40个用户，每个用户都执行一个文本编辑器。如果文本编辑器有160KB代码段和40KB数据段，需要8000KB来支持40个

32、用户。 共享页面时只需要在物理内存中保存一个编辑器的拷贝。每个用户的页表映射到编辑器的同一物理拷贝，而数据页映射到不同的块。,进程1,进程2,页表,页表,主存,分页系统中共享editor,0 21 22 60 61 70 71 80,分段系统中共享editor,进程1,进程2,80 240 380,段表,主存,可重入代码,可重入代码(纯代码)是一种允许多个进程同时访问的代码. 在其执行过程不允许任何进程对它进行修改 通常由指令和常数组成,4.6 分段存储管理,例题：在一分段存储系统中，其段表如下：,试求下列逻辑地址对应的物理地址是什么？ （1）0,430；（2）1,10；（3）2,500； （

33、4）3,400；（5）4,112；（6）5,32,段页式存储管理,1.基本思想: （1）作业地址空间进行段式管理。 （2）每段内再分成若干大小固定的页，每段都从零开始为自己的各页依次编写连续的页号。 （3）对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的物理块。 （4）作业的逻辑地址包括3个部分：段号、页号和页内位移。 （5）为实现地址变换，段页式系统设立了段表和页表。,每个段有一个页表,其中登记该段的每页在内存的映像,登记每个段的页表在内存的地址,段页式存储管理,2.地址转换过程:,段超长,页表长度 页表始址,+,+,段页式系统中，访问一次数据,需访问三次内存(段表,页

34、表,数据本身),逻辑地址,段页式存储管理,第五章 虚拟存储器,5.1 虚拟存储器,前面所介绍的各种存储管理方式，有一个共同的特点，即它们都要求将一个作业全部装入内存后才能运行，于是，就可能出现以下情况： (1) 有的作业很大，其所要求内存空间超过了内存容量，从而导致作业不能全部被装入内存，以至于该作业无法运行。 (2) 有多个作业要求运行，但可用的内存空间不足以容纳所有的作业，只能将少数的作业装入内存让它们先运行，而将其他的作业留在外存等待。 解决方案： 增加物理内存容量 虚拟存储技术,5.1 虚拟存储器,4.6.1 虚拟存储器的引入 常规存储器管理方式的特征 （1）一次性：作业在运行前需一次

35、性地全部装入内存。将导致上述两问题，以及可能的空间浪费。 （2）驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。不再使用的模块依然占据内存空间。 局部性原理 指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。 局部性又表现为时间局部性(由于大量的循环操作，某指令或数据被访问后，则不久可能会被再次访问)和空间局部性（如顺序执行，指程序在一段时间内访问的地址，可能集中在一定范围之内）。,5.1 虚拟存储器,虚拟存储器的定义 基于局部性原理，程序在运行之前，没有必要全部装入内存，仅须将当前要运行的页（段）装入内存即可。

36、运行时，如访问的页（段）在内存中，则继续执行，如访问的页未在内存中（缺页或缺段），则利用OS的请求调页（段）功能，将该页（段）调入内存。如内存已满，则利用OS的页（段）置换功能，按某种置换算法将内存中的某页（段）调至外存，从而调入需访问的页(段)。 虚拟存储器 指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。 它使用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间 。,5.1 虚拟存储器,实现虚拟存储器的物质基础是二级存储器结构和动态地址转换机构。经过操作系统的改造，把计算机的内存与外存有机的结合起来使用，从而得到一个容量很大的

37、“内存”，这就是虚存。 虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来，当作两个不同的概念。它的容量主要受到两方面的限制： (1)指令中表示地址的字长。一个虚拟存储器的最大容量是由计算机的地址结构确定的。 (2)外存的容量。虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。,5.1 虚拟存储器,4.6.2 虚拟存储器的实现方法 需在基于离散分配的存储管理方式上实现 分页请求系统 基于分页系统，增加了请求调页和页面置换功能 硬件支持： 请求分页的页表机制、缺页中断机构、地址变换机构 请求分段系统 基于分段系统，增加了请求调段和分段置换功能 硬件支持： 请

38、求分段的段表机制、缺段中断机构、地址变换机构,5.1 虚拟存储器,4.6.3 虚拟存储器的特征 多次性 每个进程不是一次全部装入内存，而是分成若干个部分，分多次装入。当进程需要执行时，才将当前运行所需要的程序和数据装入内存。 对换性 在作业运行过程中允许换入、换出，在内存中那些暂时不使用的程序和数据可以换到外存的交换区存放，以腾出尽量多的内存空间供可运行进程使用。 虚拟性 虚拟内存不是扩大实际的物理内存，而是扩充逻辑内存的容量，使用户看到的内存容量大于实际内存容量。,5.2 请求分页技术,请求分页存储管理的基本思想 请求式分页也称虚拟页式存储管理，它的基本思想是：在进程开始运行之前，不是装入全

39、部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。 为了实现页式虚存，系统需要解决下面三个问题： （1）系统如何获知进程当前所需页面不在主存。 （2）当发现缺页时，如何把所缺页面调入主存。 （3）当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。,扩充页表,缺页中断,页面置换算法,5.2 请求分页技术,4.7.1 请求分页中的硬件支持 1.页表的扩充,（1）状态位P：指示该页是否已调入内存。 （2）访问字段A：记录本页在一段时间内被访问

40、的次数或最近未被访问的时间。 （3）修改位M：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。 （4）外存地址：指出该页在外存上的地址。,5.2 请求分页技术,2.缺页中断 程序在执行时，首先检查页表，当状态位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。 同样需经历一般中断处理的全过程： 保护CPU环境、分析中断原因、转入中断处理程序、恢复CPU环境 与一般中断的区别： 1）在指令执行期间发生和处理 2）一条指令可能引发多次缺页中断,5.2 请求分页技术,3.

41、地址变换机构 在分页系统地址变换机构的基础上，增加了： 缺页中断 产生、处理 页面置换 换出老页面，换入所缺页,5.2 请求分页技术,4.7.2 内存分配策略和分配算法 1. 最小物理块数的确定 与计算机的硬件结构有关，取决于指令格式、功能和寻址方式。 如：允许间接寻址：则至少要求3个物理块。,5.2 请求分页技术,2. 物理块的分配策略 固定分配局部置换 为每个进程分配一定数量的块，运行期保持不变 缺点：难以确定分配页数.(少：置换率高，多：浪费) 2) 可变分配全局置换 为每个进程分配一定数量的块，OS也保持一个空闲物理块队列，缺页时先分配空闲块，无空闲块时才进行页面置换 3) 可变分配局

42、部置换 根据进程的缺页率进行页面数调整，缺页率高的适当增加分配物理块，缺页率低的适当减少分配。,5.2 请求分页技术,3. 物理块分配算法 平均分配算法 把可分配内存平均分配给各进程。存在浪费,或高缺页率。 2) 按比例分配算法 根据进程的大小按比例分配物理块。 考虑优先权的分配算法 为重要、紧迫的作业分配较多的内存空间。通常将可分配物理块分为两组，一组按比例分配给各进程，一组用来按进程优先权适当增加其份额。,调页策略,1.调入时机： 1）预调：（根据空间局部性，预测不久后将访问） 成功率50。故主要用于首次调入时程序员指定页面。 2）请求调页：常用，但较费系统开销。 2从何处调页： 对换区：

43、修改过的页被换出时入对换区，快 文件区：不会被修改的直接从文件区调入，稍慢 对共享页，应判断其是否在内存区。 3.页面调入过程 缺页中断-中断处理程序-查找页表找到所缺页外存地址-调入/置换，修改页表项并写入快表,抖动,定义：在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。 引发抖动的原因：一是给进程分配的物理块数过少，二是页面置换算法不合理。,5.3 页面置换算法,页面置换的过程 （1）找出所需页面在磁盘上的位置； （2）找出可用空闲内存块。如果有，就立即使用，否则，就进行页面置换，选择一

44、个老的页面置换到外存磁盘。 （3）将所需页面装入内存，修改相应的数据结构。 （4）继续执行用户进程。,5.3 页面置换算法,页面置换算法 定义：选择换出页面的算法。 评价依据：页面更换频率，低为好。 最佳置换算法(OPT) 先进先出(FIFO)页面置换算法 最近最久未使用(LRU)置换算法 Clock置换算法 最少使用(LFU)置换算法 页面缓冲(PBA)算法,最佳置换算法(OPT),最佳(Optimal)置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率

45、。 目前无法预知页面中未来的访问情况，因此该算法无法实现；但可以用来评价其他算法。 例：系统为某进程分配三个物理块，现有如下的页面号引用串：2，3，2，1，5，2，4，5，3，2，5，2,先进先出(FIFO)页面置换算法,FIFO算法总是淘汰最先进入内存的页面，即选择在内存中滞留时间最久的页面。 实现简单：把已调入页面按进入内存的次序链接成一个队列，并设置替换指针指向最老页面。 缺点：置换率高，性能较差,最近最久未使用(LRU)置换算法,1. LRU（Least Recently Used）算法描述 利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。,最近最久未使用(LRU)置换算法,2. LRU算法的硬件支持 1）移位寄存器(R=Rn-1R0) 为每个在内存的页面设置一个移位寄存器R 访问某块时，将高位(Rn-1)置1。 定时右移1位，一段时间以后，最久未被使用的页面，其寄存器R的值最小。 置换时选择R值最小的。（如图4-29）,最近最久未使用(LRU)置换算法,2) 栈 每当进程访问某页时，将其从栈中移出，压入栈顶。因此，栈顶最新，栈底最老。 置换时选择栈底。,Clock置换算法,1. 简单的Clock置换算法 为每页设一访问位，将内存中所有页面链接成循环队列 当某页被访问时，访问位置1 置换时检查访问位，是0换出；是1则置