一．說(shuō)明

本文以linux-2.4.10 為例主要分析Linux 進(jìn)程調(diào)度模塊中的schedule 函數(shù)及其相關(guān)的函數(shù)。另外相關(guān)的前提知識(shí)也會(huì)說(shuō)明。默認(rèn)系統(tǒng)平臺(tái)是自己的i386 架構(gòu)的pc。

二．前提知識(shí)

在進(jìn)行schedule 分析之前有必要簡(jiǎn)單說(shuō)明一下系統(tǒng)啟動(dòng)過(guò)程，內(nèi)存分配使用等。這樣才能自然過(guò)渡到schedule 模塊。

首先是Linux各個(gè)功能模塊之間的依賴關(guān)系：

可見(jiàn)進(jìn)程調(diào)度是整個(gè)內(nèi)核的核心。但這部分，我想說(shuō)明的是，我的pc是怎樣把操作系統(tǒng)從硬盤(pán)裝載到內(nèi)存中，并啟動(dòng)進(jìn)程調(diào)度模塊的。然后才是后面對(duì)schedule的具體分析。

首先，啟動(dòng)操作系統(tǒng)部分，涉及到到三個(gè)文件：/arch/i386/boot/bootsect.s、/arch/i386/boot/setup.s、/arch/i386/boot/compressed/head.s。編譯安裝好一個(gè)Linux系統(tǒng)后，bootsect.s模塊被放置在可啟動(dòng)設(shè)備的第一個(gè)扇區(qū)（磁盤(pán)引導(dǎo)扇區(qū)，512字節(jié)）。那么下面開(kāi)始啟動(dòng)過(guò)程，三個(gè)文件在內(nèi)存中的分布與位置的移動(dòng)如下圖。

在經(jīng)過(guò)上圖這一系列過(guò)程后，程序跳轉(zhuǎn)到system模塊中的初始化程序init中執(zhí)行，即/init/main.c文件。該程序執(zhí)行一系列的初始化工作，如寄存器初始化、內(nèi)存初始化、中斷設(shè)置等。之后內(nèi)存的分配如下圖：

此后，CPU有序地從內(nèi)存中讀取程序并執(zhí)行。前面的main從內(nèi)核態(tài)移動(dòng)到用戶態(tài)后，操作系統(tǒng)即建立了任務(wù)0，即進(jìn)程調(diào)度程序。之后再由schedule模塊進(jìn)行整個(gè)Linux操作系統(tǒng)中進(jìn)程的創(chuàng)建（fork），調(diào)度（schedule），銷毀（exit）及各種資源的分配與管理等操作了。值得一說(shuō)的是schedule將創(chuàng)建的第一個(gè)進(jìn)程是init（pid=1），請(qǐng)注意它不是前面的/init/main.c程序段。如果是在GNU/Debian系統(tǒng)下，init 進(jìn)程將依次讀取rcS.d，rcN.d（rc0.d~rc6.d），rc.local三個(gè)run command腳本等，之后系統(tǒng)的初始化就完成了，一系列系統(tǒng)服務(wù)被啟動(dòng)了，系統(tǒng)進(jìn)入單用戶或者多用戶狀態(tài)。然后init 讀取/etc/inittab，啟動(dòng)終端設(shè)備（(exec)getty）供用戶登陸，如debian中會(huì)啟動(dòng)6個(gè)tty，你可以用組合鍵ctrl+alt+Fn（F1~F6）來(lái)切換。

到這里就知道了Linux怎樣啟動(dòng)進(jìn)程調(diào)度模塊了，也知道了進(jìn)程調(diào)度模塊啟動(dòng)的第一個(gè)進(jìn)程init及之后的系統(tǒng)初始化和登陸流程。下面就回過(guò)頭來(lái)分析schedule代碼及其相關(guān)函數(shù)調(diào)用。

三．進(jìn)程調(diào)度涉及的數(shù)據(jù)結(jié)構(gòu)

文件：/linux/include/linux/sched.h

下面只簡(jiǎn)單介紹數(shù)據(jù)結(jié)構(gòu)task_struct中的兩個(gè)字段。

在Linux中，進(jìn)程（Linux中用輕量級(jí)的進(jìn)程來(lái)模擬線程）使用的核心數(shù)據(jù)結(jié)構(gòu)。一個(gè)進(jìn)程在核心中使用一個(gè)task_struct結(jié)構(gòu)來(lái)表示，包含了大量描述該進(jìn)程的信息，其中與調(diào)度器相關(guān)的信息主要包括以下幾個(gè)：

1. state

volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */

Linux的進(jìn)程狀態(tài)主要分為三類：可運(yùn)行的（TASK_RUNNING，相當(dāng)于運(yùn)行態(tài)和就緒態(tài)）；被掛起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可運(yùn)行的（TASK_ZOMBIE），調(diào)度器主要處理的是可運(yùn)行和被掛起兩種狀態(tài)下的進(jìn)程，其中TASK_STOPPED又專門(mén)用于SIGSTP等IPC信號(hào)的響應(yīng)，而TASK_ZOMBIE指的是已退出而暫時(shí)沒(méi)有被父進(jìn)程收回資源的"僵死"進(jìn)程。

2. counter

long counter;

該屬性記錄的是當(dāng)前時(shí)間片內(nèi)該進(jìn)程還允許運(yùn)行的時(shí)間。

四． 就緒進(jìn)程選擇算法（即進(jìn)程調(diào)度算法）

文件：/kernel/sched.c

1.上下文切換

從一個(gè)進(jìn)程的上下文切換到另一個(gè)進(jìn)程的上下文，因?yàn)槠浒l(fā)生頻率很高，所以通常都是調(diào)度器效率高低的關(guān)鍵。schedule()函數(shù)中調(diào)用了switch_to宏，這個(gè)宏實(shí)現(xiàn)了進(jìn)程之間的真正切換，其代碼存放于include/i386/system.h。switch_to宏是用嵌入式匯編寫(xiě)成的，較難理解。

由switch_to()實(shí)現(xiàn)，而它的代碼段在schedule()過(guò)程中調(diào)用，以一個(gè)宏實(shí)現(xiàn)。

switch_to()函數(shù)正常返回，棧上的返回地址是新進(jìn)程的task_struct::thread::eip，即新進(jìn)程上一次被掛起時(shí)設(shè)置的繼續(xù)運(yùn)行的位置（上一次執(zhí)行switch_to()時(shí)的標(biāo)號(hào)"1:"位置）。至此轉(zhuǎn)入新進(jìn)程的上下文中運(yùn)行。

這其中涉及到wakeup，sleepon等函數(shù)來(lái)對(duì)進(jìn)程進(jìn)行睡眠與喚醒操作。

2.選擇算法

Linux schedule()函數(shù)將遍歷就緒隊(duì)列中的所有進(jìn)程，調(diào)用goodness()函數(shù)計(jì)算每一個(gè)進(jìn)程的權(quán)值weight，從中選擇權(quán)值最大的進(jìn)程投入運(yùn)行。

Linux的調(diào)度器主要實(shí)現(xiàn)在schedule()函數(shù)中。

調(diào)度步驟：

Schedule函數(shù)工作流程如下：

（1）清理當(dāng)前運(yùn)行中的進(jìn)程

（2）選擇下一個(gè)要運(yùn)行的進(jìn)程（pick_next_task）

（3）設(shè)置新進(jìn)程的運(yùn)行環(huán)境

（4） 進(jìn)程上下文切換

五. Linux 調(diào)度器將進(jìn)程分為三類

進(jìn)程調(diào)度是操作系統(tǒng)的核心功能。調(diào)度器只是調(diào)度過(guò)程中的一部分，進(jìn)程調(diào)度是非常復(fù)雜的過(guò)程，需要多個(gè)系統(tǒng)協(xié)同工作完成。本文所關(guān)注的僅為調(diào)度器，它的主要工作是在所有 RUNNING 進(jìn)程中選擇最合適的一個(gè)。作為一個(gè)通用操作系統(tǒng)，Linux 調(diào)度器將進(jìn)程分為三類：

1. 交互式進(jìn)程

此類進(jìn)程有大量的人機(jī)交互，因此進(jìn)程不斷地處于睡眠狀態(tài)，等待用戶輸入。典型的應(yīng)用比如編輯器 vi。此類進(jìn)程對(duì)系統(tǒng)響應(yīng)時(shí)間要求比較高，否則用戶會(huì)感覺(jué)系統(tǒng)反應(yīng)遲緩。

2. 批處理進(jìn)程

此類進(jìn)程不需要人機(jī)交互，在后臺(tái)運(yùn)行，需要占用大量的系統(tǒng)資源。但是能夠忍受響應(yīng)延遲。比如編譯器。

3. 實(shí)時(shí)進(jìn)程

實(shí)時(shí)對(duì)調(diào)度延遲的要求最高，這些進(jìn)程往往執(zhí)行非常重要的操作，要求立即響應(yīng)并執(zhí)行。比如視頻播放軟件或飛機(jī)飛行控制系統(tǒng)，很明顯這類程序不能容忍長(zhǎng)時(shí)間的調(diào)度延遲，輕則影響電影放映效果，重則機(jī)毀人亡。

根據(jù)進(jìn)程的不同分類 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)度需求的提供了更完美的支持。

六. 調(diào)度時(shí)機(jī)：調(diào)度什么時(shí)候發(fā)生？即：schedule()函數(shù)什么時(shí)候被調(diào)用？

調(diào)度的發(fā)生主要有兩種方式：

1：主動(dòng)式調(diào)度(自愿調(diào)度)

在內(nèi)核中主動(dòng)直接調(diào)用進(jìn)程調(diào)度函數(shù)schedule()，當(dāng)進(jìn)程需要等待資源而暫時(shí)停止運(yùn)行時(shí)，會(huì)把狀態(tài)置于掛起（睡眠），并主動(dòng)請(qǐng)求調(diào)度，讓出cpu。

2：被動(dòng)式調(diào)度（搶占式調(diào)度、強(qiáng)制調(diào)度）

用戶搶占（2.4  2.6）

內(nèi)核搶占（2.6）

(1)用戶搶占發(fā)生在：從系統(tǒng)調(diào)用返回用戶空間；

                              從中斷處理程序返回用戶空間。

內(nèi)核即將返回用戶空間的時(shí)候，如果need_resched標(biāo)志被設(shè)置，會(huì)導(dǎo)致schedule()被調(diào)用，此時(shí)就會(huì)發(fā)生用戶搶占。

主動(dòng)式調(diào)度是用戶程序自己調(diào)度schedule，也許有人會(huì)覺(jué)得自己的代碼中能引用schedule嗎？也許不行吧，但大家知道wait4我們是可以調(diào)用的，前面我們沒(méi)有給出wait4的代碼，但我們知道在執(zhí)行了wait4效果是父進(jìn)程被掛起，所謂的掛起就是不運(yùn)行了，放棄了CPU，這里發(fā)生了進(jìn)程調(diào)度是顯而易見(jiàn)的，其實(shí)在代碼中有如下幾行：

current->state = TASK_INTERRUPIBLE;schedule();

還有exit也有

current->state = TASK_ZOMBIE; schedule();

這2種發(fā)生了進(jìn)程調(diào)度，從代碼上也可以看出（狀態(tài)被改成了睡眠和僵死，然后去調(diào)度可運(yùn)行進(jìn)程，當(dāng)前進(jìn)程自然不會(huì)再占有CPU運(yùn)行了），從效果中也能看出。這說(shuō)明用戶程序自己可以執(zhí)行進(jìn)程調(diào)度。

(2)內(nèi)核搶占：在不支持內(nèi)核搶占的系統(tǒng)中，進(jìn)程/線程一旦運(yùn)行于內(nèi)核空間，就可以一直執(zhí)行，直到它主動(dòng)放棄或時(shí)間片耗盡為止。這樣一些非常緊急的進(jìn)程或線程將長(zhǎng)時(shí)間得不到運(yùn)行。

在支持內(nèi)核搶占的系統(tǒng)中，更高優(yōu)先級(jí)的進(jìn)程/線程可以搶占正在內(nèi)核空間運(yùn)行的低優(yōu)先級(jí)的進(jìn)程/線程。

關(guān)于搶占式調(diào)度(強(qiáng)制調(diào)度），需要知道的是，CPU在執(zhí)行了當(dāng)前指令之后，在執(zhí)行下一條指令之前，CPU要判斷在當(dāng)前指令執(zhí)行之后是否發(fā)生了中斷或異常，如果發(fā)生了，CPU將比較到來(lái)的中斷優(yōu)先級(jí)和當(dāng)前進(jìn)程的優(yōu)先級(jí)（有硬件參與實(shí)現(xiàn)，如中斷控制器8259A芯片；通過(guò)比較寄存器的值來(lái)判斷優(yōu)先級(jí)；中斷服務(wù)程序的入口地址形成有硬件參與實(shí)現(xiàn)，等等，具體實(shí)現(xiàn)請(qǐng)見(jiàn)相關(guān)資料和書(shū)籍），如果新來(lái)任務(wù)的優(yōu)先級(jí)更高，則執(zhí)行中斷服務(wù)程序，在返回中斷時(shí)，將執(zhí)行進(jìn)程調(diào)度函數(shù)schedule。

關(guān)于搶占式調(diào)度，系統(tǒng)代碼中，除了前面我們說(shuō)到的wait4和exit等外（這兩個(gè)系統(tǒng)函數(shù)是自愿或主動(dòng)調(diào)度），還有一個(gè)地方會(huì)出現(xiàn)了schedule，就是中斷返回代碼里面出現(xiàn)了，這里出現(xiàn)了還加了限制條件，我們可以看看這個(gè)代碼（所謂的中斷返回代碼，就是恢復(fù)中斷現(xiàn)場(chǎng)的代碼，每一個(gè)發(fā)生中斷都會(huì)執(zhí)行到的代碼，無(wú)論是什么中斷），這段代碼是：

277 testl $(VM_MASK | 3),%eax  # return to VM86 mode or non-supervisor?

278 jne ret_with_reschedule

279 jmp restore_all

我們看到jne ret_with_reschedule在此之前還有一次條件判斷，代碼就不過(guò)多解釋了，意思是：當(dāng)中斷發(fā)生在用戶控件時(shí)候才會(huì)執(zhí)行ret_with_reschedule，那么我們就看到，在中斷返回到用戶空間的前夕也是可能會(huì)發(fā)生進(jìn)程調(diào)度的。

 簡(jiǎn)單的說(shuō)進(jìn)程調(diào)度發(fā)生的兩種情況：中斷返回用戶空間前夕，和用戶程序自愿放棄CPU，這2種情況會(huì)發(fā)生進(jìn)程調(diào)度。

在支持內(nèi)核搶占的系統(tǒng)中,某些特例下是不允許內(nèi)核被搶占的：

（a）內(nèi)核正在運(yùn)行中斷處理程序，進(jìn)程調(diào)度函數(shù)schedule（）會(huì)對(duì)此作出判斷，如果是在中斷中調(diào)用，會(huì)打印出錯(cuò)誤信息。

（b） 內(nèi)核正在進(jìn)行中斷上下文的bottom half（中斷的底半部）處理，硬件中斷返回前會(huì)執(zhí)行軟中斷，此時(shí)仍然處于中斷上下文。

（c） 進(jìn)程正持有spinlock自旋鎖，writelock/readlock讀寫(xiě)鎖等，當(dāng)持有這些鎖時(shí)，不應(yīng)該被搶占，否則由于搶占將導(dǎo)致其他cpu長(zhǎng)時(shí)間不能獲得鎖而死鎖。

（d） 內(nèi)核正在執(zhí)行調(diào)度程序scheduler

為了保證linux內(nèi)核在以上情況下不會(huì)被搶占，搶占式內(nèi)核使用了一個(gè)變量preempt_count,稱為內(nèi)核搶占計(jì)數(shù)。這一變量被設(shè)置在進(jìn)程的thread_info結(jié)構(gòu)體中，每當(dāng)內(nèi)核要進(jìn)入以上幾種狀態(tài)時(shí)，變量preempt_count就加1，指示內(nèi)核不允許搶占，反之減1。 

內(nèi)核搶占可能發(fā)生在：

1：中斷處理程序完成，返回內(nèi)核空間之前

2：當(dāng)內(nèi)核代碼再一次具有可搶占性的時(shí)候，如解鎖及使能軟中斷等。 

調(diào)度標(biāo)志——Tif_NEED_RESCHED

作用：內(nèi)核提供了一個(gè)need_resched標(biāo)志來(lái)表明是否需要重新執(zhí)行一次調(diào)度。

設(shè)置：當(dāng)某個(gè)進(jìn)程耗盡它的時(shí)間片，會(huì)設(shè)置這個(gè)標(biāo)志

        當(dāng)一個(gè)優(yōu)先級(jí)更高的進(jìn)程進(jìn)入可執(zhí)行狀態(tài)的時(shí)候，也會(huì)設(shè)置這個(gè)標(biāo)志位

進(jìn)程并發(fā)不能靠進(jìn)程自覺(jué)調(diào)度，只有靠中斷(時(shí)鐘中斷)。

七. 內(nèi)核調(diào)度和內(nèi)核的理解

1. 內(nèi)核調(diào)度也算是一個(gè)任務(wù)嗎??

答：不，內(nèi)核調(diào)度只能說(shuō)是一種任務(wù)調(diào)度的算法，它不一直在運(yùn)行，只是在任務(wù)結(jié)束/時(shí)間片結(jié)束的時(shí)候才執(zhí)行，選擇下一個(gè)要運(yùn)行的任務(wù)。

2. 任務(wù)和內(nèi)核的關(guān)系？

答：任務(wù)是運(yùn)行在內(nèi)核的管理之下的，也可以說(shuō)任務(wù)是運(yùn)行在內(nèi)核的這個(gè)環(huán)境里的。

內(nèi)核調(diào)度只是內(nèi)核功能的一部份。內(nèi)核本身不存在調(diào)度，它可以說(shuō)一直在運(yùn)行，主要是運(yùn)行在任務(wù)之內(nèi)和之間，它負(fù)責(zé)任務(wù)所需的資源處理。

3. 它和正在運(yùn)行的那個(gè)最高優(yōu)先級(jí)的任務(wù)是一種什么樣的關(guān)聯(lián)呢??

答：不管優(yōu)先級(jí)多高，它都是運(yùn)行在內(nèi)核環(huán)境下的，內(nèi)核是一直在運(yùn)行的，只不過(guò)它是把CPU和其它資源分配給任務(wù)，讓它運(yùn)行而已。

4. 什么是內(nèi)核？

答：其實(shí)內(nèi)核不是一個(gè)進(jìn)程，也不是一個(gè)現(xiàn)程。

內(nèi)核通過(guò)他提供的api，融合進(jìn)了應(yīng)用程序。也就是說(shuō)內(nèi)核只是一種抽象的說(shuō)法，他本身并不存在，而是在一些特定的時(shí)間和特定的條件才運(yùn)行，才給我們的應(yīng)用程序提供各種服務(wù)。