ucOSII操作系統(tǒng)就緒表分析

在ucOSII的緒表中使用一個(gè)很妙的查找方式，下面對(duì)其查找過程進(jìn)行詳細(xì)分析（目的就是加快查找速度）

對(duì)于ucOSII而言，其最大的任務(wù)數(shù)是64個(gè)，因此為了標(biāo)記其任務(wù)的狀態(tài)，ucOSII使用了八個(gè)變量表示每個(gè)任務(wù)的狀態(tài)，每個(gè)變量每個(gè)位對(duì)應(yīng)任務(wù)的狀態(tài)：

如果我們直接去查找就緒任務(wù)的最高優(yōu)先級(jí)任務(wù)，那我們需要遍歷這八個(gè)變量，去判斷最高位是1，很顯然在最壞情況下需要遍歷64次，那有沒有更好的方法呢，仔細(xì)觀察發(fā)現(xiàn)一個(gè)規(guī)律，當(dāng)任務(wù)優(yōu)先級(jí)是8的時(shí)候，其就緒標(biāo)志位在OSRdyTbl[1]中的第0位，8對(duì)應(yīng)的二進(jìn)制是00001000，這樣00001正好是1，000正好是0， 我們?cè)诳纯雌渌遣皇沁@樣，例如7的二進(jìn)制00000111，00000對(duì)應(yīng)的是0，也就是OSRdy[0]，111對(duì)應(yīng)7，也就是第7位，繼續(xù)驗(yàn)證發(fā)現(xiàn)確實(shí)所有的優(yōu)先級(jí)都滿足這個(gè)規(guī)律，因此我們可以利用這一點(diǎn)來加快查找速度。 這樣我們就有如下結(jié)構(gòu)：

實(shí)際上有OSRdyl的下標(biāo)表示中只有3，4，5三位有效，因?yàn)檫@里只有8組，不過這個(gè)無所謂，都是一樣的。 為了表示這些組中有沒有就緒任務(wù)，ucOSII中定義了一個(gè)OSRdyGrp這個(gè)變量，該變量是一個(gè)8位的無符號(hào)整型，這樣每一位表示每個(gè)組有無就緒任務(wù)：

這樣OSRdyGrp的初始值為0，當(dāng)有一個(gè)任務(wù)創(chuàng)建時(shí)，那就將該任務(wù)所在的組（即OSRdyTbl)對(duì)應(yīng)的OSRdyGrp相應(yīng)的位設(shè)置為1，當(dāng)有任務(wù)刪除時(shí)，那就將該任務(wù)所在的組對(duì)應(yīng)的OSRdyGrp相應(yīng)的位設(shè)置為0，如下：

創(chuàng)建任務(wù)（登記）：

OSRdyTbl[prio>>3] |= （prio&0x07）;

OSRdyGrp |= （prio>>3）;

刪除任務(wù)（注銷）：

OSRdyTbl[prio>>3] &= ~（prio&0x07）;

OSRdyGrp &= ~（prio>>3）;

在ucOSII中為了加快速度，定義了一個(gè)數(shù)組const UINT8 OSMapTbl[8]（說明：這里可以看到OSRdyGrp對(duì)其一個(gè)變量位操作會(huì)通過很多指令完成，但是如果對(duì)一個(gè)固定的常量進(jìn)行位操作就減少很多指令）

這樣上面的操作就變?yōu)榱巳缦虏僮鳎?/p>

創(chuàng)建任務(wù)（登記）：

OSRdyTbl[prio>>3] |= OSMapTbl [prio&0x07];

OSRdyGrp |= OSMapTbl [（prio>>3）];

刪除任務(wù)（注銷）：

OSRdyTbl[prio>>3] &= ~OSMapTbl [prio&0x07];

OSRdyGrp &= ~OSMapTbl [（prio>>3）];

這樣就完成了任務(wù)創(chuàng)建和刪除時(shí)對(duì)就緒表的操作，在ucOSII中還需要涉及到最高優(yōu)先級(jí)查找，因?yàn)楫?dāng)當(dāng)前運(yùn)行任務(wù)進(jìn)入阻塞態(tài)時(shí)，下一個(gè)運(yùn)行任務(wù)就應(yīng)該時(shí)最高優(yōu)先級(jí)任務(wù)，因此我們必須找到最高優(yōu)先級(jí)的任務(wù)，顯然，我們需要找到數(shù)組中OSRdyTbl的為1的最高位在哪。 最然這個(gè)過程很簡(jiǎn)單，但是我們需要加快查找速度，在ucOSII中定義了一個(gè)查找表，這個(gè)表可以直接索引到對(duì)應(yīng)的為1的最高位（也就是就緒表中最高優(yōu)先級(jí)），其實(shí)這個(gè)過程和上面對(duì)OSRdyGrp的操作是一個(gè)反過程，首先我們要確定哪個(gè)組（OSRdyTbl[8]）中有就緒任務(wù)，那這個(gè)如何做呢？ 假設(shè)此時(shí)OSRdyGrp=5（00000101)，可以看到最高優(yōu)先級(jí)的組在2組（最高位為2位），現(xiàn)在我們還需要確定組中的哪個(gè)位，那又如何確定呢？ 上面說過了，需要定義一個(gè)查找表，這樣我們就從這個(gè)方面下手。

首先我們需要完成OSRdyGrp=5映射到2類似這種映射（其實(shí)就是找出OSRdyGrp的最高位），其次就是找出OSRdyTb[]中的最高位，有趣的事情出現(xiàn)了，這兩個(gè)過程其實(shí)是同一個(gè)過程，都是找一個(gè)變量的最高位，因此我們只需要設(shè)計(jì)一張表就可以完成此工作哦，這個(gè)就是ucOSII中查找就緒任務(wù)的妙處所在。 好了，下面我們來設(shè)計(jì)這張表：

再次強(qiáng)調(diào)查找表的目的是找到一個(gè)變量最高位，比如5的最高位是2，3的最高位是1，1的最高位是0.....

最直接的辦法是枚舉，你沒有看錯(cuò)，就是這么簡(jiǎn)單粗暴，總共有2的8次方就是256種情況，天啊，這我弄不了，這輩子都弄不了，其實(shí)不用你一個(gè)一個(gè)去枚舉，數(shù)學(xué)家說：不就是找出一個(gè)最高位么，簡(jiǎn)單，log2X就這么easy!，好了，我們就可到了查找表：

UnMapTbl[256]={0，log21，日志22，日志23，日志24，日志25，日志26，日志27......};

通過excel計(jì)算得到UnMapTbl[256]={ 0,0,1,2,2,2,3,3,3......};

馬上有人開始說了，這不對(duì)吧，這個(gè)和源碼中的不一樣，確實(shí)，別急，且聽我說， 這里由于ucOSII中的優(yōu)先級(jí)是反的，也就是數(shù)值越大，其優(yōu)先級(jí)越低，因此，我們不是找到最高位，而是找到最低位，這樣查找表就變成了源碼中的那樣了，也就是

INT8U  const  OSUnMapTbl[256] = {
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x00 to 0x0F                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x10 to 0x1F                             */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x20 to 0x2F                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x30 to 0x3F                             */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x40 to 0x4F                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x50 to 0x5F                             */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x60 to 0x6F                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x70 to 0x7F                             */
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x80 to 0x8F                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x90 to 0x9F                             */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xA0 to 0xAF                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xB0 to 0xBF                             */
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xC0 to 0xCF                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xD0 to 0xDF                             */
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xE0 to 0xEF                             */
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0        /* 0xF0 to 0xFF                             */
};

確定最高優(yōu)先級(jí)的過程就是這樣：

grp = OSUnMapTbl [OSRdyGrp];

prio = (grp <<3) + OSUnMapTbl [OSRdyTbl [grp] ;

至此，整個(gè)ucOSII的就緒表的分析結(jié)束了，思想很重要，不要僅僅拘泥據(jù)源碼。