存储管理请求分页系统课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,学习目标,理解并掌握请求分页存储管理系统中的硬件支持,理解请求分页存储管理系统中的内存分配策略和分配算法,掌握主要页面置换算法,4.7,请求分页存储管理方式,请求分页存储管理的基本思想,请求分页存储管理方式是实现虚拟存储器的一种常用技术；,基本思想：,在进程开始运行之前，仅装入当前要执行的部分页面即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面为了实现页式虚存，系统需要解决下面三个问题,：,1,）系统如何感知进程当前所需页面不在主存（页表机制）；,2,）当发现缺页时，如何把所缺页面调入主存（缺页中断机构）；,3,）在置换页面时，根据什么策略选择欲淘汰的页面（置换算法）4.7.1,请求分页的硬件支持,状态位（中断位）：,标识该页是否在内存（,0,或,1,）；,访问位：,标识该页面的近来的访问次数或时间（换出）；,修改位：,标识此页是否在内存中被修改过；,外存地址：,记录该页面在外存上的地址，即,(,外存而非内存的,),物理块号。

页号,状态位,物理块号,外存地址,访问位,修改位,1,、页表机制,程序在执行时，首先检查页表，当状态位指示该页不在主存时，则引起一个缺页中断发生，其中断执行过程与一般中断相同：,保护现场（,CPU,环境）；,中断处理（中断处理程序装入页面）；,恢复现场，返回断点继续执行2.,缺页中断机构,缺页中断与一般中断的不同点：,一般中断是一条,指令完成后,检查是否有中断,缺页中断是,在指令执行期间,产生和处理中断，,一条指令执行时可能产生多个缺页中断,(,如指令可能访问多个内存地址，这些地址在不同的页中,),相应的中断处理程序把控制转向缺页中断子程序执行此子程序，即把所缺页面装入主存然后处理机重新执行缺页时打断的指令,这时，就将顺利形成物理地址缺页中断的处理过程是由硬件和软件共同实现的缺页中断引发的连续中断,内存分配策略和分配算法,1,最小物理块数的确定,这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数当系统为进程分配的物理块数少于此值时，进程将无法运行进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为,2,。

其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面2,物理块的分配策略,1),固定分配局部置换,(Fixed Allocation,，,Local Replacement),这是指基于进程的类型,(,交互型或批处理型等,),，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的,n,个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定若太少，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成,CPU,空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间2),可变分配全局置换,(Variable Allocation,，,Global Replacement),这可能是最易于实现的一种物理块分配和置换策略，已用于若干个,OS,中在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而,OS,自身也保持一个空闲物理块队列当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的,(,缺,),页装入其中。

这样，凡产生缺页,(,中断,),的进程，都将获得新的物理块仅当空闲物理块队列中的物理块用完时，,OS,才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加3),可变分配局部置换,(Variable Allocation,，,Local Replacement),这同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加3,物理块分配算法,1),平均分配算法,这是将系统中所有可供分配的物理块平均分配给各个进程例如，当系统中有,100,个物理块，有,5,个进程在运行时，每个进程可分得,20,个物理块这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小如有一个进程其大小为,200,页，只分配给它,20,个块，这样，它必然会有很高的缺页率；而另一个进程只有,10,页，却有,10,个物理块闲置未用。

2),按比例分配算法,这是根据进程的大小按比例分配物理块的算法如果系统中共有,n,个进程，每个进程的页面数为,S,i,，则系统中各进程页面数的总和为：,又假定系统中可用的物理块总数为,m,，则每个进程所能分到的物理块数为,b,i,，将有：,b,应该取整，它必须大于最小物理块数3),考虑优先权的分配算法,在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的调页策略,1,调入页面的时机,1),预调页策略,如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页更高效些但如果调入的一批页面中的大多数都未被访问，则又是低效的可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存如果预测较准确，那么，这种策略显然是很有吸引力的但遗憾的是，目前预调页的成功率仅约,50%,故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

2),请求调页策略,当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由,OS,将其所需页面调入内存由请求调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中大多采用此策略但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘,I/O,的启动频率4.8,页面置换算法,4,.8.1,最佳置换算法,最佳置换算法是由,Belady,于,1966,年提出的一种理论上的算法其所选择的,被淘汰页面，将是以后永不使用的，或许是在最长,(,未来,),时间内不再被访问的页面采用最佳置换算法，通常可保证获得最低的缺页率最佳理论上有指导意义，实际上无法实现（需要能看见未来！）假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：,7,，,0,，,1,，,2,，,0,，,3,，,0,，,4,，,2,，,3,，,0,，,3,，,2,，,1,，,2,，,0,，,1,，,7,，,0,，,1,2.,先进先出,(FIFO),页面置换算法,FIFO,算法是最早出现的页面置换算法该算法,总是淘汰最先进入内存的页面，即选择在内存中停留时间最长（年龄最老）的一页予以淘汰,。

实现时可以引入一个替换指针指向最老的页面,置换次数？缺页中断次数？,算法名称、思想及实现是关键！,为了说明,FIFO,页面置换算法相关的可能问题，考虑一下引用串：,1,，,2,，,3,，,4,，,1,，,2,，,5,，,1,，,2,，,3,，,4,，,5,注意到对,4,个可用内存块的缺页次数（,10,）比,3,个内存块的缺页次数（,9,）还要大这种令人难以相信的结果称为,Belady,异常现象，即缺页次数随内存块增加而增加3.,最近最久未使用,(LRU),置换算法,最近最久未使用置换算是用过去的引用串的情况来预测将要到来的引用串的情况（,以“最近的过去”作为“不久将来”的近似），选择过去的最近一段时间内最久没有使用的页面淘汰掉它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰2.LRU,置换算法的硬件支持,1),寄存器,为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为,R=R,n-1,R,n-2,R,n-3,R,2,R,1,R,0,LRU,算法实现时需要为每个页面设置一个时间项，用来记录该页面上次被访问的时间，每次将时间数值最小的页面淘汰掉。

图,4-28,某进程具有,8,个页面时的,LRU,访问情况,2),栈：,栈顶始终存放最新被访问的页面，而栈底则存放最近最久 未访问的页面,图,4-29,用栈保存当前使用页面时栈的变化情况,LRU,近似算法,要完全实现,LRU,算法是一件十分困难的事情因为要找出最近最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问都必须更新这些记录这显然要花费巨大的系统开销（包括硬件开销和时间开销）因此，在实际系统中往往使用,LRU,的近似算法，包括,NRU,（最近未使用）算法和,LFU,（最少使用）算法,NRU,算法,Clock,置换算法,NRU,（,Not Recently Used,）：最近未使用页面淘汰算法,该算法在需要淘汰某一页时，,从那些最近一个时期内未被访问的页中任选一页淘汰,只要在页表中增设一个访问位即可实现当某页被访问时，访问位置,1,否则，访问位置,O,系统周期性地对所有引用位清零当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰4.8.3 Clock,置换算法,1.,简单的,Clock,置换算法,图,4-31,简单,Clock,置换算法的流程和示例,又称为二次机会算法、,NRU,最近未使用算法,实现：需要构建循环队列，引入一个查找指针,2.,改进型,Clock,置换算法,由访问位,A,和修改位,M,可以组合成下面四种类型的页面：,1,类,(A=0,M=0):,表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2,类,(A=0,M=1),：表示该页最近未被访问，但已被修改，并不是很好的淘汰页3,类,(A=1,M=0),：最近已被访问，但未被修改，该页有可能再被访问4,类,(A=1,M=1):,最近已被访问且被修改，该页可能再被访问其执行过程可分成以下三步：,(1),从指针所指示的当前位置开始，扫描循环队列，寻找,A=0,且,M=0,的第一类页面，将所遇到的第一个页面作为所选中的淘汰页在第一次扫描期间不改变访问位,A,2),如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找,A=0,且,M=1,的第二类页面，将所遇到的第一个这类页面作为淘汰页在第二轮扫描期间，将所有扫描过的页面的访问位都置,0,3),如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复,0,然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页4.7.4,其它置换算法,最少使用,(LFU,：,Least Frequently Used),置换算法：,该算法在需要淘汰某一页时，首先淘汰到当前时间为止，,被访问次数最少的那一页这只要在页表中,给每一页增设一个访问计数器即可实现,。