嵌入式實時作業系統6——鏈表資料結構

• 鏈表結構的作用

在《RTOS系列5——就緒表》中描述了作業系統內核中的就緒表使用了鏈表結構，就緒表的框圖如下：

在作業系統內核中不僅僅是就緒表使用了鏈表結構，等待表和掛起表也都用到了鏈表結構，
鏈表資料結構有以下優點：

1、在保留原有物理順序的情況下，插入和洗掉速度快，效率高，插入和洗掉只需要改變幾個指標變數，
2、鏈表中的表項數量沒有上限，存盤的表項上限只與記憶體空間大小有關，理論上如果記憶體無限大，鏈表中的表項可以動態增加到無限個，
3、動態分配記憶體，需要用多少個表項，就分配幾個表項，不需要預先分配記憶體，不存在記憶體浪費的情況，

分析：

1、插入和洗掉效率高

如果要在元素“3”之后插入一個“8”，就需要移動元素“3”之后的“14179”5個元素，

使用鏈表結構時，只有改變4個指標的資料既可，如果元素有很多個時，鏈表的這種操作的將會帶來極高的效率，

2、鏈表中的表項數量沒有上限

如果記憶體無限大，鏈表中的表項可以動態增加到無限個，不會出現元素滿的情況，

3、動態分配記憶體

分配記憶體，不需要預先分配記憶體，不存在記憶體浪費的情況，

• 鏈表資料結構

鏈表分為單向鏈表和雙向鏈表，這兩種鏈表的結構如下：

雙向鏈表中的每個物件中包含：關鍵字key和兩個指標：next和prev，next是指向下一個后繼元素的指標，prev是指向上一個前驅元素的指標，data為用戶資料，
單向鏈表中的每個物件中包含：關鍵字key和一個指標：next，next是指向下一個后繼元素的指標，data為用戶資料，
關鍵字key用于查找物件和物件排序，
鏈表有多種形式，它可以是排序的，可以是未排序的，可以是回圈的，可以是非回圈的，
如果鏈表是排序的，鏈表的線性順序和鏈表元素中的關鍵字key的線性順序一致，在回圈串列中，表頭元素的prev指標指向表尾元素，表尾元素的next指標指向表頭元素，
鏈表的基本操作是：
1、查詢一個元素
2、插入一個元素
3、洗掉一個元素
作業系統內核中通常使用的鏈表為雙向回圈鏈表，雙向回圈鏈表的結構如下圖：

• 鏈表實作

鏈表有兩種常見的實作方式：
1、鏈表中包含用戶資料，
2、用戶資料中包含鏈表，
C語言實作如下：

這兩種實作的鏈表的結構框圖如下：

鏈表中包含用戶資料的方式最大的問題是：當用戶資料改變時，整個鏈表結構也會改變，不同的用戶資料需要定義不同的鏈表結構，
用戶資料中包含鏈表的方式可以通用一種鏈表結構，用戶資料可以不同，作業系統內核種通常使用用戶資料中包含鏈表的方式，

• 萬能藥

上文提到用戶資料中包含鏈表的方式可以通用一種鏈表結構，可以適應不同的用戶資料，但是世界上沒有萬能藥，這種鏈表形式同樣存在一個問題：

由于鏈表指標指向的是另外一個鏈表物件，此時我們將無法得到整個資料物件的地址，由上圖可知我們通過next指標可以得到下一個list元素的地址，但是我們無法獲取整個資料物件的地址，
辦法總比困難多！我們有兩種常用的方法解決“無法獲取整個資料物件的地址”的問題：
1、指標法，
2、地址反推法，

指標法
指標法是在鏈表結構種增加一個void * owner指標，用這個指標指向整個資料物件的地址,因為是void * 型別，owner指標可以指向任意型別的物件，C語言代碼實作如下：

這種鏈表的結構框圖如下：

在指標法中，使用鏈表結構中的owner指標可以定位到整個資料物件的地址，在小型的實時作業系統中通常使用這種方式，

地址反推法
地址反推法是已知資料物件的型別和鏈表的地址，可以反推得到資料物件的地址，C語言代碼實作如下：

container_of是可以根據結構體的成員變數獲取所在結構體的首地址，這種方法的原理是：編譯器記錄了每一個結構體型別資料中的每一個元素的偏移地址，現在已知一個結構體型別，和該結構體內的一個元素地址（鏈表元素地址），就能反推出該結構體物件的地址，
linux內核常用這種地址反推法定位資料物件的地址，

• 哨兵

用代碼演示一下向鏈表中插入物件：

以上代碼在一個演示了在一個空鏈表中插入了第一個物件，非空鏈表中插入物件是同樣的操作嗎？代碼如下：

由此可見鏈表在空狀態和非空狀態插入和洗掉物件的操作是不同的，這樣就給提高了程式的復雜度，需要在插入和洗掉物件前判斷鏈表是否為“空”，
哨兵機制（表頭機制）可以解決這個問題，哨兵是一個啞物件，作用是簡化邊界條件處理，使用哨兵可以使得代碼緊湊，使用哨兵機制的鏈表如下如：

使用哨兵機制（表頭機制）后鏈表在空狀態和非空狀態插入和洗掉物件的操作是相同的，這樣可以使得代碼緊湊，清晰，

• 深入分析FREERTOS就緒表

FreeRTOS就緒表的原始碼如下：

FreeRTOS中的TCB結構如下：

FreeRTOS中的就緒表特點：
1、使用的是用戶資料中包含鏈表的方式，
2、使用指標法定位物件地址，
3、使用哨兵機制（表頭機制），

分析：
1、用戶資料中包含鏈表

FreeRTOS中在TCB資料結構中加入了鏈表物件ListItem_t ，這種使用方法是用戶資料中包含鏈表的方式，

2、指標法定位物件地址

FreeRTOS中xLIST_ITEM中加入了void * pvOwner指標用于定位包含鏈表的物件的地址，這種使用方法是指標法定位物件地址，

3、哨兵機制

FreeRTOS中MiniListItem_t就是哨兵（表頭），

• 代碼：

/* github: liyinuo2017								author:liwei */
/**********************鏈表中包含戶資料形式 **********************/
struct list_contain_data_def						
{
		
	u32 		key;								/*鍵值 */
	struct		list_contain_data_def *  next;		/*指向下一個物件*/
	struct		list_contain_data_def *  previous;	/*指向上一個物件*/
	u8			user_data[100]; 					/*用戶資料*/

}list_contain_data_t;


/**********************用戶資料中包含鏈表形式 **********************/
struct list_def
{
	u32 		key;					/*鍵值 */ 	
	struct		list_def *	next;		/*指向下一個物件*/
	struct		list_def *	previous;	/*指向上一個物件*/	
	
}list;		/*鏈表 */
typedef struct	list	 list_t;  /*鏈表 */

struct data_contain_list_def
{
		
	u8			user_data[100]; 		/*用戶資料*/
	
	list_t		user_list				/*鏈表*/

}data_contain_list_t;

struct list_def
{
	u32 		key;					/*鍵值 */ 	
	struct		list_def *	next;		/*指向下一個物件*/
	struct		list_def *	previous;	/*指向上一個物件*/	
	void *		owner;					/*指向鏈表擁有者 */
	
}list;		/*鏈表 */
typedef struct	list	 list_t;  /*鏈表 */

struct data_contain_list_def
{
		
	u8			user_data[100]; 		/*用戶資料*/
	
	list_t		user_list				/*鏈表*/

}data_contain_list_t;


#define container_of(ptr, type, member) ({ \

const typeof( ((type *)0)->member ) *__mptr = (ptr); \

(type *)( (char *)__mptr - offsetof(type,member) );})
	

struct xLIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*檢查位*/
		
	configLIST_VOLATILE TickType_t xItemValue;			/*用于排序的值 */
	struct xLIST_ITEM * configLIST_VOLATILE pxNext; 	/*指向下一項*/
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*指向上一項*/
	void * pvOwner; 									/*TCB指標 */
	struct xLIST * configLIST_VOLATILE pxContainer; 	/*指向放置此串列項的串列 */

	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*檢查位*/
};
typedef struct xLIST_ITEM ListItem_t;					/* 串列項 */

struct xMINI_LIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*檢查位 */
		
	configLIST_VOLATILE TickType_t xItemValue;			/*用于排序的值 */
	struct xLIST_ITEM * configLIST_VOLATILE pxNext; 	/*指向下一項*/
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*指向上一項*/
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;	   /* MINI串列項 */

typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE				/*檢查位*/
		
	volatile UBaseType_t uxNumberOfItems;				/*串列項總數量*/		
	ListItem_t * configLIST_VOLATILE pxIndex;			/*用于遍歷串列*/
	MiniListItem_t xListEnd;							/*串列的最末項*/

	listSECOND_LIST_INTEGRITY_CHECK_VALUE				/*檢查位*/
} List_t;												/* 串列 */

#define configMAX_PRIORITIES			( 10 )	

PRIVILEGED_DATA static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];/*就緒表 */


typedef struct tskTaskControlBlock			
{
	volatile StackType_t	*pxTopOfStack;		/*堆疊指標*/
	ListItem_t				xStateListItem; 	/*任務的狀態串列項*/
	ListItem_t				xEventListItem; 	/*< 任務的事件串列項 */
	UBaseType_t 			uxPriority; 		/*優先級*/
	StackType_t 			*pxStack;			/*堆疊起始地址 */
	char					pcTaskName[ configMAX_TASK_NAME_LEN ];/*任務名 */

	/*省略部分 */

} tskTCB;

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