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

調(diào)度一直是系統(tǒng)和網(wǎng)絡(luò)中最基本的操作之一。它涉及將任務(wù)分配給CPU并在它們之間進行切換，這些決策對應(yīng)用程序性能和系統(tǒng)效率都至關(guān)重要。長期以來，操作系統(tǒng)（OS）調(diào)度專注于公平性。

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

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

1. 微秒級核心重新分配

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

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

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

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

2. 部署操作系統(tǒng)調(diào)度到Linux的框架

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

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

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

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

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

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

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

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

3.選擇最佳調(diào)度策略選項

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

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

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

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

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

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

相比之下，核心分配策略要復(fù)雜得多。例如，與過去的工作相反，作者們發(fā)現(xiàn)根據(jù)平均延遲或利用率主動回收應(yīng)用程序的核心對于小任務(wù)的性能表現(xiàn)更好，而不是等待CPU變?yōu)榭臻e狀態(tài)。他們還發(fā)現(xiàn)，在處理小任務(wù)時，最好為每個應(yīng)用程序分配一定數(shù)量的CPU，而不是動態(tài)分配。

這項分析開辟了新的研究領(lǐng)域，例如開發(fā)實現(xiàn)可擴展為全局隊列的新硬件，在模擬中表現(xiàn)甚至優(yōu)于任務(wù)獲取。此外，該研究沒有考慮搶占的存在，因此需要進一步研究搶占策略如何影響調(diào)度決策。

4.小結(jié)

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

【參考文獻】

• 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