数据结构在对操作系统的理解是有很大的帮助的,而且也是必须要掌握的。在ucosII中也有很多的数据结构的应用。
数据结构的参考书目主要是严蔚敏老师的数据结构教材了。网上也应该能找到严蔚敏老师的数据结构的视频。可以去电驴去慢慢拖。我已经在六维空间
里下过了,但是没有看过。一直放在硬盘里面存着。
数据结构中主要的部分就是线性表,队列,堆栈,串,数组,树和二叉树,图,还有一些排序和查找的快速算法。这一些东西是要求掌握的,在软件中也是经常
要考虑到和使用的(具体的参考严蔚敏老师的教材)。
ucosII中大量使用了线性表,队列,堆栈。
1.线性表: ucosII中为每一个任务配置一个任务控制块,任务控制块中,ucosII用到了双链表对所有的任务控制块进行管理。
2.队列: ucosII中对队列的使用的典型就是消息队列的应用了.
3.堆栈: 堆栈的使用在之前已经讲过了,堆栈在任务调度的时候对现场进行保存和恢复的时候是经常要用到的。
首先看任务控制块的结构体(代码在ucosII.h中):
typedef struct os_tcb {
OS_STK *OSTCBStkPtr; /* Pointer to current top of stack */
#if OS_TASK_CREATE_EXT_EN > 0
void *OSTCBExtPtr; /* Pointer to user definable data for TCB extension */
OS_STK *OSTCBStkBottom; /* Pointer to bottom of stack */
INT32U OSTCBStkSize; /* Size of task stack (in number of stack elements) */
INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */
INT16U OSTCBId; /* Task ID (0..65535) */
#endif
struct os_tcb *OSTCBNext; /* Pointer to next TCB in the TCB list */
struct os_tcb *OSTCBPrev; /* Pointer to previous TCB in the TCB list */
#if (OS_EVENT_EN) || (OS_FLAG_EN > 0)
OS_EVENT *OSTCBEventPtr; /* Pointer to event control block */
#endif
#if (OS_EVENT_EN) && (OS_EVENT_MULTI_EN > 0)
OS_EVENT **OSTCBEventMultiPtr; /* Pointer to multiple event control blocks */
#endif
#if ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) || (OS_MBOX_EN > 0)
void *OSTCBMsg; /* Message received from OSMboxPost() or OSQPost() */
#endif
#if (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0)
#if OS_TASK_DEL_EN > 0
OS_FLAG_NODE *OSTCBFlagNode; /* Pointer to event flag node */
#endif
OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run */
#endif
INT16U OSTCBDly; /* Nbr ticks to delay task or, timeout waiting for event */
INT8U OSTCBStat; /* Task status */
INT8U OSTCBStatPend; /* Task PEND status */
INT8U OSTCBPrio; /* Task priority (0 == highest) */
INT8U OSTCBX; /* Bit position in group corresponding to task priority */
INT8U OSTCBY; /* Index into ready table corresponding to task priority */
#if OS_LOWEST_PRIO <= 63
INT8U OSTCBBitX; /* Bit mask to access bit position in ready table */
INT8U OSTCBBitY; /* Bit mask to access bit position in ready group */
#else
INT16U OSTCBBitX; /* Bit mask to access bit position in ready table */
INT16U OSTCBBitY; /* Bit mask to access bit position in ready group */
#endif
#if OS_TASK_DEL_EN > 0
INT8U OSTCBDelReq; /* Indicates whether a task needs to delete itself */
#endif
#if OS_TASK_PROFILE_EN > 0
INT32U OSTCBCtxSwCtr; /* Number of time the task was switched in */
INT32U OSTCBCyclesTot; /* Total number of clock cycles the task has been running */
INT32U OSTCBCyclesStart; /* Snapshot of cycle counter at start of task resumption */
OS_STK *OSTCBStkBase; /* Pointer to the beginning of the task stack */
INT32U OSTCBStkUsed; /* Number of bytes used from the stack */
#endif
#if OS_TASK_NAME_SIZE > 1
INT8U OSTCBTaskName[OS_TASK_NAME_SIZE];
#endif
} OS_TCB;
可以看见系统为每一个任务会分配一个任务控制块,以便对任务进行控制与管理。具体的代码大家要自己研究.但是对他的了解是非常有助于我们队整个
系统的理解的。
在一个系统中,可以想到任务是很多的,此时分配给任务的任务控制块也是很多的,但是怎么进行管理与方便控制呢?
此时系统设计了一个无头结点的双链表进行管理。双链表的好处就是查找具体的某个任务的TCB时会很方便,而单链表会稍显复杂,但是双链表的每个节
点要两个指针分别之前前后节点。消耗比单链表大。
struct os_tcb *OSTCBNext; /* Pointer to next TCB in the TCB list */
struct os_tcb *OSTCBPrev; /* Pointer to previous TCB in the TCB list */
该两句就会形成双链表,分别指向前后。
系统运行的过程中,同时存在两个任务控制块链表,一个链表将暂时没有使用的空白的任务控制块连接在一起,构成了空任务控制块链表,他的头指针为
OSTCBFreeList,另一个链表将正在使用的任务控制块链表接在一起,构成任务控制块链表(很显然这两个都是必须要有的)。系统在初始化的时候会自动
生成一个空任务控制块链表,链表中的任务控制块的个数等于用户定义的最多的任务数。当调用一个OSTaskCreat()函数时,需要进行有关任务控制块的
操作,此时需要对任务控制块进行初始化,通过OS_TCBInit()实现(后面会具体讲到这个函数)。这个函数的具体功能就是从空任务控制块链表的头部取
出一个空白的任务控制块,将该任务的的相关信息(就是TCB结构体中的一些信息)填入表中。再将这个有实际信息的TCB插入到任务控制块链表的标头(不
是空白的那个),就这样每新建一个任务是我们都会进行这样的操作,当然在删除任务时我们就会进行相反的操作,就是取出控制块链表中的相应的任务控
制块(具体是哪个要进行判断,后面再讲)放到空白的任务控制链表中.而他们是怎么进行查找的呢?就是通过任务的prio(即任务的优先级号)。将任务的
优先级号作为索引就会很容易找到对应该任务的任务控制块(因为ucosII中的每个任务的prio是唯一的)。
再看队列的应用(当然队列的使用相对来说要比TCB要麻烦一点,因为他还会涉及另外一个概念就是事件控制块):
我们可以把事件控制块看成是用来管理事件的(顾名思义嘛!!)。但是此时的事件是用于任务之间的通信和同步用的消息队列,邮箱,信号量等。事件
是用于管理他们的。而事件控制块又跟TCB挂钩(这样就能全部联系在一起了,进行一些相关的操作就会很简单与方便),体现在TCB中的下面两句代码:
#if (OS_EVENT_EN) || (OS_FLAG_EN > 0)
OS_EVENT *OSTCBEventPtr; /* Pointer to event control block */
即事件控制块的头指针是任务控制块中的信息.他本来就是属于任务的,当然应该在TCB中的,因为TCB就是管理任务的信息的(管理任务的私有财产)。
毫无保留贴出ECB的代码:(呵呵)
#if (OS_EVENT_EN) && (OS_MAX_EVENTS > 0)
typedef struct os_event {
INT8U OSEventType; /* Type of event control block (see OS_EVENT_TYPE_xxxx) */
void *OSEventPtr; /* Pointer to message or queue structure */
INT16U OSEventCnt; /* Semaphore Count (not used if other EVENT type) */
#if OS_LOWEST_PRIO <= 63
INT8U OSEventGrp; /* Group corresponding to tasks waiting for event to occur */
INT8U OSEventTbl[OS_EVENT_TBL_SIZE]; /* List of tasks waiting for event to occur */
#else
INT16U OSEventGrp; /* Group corresponding to tasks waiting for event to occur */
INT16U OSEventTbl[OS_EVENT_TBL_SIZE]; /* List of tasks waiting for event to occur */
#endif
#if OS_EVENT_NAME_SIZE > 1
INT8U OSEventName[OS_EVENT_NAME_SIZE];
#endif
} OS_EVENT;
#endif
ECB是管理上面说的那些玩意的,怎么体现的呢?看ECB中的第一个信息:INT8U OSEventType; 就是事件的Type,他的定义我也找了出来,大家应该
能猜的出来他应该在哪个文件里面了,对,他同样也在ucosII.h中
/*
*********************************************************************************************************
* OS_EVENT types
*********************************************************************************************************
*/
#define OS_EVENT_TYPE_UNUSED 0u
#define OS_EVENT_TYPE_MBOX 1u
#define OS_EVENT_TYPE_Q 2u
#define OS_EVENT_TYPE_SEM 3u
#define OS_EVENT_TYPE_MUTEX 4u
#define OS_EVENT_TYPE_FLAG 5u
那么顾名思义OSEventType的值就是取他们了,有人会问我去别的不行吗?OSEventType = 100 不行吗? 当然语法上是毫无问题的!但是这种想法是毫
无意义的。这种做法也是毫无意义的。对其进行判断的时候就会出现错误。何况咱们是在享受开源的好处,如果不是开源的,你根本就看不到这些内部的
程序的具体的实现,只会给你个pdf文档,例如你甚至连OS_EVENT_TYPE_Q 的值时多少,那么OSEventType的类型应该为队列时你敢用一个随便的值吗?
#if OS_Q_EN > 0
typedef struct os_q { /* QUEUE CONTROL BLOCK */
struct os_q *OSQPtr; /* Link to next queue control block in list of free blocks */
void **OSQStart; /* Pointer to start of queue data */
void **OSQEnd; /* Pointer to end of queue data */
void **OSQIn; /* Pointer to where next message will be inserted in the Q */
void **OSQOut; /* Pointer to where next message will be extracted from the Q */
INT16U OSQSize; /* Size of queue (maximum number of entries) */
INT16U OSQEntries; /* Current number of entries in the queue */
} OS_Q;
typedef struct os_q_data {
void *OSMsg; /* Pointer to next message to be extracted from queue */
INT16U OSNMsgs; /* Number of messages in message queue */
INT16U OSQSize; /* Size of message queue */
#if OS_LOWEST_PRIO <= 63
INT8U OSEventTbl[OS_EVENT_TBL_SIZE]; /* List of tasks waiting for event to occur */
INT8U OSEventGrp; /* Group corresponding to tasks waiting for event to occur */
#else
INT16U OSEventTbl[OS_EVENT_TBL_SIZE]; /* List of tasks waiting for event to occur */
INT16U OSEventGrp; /* Group corresponding to tasks waiting for event to occur */
#endif
} OS_Q_DATA;
#endif
队列的结构体如上所示,具体的分析要大家对队列(first in first out)有个大体的掌握才行。在这我就只做抛砖引玉了。理解好FIFO基本上也就可以
理解队列的一些相关的函数了。如OSQPosth()和*OSQPend();大家需要具体的分析,相信不会很难的。注意FIFO!!!