uC/OS II 中就緒表的理解筆記(完整)

      那么優(yōu)先級(jí)為19的任務(wù)要加入就緒表，那么19優(yōu)先級(jí)處在OSRdyTbl[] 的第2元素，所以應(yīng)把OSRdyGrp的第二位置1 ，
      此時(shí)的OSRdyGrp 的值為 0b0000 0100 = 0x04  這個(gè)值也剛好是OSMapTbl[2]的值。

     兩個(gè)任務(wù)所在的優(yōu)先級(jí)組都要在OSRdyGpr 留下?tīng)顟B(tài)位，所以只要把兩個(gè)值進(jìn)行或運(yùn)算就能合并成 0b0000 1100 = 0x0C 。

我想到的改進(jìn)方法那就是不查表，直接把0x01左移動(dòng) OSRdyTbl[]元素即可。
把原算法：

================================== 2014.2.15  ===================================
http://www.torrancerestoration.com/bbs/dpj-30372-1.html  參考鏈接

難得找到高清的視頻，看到就緒表算法的時(shí)候，思維晃進(jìn)小胡同了。。。死活理解不過(guò)來(lái)。

為鞏固所得，先記下來(lái)。

UCOS-II 的優(yōu)先級(jí)是值越小優(yōu)先級(jí)越高 最高支持64級(jí)（0-63）0優(yōu)先級(jí)最高，63優(yōu)先級(jí)最低。

uC/OS II的就緒表結(jié)構(gòu)設(shè)計(jì)的非常有意思，看看Labrosse（uC/OS II設(shè)計(jì)者）的就緒表結(jié)構(gòu)設(shè)計(jì)。

任務(wù)就緒表是由一個(gè)OSRdyTbl數(shù)組表示，數(shù)組大�。∣S_RDY_TBL_SIZE）由最低優(yōu)先級(jí)(OS_LOWEST_PRIO)確定, 這樣可以減少不必要的空間浪費(fèi)，節(jié)約RAM資源。

OSRdyTbl[]是INT8U 類型數(shù)組，每一個(gè)元素占8位。每一位表示一個(gè)優(yōu)先級(jí)狀態(tài)（1為就緒，0則未就緒）。8個(gè)元素則可以表示64個(gè)優(yōu)先級(jí)(8*8=64)。為加速就續(xù)表的查找，Labrosse把每個(gè)OSRdyTbl元素劃為每一優(yōu)先級(jí)組，8個(gè)元素則有8個(gè)優(yōu)先級(jí)組，它定義了一個(gè)INT8U類型的8位變量OSRdyGrp ，OSRdyGrp的每一位對(duì)應(yīng)每個(gè)優(yōu)先級(jí)組。如下圖：

假設(shè)優(yōu)先級(jí)31的任務(wù)第一個(gè)加入了就緒任務(wù)表，此時(shí)OSRdyGrp和OSRdyTbl的情況：

OSRdyGrp的第3位為1，表示第3優(yōu)先級(jí)組有就緒任務(wù)。

OSRdyTbl的第7位為1，表示第31優(yōu)先級(jí)的任務(wù)被就緒。

此時(shí)OSRdyGrp的其他位為零，OSRdyTbl的其他元素中的位都為零

現(xiàn)在開(kāi)始分析一下算法。

定義：

#define  OS_RDY_TBL_SIZE   ((OS_LOWEST_PRIO) / 8 + 1)

OS_EXT  INT8U     OSRdyGrp;                           

OS_EXT  INT8U     OSRdyTbl[OS_RDY_TBL_SIZE];

OS_EXT  INT8U        OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}

先說(shuō)說(shuō)把指定優(yōu)先級(jí)任務(wù)加入就緒表的算法。

OSRdyGrp |= OSMapTbl[prio >> 3];                              // prio 表示指定的優(yōu)先級(jí)  

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

上面解釋了那么多，就是為了這倆句。

先看看 prio>>3 為什么要右移三位。

UCOS-II最多支持64個(gè)優(yōu)先級(jí)，即從0到63。最低的優(yōu)先級(jí)為63 轉(zhuǎn)換成二進(jìn)制：0x00111111

剛好占6位，那么可以把6為劃分為高三位和低三位，就拿上面的優(yōu)先級(jí)為31任務(wù)的例子來(lái)說(shuō)：

31取其高三位 31>>3 = 3 ，看，是不是剛好表示OSRdyGrp的第3位？也就是說(shuō)在OSRdyTbl[3]。

31取其低三位 31&0x07 = 7，看，是不是剛好表示OSRdyTbl的第7位？也就是說(shuō)在OSRdyTbl[3]的第7位。

兩個(gè)組合起來(lái)：31的優(yōu)先級(jí)在OSRdyTbl的第3個(gè)元素中的第7位。

這就是為什么prio >> 3 和 prio & 0x07了 。

(視頻教程可坑死我了，說(shuō)是在OSRdyGrp分6位。郁悶。。。我就在想，OSRdyGrp的每一位不是都對(duì)應(yīng)這就緒表的每一組嗎？怎么就又分6位了，現(xiàn)在搞明白這點(diǎn)，一下子全通了。。。)

得到之后如何進(jìn)一步得到OSRdyGrp的值和OSRdyTbl中第3個(gè)元素的值呢？

從上圖來(lái)看，OSRdyGrp的第三位置1 所以O(shè)SRdyGrp = 0b0000 1000 = 0x08  而OSRdyTbl[3]的第七位被置1 所以等于 OSRdyTbl[3] = 0b1000 0000 = 0x80 。

那么我們繼續(xù)分析它的算法，剩下的算法很簡(jiǎn)單啦，就是將得到的值和OSMapTbl表對(duì)應(yīng)起來(lái)。典型的用空間換時(shí)間的方法。

OSRdyGrp[31>>3] = 0x08，OSRdyGrp[31&0x07] = 0x80

剛好和我們上圖看的結(jié)果一樣。那既然得到了 OSRdyGrp的值和OSRdyTbl[3]那為什么不直接復(fù)制過(guò)去呢，而是要與其相| (或)，這是因?yàn)镺SRdyGrp的每一位記錄著每一個(gè)優(yōu)先級(jí)組是否有任務(wù)就緒的狀態(tài)，而OSRdyTbl的每一位都記錄著每個(gè)優(yōu)先級(jí)的就緒狀態(tài)。如果直接賦值，則會(huì)覆蓋所有的狀態(tài)位，所以要用 或運(yùn)算 來(lái)合并，這樣就不會(huì)影響其他位的狀態(tài)了。

舉個(gè)例子：

例如 優(yōu)先級(jí)19的任務(wù)此時(shí)要進(jìn)入就緒任務(wù)表

就緒表中已經(jīng)有優(yōu)先級(jí)為31的任務(wù)

那么

此時(shí)的OSRdyGrp 的值為 0b00001000 = 0x08

此時(shí)的OSRdyTbl[3]的值為 0b10000000 = 0x80

現(xiàn)在要將優(yōu)先級(jí)為19的任務(wù)加入就緒表中

根據(jù)算法：

OSRdyGrp |= OSMapTbl[prio >> 3];

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

一步一步來(lái)

// OSRdyGrp |= OSMapTbl[prio >> 3];

19 >> 3 = 0x02;       // 取高三位，確定在第2優(yōu)先級(jí)組 即 OSRdyTbl[2]

OSMapTbl[0x02] = 0x04;       // 查表得到 OSRdyGrp 的值應(yīng)為 0x04 = 0b0000 0100

0x08（OSRdyGrp）| 0x04 = 0x0C; // 0b0000 1000 | 0b0000 0100 = 0b0000 1100 和原OSRdyGrp合并得到新的值 0x0C

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

19 & 0x07 = 0x03       // 取低三位，確定在OSRdyTbl[2]的第三位

OSMapTbl[0x03] = 0x08; // 查表得到OSRdyTbl[2]的值為0x08

0x00(OSRdyTbl[0x02]) | 0x08 = 0x08; // 0b0000 0000 | 0b 0000 1000 = 0x08和原OSRdyTbl[0x02]合并得到新的值 0x08

那么此時(shí)的就緒表和OSRdyGrp 的每一位狀態(tài)應(yīng)為：

而OSRdyTbl的每一位狀態(tài)應(yīng)為

先寫(xiě)到這，現(xiàn)在只是明白了算法的原理，還不太理解OSRdyGrp存在的意義。

================================== 2014.2.16 更新  =======================
看著OS_EXT  INT8U        OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}  。
突然想到當(dāng)初學(xué)AVR編程的時(shí)候，要給某一組引腳設(shè)置輸入輸出模式的時(shí)候，用的置位方法。
這個(gè)OSMapTbl 的存在原因，不就是為了把OSRdyTbl 的元素在OSRdyGrp 對(duì)應(yīng)的位置位嗎？
想到一個(gè)改進(jìn)的方法，其實(shí)應(yīng)該可以去掉這個(gè)OSMapTbl 表。
原算法：
      優(yōu)先級(jí)的表已經(jīng)存在了優(yōu)先級(jí)為31的任務(wù)，處在OSRdyTbl[]的第3元素，所以應(yīng)把OSRdyGrp的第三位置1，
    此時(shí)的OSRdyGrp 的值為 0b0000 1000 = 0x08    這個(gè)值剛好是OSMapTbl[3]的值。

      那么優(yōu)先級(jí)為19的任務(wù)要加入就緒表，那么19優(yōu)先級(jí)處在OSRdyTbl[] 的第2元素，所以應(yīng)把OSRdyGrp的第二位置1 ，
      此時(shí)的OSRdyGrp 的值為 0b0000 0100 = 0x04  這個(gè)值也剛好是OSMapTbl[2]的值。

     兩個(gè)任務(wù)所在的優(yōu)先級(jí)組都要在OSRdyGpr 留下?tīng)顟B(tài)位，所以只要把兩個(gè)值進(jìn)行或運(yùn)算就能合并成 0b0000 1100 = 0x0C 。

我想到的改進(jìn)方法那就是不查表，直接把0x01左移動(dòng) OSRdyTbl[]元素即可。
把原算法：

================================== 2014.2.18 更新  ===================

================================== 2014.3.22  ===================================
就緒表中查找已經(jīng)就緒的最高優(yōu)先級(jí)任務(wù)的實(shí)現(xiàn)方法和原理.

實(shí)時(shí)操作相同的任務(wù)切換速度很快，每次做任務(wù)切換時(shí)，UCOS 都要找到優(yōu)先級(jí)最高的任務(wù)來(lái)執(zhí)行，所以從就緒表中尋找最高優(yōu)先級(jí)的任務(wù)的效率直接就影響了UCOS內(nèi)核的效率。

首先我們看看UCOS的算法：

y = OSUnMapTal[ OSRdyGrp ];                     // 取最高優(yōu)先級(jí)所在的任務(wù)組

x = OSUnMapTal[OSRdyTbl[y]]                     // 取該任務(wù)組中最高的優(yōu)先級(jí)

prio = (y << 3) + x;                                   // 組合計(jì)算

很簡(jiǎn)單，就三句代碼。剛開(kāi)始我看到這個(gè)很詫異，為什么要浪費(fèi)256個(gè)字節(jié)的空間來(lái)存放這些很奇怪的數(shù)值。用個(gè)循環(huán)不就可以確定優(yōu)先級(jí)了嗎？原來(lái)，在實(shí)時(shí)操作系統(tǒng)的任何操作都必須可預(yù)知的，而循環(huán)則無(wú)法確定其執(zhí)行的時(shí)間。

我們看看OSUnMapTbl[256]數(shù)組是如何出來(lái)的。

由于處于就緒狀態(tài)的任務(wù)可能有多個(gè)，也就是說(shuō)OSRdyGrp和 OSRdyTbl[]中有可能不止一位是被置1的。由于優(yōu)先級(jí)的數(shù)字越小，優(yōu)先級(jí)就越高，所以要從這些就緒的任務(wù)中找出優(yōu)先級(jí)最高的任務(wù)，只需要取OSRdyGrp和OSRdyTbl[]中被置1的最低位。

過(guò)程： 取OSRdyGrp中被置1的最低位y，得到最高優(yōu)先級(jí)所在的任務(wù)組（即在OSRdyTbl[]的y元素），再取這個(gè)任務(wù)組中被置1的最低位x，得到最高優(yōu)先級(jí)在OSRdyTbl[]所對(duì)于的位，再通過(guò)y與x的組合就得到了最高優(yōu)先級(jí)。

那么要解決的問(wèn)題出現(xiàn)了，怎么去找OSRdyGrp、OSRdyTbl[]被置1的最低位呢？哈，就是上面那個(gè)很詭異的OSUnMapTbl[]表啦，不能用循環(huán)就只能查表方法了。OSRdyGrp和OSRdyTbl[]元素都占用一個(gè)字節(jié)，一個(gè)字節(jié)等于8位，2^8 = 256 種可能性，所以定義了256個(gè)字節(jié)的OSUnMapTbl[]表。

下面是依次把各種可能性寫(xiě)下來(lái)。

0x00 ==00000000b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[0](其實(shí)為空，空的情況默認(rèn)為0，不影響計(jì)算)

0x01 ==00000001b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[1]

0x02 ==00000010b 最低位為1的位數(shù)為 bit1==1==OSUnMapTbl[2]

0x03 ==00000011b 最低位為1的位數(shù)為bit0==0==OSUnMapTbl[3] (有兩個(gè)為1的位，bit0,bit1,取最小的，因?yàn)镺SRdyGrp或OSOSRdyTbl中最小的位數(shù) 對(duì)應(yīng)的優(yōu)先級(jí)越大)

0x04 ==00000100b 最低位為1的位數(shù)為 bit2==2==OSUnMapTbl[4]

0x05 ==00000101b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[5]

0x06 ==00000110b 最低位為1的位數(shù)為 bit1==1==OSUnMapTbl[6]

0x07 ==00000111b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[7]

0x08 ==00001000b 最低位為1的位數(shù)為 bit3==3==OSUnMapTbl[8]

0x09 ==00001001b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[9]

0x0A ==00001010b 最低位為1的位數(shù)為 bit1==1==OSUnMapTbl[10]

0x0B ==00001011b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[11]

0x0C ==00001100b 最低位為1的位數(shù)為 bit2==2==OSUnMapTbl[12]

0x0D ==00001101b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[13]

0x0E ==00001110b 最低位為1的位數(shù)為 bit1==1==OSUnMapTbl[14]

0x0F ==00001111b 最低位為1的位數(shù)為 bit0==0==OSUnMapTbl[15]

…

…

y = OSUnMapTal[ OSRdyGrp ];  

// 通過(guò)查表取得OSRdyGrp最低有效位（被置1的位），即取得最高優(yōu)先級(jí)所在的任務(wù)組。

x = OSUnMapTal[OSRdyTbl[y]];

// 通過(guò)查表取得該任務(wù)組中最低有效位，即取得最高優(yōu)先級(jí)所對(duì)應(yīng)的OSRdyTbl[y]位。

prio = (y << 3) + x;                                   

// 根據(jù)OSRdyGrp與OSRdyTbl[]、OSRdyTbl[]與優(yōu)先級(jí)的對(duì)應(yīng)關(guān)系，計(jì)算出OSRdyTbl[y]中的x位與OSRdyTbl[0]中的第0位的位數(shù)。

如在OSRdyTbl[3]中的第6位，3*8 = 24，OSRdyTbl[3]前面有24位，再加上OSRdyTbl[3]中的6位，等于30 。