我是一個行程調度器，
我的職責是調度計算機內所有的行程，為他們分配 CPU 資源，
1. 批處理時代
想當初，作業系統創造我時，只是打算讓我用 FCFS 調度演算法，簡單維護下行程的秩序，但我后來的發展，遠遠超過了他的想象，
1.1 FCFS
所謂 FCFS 就是「先來先服務（First Come First Serve）」，每個行程按進入記憶體的時間先后排成一隊，每當 CPU 上的行程運行完畢或者阻塞，我就會選擇隊伍最前面的行程，帶著他前往 CPU 執行，
就拿這幾個行程來說吧：
按照 FCFS 演算法，我就會就按 A，B，C，D，E這樣的順序來將他們送往 CPU：
這一演算法聽起來簡單又公平，然而好景不長，我收到了一個短行程的抱怨：”上次我前面排了一個長行程，等了足足 200 秒他才運行完，我只用 1 秒就運行結束了，就因為等他，我多花了這么長時間，太不值得了，”
我仔細一想， FCFS 演算法確實有這個缺陷——短行程的回應時間太長了，用戶互動體驗會變差，
所以我決定，更換調度演算法，
1.2 SPN
這次我設計的演算法叫做「短任務優先」（Shortest Process Next，SPN），每次選擇預計處理時間最短的行程，因此，在排隊的時候，我會把短行程從佇列里提到前面，
這一次，短行程得到了很好的照顧，行程的平均回應時間大大降低，我和作業系統都很滿意，
但長行程們不干了：那些短行程天天插隊，導致他們經常得不到 CPU 資源，造成了「饑餓」現象，
取消 SPN 演算法的呼聲越來越高，
這可是個大問題，FCFS 雖然回應時間長，但最后所有行程一定有使用 CPU 資源的機會，但 SPN 演算法就不一樣了，如果短行程源源不斷加入佇列，長行程們將永遠得不到執行的機會——太可怕了，
因此，短任務優先演算法需要得到改進，有什么方法既能照顧短行程，又能照顧長行程呢？
1.3 HRRN
經過和作業系統的討論，我們決定綜合考量行程的兩個屬性：等待時間和要求服務時間——等待時間長，要求服務時間短（就是短行程）的行程更容易被選中，
為了量化，我們制定了一個公式：回應比 = （等待時間+要求服務時間）/ 要求服務時間，回應比高的演算法會先執行，我們稱之為「高回應比優先」（Highest Response Ratio Next，HRRN），
這個演算法得到了長短行程的一致好評，雖然我的作業量增加了（每次調度前，我都要重新計算所有等待行程的回應比）但為了行程們的公平性，這一切都是值得的，
2. 并發時代
新時代到了，
隨著計算機的普及，個人用戶大量增長，并發，即一次運行多個程式的需求出現了，這可難倒我了——處理器只有一個，怎么運行多個程式？
所幸 CPU 點醒了我：“我現在的運算速度既然這么快，何不發揮這項長處，弄一個「偽并行」出來？“
“偽并行？什么意思”
“就是看起來像并行，實際上還是串行，每個行程短時間交替使用我的資源，但在人類看來，這些行程就像在「同時」運行，”
我恍然大悟，
2.1 RR
經過 CPU 的提醒，我很快制定出了新的調度演算法——時間片輪轉演算法（Round Robin，RR），
在這個演算法里，每個行程將輪流使用 CPU 資源，只不過在他們開始運行時，我會為他們打開定時器，如果定時器到時間（或者執行阻塞操作），行程將被迫「下機」，切換至下一個行程，至于下一個行程的選擇嘛，直接用 FCFS 就好了，
新的演算法必然會面臨新的問題，現在我的問題就是，時間片的長度怎么設計？
直觀來看，時間片越短，固定時間里可運行的行程就越多，可 CPU 說過，切換行程是要消耗他不少指令周期的，時間片過短會導致大量 CPU 資源浪費在切換背景關系上，時間片過長，短互動指令回應會變慢，所以具體怎么取，還得看互動時間大小（感覺像沒說一樣，但至少給了個標準嘛），
這一階段，我的作業量大大提升——以前十幾秒都不用切換一次程式，現在倒好，一秒鐘就得切換數十次，
2.2 VRR
時間片輪轉演算法看起來十分公平——所有的行程時間片都是一樣的，但事實真是這樣嗎？
I/O 密集型行程不這么認為，他對我說：“調度器大哥，時間片輪轉沒有照顧到我們這類行程啊！我們經常在 CPU 沒呆到一半時間片，就遇到了阻塞操作，被你趕下去，而且我們在阻塞佇列，往往要停留很長時間，等阻塞操作結束，我們還得在就緒佇列排好長時間隊，那些處理器密集型行程，使用了大部分的處理器時間，導致我們性能降低，回應時間跟不上”
考慮到這些行程的要求，我決定為他們創建一個新的輔助佇列，阻塞解除的行程，將進入這個輔助佇列，進行行程調度時，優先選擇輔助佇列里的行程，
這就是「虛擬輪轉法」（Virtual Round Robin，VRR），
從后來實際性能結果來看，這種方法確實優于輪轉法，我頗為自豪，
2.3 優先級調度
有一天，作業系統忽然找到我，神神秘秘的說：“調度器啊，你是知道的，我要給整個系統提供服務，可最近用戶行程太多，導致我的服務行程有時候回應跟不上，我有點擔心這會給系統穩定性造成影響，”
我一聽，這可是個大事，系統不穩定那還得了？調度演算法得換！
既然要讓作業系統的服務得到足夠的運行資源，那就，干脆讓他們具有最高的 CPU 使用優先權吧，
優先級調度演算法就此產生了，
我向大家做出了規定——每個行程將被賦予一個優先級，自己根據自己的情況確定優先級數值，但是，用戶行程的優先級不準高于內核行程的優先級，
切換程式的時候，我會從優先級 1 的佇列里選擇一個行程，如果優先級 1 佇列為空，才會選擇優先級 2 中的行程，以此類推，
當然，為了保證低優先級行程不會饑餓，我會調高等待時間長的行程的優先級，
使用這個演算法，我更忙碌了，不僅需要大量切換行程，還需要動態調節優先級，可能這就是能力越大，責任越大吧，
不過我知道，正是因為我的存在，人類才能在計算機上運行多道程式——這令我感到自豪，
希望你在看完我的文章之后有所識訓，
感謝你的閱讀，我們后會有期！
宣告：原創文章，未經授權，禁止轉載
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71564.html
標籤：C
上一篇：C語言實作去除字串首尾空格
下一篇：C語言交換兩個指標所指位置的數值