想要資源嗎？求我啊~

調用處理器排程程式的前提是進入作業系統，處于系統态。而之前在中斷中提到，中斷是程序切換的前提，換句話說，作業系統是中斷驅動的。

處理器排程

處理器排程：CPU資源在可運作實體之間的配置設定。

在之前的程序和線程中提到過一點，程序是CPU配置設定的基本機關，線程是CPU配置設定的基本機關，看起來似乎是有沖突，但實際上，作業系統可見的線程是系統級的線程，也就是說，如果線程是在使用者級實作的，那麼作業系統實際排程的實體仍然是程序。（判斷哪一個是CPU的基本排程機關，隻需判斷該系統是否支援核心級的線程）

短程排程

短程排程是将處理器資源配置設定給程序或線程使其真正向前推進。

先解釋幾項參數名額：

1. 對處理器的一次連續使用稱為CPU陣發期，對裝置的一次連續使用稱為I/O陣發期。 （可以簡單的了解為使用處理器/裝置的時間）

2. 從計算任務就緒到處理完畢所用的時間稱為周轉時間。

3. 所有作業周轉時間與作業道數的比值稱為平均周轉時間。（可以了解為到目前計算任務為止的每個計算任務所需周轉時間之和除以這些計算任務的總數）

處理器排程算法

1. 先到先服務（FCFS）

   按照程序申請*CPU的順序*進行排程。

   是一個公平的算法，不會出現餓死的情況，但是缺點是短程序（線程）等待時間長，平均等待時間較長。

   和生活中買票場景相類似（假設售票處的票數無限），所有人都排隊買票，誰到的早，誰就能先買票。

   每人買一張票消耗一分鐘，假設有人隻買一張，有人要買幾十上百張票，此時，後到的買一張票的人會等很久，緻使最終所有排隊的人平均等待時間長。

2. 最短作業優先（SJF）

   按照CPU陣發時間遞增的次序排程，平均周轉時間短，且是不公平的，故而可能發生饑餓甚至是餓死。

   還是售票場景，此時排隊不是按照先來後到的順序，而是按照每個人所要購買票的數量進行排隊，購票數量少的排在前面，這樣做的後果是，購票數量多的人很可能要等很久，甚至因為前面的人太多而放棄購票。

3. 最短剩餘時間優先（SRTN）

   當CPU空閑時，選擇剩餘執行時間最短的程序或線程，新程序或線程到達時，比較與目前運作程序的估計剩餘時間，選擇剩餘時間最短的程序或線程。可以看出，此算法實質上是可剝奪式的的最短作業優先算法，不公平。

   繼續買票排隊，首先售票開始時，隻有一個人需要買3張票（買一張票假設需要一分鐘），一分鐘後來了第二個人要買一張票，此時第一個人還需要買兩張，比第二人的一張要多，故第二人可以插隊買一張票（買完走人），此時第三個人來了，需要買三張票，比第一人剩下的兩張要多，故第一人可以買完兩張走人，第三人開始買票。

   有圖有真相：

   

4. 最高響應比優先算法（HRN）

   是先到先服務和最短作業優先算法的折中方案，按照公式計算響應比，然後進行排程。

   響應比 = 1 + （等待時間 / CPU陣發時間）

   可以看出，同時到達的任務中，處理時間較短的任務将會被優先排程。

5. 最高優先數優先算法（HPF）

   為程序配置設定等級，用數字大小決定優先級别。

   優先數有兩種方法确定：

   • 靜态的優先數：每個程序進入系統時就被賦予了一個優先數，且在其生存期間是固定不變的，可以看出這種方法省時省力，但是公平性很差（低優先級的程序可能會長期等待）。
   • 動态優先數：每個程序建立時有一個優先數，但是在程序生存期間是可變化的，對應于靜态優先數的優缺點，可以看出這種方法公平，資源利用鍊率高，但頻繁變化，系統開銷就大了。

6. 循環輪轉算法（RR）

   和分時系統的部分思想有些類似，在這種算法中，系統會為每一個程序規定一個時間片，所有程序按照時間片的長度輪流運作（配置設定給就緒隊列中的每一個程序一個時間片，不論程序能否在這段時間内執行完成，都會被掐斷，如果能夠執行完成，那就沒有多餘動作，如果不行，則掐斷程序，将其放到隊尾等待下次配置設定）。

   循環輪轉還有分基本輪轉和改進輪轉，兩個輪轉的差別就在于配置設定給程序的時間平長度是否相同，是否可變長。

   這種算法很公平，而且響應及時，但是時間片的長度是必須要認真考慮的，否則胡亂配置設定，其好處就無從展現了。

   記得小時候在家做作業想看電視，老媽有規定，做一個小時作業，看半小時電視，看電視的時候，不論是不是看到精彩的地方，或者是還有幾十秒電視劇就演完了，老媽都會很準時的讓我去寫一個小時作業再說。

   這就是循環輪轉算法的一種思想展現（看來我很小的時候就已經接觸過這種算法了，話說，如果老一輩的人把這種思想早點弄到計算機上，那是不是就沒外國人啥事兒了）。

7. 分類排隊算法（MLQ）

   按照某種原則（如實時，分時等）加以分類，以實作所期望的排程目标，可以說，這個算法是以多個就緒程序隊列為特征的。

   隊列之間是順序執行的，但是隊列内部可以采用不同的算法來排程。

   高中的時候每年都有運動會，開幕式挺煩人的，想想看全校30多個班，上司在主席台上舒服的坐着，從高一1班開始，一直到高二16班，30多個班都要依次從體育場大門進場，途經主席台，繞着跑道走一圈到各班的位置，站着……

   按照班級分類，各班級之間是有序的，班級内部的人員調動那是班主任（排程算法）說了算，這就是分類排隊的思想。

8. 回報排隊算法（FB）

   都是排隊算法，這個也是以多個程序就緒隊列為特征的，且每個隊列通常都是采用循環輪轉算法，不過，在回報排隊算法中，程序是可以在不同的就緒隊列中移動的，适應性強。

   由于程序可以在就緒隊列中移動，是以這些就緒隊列需要設定優先級，而且優先級是遞減的，即有這種情況：

   一個程序被建立 -> 進入第一級就緒隊列 -> 使用完這一隊列的時間片，未結束 -> 進入下一級隊列

   注：如果到了最後一級隊列還沒結束，就進入同一級的就緒隊列，這種算法有幾個特點：

   • 短程序優先處理。
   • 裝置資源使用率高。
   • 系統開銷小。

你以為我要講故事呢啊，可笑！

好吧，接收嘲諷……高一某次運動會，由于長的帥，腿又長，還跑的快，于是被老師指定參加4x100接力賽，我當第一棒，槍響，沖刺，一切都進行的那麼順利，然而，當我跑到和第二棒交接的地方時，第二棒的小朋友刷的就沖出去了，最後回頭望了一眼發現我還在後面追才反應過來自己沒接上棒，這時候我都已經跑了四分之三的路程了。

這4x100就分給每人一百米的距離，我這都跑完配置設定給自己的路程了，最後還多占着第二棒的路程多跑了幾十米。

這種情況就是由于一些原因緻使程序無法在系統配置設定的時間片内結束，而移動到下一程序的隊列裡繼續執行。

中程排程

交換

交換是程序在記憶體和外存儲器之間的排程，其目标是：

1. 緩解記憶體空間等資源緊張的沖突。
2. 減小并發都以降低系統開銷。

由于交換是在記憶體和外存之間進行的，是以當程序被換到外存時，就出現了挂起态（就緒挂起，等待挂起）。

系統并發都過高時，将記憶體中的某些程序暫時交換到外存（挂起），直到系統并發度較低時再調回記憶體（解挂），這種交換也必須依據排程算法（好煩哦）。

長程排程

作業

長程排程又稱作作業排程，對應的功能是，将一個作業由輸入井調入記憶體，并為其建立相應的程序，使其具有運作的資格。

一個作業是由多個相對獨立的執行步驟組成的，這些步驟被稱為作業步 ，對應一個程序或線程。

作業有五種狀态，分别是： 1. 送出 2. 後備 3. 執行 4. 完成 5. 退出

其狀态之間的改變如圖：

其中，SPOOLing輸入/輸出對應假脫機輸入/輸出，兩段作業排程程式通常以系統程序的模式運作。

實時排程

實時排程需要滿足實時任務各自時間限制條件，有剝奪式和非剝奪式兩種。

實時排程分為随機性實時任務 ，由随機事件觸發，發生時刻不确定。周期性實施任務 ，隔固定時間發生一次。

幾項相關參數：

• 就緒時間：實施任務産生并可以開始處理的時間。
• 開始截止期：實施任務最遲開始處理的時間。
• 完成截止期：實時任務最遲完成的時間。
• 發生周期：發生周期性實時任務的間隔時間。

有一個小公式（必要條件）可以用來判斷多個周期性實時任務是否可排程。

其中Ci 為任務 Pi 的處理時間，Ti 為任務 Pi 的發生周期，Ci < Ti， i = 1,2,3…,n。

最早截止期優先排程（EDF）

該算法優先選擇完成截止期最早的實時任務，類似于最短剩餘時間優先算法，對于某個新到達的實時任務，如果其完成截止期先于正在運作任務的完成截止期，則重新配置設定處理器（剝奪）。而上述的小公式對于該算法而言是充分條件。

速率單調排程（RMS）

該算法面向周期性實時任務，是非剝奪式排程。該算法判斷多個周期性實時任務可排程的條件是：

RMS算法CPU使用率不如EDF算法，但是RMS算法省事（實作簡單，開銷小）。