一. 作業系統排程的原則
1. 什麼是排程 當計算機系統死多道程式設計系統時，通常就會有多個程序或者線程競争CPU，隻要有兩個或者更多的程序處于就緒狀态，這種情況就會發生，如果隻有一個CPU可以用，那麼必須選擇下一個要運作的程序，在作業系統中，完成選擇工作的這一部分被稱為排程程式（scheduler）。該程式使用的算法稱為排程算法（scheduler algorithm）。 幾乎所有的程序的I/O請求或者計算都是交替突發的，注意，某些I/O活動可以看做是計算，例如，當CPU向視訊RAM複制資料以等待更新螢幕時，因為使用了CPU，是以是計算活動，而不是I/O活動，按照這種觀點，當一個程序等待外部裝置完成工作而被阻塞時，才是I/O活動。
Fig 1 : CPU排程的突發使用和等待I/O的交替出現：a) CPU密集型程序；b)I/O密集型程序 2. 何時排程
- 在建立一個新程序後，需要決定是運作父程序還是子程序，需要決定是運作父程序還是子程序
- 一個程序退出後必須進行排程
- 在一個程序阻塞在I/O和信号量上或者由于其他原因阻塞的時候，必須選擇另一個程序開始運作。
- 在一個I/O發生中斷的時候，必須做出排程決策。
- 非搶占式排程：挑選一個程序，然後讓該程序運作到被阻塞。
- 搶占式排程：挑選一個程序讓他運作到某個固定時段的最大值。如果在改時間段結束時，該程序仍然在裕興，它就會被挂起，而排程程式挑選另一個程序運作，如果存在一個就緒程序。進行搶占式排程處理，需要在事件間隔的末端發生時鐘中斷，以便把CPU控制傳回給排程程式，如果沒有可用的時鐘，那麼非搶占式排程就是唯一的選擇。
3. 排程算法的三個目标
- 吞吐量 (throughout) : 系統每個小時完成的作業數量。
- 周轉時間 (turnaround time) : 一個批處理作業送出時刻到完成該作業完成時刻為止的統計平均時間。
- CPU使用率 (CPU Utilization) : 多用于度量批處理系統，反應CPU的使用情況
當然我們也可以不完全依靠作業系統的排程程序來對我們的程序進行排程，我們可以手動調整，即調整排程程式的參數。這種方法被稱為把排程機制與排程政策分離。 二. 批處理系統中的排程 對于批處理系統的排程，需要滿足以下幾個要求：
- 吞吐量——每小時最大作業量
- 周轉時間——保持從送出到終止間最小忙碌
- CPU使用率——始終保持CPU忙碌
1. 先來先去服務 (first-come first-served, FCFS) 這是一個非搶占式的排程算法。實作也很簡單，就是程序按照它們請求的CPU順序使用CPU，誰先申請誰就會在隊列的前面，後面申請的就不斷加入到隊尾即可。當一個正在運作的程序發生了阻塞，那麼隊列中的第一個程序就會繼續運作，在阻塞的程序程式設計就緒時，就像一個新來到的作業一樣，排到隊列的末尾。 2. 最短作業優先 (shortest job first) 同樣也是一個非搶占式排程算法。實作起來也非常簡單，就是把作業的時間從小到大排列，并且按這個順序進行程序的運作。但要注意，這個算法要當所有的程序都可以同時運作的時候才是最優的。比如有4個作業ABCD（假設度可以同時運作），他們的作業時間分别是1，2，4，8，我們按照ABCD的順序進行程序的排程即可得最優的平均周轉時間。 注意平均周轉時間的計算方法 (k a0 + (k - 1) a1 + (k - 2) a2 ... +)/k，其中a0，a1，a2...分别是第k個作業運作的時間，比如上述例子的最優平均周轉時間為 (4*1+3*2 + 2*4 +8)/4 = 6.5 當作業不能同時運作時，最短作業優先算法不一定是最優的，比如現在有5個作業，從A到E，運作時間分别是2，4，1，1和1，他們的到達時間是0，0，3，3和3，開始的時候我們隻能選擇A或者B運作，因為其他三個作業還沒有到達，使用最短作業優先。将按照ABCDE的順序開始運作，其平均等待時間是6.4，但是按照BCDEA的順序運作作業，其平均的等待時間則是6。 3. 最短剩餘時間優先 (shortest remaining time next) 這個算法是最短作業優先算法的搶占式的版本，使用這個算法的時候，排程程式總是選擇則剩餘運作時間最短的那個程序運作。再次提醒，有關的運作時間必須提前掌握。當一個新的作業到達打的時候，其整個時間同目前程序的剩餘時間進行比較。其程序的運作時間必須被提前知道，當一個新的作業到達的時候，其整個時間同目前程序的剩餘時間作比較。如果較新的程序比目前運作的程序需要更少的時間，目前程序就會被挂起，而運作新的程序。這種方式可以使新的短作業獲得良好的服務。 三. 互動式系統中的排程 1. 輪轉排程 最古老，最簡單，最公平而且使用最廣的算法是輪轉排程。每個程序被配置設定一個時間片（quantum），即允許該程序在該時間段中運作，如果時間片結束時該程序還在運作，則剝奪CPU并配置設定給另外一個程序。如果該程序在時間片結束前阻塞或者結束，則CPU立刻進行切換。如下圖所示：
Fig 2：輪轉排程：a) 可運作程序清單；b) 程序B用完時間片後的可運作程序清單 時間片長度的設定在輪轉排程裡面非常重要，因為從一個程序切換到另一個程序是需要一定的時間的——包括儲存和裝入寄存器的值以及記憶體映像。更新各種表格和清單，清除和重新調入記憶體高速緩存等。程序切換有時候也被稱為上下文切換。時間片設定得太短會導緻過多的程序切換。降低了CPU的效率；而設定得太長又會可能對短的互動請求的響應時間變長。 2. 優先級排程 輪轉排程隐含的假設是所有的程序都是相同的優先級的，通過動态地或者靜态地對程序設立優先級，我們可以實作優先級排程，優先級高的程序優先運作。 為了防止高優先級的程序無休止地運作下去，排程程式可以在每個時鐘周期結束時降低目前程序的優先級。如果這個動作導緻該程序的優先級低于次高優先級的程序。則進行程序切換。一個可采用的方法是，每個程序可以賦予一個允許運作的最大時間片。當這個時間片用完時，下一個次高優先級的優先級程序可以獲得機會運作。 靜态優先級可以通過預先評估程序的重要性來确定。而動态優先級的确定可以按照以下的方法進行處理：
Fig 3：有4個優先級類的排程算法 上圖的算法一目了然，就是把所有的程序分為四個優先級組，而在各類程序的内部采用輪轉排程。如圖3，隻要存在優先級為4的程序，則不會理會優先級3，2，1的程序。當優先級4的隊列為空後，才開始排程優先級3的程序。以此類推。 動态優先級排程要每隔一段時間調整程序的優先級，否則會發生饑餓。同時也要注意鎖封護和優先級反轉的問題。 3. 多級隊列 多級隊列實作的思想和優先級排程的思想類似，但是增加給不同優先級的配置設定不同的時間片。越低優先級配置設定的時間片越大，并且當一個程序用完被配置設定的時間後，會被降低一個優先級。這樣可以有效地讓短的互動程序讓出CPU。 而對于那些剛開始運作一段時間，然而後來又需要互動的程序，為了避免被永遠地懲罰。某些作業系統提供手動提高優先級的政策（比如按下F鍵可以提升優先級）。 4. 最短程序有限 如果我們把每一條執行的指令都看做是一個獨立的 “作業”，那麼我們就可以利用批處理系統的一個思想 “最短作業常常伴随着最短響應時間”，對程序的過去進行推測，并執行估計運作時間最短的那一個。假設某個終端上每條指令的估計運作時間為T0，現在假設測量到其下一次運作時間為T1。可以用這兩個值的權重和來改進估計時間。即aT0 + (1 - a)T1。通過選擇a的值，可以決定是盡快忘記老的運作時間，還是在一段唱的時間内記住他們。當a = 1/2時，可以得到如下序列：
T0 ，T0/2 + T1/2，T0/4 + T1/2 + T2/2，T0/8 + T1/8 + T2/4 + T3/2
可以看到三輪過後，T0在新的估計值中所占的比重下降到1/8，這樣的算法被稱為是老化 (aging) 。 5. 保證排程 保證排程是一個理想的排程，很難被實作。其基本實作思想是系統跟蹤每個程序自建立以來已使用了多少CPU時間。然後它計算各個程序應該獲得的CPU時間。即自建立以來的時間除以n，由于各個程序實際獲得的CPU時間是已知的。是以很容易計算出真正獲得的CPU時間和應該獲得的CPU的時間之比。比率為0.5說明一個程序隻獲得了應得時間的一半，而比率為2.0則說明它已經獲得了應得時間的兩倍。（理想情況是，在一個有n個程序的單使用者系統中，若所有的程序都等價。則每個程序将獲得1/n的CPU時間）。 6. 彩票排程 彩票排程的基本思想是向程序提供各種系統資源（如CPU時間）的彩票，一旦需要作出一項排程決策的時候，就随機抽出一張彩票，擁有該彩票的程序獲得該資源。在應用到CPU排程時候，系統可以掌握每秒鐘50次的一種彩票，作為獎勵每個獲獎者可以得到20ms的CPU時間。 彩票排程可以很簡單地實作優先級排程——隻要讓每個程序的彩票配額不一樣就可以了，有更多彩票的程序獲得CPU的幾率要更大一點。同時程序間也可以進行彩票交換，比如當一個程序請求IO而被阻塞時，它可以把彩票讓給另一個程序，讓另一個程序獲得更大的得到CPU的幾率。 7. 公平分享排程 我們上面所考慮到的排程算法都是針對單使用者的。比如使用者一有9個程序，而使用者2有1個程序，假設我們進行輪轉排程，那麼使用者1可以獲得90%的CPU的時間，但是使用者2隻能獲得10%的CPU時間。在多使用者的系統必須考慮不同使用者的CPU的時間配置設定。 四. 實時系統中的排程 實時系統是一種時間起着主導作用的系統。最典型的就是多媒體實時系統，當我們在播放CD時，必須在非常短的時間内将流轉換成音樂，如果轉換時間過長，那麼音樂就會産生問題。實時系統通常可以分為硬實時和軟實時，前者的含義是必須滿足絕對的截止時間，後者的含義是雖然不希望偶爾錯失截止時間，但是還可以容忍。 實時系統中的時間可以按照響應方式進一步分類為周期性（以規則的時間間隔發生）事件或者非周期（發生時間不可預知）事件。一個系統可能要響應多個周期性的事件流，系統可能無法響應所有事件。實時系統可排程的條件：
（有m個周期事件，事件i以周期Pi發生，并需要Ci秒CPU時間來處理事件），滿足這個條件的實時系統被稱為可排程的。 在實時系統中我們可以嘗試設定一個主要時鐘，該時鐘每秒滴答适當的次數，例如針對NTSC制式的視訊，每秒滴答30次，在時鐘的每一個觸發下，所有的程序都以相同的次序相繼運作，當一個程序完成其工作時，它将發出suspend系統調用釋放CPU直到主要時鐘再次觸發。當主要時鐘再次響應，所有的程序再次以相同的次序運作。隻要程序數較少，所有的工作都可以在一幀的時間内完成。采用輪轉排程就可以了。但是模型相當不靠譜，因為不同的程序可能以不同的頻率運作，具有不用的工作量，并且具有不同的最終時限。
Fig 4：三個周期性的程序，每個程序播放一部電影，每一部電影的幀率以及每幀的處理需求有所不同 一般實時排程模型：多個程序競争CPU，每個程序有自己的工作量和最終時限。假設系統知道每個程序必須以什麼樣的頻率運作，有多少工作要做以及下一個最終時限是什麼。多個互相競争的程序，其中若幹程序或者全部程序都必須滿足的最終時限的排程稱為是實時排程。 1. 速率單調排程（實時靜态算法） 速率單調排程算法（Rate Monotonic Scheduling，RMS）可以用于滿足以下條件的程序：
- 每個周期性程序必須在其周期内完成。
- 沒有程序依賴于任何其他程序。
- 每一個程序在一次突發中需要相同的CPU時間量。
- 任何非周期程序都沒有最終時限。
- 程序搶占時刻發生而沒有系統開銷。（理想模型）
單調速率算法按照以下規則給程序設立優先級：比如A程序每30ms運作一次，則每秒運作33次，則獲得優先級33；B程序每秒運作20次，則獲得優先級20，是以優先級與速率成線性關系，這就是這個算法的名字的來曆。RMS算法是最優的實時靜态算法中。 但是要注意的是，RMS算法并不是在什麼情況下都能正常運作的，下面會有一個RMS算法不能排程的情形。 Liu和Layland證明了在任何周期性程序系統，如果：
則RMS可以正常工作，随着m->無窮，那麼最大使用率就會逼近ln2。比如當m=3時，最大允許使用率為0.780，是以在三個周期性程序的系統中，當CPU使用率小于0.780，那麼RMS總可以工作的，但是反過來說，如果CPU使用率大于0.780，并不能說明RMS不能工作（對于特定的周期和運作時間可以的排程成功）。 2. 最早最終時限排程（實時動态算法） 最早最終時限優先算法（Earliest Deadline First，EDF）是一個動态算法，它不要求程序是周期性的，也不要求每個CPU突發具有相同的運作時間。隻要有一個程序需要CPU時間，它就宣布它的到來和最終時限。排程程式維持一個可運作的程序清單，該清單按最終時限排序，EDF算法運作清單中的第一個程序，也是具有最近最終時限的程序。當一個新的程序就緒時，系統進行檢查以了解其最終時限是否發生在目前運作的程序結束之前。如果是這樣，那麼新的程序就搶占目前正在運作的程序。 EDF算法對于任何一組可排程的程序總是可以工作的。
Fig 5：RMS和EDF排程執行個體1 在上述例子中，RMS和EDF算法都可以正常排程，對于RMS算法，前80ms的都是很好了解的，因為優先級A>B>C（A的優先級是33，B是25，C是20），是以我們隻用把ABC三個程序輪轉排程即可。注意A可以搶占B，B可以搶占C，是以在90ms的時候，A和B都處于就緒态，但是A的優先級要比B要高，是以A會搶占B，當A運作完以後，繼續運作C。 而對于EDF算法，在前90ms中，與RMS算法的處理結果都是一樣的，然而在90ms時，A和B選擇的最終時限都是一樣的，但是EDF算法規定，當目前運作的程序和其他程序的最終時限一樣時，不搶占目前運作的程序，防止而外的開銷，是以B繼續運作，然後B運作完以後排程A。
Fig 6：RMS排程失敗的例子 現在我們換一個例子，假設A程序每個周期運作15ms，而不是10ms，這個時候RMS算法就會排程失敗了，首先在RMS算法中，ABC的優先級不變，因為RMS算法中的優先級隻與程序的運作頻率有關，而與程序的運作時間是無關的。在t = 45ms的時候，排程B，而由于C的優先級低于B，是以C無法搶占B而錯過其最終時限。RMS算法排程失敗。 現在我們來看EDF算法，當t = 30時，A，B和C發生競争，而這個時候A的最終時限是60，B的最終時限是80，而C是50，是以排程算法決定排程C程序，當C程序運作完後其最終時限變為100，是以排程算法排程A，以此類推。當t = 90時，也發生了剛才A和B發生競争的情況，EDF選擇不切換程序，繼續運作B。 五. 線程排程 線程排程主要是分為使用者級線程排程和核心級線程排程，他們的差別就是在于核心是否認識到有不同的線程，如下圖所示：
Fig 7: a)使用者級線程的可能排程，有50ms時間片的程序以及每次運作5ms CPU的線程 b) 擁有相同特征的核心級線程的排程 對于使用者級線程，CPU給一個程序配置設定CPU後，由程序在使用者空間上控制線程的排程，這種排程不會影響其他程序，當這個程序的時間片用完後，核心會排程其他程序。而對于核心級線程，它不用考慮被排程的線程是屬于哪個程序的。這個時候時間片是線程擁有的。 使用者級線程和核心級線程的性能是有差别的。一般來說使用者級線程的切換非常輕松。但是對于核心級線程，線程切換需要儲存完整的上下文，修改記憶體映像，使高速緩存失效等操作。這些操作是費時的。
轉載于:https://www.cnblogs.com/Philip-Tell-Truth/p/6680529.html