Linux 2.4调度系统分析--转
http://www.ibm.com/developerworks/cn/linux/kernel/l-k24sch/index.html
楊沙洲?(pubb@163.net)國防科技大學(xué)計算機學(xué)院?
簡介：?本文詳盡地分析了Linux 2.4內(nèi)核中調(diào)度系統(tǒng)的工作原理，特別是i386體系結(jié)構(gòu)下SMP系統(tǒng)的調(diào)度表現(xiàn)。通過對2.4調(diào)度系統(tǒng)實現(xiàn)原理及其細節(jié)的分析，文章在文末指出了2.4調(diào)度系統(tǒng)在功能上、實時性上以及多處理機系統(tǒng)表現(xiàn)上存在的不足，為后繼的2.6系統(tǒng)的分析作鋪墊。
一． 前言
在開源操作系統(tǒng)中，Linux的發(fā)展最為顯著，到目前為止，它在低端服務(wù)器市場已經(jīng)占據(jù)了相當(dāng)大的份額。從最新的Linux 2.6系統(tǒng)來看，Linux的發(fā)展方向主要有兩個：嵌入式系統(tǒng)和高端計算領(lǐng)域。
調(diào)度系統(tǒng)對于操作系統(tǒng)的整體性能有著非常重要的影響，嵌入式系統(tǒng)、桌面系統(tǒng)和高端服務(wù)器對于調(diào)度器的要求是很不一樣的。Linux調(diào)度器的特點主要有兩個：
- 核心不可搶占；
- 調(diào)度算法簡單有效。
由于Linux適用于多種平臺，本文所指缺省為i386下的SMP系統(tǒng)。
回頁首
二． 相關(guān)數(shù)據(jù)結(jié)構(gòu)
在Linux中，進程用task_struct表示，所有進程被組織到以init_task為表頭的雙向鏈表中（見[include/linux/sched.h]SET_LINKS()宏），該鏈表是全系統(tǒng)唯一的。所有CPU被組織到以schedule_data（對界后）為元素的數(shù)組之中。進程與所運行的CPU之間可以相互訪問（詳見下）。
所有處于運行態(tài)的進程（TASK_RUNNING）被組織到以runqueue_head為表頭的雙向鏈表之中，調(diào)度器總是從中尋找最適合調(diào)度的進程。runqueue_head也是全系統(tǒng)唯一的。
下面分別介紹這些與調(diào)度器工作相關(guān)的數(shù)據(jù)結(jié)構(gòu)。
1． init_tss
TSS，Task State Segment，80x86平臺特有的進程運行環(huán)境，盡管Linux并不使用TSS，但將TSS所需要描述的信息保存在以cpu號為索引的tss_struct數(shù)組init_tss中，進程切換時，其中的值將獲得更新。
2． task_struct
在Linux中，線程、進程使用的是相同的核心數(shù)據(jù)結(jié)構(gòu)，可以說，在2.4的內(nèi)核里只有進程，其中包含輕量進程。一個進程在核心中使用一個task_struct結(jié)構(gòu)來表示，包含了大量描述該進程的信息，其中與調(diào)度器相關(guān)的信息主要包括以下幾個：
i. state
Linux的進程狀態(tài)主要分為三類：可運行的（TASK_RUNNING，相當(dāng)于運行態(tài)和就緒態(tài)）；被掛起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可運行的（TASK_ZOMBIE），調(diào)度器主要處理的是可運行和被掛起兩種狀態(tài)下的進程，其中TASK_STOPPED又專門用于SIGSTP等IPC信號的響應(yīng)，而TASK_ZOMBIE指的是已退出而暫時沒有被父進程收回資源的"僵尸"進程。
ii. need_resched
布爾值，在調(diào)度器中用于表示該進程需要申請調(diào)度（詳見"調(diào)度器工作流程"）。
iii. policy
在Linux 2.4中，進程的調(diào)度策略可以有三種選擇：SCHED_FIFO（先進先出式調(diào)度，除非有更高優(yōu)先級進程申請運行，否則該進程將保持運行至退出才讓出CPU）、SCHED_RR（輪轉(zhuǎn)式調(diào)度，該進程被調(diào)度下來后將被置于運行隊列的末尾，以保證其他實時進程有機會運行）、SCHED_OTHER（常規(guī)的分時調(diào)度策略）。另外，policy中還包含了一個SCHED_YIELD位，置位時表示主動放棄CPU。
iv. rt_priority
用于表征實時進程的優(yōu)先級，從1-99取值，非實時進程該項應(yīng)該為0。這一屬性將用于調(diào)度時的權(quán)值計算（詳見"就緒進程選擇算法"）。
v. counter
該屬性記錄的是當(dāng)前時間片內(nèi)該進程還允許運行的時間（以CPU時鐘tick值為單位，每個進程的counter初值與nice值有關(guān)，nice越小則counter越大，即優(yōu)先級越高的進程所允許獲得的CPU時間也相對越多），并參與"就緒進程選擇算法"。在Linux 2.4中，每個（非SCHED_FIFO實時）進程都不允許運行大于某一時間片的時間，一旦超時，調(diào)度器將強制選擇另一進程運行（詳見"調(diào)度器工作流程"）
vi. nice
用戶可支配的進程優(yōu)先級，將參與"就緒進程選擇算法"，同時該值也決定了該進程的時間片長度（詳見下）。
vii. cpus_allowed
以位向量的形式表示可用于該進程運行的CPU（見"調(diào)度器工作流程"）。
viii. cpus_runnable
以位向量的形式表示當(dāng)前運行該進程的CPU（相應(yīng)位為1）。如果不在任何CPU上運行，則為全1。這一屬性和cpus_allowed屬性結(jié)合，可以迅速判斷該進程是否能調(diào)度到某一CPU上運行（位"與"）。
ix. processor
本進程當(dāng)前（或最近）所在CPU編號。
x. thread
用于保存進程執(zhí)行環(huán)境（各個寄存器的值以及IO操作許可權(quán)映射表），內(nèi)容與TSS相近。因為TSS以CPU id為索引，而Linux無法預(yù)測被替換下來的進程下一次將在哪個CPU上運行，所以這些信息不能保存在TSS中。
3． current
核心經(jīng)常需要獲知當(dāng)前在某CPU上運行的進程的task_struct，在Linux中用current指針指向這一描述符。current的實現(xiàn)采用了一個小技巧以獲得高效的訪問速度，這個小技巧與Linux進程task_struct的存儲方式有關(guān)。
在Linux中，進程在核心級運行時所使用的棧不同于在用戶級所分配和使用的棧。因為這個棧使用率不高，因此僅在創(chuàng)建進程時分配了兩個頁（8KB），并且將該進程的task_struct安排在棧頂。（實際上這兩個頁是在分配task_struct時申請的，初始化完task_struct后即將esp預(yù)設(shè)為頁尾作為進程的核心棧棧底，往task_struct方向延伸。）
因此，要訪問本進程的task_struct，只需要執(zhí)行以下簡單操作：
__asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));此句將esp與0x0ffffe0作"與"運算，獲得核心棧的首頁基址，此即為task_struct的地址。
4． schedule_data
task_struct是用于描述進程的數(shù)據(jù)結(jié)構(gòu)，其中包含了指向所運行CPU的屬性。在Linux中，另有一個數(shù)據(jù)結(jié)構(gòu)對應(yīng)于CPU，可以利用它訪問到某CPU上運行的進程，這個數(shù)據(jù)結(jié)構(gòu)定義為schedule_data結(jié)構(gòu)，包含兩個屬性：curr指針，指向當(dāng)前運行于該CPU上的進程的task_struct，通常用cpu_curr(cpu)宏來訪問；last_schedule時間戳，記錄了上一次該CPU上進程切換的時間，通常用last_schedule(cpu)宏來訪問。
為了使該數(shù)據(jù)結(jié)構(gòu)的訪問能與CPU的Cache line大小相一致，schedule_data被組織到以SMP_CACHE_BYTES為單位的aligned_data聯(lián)合數(shù)組中，系統(tǒng)中每個CPU對應(yīng)數(shù)組上的一個元素。
5． init_tasks
調(diào)度器并不直接使用init_task為表頭的進程鏈表，而僅使用其中的"idle_task"。該進程在引導(dǎo)完系統(tǒng)后即處于cpu_idle()循環(huán)中（詳見"其他核心應(yīng)用的調(diào)度相關(guān)部分"之"IDLE進程"）。SMP系統(tǒng)中，每個CPU都分別對應(yīng)了一個idle_task，它們的task_struct指針被組織到init_tasks[NR_CPUS]數(shù)組中，調(diào)度器通過idle_task(cpu)宏來訪問這些"idle"進程（詳見"調(diào)度器工作流程"）。
?
6． runqueue_head
以runqueue_head為表頭的鏈表記錄了所有處于就緒態(tài)的進程（當(dāng)前正在運行的進程也在其中，但idle_task除外），調(diào)度器總是從中選取最適合調(diào)度的進程投入運行。
回頁首
三． 進程切換過程
從一個進程的上下文切換到另一個進程的上下文，因為其發(fā)生頻率很高，所以通常都是調(diào)度器效率高低的關(guān)鍵。在Linux中，這一功能是以一段經(jīng)典的匯編代碼實現(xiàn)的，此處就著力描述這段代碼。
這段名為switch_to()的代碼段在schedule()過程中調(diào)用，以一個宏實現(xiàn)：
| /* 節(jié)選自[include/asm-i386/system.h] */ #define switch_to(prev,next,last) do { \asm volatile("pushl %%esi\n\t" \"pushl %%edi\n\t" \"pushl %%ebp\n\t" \保存esi、edi、ebp寄存器"movl %%esp,%0\n\t" \esp保存到prev->thread.esp中"movl %3,%%esp\n\t" \從next->thread.esp恢復(fù)esp"movl $1f,%1\n\t" \在prev->thread.eip中保存"1："的跳轉(zhuǎn)地址，\當(dāng)prev被再次切換到的時候?qū)哪抢镩_始執(zhí)行"pushl %4\n\t" \在棧上保存next->thread.eip，__switch_to()返回時將轉(zhuǎn)到那里執(zhí)行，\即進入next進程的上下文"jmp __switch_to\n" \跳轉(zhuǎn)到__switch_to()，進一步處理(見下)"1:\t" \"popl %%ebp\n\t" \"popl %%edi\n\t" \"popl %%esi\n\t" \先恢復(fù)上次被切換走時保存的寄存器值，\再從switch_to()中返回。:"=m" (prev->thread.esp), \%0"=m" (prev->thread.eip),\%1"=b" (last) \ebx， \因為進程切換后，恢復(fù)的棧上的prev信息不是剛被切換走的進程描述符， \因此此處使用ebx寄存器傳遞該值給prev:"m" (next->thread.esp), \%3"m" (next->thread.eip), \%4"a" (prev), "d" (next), \eax,edx"b" (prev)); \ebx } while (0) |
?
進程切換過程可以分成兩個階段，上面這段匯編代碼可以看作第一階段，它保存一些關(guān)鍵的寄存器，并在棧上設(shè)置好跳轉(zhuǎn)到新進程的地址。第二階段在switch_to()中啟動，實現(xiàn)在__switch_to()函數(shù)中，主要用于保存和更新不是非常關(guān)鍵的一些寄存器（以及IO操作許可權(quán)映射表ioperm）的值：
- unlazy_fpu()，如果老進程在task_struct的flags中設(shè)置了PF_USEDFPU位，表明它使用了FPU，unlazy_fpu()就會將FPU內(nèi)容保存在task_struct::thread中；
- 用新進程的esp0（task_struct::thread中）更新init_tss中相應(yīng)位置的esp0；
- 在老進程的task_struct::thread中保存當(dāng)前的fs和gs寄存器，然后從新進程的task_struct::thread中恢復(fù)fs和gs寄存器；
- 從新進程的task_struct::thread中恢復(fù)六個調(diào)試寄存器的值；
- 用next中的ioperm更新init_tss中的相應(yīng)內(nèi)容
switch_to()函數(shù)正常返回，棧上的返回地址是新進程的task_struct::thread::eip，即新進程上一次被掛起時設(shè)置的繼續(xù)運行的位置（上一次執(zhí)行switch_to()時的標號"1:"位置）。至此轉(zhuǎn)入新進程的上下文中運行。
在以前的Linux內(nèi)核中，進程的切換使用的是far jmp指令，2.4采用如上所示的手控跳轉(zhuǎn)，所做的動作以及所用的時間均與far jmp差不多，但更利于優(yōu)化和控制。
回頁首
四． 就緒進程選擇算法
Linux schedule()函數(shù)將遍歷就緒隊列中的所有進程，調(diào)用goodness()函數(shù)計算每一個進程的權(quán)值weight，從中選擇權(quán)值最大的進程投入運行。
進程調(diào)度權(quán)值的計算分為實時進程和非實時進程兩類，對于非實時進程（SCHED_OTHER），影響權(quán)值的因素主要有以下幾個：
1. 進程當(dāng)前時間片內(nèi)所剩的tick數(shù)，即task_struct的counter值，相當(dāng)于counter越大的進程獲得CPU的機會也越大，因為counter的初值與（-nice）相關(guān)，因此這一因素一方面代表了進程的優(yōu)先級，另一方面也代表了進程的"欠運行程度"；（weight = p->counter;）
2. 進程上次運行的CPU是否就是當(dāng)前CPU，如果是，則權(quán)值增加一個常量，表示優(yōu)先考慮不遷移CPU的調(diào)度，因為此時Cache信息還有效；（weight += PROC_CHANGE_PENALTY;）
3. 此次切換是否需要切換內(nèi)存，如果不需要（或者是同一進程的兩個線程間的切換，或者是沒有mm屬性的核心線程），則權(quán)值加1，表示（稍微）優(yōu)先考慮不切換內(nèi)存的進程；(weight += 1;)
4. 進程的用戶可見的優(yōu)先級nice，nice越小則權(quán)值越大。（Linux中的nice值在-20到+19之間選擇，缺省值為0，nice()系統(tǒng)調(diào)用可以用來修改優(yōu)先級。）(weight += 20 - p->nice;) 對于實時進程（SCHED_FIFO、SCHED_RR），權(quán)值大小僅由該進程的rt_priority值決定（weight = 1000 + p->rt_priority;），1000的基準量使得實時進程的權(quán)值比所有非實時進程都要大，因此只要就緒隊列中存在實時進程，調(diào)度器都將優(yōu)先滿足它的運行需要。
如果權(quán)值相同，則選擇就緒隊列中位于前列的進程投入運行。
除了以上標準值以外，goodness()還可能返回-1，表示該進程設(shè)置了SCHED_YIELD位，此時，僅當(dāng)不存在其他就緒進程時才會選擇它。
如果遍歷所有就緒進程后，weight值為0，表示當(dāng)前時間片已經(jīng)結(jié)束了，此時將重新計算所有進程（不僅僅是就緒進程）的counter值，再重新進行就緒進程選擇（詳見"調(diào)度器工作流程"）。
回頁首
五． 調(diào)度器
Linux的調(diào)度器主要實現(xiàn)在schedule()函數(shù)中。
1．調(diào)度器工作流程
schedule()函數(shù)的基本流程可以概括為四步：
1). 清理當(dāng)前運行中的進程
2). 選擇下一個投入運行的進程
3). 設(shè)置新進程的運行環(huán)境
4). 執(zhí)行進程上下文切換
5). 后期整理
其中包含了一些鎖操作：就緒隊列鎖runquque_lock，全局核心鎖kernel_flag，全局中斷鎖global_irq_lock，進程列表鎖tasklist_lock。下面先從鎖操作開始描述調(diào)度器的工作過程。
A. 相關(guān)鎖
- runqueue_lock，定義為自旋鎖，對就緒隊列進行操作之前，必須鎖定；
- kernel_flag，定義為自旋鎖，因為很多核心操作（例如驅(qū)動中）需要保證當(dāng)前僅由一個進程執(zhí)行，所以需要調(diào)用lock_kernel()/release_kernel()對核心鎖進行操作，它在鎖定/解鎖kernel_flag的同時還在task_struct::lock_depth上設(shè)置了標志，lock_depth小于0表示未加鎖。當(dāng)發(fā)生進程切換的時候，不允許被切換走的進程握有kernel_flag鎖，所以必須調(diào)用release_kernel_lock()強制釋放，同時，新進程投入運行時如果lock_depth>0，即表明該進程被切換走之前握有核心鎖，必須調(diào)用reacquire_kernel_lock()再次鎖定；
- global_irq_lock，定義為全局的內(nèi)存長整型，使用clear_bit()/set_bit()系列進行操作，它與global_irq_holder配合表示當(dāng)前哪個cpu握有全局中斷鎖，該鎖掛起全局范圍內(nèi)的中斷處理（見irq_enter()）；
- tasklist_lock，定義為讀寫鎖，保護以init_task為頭的進程列表結(jié)構(gòu)。
B. prev
在schedule中，當(dāng)前進程（也就是可能被調(diào)度走的進程）用prev指針訪問。
對于SCHED_RR的實時進程，僅當(dāng)該進程時間片結(jié)束（counter==0）后才會切換到別的進程，此時將根據(jù)nice值重置counter，并將該進程置于就緒隊列的末尾。當(dāng)然，如果當(dāng)前就緒隊列中不存在其他實時進程，則根據(jù)前面提到的goodness()算法，調(diào)度器仍將選擇到該進程。
如果處于TASK_INTERRUPTIBLE狀態(tài)的進程有信號需要處理（這可能發(fā)生在進程因等待信號而準備主動放棄CPU，在放棄CPU之前，信號已經(jīng)發(fā)生了的情況），調(diào)度器并不立即執(zhí)行該進程，而是將該進程置為就緒態(tài)（該進程還未來得及從就緒隊列中刪除），參與緊接著的goodness選擇。
如果prev不處于就緒態(tài)，也不處于上面這種有信號等待處理的掛起態(tài)（prev為等待資源而主動調(diào)用schedule()放棄CPU），那么它將從就緒隊列中刪除，此后，除非有喚醒操作將進程重新放回到就緒隊列，否則它將不參與調(diào)度。
被動方式啟動調(diào)度器工作時，當(dāng)前進程的need_resched屬性會置位（見下"調(diào)度器工作時機"）。在schedule()中，該位會被清掉，表示該進程已經(jīng)在調(diào)度器中得到了處理（當(dāng)然，這一處理并不意味著該進程就一定獲得了CPU）。
C. goodness
調(diào)度器遍歷就緒隊列中的所有進程，只要它當(dāng)前可被調(diào)度（cpus_runnable & cpus_allowed & (1 << cpu)，表示該進程可在當(dāng)前運行調(diào)度器的CPU上運行，且不在其他CPU上運行），就調(diào)用goodness()計算其權(quán)值。next指針用來指向權(quán)值最大的進程，缺省指向idle_task，如果就緒隊列為空，就使用缺省的idle_task作為next。
正如前面所提到的，如果遍歷結(jié)束后的最大權(quán)值為0，則表示當(dāng)前所有可被調(diào)度的就緒進程的時間片都用完了，這時調(diào)度器將需要重新設(shè)置所有進程（包括就緒的和掛起的）的counter值，未完成時間片的進程（例如當(dāng)前被掛起的進程或者當(dāng)前正在其他CPU上運行的進程），其剩下的時間片的一半將疊加到新的時間片中。
將選中的進程設(shè)置為在本CPU上運行（task_set_cpu()）之后，runqueue_lock就可以解開了，接下來就將對next進行配置。
D. next
選取的新進程可能剛好就是需要替換出去的老進程，此時因為實際上不需要進行進程切換，所以可以跳過配置next以及下面的"switch"和"schedule_tail"兩個階段。
新進程的運行環(huán)境實際上主要就是指內(nèi)存。在task_struct中有兩個與調(diào)度器相關(guān)的內(nèi)存屬性：mm和active_mm，前者指向進程所擁有的內(nèi)存區(qū)域，后者則指向進程所實際使用的內(nèi)存。對于大多數(shù)進程，mm和active_mm是相同的，但核心線程沒有自主的內(nèi)存，它們的mm指針永遠為NULL。我們知道，任何進程的虛頁表中，核心空間永遠映射到了虛存的高端固定位置，所以，核心線程所使用的內(nèi)存無論對于哪個進程空間都是一樣的，所以也就沒有必要切換進程的內(nèi)存。在調(diào)度器中，只要判斷一下next->mm是否為空就能知道該進程是不是核心線程，如果是，則繼續(xù)使用prev的active_mm（next->active_mm = prev->active_mm），并通過設(shè)置cpu_tlbstate[cpu].state為TLBSTATE_LAZY，告訴內(nèi)存管理部件不要刷新TLB；否則就調(diào)用switch_mm()函數(shù)進行內(nèi)存的切換（具體過程牽涉到內(nèi)存管理模塊的知識，這里就從略了）。實際上，在switch_mm()中還會對prev->active_mm和next->mm判斷一次，如果兩值相等，說明兩個進程是同屬于一個"進程"的兩個"線程"（實際上是輕量進程），此時也不需要執(zhí)行內(nèi)存的切換，但這種情況TLB還是需要刷新的。
設(shè)置好next的內(nèi)存環(huán)境以后，就可以調(diào)用mmdrop()釋放掉prev的內(nèi)存結(jié)構(gòu)了。所有不在運行中的進程，其active_mm屬性都應(yīng)該為空。
E. switch
進程切換的過程在上文中已經(jīng)描述得比較詳細了。
F. schedule_tail
完成切換后，調(diào)度器將調(diào)用__schedule_tail()。這一函數(shù)對于UP系統(tǒng)基本沒什么影響，對于SMP系統(tǒng)，如果被切換下來的進程（用p表示）仍然處于就緒態(tài)且未被任何CPU調(diào)度到，__schedule_tail()將調(diào)用reschedule_idle()，為p挑選一個空閑的（或者是所運行的進程優(yōu)先級比p低的）CPU，并強迫該CPU重新調(diào)度，以便將p重新投入運行。進程從休眠狀態(tài)中醒來時也同樣需要挑選一個合適的CPU運行，這一操作是通過在wake_up_process()函數(shù)中調(diào)用reschedule_idle()實現(xiàn)的。挑選CPU的原則如下：
- p上次運行的CPU目前空閑。很顯然，這是最佳選擇，因為不需要搶占CPU，CPU Cache也最有可能和p吻合。不過，既然p可運行，調(diào)度器就不可能調(diào)度到idle_task，所以這種情況只會發(fā)生在wake_up_process()的時候。
- 所有空閑的CPU中最近最少活躍（last_schedule(cpu)最小）的一個。該CPU中的Cache信息最有可能是無用的，因此這種選擇方式可以盡最大可能減少搶占CPU的開銷，同時也盡可能避免頻繁搶占。值得注意的是，在使用支持超線程技術(shù)的CPU的SMP平臺上，一旦發(fā)現(xiàn)一個物理CPU的兩個邏輯CPU均空閑，則該CPU的其中一個邏輯CPU立即成為p候選的調(diào)度CPU，而不需要繼續(xù)尋找最近最少活躍的CPU。
- CPU不空閑，但所運行的進程優(yōu)先級比p的優(yōu)先級低，且差值最大。計算優(yōu)先級時使用的是goodness()函數(shù)，因為它所包含的信息最多。
找到合適的CPU后，reschedule_idle()就會將目標進程（正在該CPU上運行的進程，可能是idle_task）的need_resched置為1，以便調(diào)度器能夠工作（見"調(diào)度器工作時機"）。同時，因為idle_task很多情況下都使cpu處于停機（halt）狀態(tài)以節(jié)電，所以有必要調(diào)用smp_send_reschedule(cpu)向cpu發(fā)RESCHEDULE_VECTOR中斷（通過IPI接口），以喚醒該cpu。
注：對于目標進程是idle_task的情況，還要判斷它的need_resched標志位，僅當(dāng)它為0的時候才會啟動調(diào)度，因為非0狀態(tài)的idle_task本身一直都在檢查need_resched值，它自己會啟動schedule()（見下"IDLE進程"）。
G. clear
調(diào)度器工作的結(jié)果有兩種：發(fā)生了切換、沒有發(fā)生切換，但調(diào)度器退出前的清理工作是一樣的，就是恢復(fù)新進程的狀態(tài)。主要包含兩個動作：
- 清被切換走的進程的SCHED_YIELD位（不管它是否置位）；
- 如果新進程（p）的lock_depth大于等于0，則重新為核心鎖kernel_flag加鎖（見上"相關(guān)鎖"）。
2. 調(diào)度器工作時機
調(diào)度器的啟動通常有兩種方式：
A. 主動式
在核心應(yīng)用中直接調(diào)用schedule()。這通常發(fā)生在因等待核心事件而需要將進程置于掛起（休眠）狀態(tài)的時候--這時應(yīng)該主動請求調(diào)度以方便其他進程使用CPU。下面就是一個主動調(diào)度的例子：
| /* 節(jié)選自[drivers/input/mousedev.c] mousedev_read() */add_wait_queue(&list->mousedev->wait, &wait);current->state = TASK_INTERRUPTIBLE;while (!list->ready) {if (file->f_flags & O_NONBLOCK) {retval = -EAGAIN;break;}if (signal_pending(current)) {retval = -ERESTARTSYS;break;}schedule();}current->state = TASK_RUNNING; /* 這一句實際上可以省略，因為進程的狀態(tài)在喚醒過程中就已經(jīng)恢復(fù)到TASK_RUNNING了 */remove_wait_queue(&list->mousedev->wait, &wait); |
?
其過程通常可分為四步：
- 將進程添加到事件等待隊列中；
- 置進程狀態(tài)為TASK_INTERRUPTIBLE（或TASK_UNINTERRUPTIBLE）；
- 在循環(huán)中檢查等待條件是否滿足，不滿足則調(diào)用schedule()，滿足了就退出循環(huán)；
- 將進程從事件等待隊列中刪除。
從"調(diào)度器工作流程"中我們知道，調(diào)度器會將處于休眠狀態(tài)的進程從就緒隊列中刪除，而只有就緒隊列中的進程才有可能被調(diào)度到。將該進程重新放到就緒隊列中的動作是在事件發(fā)生時的"喚醒"過程中完成的。在以上所示的鼠標驅(qū)動中，鼠標中斷將調(diào)用mousedev_event()函數(shù)，該函數(shù)的最后就會使用wake_up_interruptible()喚醒等待鼠標事件的所有進程。wake_up_interruptible()將最終調(diào)用try_to_wake_up()函數(shù)：
| /* 節(jié)選自[kernel/sched.c] */ static inline int try_to_wake_up(struct task_struct * p, int synchronous) {unsigned long flags;int success = 0;spin_lock_irqsave(&runqueue_lock, flags);p->state = TASK_RUNNING;if (task_on_runqueue(p))goto out;add_to_runqueue(p); /* 添加到就緒隊列中 */if (!synchronous || !(p->cpus_allowed & (1 << smp_processor_id())))reschedule_idle(p); /* 這種情況下調(diào)用wake_up()，synchronous總為0，此時，*//* 如果本CPU不適合運行該進程，則需要調(diào)用reschedule_idle()尋找合適的CPU */success = 1;out:spin_unlock_irqrestore(&runqueue_lock, flags);return success; } |
?
這時啟動schedule()就是被動的了。
B. 被動式
在系統(tǒng)調(diào)用執(zhí)行結(jié)束后，控制由核心態(tài)返回到用戶態(tài)之前，Linux都將在ret_from_sys_call入口檢查當(dāng)前進程的need_resched值，如果該值為1，則調(diào)用schedule()：
| /* 節(jié)選自[arch/i386/kernel/entry.S] */ENTRY(ret_from_sys_call)clicmpl $0,need_resched(%ebx) #ebx中存放著current指針jne reschedule……reschedule:call SYMBOL_NAME(schedule) jmp ret_from_sys_call #反復(fù)查詢need_resched |
?
因此，只需要設(shè)置當(dāng)前進程（current）的need_resched，就有機會啟動調(diào)度器。通常有如下幾種場合會設(shè)置need_resched：
- update_process_times()，由時鐘中斷觸發(fā)，負責(zé)管理除0號進程（idle進程）以外的其他各個進程的時間片消耗。如果當(dāng)前進程（SCHED_FIFO實時進程除外）的時間片用完了（counter==0），則設(shè)置need_resched為1；（注意：此時并不計算或重置counter值，這個工作在所有進程的時間片都耗完以后在schedule()中進行）
- reschedule_idle()，此函數(shù)的功能在"調(diào)度器工作流程"一節(jié)中已經(jīng)詳細描述了，不過，最經(jīng)常的調(diào)用者是在某一事件等待隊列上休眠的進程的喚醒過程--wake_up_process()及其他一系列wake_up函數(shù)（見上"主動式調(diào)度"）；
- sched_setscheduler()、sched_yield()系統(tǒng)調(diào)用，以及系統(tǒng)初始化（rest_init()中）、創(chuàng)建新進程（do_fork()中）等從語義上就希望啟動調(diào)度器工作的場合。
由于啟動schedule()的時機實際上由當(dāng)前進程決定，因此設(shè)置了need_resched并不意味著就能及時調(diào)度，這也是"Linux內(nèi)核不可搶占"的原因（詳見下"Linux 2.4調(diào)度系統(tǒng)的一些問題"之"內(nèi)核不可搶占"）。
回頁首
六． 其他核心應(yīng)用的調(diào)度相關(guān)部分
系統(tǒng)中很多技術(shù)都和調(diào)度器相關(guān)，這里僅就其中幾個稍作展開，并且不涉及該技術(shù)的細節(jié)，僅就其中與調(diào)度器相關(guān)的部分進行討論，假定讀者對于該技術(shù)有初步的了解。
1. IDLE進程
系統(tǒng)最初的引導(dǎo)進程（init_task）在引導(dǎo)結(jié)束后即成為cpu 0上的idle進程。在每個cpu上都有一個idle進程，正如上文所言，這些進程登記在init_tasks[]數(shù)組中，并可用idle_task()宏訪問（見上"相關(guān)數(shù)據(jù)結(jié)構(gòu)"）。idle進程不進入就緒隊列，系統(tǒng)穩(wěn)定后，僅當(dāng)就緒隊列為空的時候idle進程才會被調(diào)度到。
init_task的task_struct是靜態(tài)配置的，定義在[include/linux/sched.h]中的INIT_TASK()宏中，其中與調(diào)度相關(guān)的幾個屬性分別是：
- state：TASK_RUNNING；
- counter：10*HZ/100；i386上大約100ms
- nice：0；缺省的優(yōu)先級
- policy：SCHED_OTHER；非實時進程
- cpus_runnable：-1；全1，未在任何cpu上運行
- cpus_allowed：-1；全1，可在任何cpu上運行
在smp_init()中（實際上是在[arch/i386/kernel/smpboot.c]中的smp_boot_cpus()中），init_task的processor屬性被設(shè)為0，對應(yīng)的schedule_data也設(shè)置好相應(yīng)的值。在創(chuàng)建了一個核心線程用于執(zhí)行init()函數(shù)之后（[/init/main.c]rest_init()），init_task設(shè)置自己的need_resched等于1，然后調(diào)用cpu_idle()進入IDLE循環(huán)。
在cpu_idle()中，init_task的nice值被設(shè)為20（最低優(yōu)先級），counter為-100（無意義的足夠小），然后cpu_idle()進入無限循環(huán)：
| /* 節(jié)選自[arch/i386/kernel/processs.c] cpu_idle() */ while (1) {void (*idle)(void) = pm_idle;if (!idle)idle = default_idle;while (!current->need_resched)idle();schedule();check_pgt_cache(); } |
?
初始化過程中第一次執(zhí)行cpu_idle()，因need_resched為1，所以直接啟動schedule()進行第一次調(diào)度。如上文所述，schedule()會清掉need_resched位，因此，之后本循環(huán)都將執(zhí)行idle()函數(shù)，直至need_resched再被設(shè)置為非0（比如在reschedule_idle()中，見上"調(diào)度器工作時機"）。
idle()函數(shù)有三種實現(xiàn)可能：
- default_idle()，執(zhí)行hlt指令；
- poll_idle()，如果核心參數(shù)上定義了"idle=poll"，則pm_idle會指向poll_idle()，它將need_resched設(shè)置為特殊的-1，然后反復(fù)循環(huán)直到need_resched不等于-1。因為poll_idle()采用更高效的指令，所以運行效率比default_idle()要高；
- 電源管理相關(guān)的idle過程，例如APM和ACPI模塊中定義的idle過程。
因為僅當(dāng)就緒隊列為空的時候才會調(diào)度到idle進程，所以，只有在系統(tǒng)完全空閑時才會執(zhí)行check_pgt_cache()操作，清理頁表緩存。
2. 進程創(chuàng)建
系統(tǒng)中除了init_task是手工創(chuàng)建的以外，其他進程，包括其他CPU上的idle進程都是通過do_fork()創(chuàng)建的，所不同的是，創(chuàng)建idle進程時使用了CLONE_PID標志位。
在do_fork()中，新進程的屬性設(shè)置為：
- state：TASK_UNINTERRUPTIBLE
- pid：如果設(shè)置了CLONE_PID則與父進程相同（僅可能為0），否則為下一個合理的pid
- cpus_runnable：全1；未在任何cpu上運行
- processor：與父進程的processor相同；子進程在哪里創(chuàng)建就優(yōu)先在哪里運行
- counter：父進程counter值加1的一半；同時父進程自己的counter也減半，保證進程不能通過多次fork來偷取更多的運行時間（同樣，在子進程結(jié)束運行時，它的剩余時間片也將歸還給父進程，以免父進程因創(chuàng)建子進程而遭受時間片的損失）
- 其他值與父進程相同
子進程通過SET_LINKS()鏈入進程列表，然后調(diào)用wake_up_process()喚醒（見上"調(diào)度器工作時機"）。
3. smp系統(tǒng)初始化
init_task在完成關(guān)鍵數(shù)據(jù)結(jié)構(gòu)初始化之后，在進行硬件的初始化之前，會調(diào)用smp_init()對SMP系統(tǒng)進行初始化。smp_init()調(diào)用smp_boot_cpus()，smp_boot_cpus()對每一個CPU都調(diào)用一次do_boot_cpu()，完成SMP其他CPU的初始化工作。
| /* 節(jié)選自[arch/i386/kernel/smpboot.c] do_boot_cpu() */if (fork_by_hand() < 0) /* do_fork(CLONE_VM|CLONE_PID)創(chuàng)建一個新進程，與init_task一樣具有0號pid */panic("failed fork for CPU %d", cpu);idle = init_task.prev_task; /*在進程列表中，新進程總是位于init_task的左鏈prev上 */if (!idle)panic("No idle process for CPU %d", cpu);idle->processor = cpu;idle->cpus_runnable = 1 << cpu; /* 在指定CPU上運行 */map_cpu_to_boot_apicid(cpu, apicid);idle->thread.eip = (unsigned long) start_secondary; /* 被調(diào)度到后的啟動地址 */del_from_runqueue(idle); /* idle進程不通過就緒隊列調(diào)度 */unhash_process(idle);init_tasks[cpu] = idle; /* 所有idle進程都可通過init_tasks[]數(shù)組訪問 */ |
?
該進程被調(diào)度到時即執(zhí)行start_secondary()，最終將調(diào)用cpu_idle()，成為IDLE進程。
回頁首
七． Linux 2.4調(diào)度系統(tǒng)的一些問題
1. 進程時間片
2.4內(nèi)核中進程缺省時間片是根據(jù)以下公式計算的：
| /* 節(jié)選自[kernel/sched.c] */ #if HZ < 200 #define TICK_SCALE(x) ((x) >> 2) #elif HZ < 400 #define TICK_SCALE(x) ((x) >> 1) #elif HZ < 800 #define TICK_SCALE(x) (x) #elif HZ < 1600 #define TICK_SCALE(x) ((x) << 1) #else #define TICK_SCALE(x) ((x) << 2) #endif #define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1) …… schedule() { …… p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice); …… } |
?
如上所述，時鐘中斷將不斷對當(dāng)前運行的非IDLE進程進行時間片剩余值減1的操作，直至所有就緒隊列中的counter都減為0了，就在schedule()中對每個進程（包括休眠進程）利用上述公式執(zhí)行時間片的更新。其中在[include/asm-i386/param.h]中定義了HZ為100，而counter通常初值為0，nice缺省為0（nice在-20到19之間選擇），所以，i386下counter的缺省值為6，也就是大約60ms（時鐘中斷大約每10ms一次）。
同時，對于休眠的進程而言，其參與計算的counter非0，因此實際上它的counter是在累加，構(gòu)成一個等比數(shù)列COUNTER=COUNTER/2+k，1<k<=11，其最大值趨近于2*k，也就是說，2.4系統(tǒng)中進程的時間片不會超過230ms。
因為就緒進程選取算法中counter的值占很大比重（見"就緒進程選擇算法"），因此，這種對于休眠進程時間片疊加的做法體現(xiàn)了Linux傾向于優(yōu)先執(zhí)行休眠次數(shù)比較多，也就是IO密集（IO-bound）的進程。
Linux設(shè)計者最初是希望因此而提高交互式進程的響應(yīng)速度，從而方便終端用戶，但IO密集的進程并不一定就是交互式進程，例如數(shù)據(jù)庫操作需要頻繁地讀寫磁盤，從而經(jīng)常處于休眠狀態(tài)，動態(tài)優(yōu)先級通常較高，但這種應(yīng)用并不需要用戶交互，所以它反而影響了真正的交互動作的響應(yīng)。
時間片的長度對系統(tǒng)性能影響也很大。如果太短，進程切換就會過于頻繁，開銷很大；如果太長，系統(tǒng)響應(yīng)就會太慢，Linux的策略是在系統(tǒng)響應(yīng)不至于太慢的前提下讓時間片盡可能地長。
2. 內(nèi)核不可搶占
從上面的分析我們可以看到，schedule()是進行進程切換的唯一入口，而它的運行時機很特殊。一旦控制進入核心態(tài)，就沒有任何辦法可以打斷它，除非自己放棄cpu。一個最典型的例子就是核心線程中如果出現(xiàn)死循環(huán)（只要循環(huán)中不調(diào)用schedule()），系統(tǒng)就會失去響應(yīng)，此時各種中斷（包括時鐘中斷）仍然在響應(yīng)，但卻不會發(fā)生調(diào)度，其他進程（包括核心進程）都沒有機會運行。
下面給出的是中斷返回的代碼：
| /* 節(jié)選自[arch/i386/entry.S] */ ENTRY(ret_from_intr)GET_CURRENT(%ebx) #將current指針存到ebx寄存器中備用 ret_from_exception:movl EFLAGS(%esp),%eax #取EFLAGS中的VM_MASK位判斷是否處于VM86模式movb CS(%esp),%al #取CS低兩位判斷是否處于用戶態(tài)testl $(VM_MASK | 3),%eax jne ret_from_sys_call #如果處于VM86模式或者處于用戶態(tài)，就從ret_from_sys_call入口返回， #否則直接返回jmp restore_all |
?
這是此時唯一可能調(diào)用schedule()的地方（通過ret_from_sys_call，見"調(diào)度器工作時機"），但普通的核心線程不屬于任何一種要求的狀態(tài)，它能響應(yīng)中斷，但不能導(dǎo)致調(diào)度。
這個特點的表現(xiàn)之一就是，高優(yōu)先級的進程無法打斷正在核內(nèi)執(zhí)行系統(tǒng)調(diào)用（或者中斷服務(wù)）的低優(yōu)先級進程，這對于實時系統(tǒng)來說是致命的，但卻簡化了核心代碼。內(nèi)核中很多地方都利用了這一特點，能夠不做過多保護地訪問共享數(shù)據(jù)，而不用擔(dān)心其他進程的打擾。
3. 實時性能
Linux 2.4通過就緒進程選擇算法的設(shè)計區(qū)分實時進程和非實時進程，只要有實時進程可運行，非實時進程就不會獲得運行機會。Linux又將實時進程分為SCHED_RR和SCHED_FIFO兩類。SCHED_RR時間片結(jié)束后會發(fā)生調(diào)度，并將自己置于就緒隊列的末尾，從而給其他rt_priority相同（或更高）的實時進程運行機會（見"調(diào)度器工作流程"），而SCHED_FIFO不會因時間片結(jié)束而放棄CPU（見"調(diào)度器工作時機"），或者出現(xiàn)更高優(yōu)先級的實時進程，或者主動放棄CPU，否則SCHED_FIFO將運行到進程結(jié)束。
盡管Linux 2.4中區(qū)分了實時進程和非實時進程的調(diào)度優(yōu)先權(quán)，但也僅此而已。不支持核心搶占運行的操作系統(tǒng)很難實現(xiàn)真正的實時性，因為實時任務(wù)的響應(yīng)時間無法預(yù)測。有兩種辦法使系統(tǒng)的實時性更好，一種是采用設(shè)置類似搶占調(diào)度點的做法，一種就是使內(nèi)核真正具備可搶占性。
即使是內(nèi)核可搶占的系統(tǒng)，也并不一定滿足實時性要求，它僅僅解決了CPU資源的訪問優(yōu)先權(quán)問題，其他資源也同樣需要"被搶占"，例如實時進程應(yīng)該能夠從握有某個共享資源的普通進程手中奪得它所需要的資源，它使用完后再還給普通進程。但實際上，很多系統(tǒng)都無法做到這一點，Linux的調(diào)度器更是不具備這種能力。
4. 多處理機系統(tǒng)中的局限性
Linux的調(diào)度器原本是針對單處理機系統(tǒng)設(shè)計的，在內(nèi)核發(fā)展過程中，不斷通過補丁來提高多處理機系統(tǒng)（主要是SMP系統(tǒng)）的執(zhí)行效率。這種開發(fā)方式一直持續(xù)到2.4版本，因此在2.4內(nèi)核中，SMP應(yīng)用仍然有很多無法突破的障礙，例如全局共享的就緒隊列。很多研究團體都在針對Linux調(diào)度器的多處理機擴展性作研究，參考文獻中列舉了其中兩個[5][6]，但最權(quán)威的改進還是在2.6內(nèi)核中。
對于超線程CPU，Linux調(diào)度器的支持有限，它可以區(qū)分同一物理CPU上的兩個邏輯CPU，在兩個邏輯CPU都空閑的時候，調(diào)度器可以優(yōu)先考慮將進程調(diào)度到其中一個邏輯CPU上運行（見"調(diào)度器工作流程"）。從原理上說，超線程CPU是存在兩個（或多個）執(zhí)行現(xiàn)場的單CPU，只有兩個使用CPU不同部件（比如定點部件和浮點部件）的線程在其上運行的時候才有正的加速，否則，由于執(zhí)行部件沖突以及Cache miss，使用超線程技術(shù)甚至?xí)硪欢ǔ潭壬系男阅軗p失。Linux 2.4的調(diào)度器并不能區(qū)分哪些進程是"類似"的，哪些進程會使用不同的執(zhí)行部件，因此，實際上無法恰當(dāng)使用超線程CPU。 對于其他更復(fù)雜的多處理機系統(tǒng)，例如目前高端系統(tǒng)中占統(tǒng)治地位的NUMA結(jié)構(gòu)機器，Linux在調(diào)度器上基本未作考慮。例如進程（線程）總優(yōu)先在創(chuàng)建它的CPU上運行（見"其他核心應(yīng)用的調(diào)度相關(guān)部分"之"進程創(chuàng)建"），并傾向于保持在該CPU上（見"就緒進程選擇算法"），整個CPU選擇過程沒有做任何局部性優(yōu)化。
回頁首
八． 后記
調(diào)度系統(tǒng)的表現(xiàn)關(guān)系到整個系統(tǒng)的性能，Linux的應(yīng)用目前主要集中在低端服務(wù)器系統(tǒng)和桌面系統(tǒng)，將來很可能向高端服務(wù)器市場和嵌入式系統(tǒng)發(fā)展，這就要求調(diào)度系統(tǒng)有大的改動。在新的Linux內(nèi)核2.6版本中，調(diào)度器的改動是最引人注目的，它一方面提供了核心可搶占的支持，另一方面又對多處理機系統(tǒng)上的表現(xiàn)進行了優(yōu)化。在熟悉了2.4的調(diào)度系統(tǒng)之后，我們將分析2.6中調(diào)度器的表現(xiàn)。
?
參考資料
[1][Linus Torvalds，2003]?
Linux內(nèi)核源碼v2.4.21
[2][Daniel P. Bovet, Marco Cesati，2002]?
Understanding the Linux Kernel, 2nd Edition，O'Reilly
[3][Moshe Bar，2000]?
Kernel Korner: The Linux Scheduler，Linux Journal
[4][Paul Bemowsky，2003]?
Hyper-Threading Linux，Linux World
[5][Mike Kravetz，2001]?
Enhancing Linux Scheduler Scalability，IBM Linux Tech. Center
[6][Chris King, Scott Lathrop, Steve Molloy, Paul Moore，2001]?
ELSC : Scalable Linux Scheduling on a Symmetric Multi-Processor Machine，University of Michigan
轉(zhuǎn)載于:https://www.cnblogs.com/davidwang456/p/3592502.html
總結(jié)
以上是生活随笔為你收集整理的Linux 2.4调度系统分析--转的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于Linux的集群系统（八）--转
- 下一篇： 对request.getSession(