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

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

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

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

1. 微秒級(jí)核心重新分配

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.小結(jié)

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

【參考文獻(xiàn)】

• 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