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）获取链队列的队头元素