# 調度，第 1 部分：調度過程 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Scheduling%2C-Part-1%3A-Scheduling-Processes> ## 關于調度的思考。 [CPU 調度](https://en.wikipedia.org/wiki/Scheduling_(computing))是有效選擇在系統 CPU 內核上運行哪個進程的問題。在繁忙的系統中，將有比 CPU 內核更多的可立即運行的進程，因此系統內核必須評估應該在 CPU 上運行哪些進程以及哪些進程應放在就緒隊列中以便稍后執行。 多線程和多 CPU 內核的額外復雜性被認為是對這個初始展示的干擾，因此在此忽略。 非母語人士的另一個問題是“時間”的雙重含義：“時間”一詞可用于時鐘和經過時間的上下文。例如“第一個過程的到達時間是上午 9 點。”并且，“算法的運行時間是 3 秒”。 ## 如何測量調度以及哪種調度程序最佳？ 調度會影響系統的性能，特別是系統的 _ 延遲 _ 和 _ 吞吐量 _。吞吐量可以通過系統值來度量，例如 I / O 吞吐量 - 每秒寫入的字節數，或者每單位時間可以完成的小進程數，或者使用更高級別的抽象，例如客戶數量每分鐘處理的記錄。延遲可以通過響應時間（進程可以開始發送響應之前的經過時間）或等待時間或周轉時間（完成任務所經過的時間）來度量。不同的調度程序提供不同的優化權衡，可能適合或不適合所需的使用 - 沒有針對所有可能的環境和目標的最佳調度程序。例如，“shortest-job-first”將最小化所有作業的總等待時間，但在交互式（UI）環境中，最好將響應時間最小化（以某些吞吐量為代價），而 FCFS 看起來直觀公平且易于實現但是遭遇了康宏效應。 ## 什么是到達時間？ 進程首次到達就緒隊列并準備開始執行的時間。如果 CPU 空閑，則到達時間也將是執行的開始時間。 ## 什么是先發制人？ 在沒有搶占的情況下，進程將一直運行，直到它們無法再進一步利用 CPU。例如，以下條件將從 CPU 中刪除進程，并且可以為其他進程調度 CPU：進程由于信號而終止，被阻塞等待并發原語或正常退出。因此，一旦調度了一個進程，即使具有高優先級的另一個進程（例如，較短的作業）出現在就緒隊列上，它也將繼續。 通過搶占，如果將更優選的進程添加到就緒隊列，則可以立即移除現有進程。例如，假設在 t = 0 時使用 Shortest Job First 調度程序，有兩個進程（P1 P2），執行時間為 10 和 20 ms。 P1 已預定。 P1 立即創建一個新進程 P3，執行時間為 5 毫秒，并將其添加到就緒隊列中。沒有先發制人，P3 將在 10ms 后運行（P1 完成后）。通過搶占，P1 將立即從 CPU 中逐出，而是放回到就緒隊列中，而 P3 將由 CPU 執行。 ## 哪些調度員遭受饑餓？ 任何使用優先級形式的調度程序都可能導致饑餓，因為可能永遠不會調度早期進程（分配 CPU）。例如，對于 SJF，如果系統繼續有許多要安排的短作業，則可能永遠不會安排更長的作業。這一切都取決于[類型的調度程序](https://en.wikipedia.org/wiki/Scheduling_(computing)#Types_of_operating_system_schedulers)。 ## 為什么可以將一個進程（或線程）放在就緒隊列上？ 當一個進程能夠使用 CPU 時，該進程被置于就緒隊列中。一些例子包括： * 阻止進程等待存儲或套接字中的`read`完成，現在可以使用數據。 * 已創建新進程并準備啟動。 * 進程線程在同步原語（條件變量，信號量，互斥鎖）上被阻止，但現在能夠繼續。 * 阻止進程等待系統調用完成，但已傳遞信號并且信號處理程序需要運行。 在考慮線程時可以生成類似的示例。 ## 效率措施 `start_time`是進程的掛鐘開始時間（CPU 開始工作）`end_time`是進程的結束掛鐘（CPU 完成進程）`run_time`是所需的 CPU 時間總量`arrival_time`是進程進入調度程序的時間（CPU 可能無法啟動它） ## 什么是'周轉時間'？ 從進程到達到結束的總時間。 `turnaround_time = end_time - arrival_time` ## 什么是'響應時間'？ 從進程到達到 CPU 實際開始工作所花費的總延遲（時間）。 `response_time = start_time - arrival_time` ## 什么是“等待時間”？ 等待時間是 _ 總 _ 等待時間，即進程在就緒隊列上的總時間。一個常見的錯誤是認為它只是就緒隊列中的初始等待時間。 如果沒有 I / O 的 CPU 密集型進程需要 7 分鐘的 CPU 時間才能完成，但需要 9 分鐘的掛鐘時間才能完成，我們可以得出結論，它已被放置在就緒隊列中 2 分鐘。對于那些 2 分鐘，該過程已準備好運行但沒有分配 CPU。工作等待時無關緊要，等待時間為 2 分鐘。 `wait_time = (end_time - arrival_time) - run_time` ## 什么是車隊效應？ “Convoy 效應是持續備份 I / O 密集型進程的地方，等待占用 CPU 的 CPU 密集型進程。這導致 I / O 性能不佳，即使對于 CPU 需求很小的進程也是如此。” 假設 CPU 當前已分配給 CPU 密集型任務，并且存在一組處于就緒隊列中的 I / O 密集型進程。這些進程只需要很少的 CPU 時間，但它們無法繼續，因為它們正在等待從處理器中刪除 CPU 密集型任務。在 CPU 綁定進程釋放 CPU 之前，這些進程一直處于饑餓狀態。但很少會釋放 CPU（例如，在 FCFS 調度程序的情況下，我們必須等到進程因 I / O 請求而被阻止）。 I / O 密集型進程現在可以最終滿足他們的 CPU 需求，他們可以快速完成這些需求，因為他們的 CPU 需求很小，并且 CPU 再次被分配回 CPU 密集型進程。因此，整個系統的 I / O 性能受到所有進程的 CPU 需求饑餓的間接影響。 這種效果通常在 FCFS 調度程序的上下文中討論，但循環調度程序也可以展示長時間量子的康宏效應。 ## Linux 調度 截至 2016 年 2 月，Linux 默認使用 _ 完全公平調度程序 _ 進行 CPU 調度，使用預算公平調度“BFQ”進行 I / O 調度。適當的調度會對吞吐量和延遲產生重大影響。延遲對于交互式和軟實時應用（如音頻和視頻流）尤為重要。有關詳細信息，請參閱此處的討論和比較基準[ [https://lkml.org/lkml/2014/5/27/314](https://lkml.org/lkml/2014/5/27/314) ]。 以下是 CFS 的日程安排 * CPU 創建一個紅黑樹，其中包含進程虛擬運行時（runtime / nice_value）和睡眠公平性（如果進程正在等待某些內容，則在等待時將其提供給 CPU）。 * （好的值是內核優先處理某些進程的方式，優先級越低） * 內核根據此度量標準選擇最低的一個，并安排該進程下一次運行，將其從隊列中取出。由于紅黑樹是自平衡的，因此保證$ O（log（n））$（選擇 min 進程是相同的運行時） 雖然它被稱為公平調度程序，但存在一些問題。 * 調度的進程組可能具有不平衡負載，因此調度程序粗略地分配負載。當另一個 CPU 獲得空閑時，它只能查看組計劃的平均負載而不是單個核心。因此，只要平均值很好，空閑 CPU 就不會從正在燃燒的 CPU 中獲取工作。 * 如果一組進程正在運行，則在非相鄰核心上存在錯誤。如果兩個核心超過一跳，負載平衡算法甚至不會考慮該核心。這意味著如果 CPU 是空閑的并且正在做更多工作的 CPU 超過一跳，它將不會進行工作（可能已經修補）。 * 線程在一個核心子集上進入休眠狀態后，當它被喚醒時，它只能在它正在睡眠的核心上進行調度。如果這些核心現在是公共汽車