1、背景知識(shí)

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

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

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

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

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

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

1.2 調(diào)度策略

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

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

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

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

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

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

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

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

1.3 進(jìn)程饑餓

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

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

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

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

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

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

2.1 進(jìn)程的分類(lèi)

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

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

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

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

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

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

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

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

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

linux進(jìn)程的調(diào)度算法其實(shí)經(jīng)過(guò)了很多次的演變, 但是其演變主要是針對(duì)與普通進(jìn)程的, 因?yàn)榍懊嫖覀兲岬竭^(guò)根據(jù)進(jìn)程的不同分類(lèi)Linux采用不同的調(diào)度策略.實(shí)時(shí)進(jìn)程和普通進(jìn)程采用了不同的調(diào)度策略, 更一般的普通進(jìn)程還需要啟發(fā)式的識(shí)別批處理進(jìn)程和交互式進(jìn)程.

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

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

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

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

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

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

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

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

2個(gè)調(diào)度器

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

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

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

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

6種調(diào)度策略

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

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

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

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

5個(gè)調(diào)度器類(lèi)

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

其所屬進(jìn)程的優(yōu)先級(jí)順序?yàn)?/p>

3個(gè)調(diào)度實(shí)體

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

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

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

調(diào)度器類(lèi)的就緒隊(duì)列

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

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

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

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

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

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

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

5種調(diào)度器類(lèi)為什么只有3種調(diào)度實(shí)體

正常來(lái)說(shuō)一個(gè)調(diào)度器類(lèi)應(yīng)該對(duì)應(yīng)一類(lèi)調(diào)度實(shí)體, 但是5種調(diào)度器類(lèi)卻只有了3種調(diào)度實(shí)體?

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

為什么采用EDF實(shí)時(shí)調(diào)度需要單獨(dú)的調(diào)度器類(lèi), 調(diào)度策略和調(diào)度實(shí)體

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

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

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

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

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

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

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

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

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

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

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

4.3 搶占標(biāo)識(shí)TIF_NEED_RESCHED

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

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

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

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

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

一般來(lái)說(shuō)，用戶(hù)搶占發(fā)生幾下情況：

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

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

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

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

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

內(nèi)核自然也提供了一些函數(shù)或者宏, 用來(lái)開(kāi)啟, 關(guān)閉以及檢測(cè)搶占計(jì)數(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)核時(shí)鐘中斷周期性的觸發(fā), 周期性調(diào)度器以固定的頻率激活負(fù)責(zé)當(dāng)前進(jìn)程調(diào)度類(lèi)的周期性調(diào)度方法, 以保證系統(tǒng)的并發(fā)性, 周期性調(diào)度器通過(guò)調(diào)用進(jìn)程所屬調(diào)度器類(lèi)的task_tick操作完成周期性調(diào)度的通知和配置工作, 通過(guò)resched_curr函數(shù)(早期的resched_task函數(shù))設(shè)置搶占標(biāo)識(shí)TIF_NEED_RESCHED來(lái)通知內(nèi)核在必要的時(shí)間由主調(diào)度函數(shù)完成真正的調(diào)度工作, 此種做法稱(chēng)之為延遲調(diào)度策略

4.6 主調(diào)度器schedule

主調(diào)度器

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

__schedule完成搶占

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

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

context_switch流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.9 喚醒搶占

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

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

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