一、概述

在嵌入式操作系统中，总是存在多个任务并发或并行运行。这些任务间在运行时需要同其它任务共享和竞争资源，也可能存在某种“协作”关系。在资源不可用时，或“协作”条件未达到时，任务需要等待。有时，因同一原因需要等待的任务存在多个。比如，如果我们将ＣＰＵ也视为一种资源，在一般的单处理器中，总会存在一个或多个任务在等待ＣＰＵ的空闲而被置入“就绪队列”中。

不仅是ＣＰＵ的就绪队列，对于诸如信号量、邮箱队列等内核提供的机制，操作系统也需要为这些结构实现任务的阻塞队列。当任务申请延时时，也需要将任务置于某种队列结构中，以备内核在系统时钟中断发生时或之后对这些任务进行处理。一种极端的实现机制是，不设置任务的队列结构，在事件发生或资源可用时，操作系统遍历每一个任务，检查是否阻塞，如果是，则将任务置为就绪态。这种实现机制，在任务数少，且硬件资源如RAM等不够用的情况下非常有效，但对于任务数较多，且调度算法相对而言复杂的情况下，显然效率太低。

这里，针对整个系统内核的各个对像，信号量、消息队列、就绪队列等，实现一种灵活、高效的队列结构。

二、设计的目标

首先，考虑内核的任务。在eos中，设置了多个优先级，同优先级间允许多个任务存在，未限定同优先级的最大任务数。显然，静态的表结构难以满足需求，可设置一个多级队列，队列中必须设计成链表等其它可动态管理的结构以处理任意结点删除的情况。已知内核容许的最大优先级是在编译内核时就确定好的。

 其次，考虑针对队列的各种操作：

　　１、队列提供创建、初始化的操作；

　　２、提供依据结点的优先级插入到相应的队列结构操作；这里一个结点可理解为对应一个任务；

　　３、提供从队列中取出最高优先级结点的操作，因为优先级任务高的任务有优先权，　　　当事件发生时，从队列中唤醒的首先是最高优先级的任务；

４、提供队列中任意结点的删除操作；一种情况是，当任务被删除时，如果其被阻塞在某个队列中，必须将其从队列中移除；

　　　　５、其它的一些操作：队列的判空，返回队列中任务的最高优先级等。

以上的操作，是eos内核运行基本的要求.可能在以后的设计中会有新的需要，将会适当添加。

三、数据结构的实现

在整个eos的实现中，除与硬件相关的内容外，其它的设计均是基于数据结构。

这里，实现了一种通用的多级队列结构，不是仅针对内核的队列，而是可同时供内核和应用代码使用的结构。队列由结点组成。

一)、单级队列结构设计

　　　在单级队列结构中，各结点的优先级是相同的，结点进入队列按FIFO或LIFO方式，可对队列中的任意结点进行删除操作。

１）、结点的结构

结点的由一结构体实现：

typedef struct _DQItem DQItem;

struct  _DQItem      // 双向队列结点类型

{

struct _DQItem * pre, * next; / 结点的链接指针

DQ * list; / 结点所在的队列

portDQItemValueType value; // 结点所拥有的值

portDQItemPolicyType policy;   // 对结点操作时策略

portDQItemOwnerType * owner; // 结点的所有者

};

其中list 指向该结点所在队列，这一项在删除队列中任意结点时特别有用，详见DQRemove函数。value指结构的值，可存储任务的优先级或延时值，policy指对结点进行某种操作时的策略，可用在事件标志机制中，这里暂不必考虑其功能。owner 指该结点的拥有者，一般指向拥有该结点的任务TCB（即任务控制块)。

( 说明：TCB维护了任务运行所需的所有信息，可认为TCB标识了任务)

２）、队列结构

单级队列结构：

typedef struct _DQ // 双向队列

{

struct _DQItem * front; // 队首指针

struct _DQItem * rear; // 队尾指针

}DQ;

DQ队列被设计成包含头尾指针的结构，队列中的元素按FIFO方式进出队列.

一个典型的包含多个结点的队列如图所示。

其中，首结点的.pre和尾结点的next 项均指向NULL，在对队列结构进行遍历时，依据指针是否为NULL，很容易判定是否到达队尾。结点在队列的进出按FIFO//LIFO方式，其中FIFO方式保证了单级队列间各结点间的“公平性”。

特别的，当队列为空时，.fornt, .rear均为NULL。

当队列中只有一个结点时，front, rear均指向该结点

上图基本表现出了队列和结点、结点与结点间的连接关系。

３）、基本的操作实现           

针对结点有以下操作:         

　　void DQItemInit( DQItem * item, portDQItemOwnerType * owner, portDQItemValueType value ); // 初始化任务队列的结点

该操作简单的初始化结点的owner, value域。相关代码:

item->value = value;

item->owner = owner;

针对单级队列的操作:

void DQInit( DQ * list ); // 初始化任务队列

void DQInsert( DQ * list, DQItem * item ); // 将结点插入任务队列头部

void DQAppend( DQ * list, DQItem * item ); // 将结点插入任务链表尾

void DQRemove( DQItem * item ); // 将结点从所在任务队列移除

DQItem * DQGetHead( DQ * list ); // 取任务队列头结点

#define DQEmpty( list ) ( (list)->front == ( DQItem * )0 )  // 判定任务队列是否为空

实际的代码实现比较简单，分析略。

依赖于上述的代码，队列DQ实际提供了FIFO, LIFO的结点进出队列方式。

实现的代码中，需特别注意当队列为空，和队列只有一个结点时相应操作的实现。

二）、多级队列结构实现

多级队列只是简单的由多个单级队列的组合，但各队列间的优先级不同。在实现的代码中，多级队列表现为一数组结构，数组的第一项优先级最高，依次递减。

typedef struct _MDQ           // 多级任务队列

{

u8_t value; // 当前队列中最高优先级

DQ tbl[ MDQ_LEVEL ]; 

}MDQ;

其中MPD中的.value域保存了当前多级队列中包含结点的最高优先级单级队列的优先级。之所以包含此域，是为了加快查找。当value >= MDQ_LEVEL是，表明队列为空，不包含任何结点。.tbl数组为实际的多个单优先级队列。

MPDQ的基本操作如下：

void MDQInit( MDQ * q ); // 初始多级任务队列

void MDQPut( MDQ * mdq, DQItem * item  ); // 将结点插入多级任务队列

void MDQRemove( MDQ * mdq, DQItem * item  ); //将结点从多级任务队列移除

DQItem * MDQGet( MDQ * mdq );  // 移除最高优先级任务队列的头结点

 #  define MDQEmpty( MDQ ) ( (MDQ)->value >= MDQ_LEVEL )

#define MDQHighPrio( MDQ ) ( (MDQ)->value )

MPQ的绝大部分操作是基于单级队列DQ的操作。

代码分析略。

如果将CPU的就绪队列以MDQ实现，那么，当CPU空闲时，由MDQGet()找出最高优先级的任务，再进行任务切换。而当任务主动放弃CPU时，MPDQPut（）将任务插入至多级队列中相应单级队列末。因而CPU总是运行最高优先级任务，而同优先级的任务间则由于其中针对单级队列的FIFO操作而按FCFS(　先来先服务　)的原则运行。如果配置一个定时器，在时钟中断ISR中，强迫正在运行的任务放弃CPU，将其插入就绪队列，再从就绪队列提出最高优先级任务，这样，即可实现所谓的同优先级任务间基于时间片的调度(RR调度)。

四、代码的测试与应用

略。

五、分析与总结

反观ucos的实现，其所有的队列结构均是通过位图实现，通过一个查找表，能够快速的实现队列中结点的删除、添加。然后，这种机制的实现是以内核中同一优先级只能对应于一个任务为前提的。从效果上来说，这种机制效率很高，占用的存储空间也小。

然而在eos中，同一优先级允许多个任务。前提的不同导致了这里不能简单的将ucos 的机制照搬过来。之前，我也曾考虑过是否能以位图实现，然而多个任务的同优先级情况使得非常难于实现，至少是对我而言。这里直接使用的是指针＋链表，确实比较灵活，然而无论是效率还是存储空间的占用都比不上ucos。这是必然的，更复杂的机制需要更复杂的实现。

目前的数据结构只限于队列结构，在后续的代码实现中可能会添加其它的结构实现。DQ, MDQ就整个内核来说，还是可以应付绝大多数情况。