嵌入式Linux系統(tǒng)實時進(jìn)程調(diào)度算法改進(jìn)

1  嵌入式Linux系統(tǒng)分析
1.1  嵌入式系統(tǒng)
    嵌入式系統(tǒng)（Embedded Systems）是以應(yīng)用為中心，以計算機(jī)技術(shù)為基礎(chǔ)，軟件硬件可剪裁（可編程、可重構(gòu)），適用于應(yīng)用系統(tǒng)對功能、可靠性、成本、體積、功耗有嚴(yán)格要求的專用計算機(jī)系統(tǒng)。它一般由嵌入式微處理器、外圍硬件設(shè)備、嵌入式操作系統(tǒng)以及用戶的應(yīng)用程序等四個部分組成，用于實現(xiàn)對其它設(shè)備的控制、監(jiān)視或管理等功能。其中，嵌入式處理器是嵌入式系統(tǒng)中的核心部件。
1.2　實時操作系統(tǒng)
    實時操作系統(tǒng)（RTOS，Real-Time Operation System）是指一個能夠在指定的時間范圍內(nèi)完成特定的功能或者對外部的異步時間做出響應(yīng)的操作系統(tǒng)[3]。其操作的正確性不僅依賴于邏輯判斷和邏輯設(shè)計的正確程度，而且跟這些操作進(jìn)行的時間有關(guān)。“在指定的時間范圍內(nèi)”是這個定義的核心，也就是說，實時系統(tǒng)是對響應(yīng)時間有嚴(yán)格要求的。這個定義要求了：系統(tǒng)應(yīng)該有在事先定義的時間范圍內(nèi)識別和處理離散事件的能力；系統(tǒng)能夠處理和存儲控制系統(tǒng)所需要的大量的數(shù)據(jù)。
1.3　嵌入式實時操作系統(tǒng)
    由嵌入式系統(tǒng)的概念和特點可以看出，一個嵌入式系統(tǒng)對操作系統(tǒng)的可靠性、實時性都有很高的要求。尤其在嵌入式技術(shù)廣泛應(yīng)用的工業(yè)控制、航空軍事等領(lǐng)域，對嵌入式操作系統(tǒng)的實時響應(yīng)能力提出了非常嚴(yán)格的要求，哪怕出現(xiàn)很小的時間偏差，都有可能造成無法挽回的損失。這便是為何絕大多數(shù)嵌入式操作系統(tǒng)都采用實時操作系統(tǒng)的主要原因。實時操作系統(tǒng)應(yīng)用到嵌入式領(lǐng)域，便出現(xiàn)了嵌入式實時操作系統(tǒng)，它是實時操作系統(tǒng)與嵌入式系統(tǒng)相結(jié)合的產(chǎn)物，具有實時性的同時又具有嵌入式系統(tǒng)的特點。
2　實時進(jìn)程調(diào)度算法分析
2.1　Linux進(jìn)程調(diào)度相關(guān)概念
    進(jìn)程調(diào)度分成兩個部分，一個是調(diào)度的時機(jī)，即什么時候調(diào)度；一個是調(diào)度的算法，即如何調(diào)度和調(diào)度哪個進(jìn)程。
    Linux進(jìn)程調(diào)度時機(jī)[1]：
    調(diào)度時機(jī)是指在什么情況下運(yùn)行調(diào)度程序來選擇進(jìn)程運(yùn)行。在Linux系統(tǒng)中調(diào)度程序是通過函數(shù)schedule（）來實現(xiàn)的，這個函數(shù)被調(diào)用的頻率很高，由它來決定要運(yùn)行的進(jìn)程。
    Linux調(diào)度時機(jī)主要分兩種情況[2]：主動調(diào)度和被動調(diào)度。主動調(diào)度是指當(dāng)進(jìn)程狀態(tài)發(fā)生變化時直接調(diào)用schedule（）來實現(xiàn)調(diào)度。被動調(diào)度是指當(dāng)一個進(jìn)程運(yùn)行時間片到或就緒隊列中增加了一個進(jìn)程，此時系統(tǒng)并不立即進(jìn)行調(diào)度，而僅僅是將當(dāng)前進(jìn)程的調(diào)度標(biāo)志位置1，當(dāng)系統(tǒng)由核心態(tài)向用戶態(tài)轉(zhuǎn)變之前檢查當(dāng)前進(jìn)程的調(diào)度標(biāo)志是否為1，若為1，則調(diào)用schedule（）進(jìn)行調(diào)度。
2.2　進(jìn)程調(diào)度的原理
    進(jìn)程調(diào)度分成兩個部分，一個是調(diào)度的時機(jī)，即什么時候調(diào)度；一個是調(diào)度的算法，即如何調(diào)度和調(diào)度哪個進(jìn)程。
    調(diào)度程序運(yùn)行時，要在所有可運(yùn)行的進(jìn)程中選擇最值得運(yùn)行的進(jìn)程。選擇進(jìn)程的依據(jù)主要有進(jìn)程的調(diào)度策略（policy）、靜態(tài)優(yōu)先級（priority）、動態(tài)優(yōu)先級（counter）、以及實時優(yōu)先級（rt-priority）四個部分。首先，Linux從整體上區(qū)分為實時進(jìn)程和普通進(jìn)程，二者調(diào)度算法不同，實時進(jìn)程優(yōu)先于普通進(jìn)程運(yùn)行。進(jìn)程依照優(yōu)先級的高低被依次調(diào)用，實時優(yōu)先級級別最高[3]。
2.3　實時調(diào)度算法及缺陷
    目前，實時調(diào)度算法主要可以分為三大類：時間驅(qū)動調(diào)度、優(yōu)先級驅(qū)動調(diào)度、比例共享調(diào)度。三者各有優(yōu)缺點，時間驅(qū)動調(diào)度、優(yōu)先級驅(qū)動調(diào)度側(cè)重于硬實時任務(wù)，比例共享調(diào)度更為適合于軟實時任務(wù)，在網(wǎng)絡(luò)系統(tǒng)中應(yīng)用較多。比例共享調(diào)度基本思想就是按照一定的權(quán)重比例對一組需要調(diào)度的任務(wù)進(jìn)行調(diào)度，讓它們的執(zhí)行時間與它們的權(quán)重成正比，是一種加權(quán)輪轉(zhuǎn)調(diào)度[4]。
    Linux進(jìn)程采用的是多級輪轉(zhuǎn)調(diào)度算法，盡管Linux通過將進(jìn)程劃分為實時進(jìn)程和普通進(jìn)程，按照優(yōu)先級進(jìn)行調(diào)度來實現(xiàn)實時的特性，但是僅能獲得秒級響應(yīng)時間，Linux雖然給實時進(jìn)程提供了較高的優(yōu)先級，但是沒有加入時間限制，在高實時響應(yīng)情況下還不能滿足要求。當(dāng)進(jìn)程進(jìn)入核心態(tài)時，其它進(jìn)程不管優(yōu)先級多高也必須等待。
3　實時調(diào)度算法的改進(jìn)
3.1　實時模型
    作為實時系統(tǒng)調(diào)度算法應(yīng)綜合考慮進(jìn)程的價值和截止兩個概念，以保證實時進(jìn)程在截止期內(nèi)盡可能多地完成，在這里提出新的調(diào)度算法，改進(jìn)Linux的實時性。
    即：進(jìn)程的優(yōu)先級數(shù)（Vi）=該進(jìn)程重要程度（Wi）+其緊迫度（pi/（d-Ti））*系數(shù)k。緊迫度的值越大，說明從時間上看這個任務(wù)越緊迫。優(yōu)化后調(diào)度算法仍以進(jìn)程的價值為基礎(chǔ)，同時也關(guān)注了完成進(jìn)程的緊迫度，對于優(yōu)先級相同的進(jìn)程，采用FIFO調(diào)度策略。進(jìn)程的價值越大說明該進(jìn)程越重要，CPU越應(yīng)完成它。
    優(yōu)化后調(diào)度算法仍以進(jìn)程的價值為基礎(chǔ)，同時也關(guān)注了完成進(jìn)程的緊迫度，對于優(yōu)先級相同的進(jìn)程，采用FIFO調(diào)度策略。進(jìn)程的價值越大說明該進(jìn)程越重要，CPU越應(yīng)完成它，可是對一些價值和它相差不多，而緊迫度要比它大得多的進(jìn)程來說，就不公平了。例如，有兩個進(jìn)程A，B同時提交，A的價值是1001，估計執(zhí)行時間是1ms，相對截止期是5ms，B的價值是1000，估計執(zhí)行時間是1ms，相對截止期是2ms，假設(shè)這里的系數(shù)因子k是10，則更應(yīng)該執(zhí)行進(jìn)程B。這是因為進(jìn)程A，B的價值相近，而B的緊迫度要比A的大一些，A的優(yōu)先級＝1001+1/5*10=1003，B的優(yōu)先級=1000+1/2*10=1005，因此選擇B先運(yùn)行，以防止B的夭折（注：Linux中實時進(jìn)程的值設(shè)為從1000到1099，非實時進(jìn)程的值設(shè)為從1到99，因此選擇系數(shù)因子k為10）優(yōu)化后的調(diào)度算法依然采用時間片輪轉(zhuǎn)策略，依照Linux分配給進(jìn)程的時間片為20次時鐘滴噠，也就是200ms =20*10ms[5]。
3.2　結(jié)構(gòu)定義
    本文給出實時進(jìn)程的結(jié)構(gòu)定義，非實時進(jìn)程依然采用原有的動態(tài)優(yōu)先級調(diào)度策略，其結(jié)構(gòu)定義略去。
    #define SCHED RR
    typedef struct TaskNode {
      int dtime； //進(jìn)程的截止期
      int T；//進(jìn)程提交時間
      int ptime；//進(jìn)程尚未完成時間，初值等于任務(wù)的執(zhí)行時間估計
      int flag； //其值為1時說明是實時進(jìn)程，為0時說明是非實時進(jìn)程
      int v；//進(jìn)程的優(yōu)先級數(shù)
      int w；//進(jìn)程的價值
        struct TaskNode *next
    }TaskNode *prior，*next；
3.3　鏈表定義
    整個調(diào)度算法可以用雙鏈表來描述，即兩級隊列，分別用兩個指針指向。最初，這兩部分的頭指針都指向“0”，表明這兩個隊列均為空。其中實時進(jìn)程的就緒等待隊列用一個循環(huán)單鏈表完成。
    開始時的一級隊列，是新到的比當(dāng)前運(yùn)行進(jìn)程優(yōu)先級低的實時進(jìn)程。如果一個進(jìn)程由于時間片到時或被更高優(yōu)先級任務(wù)搶占，根據(jù)它的優(yōu)先級將其插入到第二級隊列。
    若當(dāng)前進(jìn)程的時間片到時，CPU便選擇當(dāng)前隊列中第二個節(jié)點的進(jìn)程來判斷，如果它的緊迫度大于1的話，說明這個進(jìn)程在規(guī)定時間內(nèi)不能完成，它必定夭折，將其放入普通進(jìn)程隊列中，再選擇鏈表的第三個節(jié)點判斷，如果緊迫度小于等于1便運(yùn)行它，情況如圖１所示。

圖１　優(yōu)化后調(diào)度算法的實時進(jìn)程優(yōu)先級表

    當(dāng)一級隊列為空時，二級隊列便升成一級隊列。
    普通進(jìn)程的調(diào)度通過單鏈表來實現(xiàn)。如果新來的進(jìn)程屬于普通進(jìn)程，則根據(jù)優(yōu)先級高低插入普通隊列。只有實時隊列（一級和二級隊列）為空時，普通隊列才能被調(diào)度。
3.4　實時進(jìn)程的調(diào)度策略算法描述
    1）實時就緒隊列的初始化
      #define LEN sizeof（TaskNode）
創(chuàng)建空鏈表：
      TaskNode*creat new line()
        {
          TaskNode* head；
        head=（TaskNode））malloc（LEN）；
          head->w=-1；
            Head1=Head2=head：
            Head1->next=Head2->next=head；
            return head；
          }
    2） 實時進(jìn)程接收策略
  #define K 10
  void* pnow；
pnew指向新來的實時進(jìn)程，pnow指向當(dāng)前運(yùn)行的實時進(jìn)程。
新來的進(jìn)程是實時進(jìn)程：
  if（（*pnew）.flag ==1）
  {
當(dāng)前運(yùn)行的進(jìn)程是實時進(jìn)程：
      if （（*pnow）.flag ==1）
        {
        W =（*pnew）.v+（*pnew）.ptime）/（（*pnew）.dtime-（*pnew）.T））*K；
        if（w>（*pnow）.v+（（*pnow）.ptime/（（*pnow）.dtime-（*pnow）.T））*K））
        {
當(dāng)前運(yùn)行進(jìn)程插入二級隊列：
        move last runqueue（Head2，pnow）；
新來的進(jìn)程搶占CPU：
        pnow=pnew；
        }
        else
將新來的進(jìn)程插入到等待鏈表的一級隊列：
            move last runqueue（Head1，pnow）；
        }
        Else
當(dāng)前運(yùn)行的進(jìn)程是非實時進(jìn)程，將當(dāng)前進(jìn)程插入非實時隊列，非實時進(jìn)程的插入算法：
          move last（pnow）；
 move last略
  }
  else//新來的進(jìn)程是非實時進(jìn)程
    move last（pnew）；//將新來的非實時進(jìn)程插入非實時隊列插入算法略
    3）實時進(jìn)程插入策略
  move last runqueue（h，p）；
  TaskNode*h，*p；
  {
    TaskNode*p1，*p2，*t；
    P1=h；
    P2=pl->next；
    if （h==Head1）//插入一級隊列
    while（（*p）.w<=（*p2）.w&&pl!=Head2）//優(yōu)先級相同的進(jìn)程采用FIFO調(diào)度策略
    {
      pl=p2；
      p2=（*p2）.next；
      }
      （*p）.next=p2；
      （*p1）.next=P；
      if（P1==Head2）//該節(jié)點插入到一級隊列的末尾，則該節(jié)點便成了一級隊列的末尾
          Head2=P；
        else
        {
          While((*p).w<=(*p2).w)  //插入二級隊列
          {
            P1=p2；
            p2=（*p2）.next；
            （*p）.next=p2；
          （*p1）.next=P；
            }
        }
  }
    說明：根據(jù)傳來的h值，決定在一級隊列h的值是Headl時還是在二級隊列h的值是Head2時中查找插入的合適位置。
    當(dāng)P是新來的任務(wù)時，h的值是Head1，p被括入一級隊列。p2是p1的后繼節(jié)點。在循環(huán)體中，當(dāng)新來的進(jìn)程P高于一級隊列的進(jìn)程p2時，停止循環(huán)，將P插入到p1的后面；當(dāng)p1等于Head2時，說明一級隊列的節(jié)點的優(yōu)先級都比P節(jié)點的高，停止循環(huán)，把P插在p1的后面，則該節(jié)點便成了一級隊列的末尾。
    當(dāng)P是被搶占的任務(wù)時，h的值是Head2，p被插入二級隊列。在循環(huán)體中，當(dāng)P的優(yōu)先級高于二級隊列的進(jìn)程p2時，停止循環(huán)，將P插入到p1的后面；如果P高于二級隊列的所有進(jìn)程時，也會在p2指向Head時，因（*p）.w<=（*p2） .w而停止，則該節(jié)點便成了二級隊列的末尾。因為（（head1）.w=-1，而任何進(jìn)程的優(yōu)先級數(shù)都不會小于1因此當(dāng)p1，p2在這二級隊列中遍歷時，一定能有機(jī)會停止。
    4） 調(diào)度等待鏈表中的一級隊列
    當(dāng)前進(jìn)程完成或時間片到時，調(diào)度等待鏈表中的一級隊列中最前面的實時進(jìn)程：
PnowTime；//當(dāng)前的時間
    run list（pnow）；
    TaskNode*pnow；
    {
      if（*pnow）.ptime!=0）//該進(jìn)程未完成
        {
          if（*pnow）.flag==1）
            if（PnowTime-（*pnow）.T>=（*pnow）.dtime）
              move-last-runqueue（head2，now）；//將未完成的進(jìn)程插入到              二級隊列
                  else
                  pnow； //被夭折
              else
            move last（pnow）； //將未完成的非實時進(jìn)程插入到非實時隊列
            }
        p=get node（ ）；從就緒鏈表中獲得優(yōu)先級最大的進(jìn)程
          while（1）
          {
              if （p! =NULL）
                {
                if （（*p）.time <= （*p）.dtime-PnowTime）） //實時進(jìn)程并且沒超過截止期
pnow=P；
break；
else//該進(jìn)程己經(jīng)不能完成，所以重新從就緒鏈表中獲得優(yōu)先級最大的進(jìn)程
                  p=get node；
                  }
          else//實時就緒鏈表中無等待的進(jìn)程調(diào)用非實時就緒隊列
                  return p；
        }
    5）實時進(jìn)程刪除策略
    //curtime是當(dāng)前的時間
    get node()
    {
      p=（Headl）.next；
      while（1）
      if （Head1）.next!= Head1）//有進(jìn)程就緒等待
        {
          p=（Headl）.next；
          if（（*p）.ptime>（（*p）.dtime-Pnowllme）） //進(jìn)程未完成的時間大于相對截止期，該進(jìn)程夭折
          {
              （Head1）.next=（*p）.next；
            if（p= =Head2）//刪除的節(jié)點是一級隊列的尾節(jié)點時
              {
                Head2=Head3；//二級隊列榮升為一級隊列
                  Head3=Head2；//新二級隊列為空
              }
}
else
else      //p進(jìn)程可以在規(guī)定時間完成
return p；  //無進(jìn)程等待
return NULL；
    針對目前Linux實時系統(tǒng)調(diào)度算法中僅用進(jìn)程的價值來確定優(yōu)先級的現(xiàn)象，本文提出了綜合考慮進(jìn)程的重要性和緊迫度來決定優(yōu)先級的調(diào)度算法。算法將進(jìn)程的截止期和價值兩個不相關(guān)的概念，通過公式結(jié)合在一起，用來計算就緒等待隊列中進(jìn)程的優(yōu)先級數(shù)。
    該算法通過雙鏈表來實現(xiàn)。在CPU正常負(fù)載的情況下，優(yōu)化后的調(diào)度算法體現(xiàn)了更優(yōu)的實時性能。