從小型物聯網設備到大型服務器，Linux在各個領域中都得到了廣泛應用。計算吞吐量對于使用數百萬個線程來模擬人工智能和機器學習模型至關重要，但對于其他機器來說，響應性能可能很關鍵。

CPU調度是一種確定可以執行的下一個進程的技術。為特定環境使用的CPU調度程序的優化是提高性能和降低成本的重要問題。工作負載和機器的性能很大程度上取決于調度程序的配置。然而，大多數機器考慮的是Linux的通用硬件和軟件環境，使用默認調度程序配置。有效的調度對整個Linux服務器具有顯著的性能影響，大多數調度研究都專注于減少調度開銷或修改優先級操作以支持特定情況下的作業。

1. Linux 中的調度器

目前默認的 Linux 調度器，即完全公平調度器 (CFS) ，使用虛擬運行時間的概念，旨在實現理想和精準的多任務 CPU調度，以便所有任務使用相同的 CPU 時間。相比之下，FreeBSD 操作系統的默認調度器 ULE ，專為對稱多處理 (SMP) 環境設計，其中兩個或多個處理器使用一個共享內存，并允許多個線程獨立執行。它旨在通過獨立調整每個任務的交互能力、優先級和片段大小，提高同步多線程 (SMT) 環境的性能。為此，Bouron 將 FreeBSD 的 ULE 調度器移植到 Linux，并將其性能與 CFS 進行了比較。結果，確認在大多數工作負載中兩個調度器顯示相似的性能，對于具有許多交互式任務的工作負載，ULE 顯示出了更好的性能。

Kolivas 認為，用于在特定環境下改善性能的啟發式調整參數會降低性能。為了減少這種調度開銷，他們實現了一種簡單的調度算法 (BFS)，該算法消除了復雜優先級計算。BFS 提高了 Linux 桌面的響應性，適用于少于 16 個 CPU 核心的設備，并用作多個 Linux 發行版（包括 PCLinuxOS 2010、Zenwalk 6.4 和 GalliumOS 2.1）的默認調度器。

優化調度器是一個困難的問題，需要在操作系統上具有廣泛的專業知識。許多因素會影響調度程序的性能，例如硬件、工作負載和網絡，以及用戶如何操作系統。然而，理解這些許多因素之間的所有相關性是困難的。即使實現了這樣的調度程序算法，調度程序度量也會存在誤差。因此，很難確認調度程序性能是否真正得到了改善。

2. 基于ML 的調度參數調優

Lama 提出并開發了 AROMA，一個自動化 Hadoop 參數配置的系統，該平臺用于大數據分析，以提高服務質量并降低成本。AROMA 使用支持向量機 (SVM)，一種機器學習模型，以優化參數，使云服務能夠有效地使用，而無需進行低效的參數調整。

自動優化基于機器學習的 Apache Spark 參數，可以提高其性能。Spark 內部有超過 180 個參數，其中有 14 個參數對性能有重大影響，這些參數可以采用決策樹模型算法進行優化。在相關論文的性能評估結果中，初始設置的平均性能改善了 36%。

此外，對于 Android 調度器的性能， Learning EAS 是一種針對 Android 智能手機調度器 EAS 的策略梯度強化學習方法。Learning EAS 應用于正在運行任務的特征，并調整 TARGETLOAD 和 schedmigration_cost 以提高調度器性能。在 LG G8 ThinQ 上的評估結果表明，與默認 EAS 相比，Learning EAS 可將功耗降低最多 5.7%，并將性能提高了最多 25.5%。

服務器中很常見的是靜態工作負載，例如基因組分析軟件、大數據分析系統和人工智能。所讀論文旨在通過調整調度策略和參數來提高靜態工作負載的性能。在Linux內核中，定義了5個調度策略和14個調度程序參數。通過適當地修改這些策略和參數，可以提高調度程序的性能，以適應硬件環境和工作負載的特征。但是，對于單個優化，需要消耗大量成本，因為必須考慮每個參數之間的關系，并且需要專業的工作負載信息和硬件專業知識。

3.基于RL 的調度參數調優

3.1關于強化學習 RL

強化學習是一種機器學習算法，它建立了一個策略，以確定在當前狀態下總補償值最大的行為。它由環境和代理組成，如下圖所示。代理是確定下一個執行操作的主體，通過行動與環境交互，環境則回應狀態和獎勵。代理不斷與環境交互以建立最優策略。

圖片

強化學習適用于具有權衡關系的問題。特別是，短期和長期行為的獎勵值是明確的時候，RL被用于各種領域，如機器人控制等，例如DOTA 2 就通過深度強化學習進行了良好的訓練。

有許多算法用于實現強化學習，這篇論文中采用了Q-learning算法。Q-learning的代理具有一個Q表，記錄了可以在每個狀態下執行的所有動作的Q值，以解決問題。當代理首次開始學習時，Q表的所有值都被初始化為0。如果每個狀態的Q值為0，則代理會隨機選擇一個操作并更新Q表中的Q值。如果Q值不為0，則代理選擇具有最大Q值的操作，以最大化獎勵。代理重復執行這些步驟，直到找到最佳策略。

Q-learning是一種無模型強化學習，它使用貝葉斯方程來找到具有最高總獎勵的行動。在強化學習中，模型預測環境的狀態變化和補償。無模型強化學習具有易于實現或調整的優點。

3.2 強化學習的工具

OpenAI Gym為強化學習提供了一個名為Env的集成環境接口。Env提供以下功能：

Render(self)：此函數在環境內呈現一個幀，并將其顯示為GUI。在本研究中，由于沒有需要GUI，因此未使用它。

Reset(self)：此函數將環境重置為其初始狀態。此功能通常在每個學習階段結束時應用，以進行下一步學習。

Step(self, action)：此函數逐步執行一個動作，并返回以下三個變量。

• 觀測（object）：該值是一個環境特定的對象，表示對環境的觀測。
• 獎勵（flfloat）：該值表示通過上一次行動獲得的補償金額。強化學習的最終目標是最大化總獎勵值的總和。
• 完成（boolean）：這是一個標志，用于決定是重置環境還是結束學習。

OpenAI提供了各種環境的接口，論文中的實現基于OpenAI Gym。

3.3 Linux中的調度策略與內核調度參數

在Linux內核中，當前定義了五個調度策略：NORMAL(CFS)、FIFO、RR、BATCH、IDLE ，可以使用Linux提供的schedtool工具更改這些策略，而無需重新啟動服務器。

SCHED_NORMAL(CFS) 這是Linux內核的默認調度策略。CFS的目的是最大化整體CPU利用率，并為所有任務提供公平的CPU資源。CFS基于每個CPU運行隊列，這些任務按虛擬運行時間的順序運行，并通過紅黑樹排序。

SCHED_FIFO 這是一個固定優先級調度策略，每個任務以1到99的優先級值執行，并且是按高優先級順序搶占并執行CPU的策略。

SCHED_RR 這基本上與SCHED_FIFO的操作相同，但每個任務都有一個時間量子值，這是執行的最長時間。當時間量子過期時，任務以輪詢方式切換到下一個任務。

SCHED_BATCH 此策略適用于批處理作業。通過避免被其他任務搶占，我們可以運行一個任務更長時間，比其他策略更好地利用硬件緩存；但是，這對于交互式任務效果不佳。

SCHED_IDLE 此策略以非交互方式運行，類似于SCHED_BATCH。但是，與SCHED_BATCH不同，當其他進程處于空閑狀態時，可以執行SCHED_IDLE。

Linux內核提供了14個調度器參數進行優化。該論文對其中9個參數進行了優化，并排除了不影響性能的五個參數。下表顯示了可以更改的參數值范圍和Linux內核的默認值。它們可以使用Linux提供的sysctl命令在不重新啟動機器的情況下更改。

圖片

每個參數的含義如下。

sched_latency_ns： 針對CPU綁定任務的目標搶占延遲。增加此參數會增加CPU綁定任務的時間。

sched_migration_cost_ns： 這是在遷移決策中被認為是熱緩存的最后一次執行后的時間。熱任務不太可能被遷移到另一個CPU，因此增加此變量會減少任務遷移。如果CPU空閑時間高于預期而有可運行的進程，則建議減小此值。如果任務經常在CPU或節點之間反彈，則可能更好地增加它。

sched_min_granularity_ns： CPU綁定任務的最小搶占粒度。此參數與sched_latency_ns密切相關。

sched_nr_migrate： 這控制有多少個任務可跨處理器進行負載平衡。由于負載平衡使用禁用中斷的運行隊列（softirq）迭代，因此可能會對實時任務產生irq延遲懲罰。因此，增加此值可能會給大型SCHED_OTHER線程帶來性能提升，但以實時任務的irq延遲為代價。

sched_rr_timeslice_ms： 此參數可以調整SCHED_RR策略中的時間。

sched_rt_runtime_us： 這是在schedrtperiodus期間分配給實時任務的時間量子。將該值設置為* - *將禁用RT帶寬強制執行。默認情況下，RT任務每秒可以消耗CPU資源的95％，因此留給SCHED_OTHER任務5％，或0.05秒。

sched_rt_period_us： 這是測量實時任務帶寬執行的周期。

sched_cfs_bandwidth_slice_us： 在使用CFS帶寬控制時，此參數控制從任務的控制組帶寬池向運行隊列轉移的運行時間（帶寬）的數量。較小的值允許全局帶寬在任務之間以精細的方式共享，而較大的值會減少轉移開銷。

sched_wakeup_granularity_ns wakeup： 這是喚醒搶占的粒度。增加此變量會減少喚醒搶占，減少計算綁定任務的干擾。降低它可以提高對延遲關鍵任務的喚醒延遲和吞吐量，特別是當短周期負載組件必須與CPU綁定組件競爭時。

3.4 基于RL的調度器參數調整——STUN

STUN并沒有用最廣泛用于強化學習的深DQN，因為它消耗大量計算能力和內存，如果僅使用CPU而沒有GPU，則需要太長時間進行學習。事實上，它無法在合理的時間內搜索內核調度程序的最優參數。Q學習算法比深度學習輕，消耗更少的內存。因此，STUN采用了Q學習算法，這是在Linux內核中實現STUN的一種更好選擇。

體系結構

下顯示了STUN的結構。STUN由環境模塊和代理模塊組成。環境模塊定義了內核參數優化的環境，代理模塊定義了Q學習算法并執行代理。

圖片

在環境模塊中定義的reset和step函數如下。

Reset(self, f = True) 此函數初始化要優化的參數。重置用于防止在學習過程中對特定參數值進行過度獎勵。它隨機初始化值，最多可學習次數的一半，其余值為表現最佳的值。

Step(self, action): STUN在更改參數值的情況下進行測試工作負載后，返回狀態、獎勵和完成。每個變量的含義如下。

Action: 這是一個值，確定每個參數的增加或減少。當優化n個參數時，它有n + 1個值從0到n。STUN通過添加或減去預定義值α來更改優化值。

State: 這是用于指示要學習的參數的值的元素。每個參數分為50個，范圍可以修改，并且每個狀態的值為0到49，表示為（s1，s2...sn）。

Reward: 作為測試工作負載的結果，用于確定是否比先前狀態下獲得更好的性能。

Done: 這是用于提高效率的學習結束的元素。“完成”標志初始化為true。如果測試工作負載的結果小于默認性能的20％，則返回false。如果連續出現一定數量的false值，則該執行結束。

代理模塊定義Q表，該表記錄在每個狀態下執行某個動作時的動作值。STUN使用Q學習模型和值函數Q（st，at）來更新Q表的值。從值函數獲得的值是未來可以獲得的預期值，而不是判斷當前價值的好壞，與獎勵值不同。Q-學習算法每次執行操作時都會更新Q表中狀態的預期值，然后選擇具有最大預期值的操作。更新Q值的公式如下。

在上面的公式中，st和at分別表示當前狀態和動作；Rt+1是在當前狀態下執行的獎勵值；max aQt（st+1，a）是在未來假設最有利的動作時得到的預期值。在這里，γ是折扣率，反映了當前獎勵的價值高于未來獎勵的價值。由于未來獎勵的價值低于當前獎勵，因此通過將其乘以0到1之間的值γ進行反映。

在代理模塊中，學習迭代的數量由代理的事件執行次數（N）和步驟函數執行次數（T）確定。通過在單個事件中多次執行步驟函數，改變和學習參數值多達T次。因此，代理最多有N×T個學習迭代。

參數過濾

即使參數值根據調度程序策略或工作負載發生變化，也不是所有參數都會影響性能。過濾過程通過最小化性能改進的不必要的訓練來縮短訓練時間，并減少內存使用以更有效地執行優化。在Q-learning算法中使用所有五個調度程序策略和九個參數會浪費大量內存并增加學習時間。因此，需要找到一個顯著影響性能的參數。為了實現有效學習，STUN通過過濾過程選擇優化的調度程序策略和參數。

STUN將單個參數值按照最小值、最大值和默認值依次更改為每個策略，并記錄測試工作負載中的性能變化。此時，其他參數被固定為默認值。過濾過程刪除不影響應用程序整體性能的參數。為了確定參數，過濾過程使用20%的閾值作為測量誤差。由于根據系統情況可能存在10-15%的誤差范圍，因此我們決定20%的性能差異是有意義的，并測試參數的最佳值。

在整個過濾過程中，已知這些策略和參數之間的關系，因此只使用最影響性能的參數作為學習變量。因此，過濾過程可以縮短學習時間并減少內存使用，從而更有效地實現優化。

獎勵算法

獎勵是指工作負載性能是否在改善的值。通過細分和應用獎勵，STUN可以更有效地更新Q表，并縮短學習時間。

STUN獎勵函數中的獎勵和懲罰規則的一些想法如下：

• 對于性能的重大改進給予高獎勵
• 如果性能顯著下降，則給予懲罰
• 基于以前的性能給予獎勵

為了表示算法的規則，默認值是作為性能標準使用的變量。這是在不更改參數的情況下在Linux默認設置下的測試工作負載結果。請注意，結果表示測試工作負載的性能。與過濾過程一樣，根據20%以上和20%以下的結果獎勵不同，以檢查性能是否受到重大影響。從default_bench提高20%以上的結果設置為upper，低于20%的結果設置為under。如果結果優于upper，則獎勵為200，是一個大獎勵；如果低于under，則懲罰為?50。當性能在20%的范圍內變化時，如果性能高于以前的結果，則給予100的值；否則，返回0的值。算法1是獲得獎勵的算法表示。

算法1: 獎勵算法

upper : 20% greater than de f ault_bench

under : 20% less than de f ault_bench

if result_o f _testworkload > upper then

    reward = 200

else if result_o f _testworkload < under then

    reward = ?50

else if result_o f testworkload > lastresult then

    reward = 100

else

    reward = 0

end

4. 基于RL的OS調度調優的評估方法

沒有評估體系和評估指標的AI 都是在耍流氓，該論文評估了以下幾點：

基于學習迭代次數的STUN性能。通過改變決定強化學習中總迭代次數的因素，即episode count N和Max_T的值來分析結果。

微基準下的性能表現。為了確認STUN的詳細性能改進，選擇了微基準，即hackbench，并將其在經過優化的STUN調度程序參數下與在默認調度程序環境下的性能進行比較。作為評估Linux內核調度程序性能的基準，它創建進程通過套接字或管道進行通信，并測量每個對之間發送和接收數據所需的時間。對于運行hackbench的選項，給定了目標機器的核心數，并將核心數乘以40個任務應用為測量執行時間的進程。

真實工作負載下的性能表現。為了評估STUN對真實工作負載的性能影響，運行了一個使用Haar Cascades的人臉檢測應用程序，并比較了在默認和經過優化的設置下應用程序的執行時間和每秒幀數之間的差異。人臉檢測應用程序使用OpenCV提供的基于機器學習的對象檢測算法之一，它從視頻文件的幀中查找人的面部和眼睛。將默認應用程序修改為高度并行的多線程應用程序，以利用許多底層核心。

基于CPU核心數量的改進。為了確認CPU核心數是否影響STUN的性能，比較了在4核、44核和120核機器上優化Sysbench的性能改進率。Sysbench是一個基于LuaJIT的多線程基準測試工具集。雖然它主要用于基準測試數據庫，但也用于創建任意復雜的工作負載。在這個評估中，生成了CPU核心數× 10個線程，并將執行的總事件數作為結果。

為驗證在實際工作負載下的性能，在44核機器上使用STUN優化了人臉檢測程序，并分析了視頻的人臉識別時間和默認和優化參數值下的每秒幀數。STUN獲取的最佳參數值如下：

• 調度程序策略：Normal；
• kernel.sched_rt_runtime_us = 1,000,000；
• kernel.sched_min_granularity_ns = 680,100,000。

應用最佳值后的人臉檢測程序的結果, 總執行時間從58.998秒降至48.198秒，下降了18.3%，每秒幀數從16.95增加到20.748，增加了22.4%。

調度程序的性能影響在很大程度上取決于核心數量，這歸因于調度程序的功能。因此，該論文比較了在4核、44核和120核機器上通過STUN對Sysbench的性能改進。Sysbench線程選項設置為每臺機器CPU核心數的10倍。此外，策略和參數設置為通過過濾過程獲得的最佳值。表3顯示了通過STUN為每個核心數優化Sysbench的調度程序策略和參數值。

5.小結

CPU調度程序是影響系統性能的重要因素。該論文提出了STUN，這是一種使用強化學習優化Linux內核調度程序參數的優化框架。使用STUN可以在不需要人為干預的情況下增強各種調度環境。

STUN具有有效和快速優化的特點。首先，通過濾波過程選擇的參數顯著影響性能，從而實現有效優化。此外，將獎勵算法細分，以便強化學習中的代理可以有效地學習。未來可以采用另一種強化學習算法，例如策略梯度，以獲得更精確的優化參數值和更并發的參數。此外，可以將STUN的邏輯與Linux內核集成，以創建自適應調度程序。