页面置换算法.ppt
第四章 存储器管理,4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法,上节回顾,虚拟存储器：定义：P126特征：多次性、对换性、虚拟性 P127请求分页存储管理：硬件支持：页表机制、缺页中断机构、地址变换机构物理块分配策略与算法,4.6.2 内存分配策略和分配算法,1.最小物理块数的确定,2.物理块的分配策略,在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(Fixed Allocation,Local Replacement)2)可变分配全局置换(Variable Allocation,Global Replacement)3)可变分配局部置换(Variable Allocation,Local Replacemen,3.物理块分配算法,1)平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。,2)按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。,3)考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。,4.6.3 调页策略,1.何时调入页面,2.从何处调入页面,在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：,3.页面调入过程页面未在内存时，向CPU发出缺页中断中断处理程序保留CPU环境，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块能容纳新页，启动磁盘I/O将缺页调入内存，修改页表。内存已满，选出准备换出的页面如果此页已被修改，将它写回磁盘把所缺的页调入内存，修改页表中的相应表项，存在位为“1”，并将此页表项写入快表中。形成所要访问数据的物理地址，再去访问内存数据。,4.7 页面置换算法,最佳置换算法先进先出算法LRU算法Clock算法其他算法,页面置换算法的设计目标,具有较低的页面更换频率 换出以后不再访问的页面或者较长时间不再使用的页面,4.7.1 最佳置换算法和先进先出置换算法,1.最佳(Optimal)置换算法Belady于1966年提出的一种理论上的算法，思想是选择的被淘汰页面以后将永不使用，或者在最长（未来）时间内不再被访问。,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。,1.最佳(Optimal)置换算法优缺点,选择被置换的页面将是不再访问的或者较长时间不再使用的优点：可保证最低的缺页率缺点：不可能很真正实现，只可作为其他算法的评价参考特点：“往后看”，看未来，因此不可行,2.先进先出(FIFO)页面置换算法,淘汰最先进入内存的页面，即选择内存驻留时间最长的页面。需要使用替换指针,2.先进先出(FIFO)页面置换算法优缺点,优点：算法简单缺点：性能不佳特点：只看“先后顺序”,4.7.2 最近最久未使用(LRU)置换算法,1.算法描述,选择最近最久未使用的页面。使用访问字段,1.LRU置换算法,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：,1.LRU置换算法优缺点,优点：性能较好缺点：需要较多硬件支持特点：“向前看”，看过去的使用情况,2.LRU置换算法的硬件支持,LRU算法需要的元素1、进程各个页面有多久未被访问2、如何快速找到最近最久未使用的页面,1)移位寄存器1、使用移位寄存器记录某进程在内存中每页的使用情况2、数据格式：R=Rn-1Rn-2Rn-3 R2R1R0 3、页面被访问一次，最高位Rn-1置1，每隔一定时间，寄存器右移一位4、R值最小的页面是被置换页面,某进程具有8个页面时的LRU访问情况,2)栈,1、采用特殊的栈来保存当前使用的各个页面号2、栈顶保留的是最新被访问的页3、栈底保留的是最久未被访问的页，即置换目标,练习,在一个请求分页系统中，假定系统分配给一个进程的内存块数为3，进程的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用最近最久未使用置换算法（LRU），请画图表示访问过程中发生的页面置换过程，并计算缺页次数。（假定开始时，物理块为空，每次调入页面都作为一次缺页处理）,4.7.3 Clock置换算法,1.简单的Clock置换算法,Clock置换算法是LRU算法的近似算法，也称为最近未用算法。在简单的Clock算法中，为每页设置一访问位，当被访问则设置为1，未访问为0。,1.简单的Clock置换算法,1类(A=0,M=0)：最近未被访问，又未被修改，最佳淘汰页。2类(A=0,M=1)：最近未被访问，但已被修改页。3类(A=1,M=0)：最近已被访问，但未被修改。4类(A=1,M=1)：最近已被访问且被修改，最不应淘汰页。,访问位A和修改位M可以组合成下面四种类型的页面,1、从当前指针位置开始扫描循环队列，寻找第1类页面，不改变访问位A。2、第一步失败，寻找第2类页面，将所遇到的第一个这类页面作为淘汰页。将所有扫描过的页面的访问位A都置0。3、第二步也失败，重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。,执行过程可分成以下三步：,改进型Clock置换算法优缺点,优点：减少了磁盘的I/O操作次数缺点：可能需要几轮扫描，增加了系统开销特点：使用两个指标判断，访问位+修改位,练习,已知某进程有4页在内存，页码为0，1，2，3，其A、M位分别为（1，1）（1，1），（0，1），（1，1），当前指针指向2号页，若采用改进型Clock置换算法，选择哪页淘汰？选择完成后，四个页的A、M位分别为多少？,4.7.4 其它置换算法,最少使用(LFU：Least Frequently Used)置换算法对每个页面设置一个字段（移位寄存器），用来记录页面被访问的频率若用移位寄存器实现算法，LFU与LRU的访问图是完全相同的。,2.页面缓冲算法(PBA：Page Buffering Algorithm)采用可变分配和局部置换方式当一个进程换进换出频率很低时，选择页面淘汰，以备其他进程使用被淘汰页面若发生修改，放入已修改链表，否则放入空闲链表,总结,1、LRU算法、Clock算法2、了解各种算法的特点3、作业,
