作業系統設計/程序排程/搶佔

搶佔在作業系統中的使用是指作業系統能夠搶佔（即停止或暫停）當前排程的任務以支援更高優先順序的任務。被排程的資源可以是處理器或 I/O，以及其他資源。

例如，在處理中斷時會發生不可搶佔性。在這種情況下，排程會等到中斷處理完成才會繼續。

大多數現代作業系統中使用的排程器，例如各種 Unix 版本，可以搶佔使用者程序。這被稱為搶佔式多工處理，與合作式多工處理形成對比，在合作式多工處理中，程序透過使用核心資源或專門呼叫核心例程來允許其他程序執行時間，從而“放棄”其時間。

歷史

一些作業系統的排程器（包括 Linux 2.6 系列）能夠在程序處理系統呼叫時搶佔程序（可搶佔核心）。

Sinclair QDOS 是首個可供家庭使用者使用的搶佔式多工系統（1984 年）。其他搶佔式作業系統包括 AmigaOS、Windows NT 家族（包括 XP 或 Vista）、Linux、*BSD 和 Mac OS X。合作式作業系統的例子包括 Windows for Workgroups（也稱為 Windows 3.1 或 95）、NetWare 和 Mac OS 9.x 版本。

Linux 2.6 之前的 Linux 核心也是不可搶佔的，但後來的版本實現了搶佔式模型。幾個商業版本的 UNIX 是搶佔式的，包括 Solaris 和 IRIX。

類比

當前在收銀臺的人可能被打斷，必須在完成之前等待另一個顧客。

實現

在 Linux 核心中，排程器在每次定時器中斷後被呼叫（即每秒多次）。它根據各種因素確定接下來要執行的程序，包括優先順序、已執行時間等。其他核心中搶佔的實現可能類似。

優點和缺點

使排程器可搶佔的優點是更好的系統響應能力和可擴充套件性，但缺點是存在競態條件（正在執行的程序在另一個被搶佔的程序完成使用之前訪問了相同的資源）。

迴圈搶佔式排程

最簡單的搶佔式排程演算法是迴圈排程。迴圈排程器將所有可執行的程序儲存在一個迴圈佇列中。每次硬體定時器中斷當前執行的程序時（或當該程序自願放棄控制時），排程器會將該程序放到佇列的末尾。然後，排程器會獲取佇列頭部的程序並執行它。

優先順序搶佔式排程

(FIXME：考慮將此部分拆分到一個單獨的“優先順序搶佔式排程”頁面)

幾乎所有現代作業系統都使用優先順序搶佔式排程。

大多數即時計算機系統使用固定優先順序搶佔式排程 - 通常是速率單調排程或截止日期單調排程。

固定優先順序搶佔式排程

速率單調排程：啟用頻率較低的作業比（因此會被）所有啟用頻率較高的作業賦予較低的優先順序。如果 CPU 利用率小於 $\ln 2\approx 0.693147\ldots$.

截止日期單調排程：作業的優先順序與其相對截止日期成反比。（在每個作業的相對截止日期等於其週期的特殊情況下，截止日期單調排程等效於速率單調排程）。

動態優先順序搶佔式排程

最早截止日期優先排程：作業的優先順序與其絕對截止日期成反比。截止日期單調排程和最早截止日期優先排程之間的區別在於，DM 是一種靜態優先順序演算法，EDF 是一種動態優先順序演算法。 EDF 可以保證所有截止日期都能夠滿足，前提是總的 CPU 利用率小於 $1$.

固定 vs 動態 vs 迴圈

動態優先順序演算法的優點是它們可以成功地排程一些會導致靜態優先順序演算法失敗（即錯過截止日期）的作業集（即不會錯過任何截止日期）。

固定優先順序演算法相對於動態優先順序演算法的優勢在於，如果系統在某個優先順序級別上遇到過載——因此在該優先順序上排程了太多作業，以至於任何排程程式都無法滿足所有作業的截止期限——固定優先順序排程程式仍然可以保證所有較高優先順序的作業將仍然被排程，並且仍然能夠滿足其截止期限。^[3] 固定優先順序演算法的另一個優勢是更容易實現。

實現基於優先順序的排程程式的人需要擔心兩個潛在的問題

• 程序飢餓：如果一個程序請求所有它能獲得的 CPU 時間——由於意外過載或惡意拒絕服務攻擊——所有較低優先順序的程序將被鎖定。^[4]
• 優先順序反轉：(FIXME:)

迴圈排程程式的優勢在於不會出現這些與優先順序相關的問題。

混合排程

一些排程程式實現了上述排程演算法的混合。

自適應分割槽排程程式在系統沒有處於滿負荷時使用基於優先順序的排程，但也保證即使在系統負載很重的情況下，低優先順序服務也能獲得最小的 CPU 時間^[4][5]，使用類似迴圈的演算法。

許多即時系統都有一個最低優先順序的“後臺任務”，它沒有硬即時截止期限，系統只在所有即時任務完成後的閒置時間執行它。^[6][7]

這些系統中有一些使用“雙核心”，整個通用作業系統（如 Linux）及其排程程式作為單個最低優先順序任務執行在硬即時核心之上。^[8]（當即時核心使用速率單調排程時，該非即時任務至少可以獲得 $0.3$ 的 CPU 時間）。

中斷延遲

除了定時器滴答中斷外，大多數系統還有其他硬體中斷。(FIXME: 關於臨界區的某些內容)(FIXME: 關於確定性響應時間與抖動的某些內容)(FIXME: 關於流式音訊資料的一些內容)最壞情況下的中斷延遲至少是核心中最長臨界區的時間。^[6]

一些高可用性作業系統支援虛擬裝置驅動程式——以最高優先順序執行並直接操作硬體（如中斷服務例程）的程式碼量最小化；大多數裝置驅動程式工作由使用者空間中的二級中斷處理程式處理。^[7](FIXME: 可能關於硬體中斷觸發一級中斷處理程式，以及定時器滴答中斷執行排程程式，它可能會執行二級中斷處理程式？或者這已經由嵌入式系統/中斷 涵蓋了嗎？)

我們將在後面的章節中詳細討論各種硬體中斷，作業系統設計/程序/中斷。

硬即時排程程式

許多計算機系統設計為隨時接受新任務。如果只有一個任務在執行——或者如果所有其他任務都適合該任務無法做任何有用的事情的時間（因為它正在等待磁碟旋轉，網路卡完成資料包等）——那麼該任務將在最短時間內完成。但是，隨著其他任務被新增到系統中，這些任務會搶佔該任務，完成任務所需的時鐘時間將變得無界。(FIXME: 在這裡談論“無飢餓”的某些內容)

硬即時計算機系統設計為故意拒絕接受新任務。程式設計師仔細設計即時任務，使其相對容易計算最壞情況下的執行時間（即避免停機問題）。有了這個執行時間、任務所需的截止期限以及任務本身，就可以使用速率單調分析來確定在將該任務新增到已新增到系統的所有其他任務之後，是否不僅可以滿足該任務所需的截止期限，還可以繼續滿足之前所有任務所需的截止期限——如果無法保證所有這些截止期限將繼續得到滿足，則拒絕接受該新任務。有些人構建允許新任務呈現給系統的系統，並設計系統自動執行 RMA 分析，然後系統決定是否接受這個新任務。其他人手動執行 RMA 以決定允許系統中的哪些任務，然後將系統硬連線到只執行這些任務——這些系統更簡單。

構建硬即時系統的人認為，偶爾拒絕接受一些新任務非常值得保證之前所有任務都能滿足其截止期限。