UC/OS下的調度算法改造,提供非搶占的基于時間片輪轉調度

摘要:UC/OS-II是在嵌入式設備上設計的實時多任務操作系統，具有可剝奪實時內核，實現了基于優先級的搶占式任務調度算法。本算法保持現有的 UC/OS-II 內核關于任務調度的相關函數接口，提出了一種改進 UC/OS-II 內核調度的方法，使其能實現多個任務以時間片輪轉方式調度。

關鍵詞:UC/OS-II;嵌入式;操作系統;時間片輪轉

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)21-6112-02

UC/OS-II是源碼開放的實時嵌入式操作系統，其主要特點如下:小巧，源碼開放有詳細的注解，系統透明化，可移植性強; 在內核中添加關于時間片調度算法的調度依據是“任務的運行時間”，基本方法是為每個任務分配一個時間片，當任務啟動時，對任務進行計時，當任務時間片運行完后進行任務調度，即切換到下一個任務。

在本算法中，可以利用UC/OS-II現有的條件，可以對任務進行控制。對于時間片調度算法的計時，在內核中中的時鐘中斷處理函數OSTimeTick本身就有對任務的計時功能，此外，只需要添加任務的時間片參數，以及連接多個優先級相同任務的鏈表，即可實現相同優先級任務的切換。至于不同優先級任務的切換，則需要人延續內核調度算法中按照任務鏈表輪轉切換，不需要加以改進。

1 算法設計

1.1 相關數據結構的更改

OS_TASK_TIMESLICE 10:在OS_Cfg.h 中增加常量OS_TASK_TIMESLICE，其值表示任務運行的時間片。在本文討論的時間片輪轉調度算法中，所有任務的時間片都是相同的。

增加全局變量:OS_EXT INT8U SamePrioNum[OS_LOWEST_PRIO + 1]; //同優先級任務個數

為統計同優先級任務個數以及判斷同優先級是否存在，增加全局數組SamePrioNum，此數組的大小等于系統配置的最大優先級值。創建任務時，通過修改SamePrioNum[prio]的值可以方便的得到同優先級任務個數。

OS_EXTINT8USamePrioSche;//主動調度標志

為進行主動調度，引入全局標志 SamePrioSche:表示是否有同優先級任務調度的需要。若SamePrioSche為1，表示當前優先級任務有多個，并且當前任務時間片已耗盡，需要切換到下一個同優先級任務。

TCB的修改:時間片輪轉調度中一個優先級是可以對應多個任務的，OSTCBPrioTbl[]的元素應該由原來的指向單個TCB改進為指向多個TCB，采用雙向循環TCB鏈表來連接同優先級下的多個TCB塊。根據時間片輪轉調度在同優先級任務中的應用，需要對任務的TCB進行修改，增加3個屬性項:

INT8U OSTSCurLen(剩余時間片長度):保存任務時間片在本時間片的剩余長短，單位是OSTimeTick數

os_tcb *OSTimeSchNext (TCB 雙向鏈表后繼指針)

os_tcb *OSTimeSchPrev (TCB 雙向鏈表前驅指針)

通過改動，由就緒表(OSRdyTbl[]， OSRdyGrp)就能得出進入就緒狀態任務中最高優先級值，再根據最高優先級值和OSTCBPrioTbl[]確定需要進入運行態的任務TCB雙向循環鏈表，而后對鏈表中的任務進行時間片輪轉調度。

1.2 時間片輪轉調度算法設計

1.2.1 OS_TCBInit

任務控制塊初始化只需把新添加的變量賦值即可，首先要的就是把記錄優先級任務個數的值加1，然后初始化OSTSCurLen

SamePrioNum[prio]++; //記錄本優先級的任務個數

ptcb->OSTSCurLen=OS_TASK_TIMESLICE;

其次是把上面說到的那個鏈表鏈接起來，相同優先級的任務采用FIFO方式輪轉。

if(SamePrioNum[prio]==1){ //第一次創建該優先級task

ptcb->OSTimeSchPrev = ptcb;//讓同任務鏈表首尾都指向自己

ptcb->OSTimeSchNext = ptcb;

}

else{ //以前存在同優先級的task，將當前task放入鏈表

ptcb->OSTimeSchNext = OSTCBPrioTbl[prio]->OSTimeSchNext;

ptcb->OSTimeSchPrev = OSTCBPrioTbl[prio];

(OSTCBPrioTbl[prio]->OSTimeSchNext)->OSTimeSchPrev= ptcb;

OSTCBPrioTbl[prio]->OSTimeSchNext=ptcb;

}

這一處是進行相同優先級鏈表的連接，在優先級沒有被占用的時候，這個鏈表的前后都鏈向自己，這樣在調度的時候，FIFO調度就算指向下個任務，也指向的是自己，不影響優先級調度。如果此優先級的任務被占用了，就在相同優先級的雙向鏈表中加這個新建的tcb，用OSTCBPrioTbl[prio]來索引前一個具有相同優先級的任務。

1.2.2 OSTimeTick

if(SamePrioNum[OSTCBCur->OSTCBPrio]>1){ //如果同優先級里面有多個task

if(--OSTCBCur->OSTSCurLen==0){//時間片在這次調度中用完了

OSTCBCur->OSTSCurLen =OS_TASK_TIMESLICE; //就把時間片重新賦值

SamePrioSche=1; //主動調度標志設為

OSTCBPrioTbl[OSTCBCur->OSTCBPrio]=OSTCBCur ->OSTimeSchNext;

OSTCBCur=OSTCBPrioTbl[OSTCBCur->OSTCBPrio];

}

}

時間片調度計時的工作就放在OSTimeTick 中，每個時鐘tick，任務的時間片做相應的調整。只需添加以上部分內容，如果當同優先級里面有多個task，并且在此次的調度中時間片結束，就把時間片重新賦值回去，以便下一次的調度。把主動調度標志設為1，把當前的tcb指針OSTCBCur該為下一個同優先級的任務。

1.2.3 OSIntExit 退出中斷函數

因為UC/OS-II 的調度依據是優先級，而時間片任務的優先級相同，所以必須進行“主動”調度，即調用其任務切換函數OSIntCtxSw()。同優先級任務切換的基本條件是:當系統存在多于1個的同優先級任務，且任務優先級是當前就緒任務中最高的，也就是主動調度標志SamePrioSche=1。

if (OSPrioHighRdy != OSPrioCur) {/*當有高優先級任務就緒時進行優先級搶占調度*/

…}

else if(SamePrioSche==1) // 如果需要進行同優先級任務切換

OSIntCtxSw(); // 主動任務調度

1.2.4 OSIntCtxSw() 任務調度函數

if(SamePrioSche==1){

OSTCBHighRdy=OSTCBHighRdy->OSTimeSchNext;//改變最高級的任務

}

這是任務調度的關鍵之處，而原系統優先級搶占調度方式中，OSTCBHighRdy 是通過查表自動得到的，在同優先級任務調度時，OSTCBHighRdy要指向相同優先級鏈表的下一個任務，在此需要進行手動設置，否則將不能進行任務的切換。

2 總結

在 UC/OS-II 的優先級搶占式調度基礎上添加了同優先級的時間片輪轉調度策略，本算法最大的優點就是最大程度上保持了新操作系統與就內核的上層接口一致性。用戶可以在不了解任務的具體調度實現的基礎上，原來的應用程序可以不做任何修改即能運行在新系統之上，并且可以在原系統上添加更多的同優先級任務，使得UC/OS-II系統不再受到64個任務的限制，在實際應用中也不必在為相同重要程度的任務安排優先級而困擾，從而減少因多任務制約而帶來的低效率編程復雜度。

參考文獻:

[1] 成后發，楊春金. UC/OS2II操作系統內核的改進[J].通訊和計算機，2006，3(6):52-55.

[2] 趙炯. Linux內核完全注釋[M].北京:機械工業出版社，2004.

[3] 吳永忠，程文娟，鄭淑麗，徐海衛.嵌入式實時操作系統UCOS-II教程[M].西安:西安電子科技大學出版社，2007.