什么是Linux進程調(diào)度器

1、背景知識

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

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

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

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

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

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

1.2 調(diào)度策略

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

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

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

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

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

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

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

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

1.3 進程饑餓

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

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

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

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

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

2、linux進程的分類

2.1 進程的分類

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

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

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

2.2 實時進程與普通進程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2個調(diào)度器

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

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

因此當前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)度算法), 用于對不同類型的進程進行調(diào)度, 或者支持某些特殊的功能

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

idle的運行時機
idle 進程優(yōu)先級為MAX_PRIO，即最低優(yōu)先級。早先版本中，idle是參與調(diào)度的，所以將其優(yōu)先級設(shè)為最低，當沒有其他進程可以運行時，才會調(diào)度執(zhí)行 idle
而目前的版本中idle并不在運行隊列中參與調(diào)度，而是在cpu全局運行隊列rq中含idle指針，指向idle進程, 在調(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)度某一類進程, 也可以用于特殊情況或者調(diào)度特殊功能的進程.

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

3個調(diào)度實體

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

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

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

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

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

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

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

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

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

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

linux針對實時進程實現(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 進程的調(diào)度

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

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

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

當開啟內(nèi)核搶占(默認開啟)時，會多出幾個調(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í)行一個中斷，在中斷會對當前運行進程運行時間進行更新，如果進程需要被調(diào)度，在調(diào)度定時器中斷中會設(shè)置一個調(diào)度標志位，之后從定時器中斷返回，因為上面已經(jīng)提到從中斷上下文返回時是有調(diào)度時機的，在內(nèi)核源碼的匯編代碼中所有中斷返回處理都必須去判斷調(diào)度標志位是否設(shè)置，如設(shè)置則執(zhí)行schedule()進行調(diào)度。

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

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

4.3 搶占標識TIF_NEED_RESCHED

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

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

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

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

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

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

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

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

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

內(nèi)核搶占采用同搶占標識的類似方法被實現(xiàn), linux內(nèi)核在thread_info結(jié)構(gòu)中添加了一個自旋鎖標識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)度器以固定的頻率激活負責當前進程調(diào)度類的周期性調(diào)度方法, 以保證系統(tǒng)的并發(fā)性, 周期性調(diào)度器通過調(diào)用進程所屬調(diào)度器類的task_tick操作完成周期性調(diào)度的通知和配置工作, 通過resched_curr函數(shù)(早期的resched_task函數(shù))設(shè)置搶占標識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分配給與當前活動進程不同的另一個進程, 都會直接調(diào)用主調(diào)度器函數(shù)schedule或者其子函數(shù)__schedule.

__schedule完成搶占

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

4.7 進程上下文切換context_switch

context_switch流程

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

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

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

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

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

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

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

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

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

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

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

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

因此他們也是進程創(chuàng)建的時候設(shè)定好的, 我們通過nice修改的就是普通進程的靜態(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è)置進程的普通優(yōu)先級(實時進程99-rt_priority, 普通進程為static_priority)
• 計算進程的動態(tài)優(yōu)先級(實時進程則維持動態(tài)優(yōu)先級的prio不變, 普通進程的動態(tài)優(yōu)先級即為其普通優(yōu)先級)

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

4.9 喚醒搶占

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

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

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