從本章開始，我們在 OS 中加入時基清單，時基清單是跟時間相關的， 處于延時的任務和等待事件有逾時限制的任務都會從就緒清單中移除，然後插入到時基清單。 時基清單在 OSTimeTick 中更新，如果任務的延時時間結束或者逾時到期，就會讓任務就緒，從時基清單除，插入到就緒清單。 到目前為止，我們在 OS 中隻實作了兩個清單，一個是就緒清單，一個是本章将要實作的時基清單，在本章之前，任務要麼在就緒清單，要麼在時基清單。
12.1 實作時基清單：
12.1.1 定義時基清單變量：
時基清單在代碼層面上由全局數組 OSCfg_TickWheel[]和全局變量 OSTickCtr 構成， 一個空的時基清單示意圖見圖 12-1，時基清單的代碼實作具體見代碼清單 12-1。
代碼清單 12-1 時基清單定義
/* 時基清單大小，在 os_cfg_app.h 定義 */
#define OS_CFG_TICK_WHEEL_SIZE 17u
/* 在 os_cfg_app.c 定義 */
/* 時基清單 */
(1) (2)
OS_TICK_SPOKE OSCfg_TickWheel[OS_CFG_TICK_WHEEL_SIZE];
/* 時基清單大小 */
OS_OBJ_QTY const OSCfg_TickWheelSize = (OS_OBJ_QTY )OS_CFG_TICK_WHEEL_SIZE;
/* 在 os.h 中聲明 */
/* 時基清單 */
extern OS_TICK_SPOKE OSCfg_TickWheel[];
/* 時基清單大小 */
extern OS_OBJ_QTY const OSCfg_TickWheelSize;
/* Tick 計數器，在 os.h 中定義 */
OS_EXT OS_TICK OSTickCtr; (3) 代碼清單 12-1 （1）： OS_TICK_SPOKE 為時基清單數組 OSCfg_TickWheel[]的資料類型，在 os.h 檔案定義，具體見代碼清單 12-2。
代碼清單 12-2 OS_TICK_SPOKE 定義
typedef struct os_tick_spoke OS_TICK_SPOKE; (1)
struct os_tick_spoke {
OS_TCB *FirstPtr; (2)
OS_OBJ_QTY NbrEntries; (3)
OS_OBJ_QTY NbrEntriesMax; (4)
}; 代碼清單 12-2（1）： 在 uC/OS-III 中，核心對象的資料類型都會用大寫字母重新定義。
代碼清單 12-2（2）： 時基清單 OSCfg_TickWheel[]的每個成員都包含一條單向連結清單，被插入到該條連結清單的 TCB 會按照延時時間做升序排列。 FirstPtr 用于指向這條單向連結清單的第一個節點。
代碼清單 12-2（3）： 時基清單 OSCfg_TickWheel[]的每個成員都包含一條單向連結清單，NbrEntries 表示該條單向連結清單目前有多少個節點。
代碼清單 12-2（4）： 時基清單 OSCfg_TickWheel[]的每個成員都包含一條單向連結清單，NbrEntriesMax 記錄該條單向連結清單最多的時候有多少個節點，在增加節點的時候會重新整理，在删除節點的時候不重新整理。
代碼清單 12-1（2）： OS_CFG_TICK_WHEEL_SIZE 是一個宏，在 os_cfg_app.h 中定義，用于控制時基清單的大小。 OS_CFG_TICK_WHEEL_SIZE 的推薦值為任務數/4，不推薦使用偶數，如果算出來是偶數，則加 1 變成質數，實際上質數是一個很好的選擇。
代碼清單 12-1（3）： OSTickCtr 為 SysTick 周期計數器，記錄系統啟動到現在或者從上一次複位到現在經過了多少個 SysTick 周期。
12.1.2 修改任務控制塊 TCB
時基清單 OSCfg_TickWheel[]的每個成員都包含一條單向連結清單，被插入到該條連結清單的TCB 會按照延時時間做升序排列，為了 TCB 能按照延時時間從小到大串接在一起，需要在TCB 中加入幾個成員，具體見代碼清單 12-3 的加粗部分。
代碼清單 12-3 在 TCB 中加入時基清單相關字段
struct os_tcb {
CPU_STK *StkPtr;
CPU_STK_SIZE StkSize;
/* 任務延時周期個數 */
OS_TICK TaskDelayTicks;
/* 任務優先級 */
OS_PRIO Prio;
/* 就緒清單雙向連結清單的下一個指針 */
OS_TCB *NextPtr;
/* 就緒清單雙向連結清單的前一個指針 */
OS_TCB *PrevPtr;
/*時基清單相關字段*/
OS_TCB *TickNextPtr; (1)
OS_TCB *TickPrevPtr; (2)
OS_TICK_SPOKE *TickSpokePtr; (5)
OS_TICK TickCtrMatch; (4)
OS_TICK TickRemain; (3)
}; 代碼清單 12-3 加粗部分的字段可以配合圖 12-2 一起了解，這樣會比較容易。 圖 12-2是在時基清單 OSCfg_TickWheel[]索引 11 這條連結清單裡面插入了兩個 TCB，一個需要延時 1個時鐘周期，另外一個需要延時 13 個時鐘周期。
代碼清單 12-3（1）： TickNextPtr 用于指向連結清單中的下一個 TCB 節點。
代碼清單 12-3（2）： TickPrevPtr 用于指向連結清單中的上一個 TCB 節點。
代碼清單 12-3（3）： TickRemain 用于設定任務還需要等待多少個時鐘周期，每到來一個時鐘周期，該值會遞減。
代碼清單 12-3（4）： TickCtrMatch 的值等于時基計數器 OSTickCtr 的值加上TickRemain 的值，當 TickCtrMatch 的值等于 OSTickCtr 的值的時候，表示等待到期， TCB會從連結清單中删除。
代碼清單 12-3（5）： 每個被插入到連結清單的 TCB 都包含一個字段 TickSpokePtr，用于回指到連結清單的根部。
12.1.3 實作時基清單相關函數：
時基清單相關函數在 os_tick.c 實作，在 os.h 中聲明。如果 os_tick.c 檔案是第一次使用，需要自行在檔案夾 uCOS-III\Source 中建立并添加到工程的 uC/OS-III Source 組。
1. OS_TickListInit()函數
OS_TickListInit()函數用于初始化時基清單，即将全局變量 OSCfg_TickWheel[]的資料域全部初始化為 0，一個初始化為 0 的的時基清單見圖 12-3。
代碼清單 12-4 OS_TickListInit()函數
/* 初始化時基清單的資料域 */
void OS_TickListInit (void)
{
OS_TICK_SPOKE_IX i;
OS_TICK_SPOKE *p_spoke;
for (i = 0u; i < OSCfg_TickWheelSize; i++) {
p_spoke = (OS_TICK_SPOKE *)&OSCfg_TickWheel[i];
p_spoke->FirstPtr = (OS_TCB *)0;
p_spoke->NbrEntries = (OS_OBJ_QTY )0u;
p_spoke->NbrEntriesMax = (OS_OBJ_QTY )0u;
}
} 2. OS_TickListInsert()函數
OS_TickListInsert()函數用于往時基清單中插入一個任務 TCB，具體實作見代碼清單12-5。 代碼清單 12-5 可配和圖 12-4 一起閱讀，這樣了解起來會容易很多。
代碼清單 12-5 OS_TickListInsert()函數
/* 将一個任務插入到時基清單，根據延時時間的大小升序排列 */
void OS_TickListInsert (OS_TCB *p_tcb,OS_TICK time)
{
OS_TICK_SPOKE_IX spoke;
OS_TICK_SPOKE *p_spoke;
OS_TCB *p_tcb0;
OS_TCB *p_tcb1;
p_tcb->TickCtrMatch = OSTickCtr + time; (1)
p_tcb->TickRemain = time; (2)
spoke = (OS_TICK_SPOKE_IX)(p_tcb->TickCtrMatch % OSCfg_TickWheelSize); (3)
p_spoke = &OSCfg_TickWheel[spoke]; (4)
/* 插入到 OSCfg_TickWheel[spoke] 的第一個節點 */
if (p_spoke->NbrEntries == (OS_OBJ_QTY)0u) { (5)
p_tcb->TickNextPtr = (OS_TCB *)0;
p_tcb->TickPrevPtr = (OS_TCB *)0;
p_spoke->FirstPtr = p_tcb;
p_spoke->NbrEntries = (OS_OBJ_QTY)1u;
}
/* 如果插入的不是第一個節點，則按照 TickRemain 大小升序排列 */
else { (6)
/* 擷取第一個節點指針 */
p_tcb1 = p_spoke->FirstPtr;
while (p_tcb1 != (OS_TCB *)0) {
/* 計算比較節點的剩餘時間 */
p_tcb1->TickRemain = p_tcb1->TickCtrMatch - OSTickCtr;
/* 插入到比較節點的後面 */
if (p_tcb->TickRemain > p_tcb1->TickRemain) {
if (p_tcb1->TickNextPtr != (OS_TCB *)0) {
/* 尋找下一個比較節點 */
p_tcb1 = p_tcb1->TickNextPtr;
} else { /* 在最後一個節點插入 */
p_tcb->TickNextPtr = (OS_TCB *)0;
p_tcb->TickPrevPtr = p_tcb1;
p_tcb1->TickNextPtr = p_tcb;
p_tcb1 = (OS_TCB *)0; (7)
}
}
/* 插入到比較節點的前面 */
else {
/* 在第一個節點插入 */
if (p_tcb1->TickPrevPtr == (OS_TCB *)0) {
p_tcb->TickPrevPtr = (OS_TCB *)0;
p_tcb->TickNextPtr = p_tcb1;
p_tcb1->TickPrevPtr = p_tcb;
p_spoke->FirstPtr = p_tcb;
} else {
/* 插入到兩個節點之間 */
p_tcb0 = p_tcb1->TickPrevPtr;
p_tcb->TickPrevPtr = p_tcb0;
p_tcb->TickNextPtr = p_tcb1;
p_tcb0->TickNextPtr = p_tcb;
p_tcb1->TickPrevPtr = p_tcb;
}
/* 跳出 while 循環 */
p_tcb1 = (OS_TCB *)0; (8)
}
}
/* 節點成功插入 */
p_spoke->NbrEntries++; (9)
}
/* 重新整理 NbrEntriesMax 的值 */
if (p_spoke->NbrEntriesMax < p_spoke->NbrEntries) { (10)
p_spoke->NbrEntriesMax = p_spoke->NbrEntries;
}
/* 任務 TCB 中的 TickSpokePtr 回指根節點 */
p_tcb->TickSpokePtr = p_spoke; (11)
} 代碼清單 12-5（1）： TickCtrMatch 的值等于目前時基計數器的值 OSTickCtr 加上任務要延時的時間 time， time 由函數形參傳進來。 OSTickCtr 是一個全局變量，記錄的是系統自啟動以來或者自上次複位以來經過了多少個 SysTick 周期。 OSTickCtr 的值每經過一個SysTick 周期其值就加一，當 TickCtrMatch 的值與其相等時，就表示任務等待時間到期。
代碼清單 12-5（2）： 将任務需要延時的時間 time 儲存到 TCB 的 TickRemain，它表示任務還需要延時多少個 SysTick 周期，每到來一個 SysTick 周期， TickRemain 會減一。
代碼清單 12-5（3）： 由任務的 TickCtrMatch 對時基清單的大小 OSCfg_TickWheelSize進行求餘操作，得出的值 spoke 作為 時基清單 OSCfg_TickWheel[]的索引。 隻要是任務的TickCtrMatch 對 OSCfg_TickWheelSize 求餘後得到的值 spoke 相等，那麼任務的 TCB 就會被插入到 OSCfg_TickWheel[spoke]下的單向連結清單中，節點按照任務的 TickCtrMatch 值做升序排列。 舉例：在圖 12-4 中，時基清單 OSCfg_TickWheel[]的大小 OSCfg_TickWheelSize等于 12，目前時基計數器 OSTickCtr 的值為 10，有三個任務分别需要延時 TickTemain=1、TickTemain=23 和 TickTemain=25 個時鐘周期，三個任務的 TickRemain 加上 OSTickCtr 可分别得出它們的 TickCtrMatch 等于 11、 23 和 35，這三個任務的 TickCtrMatch 對OSCfg_TickWheelSize 求餘操作後的值 spoke 都等于 11，是以這三個任務的 TCB 會被插入到 OSCfg_TickWheel[11]下的同一條連結清單，節點順序根據 TickCtrMatch 的值做升序排列。
代碼清單 12-5（4）： 根據剛剛算出的索引值 spoke，擷取到該索引值下的成員的位址，也叫根指針，因為該索引下對應的成員OSCfg_TickWheel[spoke]會維護一條雙向的連結清單。
代碼清單 12-5（5）： 将 TCB 插入到連結清單中分兩種情況，第一是目前連結清單是空的，插入的節點将成為第一個節點，這個處理非常簡單；第二是目前連結清單已經有節點。
代碼清單 12-5（6）：目前的連結清單中已經有節點，插入的時候則根據 TickCtrMatch 的值做升序排列，插入的時候分三種情況，第一是在最後一個節點之間插入，第二是在第一個節點插入，第三是在兩個節點之間插入。
代碼清單 12-5（7） （8） ：節點成功插入 p_tcb1 指針，跳出 while 循環
代碼清單 12-5（9）：節點成功插入，記錄目前連結清單節點個數的計數器 NbrEntries 加一。
代碼清單 12-5（10）：重新整理 NbrEntriesMax 的值, NbrEntriesMax 用于記錄目前連結清單曾經最多有多少個節點，隻有在增加節點的時候才重新整理，在删除節點的時候是不重新整理的。代碼清單 12-5（11）：任務 TCB 被成功插入到連結清單， TCB 中的 TickSpokePtr 回指所
在連結清單的根指針。
3. OS_TickListRemove()函數
OS_TickListRemove()用于從時基清單删除一個指定的 TCB 節點，具體實作見。 代碼清單 12-6
代碼清單 12-6 OS_TickListRemove()函數
/* 從時基清單中移除一個任務 */
void OS_TickListRemove (OS_TCB *p_tcb)
{
OS_TICK_SPOKE *p_spoke;
OS_TCB *p_tcb1;
OS_TCB *p_tcb2;
/* 擷取任務 TCB 所在連結清單的根指針 */
p_spoke = p_tcb->TickSpokePtr; (1)
/* 確定任務在連結清單中 */
if (p_spoke != (OS_TICK_SPOKE *)0) {
/* 将剩餘時間清 0 */
p_tcb->TickRemain = (OS_TICK)0u;
/* 要移除的剛好是第一個節點 */
if (p_spoke->FirstPtr == p_tcb) { (2)
/* 更新第一個節點，原來的第一個節點需要被移除 */
p_tcb1 = (OS_TCB *)p_tcb->TickNextPtr;
p_spoke->FirstPtr = p_tcb1;
if (p_tcb1 != (OS_TCB *)0) {
p_tcb1->TickPrevPtr = (OS_TCB *)0;
}
}
/* 要移除的不是第一個節點 */ (3)
else {
/* 儲存要移除的節點的前後節點的指針 */
p_tcb1 = p_tcb->TickPrevPtr;
p_tcb2 = p_tcb->TickNextPtr;
/* 節點移除，将節點前後的兩個節點連接配接在一起 */
p_tcb1->TickNextPtr = p_tcb2;
if (p_tcb2 != (OS_TCB *)0) {
p_tcb2->TickPrevPtr = p_tcb1;
}
}
/* 複位任務 TCB 中時基清單相關的字段成員 */ (4)
p_tcb->TickNextPtr = (OS_TCB *)0;
p_tcb->TickPrevPtr = (OS_TCB *)0;
p_tcb->TickSpokePtr = (OS_TICK_SPOKE *)0;
p_tcb->TickCtrMatch = (OS_TICK )0u;
/* 節點減 1 */
p_spoke->NbrEntries--; (5)
}
} 代碼清單 12-6（1）： 擷取任務 TCB 所在連結清單的根指針。
代碼清單 12-6（2）： 要删除的節點是連結清單的第一個節點，這個操作很好處理，隻需更新下第一個節點即可。
代碼清單 12-6（3）： 要删除的節點不是連結清單的第一個節點，則先儲存要删除的節點的前後節點，然後把這前後兩個節點相連即可。
代碼清單 12-6（4）： 複位任務 TCB 中時基清單相關的字段成員。
代碼清單 12-6（5）： 節點删除成功，連結清單中的節點計數器 NbrEntries 減一。
4. OS_TickListUpdate()函數
OS_TickListUpdate()在每個 SysTick 周期到來時在 OSTimeTick()被調用，用于更新時基計數器 OSTickCtr，掃描時基清單中的任務延時是否到期，具體實作見代碼清單 12-7。
代碼清單 12-7 OS_TickListUpdate()函數
void OS_TickListUpdate (void)
{
OS_TICK_SPOKE_IX spoke;
OS_TICK_SPOKE *p_spoke;
OS_TCB *p_tcb;
OS_TCB *p_tcb_next;
CPU_BOOLEAN done;
CPU_SR_ALLOC();
/* 進入臨界段 */
OS_CRITICAL_ENTER();
/* 時基計數器++ */
OSTickCtr++; (1)
spoke = (OS_TICK_SPOKE_IX)(OSTickCtr % OSCfg_TickWheelSize); (2)
p_spoke = &OSCfg_TickWheel[spoke];
p_tcb = p_spoke->FirstPtr;
done = DEF_FALSE;
while (done == DEF_FALSE) {
if (p_tcb != (OS_TCB *)0) { (3)
p_tcb_next = p_tcb->TickNextPtr;
p_tcb->TickRemain = p_tcb->TickCtrMatch - OSTickCtr; (4)
/* 節點延時時間到 */
if (OSTickCtr == p_tcb->TickCtrMatch) { (5)
/* 讓任務就緒 */
OS_TaskRdy(p_tcb);
} else { (6)
/* 如果第一個節點延時期未滿，則退出 while 循環
因為連結清單是根據升序排列的，第一個節點延時期未滿，那後面的肯定未滿
done = DEF_TRUE;
}
/* 如果第一個節點延時期滿，則繼續周遊連結清單，看看還有沒有延時期滿的任務
如果有，則讓它就緒 */
p_tcb = p_tcb_next; (7)
} else {
done = DEF_TRUE; (8)
}
}
/* 退出臨界段 */
OS_CRITICAL_EXIT();
} 代碼清單 12-7（1）： 每到來一個 SysTick 時鐘周期， 時基計數器 OSTickCtr 都要加一操作。
代碼清單 12-7（2）： 計算要掃描的時基清單的索引，每次隻掃描一條連結清單。 時基清單裡面有可能有多條連結清單，為啥隻掃描其中一條連結清單就可以？因為任務在插入到時基清單的時候，插入的索引值 spoke_insert 是通過 TickCtrMatch 對 OSCfg_TickWheelSize 求餘得出，現在需要掃描的索引值 spoke_update 是通過 OSTickCtr 對 OSCfg_TickWheelSize 求餘得出，TickCtrMatch 的值等于 OSTickCt 加上 TickRemain， 隻有在經過 TickRemain 個時鐘周期後，spoke_update 的值才有可能等于 spoke_insert。如果算出的 spoke_update 小于 spoke_insert，且 OSCfg_TickWheel[spoke_update]下的連結清單的任務沒有到期，那後面的肯定都沒有到期，不用繼續掃描。
舉例，在圖 12-5， 時基清單 OSCfg_TickWheel[]的大小 OSCfg_TickWheelSize 等于 12，目前時基計數器 OSTickCtr 的值為 7，有三個任務分别需要延時 TickTemain=16、TickTemain=28 和 TickTemain=40 個時鐘周期，三個任務的 TickRemain 加上 OSTickCtr 可分别得出它們的 TickCtrMatch 等于 23、 35 和 47，這三個任務的 TickCtrMatch 對OSCfg_TickWheelSize 求餘操作後的值 spoke 都等于 11，是以這三個任務的 TCB 會被插入到 OSCfg_TickWheel[11]下的同一條連結清單，節點順序根據 TickCtrMatch 的值做升序排列。當下一個 SysTick 時鐘周期到來的時候，會調用 OS_TickListUpdate()函數，這時 OSTickCtr加一操作後等于 8，對 OSCfg_TickWheelSize（等于 12）求餘算得要掃描更新的索引值spoke_update 等 8， 則對 OSCfg_TickWheel[8]下面的連結清單進行掃描，從圖 12-5 可以得知， 8這個索引下沒有節點，則直接退出，剛剛插入的三個 TCB 是在 OSCfg_TickWheel[11]下的連結清單，根本不用掃描，因為時間隻是剛剛過了 1 個時鐘周期而已，遠遠沒有達到他們需要的延時時間。
代碼清單 12-7（3）： 判斷連結清單是否為空，為空則跳轉到第（8）步驟。
代碼清單 12-7（4）： 連結清單不為空，遞減第一個節點的 TickRemain。
代碼清單 12-7（5）： 判斷第一個節點的延時時間是否到，如果到期，讓任務就緒，即将任務從時基清單删除，插入就緒清單，這兩步由函數 OS_TaskRdy()來完成，該函數在os_core.c 中定義，具體實作見代碼清單 12-8。
代碼清單 12-8 OS_TaskRdy()函數
void OS_TaskRdy (OS_TCB *p_tcb)
{
/* 從時基清單删除 */
OS_TickListRemove(p_tcb);
/* 插入就緒清單 */
OS_RdyListInsert(p_tcb);
} 代碼清單 12-7（6）： 如果第一個節點延時期未滿，則退出 while 循環， 因為連結清單是根據升序排列的，第一個節點延時期未滿，那後面的肯定未滿。
代碼清單 12-7（7）： 如果第一個節點延時到期，則繼續判斷下一個節點延時是否到期 。
代碼清單 12-7（8）： 連結清單為空，退出掃描，因為其它還沒到期。
12.2 修改 OSTimeDly()函數:
加入時基清單之後， OSTimeDly()函數需要被修改，具體見代碼清單 12-9 的加粗部分，被疊代的代碼已經用條件編譯屏蔽。
代碼清單 12-9 OSTimeDly()函數
void OSTimeDly(OS_TICK dly)
{
CPU_SR_ALLOC();
/* 進入臨界區 */
OS_CRITICAL_ENTER();
#if 0
/* 設定延時時間 */
OSTCBCurPtr->TaskDelayTicks = dly;
/* 從就緒清單中移除 */
//OS_RdyListRemove(OSTCBCurPtr);
OS_PrioRemove(OSTCBCurPtr->Prio);
#endif
/* 插入到時基清單 */
OS_TickListInsert(OSTCBCurPtr, dly);
/* 從就緒清單移除 */
OS_RdyListRemove(OSTCBCurPtr);
/* 退出臨界區 */
OS_CRITICAL_EXIT();
/* 任務排程 */
OSSched();
} 12.3 修改 OSTimeTick()函數:
void OSTimeTick (void)
{
#if 0
unsigned int i;
CPU_SR_ALLOC();
/* 進入臨界區 */
OS_CRITICAL_ENTER();
for (i=0; i<OS_CFG_PRIO_MAX; i++) {
if (OSRdyList[i].HeadPtr->TaskDelayTicks > 0) {
OSRdyList[i].HeadPtr->TaskDelayTicks --;
if (OSRdyList[i].HeadPtr->TaskDelayTicks == 0) {
/* 為 0 則表示延時時間到，讓任務就緒 */
//OS_RdyListInsert (OSRdyList[i].HeadPtr);
OS_PrioInsert(i);
}
}
}
/* 退出臨界區 */
OS_CRITICAL_EXIT();
#endif
/* 更新時基清單 */
OS_TickListUpdate();
/* 任務排程 */
OSSched();
}