Ｌｉｎｕｘ進程調度策略分析

摘要：進程調度是多任務操作系統的核心。Linux系統中的每個進程用task_struct結構來描述，進程調度的依據是task_struct結構中的policy、priority、counter和rt_priority。Linux根據policy將進程劃分為實時和普通兩類，普通進程采用動態優先調度，實時進程采用基于優先級的FIFO調度和多級反饋輪轉調度。

關鍵詞：Linux；進程；調度策略；優先級

中圖分類號：TP316文獻標識碼：A文章編號：1009-3044(2008)29-0497-02

Research on the Linux Process Schedule

YU Yun-xia1，2

(1.College of Computer，Wuhan University，Wuhan 448000，China;2.Department of Computer，Jingchu University of Technology，Jingmen 448000，China)

Abstract: The process schedule is very important to the multi-task operating systems. The Linux scheduling policy is based on four fields， including policy，priority，counter and rt_priority，of a task_struct type structure， which plays the role of a single process descriptor. There are two kinds of processes determined by the field policy， the real-time processes， to which a First-In，First-Out or A Round Robin scheduling is applied， and the non real-time processes， to which a dynamic priority scheduling is applied.

Key words: Linux; process; schedule; priority

1 前言

Linux系統是一個龐大、高效而復雜的操作系統，它的內核包括進程調度、內存管理、進程間通信、虛擬文件系統和網絡接口五部分，其中進程調度是核心。

進程調的實質是資源的分配，如何使系統能夠保持較短的響應時間和較高的吞吐量，如何在多個可運行的進程中選取一個最值得運行的進程投入運行是調度器的主要任務。進程調度包括兩個方面的內容：何時分配CPU時間（調度時機）即調度器什么時候啟動；如何選擇進程（調度算法）即調度器該怎么做。進程調度算法是解決如何使資源分配策略最優化的關鍵。

2 Linux 進程調度原理

進程是動態的，一個進程的所有信息都被放在其對應的task_struct數據結構中。每當一個新的進程創建時，一個新的task_struct結構將分配給該進程，并同時增加到進程向量的數組中。系統還有一個當前進程指針，用來指向當前正在運行的進程。task_struct實際上就是通常所說的“進程控制塊”PCB，它是系統對進程控制的惟一且最有效的手段。

2.1 Linux進程模型

Linux中的每個進程由task_struct結構來描述。在Linux中任務和進程是相同的術語，task_struct就是指PCB（進程控制塊）。Linux將進程狀態分為五種：task_running、task_interruptible、task_uninterrcptible、task_stopped和task_zombile。進程的狀態隨著進程的調度發生改變，見圖1所示。

Task_running（運行狀態）：無論進程是否正在占用CPU，只要具備運行條件，都處于該狀態。Linux把處于該狀態的所有PCB組織成一個可運行隊列run_queue，調度程序從這個隊列中選擇進程運行。事實上，Linux是將就緒狀態和運行狀態合并成了一種狀態。

task_interruptible（可中斷阻塞狀態）：Linux將阻塞狀態劃分成task_interruptible、task_uninterruptible 、task_stopped三種不同的狀態。處于task_interruptible狀態的進程在資源有效時被喚醒，也可以通過信號或定時中斷喚醒。

task_uninterruptible（不可中斷阻塞狀態）：另一種阻塞狀態，處于該狀態的進程只有當資源有效時被喚醒，不能通過信號或定時中斷喚醒。

task_stopped（暫停狀態）：第三種阻塞狀態，處于該狀態的進程只能通過其他進程的信號才能喚醒。

task_zombile（僵死狀態）：進程已結束但尚未消亡，已經釋放了大部分資源，PCB仍未被釋放。

2.2 進程調度的時機

進程調度的時機與引起進程調度的原因以及進程調度的方式有關。Linux進程調度的時機主要有：進程狀態轉換的時刻，如進程終止、進程睡眠等；可運行隊列中新增加一個進程時；當前進程的時間片用完時；進程從系統調用返回到用戶態時；內核處理完中斷后，進程返回到用戶態時。

2.3 進程調度的策略分析

調度程序要在所有處于可運行狀態的進程中選擇最值得運行的進程投入運行。在每個進程的task_struct 結構中有：policy、priority、counter、rt_priority，這4項就是選擇進程的依據。其中policy是進程的調度策略，用于區分實時進程和普通進程，實時進程優先于普通進程運行；priority是進程(包括實時和普通)的靜態優先級；counter是進程剩余的時間片，它的起始值就是priority的值；由于counter在后面計算一個Linux的進程調度策略處于可運行狀態的進程值得運行的程度goodness時起重要作用.

1) 普通進程的調度策略－動態優先調度

當policy的值為SCHED_OTHER時，是普通的用戶進程，采用動態優先調度，選擇進程的依據是進程counter的大小。進程創建時，優先級priority 被賦一個初值，一般為0～70 之間的數字，這個數字同時也是計數器counter 的初值，進程創建時兩者是相等的。priority代表分配給該進程的時間片，counter表示該進程剩余的時間片。在進程運行過程中，counter不斷減少，而priority保持不變，以便在counter變為0的時候（該進程用完了所分配的時間片）對counter重新賦值。當一個普通進程的時間片用完以后，并不馬上用priority 對counter進行賦值，只有所有處于可運行狀態的普通進程的時間片(p->counter==0)都用完了以后，才用priority對counter重新賦值，這個普通進程才有了再次被調度的機會。在普通進程運行過程中，counter的減小給了其他進程得以運行的機會，即進程正在運行時可以被其他counter值更大的進程中斷，但只有當該進程的counter值減為0時才完全放棄對CPU的使用，這就相當于優先級在動態變化，所以稱之為動態優先調度。

2) 實時進程的調度策略－FIFO 和RR

對于實時進程，Linux采用了兩種調度策略，即先來先服務調度（FIFO調度）和時間片輪轉調度（RR調度）。當policy的值為SHED_FIFO時，遵守POSIX1.b標準的FIFO調度規則。它會一直運行，直到有一個進程因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個具有更高rt_priority的實時進程搶先。在Linux實現中，SCHED_FIFO進程仍然擁有時間片，只有當時間片用完時它們才被迫釋放CPU。

2.4 進程同步

Linux中，當進程在內核中運行時，不允許搶占，因此當一個進程決定放棄CPU時，一般來說，它已經運行到了一個一致的位置，所以內核對數據的處理是很安全的。但也有例外：內核正在對數據結構操作時發生中斷，而中斷處理程序又操作同樣的數據結構。在多處理機中，由于并行執行，可能出現同時修改同樣數據結構的情況。有些內核程序由于設計上的缺陷而導致的數據不一致。

在單處理機中處理同步所使用的機制主要是：鎖（開關中斷）、信號燈、條件變量、睡眠等待。

2.5 進程終止

進程的終止分兩步：自己調用函數exit將自己的狀態改為僵死狀態，向父進程發信號；父進程調用wait函數，回收僵死的子進程，將其從內存中徹底清除。

3 實時調度算法

常用的實時調度算法有：基于優先級的調度算法；基于時間驅動的進程調度算法；基于比例共享的調度算法。

3.1 基于優先級的調度算法

基于優先級的調度算法給每個進程分配一個優先級，在每次進程調度時，調度器總是調度那個具有最高優先級的任務來執行。根據不同的優先級分配方法，基于優先級的調度算法可以分為如下兩種類型：1) 靜態優先級調度算法：這類算法給系統中能夠運行的所有進程都靜態地分配一個優先級。2) 動態優先級調度算法：這類算法根據任務的資源需求來動態地分配任務的優先級，其目的就是在資源分配和調度時有更大的靈活性。

3.2 基于比例共享的調度算法

比例共享調度算法指基于CPU使用比例的共享式調度算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，使其執行時間與權重完全成正比。

可以通過兩種方法來實現比例共享調度算法：1) 調節各個就緒進程出現在現在調度隊列隊首的頻率，并調度隊首的進程執行；2) 逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配給每個進程的運行時間片。

3.3 基于時間驅動的進程調度算法

該算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有處理的情況下，對于各個任務的開始、切換以及結束時間等事先做出明確的安排和設計。并適合于那些很小的嵌入式系統、自控系統、傳感器等應用環境。其優點是任務的執行有很好的可預測性，其最大的缺點是缺乏靈活性，并且會出現有任務需要被執行而CPU卻保持空閑的情況。

4 結論

進程調度是多任務操作系統的核心。Linux根據policy將進程劃分為實時和普通兩類，普通進程采用動態優先調度，實時進程采用基于優先級的FIFO調度和多級反饋輪轉調度。同時，Linux 的進程調度效率高， 調度策略本身具有很高的綜合性， 并不單純地屬于某一種調度策略。

參考文獻：

[1] 陳利君.Linux操作系統內核分析[M].北京:人民郵電出版社，2000.

[2] 趙明富.Linux嵌入式系統的實時性分析[J].計算機工程，2003(29).

[3] 黃麗娜.Red Hat Linux 9.0基礎教程[M].北京:清華大學出版社，2004.

[4] 楊文志.Linux實用大全[M].北京:清華大學出版社，2001.