許璐璐　鄭吉洲

[摘要]嵌入式實時操作系統(tǒng)μC/OS-Ⅱ在時鐘節(jié)拍服務(wù)中，需要遍歷任務(wù)控制塊鏈表中的所有任務(wù)控制塊，對任務(wù)的延時進(jìn)行管理，效率比較低。針對這個問題，論文提出了一種改進(jìn)方法，使用增量鏈表對任務(wù)延時進(jìn)行高效管理，并給出了增量鏈表的實現(xiàn)及其在μC/OS-Ⅱ任務(wù)延時管理中的運用。

[關(guān)鍵詞]μC/OS-Ⅱ；任務(wù)延時管理；增量鏈表

1 引言

μC/OS-Ⅱ是一個源碼開放的嵌入式實時操作系統(tǒng)，具有結(jié)構(gòu)精簡、可裁剪、可移植性強(qiáng)、多任務(wù)可剝奪實時內(nèi)核等特點，穩(wěn)定性和安全性能好，在嵌入式領(lǐng)域應(yīng)用廣泛。任務(wù)延時是嵌入式實時操作系統(tǒng)中的一個常用操作，可能發(fā)生在任務(wù)主動讓出CPU、等待某一事件發(fā)生等情況下。每個需要延時的任務(wù)都有自己特定的延時請求，操作系統(tǒng)必須維護(hù)申請延時任務(wù)的集合，對任務(wù)的延時狀態(tài)、延時時間進(jìn)行管理。

數(shù)據(jù)結(jié)構(gòu)的設(shè)計對操作系統(tǒng)任務(wù)延時管理的效率有很大的影響。本文分析了μC/OS-Ⅱ?qū)θ蝿?wù)延時管理的缺點，提出了一個基于增量鏈表的改進(jìn)方案，能夠?qū)崿F(xiàn)對延時任務(wù)的高效管理。

2 μC/OS-Ⅱ任務(wù)延時管理分析

μC/OS-Ⅱ中調(diào)用OSTimeDly（）可實現(xiàn)對任務(wù)的延時，任務(wù)的延時時間保存在任務(wù)控制塊里的OSTCBDly變量中，在時鐘節(jié)拍服務(wù)程序OSTimeTick（）中對任務(wù)的延時狀態(tài)進(jìn)行更新，其部分代碼如下（參照μC/OS-Ⅱv2，86版本）：

從代碼可以知道。需要遍歷任務(wù)控制塊鏈表中的所有任務(wù)控制塊，對其中的延時任務(wù)進(jìn)行狀態(tài)更新，當(dāng)系統(tǒng)中任務(wù)數(shù)比較多時，這是個很耗時的操作，效率比較低。

3 使用增量鏈表對任務(wù)延時進(jìn)行有效管理

3.1 增量鏈表概述

使計算更高效的方法是使用相對時間而非絕對時間。增量鏈表包含一個延時任務(wù)集合，并且鏈表是按每個任務(wù)的延時時間進(jìn)行排序，但是每個節(jié)點存儲的不是任務(wù)延時的絕對時間，而是在增量鏈表中存儲任務(wù)相對于前一個任務(wù)必須延遲的多余的時間。

因此，增量鏈表中第一個任務(wù)的延時鍵值指定了相對于當(dāng)前的時間，該任務(wù)需要等待的時鐘滴答數(shù)，其他每一個任務(wù)的鍵值指定了相對于各自的前一個任務(wù)。該任務(wù)需要等待的時鐘滴答數(shù)。任務(wù)延遲的絕對時間等于增量鏈表中該任務(wù)的鍵值與該任務(wù)之前的所有任務(wù)的鍵值之和。

例如，假設(shè)任務(wù)A、B、C、D分別請求延遲5、20、50、100個時鐘滴答，且假設(shè)這樣的請求在幾乎相同時間做出（即在一個時鐘滴答內(nèi)），圖1顯示了使用增量鏈表存儲這4個延時任務(wù)的情況。

給定一個增量鏈表，可以通過計算部分鍵值的和得到每個任務(wù)的延時時間。

使用了增量鏈表后，由于鏈表中所有后續(xù)任務(wù)的延時時間都是與第一個延時相關(guān)的。因此在時鐘節(jié)拍服務(wù)程序中，只需要遞減增量鏈表第一項的延時鍵值，不需要掃描整個鏈表，效率有了很大的提高。當(dāng)?shù)谝豁椀逆I值變?yōu)?時，表明該任務(wù)延時時間已到，需要將其放入就緒表。

3.2 增量鏈表的實現(xiàn)

為了實現(xiàn)增量鏈表，在任務(wù)控制塊中添加項：

聲明延時增量鏈表

SO_TCB*OSDelayList。

插入鏈表操作，需要計算一個相對延遲，將指定的任務(wù)插入到OSDelayList中合適的位置。搜索過程從鏈表頭開始遍歷鏈表，將待插入節(jié)點的相對延時值與鏈表中的節(jié)點的值比較，當(dāng)發(fā)現(xiàn)待插入節(jié)點的值小于鏈表中某一節(jié)點時，則在該位置插入新節(jié)點。每當(dāng)跳過一個節(jié)點時，需要將待插入節(jié)點的值減去該節(jié)點的值，得到相對延遲量。而當(dāng)插入一個新節(jié)點時，必須在鏈表的剩余節(jié)點中減去由于插入新節(jié)點而導(dǎo)致的延時值的改變。即在下一個節(jié)點的值中減去新插入節(jié)點的值。

例如，假設(shè)某一時刻延時鏈表如圖1所示，待插入任務(wù)E的延時值為30，則插入過程如圖2所示。

插入鏈表操作關(guān)鍵代碼如下：

使用了延時增量鏈表后，在原來的OSTimeDly（）中，延時操作OSTCBCur->OSTCBDly=ticks

則變?yōu)椋?/p>

insert（OSTCBCur，ticks）；

在時鐘節(jié)拍服務(wù)程序中，只需遞減延時鏈表第一個節(jié)點的鍵值，當(dāng)其變?yōu)?時，表明其延時時間已到，需要將該任務(wù)喚醒：

函數(shù)wakeup（）需要將延時鏈表中從第一項開始延時鍵值為0的所有任務(wù)喚醒：

{

清等待狀態(tài)標(biāo)志：

if（任務(wù)狀態(tài)為ready）

任務(wù)放入就緒表；

ptcb=ptcb->delay_next；

}

OSDelayList=ptcb；

}

當(dāng)某個任務(wù)要取消延時，需將其從延時增量鏈表中移除，且需要將鏈表中該節(jié)點之后的剩余節(jié)點加上由于移除節(jié)點而導(dǎo)致的相對延時值的改變，即在下一個節(jié)點的鍵值中加上被移除節(jié)點的鍵值。

4 結(jié)束語

增量鏈表通過使用相對時間而非絕對時間。實現(xiàn)了對延時任務(wù)的高效管理，在對時間效率要求較高的實時系統(tǒng)中，有良好的應(yīng)用效果，也可將其借鑒到其他的應(yīng)用場景中。