一、前言

操作系統上運作著各種應用、服務來滿足用戶需求，這些應用、服務實現的功能，通常都會依托一個個具體的線程來完成。在2022年的今天，無論是手機用戶還是平臺廠商，都不會容忍一臺手機的功能僅限于單一的通信功能。手機設備不比服務器，其多核架構體系上只存在8個cpu core，而執行線程的數量卻輕而易舉超過8個。

每個cpu上該執行什么線程，是由linux線程調度器來進行決策的，關于這一部分，網上已經有相當多的文章進行描述，因此本文在講解一些概念的基礎上，會分析為何當前的調度器仍滿足不了android系統的業務需求，我們為何還需要做調度優化。先拋出一張圖（圖1），大家感受下高負載下的cpu，是不是像極了正在工作的你，忙的不可開交！

圖1 高負載系統運行狀態

擁有android開發經驗的伙伴，都清楚上面是通過google perfetto工具抓取的系統運行狀態圖示，8個核心全部跑滿，要達到這樣的現象并不困難，多啟動幾個應用，抓取下啟動時的狀態即可。那么問題來了，高負載的系統中，每個核心都不止運行一個線程，這必然導致線程執行存在先后順序，每次執行的時間也存在差異，那么，影響用戶體驗的線程能否及時執行起來，能否得到足夠長的執行時間，就顯得尤為重要，這也是調度團隊需要解決的問題。

二、線程調度器如何運作

實際的開發過程中，我們發現CFS調度類線程更容易出現調度問題，因此目前調度的優化圍繞該調度類展開。下文的主要分析對象為CFS調度類，我們先從幾個基礎概念入手。

2.1 基礎調度概念

調度類（sched class）：linux內核支持的調度類如圖2所示，每個線程歸屬于其中一種調度類，并遵循一種調度策略。android系統中，覆蓋面最廣的是CFS調度類fair_sched_class，其次是實時調度類中的rt_sched_class，我們喜歡將它們的線程分別成為cfs線程和rt線程。調度類存在優先級，圖2從上到下羅列的調度類，優先級從高至底。調度器總是從最高優先級的調度類中開始檢索需要執行的線程，同個調度類存在多個線程，則按具體的調度策略進行檢索。

圖2 linux支持調度類

調度類提供的實現接口用于定制具體的調度策略，開發人員也可按照相應的規則實現自己的調度類和調度策略。

運行隊列（runqueue）：線程需要執行時，會選取某個核，并放置到該核對應的運行隊列上，這個過程我們稱為入隊；當線程由于某種原因不再需要執行時，將從運行隊列上摘除，對應的過程即出隊。不同調度策略，運行隊列的維護方式不同，如cfs線程的隊列維護是通過紅黑樹完成，而rt線程的隊列維護則是通過優先級鏈表完成。

注：圖3為CFS調度類的實現，對應的接口作用如表1所示。

圖3 cfs調度策略實現接口

表1 cfs調度策略接口作用

調度延遲（sched latency）：線程在運行隊列中的等待時間，這主要來自三個方面：從idle cpu喚醒需要等待器件做好準備；等待更高優先級調度類線程執行完成；等待同調度類的線程時間片耗盡。

時間片（sched slice）：線程單次執行的時長。CFS調度策略存在調度周期，理想情況下，調度周期內運行隊列的每個線程都將執行一次，當運行隊列中只有一個線程時，將總是由該線程分得全部時間片。

圖4 調度延遲與時間片

2.2 權重的作用

CFS調度策略就是青天大老爺，它來到linux內核，只做三件事：公平！公平！還是公平！其公平規則緊緊圍繞權重展開，理解了權重的作用，也就掌握了該調度策略的核心。

我們知道，每個線程都存在優先級priority，記錄在其抽象結構體struct task_struct中，并提供相應的系統調用供用戶修改。實際上，android通過這些系統調用指定的是nice值，如表2所示。

文件路徑：system/core/libsystem/include/system/thread_defs.h

表2 android系統指定線程屬性值

nice值與priority之間存在一個轉換關系，如下：

nice值在一定程度上定義了該線程的重要程度，它是一個存在很久的概念。在CFS調度策略誕生之前，普通線程指定nice值后，調度器會賦予固定大小的時間片。nice值越小，優先級越高，時間片越大。調度器總是讓高優先級的線程優先執行完分配的時間片。這樣的做法存在兩個問題：

（1）低優先級的調度延遲無法得到有效控制。由于總是讓高優先級先執行，那么調度延遲很大程度上取決于高優先級線程的數量。

（2）固定時間片會導致低優先級線程的執行變得異常艱難。低優先級線程本身時間片是非常小的，如果長時間的等待換來的是幾個ms的執行，那它的任務將很難執行完。

因此，內核引入CFS調度策略，保證公平調度。為此，調度器特地給nice值建立一一對應的權重值，如圖5所示，注意到，一共有40個權重等級，代表CFS調度類線程的nice范圍[-20, 19]：

圖5 權重映射表

權重與nice值的計算關系如下：

weight = 1024 / (1.25 ^ nice)

權重的作用主要體現在兩個方面：

（1）時間片分配大小

時間片是按線程權重占比進行分配。如果兩個權重為1024（nice值為0）的線程放在同個核上，在沒有其它線程干擾的情況下，這兩個線程將平分整個調度周期。我們將掛在運行隊列的線程看做一個調度實體se（sched entity），則該se的時間片為：

slice = se->load.weight / cfs_rq->load

其中，se->load.weight代表該se的權重值，即圖5中nice值對應的數值（如果該se代表一個具體線程）。cfs_rq->load則代表當前運行隊列上所有調度實體的權重總和。注意，以上描述僅適用于未開啟組調度的情況，當開啟組調度后，情況會有些微不同，另有章節涉及。

（2）虛擬時間增長

調度實體的執行時間，將按照權重反饋到虛擬時間的增長上。我們之前說過，CFS調度策略是通過一棵紅黑樹來進行維護的，虛擬時間越小的線程，將掛在紅黑樹的越左端，而最左端是普遍情況下調度器選取的下一個執行對象。

對于一個權重為1024的線程，執行2ms時，會原封不動地將這2個ms累加到虛擬時間上，但是，當它的權重增加到9548時（對應nice值為-10），虛擬時間只增加0.2ms。它們之間存在以下關系：

vruntime = exectime * (1024 / se->load.weight)

虛擬時間除了會影響調度實體在紅黑樹中的位置外，還影響喚醒搶占能否成功。如下：

傳遞的參數中，*curr代表當前正在執行的調度實體，*se代表準備發起搶占的調度實體。此次搶占能否成功，取決于*curr的虛擬時間是否大于*se，當差值超過gran值時，則成功發起一次搶占。這樣設計的邏輯是，*curr通常是上一次調度器選擇時，紅黑樹中最左端的調度實體（即虛擬時間最?。?，在周期tick到來之前，它理應獲得的時間片可能還沒耗盡，此時如果直接允許喚醒的*se發起搶占，那對*curr是不公平的，那么，如果不發生搶占是否可行呢？這里運行隊列已經發生變化（一個新的task掛入隊列），需要盡快重新核算調度周期和時間片，如果等到周期tick命中當前任務再核算可能黃花菜都涼了，一個簡單的例子（圖6）：

圖6 喚醒搶占

調度周期是10ms，任務A和B由于權重相同各分5ms，圖中第二個tick到來后， A時間片耗盡切換到B。1ms后，任務C喚醒。如果發生搶占，那么在喚醒之前的調度周期中，任務B就太可憐了，沒有跟A一樣耗盡時間片。如果不發生搶占，那么喚醒的C需要等待下一次tick到來，基于新的系統狀況來核算任務B的時間片（由于新增高優先級任務，大概率會耗盡其時間片），對于C這個高優先級任務而言，調度延遲又長了點。

總之，交給虛擬時間吧！值得注意的是，gran值依然是受權重值影響，*se的權重越大，gran值越小，其潛在含義是，如果喚醒線程優先級高，那么gran值就小，從而更容易發生喚醒搶占）。如下：

gran = sysctl_sched_wakeup_granularity * (1024 / se->load.weight)

其中，sysctl_sched_wakeup_granularity是內核提供給用戶空間的一個可設置的數值。

三、如何進行優化

3.1 存在的問題

在了解調度的基礎概念以及權重的作用后，我們應該明白調度器是如何運作的。CFS調度策略最讓人驚嘆的就是其基于虛擬時間的公平調度。假定調度周期為10ms，并且只有兩個線程位于同個運行隊列上，則：

對于假設1，兩個線程的權重相同，平分10ms的調度周期，時間片均為5ms，對應的虛擬時間也相同；對于假設2，兩個線程的權重存在差異，時間片也產生很大的差別，但是將時間片轉換為虛擬時間，依然基本一致。注意，以上計算僅存在于理論中，實際上，由于存在調度時機，線程并不會在0.002ms后立刻發生切換。

這樣的“公平”設計很巧妙，但是依然不滿足手機這種強交互設備對及時性的需求。首先，執行時間會不斷累積到虛擬時間上，這意味著，一個長時間執行的線程，即便權重很高，它依然逃脫不了虛擬時間的不停增加，也就存在被其它長時間睡眠的喚醒線程搶占的可能性。其次，實際運行情況下，即便一個線程的權重很高，它始終不能分到一個周期內全部的時間片，并且分到的時間片也是有限的，當時鐘周期tick命中后，cpu使用權交給另一個線程，往往需要到下一個周期tick的調度點才能交換回來。

3.2 調度優化點

從2.2節表2可以發現，原生android對系統中一些關鍵線程會進行優化，比如將負責圖形顯示合成的surfaceflinger線程、hw-composer線程更改為實時調度類，能有效降低調度延遲，確保任務執行完再調度出去。但系統中如果存在較多的實時線程是不合適的，實時線程并不講究“公平”，很可能會導致關鍵線程執行互相受到影響，或者影響其它普通線程。因此，android主要還是通過提高CFS調度類線程的優先級來進行改善，如音頻普通線程使用的nice值為-16，前臺交互應用的UI、Render線程使用的nice值為-10，system_server下一些關鍵持鎖線程nice值為-2或者-4。

從3.1節我們也可以知道，這樣的優化在高負載下仍然會存在問題，現在系統中CFS調度類的線程對時延要求越來越高，比如120刷新率的界面，一幀合成時間就要求在8ms以內，也就兩個周期tick的時間長度（250HZ）。因此，我們可以從更底層的角度去對這些關鍵的CFS調度類線程做改善，比如做以下嘗試：

（1）喚醒搶占維度：關鍵線程喚醒時，我們是不是可以不考慮虛擬時間的評估，直接對當前非關鍵線程發起搶占呢；反之，非關鍵線程在喚醒時，則不允許對關鍵線程進行搶占。

（2）避開高優先級調度類：關鍵線程在選核時，如果能避開更高優先級調度類所在的核心，那么這一部分的調度延遲就可以避免。

（3）虛擬時間補償：原生內核其實已經存在此類做法，當線程長時間休眠時，并不會累加運行時間到其虛擬時間，線程喚醒后，將遠小于當前運行隊列的虛擬時間最小值。試想一下，如果我們不做任何改動，那該線程將長期霸占紅黑樹最左端的位置，這顯然是不合理的。因此在喚醒時，內核對其進行修正，使虛擬時間對齊到最小虛擬時間的基礎上，僅減少半個或1個調度周期時長作為補償。對于短時間休眠呢？短休眠的線程有可能其虛擬時間大于補償后的時間，那就仍維持現狀掛入。

對于關鍵線程，我們依然可以采用這個思路，喚醒時削減一定的虛擬時間作為補償，使其在接下來的幾次調度中占據優勢。

圖7 原生內核對休眠線程的vruntime補償

四、組調度的引入

4.1 認識調度組

谷歌這兩年在推行通用內核鏡像（GKI），使用android系統的手機廠商，都必須確保設備能直接使用GKI鏡像，因此，廠商在內核修改這一塊存在許多限制。在kernel-5.4內核引入GKI1.0之后，我們發現谷歌使能組調度功能， CONFIG_FAIR_GROUP_SCHED配置為true，分組的情況如圖8所示，關鍵組別如下：

dev/cpuctl/tasks ---- root組

dev/cpuctl/top-app/tasks ---- top-app組（用戶交互組）

dev/cpuctl/foreground/tasks ---- 前臺組

dev/cpuctl/background/tasks ---- 后臺組

...

圖8 android使用組調度

組調度對CFS調度策略的影響是顯著的，原生內核提供這套機制，是為了將各類線程按group的形式進行資源分配，也就是將同一屬性的線程歸納到同一個group下，而android系統也順勢將各類應用進程、服務進程放入相應的組中，內核線程則默認放在root組（這一點很重要）。

4.2 公平分配規則的變動

我們在2.2節提到過調度實體的概念，當時是將每個線程看做一個調度實體，而調度實體是掛在運行隊列上的，引入調度組之后，調度實體就不一定是代表一個待執行線程了，組調度為其建立起層級結構，如圖9所示。

圖9 組調度建立起層級結構

在頂層的cfs_rq上，掛載兩個調度實體，其中一個為task級別的se，屬于root group，你可以把它當成某個內核線程，它的pid號記錄在“dev/cpuctl/tasks”中，另一個為group級別的se，代表某個調度組在當前cpu上的調度實體，比如前臺組“foreground”。聰明的你已經發現，group的se擁有自己的運行隊列，屬于第二層的cfs_rq，其上掛載該組在當前cpu上的線程，記錄在“dev/cpuctl/foreground/tasks”中。

層級結構引入后，時間片的分配規則也隨之產生變化。我們之前提到，一個調度周期會按當前運行隊列各個調度實體的權重占比進行分配，但層級結構需要注意的分配規則變動有兩個：

（1）調度周期的分配自上而下。假如我們給定調度周期為10ms，那么，這10個ms將從頂層的cfs_rq開始分配，分配依然是按se的權重占比劃分。我們假定頂層cfs_rq底下的兩個se（task級別和group級別）各自分得5ms，那么group se的5個ms，將繼續往下一層分配給其維護的第二層cfs_rq的task se們。

（2）group級別se的權重不再與nice值掛鉤。我們之前提到，task級別的se，即具體某一個線程，可以通過調節nice值更改其權重，進而影響時間片的分配、虛擬時間的累加。然而，group se下面維護的cfs_rq，可能存在多個task se，難道是將這些task se的權重累加嗎？顯然不是這樣的，linux的設計總是統一而優雅，對于一個group se，也有其與權重掛鉤的“nice”值。

我們注意到，圖8中存在一個參數“cpu.shares”。share值即代表當前group級別se的權重，它并不受其子task se的影響，這個值在android平臺默認是1024。你也可以在其他group目錄如“dev/cpuctl/foreground/”中發現它的存在。

4.3 帶來的問題

受到4.2節（1）的影響，我們對某個task se進行虛擬時間上的補償優化，意義已經不大，因為如果你的task se是掛在某個group的cfs_rq下，那么這個做法只會讓task在group所屬的cfs_rq中存在優勢，而要讓它優先得到執行，調度器必須得先在頂層的cfs_rq中選中這個group se才行。那對group se做虛擬時間補償如何？這樣也不行，相當于group底下的所有子task se都會受益，并且你還不能確保目標task能優先得到執行。

受4.2節（2）的影響，nice值的作用在不同層級的cfs_rq中表現就不一樣了。我們之前說到group se的權重即share值，這樣的說法也不太準確，實際上，同個組的線程們極有可能運行在不同的cpu，所以內核同樣采取占比的方式來計算對應cpu上的group se的權重，公式如下：

ge->load.weight = tg->weight * grq->load.weight / SUM(grq->load.weight)

其中，ge->load.weight是當前cpu掛載的group se的權重；tg->weight就是我們提到的share值；grq->load.weight就是當前cpu掛載的group se，其維護的cfs_rq的權重，這個值是其上掛載的所有task se的權重總和；SUM(grq->load.weight)自然是group se在所有cpu的cfs_rq的權重總和。

感興趣的伙伴可以看下內核函數calc_group_shares(struct cfs_rq *cfs_rq)，上面擁有非常詳細的注釋，這個函數用來更新group se的權重，它在線程入隊、出隊、周期tick命中以及用戶修改share值時，都會調用更新。

下面通過2個實驗來看下組調度帶來的影響。我們首先創建4個循環執行的線程，命名為“root_0”、“root_1”、“top_0”、“top_1”。其中，“root_0”、“root_1”維持默認分組，也就是在root group中，它們入隊時，會直接掛在頂層的cfs_rq?！皌op_0”、“top_1”則放入新創建的tmp group中，避免收到其它線程的干擾，它們位于所在cpu的group se維護的cfs_rq。之后，我們將“root_0”、“top_0”綁定在cpu4，“root_1”、“top_1”綁定在cpu5。則調度實體的分布如圖10所示。

圖10 調度實體的分布

實驗一：4個線程nice值均為默認值0（對應權重為1024），root group和tmp group的share值均為默認值1024，調度周期target latency為10ms?！皌op_0”和“top_1”雖然處于不同的cpu，但它們都屬于tmp group。cpu4上“top_0”的時間片分配規則為：

（1）計算其所在group即tmp_grp_se的權重

tmp_grp_se.weight = tmp_grp.share * top_0_se.weight / (top_0_se.weight + top_1_se.weight) = 512

（2）頂層cfs_rq目前掛載兩個se，它們的時間片分別為：

root_0_se_slice = target_latency * root_0_se.weight / (root_0_se.weight + tmp_grp_se.weight) = 6.7 ms

tmp_grp_se_slice = target_latency * tmp_grp_se.weight / (root_0_se.weight + tmp_grp_se.weight) = 3.3 ms

（3）tmp_grp再將其配額分給其擁有的task se。由于其所屬的cfs_rq上只掛著“top_0”，因此top_0_se_slice為3.3 ms。

可以看到，雖然所有線程的nice值都是0，但是處于root group下的“root_0”卻拿到多出一倍的時間配額。

圖 11 實驗一運行結果

實驗二：在實驗一的基礎上，我們將“top_0”的nice值調整為-10，讓它成為高優先級線程，其余條件不變。按照之前的處理步驟，在cpu4上，“root_0”拿到的時間片為5.3 ms，“top_0”拿到的時間片為4.7 ms，一個高優先級的線程居然跟低優先級的線程旗鼓相當！

圖 12 實驗二運行結果

我們也可以通過調整share值來影響結果，在此不再演示?，F在我們再回過來看下，CFS調度策略還公平嗎？其實從調度組的維度來看，還是公平的。這里我們難受的一點在于，root group的線程各自獨立，在計算權重時擁有很大優勢，但實際上這些線程很少直接參與用戶圖形繪制、音頻輸入等業務。具體的業務線程又被android推入諸如top-app、foreground組，組內還包含其它不影響用戶體驗的線程，同個組的線程分散在不同的核上，引起組權重的重新分配，也就是說，一些關鍵業務線程的時間片分配會受到同組內其他不相關線程的影響；另一個點，android的業務設計上，不同組之間的線程可能會建立聯系，如app層對框架層的依賴，內核層的公共資源爭奪等，也就是說，一些關鍵業務線程也會在某些特定場景下依賴其他組的線程，這些線程理論上在這個時刻更應該看做是同個組。總之，目前調度組這樣的使用方式會帶來問題，僅從share值和nice值去調整，是很難達到目的。

五、結語

我們今天了解到權重在CFS調度策略中的重要地位，也了解到CFS調度策略存在的一些問題，包括引入組調度后產生的弊端。基于權重的“公平”，看起來并不能滿足手機場景對于關鍵線程的調度需求。如何保證關鍵線程的及時調度，同時又不餓死其它線程，或許還需要一種新的機制引入，至少目前來看，權重對這一塊的調節很有限。

參考文獻：

1、https://github.com/oppo-source/android_kernel_5.10_oppo_mt6983/

2、http://www.wowotech.net/sort/process_management

編輯：黃飛

?