（计算机软件与理论专业论文）动态自适应页面置换算法awl.pdf

动态白适应页面置换算法a w l 摘要 页面置换算法是操作系统请求页式存储管理中的一个重要组成部分。l r u 算法是页面 置换的一般策略，被“泛用于w i n d o w s ，u n i x ，l i n u x 等多种操作系统。但l r u 算法在某 些情况f 会产生较多的缺页失败，改进l r u 算法，降低缺页失败次数。可以有效地提高系统 性能。本文利用l r u 访问分布图，分析进程页面访问序列对l r u 算法的影响。依据不同的 影响，把页面访问序列划分为三类：l r u 友好页面访问序列、l r u 不友好页面访问序列、 不友好页面访问序列。 在把页面访问序列划分为三类的基础上，本文提出了一种结合动态w f l 算法和l r u 算法的自适应页面置换算法a w l 。并用实验验证在l r u 不友好页面访问序列下，a w l 算 法的缺页失败次数较l r u 算法有大幅度的降低；在l r u 友好页面访问序列和不友好页面 访问序列f ，a w l 算法的缺页失败次数近似于l r u 算法。a w l 算法与其它l r u 改进算法 相比也具有很大的优势。 关键词：页面置换算法，l r u 算法，缺页失败页面访问序列 动态自适席页面置换算法a w l i i a b s t r a c t v i n u a lm e m o r yp a g er e p j a c e m e n ta l g o r i t i sa ni m p o r t a n tc o m p o n e n to fv i r 七u a im e m o r y m a n a g e rl r u j st h ec o m m o np a g er e p l a c e m e n ts t r a t e g r y ，a n di su s e di nw i n d o w s ，u n i x ，l i n u x s y s t e m s b u ti ns o m ec a s e s ，l r ua l g o r i t h mc a u s e sm a n yp a g ef a u i t s ，s oi m p r o v i n gl r up a g e r e p i a c e m e n ta l g or i t h mc a l lr e d u c ep a g ef a u i t s ，a n dt h e r e f o r ei m p r o v et h ep e r f o r m a n c eo ft h e s y s t e m i nt h i sp a p e lw ec l a s s i 母p a g er e f e r e n c es e q u e n c e si n t ol r u - f r i e n d l yp a g er e f e r e n c e s e q u e n c e s ，l r u - u n f r i e n d l yp a g er e f e r e n c es e q u e n c e s ，u n 丹i e n d l yp a g er e f e r e n c es e q u e n c e st h e c l a s s i 行c a t j o nj sb a s e do nt h ea n a l y s i so fp a g er e f e r e n c es e q u e n c e s e f i 色c to nl r u a l g o r i t h mb y u s i n gl r ur e f e r e n c ed i s t r i b u t i o nc h a n w ep r e s e n tap a g ef e p l a c e m e n ta l g o r i t h ma d a p t i n gb e t w e e na d a p t i v ew f la n dl r ua l g o r i 岫s e x p e r i m e n t su s i n g s e v e r a l l r u - u n f r i e n d l yp a g er e f e r e n c es e q u e n c e s s h o wt h a tt i l ea w l a l g o r i t h m i s s u p e r i o rt ol r ua l g o r i t h m ，a n du s i n g s e v e r a ll r u - f r i e n d l y u n f h e n d l yp a g e r e f e r e n c es e q u e n c e ss h o wt h a tt h ea w la l g o r i t h ma p p r ox l m a t e st ol r ua l g o r j t h m a w l a l g o r i t h mi sa l s os u p e n o rt oo _ 【h e rl r ui m p r o v e da l g o r j t h m s k e y w o r d s ：p a g er e p l a c e m e n ta l g o r i t h m s ，l r ua l g o r i t h m ，p a g ef a u l t ，p a g er e f e r e n c es e q u e n c e s 东南大学学位论文 独创性声明及使用授权说明 一、学位论文独创性声明 本人卢明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：遣立赵日期：j 址 二、关于学位论文使用授权说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 签名：霹袅旧影期：中，f z 1 1 研究背景 第一章绪论 随着程序越来越大以及多道程序的并行运行，使得| = 】存紧缺成为不可回避的问题，因此 请求页式的虚拟存储管理思想应运而生。在3 2 位操作系统请求页式虚拟存储管理模式f ， 把系统所拥有的整个内存分割成m 个大小相同的物理块( 在3 2 位l i n u x 24 操作系统上，每 个物理块的火小是4 k ) ，同时为每个进程提供3 g 的虚拟空间用于映射进程代码利数据，该 虚拟空间被分割为n 个和物理块大小相同的页面。在请求分页式系统f 运行进程，不需要将 进程所有页面都装入物理块中，而只需将近期访问的代码和数据页面装入物理块中。为实现 请求分页式系统，通常在系统中设置页表，用米记录各个页面的信息，其中一位表示该页面 是否己装入物理块中。进程运行时，若需要访问某个页面，而该页面没有被装入物理块中， 称之为缺页。缺页引发缺页中断，由缺页中断处理程序负责将所缺页面动态装入物理块中。 如果在动态装入时，无空闲物理块，则需进行页面置换。页面置换算法依据一定的策略，把 在物理块中的某个页面置换山去，从而在空出一个物理块后，装入导致缺页失败的页面。 对页面映射的数学抽象”1 ：集合= 1 ，h ) 表示所有访问页面，集合m = 1 ，珑 表 示可供分配的物理块，1 i m i i | 。函数i 厂：寸吖表示从页面到物理块的映射，定义 如下： 朋，= 失败鬣裟娄； 其中f ，m 。 1 2 论文研究范畴 本文分析了5 种简单页面置换算法，剖析了l r u 算法被广泛应用的原因，同时分析了 4 种l r u 改进算法。利用8 个程序页面访问序列的l r u 分布图对l r u 算法进行详细分析， 依据不同的影响，把页面访问序列划分为三类：l r u 友好页面访问序列、l r u 不友好页面 访问序列、不友好页面访问序列。归纳出页面访问序列中出现的访问模式：当时性、顺序性 以及循环性页面访问模式。比较出l r u 算法适用丁当时性页面访问模式，m r u 算法适用丁 顺序性和循环性页面访问模式。进而推断山l r u 算法存在的不足在丁它只能适应当时性访 问模式，而对于其它不同页面访问模式没有普遍适应性。由于对l r u - 不友好页面访问序列 在不同阶段具有的不同页面访问模式采用单一的页面置换策略，导致产生较多的缺页失败。 在此基础上，本文提出一个结合动态w f l 算法和l r u 算法的自适麻页面置换算法 a w l ，该算法依据程序运行时不同阶段表现的不同页面访问模式，有选择地采用适用于不 同页面访问模式的e 置换点变化的动态w f l 算法或l r u 算法。对a w l 算法进行实验检测， 在l r u 一不友好页面访问序列r ，与l r u 算法相比，缺页失败数有大幅度的降低。在l r u 动态自适应页面置换算法a w l 2 友盘，和不友鲥页面访问序列下，缺页失败数与l r u 算法大致相等。a w l 算法与其它l r u 改进算法相比也具有很人的优势。 1 3 论述序列 本文以r 各章节组织如下： 第一章分析了5 种简单页面置换算法，剖析了l r u 算法被广泛应用的原因，最后分析了4 种l r u 改进算法。 第二章利爿j8 个程序页面访问序列的l r u 访问分布图对l r u 算法进行分析。依据对l r u 算法不同的影响，把页面访问序列划分为l r u 友好页面访问序列、l r u 不友好页面 访问序列、不友好页面访问序列。归纳出页面访问序列中出现的访问模式：当时性、 顺序性以及循环性页面访问模式。比较出l r u 算法适用于当时性页面访问模式；m r u 算法适用丁顺序性或循环性页面访问模式。 第四章提出一个结合动态w f l 算法和l r u 算法的自适应页面置换算法a w l 。 第五章对a w l 算法使用“跟踪驱动”的方法进行实验测试，并与l r u 和其它l r u 改进 算法进行比较。 第六章总结所做工作，指出未解决的问题和有待改进之处，并对未来研究工作做出展望。 2 第二章页面置换算法的分析 本章分析了5 种简单页面置换算法，剖析了l r u 算法被广泛应用的原因，最后分析了 4 种l r u 改进算法。 2 1 页面置换算法的概念 当进程运行时，访问某个页面导致缺页失败且内存中无空闲物理块，则需进行页面置换。 页面置换算法依据一定的策略，把在物理块中的某个页面置换出去，从而在空出一个物理块 后，装入导致缺页失败的页面。我们把进程运行时访问页面的次序称为页面访问序列。 对页面置换算法的数学抽象“j ： 假设= 1 ，” 表示所有访问页面，m = 1 ，m 表示可供分配的物理块， 1 兰l m l i l 。表示k 度为女的所有页面访问序列，女o 。国= l 表示一个 k 度为r 的页面访问序列，如果r = x ，则表示在页面访问序列上第f 个位置访问的页面是 x ，称在f 时间访问页面x 。s 表示物理块中页面集合，削州。表示集合 p l s e j 且蚓m ) ，蚓表示集合s 包含元素的数目。 定义1 ： 给定 彳和，爿= ( q ，吼，g ) 表示页面置换算法。 ( 1 ) q 表示物理块中页面状态 ( 2 ) 吼表示初始状态 ( 3 ) g ：m 。q 斗m 。q 表示页面置换过程 g ，g ，x ) = 07 ，g7 ) 表示在访问页面x 后，页面x 在s 7 中。 定义2 ： 给定页面访问序列珊= _ l ，页面置换算法彳从初始状态最开始处理页面访问 序列国，过程舾，g ，) 髭。， e ，g 。) = g b 一。，g 。)( 1 r r ) 。 4第二章页面置换算法的分析 如果访问的页面萑s h ，在r 时间产生缺页失败，物理块中页面变化过程如下所示 s t = s l l u x i y t 。 其中z ，至一s 。，r s f _ 1 ，x ，表示置换进的页面，表示置换出去的页面。 定义3 ： s 表示在r 时物理块中的页面。 s ? 表示具有m 个物理块。 s + x 表示s u 扛 ，当x 区s 。 s x 表示s 一缸 ，当x s 。 守义4 ： f p ，g7 ) g ( s ，g ，x ) = p + 砌”) + x 一儿g “) 当蚓 m 时，不需要置换页面直到物理块都被占用。 2 2 简单页面置换算法的分析 2 2 10 p t 算法 女口果z s ， 如果x 崔s 且l s l m ， 如果x 仨s ，l s l = 埘且s o p t 是o p t i m a l 的缩写。当发生缺页失败时，o p t 算法把在物理块中将来最长时间才被 用到的页面置换出去。 已知页面访问序列国= l _ ，把下次访问时间f 0 ，) 为最大的页面y 置换出去。 状态为，( o 蔓，s r ) 。当蚓= 埘时，o p t 算法数学模型如_ f 所示： ) ：黪“) 【p + l “ 如果l “s y ，f + 1 ) 女口果“芒s 其中y s 且对另外的x ，f o ，f ) r g ，f ) 。其中f g ，f ) 表示在时间r 访问页面x 后，下次 访问x 的时间，如果x 在时间f 后不会被访问，则f g ，f ) = r r + 1 。 4 动态自适应贞面置换算法a w l o p t 算法把在物理块中将米最长时间才被用到的页面置换出去，它需要知道将来的页 面访问序列，是一种。昏l i n e 算法。给定页面访问序列和物理块数，o p t 算法的缺页失败次 数最少，它是虽优的页面置换算法。但是，由于它需要知道将来的页面访问序列，不能在真 实的系统中被实现。但o p t 算法可以作为标准衡量其它页面置换算法的优劣。o p t 算法的 另一个性质是当给定一个页面访问序列，物理块数逐渐减少时，o p t 算法的缺页失败数也 随之减少。以物理块数为x 轴，缺页失败数为y 轴，如果某个o n 1 i n e 算法的缺页失败曲线 靠近o p t 算法的缺页失败曲线，我们可以认为该算法是较优的。另一方面，o p t 算法为实 现较优的o n 1 i n e 页面置换算法提供了依据：即需要把在物理块中将来最长时间才被用到的 页面置换山去。 2 2 2f i f o 算法 f i f o 是f i r s ti nf i r s to u t 的缩写，f i f o 算法把最早装入物理块的页面置换山去。 q = ”表示物理块中页面集台，g = r 一，) 表示一个按照进入物理块顺序排列 的页面队列，其中蚓= m 。f 工f o 算法数学模型”1 如下所示： g 挑 ) = 般吨) 嚣警嚣 其中g7 = g ，y 。，y ：，y 。一i ) 。 2 2 3l r u 算法 l r u 是l ，e a s tr e c e n t l yu s e d 的缩写，l r u 算法把在物理块中过去最长时司未被用到 页面置换出去。 g = 0 r 一，) 表示按照最后一次访问顺序排列的页面队列。l r u 算法数学模型“1 如下 所示： g 。 ，g ，z ，= 警；! ) - y 。，。) ：；羹：i ； 当x s 且x = y 女时g7 = b ，y l ，y 一l - ，y 十l ，一，y ，) 。 当x 仨s时， g “= g ，y l 一，。一。) 。 l r u 算法是一种o n 1 i n e 页面置换算法，它假定在过去最久未用到的页面在将来最长 时间才被用到，当发生缺页失败时，把在物理块中过去最久未用到的页面置换出去。l r u 算法依据o p t 算法为实现较优的。昏1 i n e 页面置换算法提供的依据，把推测出的将来最k 时 间才被州到页面置换出去。l r u 算法所需要的置换信息是物理块中页面最后一次访问的顺 序，它把在物理块中最屙一次最早被访问的页面置换山去。 第二章页面置换算法的分析 2 2 4m r u 算法 m r u 是m o s tr e c e m l yu s e d 的缩写。m r u 算法”1 把在物理块中晟近访问的的页面置换 出去。 q = r - - ，y 。) 表示按照最后一次访问顺序排列的页面队列。m r u 算法数学模型如下所 示： g 。嘶小蕊池姆1 罴嚣 当x s 且x = y t 时g7 = 0 ，y 】，一，y 一l - ，y “，一，y 。) 。当z 盛s 时，g ”= g ，y 2 一，y 。) 。 2 2 5l f u 算法 l f u 是l e a s tf r e q u e n t l yu s e d 的缩写。l f u 算法【s 1 【6 1 把在物理块中最近一段时间使用次 数最少的页面置换出去。 g = ? ，：) 表示按照在最近一段时间内访问次数多少排列的页面队列。其中成表 示y 。这个页面在最近一段时间内访问的次数是f 。l f u 算法数学模型如f 所示 踟息) ：黔7 ) 岭+ x 女口果x s y ，”，g “) 女口果工仨s 当x s 且x = “时q7 = f ，y f l ，y ：) 。当x g s 时，g “= g 1 ，y ：，y ：) 。且每隔一 段时间g = 抄：，y ：，j 要被清为g = b ? ，y ：j 。 l f u 算法假定在最近一段时间内经常被访问的页面与不经常被访问的页面相比，更有 可能在不远的将来被访问，因而把在最近一段时间i ，i j 不经常被访问的页面置换出去。与l r u 算法相比，l f u 页面置换算法能区分访问频率较低的页面与访问频率较高的页面，把访问频 率较高的页面保留在物理块中，而把访问频率较低的页面置换出去，从而使得访问频率较高 的页面占据的物理块数较多，访问频率中等的页面占据的物理块数较少，而访问频率较低 的页面占据的物理块数极少，有利于页面访问的总体优化，但不适应页面访问的变化。 2 3l r u 算法的应用 使用竞争分析模型7 1 测试页面置换算法是否优越，给定物理块数，对于任何页面访问 序列，如果一个页面置换算法导致的缺页失败次数最多是o p t 算法的c 倍，称该算法的竞 争率为c 。对任意的0 n 1 i n e 页面置换算法，最好的竞争率只能为n ，其中n 为给定的物理块 数。在这篇文章中同时证明了l r u 算法和f i f o 算法的竞争率都为n 。由于是假定的任意页 面访问序列，因而这只是理论上的竞争率”。而在进程实际运行时，页面访问序列会表现出 动态自适麻页面置换算法a w l 一定的规律性”。例如，页面访问序列的当时性规律“”“”“”1 ，即当前访问的页面在最 近的将来会被经常访问到。l r u 算法只需知道在物理块中页面最后一次访问顺序的信息，然 后根据该信息把最久未被访问到的页面置换出去，很好地适应了页面访问序列的当时f 生规 律。为页面访问当时性建立页面关系模型【1 “，对l r u 算法进行分析，结论是l r u 算法的 缺页火败数远小于n 倍o p t 算法的缺页失败数mj 。与f i f o 算法相比，l r u 算法具有较为 明显的优势。但由于l r u 算法每访问一次页面都需要更新页面访问顺序，系统开销很大所 以现代操作系统的请求页式存储管理系统普遍采用近似l r u 算法作为页面置换策略。 u n i x 系统i j ”的页面置换算法采用近似l r u 的算法。u n l x 系统为每个进程提供3 g 的 虚拟空间用于映射进程代码和数据，该虚拟空间被分割成n 个和物理块大小相同的页面，可 将它们分配到不同的物理块中。同时在内核空间中设置一张页表，在页表的每个表项中，记 录每个页面与物理块之间的映射关系。为了支持页面置换，在页表项中设置一个年龄字段， 用来指示该页在物理块中已有多久时间未被访问到。u n i x 中页面置换算法决定哪个页面被 置换山去的策略如f 所示： ( 1 ) 每隔一段时间对物理块中的所有有效页的年龄加l ， ( 2 ) 当有效页的年龄达到规定值斤便将它换出。 w i n d o w s2 0 0 0 系统的页面置换算法更接近丁l r u 算法。w i n d o w s2 0 0 0 为每个进程分 配一定数量的物理块，称为“进程_ l = 作集”，当进程j 二作集达到它的上限，或者由于有其他进 程对物理块的请求而需要对工作集进行动态调整时，虚拟存储管理器从进程工作集中移出页 面直到确认该进程还有足够的物理块。 l j n u x 系统采用l r u 算法的另一种近似算法，n u r 算法，n u r 是n e v e ru s e d 丹e q u e n t l y 的简写，即最近没有使用页面置换算法。当发生缺页失败时，把最近一个时期内 未被访问的页面中任选一个页面置换出去。该算法通过在页表中增设一个访问位实现。当某 页被访问时，访问位置1 。否则，访问位置o 。系统周期性的对所有访问位清零。l l n u x 的 页面置换上：作由守护进程k s w a p d 来完成。这个进程由内核的i n i t 进程在系统启动时运行，被 定时器周期性调用。当定时器时间到后，k s w a p d 进程依据f r e e p a g e s 变量的两个域打e ep a g e s j o w 和n p a g e sh i 曲判断系统的空闲物理块数是不是太少，如果当前系统的空闲块数小 于f r e ep a g e sh i 曲，就要把一些页面置换出去；如果小于f r e ep a g e sl o w ，k s w a p d 进程不仅 要置换出部分页面，还要将睡眠时间减为平时的一半，而在空闲块数人于f 把ep a g e si o w 时 睡眠时间义会恢复。具体页面置换由函数d ot r yt of r e ep a g e s ( 见1 i n u “m m m s c a n m ) 完成。 d ot r yt of r e ep a g e s 函数首先会调用k m e mc a c h er e 印来减少内核c a c h e 中不用的空闲物理 块然后循环采用下列三种方法释放页面，： ( 1 ) 减少缓冲和页面c a c h e 的大小，这主要是通过调用函数s h r j n km m a p ( 见l i n u ) ( m m f i l e m a p c ) 来实现，这部分采用n u r 置换算法。 ( 2 ) 减少共享页面数，这主要是通过调用函数s h ms 、v a p ( 见l i n u x i p c s h m c ) 来实现，这 部分也采用n u r 页面置换算法。 ( 3 ) 换出或者丢弃页面，这主要是通过调用函数s w 印o u t ( 见l i n u “m m v m s c a l l c ) 来实现，这 部分也采用n u r 页面置换算法。 虽然l r u 页面置换算法已经被广泛采用，在实际使用中表现也很好。但在某些页面访 问序列下，l r u 算法会导致很多的缺页失败，如页面访问序列l ，2 ，3 ，4 ，l ，2 ，3 ，4 ，l ，2 ，3 ，4 ， 物理块只有3 个，在这种情况下，l r u 算法会导致访问的页面全部失败，而采用m r u 算法能 减少一、r 的缺页失败数。l r u 算法偏离m r u 算法甚远，且该页面访问序列表现出很强的规律 性，可以对l r u 算法进行改进。由于磁盘存储器存储性能比内存差好几个数量级。而每发生 一次缺页失败，系统都需要在磁盘和内存之间进行页面交换，使得系统处理缺页失败的代价 非常高。而现代操作系统中j 、泛采用的是l r u 页面置换算法的近似算法，通过改进l r u 算 7 第二章页面置换算法的分析 法，降低缺页失败次数将会显著提高系统的性能。 2 4l r u 改进算法的分析 l r u 页面置换算法存在的不足在于它对不同类型的程序采用相同的页面置换策略，而 忽视了程序在运行时具有不同页面访问模式的情形1 4 j 。对某个特定的页面访问模式最好能选 用一个使系统缺页次数较少的较优的页面置换策略，这样系统缺页失败数能有效降低，整个 系统的性能会有很大提高。 由于现代操作系统请求页式存储管理普遍采用近似l r u 算法作为页面置换策略，但 l r u 算法依据在物理块中所有页面最后一次的访问顺序把最后一次最早访问的页面置换出 去，依据过去页面访问的信息太过简单2 1 脾】【2 3 】1 2 4 】，在某些进程的页面访问序列下，l r u 算法的缺页失败数较多。例如：在一个循环中访问的不同页面数超过物理块数时，l r u 算 法表现得很差。于是对l r u 页面_ 置换算法的改进算法被不断的提出。 2 4 1s e q 算法 s e q 是s e q u e n c eq u e r y 的缩写，s e q 算法1 4 1 是一种基于探测的页面置换算法。它的基本 思想是在没有检测到按照虚拟地址顺序产生的缺页失败队列时，采用l r u 算法。而一旦检 测到发生了按照虚拟地址顺序产生的缺页失败队列时，s e 0 算法就应用m r u 算法丁该缺页 失败队列。在一个按照虚拟地址顺序循环访问的不同页面数超过物理块数的页面访问序列 f ，l r u 算法产生的缺页失败很多，而采用s e o 算法屙，缺页失败数可以有大幅度的降低 ”j 。而在其余页面访问序列f ，s e q 算法采用l r u 算法。s e o 算法的缺点：首先在于不能 检测到不以虚拟地址顺序对不同页面数超过物理块数的循环访问，例如，通过指针对多个不 同页面的循环访问。对在一个循环中访问的不同页面数超过物理块数这一类问题，s e q 算 法缺乏普遍性的解决这类问题的能力，它只能解决这类问题中的依据虚拟地址顺序排列产生 的不同页面数超过物理块数循环缺页失败问题。对另外不利于l r u 算法的页面访问模式， s e q 就更没有能力检测得到，也就无法应用在该页面访问模式下表现较好的页面置换算法。 2 4 2e e l r u 算法 e e l r u 是e a r l ye v i c t i o nl e a s tr e c e n t l yu s e d 的缩写，e e l r u 算法【2 4 】也是一种基于探 测的页面置换算法。它的思想可以根据下面两幅图( 图2 1 ，2 2 ) 来说明： 1 em 物理块 图2 1e e l r u 算法图解l 动态自适应页面置换算法a w l 9 1 e呐 1 口工工 口 皿口口口口 口 口 物理块 图2 2 e e l r u 算法图解2 图中方框表示物理块，m 表示物理块数，横线表示l r u 访问位置，竖线表示在各个 l r u 位置上的页面访问数。当一个进程在运行时，表现出如图2 1 ，2 - 2 所示，在l r u 各个 位置上的页面访问数，其中靠近位置m 斤的页面访问数很多，而在位置e 附近的页面访问 数很少。采用l r u 算法，如幽2 1 所示，对丁位置m 后的页面访问都将导致缺页失败，而 位置靠近m 后的页面访问数很多，产生的缺页失败次数会较多，l r u 算法表现很不好。而 e e l r u 算法并不把m 处的页面置换出去，而是有选择的置换e 位置或l 位置的页面，把位 置m 后的较多页面保留在物理块中，出现如图2 2 所示的结果，可以大幅度减少缺页失败 数。e e l r u 算法的策略如下所示： 给定几组p 。和，设在一段时间，内，p 。到m 之间的页面访问数为p 纱，p 。到，之间 的页面访问总数为删，朋删算法辉删，( 等卜咖。为最大的一双和 为帅懈换始髁所有的删，( 等 一”啊螂燃删 算法。采用e e l r u 算法，每次访问页面，都需要判断这次页面访问是在p 到m ，还是在m 到，中，导致e e l r u 的开销很大，很难在一个系统中被真正实现。 2 4 3t n r p 算法 n 4 r p 是t i m eo f n e x tr e f e r e n c ep r e d i c t o r 的缩写。t n r p 算法的思想是预测在物理块中 每个页面f 一次被访问的时间，把预测得到的下一次访问时间最长的页面置换出去。t n r p 算法的策略如下所示： 定义页面p 最后一次访问的时间是以( p ) ，同时定义p 最后一次与前一次访问的时间 间隔j 护0 ) 。举例：对页面访问序列1 ，4 ，l ，6 ，l ，l ，4 ，4 ，6 ，6 的分析，在此把对相 同页面的连续访问作为一个时间计数。 时间：0 123456 访问页面：14 16 14 6 时间间隔：? ? 27 243 9 o 第二章页面置换算法的分析 给时间间隔j 护) 一定的误莘肋，则刚r p 算法预测页面f 一次的时间间隔是： 盯r ) 一5 ：d s 打乙什0 ) s 驴0 ) + | s ! d 。 t n r p 算法预测页面下一次被访问的时间是 p m ，0 ) = 肼) + j 护0 ) 。 当发生缺页失败需要空闲物理块时，t n r p 算法把在物理块中p m ，0 ) 最火的页面置换出去。 t n r p 算法只对文件缓存页面预测的较好，而对进程页面访问序列预测的并不好，不能 作为进程页面访问序列的页面置换算法。同时由于每次访问页面，t n r p 算法都需要更新该 页面的f 扫( 力和期 p ) ，导致实现t n r p 算法的开销很人，很难在一个系统中被真正实现。 2 4 4a p t 算法 给定一个页面访问序列，页面置换算法a ，页面置换算法b ，动态自适应页面置换算法 a b ”按照如下规则置换页面： 当访问某个页面时，如果算法a 产生缺页失败而算法b 没有产生缺页失败，则从算法a b 的物理块中换山一个不在算法b 物理块中的页面，并称算法a b 处于b 状态。否则，称算法a b 处于a 状态，并判断算法a b 物理块中的页面是否有不在算法a 物理块中，如果有，则把这一 个页面置换出去；否则置换a 算法要置换的页面。 动态自适应页面置换算法a b ，对任何页面访问序列，产生的缺页失败次数最多只是单 独使用算法a 或b 缺页失败次数的两倍。 单纯的动态自适应页面置换算法规则并没有体现出算法a 和算法b 的优势，需耍对动态 白适应页面置换算法规则作进一步的改进口“，设定参数s 表示状态变化阶段，动态自适应页 面置换算法a ，b 统计最近一个阶段a 算法产生的缺页火败数和b 算法产生的缺页失败数，如 果a ，算法产生的缺页火败数加上b 算法产生的缺页火败数大于s 时，认为算法a ，b 需要重新 选择页面置换策略，再比较a ，算法产生的缺页失败数是否小了= b 算法产生的缺页失败数，如 果是小于，则页面访问模式在最近一个阶段处于a ，算法适应的模式r 。如果是大于，则页面 访问模式在最近一个阶段处于b 算法适应的模式下。如果是等于，则页面访问模式与前一个 模式相同。依据进程页面访问序列的模式具有一定的连续性，假定r 一阶段的模式与最近阶 段的模式相同，丁是为下一阶段选择适应最近阶段模式的算法a 或b 。依据改进规则作山的 动态自适应置换算法a ，b 产生的缺页失败数最多只是单独使用算法a ，或b 缺页火败数的三 倍。 动态白适应算法a b 算法对算法a 和b 没有要求，只需有为实现算法a 和b 所需的置换 信息。动态自适庶规则还可被递归应用，即动态自适应算法a b 可以作为另一个动态自适应 算法( a b ，) c 的a ”部分。y a n n j s 具体实现了一个顺序结合m r u ，l f u ，s e q ，l r u 算法的 a p t 算法【2 6 】。 动态自适应算法通过比较a ，算法和b 算法在虽近阶段缺页失败数，从而为下一阶段选择 在最近阶段缺页火败数少的算法a 或b 。它主要的缺点是滞后性，即如果页面访问模式发生 了转变，动态自适应算法无法立即重新选择较好的算法，还得过一阶段才能重新选择较优的 算法。动态自适应算法结合的算法越多，滞后性就越大。 0 动态自适应页面置换算法a w l 2 5 小结 本章介绍了5 种简单页面置换算法的数学模型，对5 种简单页面置换算法进行了分析。 剖析了l r u 算法被广泛应用的原因。并对现今提山的l r u 改进算法s e o ，e e l r u ， t n r p ，a p t 算法进行了分析。这些算法都是依据过去页面访问信息预测将米可能的页面访 问行为，从而决定将某个页面从物理块中置换出去。这些算法都不同程度地对在某些页面访 问序列下，l r u 算法表现较著时作了一些改进。但s e 0 ，e e l r u ，t n r p 页面置换算法各 自有着不同的缺点，s e q 算法只能检测以虚拟地址顺序对不同页面数超过物理块数循环访 问的模式。e e l r u 算法的开销较大，很难在一个系统中被真正实现。仆承p 算法不能作为 进程页面的置换算法。动态自适应页面置换算法a p t 依据不同的页面访问模式灵活地选择 算法a 或b ，能有效地降低缺页失败次数。动态白适应页面置换算法a p t 依据算法a 和b 的缺页失败信息选择算法a 或b 的规则非常简单。同时由于所需要的信息是a 和b 缺页失 败信息，而缺页欠败的次数与整个页面访问序列数相比是非常稀少的，a p t 算法的开销很 小。它主要的缺点是滞后性，即如果页面访问模式发生了转变，动态白适应算法无法立即重 新选择较好的算法，还得过一阶段才能重新选择较优的算法。动态自适应算法结合的算法越 多，滞后性就越大。 本文对l r u 页面_ 置换算法的改进依据动态自适应页面置换算法a p t 的思想进行，在下 一章中利用8 个程序页面访问序列的l r u 访问分布图对l r u 算法进行分析，依据对l r u 算法不同的影响，把页面访问序列划分为l r u 友好页面访问序列、l r u 不友好页面访问序 列、不友好页面访问序列。归纳出三种不同页面访问模式：当时性、顺序性和循环性页面访 问模式。比较山l r u 算法适应当时性页面访问模式，m r u 算法适应顺序性及循环性页面访 问模式。在此基础上，本文提出了一个适应顺序性、循环性和当时性页面访问模式的动态自 适应页面置换算法a w l 。 第三章页面访问序列性态分析 本章利削8 个程序页面访问序列的l r u 访问分布图对l r u 算法进行分析，依据对l r u 算法不同的影响，把页面访问序列划分为l r u 友好页面访问序列，l r u 一不友好页面访问序 列，不友好页面访问序列。归纳出三种不同页面访问模式：当时性，顺序性及循环性页面访 问模式。比较出l r u 算法适应当时性页面访问模式，m r u 算法适应顺序性及循环性页面访 问模式。 3 1 页面访问间隔数 对页面访问间隔数的定义：在程序运行时第k 次访问页面p ，访问n 个不同的页面后( 包 括它自己) 第k + 1 次访问这个页面p ，称n 为p 页面第k 次的访问间隔数。如果是最后一次 访问页面p ，则设定该页面最后一次的访问间隔数是m + 1 ，其中m 是总的访问页面数。使用 l r u 页面置换算法，在p 页面两次访问期间，如果程序访问的不同页面数n 超过物理块数m 时，则该页面在第二次访问之前会被置换出去，而如果某个页面两次访问期间，程序访问的 不同页面数n 不超过物理块数m 时，则该页面会被保留在物理块中。给定一个页面访问序列， 使用l r u 算法，可以利用页面访问间隔数判断下次访问该页面是否会导致缺页火败。例：页 面访问序列是1 ，2 ，3 ，4 ，l ，2 ，3 ，4 ，2 。l ，3 4 ，物理块数3 ，在该页面访问序列下， 第一次访问1 ，2 ，3 ，4 页面的访问间隔数都是4 ，由于4 人于3 ，所以第一次访问l ，2 ，3 ， 4 ，都会被置换出去，缺页失败数为4 。第二次访问1 ，2 ，3 ，4 ，访问间隔数分别是4 ，3 ， 4 ，4 。l ，3 ，4 会被置换出去，2 保留在物理块中，缺页失败数为3 。第三次访问2 ，l ，3 ，4 ，2 ，l ，3 ，4 的访问间隔数都是4 + l ，缺页失败数为4 。在该页面访问序列下，当物理块数为3 时，l r u 算法产生的缺页失败数是1 l 。 3 2l r u 访问分布图 页面访问序列l r u 访问分布幽中每个点的x 坐标表示页面访问间隔数，y 坐标表示页面 访问序列位置。依据访问间隔数的作用，利用页面访问序列的l r u 访问分布图可以直观分析 页面访问序列对l r u 算法的影响。我们取6 个工作集较大，1 个工作集较小，1 个工作集 极小的页面访问序列作为样本，分析页面访问序列对l r u 算法的影响。8 个程序的详细信 息见表3 1 。 表3 18 个程序信息一览表 程序名 程序介绍总访问页面数 印p l u 计算偏微分的程序 3 6 3 1 g n u p l o t 绘制图表的程序 1 5 6 2 9 m 8 8 k s i m 微处理器模拟器 4 8 3 8 m u r p h i 协议校验者2 3 4 5 t r y 殍s l矩阵运算程序 1 7 4 2 2 w a v e 5 等离子模拟器7 1 7 5 c c l g c c 编译器核心 7 1 6 g r o b n e o 公式转换程序 6 7 2 动态白适应页面置换算法a w l 进稗运行时，页面访问次数非常多，仅仅储存它，就要占用巨火空间口7 j j 。需要使用 o l r 压缩算法”对上面8 个进程的页面访问序列进行压缩，这不影响8 个页面访问序列的 l r u 访问分布图。 l r u 访问分布图中横轴表示页面访问间隔数，纵轴表示页面访问序列位置。依据访问 间隔数的作用，利用页面访问序列的l r u 访问分布图可以直观分析页面访问序歹对l r u 算法 的影响。通过分析，把页面访问序列划分为对l r u 算法有不同影响的三类： 第一类，c c l ( 图3 一1 ) ，g r o b n e r ( 图3 2 ) 的页面访问序列就属于这一类型。程序运行 时，页面访问序列会表现出当时性”o “”“，即当前访问的页面在最近的页面访问序 列中会被经常访问到，称这种情况为当时陛页面访问模式。如果在整个页面访问序列中，大 部分页面访问间隔数都分布在靠近y 轴附近较小范围内，称这种情况为强当时性页面访问模 式。我们把这样的页面访问序列称之为l r u 一友好页面访问序列。在这类页面访问序列下， 给定一定的物理块数，l r u 算法的缺页失败数较少。 第二类以g n u p l o t ( 图3 3 ) 的页面访问序列为典型代表，t r y g t s l ( 图3 4 ) 、w a v e 5 ( 图 3 5 ) 和a p p l u ( 图3 6 ) 的页面访问序列也属于该类。在这一类页面访问序列下，很火一部 分的页面访问间隔数较大，但分布的范围非常集中，例如：g n u p l o t 页面的访问间隔数集中 在o 一4 0 0 之间以及1 5 0 0 0 两个范围附近，而在其它范围几乎没有。在g n u p l o t 页面访问序列 r ，l r u 算法的缺页失败数远超过m r u 算法的缺页失败数，需要对l r u 算法进行改进。我们 把这样的页面访问序列称之为l r u 一不友好页面访问序列。对很多不同页面的顺序访问和循 环访问都属于l r u 一不友好页面访问序列。 如果突然访问大量的只被访问一次的页面，例如，多媒体处理类程序就会对一个大文件 进行顺序访问”。在这类访问序列r ，使用l r u 算法，会把对人文件顺序访问后要访问的页 面置换山去，而在物理块中保留大文件的内容，而这些内容以后不会被访问到。在该页面访 问序列f ，采用m r u 算法，当产生缺页失败时，它把在物理块中最近访问的的页面置换出 去。m r u 算法把包含大文件内容的页面置换出去，而在物理块中保留顺序访问大文件后要 访问的页面，m r u 算法的缺页失败数与l r u 算法相比少很多。称这种页面访问情形为顺序性 页面访问模式。 对很多不同页面的循环访问，g n u p l o t 的l r u 访问分布图( 图3 3 ) 就表现山这样一种 情形，对大约1 5 0 0 0 个不同页面有3 次循环访问。在这种情形f ，由于很大一部分页面访问 间隔数较人，当给定物理块数小丁页面访问间隔数时，采用l r u 置换算法，会导致很多缺页 火败。半个简化的例子，页面访问序列是l ，2 ，3 ，4 ，l ，2 ，3 ，4 ，l ，2 ，3 ，4 ，物理块数是3 ，在该 页面访问序列下，采用l r u 置换算法，所有页面都导致缺页火败。所有页面都导致缺页失败 的原因是由丁l r u 算法假定晟久未访问的页面在将来最比时间才会被访问，而在该序列下， 刚好相反，晟久未访问到的页面在将来最短时间就会被访问到，导致l r u 算法远离o p t 算法。 l r u 算法不适用于这种页面访问序列，而如果使用的m r u 页面置换算法，即把物理块中最近 访问的页面置换出去，反而能更接近o p t 算法。同时在这种页面访问序列下，增加物理块数， l r u 算法的缺页失败次数并不随着物理块数的增加而降低，直到物理块数增加到大于页面访 问间隔数时l r u 算法的缺页失败次数才会有一个人幅度的降低。而对o p t 算法，随着物理 块的增加，缺页火败次数会逐渐降低。称这种页面访问情形为循环性页面访问模式。 第三类，这一类以m 8 8 k s i m 的和m u r p h i ( 幽3 7 ，3 8 ) 的页面访问序列为代表。如果在 某个页面访问序列下，页面访问间隔数范围分布广泛，且