分类：
2009-12-06 00:21:36
读书笔记：keter的UCOS时间片轮转调度算法进度
下步计划：
1. 完成OSTCBPrioTbl的跟踪变化（<3days）
2. 完成ostimeTick的理解(<3days)
3. 使用sourceInsight找到对应版本的修改(<3days)
4. 使用vc对版本编译，测试。(<3days)
作者：转阅keter
UCOS一种只支持优先级抢占型调度的操作系统。它不支持同一个优先级有2个及以上的任务同时运作。
我修改的UCOS支持不同优先级调度的同时，支持同一个优先级有2个以上的任务以时间片轮转方式进行调度。
这个就是UCOS和我修改的UCOS的区别。
我修改后的UCOS，在以后的文段中就称为“FIFO-UCOS”。
FIFO就是先进先出的意思，和时间片轮转调度差不多的意思。
看后总结：
1. 定义是在uc_os ii.h文件。
2. 增加了传入参数,OsTaskCreat(….,id , counter)
3. 改进了OsTCBInit() ,使其对同一优先级的任务使用循环链表。
4. 改进了OsTimeTick(void)用于时间片计时
核心思想
我不对UCOS做过多的解释，我本人对UCOS的代码也没有看完。
事实上这个代码是我一年半以前做出来的了，当时就是为了帮一个朋友完成论文，并且为我卖的S3C44B0开发板增加一些东西吧。（不过我的板子最后没有卖出去多少，题外话，也许这个东西并没有多少人热心吧）
这一年半我再也没有从事过软件开发（我一直都是硬件工程师），对UCOS也有些遗忘了。也许有的东西讲错了，还请包函。
当时和那个做论文的朋友讨论的时候，他也设计了一个调度方式，但是事实证明没有我做的那个好。毕竟它增加了另外一个PCB链。
UCOS写得很好，把很多东西都做得很完善了。我要说的核心思想，就只有下面一小段话，注意看了哦：
UCOS在调度的时候，会按照优先级选择进程进行调度，我做的部分就仅仅是在他进行优先级检查之前，把和运行态同等级的进程进行了替换，替换成了时间片轮转调度的下一个进程！
呵呵，核心思想讲完了。下一节讲解具体代码了。
顺便一说
本人提供UCOS在S3C44B0上运行的完整代码。
注意，是UCOS代码，不是FIFO-UCOS；
发邮件到我邮箱：
请不要在这个地方回复邮件地址问我要，我不想复制地址那么麻烦，就直接回复你的邮件是最简单的。
TCB的修改
FIFO-UCOS和UCOS并不能完全兼容，最大的改变，就是对TCB的结构做了改动，加入了我自己的段。
该部分代码在UCOS-II.H文件中：
typedef struct os_tcb {
……………………………………………...
#if OS_TASK_DEL_EN > 0
BOOLEAN OSTCBDelReq; /* Indicates whether a task needs to delete itself */
#endif
//////////////////////////////////////////////////////////////////////////
//就是在最后添加元素
//this is my FIFO shedule code
#ifdef OS_TIME_SCHEDULE
struct os_tcb *OSTSnext;
struct os_tcb *OSTSprev;
INT8U OSTSLen;
INT8U OSTSCurLen;
#endif
//////////////////////////////////////////////////////////////////////////
} OS_TCB;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
当进程为同一个优先级的时候，*OSTSnext和*OSTSprev就形成一个链表，该链表是双向的，前后形成一个环链表。
OSTLen记录了该进程占用多少个时间片；
OSTSCurLen记录的是该进程现在还剩下多少个时间片时间可以用；
（三）－－进程创建
我的语言习惯很差，毕竟做软件不是我的专业。我再次说明，我是硬件工程师。
把代码给一个朋友看的时候，他直皱眉头。他说：你改过的地方，为什么不用
#ifdef FIFO_Schedule 来进行选择？
呵呵，以后的代码可能要让行家郁闷了，很难看，见笑！
进程创建的主要目的是跳过原代码中的优先级占用检查，并在这里加入FIFO
进程创建。
文件在Os_task.c中：
INT8U OSTaskCreate (void (*task)(void *pd), void *pdata, OS_STK *ptos,
INT8U prio,INT16U id, INT8U TSlen)
{
//增加了两个参数，在文件可以使用两个OSTaskCreate,使用#ifdef判断
……………………………………………….
if (OSTCBPrioTbl[prio] == (OS_TCB *)0) { /* Make sure task doesn't
already exist at this priority */
///////////////////////////////////////////////////////////////////////////////
////////
// if you want run the fifo mask this code
//OSTCBPrioTbl[prio] = (OS_TCB *)1; /* Reserve the priority to prevent
others from doing ... */
/* ... the same thing until task is created. */
//////////////////////////////////////////////////////////////////////
OS_EXIT_CRITICAL();
psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the
task's stack */
err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen);
if (err == OS_NO_ERR) {
OS_ENTER_CRITICAL();
OSTaskCtr++; /* Increment the #tasks counter */
OS_EXIT_CRITICAL();
if (OSRunning == TRUE) { /* Find highest priority task if multitasking
has started */
OS_Sched();
}
} else {
OS_ENTER_CRITICAL();
OSTCBPrioTbl[prio] = (OS_TCB *)0;/* Make this priority available to
others */
OS_EXIT_CRITICAL();
}
return (err);
}
////////////////////////////////////////////////////////////////////
else //this is FIFO task create code
{
OS_EXIT_CRITICAL();
psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the
task's stack */
err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen);
if (err == OS_NO_ERR) {
OS_ENTER_CRITICAL();
OSTaskCtr++; /* Increment the #tasks counter */
OS_EXIT_CRITICAL();
if (OSRunning == TRUE) { /* Find highest priority task if multitasking
has started */
OS_Sched();
}
}
return(err);
}
////////////////////////////////////////////////////////////////////
OS_EXIT_CRITICAL();
return (OS_PRIO_EXIST);
}
其中加入的传递参数有两个，一个是id，一个是TSLen
因为会出现同优先级的任务，那么采用优先级做为任务ID
的方式是不可取的了，我们必须加入任务id段
TSLen段，是该进程的时间片为多长。
///////////////////////////////////////////符号中的都是我加的代码，注意看注
释很容易看懂的。
7楼： >>参与讨论
作者： keter 于 2006-8-12 19:55:00 发布：
--------------------------------------------------------------------------------
进程初始化
进程初始化基本保留以前的东西不动，要的就仅仅是把TSLen加入TCB，把上面说到的那个链表链接起来。
代码在文件Os_task.c中
INT8U OS_TCBInit (INT8U prio, OS_STK *ptos, OS_STK *pbos, INT16U id, INT32U stk_size, void *pext, INT16U opt, INT8U TSlen)
{
…………………………………
#if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) && (OS_TASK_DEL_EN > 0)
ptcb->OSTCBFlagNode = (OS_FLAG_NODE *)0; /* Task is not pending on an event flag */
#endif
#if (OS_MBOX_EN > 0) || ((OS_Q_EN > 0) && (OS_MAX_QS > 0))
ptcb->OSTCBMsg = (void *)0; /* No message received */
#endif
/////////////////////////////////////////////////////////////////////////////
ptcb->OSTSLen=TSlen;
ptcb->OSTSCurLen=TSlen;
/////////////////////////////////////////////////////////////////////////////
#if OS_VERSION >= 204
OSTCBInitHook(ptcb);
#endif
OSTaskCreateHook(ptcb); /* Call user defined hook */
OS_ENTER_CRITICAL();
////////////////////////////////////////////////////////////////////////
if(OSTCBPrioTbl[prio] == 0)
{
OSTCBPrioTbl[prio] = ptcb;
ptcb->OSTSnext = ptcb;
ptcb->OSTSprev = ptcb;
}
else
{
ptcb->OSTSnext = OSTCBPrioTbl[prio]->OSTSnext;
OSTCBPrioTbl[prio]->OSTSnext = ptcb;
ptcb->OSTSprev = OSTCBPrioTbl[prio];
(ptcb->OSTSnext )->OSTSprev=ptcb;
}
///////////////////////////////////////////////////////////////////////////
ptcb->OSTCBNext = OSTCBList; /* LINK into TCB chain */
ptcb->OSTCBPrev = (OS_TCB *)0;
if (OSTCBList != (OS_TCB *)0) {
OSTCBList->OSTCBPrev = ptcb;
}
OSTCBList = ptcb;
OSRdyGrp |= ptcb->OSTCBBitY; /* Make task ready to run */
OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX;
OS_EXIT_CRITICAL();
return (OS_NO_ERR);
}
OS_EXIT_CRITICAL();
return (OS_NO_MORE_TCB);
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
if(OSTCBPrioTbl[prio] == 0)
{
OSTCBPrioTbl[prio] = ptcb;
ptcb->OSTSnext = ptcb;
ptcb->OSTSprev = ptcb;
}
else
{
ptcb->OSTSnext = OSTCBPrioTbl[prio]->OSTSnext;
OSTCBPrioTbl[prio]->OSTSnext = ptcb;
ptcb->OSTSprev = OSTCBPrioTbl[prio];
(ptcb->OSTSnext )->OSTSprev=ptcb;
}
附数据结构解释：
这一段解释一下
链表必须进行链接，在优先级没有被占用的时候，这个链表的前后都链向自己，这样在调度的时候，FIFO调度就算指向下个任务，也指向的是自己，不影响优先级调度。
当在这个优先级已经有进程的时候，那么我们需要的就是把这个进程加入到这个优先级的链表中，链表操作相信大家都能看懂，不多做解释。
8楼： >>参与讨论
作者： keter 于 2006-8-12 20:11:00 发布：
--------------------------------------------------------------------------------
最终贴－－进程调度
进程调度基本还是依靠UCOS自己的调度算法，修改的，就仅仅是在调度之间，把运行态优先级的任务进行运算，时间片使用完，就指向下一个进程。
Os_core.c
void OSTimeTick (void)
{
#if OS_CRITICAL_METHOD == 3 /* Allocate storage for CPU status register */
OS_CPU_SR cpu_sr;
#endif
OS_TCB *ptcb;
OSTimeTickHook(); /* Call user definable hook */
#if OS_TIME_GET_SET_EN > 0
OS_ENTER_CRITICAL(); /* Update the 32-bit tick counter */
OSTime++;
OS_EXIT_CRITICAL();
#endif
if((OSTCBCur->OSTSCurLen)>0)//如果时间片没有用完
{
if(--OSTCBCur->OSTSCurLen==0)//时间片在这次调度中用完了
{
if(OSTCBCur->OSTSnext != OSTCBCur)//如果优先级里面至少有两个进程（看上一篇文章来理解这个地方）
{
OSTCBCur->OSTSCurLen = OSTCBCur->OSTSLen;//把现在时间片用完的进程的时间补回来，以便下次调度
OSTCBPrioTbl[OSTCBCur->OSTCBPrio] = OSTCBCur->OSTSnext;//把该优先级的任务替换成下一个任务；
OSPrioCur=0;//把当前的运行优先级改成0，不然调度认为该优先级的任务没有结束，不执行任务调度，结果回到的地方，还是上一个时间片的任务，就死翘翘了！ }
问题：优秀级0不是最高的吗？
}
}
ptcb = OSTCBList; /* Point at first TCB in TCB list */
while (ptcb->OSTCBPrio != OS_IDLE_PRIO) { /* Go through all TCBs in TCB list */
OS_ENTER_CRITICAL();
if (ptcb->OSTCBDly != 0) { /* Delayed or waiting for event with TO */
if (--ptcb->OSTCBDly == 0) { /* Decrement nbr of ticks to end of delay */
if ((ptcb->OSTCBStat & OS_STAT_SUSPEND) == 0x00) { /* Is task suspended? */
if(OSTCBPrioTbl[ptcb->OSTCBPrio]==0)//如果该优先级只剩下一个进程了
{
OSRdyGrp |= ptcb->OSTCBBitY; /* No, Make task Rdy to Run (timed out)*/
OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX;
OSTCBPrioTbl[ptcb->OSTCBPrio]=ptcb;
ptcb->OSTSnext=ptcb;//指向自己
ptcb->OSTSprev=ptcb;//指向自己
}
else//增加了链表操作而已，自己看吧，把任务脱出链表而已
{
ptcb->OSTSnext=OSTCBPrioTbl[ptcb->OSTCBPrio]->OSTSnext;
OSTCBPrioTbl[ptcb->OSTCBPrio]->OSTSnext=ptcb;
ptcb->OSTSprev=OSTCBPrioTbl[ptcb->OSTCBPrio];
(ptcb->OSTSnext)->OSTSprev=ptcb;
}
} else { /* Yes, Leave 1 tick to prevent ... */
ptcb->OSTCBDly = 1; /* ... loosing the task when the ... */
} /* ... suspension is removed. */
}
}
ptcb = ptcb->OSTCBNext; /* Point at next TCB in TCB list */
OS_EXIT_CRITICAL();
}
}
该函数是UCOS调度的关键函数，也是FIFO最核心的东西。
我知道有些东西多余了，比如完全没有必要判断是否这个优先级只有一个任务。但是，这个是任务调度处理中，消耗的OS时间，也就是调度效率，我个人认为，调度占用时间越短越好。呵呵。
UCOS调度的文章就写到这里，信号量等其他地方修改还请大家自己动手了！
