FreeRTOS簡單內核實現2 雙向鏈表

来源:https://www.cnblogs.com/lc-guo/p/18248757
-Advertisement-
Play Games

FreeRTOS 的 list.c / list.h 文件中有 3 個數據結構、2 個初始化函數、2 個插入函數、1 個移除函數和一些巨集函數，鏈表是 FreeRTOS 中的重要數據結構 ...


FreeRTOS Kernel V10.3.1

FreeRTOS 的 list.c / list.h 文件中有 3 個數據結構、2 個初始化函數、2 個插入函數、1 個移除函數和一些巨集函數，鏈表是 FreeRTOS 中的重要數據結構，下述 “1、數據結構” 和 “2、操作鏈表” 兩個小節內容主要對其原理進行講解

1、數據結構

1.1、xLIST_ITEM

鏈表項，即節點，通常用鏈表項來表示一個任務

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;
    // 記錄此 鏈表項 歸誰擁有，通常是 TCB (任務控制塊)
    void * pvOwner;
    // 擁有該 鏈表項 的 鏈表 
    struct xLIST * configLIST_VOLATILE pxContainer;
    // 檢驗一個 鏈表項 數據是否完整
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
};
typedef struct xLIST_ITEM ListItem_t;

1.2、XMINI_LIST_ITEM

MINI 鏈表項，鏈表項的縮減版，專門用於表示鏈表尾節點，在 32 位 MCU 上不啟用鏈表項數據完整性校驗的情況下相比於普通的鏈表項節省了 8 個位元組（兩個指針）

struct xMINI_LIST_ITEM
{
	// 檢驗一個 MINI鏈表項 數據是否完整
    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;

1.3、xLIST

由多個鏈表項構成的鏈表，常用於區分不同任務狀態或任務優先順序，比如就緒狀態的任務放在就緒鏈表中，阻塞狀態的任務放在阻塞鏈表中，方便任務管理

typedef struct xLIST
{
	// 檢驗一個 鏈表 數據是否完整
    listFIRST_LIST_INTEGRITY_CHECK_VALUE 
    // 記錄 鏈表 中 鏈表項 數目
    volatile UBaseType_t uxNumberOfItems;
    // 遍歷 鏈表 的指針
    ListItem_t * configLIST_VOLATILE pxIndex;
    // 使用 MINI鏈表項 表示 鏈表尾部
    MiniListItem_t xListEnd;
    // 檢驗一個 鏈表 數據是否完整
    listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;

2、操作鏈表

註意：由於不涉及數據校驗完整性，因此下述函數中關於校驗的所有部分將被刪除

2.1、初始化

2.1.1、vListInitialiseItem( )

初始化鏈表項函數

將鏈表項的 pxContainer 成員設置為 NULL ，因為初始化的時候該鏈表項未被任何鏈表包含

void vListInitialiseItem( ListItem_t * const pxItem )  
{  
    // 確保鏈表項未被記錄在鏈表中
    pxItem->pxContainer = NULL;
}

2.1.2、vListInitialise( )

初始化鏈表函數，具體步驟如下

  1. 將鏈表當前指針 pxIndex 指向尾鏈表項 xListEnd
  2. 確保尾鏈表項 xListEnd 被排在鏈表最尾部
  3. 將尾鏈表項 xListEnd 的前/後鏈表項指針均指向自己，因為初始化鏈表時只有尾鏈表項
  4. 鏈表中有 0 個鏈表項
void vListInitialise( List_t * const pxList )  
{  
    // 鏈表當前指針指向 xListEnd
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
    
    // 設置鏈表尾鏈表項排序值為最大， 保證 xListEnd 會被放在鏈表的尾部
    pxList->xListEnd.xItemValue = portMAX_DELAY;
  
    // 尾鏈表項 xListEnd 的前/後鏈表項指針均指向自己
    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
	// 初始化時鏈表中有 0 個鏈表項
    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

2.2、插入

2.2.1、vListInsertEnd( )

將一個鏈表項插入到鏈表當前指針 pxIndex 指向的鏈表項前面，具體步驟如下

  1. 改變要插入鏈表項自身的 pxNext 和 pxPrevious
  2. 改變前一個鏈表項（也就是 pxIndex 指向的鏈表項的 Previous）的 pxNext
  3. 改變後一個鏈表項（也就是 pxIndex 指向的鏈表項）的 pxPrevious
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )  
{
	// 獲取鏈表中當前指針 pxIndex 位置
	ListItem_t * const pxIndex = pxList->pxIndex;
	 
	// 1. 改變自身 pxNext 和 pxPrevious
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    
	// 2. 改變前一個鏈表項的 pxNext
    pxIndex->pxPrevious->pxNext = pxNewListItem;
    // 3. 改變後一個鏈表項的 pxPrevious
    pxIndex->pxPrevious = pxNewListItem;
	  
    // 標記新插入的鏈表項所在的鏈表 
    pxNewListItem->pxContainer = pxList;
	// 鏈表數量增加一
    ( pxList->uxNumberOfItems )++;
}

為方便繪圖演示，將鏈表的結構在圖上做了簡化，具體如下圖所示

註意：這裡 pxList->pxIndex 自初始化以來從未修改過，保持指向鏈表 xListEnd 鏈表項，下圖所有演示中，橙色虛線表示該步驟做了修改，黑色實線表示與上一步驟相比無修改

插入一個鏈表項

插入第二個鏈表項

插入第三個鏈表項

插入第四個鏈表項

2.2.2、vListInsert( )

將一個鏈表項按照鏈表中所有鏈表項的 xItemValue 值大小升序插入鏈表中，具體步驟如下

  1. 找到應該插入的位置（應該插入到 pxIterator 的後面）
  2. 改變要插入鏈表項自身 pxNext 和 pxPrevious
  3. 改變後一個鏈表項的 pxPrevious
  4. 改變前一個鏈表項的 pxNext （也即 pxIterator 指向的鏈表項的 pxNext）
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )  
{
	ListItem_t *pxIterator;
	// 記錄要插入的鏈表項的排序值
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
	
	// 如果新插入的鏈表項排序值為最大值，直接插到尾節點 xListEnd 的前面
	if( xValueOfInsertion == portMAX_DELAY )  
	{  
	    pxIterator = pxList->xListEnd.pxPrevious;  
	}
	else  
	{
		/*
		1. 遍歷鏈表，將當前鏈表項 pxIterator 與要插入的新的鏈表項 pxNewListItem 
		的 xItemValue 值比較，直到 pxIterator 的 xItemValue 大於 pxNewListItem 
		的 xItemValue 值，此時 pxNewListItem 應該插入到 pxIterator 的後面
		*/
		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); 
			 pxIterator->pxNext->xItemValue <= xValueOfInsertion; 
			 pxIterator = pxIterator->pxNext ){}
	}
	// 2. 改變要插入鏈表項自身 pxNext 和 pxPrevious
	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxPrevious = pxIterator;
	// 3. 改變後一個鏈表項的 pxPrevious
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	// 4. 改變前一個鏈表項的 pxNext
	pxIterator->pxNext = pxNewListItem;
	
	// 標記新插入的鏈表項所在的鏈表
	pxNewListItem->pxContainer = pxList;
	// 鏈表數量增加一
	( pxList->uxNumberOfItems )++;
}

2.3、移除

2.3.1、uxListRemove( )

從鏈表中移除指定的鏈表項，具體步驟如下

  1. 改變後一個鏈表項的 pxPrevious
  2. 改變前一個鏈表項的 pxNext
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )  
{  
	List_t * const pxList = pxItemToRemove->pxContainer;  
	
	// 1. 改變後一個鏈表項 pxPrevious
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    // 2. 改變前一個鏈表項 pxNext
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
	  
    // 確保索引指向有效的項目
    if( pxList->pxIndex == pxItemToRemove )  
    {  
       pxList->pxIndex = pxItemToRemove->pxPrevious;  
    }
	
	// 從鏈表中移除鏈表項後，該鏈表項不屬於任何鏈表
    pxItemToRemove->pxContainer = NULL;  
    // 鏈表中鏈表項的數量減一
    ( pxList->uxNumberOfItems )--;  
	
	// 返回鏈表中鏈表項的數量
    return pxList->uxNumberOfItems;  
}

2.4、巨集函數

2.4.1、設置相關

// 設置 pxListItem 的 pxOwner 成員
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )

// 設置 pxListItem 的 xValue 成員值
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue )

2.4.2、獲取相關

// 獲取 pxListItem 的 pxOwner 成員
#define listGET_LIST_ITEM_OWNER( pxListItem )

// 獲取 pxListItem 的 xValue 成員值
#define listGET_LIST_ITEM_VALUE( pxListItem )

// 獲取鏈表中頭鏈表項的 xItemValue 成員值
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )

// 獲取鏈表中頭鏈表項地址
#define listGET_HEAD_ENTRY( pxList )

// 獲取某個鏈表項的下一個鏈表項地址
#define listGET_NEXT( pxListItem )

// 獲取鏈表中 xListEnd 的地址
#define listGET_END_MARKER( pxList )

// 獲取鏈表當前長度
#define listCURRENT_LIST_LENGTH( pxList )

// 將鏈表中 pxIndex 指向下一個鏈表項，用於獲取下一個鏈表項（任務）
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )

// 獲取鏈表中頭鏈表項的 pvOwner 成員
#define listGET_OWNER_OF_HEAD_ENTRY( pxList )

// 獲取鏈表項的 pxContainer 成員
#define listLIST_ITEM_CONTAINER( pxListItem )

2.4.3、判斷相關

// 判斷鏈表是否為空
#define listLIST_IS_EMPTY( pxList )

// 判斷鏈表項是否和鏈表匹配（鏈表項是否在該鏈表中）
#define listIS_CONTAINED_WITHIN( pxList, pxListItem )

// 判斷鏈表是否被初始化
#define listLIST_IS_INITIALISED( pxList )

3、鏈表移植

下麵直接將 FreeRTOS 內核中 list.c / list.h 文件移植到自己的工程中使用（當然，如果你已經懂得雙向鏈表數據結構的原理，你也可以構建屬於你自己的 list.c / list.h 文件）

移植可以總結為以下 4 個步驟

  1. 用 FreeRTOS Kernel V10.3.1 內核中 list.c / list.h 替換掉 RTOS 文件夾中的同名文件
  2. 在 portMacro.h 中統一一些用到基本類型
/* portMacro.h */
#include <stdint.h>

#define port_CHAR                   char
#define port_FLOAT                  float
#define port_DOUBLE                 double
#define port_LONG                   long
#define port_SHORT                  short
#define port_STACK_TYPE             unsigned int
#define port_BASE_TYPE              long

typedef port_STACK_TYPE             StackType_t;
typedef long                        BaseType_t;
typedef unsigned long               UBaseType_t;

typedef port_STACK_TYPE*            StackType_p;
typedef long*                       BaseType_p;
typedef unsigned long*              UBaseType_p;


#if(configUSE_16_BIT_TICKS == 1)
    typedef uint16_t                TickType_t;
    #define portMAX_DELAY           (TickType_t) 0xffff
#else
    typedef uint32_t                TickType_t;
    #define portMAX_DELAY           (TickType_t) 0xffffffffUL
#endif

#define pdFALSE                     ((BaseType_t) 0)
#define pdTRUE                      ((BaseType_t) 1)
#define pdPASS                      (pdTRUE)
#define pdFAIL                      (pdFALSE)

configUSE_16_BIT_TICKS 是一個巨集，用於 TickType_t 類型位數，具體定義如下

/* FreeRTOSConfig.h */
// 設置 TickType_t 類型位 16 位 
#define configUSE_16_BIT_TICKS                  0
  1. 刪除掉 list.c 文件中所有的 mtCOVERAGE_TEST_DELAY() 測試函數
  2. 刪除掉 list.h 文件中所有的 PRIVILEGED_FUNCTION 巨集

完成後編譯工程應該不會出現錯誤，這樣實現 RTOS 簡單內核關鍵的雙鏈表數據結構就完成了


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • SecureFX安裝問題（包含SecureCRT）
    我想用SecureFX（以及SecureCRT），但是FX安裝過程各種問題，導致安裝/卸載了大概4、5次，非常磨人。這裡記錄解決過程。 問題 secureFX註冊機缺少dll secureFX破解失敗，提示“the license is for a different version” 版本 系統： ...
  • 網路診斷工具iPerf的使用
    iPerf 是一個網路性能測試工具，用於測量最大 TCP 和 UDP 帶寬性能。它支持多種平臺，包括 Windows、Linux、macOS 等。以下是 iPerf 的基本使用方法： 安裝 iPerf 在 Linux 系統中，你可以使用包管理器來安裝 iPerf。在 Ubuntu 或 Debian ...
  • FreeRTOS簡單內核實現4 臨界段
    @目錄0、思考與回答0.1、思考一0.2、思考二0.3、思考三1、關中斷1.1、帶返回值1.2、不帶返回值2、開中斷3、臨界段4、應用 0、思考與回答 0.1、思考一 為什麼需要臨界段？ 有時候我們需要部分代碼一旦這開始執行，則不允許任何中斷打斷，這段代碼稱為臨界段 0.2、思考二 如何實現臨界段？ ...
  • 針對make工具和Makefile文件的學習心得
    目錄為什麼要學習使用make工具？什麼是make工具？make工具的學習過程1. 安裝make：sudo apt install make；並學習使用make安裝make流程學習使用make指令make指令的相關特點make只會對修改過的或者可執行目標文件不存在的.c文件進行編譯使用make時，若不 ...
  • FreeRTOS簡單內核實現3 任務管理
    0、思考與回答 0.1、思考一 對於 Cortex-M4 內核的 MCU 在發生異常/中斷時，哪些寄存器會自動入棧，哪些需要手動入棧？ 會自動入棧的寄存器如下 R0 - R3：通用寄存器 R12：通用寄存器 LR （Link Register）：鏈接寄存器，保存返回地址 PC （Program Co ...
  • Makefile手冊中"+=",":=","?="操作符的區別
    目錄Makefile手冊中"+=",":=","?="操作符的區別1."?="操作符2."+="操作符3.":="操作符 Makefile手冊中"+=",":=","?="操作符的區別 1."?="操作符 在GNUmake中，有一個變數在之前沒有被賦值的情況下才會對這個變數進行賦值的操作，被稱為條件 ...
  • QT210開發板學習(2): 通過DNW點亮LED燈
    查找開發板原理圖,可知 可用的LED有4個, 引腳為EINT0/1/2/3, 對應的IO口則是GPH0_0/1/2/3, 寄存器有GPH0CON,GPH0DAT,GPH0PUD,GPH0DRV GPH0CON用來設置IO模式(地址為0xE0200C00), GPH0DAT是電平狀態(地址為0xE02 ...
  • QT210開發板學習(1): SEC S5PC110 Test B/D驅動安裝
    把開發板的開關撥到USBBOOT，通過USB線連接到開發板的OTG口，打開板上總電源，會提示驅動安裝失敗 我們需要下載驅動(win7-64-DNW-USB) https://github.com/joyjohn131/QT210/tree/main/1 打開dseo13b.exe，依次點擊 Next ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類