非抢占式调度算法的实现(非抢占式、不可剥夺式）

时间如冲冲流水，一转眼间都毕业快一年了。这一年里忙忙碌碌，却又碌碌无为。有时又总想，生亦何苦，死亦何哀。

 

也好久没更新博文了，之前做了个STM8的脱机编程器，使用了EMWIN，学习到了人家的消息机制。觉得自己编程在无法移植系统的情况下能不能自己设计个模块呢？就有了标题中的思想。

 

以下是我在论坛上发的。

 

 

    今天我也来个凑热闹讲讲操作系统，理论嘛，人人都懂，所以不讲了。

          首先想问大家，平时在8位机上会用到操作系统吗？还是一直都是裸奔？当然了我一直都是在祼奔。
  背景：
          为什么要装B还说要设计个OS，这么简单还不人人都去设计。事实也的确如此，难。不知道各位有没有遇到这样的情况：

        给公司写软件的时候，其核心内容设计好后公司总会有一些需要特别功能的产品，但仍基于设计好的核心，因此需要将此COPY两份，在其中一份中增加功能。如果公司这样的产品较多，那么你的文件夹中出现各种复件，如果核心软件优化了将对所有文件全部一一优化。自然有人说可以有预处理指令来增加功能模块，但这样的代码还是难于维护。。

重点来了，当软件初步完成后，维护时往往并没有设计时的激情，一是并没有设计时的思路，二总想换个思路重新写，或者压根就不想再碰！我是这样的，你呢？

因此我一直在找基于8位机的RTOS。

        再后来我使用了EMWIN设计了一个产品，它的消息机制真的很棒，我就想能不能通过消息来驱动任务。emwin的消息是针对窗口对象的。我只要将各个任务看作对象不也应该可以设计么？针对这样的想法就开始了设计之路。

===============================================================

____:  初步想法：
        给每个任务建立一个消息池，任务等待消息，等到消息后执行该任务。消息由其它任务或中断中给出。

____:  又来了想法：
        如果同时有任务等到消息到底谁先运行，所以在任务中建立优先级，以使同时等到消息的任务中优先级高的得到CPU的使用权？
        那么这样就得有一个调度器，在任务间进行切换。
        为此我给每个函数统一名称叫消息进程，以MP_xxx开头。

        即然用到优先级就会想到ucos中优先级查找机制，翻开ucos的书，其中一段让我的想法步入了正轨——不可剥夺型内核。

____:    什么是非抢占式优先级调度操作系统也叫不可剥夺型内核(来自ucosii ……)

        不可剥夺型内核要求每个任务自我放弃 CPU 的所有权。不可剥夺型调度法也称作合作型多任务，各个任务彼此合作共享一个 CPU。异步事件还是由中断服务来处理。中断服务可以使一个高优先级的任务由挂起状态变为就绪状态。但中断服务以后控制权还是回到原来被中断了的那个任务， 直到该任务主动放弃 CPU 的使用权时，那个高优先级的任务才能获得 CPU的使用权。
        不可剥夺型内核的一个优点是响应中断快。在讨论中断响应时会进一步涉及这个问题。在任务级，不可剥夺型内核允许使用不可重入函数。 函数的可重入性以后会讨论。每个任务都可以调用非可重入性函数，而不必担心其它任务可能正在使用该函数， 从而造成数据的破坏。 因为每个任务要运行到完成时才释放 CPU 的控制权。 当然该不可重入型函数本身不得有放弃 CPU 控制权的企图。使用不可剥夺型内核时，任务级响应时间比前后台系统快得多。 此时的任务级响应时间取决于最长的任务执行时间。
(省略部分请参阅ucos系统概念部分)

        好吧，我脸皮子就厚了，将MP_XXX命名修改成OS_XXX,毕竟这也叫操作系统嘛。重新整理了思绪如下：


整个设计为了节约内存，毕竟不是实时系统要求的不是响应速度。        
        1、既然是非抢占式OS，那么每个任务必须执行完后才会交出CPU的使用权。所以任务不应该是超级循环，并尽量控制任务执行时间。

        2、任务有就绪态、挂起态，运行态。

        3、每一个任务需要等待被执行的消息，可以接收多个消息，消息间可使用逻辑运算and or进行操作。并给每个任务分配消息等待超时时长。任务在规定时间内未等到消息也将进入就绪状态。如果建立任务时即未给出等待消息也未给出超时时长则任务立即进入就绪状态，否则进入挂起态。

        4、任务的调度由任务查找就绪表中最高优先级的任务并执行任务，等待该任务执行完后再重新调用调度器查找更高优先级的任务。

        5、需要在一个定时器刷新每个任务超时时间。并且就绪已超时的高优先级的任务。当然中断返回后返回到被中断的任务，在该任务结束后才会执行更高优先级任务。

 

即然发这个贴了自然是实现了，并不是连载，而是分开写有层次感，看得不会累。系统的命名仿照UCOS，让人不会那么陌生。

设计好的内核有如下功能：
1、支持最多16个任务，并且支持多少个任务就支持多少个优先级。如果系统中规定只有5个任务，那么只有0-4的优先级，因为未使用链表，使用数组，由优先级作为索引(只考虑节约内存)。

2、系统在初始化时建立一个空闲任务，优先级最低，并且一直处于就绪态，不得删除，不然会出现没有就绪任务时调试器会调用优先级为0的任务，不管该任务是否存在。后果无法预测。

3、系统可使能统计任务，优先级次低，用户可设定调用周期，如果使用统计函数，系统在初始化时会阻塞周期时长用于统计规定时间内总空闲计数值。cpu使用率=1-本次采样空闲计数器/周期内总计数值(阻塞时获得)


6、初次设计，没有给任务分配参数。也没有修改优先级，有删除任务，但请不要在中断中使用(如果删除被中断的任务，中断返回后将执行一个不存在的任务)。
即使是非抢占式操作系统也需要考虑重入问题，本文使用临界来解决。
(待补充)


系统性能：
        测试条件51单片机12MHZ仿真
        如果在任务建立时就计算好就绪任务的位置则任务切换时间为固定时长48us。为了节约内存并未计算好这些值，所以切换任务时长为52us。
        更多测试请看下面更新。



思想大概就是这样，接下来就是实现细节：
========================================================================================
先看数据组成：
typedef struct
{
  void                 (*Task)(void);                         //任务
  OS_MSG         OSTCBMsg;                        //任务所需要的消息  8位
  OS_MSG         OSTCBRecMsg;                        //任务接收到的消息
  int                 OSTCBOverTime;                        //任务超时时长
  int                 OSTCBCopyOverTime;                //备份超时时长，或者叫影子
  u8                  OSTCBLogicl;                        //接收到的消息逻辑操作   and  or
  u8                  OSTCBPrio;                        //任务优先级
}OS_TCB;
任务控制块，为了节约内存未使用链表，结合之前描述的消息使任务就续再看一下各个数据的注释大体能明白它们在做什么。



OS_TCB                         OSTCBTbl [OS_TASK_NUM];        //申请任务控制块
u8                          OSPrioTbl[OS_TASK_NUM];        //任务注册池，为0/1分别代码任务不存在和存在，删除任务只是将该任务注册池置0而已

========================================================================================

任务是如何建立的？初始化任务的各个参数，并将任务地址传到内核，由内核管理。
这里要注意的是哪些地方要进入临界，为什么？在注释中也写出了，
当然也有可能有些未考虑到的。大家注重思想就好。

暂时没有实现给任务传递参数，和任务这间的通信，但不难实现，就好像教科书上给出马的框框就可以让同学画徐悲鸿的马了。。。。
========================================================================================

OS_STA OS_CreateTask(void(*Task)(void),OS_MSG OSTCBMsg,char OSTCBLogicl,int OverTime,u8 OSTCBPrio)
{
        u8 OS_ITSTATUS;
        OS_TCB *PTcb=&OSTCBTbl[OSTCBPrio];                        //使用指针，节省建立时间
        
        OS_ENTER_CRITICAL();                                                  //防止在任务在中断中删除了此任务(想实现中断中不可删除任务）
        if((OSPrioTbl[OSTCBPrio]==1)||(OSTCBPrio>=OS_TASK_NUM))
        {   
                OS_EXIT_CRITICAL();
                return OS_PRIO_INVALID;                                          //该优先级被注册过,或者超过了任务数
        }
        
        OSPrioTbl[OSTCBPrio]                        =        1;                         //注册任务,进入临界，以防止被中断函数注册                                                        
        PTcb->OSTCBMsg                        =        OSTCBMsg;                //需要接收到的消息
        PTcb->OSTCBRecMsg                        =        0;                        //接收的消息
        PTcb->OSTCBLogicl                        =        OSTCBLogicl;        //接收消息方式
        PTcb->OSTCBOverTime                =        OverTime;                //超时时间
        PTcb->OSTCBCopyOverTime                =        OverTime;                //备份超时时间

        OS_EXIT_CRITICAL();                                                          //以上参数在其它函数中都可能被修改，所以需要关中断喽                                

        PTcb->Task                                =        Task;                        //用户任务
        PTcb->OSTCBPrio                        =        OSTCBPrio;                //任务优先级

        if((PTcb->OSTCBMsg==0)&&(PTcb->OSTCBOverTime)==0)OS_TaskRdy(OSTCBPrio);        //没有要等待的事件或者时间则任务立即进入就绪态
        
        return OS_OK;
}

注释详尽(有吗？)，具体细节请下载代码查看。




========================================================================================
既然称这个为系统，那么任务的调度自然是少不了，给它响亮的名字叫调度器，但这个函数叫任务切换。再给它包个皮就叫调度器了。
========================================================================================
OS_STA OS_TaskSw(void)
{
        u8 OSTCBPrio,y;
        u8 OS_ITSTATUS;
        y=OSUnMapTbl[OSRdyGrp];
        OSTCBPrio=(y<<2)+OSUnMapTbl[OSRdyTbl[y]];        //没有任务时返回0，0是最高优先级,使用同ucos，只是优先级只有16个，节约内存
        OS_ENTER_CRITICAL();                                        //进入临界防止刚判断任务存在就在中断函数中被删除
          if((OSPrioTbl[OSTCBPrio]==0)||(OSTCBPrio>=OS_TASK_NUM))
        {
                OS_EXIT_CRITICAL();
                return OS_PRIO_INVALID;
        }
        OSPrioSelf=OSTCBPrio;                                //当前运行的任务
        OS_EXIT_CRITICAL();
        OSTCBTbl[OSTCBPrio].Task();                //此处调用任务是开中断的，如果此时来了中断并将该任务删除，返回到这里将执行被删除的任务，
        return OS_OK;                                        //所以在中断中不能掉用删除任务函数
}
需要注意OSTCBTbl[OSTCBPrio].Task();调用任务后的中断是打开的，当运行该任务时进入中断，在中断中挂起该任务，或者删除该任务，那么中断返回后应该去哪？所以在中断中不允许使用挂起和删除函数，但未在软件加入限制，也会在今后修改

========================================================================================
不管哪个系统都需要用户编写部分代码。而非抢占式的不需要用户修改寄存器SP PC LR等。但任务是需要心跳的，这部分是和硬件有关的，不同的处理器自然也不一样。
这里是在51中结合protues仿真的，定时中断为1ms1次，具体多少可以在OS_CONFIG.h中进行设计每秒钟的中断次数。
========================================================================================

定时器的初始化函数则由用户编写。根据不同的MCU代码自然是不一样的。51如下：
void Timer_Init(void)
{
        u16 TimerValue;
        TimerValue=0xffff-1000000/OS_TICK_PRE_SEC;                         //使用定时方式1，最大时长65ms。所以用户情况设置此值，在.h文件中
        th=TimerValue>>8;
        tl=TimerValue;
        TMOD=0x01;
        TH0=th;
        TL0=tl;
        ET0=1;
        TR0=1;
        EA=1;
}

OS_TICK_PRE_SEC 留给用户设置的，即每秒应该中断的次数


void Timer_Exception(void) interrupt 1
{        
        TR0=0;
        TH0=th;
        TL0=tl;
        OS_TimeMsgPost();                                        //刷新每个任务的超时时长，递减的方式，并且就绪高优先级任务
        TR0=1;
}

void OS_TimeMsgPost(void)
{
        u8 i;
        u8 OS_ITSTATUS;
        OS_TCB *Ptr=OSTCBTbl;                                //用指针可加快速度
        for(i=0;i
        {
                OS_ENTER_CRITICAL();
                if(Ptr->OSTCBOverTime>0)                        //超时值大于0时刷新变量
                {
                        Ptr->OSTCBOverTime--;                  //防止其它任务将此值变成0后减成0xFF
                        OS_EXIT_CRITICAL();
                        if(Ptr->OSTCBOverTime==0)
                        {
                                OS_TaskRdy(i);                        //超时时间到，就绪对应任务        
                        }
                }
                OS_EXIT_CRITICAL();
                Ptr++;                                                   //刷新到下一个任务的超时标志
        }        
}

 

 

主要提高自己的编程乐趣。 ======================================================================================== 以下列出函数，具体细节请查看源代码： extern OS_STA         OS_CreateTask(void(*Task)(void),OS_MSG OSTCBMsg,char OSTCBLogicl,int OverTime,u8 OSTCBPrio);//任务建立 extern OS_STA         OS_DeleteTask(u8 OSTCBPrio);                        //删除任务 extern void         OS_ResumeTime(u8 OSTCBPrio);                        //重新将恢复任务超时时长 extern OS_STA         OS_TaskRdy(u8 OSTCBPrio)reentrant;                //将任务就绪，不可重入，不同的编译器可能处理不一样 extern OS_MSG         OS_MsgGet(u8 OSTCBPrio,OS_STA *err);        //获取指定任务消息 extern OS_STA         OS_MsgPost(u8 OSTCBPrio,OS_MSG OSMsg);        //发送消息给指定任务，并判断是否需要就绪 extern void         OS_TimeMsgPost(void);                                //刷新超时时长，就绪超时的任务，由定时器调用 extern OS_STA         OS_TaskSuspend(u8 OSTCBPrio);                        //挂起任务 extern OS_STA         OS_MsgClear(u8 OSTCBPrio,OS_MSG OSMsg);        //清除指定任务消息 extern OS_STA         OS_TaskSw(void);                                        //任务切换 extern OS_STA         OS_TaskSched(void);                                        //任务调度 extern void         OS_Start(void);                                                //开始系统运行 extern OS_STA         OS_Init(void);                                                //系统初始化，用于建立空闲任务和统计任务（可选） extern void         OS_StatInit(void);                                        //统计任务初始化（需要使能） ======================================================================================== 没有实践就没有发言权：请看例子： sbit LED1=P2^0; sbit LED2=P2^1; sbit LED3=P2^2; #define TASK_PRI_LED1 0                                 //定义任务的优先级 #define TASK_PRI_LED2 1 #define TASK_RPI_LED3 2 void LED1_Task(void)                                                //任务1就是闪烁LED1，运行它的条件由任务建立时给出，200ms 1次 {         LED1=~LED1;         OS_MsgPost(TASK_PRI_LED3,MBit1);                //给LED3发送消息0x01         OS_TaskSuspend(OSPrioSelf);                        //将自身挂起 } void LED2_Task(void)                                                //任务2就是闪烁LED2，运行它的条件由任务建立时给出，200ms 1次 {         LED2=~LED2;         OS_MsgPost(TASK_PRI_LED3,MBit2);                //给LED3发送消息0x02         OS_TaskSuspend(OSPrioSelf);                        //将自身挂起 } void LED3_Task(void)                                                //任务3就是闪烁LED3，运行它的条件由任务建立时给出，接收由任务1和任务2的消息才被调用 {         LED3=~LED3;         OS_TaskSuspend(OSPrioSelf);                        //将自身挂起 } void main(void) {         OS_Init();         Timer_Init();         OS_CreateTask(LED1_Task,         MBitNop,                0,                200,        TASK_PRI_LED1);                         //200ms后进入就绪态                         OS_CreateTask(LED2_Task,         MBitNop,                0,                200,        TASK_PRI_LED2);                         //200ms后进入就绪态                         OS_CreateTask(LED3_Task,        MBit1|MBit2,        OS_AND,                0,                TASK_PRI_LED3);         //等到Mbit1且还要等到Mbit2即0x03。因为是OS_AND与操作         OS_Start(); } 任务3由任务1和任务2一起驱动，在任务1或者任务2中的任一1个OS_MsgPost注释掉任务3将不会被执行。灯自然也不会闪烁，虽然是三个独立任务，并且不是同时点亮，但确是同步闪烁。 一共运行了四个任务(+空闲任务）和1个1ms中断的定时器的代码量和运行效果如下：1.5K左右的ROM空间和84字节的RAM空间。

上一篇:mega128的mpu6050dmp库使用心得

下一篇:用汇编语言实现单片机的循环灯控制