《存储管理请求页式管理请求段式管理》由会员分享，可在线阅读，更多相关《存储管理请求页式管理请求段式管理（57页珍藏版）》请在金锄头文库上搜索。
1、1,第四章存储器管理,4.6 虚拟存储器 4.7 请求分页存储管理方式4.8 页面置换算法 4.9 请求分段存储管理,2,复习,虚拟存储器的引入,程序的局部性规律，程序往往会不均匀地高度局部化地访问内存。,这种特性使得程序的执行在一段时间内被限制在作业的某一局部范围。,（1）时间局限性:最近被访问的存储位置，很可能不久的将来还要被访问。,(2)空间局限性:存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。,3,虚拟存储器的定义？,所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。,虚拟存储器的大小受计算机系统地址结构和
2、可用外存数量的限制，与实际内存单元的数量无关。,4,页式虚拟存储系统,分页系统的基础上，增加了请求调页功能、页面置换功能所形成的分页请求系统。,请求分段系统,在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。,5,4.7 请求分页存储管理方式,在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,请求分页存储管理方式是建立在纯分页基础上的.其基本思想是？,6,4.7.1 请求分页中的硬件支持,一、页表机制的改进,(1)状态位（驻留位
3、）P:该页是在内存还是在外存(2)访问字段位A：记录本页在一段时间内被访问的次数;根据访问位来决定淘汰哪页（由不同的算法决定） (3)修改位M :该页调入内存后是否在被修改过(4)外存地址:该页在外存上的地址,通常为外存物理块号.,7,2、缺页中断机构,在请求分页系统中，当要访问的页面不在内存时，硬件发一个缺页中断，转交OS处理。,3、地址变换机构,请求分页系统中的地址变换机构是以分页系统的地址变换机构为基础的，还增加了产生缺页中断、处理缺页中断，置换等功能。,8,4.7.2 内存分配策略和分配算法,物理块的分配策略,1)、固定分配局部置换,2)、可变分配全局置换,3)、可变分配局部置换,9,
4、4.7.3 调页策略,1、何时调入页面,1、预调页策略,2、请求调页策略,用于首次调入,10,4.8.1最佳置换算法和先进先出算法,4.8 页面置换算法,假定作业p共计n页，而系统分配给它的主存块只有m块（m,n均为正整数，mn），即最多只能容纳m页。如果程序p在运行中成功的访问次数为s,不成功的访问次数为f,那么，其总的访问次数a=s+f，若定义f =f/a，称f 为缺页中断率。,缺页中断率:,11,影响缺页中断次数的因素,（1）分配给进程的物理页面数物理页面数多，缺页中断少，反之，则缺页中断多物理页面数多，进程数少（影响系统效率），反之，则进程数多（缺页中断多）根据试验分析：对一共有n页的
5、进程来说，只要能分到n/2块内存空间，就可使系统获得最高效率；,（2）页面本身的大小页面大，进程的页数少，一页的信息就大，缺页中断次数减少；不同的计算机系统，有不同页面大小；,12,例：程序要把128128的数组初值置“0”，数组中每一个元素为一个字，假定页面大小为128个字，数组中的每一行元素存放一页，能供该程序使用的主存块只有1块。初始时第一页在内存；,程序编制方法1： For j:=1 to 128 For i:=1 to 128 Aij:=0;按列：缺页中断次数：1281281,程序编制方法2： For i:=1 to 128 For j:=1 to 128 Aij:=0;按行：缺页中
6、断次数 128-1,（3）程序的编制方法,可见：缺页中断率与程序的局部化程度密切相关。希望编制的程序能经常集中在几个页面上；,13,14,(4) 页面淘汰算法理论的页面淘汰算法应该选择的被淘汰页面将是以后永不使用的，或在最长(未来)时间内不再被访问的页面。（OPT算法）。实际上，可以用理论的页面淘汰算法作标准，选择其它较好的页面淘汰算法,页面淘汰算法选择不合适，会使系统“抖动”,15,刚被换出的页很快又被访问，需要重新调入，为此又需再选出一页调出；而刚被换出的页，很快又要被访问，又需把它调入，如此频繁地更换页面，以致一个进程在运行中，把大部分时间花费在完成页面的置换工作上，使得调度页面所需时间
7、比进程实际运行的时间还多. 我们称该进程发生了“抖动”。,抖动,16,最佳置换算法是由Relady在1966年提出的，这种算法选择的被淘汰页面，将是永不使用的，或在最长时间内不再被访问的页面。 “最佳”是指对于任意的内存固定空间m和程序 p, 缺页中断率最小。它是一个理论上的算法。,1、最佳置换算法（OPT）,17,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。,采用最佳置换算法，只发生了6次页面置换，发生了9次缺页中断。缺页率=9/21,18,2、先进先出页面置换算法（FIFO）,这是最早出现的置换算法，这种算法总是淘汰最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘
8、汰。,19,采用FIFO算法进行页面置换时的情况。,一共发生了12次页面置换，比最佳置换算法多了1倍。缺页率15/21=3/4，15次页面中断。,20,FIFO是根据各个页面调入内存的时间来选择被淘汰页面，但页面调入的先后并不能反映页面的使用情况。 FIFO算法只是在按线性顺序访问地址空间才是理想的。 未考虑到程序的动态特性。 可能引起异常。,21,先进先出置换算法的一个异常现象：对于一些特定的页面访问序列，先进先出置换算法有随着分给的页架数增加，缺页频率也增加的异常现象。,A B C D A B E E E C D D A B C D A B B B E C C A B C D A A A
9、B E E+ + + + + + + + +,页面访问序列,A B C D A B E A B C D E,九次缺页,三个页面,A B C D D D E A B C D E A B C C C D E A B C D A B B B C D E A B C A A A B C D E A B+ + + + + + + + + +,页面访问序列,十次缺页,四个页面,22,4.8.2 最近最久未使用LRU置换算法,1、LRU（Least Recently Used）算法的描述,基本思想：基于程序的局部性原理，在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用，反之，已经很久没有使用的
10、页面很有可能在未来较长一段时间内不会使用；因此，在缺页发生时，淘汰掉最久未使用的页；,选择淘汰的页面是最近最久未使用,23,我们用“最近的过去”来直接推断“最近的将来”。,发生了9次页面置换。,标明访问时间,24,2、LRU算法的硬件支持,为了实现LRU算法必须解决： （1）一个进程在内存中的各个页面各有多久时间未被进程访问； （2）如何快速地知道哪一页是最近最久未使用的页面。 需要两类硬件之一：寄存器 或 栈,25,1、寄存器,为每个在内存中的页面配置一个移位寄存器，表示为： R=Rn-1Rn-2Rn-3R1R2R0,当进程访问某物理块时，要将相应的寄存器的Rn-1位置为1。,定时信号将每隔
11、一定时间将寄存器右移一次，把n位寄存器的数看作是一个无符号的整数，最近最久未使用的页面就对应着具有最小数值的寄存器 。,用于记录某进程在内存中各页的使用情况。,26,2、栈,LRU置换算法可用堆栈的方法来实现。,栈中存放当前内存中的页面号，每当访问一页时就调整一次堆栈，总是使最近访问的那页的页面号保持在栈顶，然后根据当前被访问时间的近远，依次排列，栈底总是最近最久未使用的那页的页面号。,淘汰,27,作业固定占用4块主存,例如，某作业按下列页号访问：,28,4.8.3 CLock置换算法,CLock算法就是用得较多的一种LRU近似算法。,1、简单的CLock置换算法,当需要置换一页时，选择在最近
12、一段时间内最久未用的页予以淘汰，因此称为最近未用的算法NRU（Not Recently Used）。,29,这种近似算法，要求为每一页设置一位访问位，再将内存中的所有页面都通过指针按FIFO链成一个循环队列。,当某页被访问时，访问位由硬件自动置“1”。根据访问位的状态来判断各个页面最近使用的情况。如果是“0”，就选择该页换出；若为1，则重新将它置为0，再按照FIFO算法检查下一个页面。,30,替换指针,总是指向最近被替换的页所在的存储块，缺页时从其后一块开始。,31,2、改进型CLock置换算法,1类 （A=0，M=0），最近既未被访问，又未被修改，是最佳淘汰页。,2类 （A=0，M=1），最
13、近未被访问，但已被修改，不是很好的淘汰页。,3类 （A=1，M=0），最近已被访问，但未被修改，可能再被访问。,既要考虑到页面的使用情况，还要考虑置换代价,4类 （A=1，M=1），最近已被访问且被修改，可能再被访问。,根据访问位A和修改位M的组合来确定,32,改进型CLock算法，执行过程可分为以下三步：,（1）从指针的当前位置开始，扫描按先进先出循环队列，寻找A=0且M=0的第一类页面，将符合条件的第一个页面作为淘汰页，在第一次扫描期间A不改变。,33,（2）第一步失败，开始第二轮扫描，寻找A=0且M=1的第二类页面，将符合条件的第一个页面作为淘汰页。将所有经过的页面的访问位置0。,（3）
14、第二步也失败，把指针返回到开始的位置，把所有的访问位A置为0，然后重复第一步，如还是失败，重复第二步，就一定能找到被淘汰的页。,34,改进型Clock算法的特点,该算法与简单 Clock算法比较，可减少磁盘的I/O操作次数，但为了找到要淘汰的页面，可能需要经过几轮扫描，使该算法本身的开销有所增加。,35,4.8.4 其它置换算法,1、最少使用（Least Frequently Used）置换算法（LFU ）,既可实现LRU，也可实现LFU,为内存中的每个页面设置一个移位寄存器，用来记录页面被访问的频率，淘汰页是最少使用或是访问次数最少的页面。,ri最小的页就是最近一段时间使用最少的页面。,36,2、页面缓冲算法（Page Buffering Algorithm）,PBA,采用可变分配和局部置换方式，采用FIFO置换算法,实际上,页面在内存中并不做物理上的移动,只是将页表中的表项移到上述链表;这种方法, 修改或未修改的页面还在内存中,当该进程需要再次访问这些页面时,花费很小就能使这些页面返回到进程中; 当被修改的页面数目达到一定值时,一起写回磁盘上,从而显著减少磁盘I/O的操作次数;,37,
