1、背景知識

1.1 什么是調(diào)度器

通常來說，操作系統(tǒng)是應(yīng)用程序和可用資源之間的媒介。

典型的資源有內(nèi)存和物理設(shè)備。但是CPU也可以認(rèn)為是一個資源，調(diào)度器可以臨時分配一個任務(wù)在上面執(zhí)行（單位是時間片）。調(diào)度器使得我們同時執(zhí)行多個程序成為可能，因此可以與具有各種需求的用戶共享CPU。

內(nèi)核必須提供一種方法, 在各個進(jìn)程之間盡可能公平地共享CPU時間, 而同時又要考慮不同的任務(wù)優(yōu)先級.

調(diào)度器的一個重要目標(biāo)是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調(diào)度器還需要面對一些互相沖突的目標(biāo)，例如既要為關(guān)鍵實時任務(wù)最小化響應(yīng)時間, 又要最大限度地提高 CPU 的總體利用率.

調(diào)度器的一般原理是, 按所需分配的計算能力, 向系統(tǒng)中每個進(jìn)程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進(jìn)程被虧待.

1.2 調(diào)度策略

傳統(tǒng)的Unix操作系統(tǒng)的都奧杜算法必須實現(xiàn)幾個互相沖突的目標(biāo):

• 進(jìn)程響應(yīng)時間盡可能快
• 后臺作業(yè)的吞吐量盡可能高
• 盡可能避免進(jìn)程的饑餓現(xiàn)象
• 低優(yōu)先級和高優(yōu)先級進(jìn)程的需要盡可能調(diào)和等等

調(diào)度策略(scheduling policy)的任務(wù)就是決定什么時候以怎么樣的方式選擇一個新進(jìn)程占用CPU運行.

傳統(tǒng)操作系統(tǒng)的調(diào)度基于分時(time sharing)技術(shù): 多個進(jìn)程以”時間多路服用”方式運行, 因為CPU的時間被分成”片(slice)”, 給每個可運行進(jìn)程分配一片CPU時間片, 當(dāng)然單處理器在任何給定的時刻只能運行一個進(jìn)程.

如果當(dāng)前可運行進(jìn)程的時限(quantum)到期時(即時間片用盡), 而該進(jìn)程還沒有運行完畢, 進(jìn)程切換就可以發(fā)生.

分時依賴于定時中斷, 因此對進(jìn)程是透明的, 不需要在承租中插入額外的代碼來保證CPU分時.

調(diào)度策略也是根據(jù)進(jìn)程的優(yōu)先級對他們進(jìn)行分類. 有時用復(fù)雜的算法求出進(jìn)程當(dāng)前的優(yōu)先級, 但最后的結(jié)果是相同的: 每個進(jìn)程都與一個值(優(yōu)先級)相關(guān)聯(lián), 這個值表示把進(jìn)程如何適當(dāng)?shù)胤峙浣oCPU.

在linux中, 進(jìn)程的優(yōu)先級是動態(tài)的. 調(diào)度程序跟蹤進(jìn)程正在做什么, 并周期性的調(diào)整他們的優(yōu)先級. 在這種方式下, 在較長的時間間隔內(nèi)沒有任何使用CPU的進(jìn)程, 通過動態(tài)地增加他們的優(yōu)先級來提升他們. 相應(yīng)地, 對于已經(jīng)在CPU上運行了較長時間的進(jìn)程, 通過減少他們的優(yōu)先級來處罰他們.

1.3 進(jìn)程饑餓

進(jìn)程饑餓，即為Starvation，指當(dāng)?shù)却龝r間給進(jìn)程推進(jìn)和響應(yīng)帶來明顯影響稱為進(jìn)程饑餓。當(dāng)饑餓到一定程度的進(jìn)程在等待到即使完成也無實際意義的時候稱為饑餓死亡。

產(chǎn)生饑餓的主要原因是

在一個動態(tài)系統(tǒng)中，對于每類系統(tǒng)資源，操作系統(tǒng)需要確定一個分配策略，當(dāng)多個進(jìn)程同時申請某類資源時，由分配策略確定資源分配給進(jìn)程的次序。

有時資源分配策略可能是不公平的，即不能保證等待時間上界的存在。在這種情況下，即使系統(tǒng)沒有發(fā)生死鎖，某些進(jìn)程也可能會長時間等待．當(dāng)?shù)却龝r間給進(jìn)程推進(jìn)和響應(yīng)帶來明顯影響時，稱發(fā)生了進(jìn)程饑餓，當(dāng)饑餓到一定程度的進(jìn)程所賦予的任務(wù)即使完成也不再具有實際意義時稱該進(jìn)程被餓死。

舉個例子，當(dāng)有多個進(jìn)程需要打印文件時，如果系統(tǒng)分配打印機的策略是最短文件優(yōu)先，那么長文件的打印任務(wù)將由于短文件的源源不斷到來而被無限期推遲，導(dǎo)致最終的饑餓甚至餓死。

2、linux進(jìn)程的分類

2.1 進(jìn)程的分類

當(dāng)涉及有關(guān)調(diào)度的問題時, 傳統(tǒng)上把進(jìn)程分類為”I/O受限(I/O-dound)”或”CPU受限(CPU-bound)”.

另外一種分類法把進(jìn)程區(qū)分為三類:

注意
前面的兩類分類方法在一定程序上相互獨立
例如, 一個批處理進(jìn)程很有可能是I/O受限的(如數(shù)據(jù)庫服務(wù)器), 也可能是CPU受限的(比如圖形繪制程序)

2.2 實時進(jìn)程與普通進(jìn)程

在linux中, 調(diào)度算法可以明確的確認(rèn)所有實時進(jìn)程的身份, 但是沒辦法區(qū)分交互式程序和批處理程序(統(tǒng)稱為普通進(jìn)程), linux2.6的調(diào)度程序?qū)崿F(xiàn)了基于進(jìn)程過去行為的啟發(fā)式算法, 以確定進(jìn)程應(yīng)該被當(dāng)做交互式進(jìn)程還是批處理進(jìn)程. 當(dāng)然與批處理進(jìn)程相比, 調(diào)度程序有偏愛交互式進(jìn)程的傾向

根據(jù)進(jìn)程的不同分類Linux采用不同的調(diào)度策略.

對于實時進(jìn)程，采用FIFO或者Round Robin的調(diào)度策略.

對于普通進(jìn)程，則需要區(qū)分交互式和批處理式的不同。傳統(tǒng)Linux調(diào)度器提高交互式應(yīng)用的優(yōu)先級，使得它們能更快地被調(diào)度。而CFS和RSDL等新的調(diào)度器的核心思想是”完全公平”。這個設(shè)計理念不僅大大簡化了調(diào)度器的代碼復(fù)雜度，還對各種調(diào)度需求的提供了更完美的支持.

注意Linux通過將進(jìn)程和線程調(diào)度視為一個，同時包含二者。進(jìn)程可以看做是單個線程，但是進(jìn)程可以包含共享一定資源（代碼和/或數(shù)據(jù)）的多個線程。因此進(jìn)程調(diào)度也包含了線程調(diào)度的功能.

linux進(jìn)程的調(diào)度算法其實經(jīng)過了很多次的演變, 但是其演變主要是針對與普通進(jìn)程的, 因為前面我們提到過根據(jù)進(jìn)程的不同分類Linux采用不同的調(diào)度策略.實時進(jìn)程和普通進(jìn)程采用了不同的調(diào)度策略, 更一般的普通進(jìn)程還需要啟發(fā)式的識別批處理進(jìn)程和交互式進(jìn)程.

實時進(jìn)程的調(diào)度策略比較簡單, 因為實時進(jìn)程值只要求盡可能快的被響應(yīng), 基于優(yōu)先級, 每個進(jìn)程根據(jù)它重要程度的不同被賦予不同的優(yōu)先級，調(diào)度器在每次調(diào)度時, 總選擇優(yōu)先級最高的進(jìn)程開始執(zhí)行. 低優(yōu)先級不可能搶占高優(yōu)先級, 因此FIFO或者Round Robin的調(diào)度策略即可滿足實時進(jìn)程調(diào)度的需求.

但是普通進(jìn)程的調(diào)度策略就比較麻煩了, 因為普通進(jìn)程不能簡單的只看優(yōu)先級, 必須公平的占有CPU, 否則很容易出現(xiàn)進(jìn)程饑餓, 這種情況下用戶會感覺操作系統(tǒng)很卡, 響應(yīng)總是很慢.

此外如何進(jìn)程中如果存在實時進(jìn)程, 則實時進(jìn)程總是在普通進(jìn)程之前被調(diào)度

3、linux調(diào)度器的演變

一開始的調(diào)度器是復(fù)雜度為O(n)O(n)的始調(diào)度算法(實際上每次會遍歷所有任務(wù)，所以復(fù)雜度為O(n)), 這個算法的缺點是當(dāng)內(nèi)核中有很多任務(wù)時，調(diào)度器本身就會耗費不少時間，所以，從linux2.5開始引入赫赫有名的O(1)O(1)調(diào)度器

然而，linux是集全球很多程序員的聰明才智而發(fā)展起來的超級內(nèi)核，沒有最好，只有更好，在O(1)O(1)調(diào)度器風(fēng)光了沒幾天就又被另一個更優(yōu)秀的調(diào)度器取代了，它就是CFS調(diào)度器Completely Fair Scheduler. 這個也是在2.6內(nèi)核中引入的，具體為2.6.23，即從此版本開始，內(nèi)核使用CFS作為它的默認(rèn)調(diào)度器，O(1)O(1)調(diào)度器被拋棄了, 其實CFS的發(fā)展也是經(jīng)歷了很多階段，最早期的樓梯算法(SD), 后來逐步對SD算法進(jìn)行改進(jìn)出RSDL(Rotating Staircase Deadline Scheduler), 這個算法已經(jīng)是”完全公平”的雛形了， 直至CFS是最終被內(nèi)核采納的調(diào)度器, 它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進(jìn)程的睡眠時間，也不再企圖區(qū)分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對待，這就是公平的含義。CFS的算法和實現(xiàn)都相當(dāng)簡單，眾多的測試表明其性能也非常優(yōu)越。

4、Linux的調(diào)度器設(shè)計

4.1 linux進(jìn)程調(diào)度器的框架

2個調(diào)度器

可以用兩種方法來激活調(diào)度

• 一種是直接的, 比如進(jìn)程打算睡眠或出于其他原因放棄CPU
• 另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要

因此當(dāng)前l(fā)inux的調(diào)度程序由兩個調(diào)度器組成：主調(diào)度器，周期性調(diào)度器(兩者又統(tǒng)稱為通用調(diào)度器(generic scheduler)或核心調(diào)度器(core scheduler))

并且每個調(diào)度器包括兩個內(nèi)容：調(diào)度框架(其實質(zhì)就是兩個函數(shù)框架)及調(diào)度器類

6種調(diào)度策略

linux內(nèi)核目前實現(xiàn)了6中調(diào)度策略(即調(diào)度算法), 用于對不同類型的進(jìn)程進(jìn)行調(diào)度, 或者支持某些特殊的功能

比如SCHED_NORMAL和SCHED_BATCH調(diào)度普通的非實時進(jìn)程, SCHED_FIFO和SCHED_RR和SCHED_DEADLINE則采用不同的調(diào)度策略調(diào)度實時進(jìn)程, SCHED_IDLE則在系統(tǒng)空閑時調(diào)用idle進(jìn)程.

idle的運行時機
idle 進(jìn)程優(yōu)先級為MAX_PRIO，即最低優(yōu)先級。早先版本中，idle是參與調(diào)度的，所以將其優(yōu)先級設(shè)為最低，當(dāng)沒有其他進(jìn)程可以運行時，才會調(diào)度執(zhí)行 idle
而目前的版本中idle并不在運行隊列中參與調(diào)度，而是在cpu全局運行隊列rq中含idle指針，指向idle進(jìn)程, 在調(diào)度器發(fā)現(xiàn)運行隊列為空的時候運行, 調(diào)入運行

linux內(nèi)核實現(xiàn)的6種調(diào)度策略, 前面三種策略使用的是cfs調(diào)度器類，后面兩種使用rt調(diào)度器類, 最后一個使用DL調(diào)度器類

5個調(diào)度器類

而依據(jù)其調(diào)度策略的不同實現(xiàn)了5個調(diào)度器類, 一個調(diào)度器類可以用一種種或者多種調(diào)度策略調(diào)度某一類進(jìn)程, 也可以用于特殊情況或者調(diào)度特殊功能的進(jìn)程.

其所屬進(jìn)程的優(yōu)先級順序為

3個調(diào)度實體

調(diào)度器不限于調(diào)度進(jìn)程, 還可以調(diào)度更大的實體, 比如實現(xiàn)組調(diào)度: 可用的CPUI時間首先在一半的進(jìn)程組(比如, 所有進(jìn)程按照所有者分組)之間分配, 接下來分配的時間再在組內(nèi)進(jìn)行二次分配.

這種一般性要求調(diào)度器不直接操作進(jìn)程, 而是處理可調(diào)度實體, 因此需要一個通用的數(shù)據(jù)結(jié)構(gòu)描述這個調(diào)度實體,即seched_entity結(jié)構(gòu), 其實際上就代表了一個調(diào)度對象，可以為一個進(jìn)程，也可以為一個進(jìn)程組.

linux中針對當(dāng)前可調(diào)度的實時和非實時進(jìn)程, 定義了類型為seched_entity的3個調(diào)度實體

調(diào)度器類的就緒隊列

另外，對于調(diào)度框架及調(diào)度器類，它們都有自己管理的運行隊列，調(diào)度框架只識別rq（其實它也不能算是運行隊列），而對于cfs調(diào)度器類它的運行隊列則是cfs_rq（內(nèi)部使用紅黑樹組織調(diào)度實體），實時rt的運行隊列則為rt_rq（內(nèi)部使用優(yōu)先級bitmap+雙向鏈表組織調(diào)度實體）, 此外內(nèi)核對新增的dl實時調(diào)度策略也提供了運行隊列dl_rq

調(diào)度器整體框架

本質(zhì)上, 通用調(diào)度器(核心調(diào)度器)是一個分配器,與其他兩個組件交互.

• 調(diào)度器用于判斷接下來運行哪個進(jìn)程，內(nèi)核支持不同的調(diào)度策略(完全公平調(diào)度, 實時調(diào)度, 在無事可做的時候調(diào)度空閑進(jìn)程,即0號進(jìn)程也叫swapper進(jìn)程,idle進(jìn)程), 調(diào)度類使得能夠以模塊化的方法實現(xiàn)這些側(cè)露額, 即一個類的代碼不需要與其他類的代碼交互
• 當(dāng)調(diào)度器被調(diào)用時, 他會查詢調(diào)度器類, 得知接下來運行哪個進(jìn)程，在選中將要運行的進(jìn)程之后, 必須執(zhí)行底層的任務(wù)切換，這需要與CPU的緊密交互. 每個進(jìn)程剛好屬于某一調(diào)度類, 各個調(diào)度類負(fù)責(zé)管理所屬的進(jìn)程. 通用調(diào)度器自身不涉及進(jìn)程管理, 其工作都委托給調(diào)度器類.

每個進(jìn)程都屬于某個調(diào)度器類(由字段task_struct->sched_class標(biāo)識), 由調(diào)度器類采用進(jìn)程對應(yīng)的調(diào)度策略調(diào)度(由task_struct->policy )進(jìn)行調(diào)度, task_struct也存儲了其對應(yīng)的調(diào)度實體標(biāo)識

linux實現(xiàn)了6種調(diào)度策略, 依據(jù)其調(diào)度策略的不同實現(xiàn)了5個調(diào)度器類, 一個調(diào)度器類可以用一種或者多種調(diào)度策略調(diào)度某一類進(jìn)程, 也可以用于特殊情況或者調(diào)度特殊功能的進(jìn)程.

它們的關(guān)系如下圖

5種調(diào)度器類為什么只有3種調(diào)度實體

正常來說一個調(diào)度器類應(yīng)該對應(yīng)一類調(diào)度實體, 但是5種調(diào)度器類卻只有了3種調(diào)度實體?

這是因為調(diào)度實體本質(zhì)是一個可以被調(diào)度的對象, 要么是一個進(jìn)程(linux中線程本質(zhì)上也是進(jìn)程), 要么是一個進(jìn)程組, 只有dl_sched_class, rt_sched_class調(diào)度的實時進(jìn)程(組)以及fair_sched_class調(diào)度的非實時進(jìn)程(組)是可以被調(diào)度的實體對象, 而stop_sched_class和idle_sched_class

為什么采用EDF實時調(diào)度需要單獨的調(diào)度器類, 調(diào)度策略和調(diào)度實體

linux針對實時進(jìn)程實現(xiàn)了Roound-Robin, FIFO和Earliest-Deadline-First(EDF)算法, 但是為什么SCHED_RR和SCHED_FIFO兩種調(diào)度算法都用rt_sched_class調(diào)度類和sched_rt_entity調(diào)度實體描述, 而EDF算法卻需要單獨用rt_sched_class調(diào)度類和sched_dl_entity調(diào)度實體描述

為什么采用EDF實時調(diào)度不用rt_sched_class調(diào)度類調(diào)度, 而是單獨實現(xiàn)調(diào)度類和調(diào)度實體?

4.2 進(jìn)程的調(diào)度

首先，我們需要清楚，什么樣的進(jìn)程會進(jìn)入調(diào)度器進(jìn)行選擇，就是處于TASK_RUNNING狀態(tài)的進(jìn)程，而其他狀態(tài)下的進(jìn)程都不會進(jìn)入調(diào)度器進(jìn)行調(diào)度。

系統(tǒng)發(fā)生調(diào)度的時機如下

• 調(diào)用cond_resched()時
• 顯式調(diào)用schedule()時
• 從系統(tǒng)調(diào)用或者異常中斷返回用戶空間時
• 從中斷上下文返回用戶空間時

當(dāng)開啟內(nèi)核搶占(默認(rèn)開啟)時，會多出幾個調(diào)度時機，如下

• 在系統(tǒng)調(diào)用或者異常中斷上下文中調(diào)用preempt_enable()時(多次調(diào)用preempt_enable()時，系統(tǒng)只會在最后一次調(diào)用時會調(diào)度)
• 在中斷上下文中，從中斷處理函數(shù)返回到可搶占的上下文時(這里是中斷下半部，中斷上半部實際上會關(guān)中斷，而新的中斷只會被登記，由于上半部處理很快，上半部處理完成后才會執(zhí)行新的中斷信號，這樣就形成了中斷可重入)

而在系統(tǒng)啟動調(diào)度器初始化時會初始化一個調(diào)度定時器，調(diào)度定時器每隔一定時間執(zhí)行一個中斷，在中斷會對當(dāng)前運行進(jìn)程運行時間進(jìn)行更新，如果進(jìn)程需要被調(diào)度，在調(diào)度定時器中斷中會設(shè)置一個調(diào)度標(biāo)志位，之后從定時器中斷返回，因為上面已經(jīng)提到從中斷上下文返回時是有調(diào)度時機的，在內(nèi)核源碼的匯編代碼中所有中斷返回處理都必須去判斷調(diào)度標(biāo)志位是否設(shè)置，如設(shè)置則執(zhí)行schedule()進(jìn)行調(diào)度。

而我們知道實時進(jìn)程和普通進(jìn)程是共存的，調(diào)度器是怎么協(xié)調(diào)它們之間的調(diào)度的呢，其實很簡單，每次調(diào)度時，會先在實時進(jìn)程運行隊列中查看是否有可運行的實時進(jìn)程，如果沒有，再去普通進(jìn)程運行隊列找下一個可運行的普通進(jìn)程，如果也沒有，則調(diào)度器會使用idle進(jìn)程進(jìn)行運行。

系統(tǒng)并不是每時每刻都允許調(diào)度的發(fā)生，當(dāng)處于硬中斷期間的時候，調(diào)度是被系統(tǒng)禁止的，之后硬中斷過后才重新允許調(diào)度。而對于異常，系統(tǒng)并不會禁止調(diào)度，也就是在異常上下文中，系統(tǒng)是有可能發(fā)生調(diào)度的。

4.3 搶占標(biāo)識TIF_NEED_RESCHED

內(nèi)核在檢查need_resched標(biāo)識TIF_NEED_RESCHED的值判斷是否需要搶占當(dāng)前進(jìn)程, 內(nèi)核在thread_info的flag中設(shè)置了一個標(biāo)識來標(biāo)志進(jìn)程是否需要重新調(diào)度, 即重新調(diào)度need_resched標(biāo)識TIF_NEED_RESCHED, 內(nèi)核在即將返回用戶空間時會檢查標(biāo)識TIF_NEED_RESCHED標(biāo)志進(jìn)程是否需要重新調(diào)度

系統(tǒng)中每個進(jìn)程都有一個特定于體系結(jié)構(gòu)的struct thread_info結(jié)構(gòu), 用戶層程序被調(diào)度的時候會檢查struct thread_info中的need_resched標(biāo)識TLF_NEED_RESCHED標(biāo)識來檢查自己是否需要被重新調(diào)度.

如果內(nèi)核檢查進(jìn)程的搶占標(biāo)識被設(shè)置, 則會在一個關(guān)鍵的時刻, 調(diào)用調(diào)度器來完成調(diào)度和搶占的工作

4.4 內(nèi)核搶占和用戶搶占

而根據(jù)進(jìn)程搶占發(fā)生的時機, 搶占可以分為內(nèi)核搶占和用戶搶占, 內(nèi)核搶占就是指一個在內(nèi)核態(tài)運行的進(jìn)程, 可能在執(zhí)行內(nèi)核函數(shù)期間被另一個進(jìn)程取

一般來說，用戶搶占發(fā)生幾下情況：

• 從系統(tǒng)調(diào)用返回用戶空間；
• 從中斷(異常)處理程序返回用戶空間

內(nèi)核搶占發(fā)生的時機，一般發(fā)生在：

• 當(dāng)從中斷處理程序正在執(zhí)行，且返回內(nèi)核空間之前。當(dāng)一個中斷處理例程退出，在返回到內(nèi)核態(tài)時(kernel-space)。這是隱式的調(diào)用schedule()函數(shù)，當(dāng)前任務(wù)沒有主動放棄CPU使用權(quán)，而是被剝奪了CPU使用權(quán)。
• 當(dāng)內(nèi)核代碼再一次具有可搶占性的時候，如解鎖（spin_unlock_bh）及使能軟中斷(local_bh_enable)等, 此時當(dāng)kernel code從不可搶占狀態(tài)變?yōu)榭蓳屨紶顟B(tài)時(preemptible again)。也就是preempt_count從正整數(shù)變?yōu)?時。這也是隱式的調(diào)用schedule()函數(shù)
• 如果內(nèi)核中的任務(wù)顯式的調(diào)用schedule(), 任務(wù)主動放棄CPU使用權(quán)
• 如果內(nèi)核中的任務(wù)阻塞(這同樣也會導(dǎo)致調(diào)用schedule()), 導(dǎo)致需要調(diào)用schedule()函數(shù)。任務(wù)主動放棄CPU使用權(quán)

內(nèi)核搶占采用同搶占標(biāo)識的類似方法被實現(xiàn), linux內(nèi)核在thread_info結(jié)構(gòu)中添加了一個自旋鎖標(biāo)識preempt_count, 稱為搶占計數(shù)器(preemption counter).

struct thread_info
{
/* ...... /
int preempt_count; / 0 => preemptable, <0 => BUG /
/ ...... */
}

內(nèi)核自然也提供了一些函數(shù)或者宏, 用來開啟, 關(guān)閉以及檢測搶占計數(shù)器preempt_coun的值, 這些通用的函數(shù)定義在include/asm-generic/preempt.h, 而某些架構(gòu)也定義了自己的接口， 比如x86架構(gòu)/arch/x86/include/asm/preempt.h

4.5 周期性調(diào)度器scheduler_tick

周期調(diào)度器

周期性調(diào)度器scheduler_tick由內(nèi)核時鐘中斷周期性的觸發(fā), 周期性調(diào)度器以固定的頻率激活負(fù)責(zé)當(dāng)前進(jìn)程調(diào)度類的周期性調(diào)度方法, 以保證系統(tǒng)的并發(fā)性, 周期性調(diào)度器通過調(diào)用進(jìn)程所屬調(diào)度器類的task_tick操作完成周期性調(diào)度的通知和配置工作, 通過resched_curr函數(shù)(早期的resched_task函數(shù))設(shè)置搶占標(biāo)識TIF_NEED_RESCHED來通知內(nèi)核在必要的時間由主調(diào)度函數(shù)完成真正的調(diào)度工作, 此種做法稱之為延遲調(diào)度策略

4.6 主調(diào)度器schedule

主調(diào)度器

schedule就是主調(diào)度器的工作函數(shù), 在內(nèi)核中的許多地方, 如果要將CPU分配給與當(dāng)前活動進(jìn)程不同的另一個進(jìn)程, 都會直接調(diào)用主調(diào)度器函數(shù)schedule或者其子函數(shù)__schedule.

__schedule完成搶占

• 完成一些必要的檢查, 并設(shè)置進(jìn)程狀態(tài), 處理進(jìn)程所在的就緒隊列
• 調(diào)度全局的pick_next_task選擇搶占的進(jìn)程，如果當(dāng)前cpu上所有的進(jìn)程都是cfs調(diào)度的普通非實時進(jìn)程, 則直接用cfs調(diào)度, 如果無程序可調(diào)度則調(diào)度idle進(jìn)程，否則從優(yōu)先級最高的調(diào)度器類sched_class_highest(目前是stop_sched_class)開始依次遍歷所有調(diào)度器類的pick_next_task函數(shù), 選擇最優(yōu)的那個進(jìn)程執(zhí)行
• context_switch完成進(jìn)程上下文切換，調(diào)用switch_mm(), 把虛擬內(nèi)存從一個進(jìn)程映射切換到新進(jìn)程中，調(diào)用switch_to(),從上一個進(jìn)程的處理器狀態(tài)切換到新進(jìn)程的處理器狀態(tài)。這包括保存、恢復(fù)棧信息和寄存器信息

4.7 進(jìn)程上下文切換context_switch

context_switch流程

context_switch其實是一個分配器, 他會調(diào)用所需的特定體系結(jié)構(gòu)的方法

• 調(diào)用switch_mm(), 把虛擬內(nèi)存從一個進(jìn)程映射切換到新進(jìn)程中，switch_mm更換通過task_struct->mm描述的內(nèi)存管理上下文, 該工作的細(xì)節(jié)取決于處理器, 主要包括加載頁表, 刷出地址轉(zhuǎn)換后備緩沖器(部分或者全部), 向內(nèi)存管理單元(MMU)提供新的信息
• 調(diào)用switch_to(),從上一個進(jìn)程的處理器狀態(tài)切換到新進(jìn)程的處理器狀態(tài)。這包括保存、恢復(fù)棧信息和寄存器信息，switch_to切換處理器寄存器的呢內(nèi)容和內(nèi)核棧(虛擬地址空間的用戶部分已經(jīng)通過switch_mm變更, 其中也包括了用戶狀態(tài)下的棧, 因此switch_to不需要變更用戶棧, 只需變更內(nèi)核棧), 此段代碼嚴(yán)重依賴于體系結(jié)構(gòu), 且代碼通常都是用匯編語言編寫.

為什么switch_to需要3個參數(shù)

在新進(jìn)程被選中執(zhí)行時, 內(nèi)核恢復(fù)到進(jìn)程被切換出去的點繼續(xù)執(zhí)行, 此時內(nèi)核只知道誰之前將新進(jìn)程搶占了, 但是卻不知道新進(jìn)程再次執(zhí)行是搶占了誰, 因此底層的進(jìn)程切換機制必須將此前執(zhí)行的進(jìn)程(即新進(jìn)程搶占的那個進(jìn)程)提供給context_switch. 由于控制流會回到函數(shù)的該中間, 因此無法通過普通函數(shù)的返回值來完成. 因此使用了一個3個參數(shù), 但是邏輯效果是相同的, 仿佛是switch_to是帶有兩個參數(shù)的函數(shù), 而且返回了一個指向此前運行的進(jìn)程的指針.

switch_to(prev, next, last);
即
prev = last = switch_to(prev, next);

其中返回的prev值并不是做參數(shù)的prev值, 而是prev被再次調(diào)度的時候搶占掉的那個進(jìn)程last.

4.8 處理進(jìn)程優(yōu)先級

內(nèi)核使用一些簡單的數(shù)值范圍0~139表示內(nèi)部優(yōu)先級, 數(shù)值越低, 優(yōu)先級越高。

從099的范圍專供實時進(jìn)程使用, nice的值[-20,19]則映射到范圍100139

其中task_struct采用了三個成員表示進(jìn)程的優(yōu)先級:prio和normal_prio表示動態(tài)優(yōu)先級, static_prio表示進(jìn)程的靜態(tài)優(yōu)先級.

此外還用了一個字段rt_priority保存了實時進(jìn)程的優(yōu)先級

靜態(tài)優(yōu)先級static_prio(普通進(jìn)程)和實時優(yōu)先級rt_priority(實時進(jìn)程)是計算的起點

因此他們也是進(jìn)程創(chuàng)建的時候設(shè)定好的, 我們通過nice修改的就是普通進(jìn)程的靜態(tài)優(yōu)先級static_prio

首先通過靜態(tài)優(yōu)先級static_prio計算出普通優(yōu)先級normal_prio, 該工作可以由nromal_prio來完成, 該函數(shù)定義在kernel/sched/core.c#L861

內(nèi)核通過effective_prio設(shè)置動態(tài)優(yōu)先級prio, 計算動態(tài)優(yōu)先級的流程如下

• 設(shè)置進(jìn)程的普通優(yōu)先級(實時進(jìn)程99-rt_priority, 普通進(jìn)程為static_priority)
• 計算進(jìn)程的動態(tài)優(yōu)先級(實時進(jìn)程則維持動態(tài)優(yōu)先級的prio不變, 普通進(jìn)程的動態(tài)優(yōu)先級即為其普通優(yōu)先級)

最后, 我們綜述一下在針對不同類型進(jìn)程的計算結(jié)果

4.9 喚醒搶占

當(dāng)在try_to_wake_up/wake_up_process和wake_up_new_task中喚醒進(jìn)程時, 內(nèi)核使用全局check_preempt_curr看看是否進(jìn)程可以搶占當(dāng)前進(jìn)程可以搶占當(dāng)前運行的進(jìn)程.

每個調(diào)度器類都因應(yīng)該實現(xiàn)一個check_preempt_curr函數(shù), 在全局check_preempt_curr中會調(diào)用進(jìn)程其所屬調(diào)度器類check_preempt_curr進(jìn)行搶占檢查, 對于完全公平調(diào)度器CFS處理的進(jìn)程, 則對應(yīng)由check_preempt_wakeup函數(shù)執(zhí)行該策略.

新喚醒的進(jìn)程不必一定由完全公平調(diào)度器處理, 如果新進(jìn)程是一個實時進(jìn)程, 則會立即請求調(diào)度, 因為實時進(jìn)程優(yōu)先極高, 實時進(jìn)程總會搶占CFS進(jìn)程。