在任何多路復用資源的系統中，計算在哪里運行以及何時運行的調度問題都可能是最基本的問題。然而，就像計算機中許多其他重要問題一樣（例如數據庫中的查詢優化），調度器的研究像鐘擺一樣，時而活躍，時而處于休眠狀態，因為它被認為是一個“已解決”的問題。

調度一直是系統和網絡中最基本的操作之一。它涉及將任務分配給CPU并在它們之間進行切換，這些決策對應用程序性能和系統效率都至關重要。長期以來，操作系統（OS）調度專注于公平性。

然而，近年來的兩個發展導致了OS調度研究的復興。首先，云計算的出現賦予了不同的，難以優化的指標。例如，微延遲和微秒（μs）尺度，這些指標在傳統的調度器中沒有被考慮。其次，摩爾定律的結束使得操作系統堆棧（包括調度）的專業化成為了繼續提高性能的必要條件。

近年來有三篇論文或許實現了性能、可擴展性和策略選擇相關的突破。第一篇論文挑戰了低延遲（通常通過配置專用核心實現）和高利用率（需要核心重新分配）之間的假定權衡，通過在單微秒粒度上實現分配決策來解決這個問題。第二篇論文通過將策略的創建和操作進行分解，使得用戶空間代理完全可以處理策略的創建和操作，而固定的內核機制則負責向代理通信事件和應用實施調度決策。第二篇論文根據微秒級靈活策略進行負載均衡和分配決策的能力，最終選擇了根據應用程序選擇策略的問題。

1. 微秒級核心重新分配

第一篇論文由Ousterhout等人回答了一個基本問題，即操作系統中核心分配可以多快進行以及這種重新分配是否有益于應用程序的性能。該論文介紹的系統名為Shenango，挑戰了廣泛存在的觀念，即在微秒級別上跨應用程序分配核心是不可行的，因為存在高開銷和潛在的緩存污染。

在這篇論文中，作者們詳細闡述了Shenango系統的設計和實現，包括如何實現快速核心重新分配，以及如何避免因重新分配而導致的性能下降。此外，作者們還通過大量的實驗驗證了Shenango系統的有效性，快速核心重新分配確實是可能的，并展示了其在性能方面的顯著優勢。

在Shenango操作系統中，我們實現了微秒級別的核心重新分配，其關鍵在于使用了專用調度核心。該核心每5微秒可以做出一次CPU核心的分配決策，以確保系統的高效性。為了確定何時從應用程序中分配或回收核心，Shenango監視每個應用程序的線程運行隊列和網絡數據包隊列的長度，并使用其導數作為擁塞信號。這種方法可以有效避免系統擁塞，保障了系統的穩定性和可靠性。同時，該算法完全在專用核心上運行，該核心還管理將傳入的網絡數據包引導到其相應的目標應用程序的CPU核心。這使得整個系統的運行更加高效，同時也提高了系統的可靠性和安全性。

作者們展示了這種方法的有效性，通過展示如何通過細粒度的CPU核心重新分配，來改善在同一系統上共存的延遲敏感和批處理應用程序的性能。通過基于瞬時輸入的數據包速率分配CPU核心，Shenango操作系統在使用5微秒核心重新分配間隔與100微秒間隔相比，前者的延遲降低了，后者的吞吐量提高了6倍以上。隨后的研究表明，Shenango的微秒級調度程序還可以幫助緩解其他系統資源（例如緩存和內存帶寬）的干擾，并向網絡提供細粒度反饋以防止過載。

2. 部署操作系統調度到Linux的框架

構建像Shenango這樣高效的調度器是一個有趣的實驗室練習，但是在生產環境中需要考慮更多的因素。比如，如何兼容現有的應用程序和操作系統（如Linux），如何滿足不同的需求以及如何實現更高的可擴展性和可靠性等等。為了解決這些問題，一些Google的工程師構建了一個名為ghOSt的框架，該框架可以實現不同的調度策略，并將它們部署到Linux內核中，以方便用戶更容易地使用。

ghOSt設計背后的關鍵理由是為了提高操作系統的靈活性。ghOSt從微內核中汲取靈感，將OS調度委托給用戶空間代理，可以是全局的或每個CPU。這種方法的優點顯而易見：用戶空間代理可以根據不同的需求和場景制定不同的調度策略，而不僅僅是受限于內核代碼的固有規則。因此，開發人員可以享受用戶空間開發的靈活性，而不受內核代碼的限制和長時間部署周期的困擾。

為了在用戶空間代理和內核之間實現無縫的通信，ghOSt使用了共享內存來傳遞提示信息，使代理能夠做出更明智的調度決策。這種方法不僅提高了操作系統的性能，而且還為應用程序提供了更廣泛的功能和更高的效率。而最簡化內核調度類，是ghOSt設計中最為重要的組成部分之一。內核調度類負責將代理傳遞的調度事件轉換為內核可以理解的格式，并將處理結果返回給代理。

總的來說，ghOSt的設計使得操作系統變得更加靈活和高效，從而能夠更好地滿足不同用戶的需求。它為開發人員提供了更多的自由度和創造空間，使得他們可以更好地實現自己的想法和創意。同時，ghOSt的設計也為用戶提供了更好的體驗和更快的響應速度，使得他們能夠更加高效地完成工作。

ghOSt面臨的最大挑戰是內核組件與用戶空間代理之間的通信延遲，可能需要達到5微秒。這可能會導致：

（1）競爭條件，例如，用戶空間代理向已從線程的CPU掩碼中刪除的CPU來調度線程）；

（2）低利用率，因為CPU保持空閑等待代理的調度決策。

ghOSt通過在共享內存上實現事務API來避免競爭條件，該API允許代理以原子方式提交調度決策。為了減輕第二個問題，作者們建議使用自定義的eBPF程序，在每個核心上本地運行并臨時調度任務，直到收到代理的決策。當將其他操作系統功能卸載到用戶空間（例如內存管理）時，相同的技術也適用。

3.選擇最佳調度策略選項

在引入ghOSt之后，可以輕松開發和部署自定義調度策略，但問題在于每個應用程序應該使用哪種策略。為了回答這個問題，McClure等人進行了全面的分析。

在引入ghOSt之后，可以輕松開發和部署自定義調度策略。然而，雖然這是一個不錯的進展，但是使用哪種策略對于每個應用程序來說都是一個重要的問題。為了解決這個問題，McClure等人進行了全面的分析，并提出了以下建議：

首先，應該考慮應用程序的需求以及其性質。例如，一些應用程序需要保持高可用性，需要在任何時候都能夠提供服務，因此需要使用具有高容忍度的策略。另一些應用程序可能會經常需要進行擴展，因此需要使用具有良好擴展性的策略。了解應用程序的性質是選擇調度策略的關鍵。

其次，應該考慮數據中心的資源利用率。在數據中心中運行的應用程序通常會共享物理資源，例如CPU，內存和網絡帶寬。因此，應該選擇那些可以最大程度利用這些資源的策略。例如，可以使用負載均衡策略來確保每個節點都能夠平均分配負載，從而使整個數據中心的資源利用率最大化。

最后，應該考慮操作和管理的成本。一些策略可能會增加管理和操作的成本，因此需要權衡這些成本和性能。應該選擇那些既能夠滿足應用程序的需求，又可以最小化操作和管理成本的策略。

作者們將調度過程分為兩個不同的策略：在應用程序之間分配核心和在每個應用程序內的CPU之間平衡負載任務。令人驚訝的是，他們發現第二個策略相對簡單；無論任務服務時間分布，核心數量，核心分配策略和負載均衡的開銷如何，無論是延遲還是效率，都是最好的負載均衡策略。

相比之下，核心分配策略要復雜得多。例如，與過去的工作相反，作者們發現根據平均延遲或利用率主動回收應用程序的核心對于小任務的性能表現更好，而不是等待CPU變為空閑狀態。他們還發現，在處理小任務時，最好為每個應用程序分配一定數量的CPU，而不是動態分配。

這項分析開辟了新的研究領域，例如開發實現可擴展為全局隊列的新硬件，在模擬中表現甚至優于任務獲取。此外，該研究沒有考慮搶占的存在，因此需要進一步研究搶占策略如何影響調度決策。

4.小結

這三篇論文，探討了在操作系統調度器中如何引入現代化的方法。第一篇論文專注于構建盡可能快速的調度器，第二篇旨在簡化實現并與現有應用程序和操作系統兼容的新策略。第三篇論文則探討不同類型應用程序的最佳調度策略。最終，這三篇論文為致力于開發現代計算系統更好的調度策略作出了有益的貢獻。這些論文強調了需要更好、更有效率、更靈活的操作系統調度程序，開辟了新的研究領域，并展示了操作系統調度策略持續發展和創新的重要性。

【參考文獻】

• Amy Ousterhout, Joshua Fried, Jonathan Behrens, Adam Belay, 和 Hari Balakrishnan (MIT CSAIL). “Shenango: Achieving High CPU Efficiency for Latencysensitive Datacenter Workloads. Proceedings of the 16th Usenix Symposium on Networked Systems Design and Implementation”, 2019. https://dl.acm.org/doi/10.5555/3323234.3323265 （https://www.usenix.org/conference/nsdi19/presentation/ousterhout）
• Jack Tigar Humphries (Google), Neel Natu (Google),Ashwin Chaugule (Google), Ofir Weisse (Google), Barret Rhoden (Google), Josh Don (Google), Luigi Rizzo (Google), Oleg Rombakh (Google), Paul Turner (Google), 和 Christos Kozyrakis (Stanford University and Google). “ghOSt: Fast & Flexible User-space Delegation of LinuxScheduling. Proceedings of the 28th ACM Symposium on Operating Systems Principles”, 2021. https://dl.acm.org/doi/10.1145/3477132.3483542
• Sarah McClure (UC Berkeley), Amy Ousterhout (UCBerkeley), Scott Shenker (UC Berkeley and ICSI), Sylvia Ratnasamy (UC Berkeley). "Efficient Scheduling Policies for Microsecond-scale Tasks." Proceedings of the 19th Usenix Symposium on Networked Systems Design and Implementation, 2022. https://www.usenix.org/conference/nsdi22/presentation/mcclure