Linux是一套使用和自由傳播的類(lèi)Unix操作系統(tǒng)，是一個(gè)基于POSIX和UNIX的多用戶、多任務(wù)、支持多線程和多CPU的操作系統(tǒng)。它能運(yùn)行主要的UNIX工具軟件、應(yīng)用程序和網(wǎng)絡(luò)協(xié)議。
　　1.前言
　　處理機(jī)(CPU)是整個(gè)計(jì)算機(jī)系統(tǒng)的資源，在多進(jìn)程的操作系統(tǒng)中，進(jìn)程數(shù)往往多于處理機(jī)數(shù)，這將導(dǎo)致各進(jìn)程互相爭(zhēng)奪處理機(jī)。進(jìn)程調(diào)度對(duì)系統(tǒng)功能的實(shí)現(xiàn) 及各方面的性能都有著決定性的影響，其實(shí)質(zhì)就是把處理機(jī)公平、合理、高效地分配給各個(gè)進(jìn)程。調(diào)度是實(shí)現(xiàn)多任務(wù)并發(fā)執(zhí)行的必要手段，不同的操作系統(tǒng)有著不同 的調(diào)度目標(biāo)。在傳統(tǒng)的Unix類(lèi)分時(shí)系統(tǒng)中，保證多個(gè)進(jìn)程公平地使用系統(tǒng)資源，提供較好的響應(yīng)時(shí)間是調(diào)度的主要目標(biāo);而在強(qiáng)實(shí)時(shí)操作系統(tǒng)中，總是優(yōu)先級(jí)高 的任務(wù)優(yōu)先獲得處理機(jī)的使用權(quán)。

　　Linux具有內(nèi)核穩(wěn)定、功能強(qiáng)大、可裁減、低成本等特點(diǎn)，非常適合嵌入式應(yīng)用。但是Linux內(nèi)核本身并不具備 強(qiáng)實(shí)時(shí)特性，且內(nèi)核體積較大，因此，想要把Linux用于嵌入式系統(tǒng)，必須對(duì)Linux進(jìn)行實(shí)時(shí)化、嵌入式化。Linux結(jié)合實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程(普通 進(jìn)程)自身的特點(diǎn)，綜合了上述幾種調(diào)度策略，實(shí)現(xiàn)了高效、靈活的進(jìn)程調(diào)度。
　　2.Linux進(jìn)程調(diào)度分析
　　2.1　Linux進(jìn)程狀態(tài)的描述
　　Linux將進(jìn)程狀態(tài)描述為如下五種：
　　TASK_RUNNING：可運(yùn)行狀態(tài)。處于該狀態(tài)的進(jìn)程可以被調(diào)度執(zhí)行而成為當(dāng)前進(jìn)程。
　　TASK_INTERRUPTIBLE：可中斷的睡眠狀態(tài)。處于該狀態(tài)的進(jìn)程在所需資源有效時(shí)被喚醒，也可以通過(guò)信號(hào)或定時(shí)中斷喚醒。
　　TASK_UNINTERRUPTIBLE：不可中斷的睡眠狀態(tài)。處于該狀態(tài)的進(jìn)程僅當(dāng)所需資源有效時(shí)被喚醒。
　　TASK_ZOMBIE：僵尸狀態(tài)。表示進(jìn)程結(jié)束且已釋放資源，但其task_STruct仍未釋放。
　　TASK_STOPPED：暫停狀態(tài)。處于該狀態(tài)的進(jìn)程通過(guò)其他進(jìn)程的信號(hào)才能被喚醒。
　　2.2　調(diào)度方式
　　Linux中的每個(gè)進(jìn)程都分配有一個(gè)相對(duì)獨(dú)立的虛擬地址空間。該虛存空間分為兩部分：用戶空間包含了進(jìn)程本身的代碼和數(shù)據(jù);內(nèi)核空間包含了操作系統(tǒng)的代碼和數(shù)據(jù)。
　　Linux采用“有條件的可剝奪”調(diào)度方式。對(duì)于普通進(jìn)程，當(dāng)其時(shí)間片結(jié)束時(shí)，調(diào)度程序挑選出下一個(gè)處于TASK_RUNNING狀態(tài)的進(jìn)程作為當(dāng)前進(jìn)程 (自愿調(diào)度)。對(duì)于實(shí)時(shí)進(jìn)程，若其優(yōu)先級(jí)足夠高，則會(huì)從當(dāng)前的運(yùn)行進(jìn)程中搶占CPU成為新的當(dāng)前進(jìn)程(強(qiáng)制調(diào)度)。發(fā)生強(qiáng)制調(diào)度時(shí)，若進(jìn)程在用戶空間中運(yùn) 行，就會(huì)直接被剝奪CPU;若進(jìn)程在內(nèi)核空間中運(yùn)行，即使迫切需要其放棄CPU，也仍要等到從它系統(tǒng)空間返回的前夕才被剝奪CPU。
　　3.調(diào)度策略
　　3.1　三種調(diào)度策略
　　(1)SCHED_OTHER。SCHED_OTHER是面向普通進(jìn)程的時(shí)間片輪轉(zhuǎn)策略。采用該策略時(shí)，系統(tǒng)為處于TASK_RUNNING狀態(tài)的每個(gè)進(jìn)程分配一個(gè)時(shí)間片。當(dāng)時(shí)間片用完時(shí)，進(jìn)程調(diào)度程序再選擇下一個(gè)優(yōu)先級(jí)相對(duì)較高的進(jìn)程，并授予CPU使用權(quán)。
　　(2)SCHED_FIFO。SCHED_FIFO策略適用于對(duì)響應(yīng)時(shí)間要求比較高，運(yùn)行所需時(shí)間比較短的實(shí)時(shí)進(jìn)程。采用該策略時(shí)，各實(shí)時(shí)進(jìn)程按其進(jìn)入可 運(yùn)行隊(duì)列的順序依次獲得CPU。除了因等待某個(gè)事件主動(dòng)放棄CPU，或者出現(xiàn)優(yōu)先級(jí)更高的進(jìn)程而剝奪其CPU之外，該進(jìn)程將一直占用CPU運(yùn)行。
　　(3)SCHED_RR。SCHED_RR策略適用于對(duì)響應(yīng)時(shí)間要求比較高，運(yùn)行所需時(shí)間比較長(zhǎng)的實(shí)時(shí)進(jìn)程。采用該策略時(shí)，各實(shí)時(shí)進(jìn)程按時(shí)間片輪流使用CPU。當(dāng)一個(gè)運(yùn)行進(jìn)程的時(shí)間片用完后，進(jìn)程調(diào)度程序停止其運(yùn)行并將其置于可運(yùn)行隊(duì)列的末尾。
　　3.2 進(jìn)程調(diào)度依據(jù)
　　Linux只有一個(gè)可運(yùn)行隊(duì)列，處于TASK_RUNNING狀態(tài)的實(shí)時(shí)進(jìn)程和普通進(jìn)程都加入到這個(gè)可運(yùn)行隊(duì)列中。Linux的進(jìn)程調(diào)度采用了動(dòng)態(tài)優(yōu)先級(jí) 和權(quán)值調(diào)控的方法，既可實(shí)現(xiàn)上述三種調(diào)度策略，又能保證實(shí)時(shí)進(jìn)程總是比普通進(jìn)程優(yōu)先使用CPU。描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)task_struct中用以下幾個(gè)數(shù) 據(jù)作為調(diào)度依據(jù)：
　　Struct task_struct {
　　……
　　volaTIle lONg need_resched; /*是否需要重新調(diào)度*/long counter; /*進(jìn)程當(dāng)前還擁有的時(shí)間片*/
　　long nice; /*普通進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)，來(lái)自UNIX系統(tǒng)*/unsigned long policy; /*進(jìn)程調(diào)度策略*/
　　unsigned long rt_priority; /*實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)*/……
　　};
　　counter的值是動(dòng)態(tài)變化的，進(jìn)程運(yùn)行時(shí)，每一個(gè)時(shí)鐘滴答后，其值減1。當(dāng)counter值為0時(shí)，表示該進(jìn)程時(shí)間片已用完，該進(jìn)程回到可運(yùn)行隊(duì)列中，等待再次調(diào)度。
　　為保證實(shí)時(shí)進(jìn)程優(yōu)于普通進(jìn)程，Linux采取加權(quán)處理法。在進(jìn)程調(diào)度過(guò)程中，每次選取下一個(gè)運(yùn)行進(jìn)程時(shí)，調(diào)度程序首先給可運(yùn)行隊(duì)列中的每個(gè)進(jìn)程賦予一個(gè)權(quán) 值weight。普通進(jìn)程的權(quán)值就是其counter和優(yōu)先級(jí)nice的綜合，而實(shí)時(shí)進(jìn)程的權(quán)值是它的rt_priority的值加1000，確保實(shí)時(shí)進(jìn) 程的權(quán)值總能大于普通進(jìn)程。調(diào)度程序檢查可運(yùn)行隊(duì)列中所有進(jìn)程的權(quán)值，選取權(quán)值者作為下一個(gè)運(yùn)行進(jìn)程，保證了實(shí)時(shí) 進(jìn)程優(yōu)先于普通進(jìn)程獲得CPU。 Linux使用內(nèi)核函數(shù)goodness()對(duì)進(jìn)程進(jìn)行加權(quán)處理：
　　StaTIc inline goodness (struct task_struct * pint this_cpu， struct mm_struct *this_mm){
　　Int weight;
　　Weight=-1;
　　/*判斷如果任務(wù)的調(diào)度策略被置為SCHED_YIELD的話，則置權(quán)值為-1，返回。系統(tǒng)調(diào)用SCHED_YIELD表示為“禮讓”進(jìn)程，其權(quán)值為*/If (p-》policy & SCHED_YIELD)
　　goto out;
　　/*先對(duì)普通進(jìn)程進(jìn)行處理(由于多數(shù)是普通進(jìn)程，這樣做有利于提高系統(tǒng)效率)*/If (p-》policy==SCHED_OTHER){
　　weight=p-》counter; /*返回權(quán)值為進(jìn)程的counter值*//*如果當(dāng)前進(jìn)程的counter為0，則表示當(dāng)前進(jìn)程的時(shí)間片已用完，直接返回*/If (! weight)
　　Goto out;
　　#Ifdef CONFIG_SMP
　　If (p-》processor==this_cpu)
　　Weight+=PROC_CHANGE_PENALTY;
　　#Endif
　　/*對(duì)進(jìn)程權(quán)值進(jìn)行微調(diào)，如果進(jìn)程的內(nèi)存空間使用當(dāng)前正在運(yùn)行的進(jìn)程的內(nèi)存空間，則權(quán)值額外加1*/If (p-》mm==this_mm||! p-》mm)
　　Weight+=1;
　　/*將權(quán)值加上20與進(jìn)程優(yōu)先級(jí)nice的差。普通進(jìn)程的權(quán)值主要由counter值和nice值組成*/Weight+=20-p-》nice;
　　Goto out;
　　}
　　/*對(duì)實(shí)時(shí)進(jìn)程進(jìn)行處理，返回權(quán)值為rt_priority+1000，確保優(yōu)先級(jí)高于普通進(jìn)程*/Weight=1000+p-》rt_priority;
　　Out：
　　return weight;
　　}
　　從goodness()函數(shù)可以看出，對(duì)于普通進(jìn)程，其權(quán)值主要取決于剩余的時(shí)間配額和nice兩個(gè)因素。nice的規(guī)定取值范圍為19～-20，只有特 權(quán)用戶才能把nice值設(shè)為負(fù)數(shù)，而表達(dá)式(20-p-》nice)掉轉(zhuǎn)方向成為1～40。所以，綜合的權(quán)值在時(shí)間片尚未用完時(shí)基本上是兩者之和。 如果是內(nèi)核進(jìn)程，或者其用戶空間與當(dāng)前進(jìn)程相同，則權(quán)值將額外加1作為獎(jiǎng)勵(lì)。對(duì)于實(shí)時(shí)進(jìn)程，其權(quán)值為1000+p-》rt_priority，當(dāng) p-》counter達(dá)到0時(shí)該進(jìn)程將移到隊(duì)列的尾部，但其優(yōu)先級(jí)仍不少于1000?？梢?jiàn)當(dāng)有實(shí)時(shí)進(jìn)程就緒時(shí)，普通進(jìn)程是沒(méi)機(jī)會(huì)運(yùn)行的。
　　由此可以看出，通過(guò)goodness()函數(shù)，Linux從優(yōu)先考慮實(shí)時(shí)進(jìn)程出發(fā)，實(shí)現(xiàn)了多種調(diào)度策略的統(tǒng)一處理，其設(shè)計(jì)思想可謂非常巧妙。
　　3.3 進(jìn)程調(diào)度
　　Linux的進(jìn)程調(diào)度由調(diào)度程序schedule()完成，通過(guò)對(duì)schedule()的分析能更好理解調(diào)度的過(guò)程。schedule()首先判斷當(dāng)前運(yùn)行進(jìn)程是否具有SCHED_RR 標(biāo)志，本文取一部分加以分析：
　　if (prev-》policy==SCHED_RR) /*如果是輪轉(zhuǎn)調(diào)度，先作goto特殊處理*/Goto move_rr_last;
　　……
　　Move_rr_last：
　　If (! prev-》counter){ /*如果counter減至0*/Prev-》counter=NICE_TO_TICKS (prev-》nice);Move_last_runqueue (prev);
　　}
　　Goto move_rr_back;
　　prev-》counter代表當(dāng)前進(jìn)程的運(yùn)行時(shí)間配額，其值逐漸減小。一旦減至0，就要從可執(zhí)行隊(duì)列runqueue中當(dāng)前的位置移到末尾，宏操 作NICE_TO_TICKS根據(jù)系統(tǒng)時(shí)鐘的將進(jìn)程的優(yōu)先級(jí)別換算成可以運(yùn)行的時(shí)間配額，即恢復(fù)其初始的時(shí)間配額。把該進(jìn)程移到末尾意味著：如果沒(méi)有 權(quán)值更高的進(jìn)程，但是有一個(gè)權(quán)值與這相同的進(jìn)程存在，那么，那個(gè)權(quán)值相同而排列在前的進(jìn)程就會(huì)被選中，從而顧全了大局。
　　接下來(lái)調(diào)度函數(shù)查詢當(dāng)前運(yùn)行進(jìn)程的狀態(tài)是否改變：
　　Move_rr_back：
　　switch(prev-》state){ /*查看進(jìn)程當(dāng)前的狀態(tài)*/Case TASK_INTERRUPTIBLE：
　　if (signal pending(prev)){ /*判斷運(yùn)行期間是否收到信號(hào)*/Prev-》state=TASK_RUNNING;
　　Break;
　　}
　　default： /*當(dāng)前運(yùn)行進(jìn)程處于非TASK_RUNNING狀態(tài)*/Del_from_runqueue (prev);
　　Case TASK_RUNNING：
　　}
　　Prev-》need_resched=0;
　　容易理解：如果發(fā)現(xiàn)進(jìn)程處于TASK_INTERRUPTIBLE狀態(tài)且有信號(hào)等待處理，則內(nèi)核將其狀態(tài)設(shè)為T(mén)ASK_RUNNING，讓其處理完信號(hào)， 接下來(lái)仍有機(jī)會(huì)獲得CPU;如果沒(méi)有信號(hào)等待，則將其從可運(yùn)行隊(duì)列中撤下來(lái);如果處于TASK_RUNNING狀態(tài)，則繼續(xù)進(jìn)行。然后，將 prev-》need_resched的值恢復(fù)成0，因?yàn)樗璧恼{(diào)度已經(jīng)在運(yùn)行。
　　Repeat schedule ()：
　　next=idle_task(this_cpu); /*next指向候選進(jìn)程*/c=-1000; 　/*進(jìn)程的綜合權(quán)值，初始時(shí)是0號(hào)進(jìn)程，-1000是可能的值*/If (prev-》state==TASK_RUNNING)
　　Goto still_running;
　　Still_running_back：
　　List_for_each (tmp， &runqueue_head){
　　P=list_entry (tmp， struct task_struct， run_list);if (can_schedule(p，this_cpu)){ /*計(jì)算p指向的進(jìn)程的權(quán)值*/Int weight=goodness (p， this_cpu， prev-》active_mm);if (weight》c) /*比較權(quán)值大小*/
　　C=weight， next=p;
　　}
　　}
　　調(diào)度之前，將待調(diào)度的進(jìn)程默認(rèn)為0號(hào)進(jìn)程，權(quán)值置為-1000。0號(hào)進(jìn)程比較特別，既不會(huì)睡眠，又不能被殺死。接下來(lái)內(nèi)核遍歷可執(zhí)行隊(duì)列run queue中的每個(gè)進(jìn)程，為每個(gè)進(jìn)程通過(guò)goodness()函數(shù)計(jì)算出它當(dāng)前所具有的權(quán)值，然后與當(dāng)前的值c相比。如果兩個(gè)進(jìn)程具有相同權(quán)值的話， 那么排在前面的進(jìn)程勝出。
　　Still_running：
　　C=goodness (prev， this_cpu， prev-》active_mm);Next=prev;
　　Goto still_running_back;
　　上面的代碼告訴我們，如果當(dāng)前進(jìn)程想要繼續(xù)運(yùn)行，那么在挑選進(jìn)程時(shí)以當(dāng)前進(jìn)程此刻的權(quán)值開(kāi)始。這意味著，相對(duì)于權(quán)值相同的其他進(jìn)程來(lái)說(shuō)，當(dāng)前進(jìn)程優(yōu)先。
　　若發(fā)現(xiàn)當(dāng)前已選進(jìn)程的權(quán)值為0，則需要重新計(jì)算各個(gè)進(jìn)程的時(shí)間配額，schedule()將轉(zhuǎn)入recalculate部分。限于篇幅，在此不再展開(kāi)。
　　4.結(jié)束語(yǔ)
　　以上結(jié)合代碼簡(jiǎn)要介紹了Linux中進(jìn)程調(diào)度的基本思想、依據(jù)和策略，容易發(fā)現(xiàn)Linux高效率和較強(qiáng)支持并發(fā)進(jìn)程等特點(diǎn)。近年來(lái)，嵌入式Linux的研 究正在成為一個(gè)熱點(diǎn)，理解Linux進(jìn)程調(diào)度的原理，并在此基礎(chǔ)上改進(jìn)調(diào)度算法可能存在的缺陷，可以進(jìn)一步增強(qiáng)其對(duì)實(shí)時(shí)性的支持，使之進(jìn)一步適應(yīng)在嵌入式 系統(tǒng)領(lǐng)域內(nèi)的應(yīng)用。