基于Linux的颠簸分析与处理

刘铁武,张铁楠,冯 剑

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

Linux因其稳定性、安全性、源代码开放等特点而成为当今最具发展潜力的操作系统.存储管理作为Linux的核心部分,直接关系整个计算机系统的性能.

Linux采用了请求分页式存储管理,其内存管理部件与交换子系统都是以页为操作粒度的.

Linux请求分页的思想很简单:一个进程并不要全部在内存中,仅只用户结构和页表.如果它们存在于内存,对应进程就被认为“在内存中”,代码、数据和栈段的页面是仅仅当其被引用时动态载入的.如此,从逻辑上实现了对内存容量的扩充.

因为页面的动态载入,势必将产生缺页而需要在内、外存间进行页面置换.如果进程运行过程中因为缺页而频繁在内外存间进行页面交换,则主要执行I/O操作而CPU利用率极低,进程几乎没有完成有效的工作,这种状态就是颠簸.本文从理论上分析了颠簸的形成机制、刻划了它的特征.在此基础上,讨论了颠簸的处理策略.

1 颠簸的形成机制

1.1 进程拥有的物理块不足

与局部置换相比,页面的全局置换能提高请求分页式系统性能[4].实际上,一般操作系统都采用了此种策略.但另一方面,这种置换策略决定了:如果增加某个进程的物理块数目,可能直接导致另一进程的物理块数目减少.当整个系统的物理块不能满足诸进程的需要时,缺页率将持续维持于一高水平值,意味着颠簸已实际形成.其具体表现形式如下:

(1)进程竞争临界资源.考虑这样的情况:系统中已不存在空闲物理块,而进程A却要求增加物理块,于是,中断处理程序只得将原属于进程B的物理块分配给进程A;同样地,进程B又分配到原属于进程C的物理块,如此等等.一定时候,各缺页进程都将被阻塞,就绪队列为空,颠簸从此形成[9].

(2)增加多道程序度[5].当CPU利用率处于低水平时,为提高多道程序度,调度程序要求从后备输入队列选择进程加载内存.

图1 多道程序度与CPU利用率的关系

图1 可清楚地说明这种情形下颠簸的形成原因.首先,随着多道程序度的增加,CPU利用率随之增加而达到一个理论极值.但在极值点右边,再增加多道程序度,因为进程事实上只能从已加载的进程处获得物理块,从而使得更多的进程因缺页而阻塞,随着更多的进程执行内外存的I/O操作,CPU利用率反而更低;为提高CPU利用率,调度程序又要求调入新进程.如此形成恶性循环,系统诸进程都将缺页,颠簸形成.

(3)内存分配机制引起颠簸.由于异构硬件的限制,物理内存并没被同等对待.Linux有三种内存区域:ZONE_DMA;ZONE_NORMAL;ZONE_HIGHMEM.前两种是内核和内存映射,被“钉”在内存中(页面从不换出).当应用进程请求分配内存时,采用“伙伴算法”[6]由页面分配器予以分配.该算法可能导致大量的内存碎片;而另一方面,Linux的虚拟地址空间被分割成同构连续的页面对齐的区域.则可能实际空闲空间具备却没一块连续的空间来满足任一进程的需求,各进程都将阻塞.

1.2 因页面置换算法而形成

虚拟存储技术的理论基础是P.Denning的局部性原理.即程序在执行时将呈现时间局限性和空间局限性.事实上,在结构化程序设计理论中,已经证明采用三大结构,可以解决任何复杂问题.其中顺序结构和循环结构很好地体现了时空局部性,例外的选择结构在程序中实际占的比重是较小的.

基于局部性原理,几乎所有的页面置换算法总是试图从当前正在引用的页面去＂预测＂将要引用的页面,据此产生淘汰页和置换页.大多数情形下,这种预测的命中率可以很高.但对于特定的程序(如有大量的转向语句的程序),命中率将很低,其结果很可能是所选择的淘汰页却是即将要引用的页;而从外存置换到内存的页面在最近很长时间却不会被引用.不得已,继续进行页面置换,反反复复,颠簸形成.

当然,我们也容易知道与局部性原理背道而驰的页面置换算法在大多数的情形下有可能产生颠簸.

2 颠簸的处理

颠簸一旦形成,CPU得不到有效利用,系统只是反复进行磁盘-内存对换操作这等无用功.为解除之,调度程序不得已地必须对系统中诸进程重新予以调度.只能选择挂起进程或者是撤消进程.这两种方法的调度总代价都非常大.因此,首先应尽量避免颠簸形成.

2.1 颠簸的预防

(1)局部置换

如果进程执行时发生缺页,约定只能从属于本进程的物理块中产生淘汰页,而不允许从其它进程处获得物理块.如此,某个进程的颠簸不会引起其它进程的颠簸,可将颠簸框定在一个特定的、较小的范围内.

当然,这种方法并不理想.全局分配是保证分页式系统性能的要素,这与局部分配本身是矛盾的;另外,它并不能从根本上防止颠簸,只能局限其范围.如果某进程处于颠簸状态,则其将长期处于阻塞队列,不断地进行内外存交换,又必然会影响其它进程进行缺页处理.

(2)跟踪缺页率

根据局部性原理,绝大多数时候,进程是从一个局部区域转移到另一个局部区域执行.所以,必须有足够的物理块供使用,以减少缺页,避免颠簸.到底应为每个进程分配多少物理块呢?实际上,它是系统拥有总的物理块数与当前系统实际应用相关的一个经验值.这从缺页率与所分配的物理块数关系曲线得到证实.在拐点附近,每增加(减少)进程的物理块数都能显著地改变缺页率;而一定时候以后,即使再增加物理块,缺页率变化也不明显.拐点左边缺页率非常高的区域就是本来的颠簸,拐点就是理想的物理块数目.据此,可对系统中的进程定义其缺页率的上限和下限阀值,此区间内的物理块数是进程拥有的相对合理的物理块数,缺页率高于上限时说明其分配到的物理块太少应当追加;而当缺页率低于下限时说明该进程所拥有的物理块数太多,可收回一部分.

图2 进程分配的物理块与缺页率关系

(3)调整页面置换算法

页面置换算法与实际应用相关,对于大多数的进程,与置换算法同时吻合了局部性原理,从而缺页率低;而其余少数进程因与局部性原理相背,而使＂预测＂失效,其缺页率偏高可能引发颠簸.

我们可以在一个系统中预备2种以上不同的选择淘汰页和置换页策略的置换算法,并定义一缺页率的阀值,处理程序中设置一开关,当缺页率大于阀值时改用另一种置换算法.

(4)锁定缺页进程

具体做法是:在进程进行淘汰或置换时,总是将缺页进程锁定,不允许其换出页,所调入的页总是占据那些暂时得不到运行的进程所有的物理块,这相当于扩大了缺页进程的工作集.

(5)其它考虑

进程的缺页率实际上还与应用者有关.程序员如能设计恰当的数据结构,将增加进程的局部性,从而降低缺页率.下面的实例能精确说明这一问题.数组按行优先顺序存储还是按列优先顺序存储,其换页次数是完全不同的.

所以,程序员也应考虑程序的结构,尽量减少缺页.

2.2 颠簸的解除

颠簸形成后,系统表现为:CPU利用率低,于是,调度程序又调入新的进程,CPU利用率又将变得更低.要解决这种局面,没有选择地只能调节系统的多道程序度.具体方法是:

(1)挂起进程

在Linux系统中,可设置CPU利用率的下限阀值,一旦低于此值,即“认定”系统处于颠簸状态,从而检查进程运行中的内存资源使用情况.再根据某种选择策略将阻塞队列中某进程换至外存中挂起,以腾出内存空间分配给颠簸的进程.反复如此,直至颠簸解除.

可每次挂起一批进程,这样挂起的代价相对较小;较温和的是每次挂起一个进程,但代价较大.被挂起的进程一般为优先权较低的;当内存非常拥挤时,也可选择优先权相对较低却占用物理块较多的进程挂起,以便一次释放较大的内存空间;还可选择尚需执行时间最多的进程挂起等.

(2)撤消进程

选择进程予以撤消,是解除颠簸最简单最有效的方法,但代价也最大.与挂起进程类似,也可一次撤消一批进程或是一个进程,撤消进程时也应考虑选择策略.

对颠簸进行处理时必须注意两个问题.其一是挂起(撤消)进程的代价问题.其二是饥饿现象.对于确定的选择策略,从理论上说,某个进程可能每次都被选择而被挂起(撤消),该进程将永远没有执行的机会.可以设置进程被选中的上限次数加以避免.

3 结束语

Linux是一个请求分页系统,没有工作集的概念.由于是全局置换,当系统总的物理块数目不能满足需要,而诸进程的却竞争使用;在大多数时候性能优良的页面置换算法,对于极少数极端输入;Linux本身固有的内存分配机制都可能引起甚至直接触发颠簸.

颠簸一旦形成,解除的代价总是非常大的,挂起或者撤消进程成为不得已的选择,所以,应尽量避免颠簸.

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

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

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

[4]张尧学,史美林,张 高.计算机操作系统教程[M].北京:清华大学出版社,2006.

[5]Tie-nan Zhang,Tie-wu Liu The Cause and Treatment Strategy on Thrashing[C].Advanced M aterials Reasearch,2011,216(3).