μC/OS—Ⅱ任務(wù)延時(shí)管理的改進(jìn)

許璐璐　鄭吉洲

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

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

1 引言

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

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

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

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

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

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

3.1 增量鏈表概述

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

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

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

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

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

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

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

聲明延時(shí)增量鏈表

SO_TCB*OSDelayList。

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

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

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

使用了延時(shí)增量鏈表后，在原來(lái)的OSTimeDly（）中，延時(shí)操作OSTCBCur->OSTCBDly=ticks

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

insert（OSTCBCur，ticks）；

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

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

{

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

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

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

ptcb=ptcb->delay_next；

}

OSDelayList=ptcb；

}

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

4 結(jié)束語(yǔ)

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