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.