嵌入式實時作業系統5——就緒表

就緒表作用

作業系統內核會將就緒的任務存放在就緒表，內核總是從就緒表中找出最高優先級任務，并執行該任務，
內核調度任務時只用關注就緒表，從就緒表中最高優先級項中選擇任務并執行，

就緒表是存放就緒任務的串列，就緒表通常有兩個專案：優先級，任務成員，同一個優先級的任務放在就緒表中的同一個優先級串列項中,就緒表框架如下：

構建就緒表
使用靜態陣列的方式可以構建一個就緒表，代碼實作如下：

其中tcb_item_t為 TCB項 ，list_item_t串列項，ready_list為就緒表，
就緒表中包含了10個串列，每個串列對應一個優先級，ready_list[0]表示優先級0的任務串列，ready_list[9]表示優先級9的任務串列，
ready_list中的每個串列包含10個TCB項，itme[0]表示該優先級下的任務0，itme[9]表示該優先級下的任務9，
每個TCB項中包含一個標志位和TCB指標，TCB指標指向任務的TCB資料結構，資料結構圖如下：

使用靜態陣列方式的優點是：結構簡單，使用方便，但是使用靜態陣列的缺點非常明顯：
1、每個一優先級容納的任務數量是固定的，一旦需要增加某個優先級任務數量，整個串列大小將增加，
2、在同一個優先級任務中間插入一個任務，需要移動多個TCB項，
3、存在多個優先級未用的情況，導致記憶體浪費嚴重，
綜合上述問題，因此使用靜態陣列的方式是不明智的選擇，
但是這種資料結構能讓我們認清就就緒表的本質：就緒表分為多個優先級，就緒表的每個優先級可以容納多個任務，

構建就緒表可以使用雙向鏈表的方式，代碼實作如下：

list_item_t串列項，ready_list為就緒表，
就緒表中包含了10個串列，每個串列對應一個優先級，ready_list[0]表示優先級0的任務串列，ready_list[9]表示優先級9的任務串列，
每個list_item_t串列中包含一個TCB指標，下一個串列項指標和上一個串列項指標，資料結構圖如下：

使用雙向鏈表的方式有以下優點：
1、每一個鏈表可以連接任意數量的鏈表項，長度不受限制，
2、鏈表的每一項，都是有用項，不存在記憶體浪費
3、在鏈表中間插入一項，操作效率較高，
使用雙向鏈表構建就緒表是很好的選擇，

就緒表原始碼分析
接下來我們一起來分析FreeRTOS就緒表的原始碼，原始碼如下：

根據原始碼可知：FreeRTOS就緒表由鏈表組成，
pxReadyTasksLists為就緒表，就緒表中包含10個串列，pxReadyTasksLists[0]表示優先級0的任務串列，pxReadyTasksListst[9]表示優先級9的任務串列，
每個串列包含一個xListEnd項，xListEnd中包含下一個串列項指標和上一個串列項指標，

FreeRTOS中的TCB結構，根據原始碼可知TCB內部有名為xStateListItem的串列項（ListItem_t），就緒表中的串列項xListEnd指標指向TCB結構中的串列項，

FreeRTOS的就緒表和任務TCB關系框圖如下：

就緒表操作
作業系統內核總是選擇最高優先級的任務運行，相同優先級的任務輪流運行，
針對這種調度原則，內核只需要從就緒表中找出最高優先級任務串列pxReadyTasksLists[n]，運行該串列中第一個串列項指向的任務，任務運行完畢后內核將任務插入串列的尾部，然后內核再運行該任務串列中第一個串列項指向的任務，從而實作輪流運行，新任務加入就緒表時，總是插入到對應優先級串列的尾部，
根據應用要求，內核還可以移除串列中任意位置的串列項，

內核操作就緒表有三個基本操作：
1、頭部取出，內核總是從最高優先級串列中取出第一個串列項任務運行，
2、尾部插入，任務運行完畢或者新任務加入就緒表時，總是插入到對應優先級串列的尾部，
3、任意位置移除，內核可以移除串列中任意位置的串列項，

FreeRTOS的就緒表操作原始碼：

prvAddTaskToReadyList 的功能是將任務加入就緒表， vListInsertEnd 的功能是將任務插入串列尾部，

taskSELECT_HIGHEST_PRIORITY_TASK的功能是選擇最高優先級任務，listGET_OWNER_OF_NEXT_ENTRY 的功能是從該優先級串列中取出第一個串列項，

uxListRemove的功能是在串列中移除指定的一個串列項，

就緒表更新
上一節描述了內核操作就緒表的三個基本操作：頭部取出，尾部插入，任意位置移除，那么哪些位置會對就緒表進行操作？作業系統會在如下位置更新就緒表（參考FreeRTOS）：

xTaskCreate
xTaskCreate的作用是創建一個任務，該系統函式的呼叫流程如下：
xTaskCreate -> prvAddNewTaskToReadyList -> prvAddTaskToReadyList -> vListInsertEnd
就緒表變化：任務插入到就緒表對應優先級串列的尾部，

vTaskDelete
vTaskDelete的作用是洗掉一個任務，該系統函式的呼叫流程如下：
vTaskDelete -> uxListRemove
就緒表變化：任務從就緒表對應優先級串列中移除

vTaskSuspend
vTaskSuspend的作用是暫停一個任務，該系統函式的呼叫流程如下：
vTaskSuspend -> uxListRemove
就緒表變化：任務從對應優先級串列中移除

vTaskResume
vTaskResume的作用是恢復一個任務，該系統函式的呼叫流程如下：
vTaskResume -> prvAddTaskToReadyList -> vListInsertEnd
就緒表變化：任務插入到就緒表中對應優先級串列的尾部，

vTaskPrioritySet
vTaskPrioritySet的作用是改變一個任務優先級，該系統函式的呼叫流程如下：
vTaskPrioritySet ->uxListRemove -> prvAddTaskToReadyList -> vListInsertEnd
就緒表變化：任務從就緒表中的當前優先級串列中移除，并將任務插入到設定的優先級串列的尾部，

vTaskDelay
vTaskDelay的作用是將當前任務從就緒表中移動到等待表中，該系統函式的呼叫流程如下：
vTaskDelay -> uxListRemove -> vListInsert
就緒表變化：任務從就緒表中移除，并將任務插入到等待表中，

xQueueSemaphoreTake
xQueueSemaphoreTake的作用是當前任務等待一個信號，該系統函式的呼叫流程如下：
xQueueSemaphoreTake -> vListInsert -> prvAddCurrentTaskToDelayedList -> uxListRemove -> vListInsert
就緒表變化：將當前任務插入到掛起中，并當前任務從就緒表中移除，最后將當前任務插入等待表中，

xQueueGenericSend
xQueueSemaphoreTake的作用是發生一個信號，該系統函式的呼叫流程如下：
xQueueGenericSend -> xTaskRemoveFromEventList-> uxListRemove -> prvAddTaskToReadyList -> vListInsertEnd
就緒表變化：將移除掛起表中的第一個任務，并該任務插入到就緒表中中對應優先級串列的尾部，

就緒表框圖

TCB設計

增加任務的TCB結構：

TCB中包含了：
1、堆疊指標，
2、任務狀態串列，
3、任務事件串列，
4、優先級，
5、堆疊起始地址
6、任務名

TCB結構，暫存器堆和任務堆疊的關系圖如下：

靜態區定義的任務TCB物件中的堆疊指標指向任務堆疊區的堆疊頂，任務堆疊區保存著暫存器堆的資料，暫存器堆中的PC值指向任務的代碼區，任務狀態串列和任務事件串列與就緒表，等待表和掛起表關聯，

未完待續…
實時作業系統系列將持續更新
創作不易希望朋友們點贊，轉發，評論，關注，
您的點贊，轉發，評論，關注將是我持續更新的動力
作者：李巍
Github：liyinuoman2017