请求分页式系统设计的性能保证

刘铁武,李 峰

(湖南工程学院计算机与通信学院,湘潭 411104)

请求分页式系统设计的性能保证

刘铁武,李 峰

(湖南工程学院计算机与通信学院,湘潭 411104)

请求分页式是当今应用最为广泛的虚拟存储技术.要保证其获得良好的性能,仅关心页面置换算法是不够的,还必须关注诸如存储器分配策略、页面大小、程序结构等多个方面.请求分页式系统的理论依据是局部性原理,在此基础上,结合已有研究成果,从设计者和应用者的角度着重就其中几个因素进行了讨论和研究,力求在理论上得出一般性的结论.

请求分页;性能;颠簸;全局分配

操作系统中管理分层存储器体系的存储管理器的任务是有效地管理内存,即记录当前哪些内存正被使用,哪些内存是空闲的;对进程的内存需求进行分配和回收.限于物理内存,使用重叠与动态绑定,虽可在程序执行时不需要将整个程序都加载,但在存储管理器的设计中会增加很多额外工作,亦会造成维护与扩展困难.当前主流操作系统广泛采用支持多道程序的虚拟存储技术,有请求分页式、请求分段式和段页式等,市场份额最大的是请求分页式.

请求分页式技术的要点是仅调入每个进程的一部分页.1968年P.Denning提出的局部性原理指出,程序在执行时将呈现时间局限性和空间局限性.亦即,大多时候,将要执行的页可预知,这为虚拟存储技术的实现提供了理论依据.另一方面,由于仅调入部分页,实际执行时必定产生缺页,缺页处理的效率实质上就是存储管理器的性能,可用有效访问时间T衡量.

其中,p是缺页率,m是内存访问时间,d是磁盘访问时间.硬件特性决定,m和d是不同数量级的,m＜＜d可知,有效访问时间正比于缺页率,降低缺页率是提高性能的关键.反之,将增加有效访问时间,大幅延迟进程的处理时间.

页面置换算法是决定缺页率大小的机制,正因为不是所有将要执行的页面都可预知,所以任何一个实用置换算法并不能保证缺页率达到理论最小,这就为人们研究置换算法提供了空间,人们已研究出许多不同目标函数的置换算法.

实质上,决定缺页率大小的除了置换算法还有其它诸多因素,它们是操作系统设计者必须考虑的,本文从页面、物理块的分配、页面调入与清除策略、负载控制、程序的结构等方面进行了研究和讨论,从理论和实践上得出了其一般性结论.

1 页 面

面的大小应适当;应支持页面共享.

1.1 页面的大小

最佳页面的大小是由几个互相矛盾的因素决定的,故不存在全局最优.一方面,对于任一进程,其正文段、数据段和堆栈段不恰好装满页面,平均情形下,有一半是空的,所以选择小页面内部碎片较小.但另一方面,页面小意味着需要更多的页面,所需要的页表项更多,页表也更长;并且与外存交换页面的次数相对更多,因为每次内外存交换大部分时间用于寻道和旋转延迟,所以时间开销更大.下面的数学分析可得出理论上的页面最佳值.

设进程的平均大小为s字节,页面大小为p字节,每页表项占e字节,k为总开销,则 k=se/p+p/2

我父亲说，从前——几世纪还是几年以前——巴比伦的彩票是带有平民性质的赌博。他说（我不知道是否真实），理发师发售彩票，收的是铜币，给的是绘有符号的长方形骨片或羊皮纸。大白天抽签开彩：中彩的人凭票领取银币。显而易见，手续非常简单。

对p一阶求导,令右边等于0得极值

现在CPU速度越来越快,为减少外存访问次数,采用较大的分页可能是更好的选择.

1.2 页面共享

多道系统中,不同的用户运行同一程序是很常见的.显然,在内存中保存多个副本不是好方法,页面共享效率更高.但并非所有的页面都适合共享,如只读的页面可共享而数据页面却不需要共享.

共享的实现方法可多种,PDP-11就是一范本.其主要思想是将指令空间和数据空间分离,多个进程使用相同的指令空间页表和不同的数据空间页表以实现共享.

2 物理块的分配

2.1 最少物理块数

保证进程能运行的最少物理块数目是由CPU的结构和指令的结构所决定的.指令由操作码和操作数构成.一般的微计算机的指令的存储位不超过8位,但某些功能强大的计算机其指令超过256,亦即指令存储位可能是2个甚至更多的字节,则指令本身可能跨越2个页面.而一条指令又可以有多个操作数(如0,1,2,3等),如采用间接寻址方式,每个操作数需要2个页面.所以,进程所需最少物理块数就是一条指令可能跨越的页面数的最大值.如对一般的微计算机,指令最多有3个操作数时所需的最少物理块为7.

2.2 局部分配与全局分配

一般地,在讨论页面置换算法时,都回避了怎样在相互竞争内存的进程间分配内存这一问题,如当产生缺页中断时,淘汰页到底从本进程产生还是从系统的所有的进程中产生值得商榷,理论上,每个进程分配的物理块更多,其缺页率更低,但当达到一定数量后,再继续增加进程的物理块并不能显著地改善其缺页率,我们称这时进程物理块富余.进程实际运行时,工作集的大小可能随时间发生变化,如采用局部分配,进程可能有时物理块富余,而有时又物理块紧张而导致抖动.

所以,一般全局分配方式性能更优,可以增加许多分页替换的选择,平衡系统资源.

3 页面调入与清除

3.1 页面调入策略

进程开始运行,必须调入待执行的页.有两种调页策略:一是当进程执行,发现所需页面不在内存时,由系统将对应页面调入的请求调页;另一种是根据预测,将可能要执行的一批页面预先调入的预调页.

请求调页能保证调入的页面会马上执行,并且容易实现.但每次仅调入一页,增加了磁盘启动的频率,开销大.预调页每次调入一批页面,磁盘启动次数较少,又因为每次调入的是相邻的页面,磁盘寻道时间少,当然其前提是预测的命中率.高命中率的预调页算法是值得我们研究的.

3.2 清除策略

当页面被选中为淘汰页时,该页在前面过程中可能被引用,也可能尚未被引用.而被引用的页可能被修改也可能没有.一般说来,如果页面未被修改,直接覆盖该淘汰页即可,而如果修改过,则应将其写回磁盘.总之,应有一数据结构记录当前页面的使用情况.

4 负载控制

当CPU使用率较低时,CPU调度器为提高CPU利用率,通常是提高系统的多道程序度,也就是根据调度准则,从后备输入队列中选择一个进程加载到内存中.而正是因为这一进程的加入,会导致系统缺页率的上升.以物理块的全局分配为例来看,新加载的进程可能会抢占其它进程的物理块,以求得正常运行.不难想到,如果一味追求CPU利用率,不断增加多道程序度,系统必然产生颠簸现象.

一般地,多道程序度增多,CPU利用率随之增长.但到了一定时候,增长幅度趋缓;如再继续增加多道程序度,将发生颠簸现象,CPU利用率急剧下降.一旦发生颠簸,最好的方法是将一部分进程交换到磁盘,这时多道程序度降低了.值得一提的是,将哪个进程交换出去,不光要考虑进程的大小和缺页率,还要考虑其它特性,如它是CPU密集型还是I/O密集型的等.

所以,一定要合理控制系统的的负载.Denning于1980年就提出了"L=S准则",用以调整和决定多道程序度,许多研究人员已证明了这一准则的价值.

5 其它考虑

5.1 程序的结构

系统的性能不但与设计者有密切关系,实际上还与应用者有关.程序员如能设计恰当的数据结构,将增加进程的局部性,从而降低缺页率.这从下面的实例来说更明确.设分页大小为1K,对于一512512的整型数组,每个元素占2字节,如果是按行优先顺序存储,则每行占用一个分页,共占用512个分页.下图是对其初始化的C程序段.

内存循环在一个页面内工作,双层循环共发生了512页置换;但如果改为a[j][i]=0,则共有512×512次页面置换.

5.2 实时系统

实时任务要求进程在取得CPU执行权后,在规定的时限下完成.但虚拟存储机制下,进程执行过程中,必须等待某些页置换入内存,而这种置换还与系统的其它进程有关.换言之,其时间延迟不可预知.所以,实时系统不宜采用虚拟存储系统.

6 结束语

请求分页式存储管理技术是现代操作系统主流的虚拟存储技术,其理论依据是P.Denning的局部性原理.提高系统的性能是设计者和应用者始终追求的目标,究其根本,其性能就是缺页率的高低.它本身是由多个因素决定的,既依赖于设计者,还与应用者有关.它们都是性能提升的必要条件,仅对某一方面孜孜以求,结果将是“大马拉小车”.

[1]ADAMS,K.,AGESON.A Comparison of Software and Hardware Technqiues for X86 Virtualization[J].ACM,2006:2-13.

[2]Liu Huai,Fei Shu-min.A Fault-tolerant Scheduling Algorithm Based on EDF for Distributed Control Systems[J].Journal of Software,2003,14(8):1371-1378.

[3]Mark Allen Weiss,Data Structures and Algorithm A-nalysis in C 2nd ed[M].China Machine Press,2004.

[4]薛智文.操作系统[M].北京:中国铁道出版社,2003.

[5]汤子瀛,哲风屏,汤小丹.计算机操作系统[M].陕西:西安电子科技大学出版社,1996.

[6](荷)Andrew S.Tanenbaum.现代操作系统[M].陈向群,马洪兵译,北京:机械工业出版社,2009.

[7]Inline Assembly for X86 in Linux http://www-106.ibm.com/developerworks/Linux/library/l-ia.html[EB/OL].

The Performance Guaranty of Demand Paging System

LIU Tie-wu,LI Feng

(Computer and Communication School,Hunan Institute of Engineering,Xiangtan 411104,China)

T he demand paging is the most widely used virtual memory technology today.To get the better performance,it not only needs caring for the page replacement algorithm,but also needs paying attention to other aspects such as allocating policy of memory,size of page and program structure.Based on the local principle and combined with the existing research results,some inner factors are discussed and analysed from the perspective of designer and utilizer,striving to get the general conclusion in theory.

demand paging;performance;thrashing;global allocation

TP302

A

1671-119X(2011)02-0046-03

2010-09-26

湖南省教育厅科研资助项目(09C271)

刘铁武(1966-),男,高级讲师,研究方向:数据结构与算法.