2.3　實時操作系統內核使用的數據結構

實時操作系統內核代碼中使用了棧、堆、隊列、鏈表等數據結構，本節簡要介紹這些基礎知識。

2.3.1　棧與堆

1.棧和堆的基本概念

在數據結構中，棧（Stack）是一種操作受限的線性表，只允許在表的一端進行插入和刪除操作。允許插入和刪除操作的一端被稱為棧頂（Top），不允許插入和刪除的另一端稱為棧底（Bottom）。向一個棧插入新元素稱為進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素稱為出棧或退棧，它是把棧頂元素刪除，使其相鄰的元素成為新的棧頂元素。棧的操作是按后進先出原則進行的。如圖2-2所示，棧中先按a1，a2，…，an的順序入棧，最后加入棧中的an元素為棧頂，而出棧的順序反過來，先an出棧，然后an-1才能出棧，最后a1出棧。

在操作系統中，棧是RAM中的存儲單元，常用于保存和恢復中斷現場，也用于保存一個函數調用所需要的、被稱為棧幀（Stack Frame）的維護信息，初始時棧底地址等于棧頂地址。棧幀一般包括函數的返回值和參數、臨時變量（包括函數的非靜態局部變量及編譯器自動生成的其他臨時變量）、保存的上下文（包括函數調用前后需要保持不變的寄存器）。在ARM Cortex-M處理器中，棧地址是向下（低地址）擴展的，是一塊連續的內存區域。因此，棧指針初始值一般為RAM的最大地址，進棧地址減小，出棧地址增加，棧的操作按后進先出原則進行。棧空間資源由編譯器自動分配和釋放，存取速度比堆快，其操作方式類似于數據結構中的棧。

在數據結構中，堆（Heap）是一個特殊的完全二叉樹，有最小堆和最大堆之分，常用來實現排序。在操作系統中，堆是內存中的存儲單元，堆空間分配方式類似于鏈表，堆地址是向上（高地址）擴展的，是不連續的內存區域。在C語言中，堆存儲空間是由new運算符或malloc（）函數動態分配的內存區域，一般速度比較慢，而且容易產生內存碎片，但是堆的空間較大，使用起來靈活、方便。堆一般由用戶自行釋放，若用戶不釋放，程序結束時可能由操作系統回收（操作系統內核需要有這種功能）。

由于在RAM中堆空間之后就是棧空間，它們是相連的，而且堆是由低地址向高地址方向使用，棧是由高地址向低地址方向使用，故通常在概念上將堆和棧合在一起稱為堆棧，堆棧操作通常理解為棧操作。由于堆的操作比較復雜，本書只介紹棧的基本操作。

可以使用下列語句來定義一個順序棧：

其中，stack_size表示棧的容量。順序棧的初始化操作會給棧分配由stack_size指定空間大小的連續存儲區域，并將該區域的地址賦給base和top。base為棧底指針，始終指向棧底位置。top為棧頂指針，初值指向棧底，即top=base（可作為?？盏臉擞洠?。

2.棧的基本操作

棧的基本操作包括棧的初始化、判空、入棧、出棧、清空棧等，本書中的棧主要指內存的一段連續的區域，即順序棧，涉及棧的操作主要是入棧（Push）和出棧（Pop），下面介紹這兩個操作。

1）入棧

入棧操作指的是向棧中插入一個元素。棧只允許在棧頂插入元素，每當插入新元素時，棧頂指針上移一個存儲單元。入棧操作如圖2-3所示。

算法表述：

2）出棧

出棧操作指的是從棧中刪除一個元素。棧只允許在棧頂刪除元素，每當出棧一個元素時，棧頂指針下移一個存儲單元。出棧操作如圖2-4所示。

算法表述：

3.棧操作指令舉例

ARM Cortex-M處理器在物理上存在兩個棧指針分別指向兩個棧：①主堆棧指針（MSP），是系統復位后默認的棧指針，用于所有的異常處理；②進程堆棧指針（PSP），是進程模式的棧指針，用于常規的應用程序代碼（不處于中斷服務程序中時）。在匯編語言中，入棧和出棧操作都被封裝到PUSH和POP指令中，可以直接使用以下指令：

雖然指令能幫助完成入棧和出棧操作，但是只有明白了入棧和出棧過程中元素的操作順序和棧頂指針的變化情況，才能真正理解程序的含義。

2.3.2　隊列

1.隊列的基本概念

和棧相反，隊列（Queue）是一種先進先出的線性表，它只允許在表的一端插入，在另一端刪除。允許插入的一端稱為隊尾（Rear），允許刪除的一端稱為隊頭（Front），如圖2-5所示。隊列中沒有元素時，稱為空隊列。隊列的數據元素又稱為隊列元素，在隊列中插入一個元素稱為入隊，從隊列中刪除一個元素稱為出隊，只有最早進入隊列的元素才能最先從隊列中刪除。按照存儲空間的分配方式，隊列可以分為順序隊列與鏈隊列兩種。在操作系統中經常使用隊列來進行對象的管理和調度。

2.隊列的基本操作

隊列的基本操作包括初始化、入隊、出隊、判空等。本書主要涉及鏈隊列，下面將結合鏈表對隊列的基本操作進行介紹。

2.3.3　鏈表

1.鏈表的基本概念

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列節點組成，節點可以在運行時動態生成。每個節點包括兩個部分：一是存儲數據元素的數據域；二是存儲后繼節點（也可以存儲前驅節點）地址的指針域。在程序實現時，必須由包含指針的變量來存放相鄰節點的地址信息，可以用結構體變量來定義節點，節點之間通過節點的指針域串聯成一個鏈表。鏈表具有不必按順序存儲，可以動態生成節點分配存儲單元，對節點進行插入和刪除操作時不需移動節點，只需修改節點的指針域等優點。因此，在實時操作系統的很多場合都采用鏈表作為管理媒介。

按照節點是否包含前驅指針，鏈表可分為單鏈表（Singly Linked List）和雙向鏈表（Doubly Linked List）兩種，如圖2-6所示。一個鏈表通常都有一個頭指針，頭指針指向鏈表的第一個節點，其他節點的地址則在前驅節點的指針域中，最后一個節點沒有后繼節點，該節點的指針域為NULL（在圖2-6中用符號“^”表示）。因此，對鏈表中任一節點的訪問必須先根據頭指針找到第一個節點，再按有關節點的指針域中存放的指針順序往下找，直到找到所需節點。

鏈表的操作包括鏈表的判空與遍歷、節點的插入與刪除及讀取節點元素等。鏈表在初始化時，將第一個節點的地址賦給鏈表的頭指針，頭指針是操作鏈表的基礎。下面給出部分操作的實現方法。

2.鏈表節點的插入操作

鏈表的插入操作首先需要確定節點的插入位置，然后改變鏈表中相關節點的指針指向。改變指針指向的時候必須注意順序，因為節點的指針域存有相鄰節點的地址信息，如果指針操作順序不當，丟失節點地址信息，就會導致插入失敗。圖2-7給出了在單鏈表的第i個節點之后插入節點時的指針變化情況。

假設節點類型定義如下：

單鏈表插入算法：

雙向鏈表的插入操作：由于雙向鏈表在表節點中多出了一個前驅節點，因此在改變指針指向時要多出兩個操作步驟，本質上與單鏈表的插入是一致的。圖2-8給出了在雙向鏈表的第i個節點之后插入節點時的指針變化情況。

雙向鏈表插入節點算法：

3.鏈表節點的刪除

理解了鏈表的插入操作后，再理解鏈表的刪除操作就相對容易一些了。刪除表節點首先需要知道節點的位置，然后改變相鄰節點的指針指向，就可從鏈表中刪除表節點。同樣，在刪除節點時需要注意指針的操作順序。圖2-9給出了單鏈表中刪除第i個節點的指針變化情況，圖2-10給出了雙向鏈表中刪除第i個節點時的指針變化情況。

1）單鏈表刪除算法

2）雙向鏈表刪除算法

4.鏈表的創建

鏈表的創建實際上是表節點不斷插入的過程。從空鏈表開始（頭指針為空），將第一個節點的地址賦給頭指針，接著一個個插入后續表節點形成鏈表。鏈表的創建有兩種方式，一種是頭插法，一種是尾插法。

頭插法創建單鏈表從空鏈表開始，每次申請一個新節點，將新節點插入當前鏈表的第一個節點之前，這樣當所有節點插入完畢，鏈表的創建過程也就完成了。頭插法創建的鏈表節點順序剛好與節點的插入順序相反，最后一個插入的節點在鏈表中是第一個節點，第一個插入的節點變成鏈表的最后一個節點，如圖2-11所示。

1）頭插法算法

尾插法與頭插法剛好相反，每次插入新節點的位置為當前鏈表的尾部，這樣構建鏈表的好處是單鏈表節點的順序與節點的插入順序是一致的。尾插法創建單鏈表如圖2-12所示。

2）尾插法算法

5.鏈隊列操作

隊列的鏈表實現形式稱為鏈隊列。按照隊列的操作原則，出隊操作即刪除隊列元素要從隊列的頭部進行，入隊操作即插入元素必須從隊列尾部進行。理解了鏈表的插入和刪除操作，鏈隊列的入隊和出隊就比較容易理解了。圖2-13所示為鏈隊列的入隊和出隊操作示意圖。

假設鏈隊列類型定義如下：

1）鏈隊列的出隊算法

2）鏈隊列的入隊算法

3）獲取鏈隊列的隊頭元素