09年4月7號課程筆記

表一



1010 ==> 10
^^^^
8421

index




0000
0110
0000
1000
^^^^
3210

表二



先說怎麼得到index值
從表二的最上面一列和index的最右邊開始，表二的每一個row對應出index的每個column值，每個index column只能填零或一。

只要表二的row空格有一個值以上是一，對應到的index column值就是一，如果表二的某個row空格全部是零，則對應到的index column值是零。



uC/OSII Schedular 的功用
1.找出最高優先權的task
2.增加一個task
3.刪除一個task

正常來說 schedular 的 time complexity應該是O(lgn)，但實際上是O(1)，為什麼可以這麼快呢？因為是使用查表加速的！

uC/OSII中task的priority number愈小，代表其優先權愈高。

舉例來說
如果我們想找到最高優先權的task，schedular會怎麼做呢?


以下是找到最高優先權的task之步驟: min(PriorityNumber)
1.將得到的index查表一，從零開始數(0,1,2,3,...etc)，可以得到一數字。
2.將它乘以index容量大小，這裡有四個column，所以乘以四。
3.看index最右邊的一出現在表二的哪個row，取得那個row的數字，再查表。
4.得到的數字加上之前算的結果，即得到目前是最高優先權的task。

註:uC/OSII已經限制PriorityNumber的大小，最大的數字是六十四