CH4存储器管理

null第4章 存储管理第4章 存储管理§4.1 存储管理概念（*） §4.2 分区存储管理（*** ） §4.3 页式存储管理 （*****） §4.4 段式存储管理 （ *** ） §4.5 虚拟存储管理 （*****）存储管理的功能:存储管理的功能:主存储空间的分配和去配 地址转换和存储保护 主存储空间的共享 主存储空间的扩充null§4.1 存储管理的概念 由于系统开工期间，OS程序与其他程序一起共享主存，为安全起见，多道程序系统常由OS把内存初始化为：二、常用的基本概念二、常用的基本概念 ②逻辑地址（相对地址）：程序用来访问信息所用的一系列的地址单元。又称相对地址或虚地址。 逻辑地址的集合称为逻辑地址空间，也叫相对地址空间或虚空间。 作业运行时不能按其相对地址访问内存单元，而应按相应的物理地址访问，需要进行相对地址到物理地址的转换。 1.物理地址和逻辑地址①物理地址（绝对地址）：指内存单元的地址.主存中一系列存储物理单元。物理地址的集合称为物理地址空间，也叫绝对地址空间或实空间或存储空间，亦即内存空间。 2.重定位  2.重定位 当一个地址装入与其地址空间不一致的存储空间中，就得要地址变换。也就是说将虚地址映射为内存地址，把这种作法叫做地址重定位 ＝》静态重定位：是指在程序运行之前由装入程序完成的重定位过程。在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。 ＝》动态重定位：是在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址. 动态重定位由软件（操作系统）和硬件（地址转换机构）相互配合来实现。3．内存扩充技术 3．内存扩充技术 ①覆盖（overlay技术） 所谓覆盖，是指同一主存区可以被不同的程序段重复使用。通常一个作业由若干个功能上相互独立的程序段组成，作业在一次运行时，也只用到其中的几段，利用这样一个事实，我们就可以让那些不会同时执行的程序段共用同一个主存区。因此，我们把可以相互覆盖的程序段叫做覆盖。而把可共享的主存区叫做覆盖区。 覆盖的基本原理可用图例说明 覆盖的基本原理可用图例说明 主程序(30k)主程序(30k)子程序 A(8k)子程序 B(10k)子程序M(20k)子程序N(25k)子程序X(15k) 主程序（30k)覆盖区1(25k)覆盖 区0 (10k)内 存 区用 户 的 结 构 化 程 序 区由图中的调用关系不难看出：由图中的调用关系不难看出：主程序是一个独立的段，它调用子A和子B，且子A与子B是互斥被调用的两个段，在子A执行过程中，它调用子X，而子B执行过程中它又调用子M和子N，显然子M和子N也是互斥被调用的。 覆盖技术的主要特点是打破了必须将一个作业的全部信息 装入主存后才能运行的限制。在一定程度上解决了小主存 运行大作业的矛盾。null ①交换技术被广泛地运用于早期的小型分时系统的存贮管理中。 ②被换出到外存的程序只是临时被剥夺了对内存的使用权，过一段时间，还必须换入内存运行。因此，交换是一种用时间换空间的技术。 ② 交换（swapping）技术 所谓交换，就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。所以，交换技术也叫对换或滚进滚出（roll-in,roll-out）。也有的系统叫挂起调度或中级调度。null交换的时机通常在以下情况发生： (1)作业的进程用完时间片或等待输入输出； (2)作业要求扩充存贮而得不到满足时。 同覆盖技术一样，交换技术也是利用外存来逻辑地扩充主存。 它的主要特点是打破了一个程序一旦进入主存便一直运行到结束的限制。 交换时机问题③虚拟内存技术 ③虚拟内存技术 虚拟内存技术诞生于1961年。广泛使用是从上个世纪70年代初以后，今天几乎所有的操作系统都采用虚拟内存技术来管理内存。 这是一种利用虚拟存储器来逻辑扩充物理内存的技术。其基本思想是:用软硬件技术把内存与外存这两级存储器当成一级存储器来用，从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器，使得用户编程时再也不用考虑内存大小的限制了，给用户编程带来极大的方便。 虚拟内存技术的实现也利用了自动覆盖和交换技术。 单用户连续存储管理（了解）单用户连续存储管理（了解） 栅栏寄存器、重定位和存储保护静态重定位动态重定位单用户连续存储管理缺点单用户连续存储管理缺点处理器和外部设备串行工作； 一个作业独占主存储空间，降低存储空间的利用率； 计算机的外围设备利用率不高。§4.2 分区存储管理§4.2 分区存储管理 分区存储管理是把主存储器中的用户区作为一个连续区或分成若干个连续区进行管理，每个连续区中可装入一个作业。 多道程序系统一般都采用多个分区的存储管理，具体可分为固定分区和可变分区两种方式。 null一、固定分区存储管理OS0abcd空 job2 把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。这是一种静态分区法。 在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。 在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。 等待进入主存的作业排成一个作业队列。当主存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作业。当所有的分区都已装有作业，则其他的作业暂时不能再装入，绝对不允许在同一分区中同时装入两个或两个以上的作业。已经装入主存的作业在获得处理机运行时，要限定它只能在所占的分区中执行。 1.主存空间的分配与释放 1.主存空间的分配与释放 为了管理主存空间的使用，必须设置一张“主存分配表”，以说明各分区的分配情况。主存分配表中应指出各分区的起始地址和长度，并为每个分区设一个标志位。当标志位为“0”时，表示对应的分区是空闲分区，当标志位为非“0”时，表示对应的分区已被某作业占用。空闲分区可以用来装作业。OS作业A(6k)作业B(28k)0 32k 40k 56k 88k 当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。 当作业队列中有作业要装入主存时，存储管理可采用“顺序分配算法”进行主存空间的分配。 顺序查看主存分配表，找到一个标志为“0”的并且长度大于或等于欲装入作业的地址空间长度的分区，则把此分区分配给该作业，相应表目的标志位改成作业名的标识；若找不到一个这样的空闲分区，则该作业暂时不能装入主存。 主存空间的释放很简单。某作业执行结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表目后，把其中的标志位重新置成“0”即可。 2．地址转换和存储保护 2．地址转换和存储保护 固定分区管理方式下作业的地址转换常采用静态重定位技术。 固定分区管理方式下只考虑判断其物理地址即可。常采用“界限寄存器对”法。 If 下限地址<=物理地址<=上限地址 Then 继续 Else 产生“越界中断” ，转越界中断处理子程序 null 碎片大，存在小作业占用大分区的情况。不利于提高资源的利用率 。可调入的作业大小受分区大小的严格限制。分区数目在系统初启时确定，限制了多道运行的程序数。只适合于程序大小和出现频率已知的情形，实现简单。 解决办法：采用可变分区存储管理 4．固定分区的优、缺点二、可变分区存储管理二、可变分区存储管理内存管理的可变分区模式，又称变长分区模式。 与固定分区的区别就是：动态划分分区。 克服固定分区管理的“内碎片”问题。 可变分区(variable partition) 存储管理是按作业的实际大小来划分分区，且分区个数也是随机的,实现多个作业对内存的共享，进一步提高内存资源利用率。nullOSP1P2OSP1P2P3例子：一计算机系统有2560KB内存，采用可变分区模式管理，OS占低地址的400KB空间，用户内存为2160KB。 如图所示： 通过 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 得到： 通过分析得到：可变分区模式下，刚开始，OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。已占用区和空闲分区并不是绝对的。 必须有表来记录分区的情况。 程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的空闲表和已分配区表。 一旦一个内存分区被分配给一个进程，该进程可能被装入该块中执行，装入时需重定位。① 最先适应分配算法：① 最先适应分配算法：=>1.顺序查找各个空闲区，把第一个找到能容纳申请要求的内存区分配给申请者.（若空闲区比作业长度大，则分割该空闲区。一部分分配给作业一部分空闲。） =>2.调整相应的空闲表和已分配表。 评价：性能一般但实现比较简单直接，易于释放时合并相邻空间分区。比较容易满足大作业的需要。完成一次分配平均需要的搜索次数较大，影响了工作效率。② 最佳适应算法：② 最佳适应算法： 搜索整个空闲区以找出满足要求的最小空闲区。 思想：先使用小的空闲区，将大的空闲区留给大作 业，所以它总是试图找出最接近实际需要的 空闲区。 评价：尽可能的保留了较大的空间。 产生大量的不用被使用的很小的空闲区。 该算法不一定是最佳的。③最坏适应算法③最坏适应算法 总是搜索整个链表以找到够用的最大的空闲区，使分裂出来的小空闲区比较大，因而可以继续使用。 评价：分割后产生的空闲区一般仍可以供以后分配使用。 工作一段时间后，不能满足大作业对空闲区的请求。例题：分区存储管理算法题例题：分区存储管理算法题假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为：32k,10k,15k,228k,100k.现有五个作业J1,J2,J3,J4,J5。他们各需要主存1k,10k,128k,28k,115k。 判断用最先适应分配算法，最坏适应分配算法，最佳分配适应算法能否将这五个作业顺序装入？null示意图：空闲区表 起始地址 长度 标志位 30K 70K ZS已分配区表去配算法（一般了解）：去配算法（一般了解）：比固定分区管理增加了合并相邻空闲区的操作。 主要是为了减少“外碎片”，利于今后大作业的到来。 回收内存空间，关键是修改两个表。nullA B C D E FL1H2H1(a)若释放区R既有上邻空闲区，又有下邻空闲区。将三个空闲区合并成一个大空闲区。(a)若释放区R既有上邻空闲区，又有下邻空闲区。将三个空闲区合并成一个大空闲区。 (b)若释放区R只有上邻空闲区F1，则只修改空闲区F1大小即可。空闲区 F1释放区R低地址 高地址空闲区F2低地址 高地址空闲区 F1(a)合并后 先将R与F2合并记为F2,再将F2与F1合并记为F1,并将F2从链中删除。 (c)只有下邻空闲区 (c)只有下邻空闲区占用区1进程 P空闲区F2空闲区F2占用区1低地址 高地址低地址 高地址合并后修改空闲区F2的首地址。 F2的大小＝F2的大小＋R的大小 (d)既无上邻又无下邻空闲区修改释放区的首地址为空闲区的起始地址null小结：可变分区的回收情况内存扩充内存扩充消除了固定分区管理造成的“内碎片”，但是不可避免的在内存空间造成“外碎片”。 例如：如图中已有J1,J3,J4三个作业在内存，还有两个长度分别为300K和260K的空闲区。但是这两个空闲区都不满足作业J5的500K空间的要求。 采用移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。null经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，此进程就无法运行。 要使其运行，必须进行“动态重定位”。 紧缩的条件和时机： （1）一旦有归还的分区便进行紧缩，系统开销大。 （2）当发现内存不够用时…. 移动（紧缩）技术null 分页存储管理是解决存储零头的一种方法。 （移动）动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高，这是因为这种分配要求把作业必须安置在一连续存储区内的缘故，而分页存储管理正是要避开这种连续性要求。§4.3 分页式存储管理一、分页式存储管理一、分页式存储管理 假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现在有一个新婚旅游团要求入住。接待员统计了一下，对旅游团领队说：“贵团全体成员都能住下，两人一个房间，但是不能住在同一楼层了，因为每层空着的客房不够，更没有几个挨着的。请原谅！”。 对于这样的安排，一般人不会感到奇怪。因为该旅游团本来就是由一对对夫妻等组成的，而饭店的客房本来也是两人一间的，两人一组正好可住在一个客房里；另外，饭店几乎每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。 1.基本原理（引例）2.基本思想2.基本思想 ①将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个物理块、物理页或实页，页架或页帧（frame），可简称为块（block）。所有的块按物理地址递增顺序连续编号为0、1、2、……。 这里的块相当于饭店的客房，系统对内存分块相当于饭店把大楼所有的客房都 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 成标准的双人间。 ②每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页，也有人叫页面，可简称为页（page）。所有的页按照逻辑地址递增顺序连续编号为0、1、2、……。 这里，对作业地址空间分页就相当于把旅游团成员分成夫妇两人一组。 null ③一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，以页为单位分配内存，一页分配一个块，作业所有的页所占的块可以不连续。系统同时为这个作业建立一个页号与块号的对照表，称为页表。 这好象饭店有个记录客户入住情况的客户登记表一样。另外，饭店安排客户入住是要查看全部客房的使用情况一览表，相应地系统给作业分配内存时要查看主存分配表或者内存块说明表。 ④每个块的大小是固定的，一般是个1/2KB～4KB之间的数值（请思考：块尺寸为什么太大或太小都不好），而且必须是个2的幂次。 对块尺寸这样规定相当于饭店规定客房是双人间。可以设想一下，如果上例中饭店所有的客房都是十人间的话，效益肯定不如全是双人间的好。 分页存储管理的基本原理： 分页存储管理的基本原理：系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续。 这实际是个把作业从地址空间映射到存储空间的过程。 3.地址转换3.地址转换页面的划分完全是一种系统硬件的行为，一个逻辑地址放到这种地址结构中，自然就分成了页号和页内单元号两部分。31 12 11 0页面大小为：4KB（12位）（1）数据结构（1）数据结构在分页系统中，允许将作业（进程）的任一页装入到内存中的任一可用的物理块中，但进程的地址空间本来是连续的，若把它分页后装入到不相邻的物理块中，要保证系统仍能正确运行，就要实现从进程的逻辑地址变换为内存的物理地址。 所以，系统为每个进程建立一张页面映射表，简称页表（通过页表实现页面映射）。null0页 1页 2页 3页 4页 … N页页表用户程序内存通过页表实现页面映射（2）地址映射（2）地址映射在系统中设置地址变换机构，能将用户进程地址空间中的逻辑地址变为内存空间中的物理地址。 由于页面和物理块的大小相等，页内偏移地址和块内偏移地址是相同的。无须进行从页内地址到块内地址的转换。 地址变换机构的任务，关键是将逻辑地址中的页号转换为内存中的物理块号。物理块号内的偏移地址就是页内偏移地址。 页表的作用就是从页号到物理块号的转换，所以地址变换的任务是借助于页表来完成的。null 地址转换: 绝对地址 ＝ 块号×块长 + 页内地址地址变换机构例：一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理快（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]；例：一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理快（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]；解答：因为每页有1024B，所以内存中 每块也有1024B。 物理地址 ＝ 块号×块长 + 页内地址， 得到：（1）的物理地址为：3×1024+100=3072+100=3172 （2）的物理地址为：5×1024+179=5120+179=5299 （3）的物理地址为：6×1024+785=6144+785=6929 null因为页表是存放在内存中的，CPU要存取一个数据，需访问主存两次： 第一次：访内存中的页表，找到该页的的物理块号，将此块号与页内地址拼结形成物理地址； 第二次：真正访问该物理地址，存取其中的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 。 这样就把程序的执行速度降低一倍。 为了提高存取速度，在地址变换机构中增设一组寄存器，用来存放访问的那些页表。把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫相联（联想）存贮器。 联想存贮器的存取速度比主存高，但造价高容量小，因此只能少量采用。相联（联想）存贮器和快表null其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所对应的主存块号；访问位指示该页最近是否被访问过。“0”表示没有被访问，“1”表示访问过 ；“状态”位指示该寄存器是否被占用。通常“0”表示空闲，“1”表示占用。 为了保证快表中的内容为现正运行程序的页表内容，在每个程序被选中时，由恢复现场程序把快表的所有状态位清“0”，或恢复已保存的快表内容。null当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。 当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入快表中；若快表已满，则置换其中访问位为0的一项（先进先出）。 另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与CPU给出的页内位移相拼接，得到访问主存的绝对地址。快表的使用null分段存储管理引入的主要原因 模块化程序设计的分段结构 分段存储管理---二维地址结构 §4.4 段式存储管理模块化程序设计的分段结构模块化程序设计的分段结构 1.分段式存储管理的基本原理1.分段式存储管理的基本原理二维逻辑地址 ：（段号，段内地址） 作业表和段表 null 2.段式存储管理的地址转换和存储保护3.段的共享3.段的共享段的共享，是通过不同作业段表中的项指向同一个段基址来实现。 几道作业共享的例行程序就可放在一个段中，只要让各道作业的共享部分有相同的基址/限长值。 对共享段的信息必须进行保护。4.分段和分页的比较4.分段和分页的比较分段是信息的逻辑单位，由源程序的逻辑结构所决定，用户可见；分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见。 段长可根据用户需要来规定，段起始地址可从任何主存地址开始；页长由系统确定，页面只能以页大小的整倍数地址开始。 分段方式中，源程序(段号，段内位移)经连结装配后地址仍保持二维结构；分页方式中，源程序(页号，页内位移)经连结装配后地址变成了一维结构。§4.5 虚拟存储管理(P328)§4.5 虚拟存储管理(P328) 指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为： 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内； 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。1.局部性原理(principle of locality)(1) 虚拟存储技术的引入(1) 虚拟存储技术的引入虚拟存储器的基本思路：部分装入，部分对换。 引入虚拟存储技术的好处： A、大程序：可在较小的可用内存中执行较大的用户程序； B、大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)； C、并发：可在内存中容纳更多程序并发执行。2、虚拟存储技术(2)虚拟存储技术的特征(2)虚拟存储技术的特征不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）； 部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的； 大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间； 总容量不超过物理内存和外存交换区容量之和。其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理技术。 4.6 请求分页式存储管理4.6 请求分页式存储管理系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。 这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。 4.6.1 基本原理4.6.2 请求分页中的硬件支持4.6.2 请求分页中的硬件支持页表表目需增加外存块号、状态位、访问位、修改位等字段。 外存块号指出该页在外存的地址，供调入该页时用；状态位指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位；访问位则是该页被访问过的标志或该页被访问过的次数；供选择换出页面时用；修改位表示该页是否被修改过，供置换页面时参考。1.页表机制2.缺页中断机构当要访问的页面不在内存时，便产生一次缺页中断。 缺页中断的特殊性。3.地址变换机构 产生和处理缺页中断，从内存换出一页等功能）4.6.3 页面调入策略 4.6.3 页面调入策略 A、请求调入 当发生页面故障时进行调度，即当进程访问不在内存的页面引发缺页中断时，由系统根据这种访问请求把所缺页面装入内存。 优点：由请求调入策略装入的页一定会被访问，再加之比较容易实现，故在目前的虚拟存储器中，大多采用此策略。 缺点：处理缺页中断和调页的系统开销较大，每次仅调入一页，增加了磁盘I/O的启动频率。 B、预调入 B、预调入 也称先行调度，即系统预测进程将要使用的页面,使用前预先调入主存,以减少今后的缺页率。每次调入若干页面,而不是仅调一页。 主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页面。 优点：一次调入多页能减少磁盘I/O启动次数,节省寻道和搜索时间，提高调页的I/O效率。 缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。4.7 页面置换算法4.7 页面置换算法页面替换算法又称页面调度算法、淘汰算法或置换算法。 当主存空间已装满而又要装入新页时，必须按一定算法把主存的一些页面调出去，这项工作称页面替换。 如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需要将它调入，如此频繁更换页面，以致花费大量时间，称这种现象为“抖动”。 null这是Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。 显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。 （1）最佳淘汰算法——OPT(Optimal)假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2采用OPT淘汰算法： 7 7 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 4 4 4 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 命中 * * * * * * *7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2缺页8次，命中7次（2）先进先出淘汰算法——FIFO（2）先进先出淘汰算法——FIFO这是最早出现的淘汰算法。 总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。 缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现bleady现象。 采用FIFO淘汰算法（三个物理块）：采用FIFO淘汰算法（三个物理块）： 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 1 0 0 0 3 3 3 3 3 2 * * * 命中7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2缺页12次，命中3次采用FIFO淘汰算法(4个物理块)：采用FIFO淘汰算法(4个物理块)：0 1 2 2 3 3 4 4 4 0 0 0 1 2 7 0 1 1 2 2 3 3 3 4 4 4 0 1 7 0 0 1 1 2 2 2 3 3 3 4 0 7 7 0 0 1 1 1 2 2 2 3 4 * * * * * * 命中7，0，1，2，0，3，0，4，2，3，0 ，3，2，1，2缺页9次，命中6次nullBelady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。 Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。 Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。Belady现象（3）最近最久未使用算法（LRU） （3）最近最久未使用算法（LRU） 根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向前看的，而LRU是向后看的。 下面给出LRU的两个实现算法： 下面给出LRU的两个实现算法： 计时法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。 堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。 假定现有一进程所访问的页面的页面号序列为：4，8，0，8，1，0，2，1，2，6假定现有一进程所访问的页面的页面号序列为：4，8，0，8，1，0，2，1，2，6随着进程的访问，栈中页面号的变化情况： 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1 8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 84，8，0，8，1，0，1，2，1，2，6 缺页6次 * * * * * 命中5次null这是一种LRU的近似算法，是通过对FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。 该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为0的较早进入内存的页为止，把它选为被淘汰的页。 （4）二次机会淘汰算法(SC)（5）时钟(Clock)淘汰算法 （5）时钟(Clock)淘汰算法 该算法首先检测指针所指的页面，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为0的页面为止。 缺点：就是需要把访问位为1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的LRU近似算法——时钟淘汰算法。 （6）最近未用淘汰算法——NRU（6）最近未用淘汰算法——NRU它把FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近LRU算法的淘汰对象。 该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成1；当对某页面执行读操作时，只有其访问位被硬件置成1。系统每隔固定时间将所有访问位都清0。按照下列次序选择被淘汰的页面：按照下列次序选择被淘汰的页面：①访问位＝０，修改位＝０；直接淘汰； ②访问位＝０，修改位＝１；直接淘汰； ③访问位＝１，修改位＝０；直接淘汰； ④访问位＝１，修改位＝１；写回外存后淘汰； 影响缺页中断率的因素 影响缺页中断率的因素 （1）页面调度算法不合理 抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。 显然，抖动是由于缺页中断率很高而引起的一种坏现象，它将严重影响系统的效率，甚至可能使系统全面崩溃。 （2）分配给作业的内存块数太少 （2）分配给作业的内存块数太少 作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。 （3）页面大小的选择不合理（3）页面大小的选择不合理 虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在0.5KB-4KB之间，是个实验统计值。因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。 （4）用户程序编制的方法不合适 作业的缺页中断率与程序的局部化（包括时间局部化和空间局部化）程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。 置换算法举例置换算法举例某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。nullnullnull1、思考题：设一个逻辑空间有16个页面，每页大小为2048B，逻辑地址需要多少位表示？ 解答：由题义：页面数为16，故需要4位二进制数表示；每页有2048B，故页内地址需要11位二进制数表示；逻辑地址由页号和页内地址组成，所以需要4+11=15位二进制数表示。0K 5K 20K 40K 50K 90K 100K 128K 0K 5K 20K 40K 50K 90K 100K 128K 2、假设某计算机系统的内存容量为128KB，对存储器采用可变分区存储管理办法，现有三个作业（J1，J2，J3）在内存，其存储器的分配如下图所示。现有一个需要25KB存储空间的作业J4请求装入内存，若使用最优适应分配算法给J4分配空间。请给出装入J4后的内存分配表。 null解答：装入J4后的内存占用表、空闲表如下：0K 5K 20K 40K 50K 90K 100K 125K 128K 内存占用表空闲表 3、一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理快（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]； （4）[3，1010] 3、一个由四个页面（页号为0―3），每页由1024个字节组成的程序，把它装入由8个物理快（块号为0―7）组成的存储器中，装入情况如下表所示。已知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址）， 请按页表求出对应的物理地址。 （1）[0，100]； （2）[1，179]； （3）[2，785]； （4）[3，1010] 解答：因为每页有1024B，所以内存中 每块也有1024B。故内存中每块的起始 地址为（每块起始地址=块号×块长）： 0块：0000 1块：1024 2块：2048 3块：30724块：4096 5块：5120 6块：6144 7块：7168 （1）的物理地址为：3072+100=3172 （2）的物理地址为：5120+179=5299 （3）的物理地址为：6144+785=6929 （4）的物理地址为：2048+1010=3058 4、给定段表如下，给定地址为段号\位数：1）[0,430] 2)[3,400] 3)[1,1] 4)[2,500] 5)[4,42]，试求出对应的物理地址。 4、给定段表如下，给定地址为段号\位数：1）[0,430] 2)[3,400] 3)[1,1] 4)[2,500] 5)[4,42]，试求出对应的物理地址。根据给出的逻辑地址，可得物理地址如下： 1）的物理地址为：219+430=649 2）的物理地址为：1327+400=1727 3）的物理地址为：2300+1=2301 4）由逻辑地址知此次要访问第2段，段内位移为500，而第2段段长为100，位移超出段长，发生越界访问，系统给出出错信息，并使访问终止而退出系统。 5）的物理地址为：1592+42=19945、在一个分页式虚存系统中，用户编程空间32个页，页长1KB，主存为16KB，如果用户程序有10页长，若已知虚页0，1，2，3，已分到页框8，7，4，10，试把虚地址0AC5H和1AC5H转换成对应的物理地址。5、在一个分页式虚存系统中，用户编程空间32个页，页长1KB，主存为16KB，如果用户程序有10页长，若已知虚页0，1，2，3，已分到页框8，7，4，10，试把虚地址0AC5H和1AC5H转换成对应的物理地址。 （2）逻辑地址1AC5H（001101011000101）的页号为00110即6，故页号合法，但该页未装入内存，故产生缺页中断。 （1）逻辑地址0AC5H（000101011000101）的页号为00010即2，故页号合法，从页表中找到对应的内存块号为4，即0100；与页内地址1011000101拼接形成物理地址01001011000101，即12C5。 由题目所给的条件可知，该系统的逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址有14位，其中高4位为块号，低10位为块内地址。另为由于题目给出的逻辑地址是16进制数，故可将其转换为2进制数以直接获得页号和页内地址，再完成地址转换。null