ucos中的任务调度

看了一个星期在2440上实现的ucos2。这个操作系统比较简单，但是如果真正去移植一次，应该收获会很大。暂时不打算做这个工作。下面记录一下

1. ucos中任务的栈

首先，在ucos中每个任务是有自己的栈区，这个在创建任务的时候就需要指定。

[cpp] view plain copy
print?

• OSTaskCreate (MainTask,(void *)0, &MainTaskStk[MainTaskStkLengh - 1], MainTaskPrio);
  

其中，MainTaskStck[]就是我们给maintask分配的栈区，其实就是一个静态存储区。当然在分配的时候在，这个栈区的大小也就已经固定了。所以写程序时候，要注意分配栈区不能太小。另外，ucos2提供了检测栈使用量的方法。

[cpp] view plain copy
print?

• OSTaskCreateExt (Task0,(void *)0, &Task0Stk[Task0StkLengh - 1], Task0Prio,
•                   OS_TASK_TASK1_ID,
•                   &Task0Stk[0],
•                   Task0StkLengh,
•                   (void*)0,
•                   OS_TASK_OPT_STK_CHK | OS_TASK_OPT_STK_CLR);
  

利用上面这种创建任务的方法，就指定了栈区的大小。然后，ucos对于由ostaskCreateExt创建的task，提供了检测它的栈使用量的方法。具体的操作办法就是，在创建任务的时候，将任务的栈全部赋值为0.这样检测的时候，从栈底开始，读到不为0的地方，就可以直到栈使用了的大小了。
任务的tcb结构体struct os_tcb中，有OS_STK    *OSTCBStkPtr， 指向了当前的栈顶。这样每次任务换入的时候，就把OSTCBStkPtr赋值给sp；任务换出时候，把sp的值保存到OSTCBStkPtr。

2. 任务的调度的优化算法

     ucos中，可以支持64个任务（ucos2中可以支持更多任务），各个task的priority都不相同（linux不是这样的）。 ucos中有一个数组：

OS_EXT  OS_TCB    *OSTCBPrioTbl[OS_LOWEST_PRIO + 1]。 这个数组用priority作为index，对应每个priority的任务都有一个这样的结构体。每次任务调度，就是要找到优先级最高的任务（priority越低，优先级越高），并执行该任务。 按照最原始的算法， 要找到优先级最高的任务，就是从OSTCBPrioTbl[0]开始遍历，直到找到一个状态为ready的任务。 这样每次查找的复杂度是O(n)。 但是在ucos中，对此进行了优化。以前也看到过这种方法，具体优化的思想是这样的：

首先，利用位运算的思想，64个任务用8个char型变量可以表示，连续的8个任务分为1组，用OSRdyTbl[8]数组来表示，其中OSRdyTbl[0]的0位代表的是 task0是否就绪，如果就绪就置为1。

然后，在建立一级索引，用char型变量OSRdyGrp的8位分别表示 OSRdyTbl[x]中是否为0。 如果OSRdyGrp的第0位为0，就表示 OSRdyTbl[0] 是0。

这样，要找到优先级最高的任务，就先检测OSRdyGrp，找到第一个不为0的第n位。然后，检测OSRdyTbl[n]，找到第一个不为0的m位，这样，最优先的任务就是task[8*n + m]。

最后，对于上面的两次查找，都涉及到 找一个char型变量第一个不为0的位是哪一位，这个的复杂度仍是O(n/8)。我们可以用打表的方式来进行优化，使复杂度变成了O(1)。 建立一个数组， OSUnMapTbl[256]，记录每一个数字第一个1所在的位置。

这样，每次查找优先级最高的任务，只需要两条语句。复杂度是O(1)。这样进行了优化。

3.  CPU利用率的计算

在ucos中有一个优先级最低的idletask，当没有其他task处于ready时候，cpu就会运行idletask。 在idletask中有一个计数器idlecnt，每次调用idletask, 都会idlecnt++。在ucos刚启动时，会先统计1s内只运行ldletask时，idlecnt的值为maxcnt，这个值作为cpu利用率为100%。

这样， 得到正常运行时，1s内idlecnt的值。然后，cpu 利用率等于   (maxcnt - idlecnt)/ maxcnt。

不知道windows是不是这样算的。linux也有一个类似的idletask。

4. 任务间通信

任务间通信可以通过信号量、邮箱、消息队列。他们都是基于os_event实现的。如下

[cpp] view plain copy
print?

• 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)          */
•     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                */
• } OS_EVENT;
  

.OSEventTbl[] 和 .OSEventGrp 很像前面讲到的 OSRdyTbl[]和 OSRdyGrp，只不过前两者包含的是等待某事件的任务，而后两者包含的是系统中处于就绪状态的任务。每个等待事件发生的任务都被加入到该事件事件控制块中的等待任务列表中。当一个事件发生后，该事件的等待事件列表中优先级最高的任务，也即在.OSEventTbl[]中，所被置 1 的位中，优先级代码最小的任务得到该事件

。

信号量是维护了一个计数器 OSEvenvCnt，表示资源的个数。 mailbox是维护了一个OSEventPtr，当有任务向mailbox post后，等待mailbox的优先级最高的任务进入ready状态（有可能直接运行）。 对于 messagequeue适合用于 生产者消费者模型，在ucos中printf就是利用messagequeue实现的。

5. 动态内存分配

在ucos中实现了自己的动态内存分配，具体的算法和linux中很相似。

[cpp] view plain copy
print?

• typedef struct {
• void   *OSMemAddr;
• void   *OSMemFreeList;
• INT32U OSMemBlkSize;
• INT32U OSMemNBlks;
• INT32U OSMemNFree;
• } OS_MEM;
  

首先，空闲的内存用于固定的用途，所以把空闲的内存分成相同大小的块，然后把空闲内存块用链表链接起来，也就是在每块内存的起始位置放着下一块内存的地址。用OSMemFreeList指向第一块空闲内存的首地址。当内存使用时，就把 OSMemFreeList指向下一块内存，返回当前指向的内存。同理，有内存释放后，再把释放的内存添加到 链表的头部。

6. 实时的体现

        实时系统是指能够在确定的时间内执行计算或处理功能，并对外部的异步事件做出响应的计算机系统。多任务实时系统的性能主要体现在系统中每个任务的调度时间和执行时间的确定性。在系统硬件平台确定的情况下，系统的实时性完全取决于多任务调度算法。与非实时系统相比，实时系统最大的特点在于，系统执行的正确性不仅仅在于计算的逻辑或者算术结果的正确性，还取决于系统产生结果的时间。

按照Rhea ls to ne 方法[4 ]，定义了以下6 项指标来衡量实时系统的性能：
(1 ) 任务切换( Tas k Switch)时间，即系统在两个独立的、处在激活态并具有相同优先级的任务之间切换所需要的平均时间。切换时间取决于在存入和恢复上下文时处理数据结构的效率以及中央处理器(CPU) 的结构和指令集。
(2 ) 抢占(Pre emption) 时间，即系统将控制从低优先级的任务转移到高优先级的任务所花费的平均时间。

(3 ) 中断等待时间(Lat en cy ) ，即从CPU 收到中断请求到执行中断服务程序的第一条指令所用的时间。

(4 ) 信号灯(S ema p h o r e ) 交替延迟时间，指从一个任务释放信号灯到另一个等待信号灯的任务被激活的时间延迟。
(5 ) 死锁解脱时间，指系统解开死锁所需的平均时间。死锁解脱时间反映了操作系统解决死锁算法的效率。
(6 ) 数据报(Dat a Gram) 通过率是，当一个任务调用实时操作系统的原语把数据传送到另一个任务时，每秒传送的字节数。

在ucos上，这些时间我理解的都是一个可确定的时间。首先，当一个高优先级的task就绪后，就立刻进行任务切换，并开始运行。任务调度发生的时间在：

一个新任务被创建或退出；

中断处理结束后，其中包括时钟tick的中断，也就是说每次tick都可能发生任务切换

信号量\mailbox等的相关操作

任务调用延时函数timedly

上面这些情况中，都可以保证一个高优先级的任务可以先于低优先级任务而运行，当然ucos中存在优先级反转的问题。

在linux中，就没有做到这一点。linux给所有任务都分配了时间片，当前任务的时间片没有用完时，即使有更高优先级的任务ready，也不会发生任务 切换。高优先级的任务可以分配到更多的时间片，但调度时并没有优先调度高优先级的任务。 这样，就导致任务 的抢占时间变得不确定，所以说linux不是实时操作系统，有些书上称它为软实时的。