Linux内核交互式和非交互式进程判别算法的质疑

张 科, 杨 斌

(西南交通大学信息科学与技术学院,四川成都610031)

在Linux2.6.18的内核中,调度程序采用了动态优先级、O(1)调度算法、时间片粒度、内核抢占点和进程分类一系列提高内核运行效率的算法和策略,使得系统的运行更加流畅和高效。内核将进程分为实时进程和非实时进程,在Linux操作系统下运行的进程默认情况下都是非实时进程,非实时进程又分为交互式进程和批处理进程。

交互式进程的定义：进程需要和用户进行交互,花大量的时间等待键盘输入和鼠标操作,一旦进程接受到输入,必须被尽快唤醒。通常来说,平均延迟时间是在50-150ms之间[1]。

批处理进程的定义：进程在系统后台运行,不需要用户的干预,不需要被系统尽快响应,经常被调度程序降低优先级。如程序编译器,数据库引擎和科学计算[1]。

被内核认定为交互式进程的好处：(1)可以提升进程的动态优先级;(2)当进程的时间片使用完毕后,调度程序仍然将该进程放到active运行队列末尾,而不是放到expired队列中。这样就可以保证交互式进程如果处在就绪队列中,能够有很高的优先级先被执行,反映在用户层面即有很快的响应速度。

1 与交互式进程识别相关的变量和函数

1.1 与交互式进程判别相关的变量

与交互式进程判别相关的变量有：prio：动态优先级;static-prio：静态优先级;sleep-avg：平均睡眠时间;bonus：红利;state：进程状态;time-slice：时间片;sleep-type：睡眠类型;sleep-time：进程阻塞时的睡眠时间;runtime：进程占用CPU的时间。

1.2 与交互式进程判别相关的函数

与交互式进程判别相关的函数有：

(1)do-fork：创建一个新进程,其 prio、static-prio、sleep-avg都延续父进程的值,其 time-slice为父进程time-slice的一半。进程创建完毕后被放入active运行队列末尾。

(2)每当系统时钟的一个tick产生时,调用scheduler-tick()函数,将time-slice减1,如果time-slice等于0时,调用effective-prio函数重新计算动态优先级(见动态优先级的计算公式),调用task-timeslice重新计算时间片,然后调用TASK-INTERACTIVE来判断进程是否是交互式进程(见交互式进程的判别公式),如果是则重新添加到active队列末尾,否则将进程添加到expired队列末尾。

(3)schedule函数计算当前进程的run-time,即当前进程这次占用CPU的时间,然后计算sleep-avg(见平均睡眠时间的计算方法),接着将当前进程切换出CPU,在进程优先级位图中查找优先级最高的进程,判断该进程上次睡眠是否是交互式睡眠,如果是则重新计算优先级recalc-task-prio,然后调入CPU运行。

(4)当进程由于等待资源而进入阻塞队列,当资源满足的时候,系统通过中断或者信号处理程序调用trywake-up函数将该阻塞的进程放入运行队列,在放入运行队列之前,要对该进程计算本次睡眠时间,根据本次睡眠时间重新计算该进程的sleep-avg(见平均睡眠时间的计算方法)和动态优先级。然后根据计算出的动态优先级决定进入active中对应的优先级队列。

计算进程是否是交互式进程,以及进程能够进入active中的哪个级别的优先级队列和这4种情况密切相关。下面具体分析各个参数的计算方法。

2 交互式进程同批处理进程的区分算法

2.1 动态优先级的计算公式

式(2)中sleep-avg和bouus的关系如图1所示。其中MAX-BONUS=10;MAX-SLEEP-AVG=1000ms该公式的含义为：将平均睡眠时间分为10个等级,平均睡眠时间越长,红利就越高,计算出的动态优先级也就越高。

图1 sleep-avg和bonus的关系

2.2 交互式进程的判别公式

当进程的时间片使用完毕后,判断如果进程是交互式进程,则将进程添加到active队列末尾。

其中INTERACT IVE-DELTA为固定值2。

由式(1)、(3)可得：

由式(2)、(4)、(5)得出：

即当满足式(6)的情况下时,那么进程就是交互式进程。其中static-prio和sleep-avg的关系如图2所示。

由式(5)可见static-prio[100,139]被分为 10个等级,sleep-avg也被划分为10个等级进行对应处理。

可见当static-prio在[136,139]之间时,sleep-avg的最大值为1000ms,式(5)不能成立,故当静态优先级在[136,139]之间时,进程永远不可能被识别为交互式进程。

2.3 平均睡眠时间的计算方法

(1)进程从阻塞到运行队列时计算的sleep-avg

由于进程等待资源而产生阻塞,进入相应的阻塞队列。随着被等待的资源释放,进程被唤醒,重新计算平均睡眠时间和动态优先级,重新设置进程状态和sleep-type,然后将该进程放入相应的运行队列,等待调度程序调度。

在内核计算平均优先级的方法如下：

Linux内核中存在一个交互式睡眠的时间表INTERACTIVE-SLEEP(p),公式为：

图2 static-prio和sleep-avg的关系

化简后：INTERACTIVE-SLEEP(p)=25*static-prio-2201。其中INTERACTIVE-SLEEP和static-prio的关系如图3所示。

如果此次的睡眠时间(即调度程序将该进程切换出CPU到该进程重新进入就绪队列中的时间)大于INTERACTIVESLEEP(p),并且 sleep-avg ＜ INTERACTIVE-SLEEP(p),将sleep-avg=INTERACTIVE-SLEEP(p)

当进程因为读取硬盘资源而阻塞的时候,其阻塞状态为TASK-UNINTERRUPTIBLE,当进程被唤醒的时候,sleeptype设置为SLEEP-NONINTERACTIVE。

当sleep-type为SLEEP-NONINTERACTIVE状态的时候,如果平均睡眠时间超过阈值,或此次睡眠时间和平均睡眠时间之和超过阈值的时候,平均睡眠时间就被置为阈值。但不超过平均睡眠时间的最大值ls。

(2)从CPU中切换下来时,平均睡眠时间的计算在进程被调度程序切换出CPU时：

其中CURRENT-BONUS=sleep-avg*MAX-BONUS/MAX-SLEEP-AVG

可见如果平均睡眠时间越高(即该进程越有可能是交互式进程),其运行时间减少得越快,sleep-avg减少得也就越慢,这样处理的目的是保证进程不会从交互式进程和批处理进程之间频繁切换。

这样 ：sleep-avg=sleep-avg+sleep-time-run-time。

图3 INTERACTIVE-SLEEP和static-prio的关系

3 测试例程设计

3.1 测试程序功能

(1)在内核中调度阶段、进程唤醒阶段和时间片使用完毕阶段加入打印信息

(2)使用驱动程序打开内核中对应pid的打印信息

(3)用户测试进程完成的功能

打开驱动,修改内核变量,使内核只打印该进程的内核信息。

遍历硬盘上某个目录下的所有文件,并读取每个文件内容,然后将每个文件再写入磁盘,遍历完所有文件后退出程序。目的：模拟编译程序的执行过程,判别该进程最终是否被内核识别出为非交互式进程和识别的过程。

当进程在shell中执行时,shell为其父进程,该进程被fork时,sleep-avg,static-prio,prio这些都从父进程中继承下来,即与shell的参数相同,其他参数测试结果如表1所示。

表1 未修改静态优先级时进程的测试结果

测试2：

当进程在shell中执行时,shell为其父进程,该进程被fork时,采用setpriority函数修改进程的静态优先级为136,结果如表2所示。

表2 设定静态优先级是136的测试结果

4 总结

根据测试结果分析,由于进程频繁访问硬盘,从硬盘获取数据,不断造成进程阻塞,处于TASK-UNINTERRUPTIBLE阻塞状态,当磁盘控制器将读取的数据放入内存中时,产生中断,调用try-wake-up函数唤醒进程。由于访问硬盘的时间比运行时间长,造成sleep-avg的值不断增大,最终被判定为交互式进程。根据以上的分析：

(1)当进程的静态优先级在[100,135]时,2.6.18内核并不能真正区分交互式进程和批处理进程。

(2)当进程的静态优先级在[136,139]时,不论进程是否真的是交互式进程,内核一律将之识别为非交互式进程处理。

由于2.6.18内核的对交互式进程判别的不正确。当在编写频繁访问硬盘数据的程序时,可以采用setpriority函数适当地降低该进程的优先级来保证系统对真正需要交互的进程的及时响应。

如果不降低该进程的优先级,将会造成比该进程优先级低的真正的交互式进程无法得到运行而呈现死机的状态。

[1]Daniel P.Bovet,Marco Cesati.Understanding the Linux Kernel[M].O'Reilly,2005.

[2]毛德操,胡希明.Linux内核源代码情景分析[M].浙江：浙江大学出版社,2001.

[3]赵炯.Linux内核完全剖析[M].北京：机械工业出版社,2006.