操作系統簡介
嘿哈布爾！ 我想提請您注意一系列文章——我認為是一本有趣的文學作品的翻譯——OSTEP。 本材料非常深入地討論了類 unix 操作系統的工作，即與進程、各種調度程序、內存和構成現代操作系統的其他類似組件一起工作。 你可以在這裡看到所有材料的原件 . 請注意，翻譯是非專業的（相當隨意），但我希望我保留了一般意思。
關於這個主題的實驗室工作可以在這裡找到：
其他部分：
您也可以查看我的頻道 =)
規劃：多級反饋隊列
在本次講座中，我們將討論開發最著名的方法之一的問題
規劃，這就是所謂的 多級反饋隊列 （MLFQ）。 MLFQ 調度程序於 1962 年由 Fernando J. Corbató 在一個名為
兼容的分時系統（CTSS）。 這些作品（包括後來的作品
Multics）隨後被提名為圖靈獎。 調度程序是
隨後改進並獲得了現有的外觀
一些現代系統。
MLFQ 算法嘗試解決兩個基本的重疊問題。
首先，它試圖優化周轉時間，正如我們在上一講中討論的那樣，它是通過從隊列最前面開始的方法來優化的
短期任務。 然而，操作系統不知道這個或那個進程將運行多長時間，並且這個
操作SJF、STCF算法的必要知識。 其次, MLFQ 嘗試
使系統對用戶做出響應（例如，對於坐著的用戶）
等待任務完成時盯著屏幕），從而最大限度地減少時間
回复。 不幸的是，像 RR 這樣的算法減少了響應時間，但是
對周轉時間指標產生不良影響。 因此我們的問題是：如何設計
可以滿足我們的要求但同時又一無所知的調度程序
一般過程的性質？ 調度器如何學習任務的特徵，
它啟動哪個從而做出更好的調度決策？
問題的本質：在知識不完善的情況下如何規劃任務的設置？
如何設計一個同時最小化響應時間的調度程序
用於交互式任務，同時在不知情的情況下最大限度地減少周轉時間
了解任務執行時間？
注：從以往的事件中吸取教訓
MLFQ 隊列是一個很好的系統示例，該系統經過以下訓練：
過去的事件可以預測未來。 此類方法常常
發現於操作系統（以及計算機科學的許多其他分支，包括分支
硬件預測和緩存算法）。 類似的行程
當任務具有行為階段並因此可預測時觸發。
然而，人們應該小心使用這種技術，因為預測非常容易。
可能會被證明是錯誤的，並導致系統做出比
將完全沒有知識。
MLFQ：基本規則
考慮 MLFQ 算法的基本規則。 儘管該算法的實現
有幾種，基本方法是相似的。
在我們將考慮的實現中，MLFQ 將有幾個
單獨的隊列，每個隊列都有不同的優先級。 任何時候，
準備執行的任務位於一個隊列中。 MLFQ 使用優先級，
決定運行哪個任務來執行，即具有更高的任務
優先級（隊列中優先級最高的任務）將首先啟動
隊列。
當然，一個特定隊列中可以有多個任務，所以
因此他們將具有相同的優先級。 在這種情況下，將使用該機制
RR 用於這些任務中的啟動計劃。
因此，我們得出 MLFQ 的兩個基本規則：
- 規則1：如果優先級（A）>優先級（B），則任務A將被啟動（B將不會）
- 規則2：如果優先級(A) = 優先級(B)，則A&B使用RR啟動
基於上述，規劃 MLFQ 的關鍵要素是
是優先事項。 而不是給每個人一個固定的優先級
任務時，MLFQ 根據觀察到的行為改變其優先級。
例如，如果某個任務在等待鍵盤輸入時不斷在 CPU 上退出，
MLFQ 將保持進程優先級高，因為這就是
交互過程應該有效。 相反，如果任務是持續不斷的
長時間是CPU密集型的，MLFQ會降級它
優先權。 因此，MLFQ 將研究進程運行時的行為
和使用行為。
讓我們畫一個例子來說明隊列在某個時刻可能是什麼樣子
時間然後你會得到這樣的東西：
在該方案中，2個進程A和B位於具有最高優先級的隊列中。 過程
C 位於隊列的中間，進程 D 位於隊列的最後。 根據上述
根據 MLFQ 算法的描述，調度器只會執行具有最高優先級的任務
根據RR優先級，任務C、D將無法工作。
當然，靜態快照無法全面了解 MLFQ 的工作原理。
準確理解情況如何隨時間變化非常重要。
嘗試 1：如何更改優先級
此時，您需要決定MLFQ將如何改變優先級
任務（以及任務在隊列中的位置）在其生命週期內。 為了
其中，您需要記住工作流程：一定數量
運行時間短的交互式任務（因此頻繁發布
CPU）和幾個長時間使用 CPU 的任務，同時
此類任務的響應時間並不重要。 這樣你就可以進行第一次嘗試
使用以下規則實現 MLFQ 算法：
- 規則3：當一個任務進入系統時，它被放入具有最高優先級的隊列中
- 優先事項。
- 規則 4a：如果任務使用其整個時間窗口，那麼它
- 優先級降低。
- 規則 4b：如果任務在其時間窗口到期之前釋放 CPU，則它
- 保持相同的優先級。
示例 1：單個長時間運行的任務
從這個例子中可以看出，准入任務設置為最高
優先事項。 經過 10ms 的時間窗口後，進程的優先級會降低。
調度程序。 在下一個時間窗口之後，任務最終降級為
系統中的最低優先級，保留在原處。
示例 2：選擇一個簡短的任務
現在讓我們看一個 MLFQ 如何嘗試接近 SJF 的示例。 在那裡面
例如，兩個任務：A，這是一個持續長時間運行的任務
佔用CPU和B，是一個短交互任務。 認為
當任務 B 到達時，A 已經運行了一段時間。
該圖顯示了該場景的結果。 任務 A 與任何任務一樣，
CPU使用率處於最低水平。 任務 B 將在時間 T=100 到達並且將
放入最高優先級隊列。 由於它的運行時間很短，那麼
它將在到達最後一個隊列之前完成。
從這個例子中，你應該明白該算法的主要目標：因為該算法不
知道一項長任務或短任務，那麼首先他假設該任務
短並給予它最高優先級。 如果這真的是一個很短的任務，那麼
它會執行得很快，否則如果它是一個很長的任務，它會緩慢地執行
優先級下降，很快就會證明她確實是一個長期的任務，不
需要回應。
示例 3：I/O 怎麼樣？
現在讓我們看一個 I/O 示例。 如規則 4b 中所述，
如果進程在沒有使用其所有處理器時間的情況下釋放處理器，
然後它保持相同的優先級。 這條規則的意圖非常簡單。
- 如果交互式作業執行大量 I/O，例如等待
從用戶擊鍵或鼠標，這樣的任務將釋放處理器
在指定的窗口之前。 我們不想降低此類任務的優先級，
因此它將保持在同一水平。
此示例展示了算法如何處理此類進程 - 交互式任務 B，執行前只需要 CPU 1 毫秒
I/O 進程和一個長時間佔用 CPU 的作業 A。
MLFQ 使進程 B 保持最高優先級，因為它繼續
釋放CPU。 如果B是一個交互任務，那麼本例的算法就達到了
其目的是快速啟動交互式任務。
當前MLFQ算法存在的問題
在前面的示例中，我們構建了 MLFQ 的基本版本。 而且他似乎
很好、公平地完成了它的工作，在之間公平地分配 CPU 時間
長任務並允許短任務或訪問頻繁的任務
快速處理 I/O。 不幸的是，這種方法包含幾個
嚴重的問題。
首先、飢餓問題：如果系統有很多交互
任務，它們會消耗所有的CPU時間，因此不會有一個長的任務
該任務將沒有機會被執行（他們正在挨餓）。
其次，聰明的用戶可以編寫他們的程序，以便
愚弄調度程序。 欺騙在於為了強迫而做某事
調度程序給進程更多的CPU時間。 該算法
上面描述的很容易受到此類攻擊：在時間窗口實際上之前
結束後，需要執行一次I/O操作（對某些，無論是哪個文件）
從而釋放CPU。 這樣的行為會讓你保持在同樣的狀態
隊列本身並再次獲得更大百分比的 CPU 時間。 如果你這樣做
這是正確的（例如，在釋放 CPU 之前運行 99% 的窗口時間），
這樣的任務可以簡單地獨占處理器。
最後，程序可以隨著時間的推移改變其行為。 那些任務
其中使用了CPU就可以變成交互式的。 在我們的例子中，類似
任務不會像其他任務那樣從調度程序中得到應有的待遇
（原始）交互式任務。
向觀眾提問：在現代世界中，可以對調度程序進行哪些攻擊？
嘗試 2：提高優先級
讓我們嘗試改變規則，看看是否可以避免出現問題
禁食。 我們可以做什麼來確保相關
CPU 任務將得到它們的時間（即使不長）。
作為問題的簡單解決方案，您可以定期提出建議
增加系統中所有此類任務的優先級。 有很多方法
為了實現這一點，讓我們嘗試實現一些簡單的例子：
所有任務同時具有最高優先級，因此新規則：
- 規則5：經過一段時間S後，將系統中的所有任務轉移到最高隊列。
我們的新規則同時解決了兩個問題。 一、流程
保證不會挨餓：最高隊列中的任務將共享
根據 RR 算法的處理器時間，因此所有進程都會收到
處理器時間。 其次，如果以前使用過某個進程
只有處理器變得交互，它才會保留在最高的隊列中
收到後優先級一次性增加到最高。
考慮一個例子。 在這種情況下，考慮使用單個進程
CPU 和兩個交互的短進程。 在圖中的左側，該圖顯示了沒有優先級提升的行為，因此在兩個交互式任務到達系統後，長時間運行的任務開始飢餓。 在右圖中，每 50ms 執行一次優先級增加，因此所有進程都保證接收處理器時間並定期啟動。 本例以50ms為例，實際這個數字要高一些。
顯然，加上週期性增加時間S導致
邏輯問題：應該設置什麼值？ 當之無愧的其中之一
系統工程師 John Ousterhout 將系統中類似的量稱為“voo-doo”
恆定，因為它們在某種程度上需要黑魔法才能正確
接觸。 而且，不幸的是，S有這樣的味道。 如果您也設置了該值
大而長的任務將會挨餓。 如果你把它設置得太低，
交互式任務將無法獲得正確的 CPU 時間。
嘗試 3：更好的會計
現在我們還有一個問題需要解決：如何不
讓我們的調度程序被愚弄？ 造成這種可能性的人是
規則 4a、4b 允許作業通過釋放處理器來保持其優先級
在指定的時間到期之前。 怎麼處理呢？
這種情況下的解決方案可以被認為是更好地計算每個節點上的 CPU 時間
MLFQ 級別。 而不是忘記程序使用的時間
處理器分配的時間間隔，您應該考慮並保存它。 後
該進程已用完分配的時間，應將其降級到下一個進程
優先級。 現在，進程如何使用其時間並不重要 - 如何
不斷地在處理器上計算或作為一組調用。 因此，
規則 4 應重寫如下：
- 規則4：任務用完當前隊列中分配的時間後（無論它釋放了多少次CPU），該任務的優先級都會降低（它在隊列中向下移動）。
讓我們看一個例子：
»
該圖顯示瞭如果您嘗試像這樣欺騙調度程序會發生什麼
如果按照前面的規則4a、4b，將會得到左邊的結果。 新快樂
規則就是右邊的結果。 在保護之前，任何進程都可以在完成之前調用 I/O，並且
因此，在啟用保護後，無論行為如何，都可以控制 CPU
I/O，他仍然會在隊列中向下移動，因此無法不誠實地
接管CPU資源。
改善MLFQ等問題
經過上述改進，出現了新的問題：主要問題之一
問題 - 如何參數化這樣的調度程序？ 那些。 應該是多少
隊列？ 隊列中程序窗口的大小應該是多少？ 如何
計劃通常應優先考慮，以避免飢餓和
考慮到程序行為的變化？ 這些問題沒有簡單的答案
回答並且僅對負載和後續配置進行實驗
調度程序可以帶來一些令人滿意的平衡。
例如，大多數 MLFQ 實現允許您分配不同的
不同隊列的時間段。 高優先級隊列通常是
間隔短。 這些隊列由交互式任務組成，
之間的切換非常敏感，應該需要 10 或更少
多發性硬化症。 相反，低優先級隊列由長時間運行的任務組成，這些任務使用
中央處理器。 在這種情況下，長時間間隔非常合適（100 毫秒）。
在此示例中，有 2 個任務在高優先級隊列 20 中工作
ms 分為 10ms 窗口。 中間隊列（40ms 窗口）和低優先級隊列 20ms
隊列時間窗口變為 40 毫秒，任務完成其工作。
MLFQ 在 Solaris OS 中的實現是一類分時調度程序。
調度程序將提供一組表來準確定義它應該如何進行
改變進程在其生命週期中的優先級，大小應該是多少
分配的窗口以及您需要提高任務優先級的頻率。 行政人員
系統可以與該表進行交互並使調度程序發揮作用
不同。 該表默認有60個隊列，並逐漸增加
窗口大小從 20 毫秒（高優先級）到幾百毫秒（低優先級），以及
還每秒提升所有任務一次。
其他 MLFQ 調度程序不使用表或任何特定的
相反，本章中描述的規則，它們使用以下方法計算優先級
數學公式。 例如，FreeBSD 中的調度程序使用以下公式：
根據進程的多少計算當前任務的優先級
使用了CPU。 此外，CPU 使用率會隨著時間的推移而下降，因此
因此，優先級增加與上面描述的有些不同。 這是真實的
稱為衰減算法。 從版本 7.1 開始，FreeBSD 使用 ULE 調度程序。
最後，許多規劃師還有其他功能。 例如，一些
調度程序為操作系統的操作保留更高的級別，從而
因此，任何用戶進程都無法獲得最高優先級
系統。 有些系統允許您提供建議以提供幫助
規劃者可以正確設置優先級。 例如，使用命令 尼斯
您可以增加或減少任務的優先級，從而增加或減少
減少程序佔用CPU時間的機會。
MLFQ：總結
我們描述了一種稱為 MLFQ 的規劃方法。 他的名字
總結操作原理 - 它有多個隊列並使用反饋
確定任務的優先級。
規則的最終形式如下：
- 規則1：如果優先級（A）>優先級（B），則任務A將啟動（B將不會）
- 規則2：如果優先級(A) = 優先級(B)，則A&B使用RR啟動
- 規則3：當任務進入系統時，被放入最高優先級隊列中。
- 規則4：任務用完當前隊列中分配的時間後（無論它釋放了多少次CPU），該任務的優先級都會降低（它在隊列中向下移動）。
- 規則5：經過一段時間S後，將系統中的所有任務轉移到最高隊列。
MLFQ 很有趣，原因如下 - 而不是需要有關以下內容的知識
提前了解任務的性質，算法學習任務過去的行為並設置
相應的優先事項。 因此，他嘗試同時坐在兩把椅子上 - 實現小任務（SJF、STCF）的表現並誠實地運行長任務，
CPU 負載作業。 因此，許多系統，包括 BSD 及其衍生產品，
Solaris、Windows、Mac 使用某種形式的算法作為調度程序
MLFQ 作為基線。
其他材料：
- （計算）
來源： www.habr.com