操作系統簡介
嘿哈布爾！ 我想提請您注意一系列文章——我認為是一本有趣的文學作品的翻譯——OSTEP。 本材料非常深入地討論了類 unix 操作系統的工作，即與進程、各種調度程序、內存和構成現代操作系統的其他類似組件一起工作。 你可以在這裡看到所有材料的原件 . 請注意，翻譯是非專業的（相當隨意），但我希望我保留了一般意思。
關於這個主題的實驗室工作可以在這裡找到：
其他部分：
您也可以查看我的頻道 =)
調度器簡介
問題的本質：如何制定調度器策略
底層的調度策略框架該如何設計？ 關鍵假設應該是什麼？ 哪些指標很重要？ 早期計算系統使用了哪些基本技術？
工作負載假設
在討論可能的策略之前，我們首先對系統中運行的進程進行一些簡單的題外話，這些進程統稱為 工作量。 定義工作負載是建立策略的關鍵部分，您對工作負載了解得越多，就能寫出更好的策略。
讓我們對系統中運行的進程（有時也稱為 工作 （任務）。 幾乎所有這些假設都不現實，但卻是思想發展所必需的。
- 每個任務運行相同的時間，
- 所有任務同時設定，
- 分配的任務一直持續到完成為止，
- 所有任務僅使用CPU，
- 每個任務的運行時間是已知的。
調度程序指標
除了一些關於負荷的假設之外，還需要另一個用於比較不同調度策略的工具：調度程序指標。 度量只是對某事物的某種度量。 有許多指標可用於比較調度程序。
例如，我們將使用一個名為 週轉時間 （週轉時間）。 任務週轉時間定義為任務完成時間與任務到達系統時間之間的差異。
T週轉=T完成-到達
由於我們假設所有任務同時到達，則 Ta=0，因此 Tt=Tc。 當我們改變上述假設時，這個值自然會改變。
另一個指標—— 公平 （公平、誠實）。 生產力和公平性往往是規劃中對立的特質。 例如，調度程序可能會優化效能，但代價是等待其他任務運行，從而降低公平性。
先進先出 (FIFO)
我們可以實現的最基本的演算法稱為 FIFO 或 先來（進來），先服務（出去）。 該演算法有幾個優點：它非常容易實現，它符合我們所有的假設並且很好地完成了工作。
讓我們來看一個簡單的例子。 假設同時設定了 3 個任務。 但我們假設任務 A 比其他任務早到達一點，因此它會比其他任務更早出現在執行清單中，就像 B 相對於 C 一樣。假設它們每個都會執行 10 秒。 在這種情況下，完成這些任務的平均時間是多少？
透過計算值 - 10+20+30 並除以 3，我們得到平均程式執行時間等於 20 秒。
現在讓我們試著改變我們的假設。 特別是假設 1，因此我們將不再假設每個任務需要相同的時間來執行。 這次 FIFO 會表現如何呢？
事實證明，不同的任務執行時間對 FIFO 演算法的生產力有極為負面的影響。 假設任務 A 需要 100 秒才能完成，而任務 B 和 C 仍各需要 10 秒。
從圖中可以看出，系統的平均時間為(100+110+120)/3=110。 這種效應稱為 護航效應，當資源的一些短期消費者將在重度消費者之後排隊。 這就像雜貨店裡的排隊隊伍，前面有一位顧客推著滿滿的購物車。 解決問題的最好方法是嘗試更換收銀機或放鬆深呼吸。
最短工作優先
是否有可能以某種方式解決重量級流程的類似情況？ 當然。 另一種類型的規劃稱為最短工作優先 （SJF）。 它的演算法也相當原始——顧名思義，最短的任務會先啟動，一個接著一個。
在此範例中，運行相同進程的結果將是平均程式週轉時間的改進，它將等於 50 個而不是 110 個，幾乎好 2 倍。
因此，對於所有任務同時到達的給定假設，SJF 演算法似乎是最優演算法。 然而，我們的假設似乎仍然不切實際。 這次我們改變假設 2，這次假設任務可以隨時出現，而不是同時出現。 這會導致什麼問題？
假設任務 A (100c) 首先到達並開始執行。 在 t=10 時，任務 B 和 C 到達，每個任務需要 10 秒。 因此，平均執行時間為 (100+(110-10)+(120-10))3 = 103。調度程序可以採取什麼措施來改善這一點？
最短完成時間優先 (STCF)
為了改善這種情況，我們省略了假設 3，即程式已啟動並運行直至完成。 此外，我們需要硬體支持，正如您可能猜到的，我們將使用 計時器 中斷正在運行的任務並 上下文切換。 因此，調度器可以在任務 B、C 到達時做一些事情——停止執行任務 A，將任務 B 和 C 放入處理中，並在完成後繼續執行進程 A。這樣的調度器稱為 STCF或 搶佔式作業優先.
此規劃器的結果將是下列結果：((120-0)+(20-10)+(30-10))/3=50。 因此，這樣的調度程序對於我們的任務來說變得更加最佳化。
指標回應時間
因此，如果我們知道任務的運行時間並且這些任務只使用CPU，STCF將是最好的解決方案。 在早期，這些演算法運行得很好。 然而，用戶現在大部分時間都在終端上度過，並期望獲得高效的互動體驗。 於是，一個新的衡量標準誕生了—— 回應時間 (回覆).
回應時間計算如下：
響應=T首次運行−到達
因此，對於前面的範例，回應時間將為：A=0、B=0、C=10 (abg=3,33)。
事實證明，STCF 演算法在 3 個任務同時到達的情況下不太好——它必須等到小任務完全完成。 因此，此演算法對於週轉時間指標有利，但對於互動性指標不利。 想像一下，如果您坐在終端前嘗試在編輯器中輸入字符，卻必須等待 10 秒以上，因為其他任務正在佔用 CPU。 這不是很愉快。
那麼我們面臨另一個問題——如何建立一個對響應時間敏感的調度器？
循環賽
開發了一種演算法來解決這個問題 循環賽 （RR）。 基本想法非常簡單：我們不是運行任務直到任務完成，而是運行任務一段時間（稱為時間片），然後切換到佇列中的另一個任務。 該演算法重複其工作，直到完成所有任務。 在這種情況下，程式的運行時間必須是定時器中斷程序的時間的倍數。 例如，如果定時器每x=10ms中斷一個進程，那麼進程執行視窗的大小應該是10的倍數並且是10,20或x*10。
讓我們來看一個例子：ABC 任務同時到達系統，每個任務都想運作 5 秒。 SJF 演算法將完成每項任務，然後再開始另一項任務。 相較之下，啟動視窗 = 1s 的 RR 演算法將完成以下任務（圖 4.3）：
（再次 SJF（不利於反應時間）
（循環法（有利於反應時間）
RR演算法的平均回應時間為(0+1+2)/3=1，而SJF演算法的平均回應時間為(0+5+10)/3=5。
可以合理地假設時間窗口是 RR 的一個非常重要的參數；時間窗口越小，反應時間越長。 但是，不應將其設定得太小，因為上下文切換時間也會影響整體效能。 因此，執行視窗時間的選擇由作業系統架構師設置，並且取決於計劃在其中執行的任務。 切換上下文並不是唯一浪費時間的服務操作 - 正在運行的程式還對許多其他東西進行操作，例如各種緩存，並且每次切換都需要保存和恢復此環境，這也可能需要花費大量時間。
如果我們只討論回應時間指標，RR 是一個很棒的排程器。 但是，該演算法的任務週轉時間指標將如何表現？ 考慮上面的例子，當A、B、C的運行時間=5s並且同時到達。 任務 A 將在 13 秒結束，B 將在 14 秒結束，C 將在 15 秒結束，平均週轉時間為 14 秒。 因此，RR 是周轉指標最差的演算法。
更一般地說，任何 RR 類型的演算法都是公平的；它在所有進程之間平均分配 CPU 時間。 因此，這些指標不斷地相互衝突。
因此，我們有幾種對比演算法，同時仍然有幾個假設 - 任務時間已知且任務僅使用 CPU。
與 I/O 混合
首先，我們去掉假設4，即進程只使用CPU；當然，情況並非如此，進程可以存取其他設備。
當任何進程請求 I/O 操作時，該進程就會進入阻塞狀態，等待 I/O 完成。 如果I/O發送到硬碟，那麼這個操作可能需要長達幾毫秒甚至更長的時間，而此時處理器將處於空閒狀態。 在此期間，調度程序可以讓任何其他進程佔用處理器。 調度程序必須做出的下一個決定是進程何時完成其 I/O。 當這種情況發生時，就會發生中斷，作業系統會將呼叫 I/O 的進程置於就緒狀態。
讓我們看一下幾個任務的範例。 它們每個都需要 50ms 的 CPU 時間。 然而，第一個將每 10ms 訪問一次 I/O（也將每 10ms 執行一次）。 而進程B只是使用一個沒有I/O的50ms處理器。
在此範例中，我們將使用 STCF 調度程式。 如果在調度程序上啟動像 A 這樣的進程，調度程序將如何表現？ 他將執行以下操作：首先他將完成流程 A，然後完成流程 B。
解決這個問題的傳統方法是將進程 A 的每個 10 ms 子任務視為單獨的任務。 因此，當開始使用 STJF 演算法時，50 ms 任務和 10 ms 任務之間的選擇是顯而易見的。 然後，當子任務A完成時，進程B和I/O將被啟動。 I/O 完成後，習慣上會再次啟動 10ms 的進程 A，而不是進程 B。這樣就可以實現重疊，即在第一個進程等待 CPU 的同時，CPU 被另一個進程使用。輸入/輸出。 結果，系統得到了更好的利用——在互動式進程等待 I/O 的時刻，其他進程可以在處理器上執行。
神諭已不復存在
現在讓我們試著擺脫任務運行時間已知的假設。 這通常是整個清單中最糟糕和最不切實際的假設。 事實上，在一般的普通作業系統中，作業系統本身通常對任務的執行時間知之甚少，那麼在不知道任務執行時間的情況下如何建立調度器呢？ 或許我們可以用一些RR原理來解決這個問題？
總
我們研究了任務調度的基本思想，並研究了 2 個調度程序系列。 第一個首先啟動最短的任務，從而增加週轉時間，而第二個則在所有任務之間平均分配，從而增加回應時間。 兩種演算法都不好，而其他系列的演算法都很好。 我們也研究了CPU和I/O的平行使用如何提高效能，但沒有解決作業系統千里眼的問題。 在下一課中，我們將介紹一個回顧剛剛過去並嘗試預測未來的規劃器。 這就是所謂的多層回饋隊列。
來源： www.habr.com