優先級位圖演算法詳解

在嵌入式作業系統復習中，我們了解了μC/OS-II的相關基礎知識，在任務調度這一節，我們提到了優先級位圖演算法，本文詳細介紹該演算法的原理和實作， 說明： 本文參考了這篇文章，加入了一些自己的理解，如有侵權，請聯系洗掉：原文鏈接

1、μC/OS-II任務優先級相關簡介：μC/OS-II中共有64個優先級（0~63級，數字越小優先級越高），因為是實時系統，所以對應每個任務就分配一個優先級，

2、2進制和10進制轉換基礎 這里先介紹一個數學知識，二進制如何變為十進制，比如十進制26，其8位二進制表示為：00 011 010，當十進制為0~63時，前兩位無作用，所以只看后6位——011 010.怎么計算成十進制呢？很簡單：把這個十進制數，分為兩個部分，高三位和低三位，這個十進制數的大小就等于高三位的十進制8+低三位的十進制數（其實就是二進制轉八進制再轉十進制），高三位的011=3 ，低三位的010=2，所以26=3x8+2=（011）<<3+(010).即將高三位左移三位就是8再加上低三位，下面要介紹的演算法也是這個數學方法，

3、優先級任務調度程序

1. 創建任務并分配優先級
2. 通過演算法，作業系統對創建完成的任務（即就緒任務）進行標記，并通過標記來查找當中任務中優先級最高的任務
3. 呼叫調度函式進行調度，讓最高優先級任務運行

優先級創建 μC/OS-II中創建任務的函式原型： INT8U OSTASKCeate(void (*task)(void *pd),void *pdata,os_stk *ptos,INT8U prio)，從這個函式可以看出，最后一個引數就是優先級，所以結論是，在創建任務的同時就要確定任務的優先級，并且是該優先級是8位的（0~2^8-1），這里也可以看出為什么會有64個優先級，

因為用戶可以指定任務的優先級，但實時作業系統最大的好處就是高優先級的任務可以搶占低優先級的任務，那怎么實作的呢？當然是通過優先級實作， 既然用戶在呼叫系統函式創建任務的同時指定了任務的優先級，一旦創建了任務，該任務就會立即成為就緒狀態，作業系統就會將該任務的優先級標志位置位1，相當于做個記號，作業系統心里就會想，哦，這個優先級的任務已經就緒了，同樣創建了其他的任務，作業系統都會在某個地方做好標記表明對應優先級的任務已經就緒，然后在調度函式的調度下進行調度，那么在哪個地方做個標記呢？既然是實時作業系統，作業系統用什么演算法去查找優先級最高的任務呢？

任務優先級的標定 什么是優先級的標定：就是作業系統要知道哪個任務已經就緒了，然后就在這些就緒了的任務里面切換調度，所以第一步就是要知道哪些任務就緒了，然后就可以操作了， 這里要先介紹兩個資料結構，：OSRdyGrp、OSRdyTbl[]，這兩個變數協同完成優先級的標定， OSRdyGrp：優先級就緒組 這是一個8位的變數，每一個變數對應于OSRdyTbl[]中的一行（實際上是一個元素，但也可以理解為一行）， OSRdyTbl[]：優先級就緒表 這是一個陣列，有8個成員，每個成員都是8位的變數，所以就可以構成了8*8的矩陣了，所以64個優先級都是標定在這個陣列中的，

從上圖可以明顯看出，這個圖有64個空格（64個位），每個空格對應一個數字，該數字就是優先級的標號，但是這個是人為的標上的，實際上這是64個空格，現在要做的事情就是將就緒任務的優先級相對應的標號置1，表示這個優先級任務就緒了，比如剛創建了一個任務，它的優先級是7，所以往表格中數字為7的空格寫入1就表明該優先級的任務就緒了，可以被調度了，另外當所有需要創建任務都創建完畢后，各個就緒任務的相應數字空格都會置1，表明這些任務都就緒了，比如，現在創建了5個任務，優先級分別為4,7,9,10,24.所以在創建完這些任務后，這個優先級就緒表中的相對應的數字空格都會被置1,要特別注意上圖的優先級順序，0的優先級最高，63的優先級最低，

那到底怎么往空格里置1的呢? 這里就要分析這個優先級就緒表了:

1.這個表的資料結構是陣列，也就是說，這個陣列有8個成員，每個成員都是8位的變數， 2.通過二級查找實作對就緒任務的標定的，這里可以理解為一個矩陣，找某個數，肯定是先找行，再找列，從而找到這個元素位置，思想就是這個， 怎么找行呢?這里的一個變數OSRdyGrp，是一個8位的變數，每一位對應上圖的一行，當某一位置1時，就表明就緒表對應的行有就緒任務，然后再查找列，就可以找到哪個任務就緒了，現在舉個列子來說明：

創建一個任務，它的優先級為 prio=11（這是用戶指定的），此優先級用二進制表示（8位）：最前面兩位無用處，前面已說過 00 001 011，那么怎么在對應的OSRdyTbl[]優先級就緒表中進行標定呢?

1. 把這個二進制數分為兩個部分：高3位 （001）和低3位（011）;
2. 高三位負責找到陣列中的行，低三位負責找到陣列中的列（其實這里不是列，是一個變數的8個位，也可以按列理解），這樣配合就可以尋址，往相應數字標號里寫1，對上面這個數來說 001 =1說明是第1行（陣列從0行開始），011=3說明在第3個位置要寫入1，合在一起就是第一行的第三個位置寫入1，這樣就完成了對應數字優先級標號的標記，

那從上面的思路來看，我們只要知道陣列中的第幾行和第幾列的值就可以了，所以又引進了一個映射陣列： OSMapTbl[]，其具體內容如下，下標0對應的就是0位為1,下標1對應的就是1位為1，然后把這個數賦值給OSRdyGrp優先級就緒組，則OSRdyGrp哪個位為1則說明就是就緒表哪個行有就緒任務了，這樣做的好處就是快，這也就是這個陣列就是個映射陣列，方便操作而已，

至此，以上涉及3個資料結構了，現在來總結一下： 1.OSRdyGrp優先級就緒組：第幾位被置1，就說明就緒表中第幾行有就緒任務，比如OSRdyGrp=0000 0001，說明OSRdyTbl[0]行有就緒任務，具體是這行的哪個列還要根據低三位的值來決定. 2.OSRdyTbl[]優先級就緒表：行+列就能標定就緒任務的優先級. 3. OSMapTbl[]優先級映射表：用來方便生成第幾行，第幾列的一個轉換.

下面來看ucos中的原始碼怎么實作的： 任務就緒原始碼如下：

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

代碼解釋：prio>>3是獲取優先級的高3位，prio&0x07是獲取優先級的低3位，然后在通過OSMapTbl的映射分別獲得了就緒表中的行和就緒表中的列， 然后查詢就緒演算法：

y = OSUnMapTbl[OSRdyGrp]; 
x = OSUnMapTbl[OSRdyTbl[y]]; 
prio = (y << 3) + x; 

舉個例子： 創建一個任務，且prio=11=001 011 的情況分析： 高3位：001=1通過OSMapTbl映射后，OSRdyGrp=0000 0010，即是就緒表中第1行有任務就緒， 低3位：011=3，通過OSMapTbl映射后

//低三位的映射
OSMapTbl[prio&0x07] = OSMapTbl[3] = 0000 1000;
OSRdyTbl[prio>>3] = OSRdyTbl[1] = 0000 1000;

通過這句代碼就往就緒表第一行（從OSRdyTbl[1]看到）第3個位置（從右往左看0000 1000，第一個為1的位，0開始）寫入1，表明該任務就緒了，

這樣就完成了單個任務優先級的標定，

多任務優先級設定 這里引入一個表格：優先級判定表OSUnMapTbl[]，這個表的作用是為了節省時間，這樣查表的話，耗的時間是一定的，很好的滿足了實時性，下面來分析這個表的作用， 1.先看最旁邊的注釋，說明的是該陣列中對應的位置， 2.解釋這個陣列中內容，這些數字怎么來的，

舉例：0x53 如上圖所示的位置，為什么是0呢？我們把0x53變成二進制來看： 0101 0011，從右往左看，第一個出現1的位，就是0位所以為0. 為什么是從右往左看呢？因為高優先級的數字低，你應該懂的，

例子 ： 有4個任務 ，優先級分別為6，10，11，17.，把上面就緒任務演算法再貼一遍：前面2位不管，

6對應二進制：000 110   
高3位：000=0 通過OSMapTbl映射后， 
OSMapTbl[prio>>3]= OSMapTbl[0]=0000 0001
低3位：110=6，通過OSMapTbl映射后 
OSMapTbl[6]=0100 0000
OSRdyTbl[prio>>3]= OSRdyTbl[0]=0100 0000  

10對應二進制：001 010   
高3位：001=1 通過OSMapTbl映射后， 
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010. 
低3位：010=2，通過OSMapTbl映射后 
OSMapTbl[2]=0000 0100
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 0100 

11對應二進制：001 011   
高3位：001=1 通過OSMapTbl映射后， 
OSMapTbl[prio>>3]= OSMapTbl[1]=0000 0010. 
低3位：011=3，通過OSMapTbl映射后 
OSMapTbl[3]=0000 1000
OSRdyTbl[prio>>3]= OSRdyTbl[1]=0000 1000  

17對應二進制：010 001   
高3位：010=2 通過OSMapTbl映射后， 
OSMapTbl[prio>>3]= OSMapTbl[2]=0000 0100. 
低3位：001=1，通過OSMapTbl映射后 
OSMapTbl[1]=0000 0010
OSRdyTbl[prio>>3]= OSRdyTbl[2]=0000 0010 

通過就緒任務演算法：

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

最終OSRdyGrp的值就是將所有的OSMapTbl[prio>>3]進行位或運算：

OSRdyGrp=
 000 00001
|0000 0010
|0000 0010
|0000 0100
=0000 0111 = 0x07 

OSRdyTbl[0]=0100 0000 
OSRdyTbl[1]=
 0000 0100
|0000 1000
=0000 1100（相同的列進行位或運算）

OSRdyTbl[2]=0000 0010  

然后查找優先級判定表OSUnMapTbl[]

OSRdyGrp=0x07 
Y=OSUnMapTbl[0x07]=0

說明是最高優先級在第0組，

OSRdyTbl[0]=0100 0000=0x40
X = OSUnMapTbl[0x40]=6

最高優先級為:prio= y*8+x=6

至此，最高優先級就選出來了，然后調度此任務運行就是了，另外，洗掉任務就是將對應就緒串列位的置的1清零就是，

if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0) 
 OSRdyGrp &= ~OSMapTbl[prio >> 3];  

看到這里，這行代碼理解應該沒有問題，就是反操作而已，