基于Linux系統中進程調度分析

[摘要]Linux是一個多用戶多任務的操作系統，Linux中實現了對多個進程公平、高效的調度，并不是采用單一的調度策略，而是幾種調度策略有機地綜合應用。

[關鍵詞] 進程調度 優先級 時間片輪轉 實時進程

在任何一種操作系統中，進程調度一直是一個核心問題，進程調度策略的選擇對整個系統性能有至關重要的影響，一個好的調度算法應該考慮很多方面:公平、有效、響應時間、周轉時間、系統吞吐量等等，但這些因素之間又是相互矛盾的，最終的取舍根據系統要達到的目標而定，本文以Linux操作系統為例，分析其進程調度策略，以期對進程調度過程有更深層次的認識。

一、 Linux的進程調度

Linux支持多進程，進程控制塊PCB(Process Control Block)是系統中最為重要的數據結構之一，用來存放進程所必需的各種信息，PCB用結構task-struct來表示，包括進程的類型、進程狀態、優先級、時鐘信息等，Linux系統中，進程調度操作由schedule()函數執行，這是一個只在內核態運行的函數，函數代碼為所有進程共享。

二、 Linux進程調度時機

Linux的進程調度時機與現代操作系統中的調度時機基本一致，為了判斷是否可以執行內核的進程調度程序來調度進程，Linux中設置了進程調度標志need-resched，當標志為1時，可執行調度程序.通常，Linux調度時機分以下兩種情況:(1)主動調度:指顯式調用schedule()函數明確釋放CPU，引起新一輪調度.一般發生在當前進程狀態改變，如:進程終止、進程睡眠、進程對某些信號處理過程中等，(2)被動調度:指不顯示調用schedule()函數，只是PCB中的need-resched進程調度標志，該域置位為1將引起新的進程調度，而每當中斷處理和系統調用返回時，核心調度程序都會主動查詢need-resched的狀態(若置位，則主動調用schedule()函數)，一般發生在新的進程產生時、某個進程優先級改變時、某個進程等待的資源可用被喚醒時、當前進程時間片用完等。

三、Linux進程調度策略

一般來說，不同用途的操作系統的調度策略是不同的，Linux進程調度是將優先級調度、時間片輪轉法調度、先進先出調度綜合起來應用，Linux系統中，不同類型的進程調度策略也不一樣。

1. 與進程調度相關的數據結構

每個進程都是一個動態的個體，其生命周期依次定義的數據結構為:TASK-RUNNING，TASK-INTERRUPTIBLE，TASK-UNINTERRUPTIBLE，TASK-ZOMBIE和TASK-STOPPED，一個進程在其生存期間，狀態會發生多次變化，與其數據結構相對應的即是Linux進程的狀態，分別是:運行態、等待態、暫停態和僵死態。

2. 進程狀態及其轉換過程的描述

進程創建時的狀態為不可打斷睡眠，在do-fork()結束前被父進程喚醒后，變為執行狀態，處于執行狀態的進程被移到run-queue就緒任務隊列中等待調度，適當時候由schedule()按調度算法選中，獲得CPU，若采用輪轉法，即時，由時鐘中斷觸發timer-interrupt()，其內部調用schedule()，引起新一輪調度，當前進程的狀態仍處于執行狀態，因而把當前進程掛到ruil-queue隊尾。

獲得CPU且正在運行的進程若申請不到某資源，則調用sleep-on()或interruptible-sleep-on()睡眠，其task-struct進程控制塊掛到相應資源的wait-queue等待隊列，如果調用sleep-on()，則其狀態變為不可打斷睡眠，如果調用interruptible-sleep-on()，則其狀態變為可打斷睡眠，Sleep-on()或interruptible-sleep-on()將調用schedule()函數把睡眠進程釋放.

3.進程分類和相應的進程調度策略

Linux系統中，為了高效地調度進程，將進程分成兩類:實時進程和普通進程(又稱非實時進程或一般進程)，實時進程的優先級要高于其他進程，如果一個實時進程處于可執行狀態，它將先得到執行，實時進程又有兩種策略:時間片輪轉和先進先出，在時間片輪轉策略中，每個可執行實時進程輪流執行一個時間片，而先進先出策略每個進程按各自在運行隊列中的順序執行且順序不能變化。

在Linux中，進程調度策略共定義了3種:

Linux系統中的每個進程用task-struct結構來描述，進程調度的依據是task-struct結構中的policy、priority、counter和rt-priority，PCB中設置Policy數據項，其值用于反映針對不同類型的進程而采用的調度策略。SCHED- RR和SCHED-FIFO用于實時進程，分別表示輪轉調度策略和先進先出調度策略;SCHED-OTHER表示普通進程，也按照輪轉調度策略處理。這三類調度策略均基于優先級.PCB中設置Priority數據項，其值為普通進程的調度優先級.普通進程的可用時間片的初始值即為該值，該值通過系統調用是可以改變的。

PCB中設置rt-priority數據項，其值是實時進程專用的調度優先級，實時進程的可用時間片的初始值即為該值，該優先級也可以用系統調用來修改，PCB中設置counter數據項，用于進程可用時間片時值的計數，初始值為rt-priority或Priority，進程啟動后該值隨時鐘周期遞減。

通過對Linux進程調度策略的簡單分析，可以看出多進程的管理是一種非常復雜的并發程序設計，每個進程的狀態不僅由其自身決定，而且還要受諸多外在因素的影響，而在此基礎上的進程調度，為了保證操作系統的穩定性、提高效率和增加靈活性，還必須采用很多方法，這些都是值得我們去研究和探討的。

參考文獻:

[1]劉振鵬李亞平王煜:操作系統[M].北京:中國鐵道出版社，2003

[2]趙明富李太福陳鴻雁:Linux嵌入式系統的實時性分析[J].電腦知識與技術，2003，29(18):53—55