為了保證系統(tǒng)的實(shí)時(shí)性，在就緒表這一塊，內(nèi)核設(shè)計(jì)者設(shè)計(jì)了一種算法，這個(gè)算法在O(1)的時(shí)間里完成查找就緒表中最高優(yōu)先級(jí)的任務(wù)（遍歷就緒表來查找最高優(yōu)先級(jí)的做法是不能保證實(shí)時(shí)性要求的）。關(guān)于就緒表，這里涉及到四個(gè)數(shù)據(jù)結(jié)構(gòu)，分別是：OSRdyGrp、OSRdyTbl[]、OSMapTbl[]和OSUnMapTbl[]。前兩者是全局變量（INT8U），OSRdyTbl[]數(shù)組的大小取決于OS_LOWEST_PRIO。后面兩個(gè)數(shù)組是靜態(tài)成員，其值見下面的表格和代碼：
INT8U const OSUnMapTbl[] = {
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
};
先把就緒表的結(jié)構(gòu)圖貼出來看看：
至于這個(gè)就緒表是怎么構(gòu)成的，為什么是8x8表格，這里就不浪費(fèi)寶貴的網(wǎng)絡(luò)資源了，任何一本書上都說得我比清楚。
這里主要是說明一下OSMapTbl[]和OSUnMapTbl[]這兩個(gè)數(shù)組的值是怎么得來的，以及對(duì)進(jìn)入、脫離就緒態(tài)代碼和找出最高優(yōu)先級(jí)任務(wù)代碼的理解。
一、OSMapTbl[]數(shù)組。
這個(gè)數(shù)組出現(xiàn)的目的是為了更方便的置位。說白點(diǎn)，使用OSMapTbl[index]的作用是更方便的把某個(gè)數(shù)值的第index位置1。比如：使任務(wù)進(jìn)入就緒態(tài)的代碼是：
OSRdyGrp |= OSMapTbl[prio>>3]; （1）
OSRdyTbl[prio>>3] |= OSMapTbl[prio&0x07]; （2）
先取prio（任務(wù)優(yōu)先級(jí)）的“高三位”（這里的高三位是指不考慮prio的最高兩位，剩下的六位中的高三位），“高三位”是OSRdyGrp的索引，就是說：“高三位”的值（0到7）指定OSRdyGrp（8位）中某一位置位，比如，“高三位”是111，即7，這樣就把OSRdyGrp的第7位置1。再看代碼（1），先通過prio>>3確定OSRdyGrp的哪一位應(yīng)該置1（比如第7位），然后通過OSMapTbl[]表把這一位置1，其他位為0（比如OSMapTbl[7]=10000000），再通過位或操作就可以把OSRdyGrp的相應(yīng)位（第7位）置1了。代碼（2）是同樣的道理。這里就說明了OSMapTbl[]數(shù)組的用處了。
使任務(wù)脫離就緒態(tài)要對(duì)某些位進(jìn)行清0操作，這里也要用到OSMapTbl[]數(shù)組，原理是一樣的。代碼如下：
- if ((OSRdyTbl[prio >> 3] &= ~OSMapTbl[prio & 0x07]) == 0)
- OSRdyGrp &= ~OSMapTbl[prio >> 3];
第一行先對(duì)OSRdyTbl[]中某數(shù)據(jù)的某一位清0，然后進(jìn)行判斷，如果OSRdyTbl[]中這個(gè)數(shù)據(jù)為0（也主相當(dāng)于這個(gè)數(shù)據(jù)的所有8位都已經(jīng)清0了），再對(duì)OSRdyGrp的某位清0。
二、OSUnMapTbl[]數(shù)組
OSUnMapTbl[]數(shù)組主要是用于找出進(jìn)入就緒態(tài)的優(yōu)先級(jí)最高的任務(wù)。而這個(gè)地方也是我一開始沒搞明白的，不明白OSUnMapTbl[]中的數(shù)值是怎么來的。
先脫離所有上下文關(guān)系來說說OSUnMapTbl[]的一般意義。這里用二進(jìn)制比較方便說明問題。OSUnMapTbl[]共0xFF個(gè)元素，0x00~0xFF為索引，而OSUnMapTbl[]里的值就是通過分析索引得到的。比如說，索引0x50, 二進(jìn)制表示為0101 0000,然后從右邊數(shù)，看第幾位首先為1，則OSUnMapTbl[0x50]的值就為幾。易知，0101 0000從右起，第4位首先為1，所以有OSUnMapTbl[0x50]=4。再比如0x51，二進(jìn)制為0101 0001，右起第0位為1，所以O(shè)SUnMapTbl[0x51]=0。
那為什么要從右數(shù)起呢？這個(gè)和優(yōu)先級(jí)表有關(guān)系，優(yōu)先級(jí)的值越小，優(yōu)先級(jí)就越高。再看上面那幅優(yōu)先級(jí)的結(jié)構(gòu)圖，可見，優(yōu)先級(jí)是從右至左，從上至下越來越低的，最低優(yōu)先級(jí)給了空閑任務(wù)。
結(jié)合代碼分析一下：
- y = OSUnMapTbl[OSRdyGrp];
- x = OSUnMapTbl[OSRdyTbl[y]];
- prio = (y << 3) + x;
x、y的含義看上面的圖就知道了：y是“高三位”，x是“低三位”。
找最高優(yōu)先級(jí)任務(wù)的過程是這樣的：首先，查OSRdyGrp，看OSRdyGrp中右起的第幾位首先為1，比如OSRdyGrp=0x56，0x56的二進(jìn)制為0101 0110,可見右起第1位首先為1，所以y=OSUnMapTbl[0x56]=1，然后再去OSRdyTbl[y]即OSRdyTbl[1]中查找（為什么是OSRdyTbl[y]，這個(gè)書上說得很明確，這個(gè)得清楚得了解OSRdyGrp和OSRdyTbl[]之間的關(guān)系），這里假設(shè)OSRdyTbl[1]=0xD4，即1101 0100，同樣找到OSRdyTbl[1]中右起的第2位首先為1，這樣得到x=2，再通過第3行的移位運(yùn)算就可以得到最高優(yōu)先級(jí)的任務(wù)的優(yōu)先級(jí)了。
|
