操作系統的進程調度演算法

A. 幾種進程調度演算法分析

前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。 ，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類： 批處理系統中的調度演算法， 代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。 互動式系統中的調度演算法， 代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。 實時系統中的調度演算法 ，代表調度演算法有：速率單調調度、最早最終時限優先調度。 下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。 保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。 彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。 彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。 速率單調調度 速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。 速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。 速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。 最早最終時限優先調度 最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。 由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。

B. 常見的調度演算法總結

一、FCFS——先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。

先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。

2. 短作業（進程）優先調度演算法。

短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、FPF高優先權優先調度演算法

1. 優先權調度演算法的類型。

為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：

1)非搶占式優先權演算法

2)搶占式優先權調度演算法（高性能計算機操作系統）

2. 優先權類型 。

對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。

3.動態優先權

高響應比優先調度演算法為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基於時間片的輪轉調度演算法

1.時間片輪轉法。

時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。

2. 多級反饋隊列調度演算法

多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：

1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。

2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。

3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；

僅當第1到第（ i-1 ）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。

4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

C. 進程調度演算法1——FCFS、SJF、HNNR

  進程的調度方式有兩種： 非剝奪調度方式（非搶占式）和剝奪調度方式（搶占方式）。
  非搶占式：只允許進程主動放棄處理機。如進程運行結束、異常結束或主動請求I/O阻塞。在運行的過程中即使有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或主動要求進入阻塞態。
  搶占式：當一個進程正在處理機上執行時，如果有一個更重要更緊迫的進程需要處理機，則立即暫停正在執行的進程，將處理機分配給更重要更緊迫的那個進程。
  下面介紹適用於早期操作系統幾種進程調度的演算法

  先來先服務（FCFS）：按照到達的先後順序調度，事實上就是等待時間越久的越優先得到服務。
  下面表示按照先來先服務演算法的執行順序

  計算進程的幾個衡量指標：

  短作業優先演算法是非搶占式的演算法，但是也有搶占式的版本—— 最短剩餘時間優先演算法（STRN,Shortest Remaining Time Next） 。
  用於進程的調度演算法稱為短進程優先調度演算法（SPF,Shortest Process First）。

  短作業/進程優先調度演算法：每次調度時選擇當前已到達且運行時間最短的作業/進程.。

  因為進程1最先達到，此時沒有其他線程，所以進程1先被服務。當進程1運行完後，進程2和3已經到達，此時進程3需要的運行時間比進程2少，所以進程3先被服務…
  計算進程的幾個衡量指標：

  最短剩餘時間優先演算法：每當有進程 加入就緒隊列改變時就需要調度 ，如果新到達的進程的所需的運行時間比當前運行的進程剩餘時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列。此外，當一個 進程完成時也需要調度 。

通過比較上面三組的平均周轉時間、平均帶權周轉時間和平均等待時間可以看出，短作業優先演算法可以減少進程的等待時間，對短作業有利。

  高響應比優先演算法： 非搶占式的調度演算法 ，只有當前運行的進程主動放棄CPU時（正常/異常完成、或主動阻塞），才需要進行調度，調度時計算所有就緒進程的相應比，選響應比最高的進程上處理機。

   響應比 = （等待時間 + 運行時間）/ 運行時間

  上面的三種調度演算法一般適用於 早期的批處理系統 ，沒有考慮響應時間也不區分任務的緊急程度。因此對用戶來說交互性差。

  如發現錯誤，請指正！！！

D. 進程調度演算法

FCFS調度演算法屬於不可剝奪演算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使後面許多短作業等待很長時間，因此它不能作為分時系統和實時系統的主要調度策略。但它常被結合在其他調度策略中使用。例如，在使用優先順序作為調度策略的系統中，往往對多個具有相同優先順序的進程按FCFS原則處理。

FCFS調度演算法的特點是演算法簡單，但效率低； 對長作業比較有利，但對短作業不利（相對SJF和高響應比）；

FCFS調度演算法有利於CPU繁忙型作業，而不利於I/O繁忙型作業。

​ 短作業優先調度演算法是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。 但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

缺點：

該演算法對長作業不利，SJF調度演算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的後備隊列，由於調度程序總是優先調度那些 (即使是後進來的）短作業，將導致長作業長期不被調度（「飢餓」現象，注意區分「死鎖」。後者是系統環形等待，前者是調度策略問題）。

該演算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。

由於作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業優先調度。

SJF調度演算法的平均等待時間、平均周轉時間最少。

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：

響應比 =（等待時間+要求服務時間）/ 要求服務時間,即RR=（w+s）/s=1+w/s，因此 響應比一定是大於等於1的。

短作業與先後次序的兼顧，且不會使長作業長期得不到服務。

響應比計算系統開銷，增加系統開銷。

高響應比優先調度演算法適合批處理系統，主要用於作業調度。

為了實現 RR 調度，我們將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程序從就緒隊列中選擇第一個進程，將定時器設置在一個時間片後中斷，最後分派這個進程。

接下來，有兩種情況可能發生。進程可能只需少於時間片的 CPU 執行。對於這種情況，進程本身會自動釋放 CPU。調度程序接著處理就緒隊列的下一個進程。否則，如果當前運行進程的 CPU 執行大於一個時間片，那麼定時器會中斷，進而中斷操作系統。然後，進行上下文切換，再將進程加到就緒隊列的尾部，接著 CPU 調度程序會選擇就緒隊列內的下一個進程。

採用 RR 策略的平均等待時間通常較長。

在 RR 調度演算法中，沒有進程被連續分配超過一個時間片的 CPU（除非它是唯一可運行的進程）。如果進程的 CPU 執行超過一個時間片，那麼該進程會被搶占，並被放回到就緒隊列。因此， RR調度演算法是搶占的。

演算法描述

1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。

2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，當且僅當在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。

3、對於同一個隊列中的各個進程，按照FCFS分配時間片調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。

4、在最後一個隊列QN中的各個進程，按照時間片輪轉分配時間片調度。

5、在低優先順序的隊列中的進程在運行時，又有新到達的作業，此時須立即把正在運行的進程放回當前隊列的隊尾，然後把處理機分給高優先順序進程。換而言之，任何時刻，只有當第1~i-1隊列全部為空時，才會去執行第i隊列的進程（搶占式）。特別說明，當再度運行到當前隊列的該進程時，僅分配上次還未完成的時間片，不再分配該隊列對應的完整時間片。

E. linux環境下的進程調度演算法有哪些

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

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

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。

F. 第三章 進程調度的幾種方式

進程調度概念：操作系統必須為多個，嗎進程可能有競爭的請求分配計算機資源。對處理器而言，可分配的資源是在處理器上的執行時間，分配途徑是調度。調度功能必須設計成可以滿足多個目標，包括公平、任何進程都不會餓死、有效地使用處理器時間和低開銷。此外，調度功能可能需要為某些進程的啟動或結束考慮不同的優先順序和實時最後期限。

這些年以來，調度已經成為深入研究的焦點，並且已經實現了許多不同的演算法。如今，調度研究的重點是開發多處理系統，特別是用於多線程的。

下面簡介幾種調度演算法。

一、先來先服務和短作業(進程)優先調度演算法

1．先來先服務調度演算法

先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。

2．短作業(進程)優先調度演算法

短作業(進程)優先調度演算法SJ(P)F，是指對短作業或短進程優先調度的演算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度演算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度演算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

二、高優先權優先調度演算法

1．優先權調度演算法的類型

為了照顧緊迫型作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先(FPF)調度演算法。此演算法常被用於批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度演算法，還可用於實時系統中。當把該演算法用於作業調度時，系統將從後備隊列中選擇若干個優先權最高的作業裝入內存。當用於進程調度時，該演算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該演算法分成如下兩種。

1) 非搶占式優先權演算法

在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度演算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。

2) 搶占式優先權調度演算法

在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在採用這種調度演算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度演算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

2．高響應比優先調度演算法

在批處理系統中，短作業優先演算法是一種比較好的演算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所述的動態優先權，並使作業的優先順序隨著等待時間的增加而以速率a 提高，則長作業在等待一定的時間後，必然有機會分配到處理機。該優先權的變化規律可描述為：

由於等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當於響應比RP。據此，又可表示為：

由上式可以看出：

(1) 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該演算法有利於短作業。

(2) 當要求服務的時間相同時，作業的優先權決定於其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。

(3) 對於長作業，作業的優先順序可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先順序便可升到很高，從而也可獲得處理機。簡言之，該演算法既照顧了短作業，又考慮了作業到達的先後次序，不會使長作業長期得不到服務。因此，該演算法實現了一種較好的折衷。當然，在利用該演算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。

三、基於時間片的輪轉調度演算法

1．時間片輪轉法

1) 基本原理

在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鍾中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用戶的請求。

2．多級反饋隊列調度演算法

前面介紹的各種用作進程調度的演算法都有一定的局限性。如短進程優先的調度演算法，僅照顧了短進程而忽略了長進程，而且如果並未指明進程的長度，則短進程優先和基於進程長度的搶占式調度演算法都將無法使用。而多級反饋隊列調度演算法則不必事先知道各種進程所需的執行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度演算法。在採用多級反饋隊列調度演算法的系統中，調度演算法的實施過程如下所述。

(1) 應設置多個就緒隊列，並為各個隊列賦予不同的優先順序。第一個隊列的優先順序最高，第二個隊列次之，其餘各隊列的優先權逐個降低。該演算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。

(2) 當一個新進程進入內存後，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可准備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列後，在第n 隊列便採取按時間片輪轉的方式運行。

(3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。

G. 實時操作系統常用任務調度演算法有哪些

實時操作系統常用任務調度演算法有哪些
操作系統常用的批處理作業調度演算法
1．先來先服務調度演算法
先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
2．短作業(進程)優先調度演算法

H. 操作系統進程調度演算法(數組)c++

1.程序演算法
struct PCB
{
int pname;
int pri;
int runtime;
int waitting;
struct PCB*next;
}
pcb[7];
struct PCB*running,ready,wait;
int sin=0;
main()
{ 創建PCB[3]--PCB[9]並插入ready隊列；／*pname分別為3--9,
pri=0,runtime=10,waittime=0 */
for(;;)/*系統程序，完成初始化和處理機分派功能*/

{cast{sig=0:swtch;
sig=1:waiter;
sig=3:proc3;
sig=4:proc4;
sig=5:proc5;
sig=6:proc6;
sig=7:proc7;
sig=8:proc8;
sig=9:proc9;}
}
}

2.進程調度程序
swtch()
{
while(ready==NULL)wakeup();
移出就緒隊列第一個PCB;
送running指針；
若pri=1,則runntime=4,否則runtime=10;
將running→pname送sig
}

3。 將進程等待函數
wait()
{將運行進程插入wait隊列，優先數置1；
sig=0;
}
4。進程喚醒函數
wakeup()
{
將wait隊列中所有的PCB中waittime減1；
將wait隊列中的所有的waittime=0的PCB揭除；
插入到ready隊列中第一個優先順序為0的PCB前面
｝

I. 操作系統進程調度演算法

你好，我復制的，希望對你有用。
調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。
一、先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。
2. 短作業（進程）優先調度演算法。短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、高優先權優先調度演算法

1. 優先權調度演算法的類型。為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：
1)非搶占式優先權演算法
2)搶占式優先權調度演算法（高性能計算機操作系統）
2. 優先權類型 。對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。
3. 高響應比優先調度演算法
為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基於時間片的輪轉調度演算法

1. 時間片輪轉法。時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。 2. 多級反饋隊列調度演算法 多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：
1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。
2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。
3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。
4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

祝你好運！

J. 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。