在μC/OS-II上实现RMS调度算法

实验目的

一个课程作业，debug还蛮久的

参考实验目录下μCOSII下的代码 https://www.micrium.com/download/micrium_win32_kernel/

在μC/OS-II上实现RMS调度算法，并且打印每次进程切换的信息（任务之间有数据相关性和任务之间没有数据相关性），以及打印可能会发生的deadline violations

实验环境

IDE

visual Studio 2017 for Windows

MICRIUM PRODUCT

  • uC/OS-II  v2.92.13 OR uC/OS-III v3.06.02

  • uC/CPU    v1.31.01

  • uC/LIB    v1.38.02

实验步骤

更改每秒钟的tick数

方便进程调试

在os_cfg.h文件下将100u改为1u，每秒一个tick

1
2
3
#define OS_TICK_STEP_EN           1u   /* Enable tick stepping feature for uC/OS-View                  */
//#define OS_TICKS_PER_SEC        100u   /* Set the number of ticks in one second                        */
#define OS_TICKS_PER_SEC        1u

更改默认TCB结构

在ucos_ii.h文件下的os_tcb结构体中新增两个参数

1
2
3
4
5
typedef struct os_tcb {
  INT32U      runTime;        // 这个进程已经运行的时间
  INT32U      executionTime;      // 每个进程需要执行的时间  
    ...
}

取消无关进程的创建（61，62优先级的进程）

进入OSInit()函数，在os_core.c文件中注释掉Stat和Tmr进程

1
2
3
4
5
6
#if OS_TASK_STAT_EN > 0u
    //OS_InitTaskStat();                                           /* Create the Statistic Task                */
#endif
#if OS_TMR_EN > 0u
    //OSTmr_Init();                                                /* Initialize the Timer Manager             */
#endif

取消无关信息的打印

在os_cpu_c.c文件的1237行，取消打印running信息

1
2
3
#if (OS_MSG_TRACE > 0u)
    //OS_Printf("Task[%3.1d] '%s' Running\n", p_tcb->OSTCBPrio, p_tcb->OSTCBTaskName);
#endif

创建三个进程

声明三个进程的执行时间和周期

在main.c文件下

1
2
INT32U execution_times[] = { 1,2,2 };
INT32U periods[] = { 4,5,10 };

创建三个进程的任务代码

在main.c文件下创建三个Task函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static  void  Task1(void  *p_arg); // 声明
static void Task1(void *p_arg) 
{
    // 存放信号量pend和post的错误信息
  INT8U  err;
  // 执行时间
  int time = execution_times[0];
  // 将执行所需时间添加到TCB中
  OSTCBCur->executionTime = time;
  // 执行周期 
  int period = periods[0];
  // 第一个周期的开始时间
  int start_time = OSTimeGet();
  // APP_TRACE_DBG(("task 1 start at %d \n", start_time));
    // 设置第一个deadline为第一个周期结束
  int deadline = period;
  int end_time, delayed_time;
  while (1)          
  {
    //OSSemPend(pevent, 0u, &err); //0u代表会永远等待semaphore或者直到资源被释放
    while (OSTCBCur->runTime < time);
    //OSSemPost(pevent);
    end_time = OSTimeGet();
    delayed_time = deadline - end_time;
        // 出现了deadline violated的情况
    if (delayed_time < 0)
    {
      printf("Deadline Violated: Task %d expected to finish before %d but finished on %d\n", OSTCBCur->OSTCBPrio, deadline, end_time);
    }
        // 可能会存在延时了多个周期进程才完成的情况，用while语句来使得delayed_time为正数
    while (delayed_time < 0)
    {
      delayed_time = delayed_time + period;
    }
    OSTCBCur->runTime = 0;
        // deadline增加一个周期的时间
    deadline = deadline + period;
    OSTimeDly(delayed_time);
  }
}

创建三个进程所需的栈空间

在main.c文件下添加二维数组

1
static  OS_STK  UserTaskStk[3][APP_CFG_STARTUP_TASK_STK_SIZE];

创建进程

在main.c文件下注释掉实例代码，然后添加三个进程的创建代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
OSTaskCreateExt( Task1,                                          
    0,
    &UserTaskStk[0][APP_CFG_STARTUP_TASK_STK_SIZE -1],
    1u,
    1u,
    &UserTaskStk[0][0],
    APP_CFG_STARTUP_TASK_STK_SIZE,
    0u,
    (OS_TASK_OPT_STK_CHK | OS_TASK_OPT_STK_CLR));
  OSTaskCreateExt(Task2,
    0,
    &UserTaskStk[1][APP_CFG_STARTUP_TASK_STK_SIZE -1],
    2u,
    2u,
    &UserTaskStk[1][0],
    APP_CFG_STARTUP_TASK_STK_SIZE,
    0u,
    (OS_TASK_OPT_STK_CHK | OS_TASK_OPT_STK_CLR));
  OSTaskCreateExt(Task3,
    0,
    &UserTaskStk[2][APP_CFG_STARTUP_TASK_STK_SIZE -1],
    3u,
    3u,
    &UserTaskStk[2][0],
    APP_CFG_STARTUP_TASK_STK_SIZE,
    0u,
    (OS_TASK_OPT_STK_CHK | OS_TASK_OPT_STK_CLR));

添加代码记录当前TCB运行时间

记录运行时间以便与每个task函数中的 while (OSTCBCur->runTime < time); 跳出循环，执行结束，让出处理器。

在os_core.c的OSTimeTick()函数中修改

OSTimeTick()函数被OSTickW32 (LPVOID  p_arg)函数调用，用来进行tick中断，增加系统时间OStime，并且在每个OStime+1的时候，将TCB链表中的每个tcb的等待时间-1，如果等待时间变为0，就将其加入到就绪表中（OSRdyGrp和OSRdyTbl）

1
2
3
4
5
6
#if OS_TIME_GET_SET_EN > 0u
    OS_ENTER_CRITICAL();                                   /* Update the 32-bit tick counter               */
    OSTime++;
  OSTCBCur->runTime++;                 // 添加代码：当前正在运行的tcb的运行时间+1
    OS_TRACE_TICK_INCREMENT(OSTime);
    OS_EXIT_CRITICAL();

增加进程切换信息的打印代码

complete信息

在os_core.c文件下的OS_Sched (void)函数中增加打印信息的代码(下面代码的最后一行为添加的代码）

OS_Sched (void)函数主要是用来在一个进程放弃处理器的时候，通过OS_SchedNew()函数选出新的进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
OS_ENTER_CRITICAL();
  // 如果中断服务例程都结束了,CPU处于空闲，看是否有rdy的任务
    if (OSIntNesting == 0u) {                          /* Schedule only if all ISRs done and ...       */
        if (OSLockNesting == 0u) {                     /* ... scheduler is not locked                  */
            // 找到OSPrioHighRdy
            OS_SchedNew();
      // 根据priority为下标，找到HighRdyTCB
            OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy];
      // 如果当前的不是最高优先级的在运行，switch
            if (OSPrioHighRdy != OSPrioCur) {          /* No Ctx Sw if current task is highest rdy     */
#if OS_TASK_PROFILE_EN > 0u
                OSTCBHighRdy->OSTCBCtxSwCtr++;         /* Inc. # of context switches to this task      */
#endif
                OSCtxSwCtr++;                          /* Increment context switch counter             */
        // 增加打印信息的的代码
                printf( "%d\t%12s%6d%6d\n", OSTime, "Complete", OSPrioCur, OSTCBHighRdy->OSTCBPrio);

preempt信息

在os_core.c文件下的OSIntExit (void)函数中增加打印信息的代码(下面代码的最后一行为添加的代码）

OSIntExit (void)函数在每个时钟中断中，在OSTimeTick()过后被调用，在没有ISR和没有被lock的情况下，通过OS_SchedNew()函数判断是否有更高优先级的tcb进入了就绪表，如果有那么就进行进程切换OSIntCtxSw()   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void  OSIntExit (void)
{
#if OS_CRITICAL_METHOD == 3u                               /* Allocate storage for CPU status register */
    OS_CPU_SR  cpu_sr = 0u;
#endif    
  if (OSRunning == OS_TRUE) {
        OS_ENTER_CRITICAL();
        if (OSIntNesting > 0u) {                           /* Prevent OSIntNesting from wrapping       */
            OSIntNesting--;
        }
        if (OSIntNesting == 0u) {                          /* Reschedule only if all ISRs complete ... */
            if (OSLockNesting == 0u) {                     /* ... and not locked.                      */
        OS_SchedNew();
                OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy];
                if (OSPrioHighRdy != OSPrioCur) {          /* No Ctx Sw if current task is highest rdy */
#if OS_TASK_PROFILE_EN > 0u
                    OSTCBHighRdy->OSTCBCtxSwCtr++;         /* Inc. # of context switches to this task  */
#endif
                    OSCtxSwCtr++;                          /* Keep track of the number of ctx switches */
          // 打印，即将开始更高优先级的任务
          printf("%d\t%12s%6d%6d\n", OSTime, "Preempt", OSPrioCur, OSTCBHighRdy->OSTCBPrio);
                    ...
}

运行项目

运行代码截图如下（执行时间分别为1，2，2，周期分别为4，5，10）

运行问题分析

通过分析，在时间点8本应该任务3完成，然后跳转到任务1，即显示 8 complete 3 1 ，但是在截图中却显示，在时间点8，任务3被任务1抢断，直到时间点9的时候才和任务1一起执行结束，这导致了任务3的执行完成时间往后顺延了一个时间点，是存在问题的，即：

高优先级到来和低优先级任务完成同时到来的时候，将会执行高优先级抢占低优先级而不是低优先级完成过渡到高优先级。

Debug

通过观察源码可以知道，

  • preempt打印语句出现在OSIntExit(）中

  • 而OSIntExit只会在每个时钟中断中被调用，即被OSTickW32 ()调用，这个函数的主要作用是进入中断，进行时钟+1

  • OSIntExit ()函数在每个时钟中断中，在OSTimeTick()过后被调用，通过OS_SchedNew()函数判断是否有更高优先级的tcb进入了就绪表，如果有那么就进行进程切换OSIntCtxSw()。

  • 所以，当OSTime+1，低优先级的执行时间runTime+1过后，在OSTimeTick()总会检查是否有高优先级的任务就绪，在OSIntExit ()进行任务切换

  • 所以，就算低优先级任务的执行时间runTime已经达到了所需要的执行时间execution_time，即实际执行完毕的时候只要有高优先级任务就绪，就会被抢占，显示preempt，而在task()函数中，现在还在内部while的循环中，就被中断了，所以最后低优先级任务的结束时间也会往后拖延（时间为高优先级执行所需时间）

解决方法

在OS_SchedNew()函数中，新增一个逻辑，当一个任务的运行时间等于所需执行时间的时候（已经执行完毕），将不会选举出更高优先级的任务（即不会被抢占）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static  void  OS_SchedNew (void)
{
#if OS_LOWEST_PRIO <= 63u                        /* See if we support up to 64 tasks                   */
    INT8U   y;
    y             = OSUnMapTbl[OSRdyGrp];
    OSPrioHighRdy = (INT8U)((y << 3u) + OSUnMapTbl[OSRdyTbl[y]]);
    // 下面为增加代码
  if (OSTCBCur == NULL)
  {
    return;
  }
  if (OSTCBCur->runTime == OSTCBCur->executionTime)
  {
    OSPrioHighRdy = OSTCBCur->OSTCBPrio;
  }

重新执行代码后，问题解决

数据相关性的实现

通过信号量的pend和post实现任务互斥

在main.c文件声明并且创建信号量

1
2
3
4
5
6
7
static OS_EVENT * pevent;
...
int  main (void)
{
    ...
  pevent = OSSemCreate(1);                    // 创建信号量
    ...

在task1函数和task3函数下，增加pend和post代码，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
static void Task1(void *p_arg) 
{
  // 保存信号量pend和post的错误信息
  INT8U  err;
  ...
  while (1)          
  {
    OSSemPend(pevent, 0u, &err);
    while (OSTCBCur->runTime < time);
    OSSemPost(pevent);
        ...
  }
}// task3同理

执行结果

无数据相关性

执行时间分别为1，2，2，周期分别为4，5，10，优先级和任务名分别为1，2，3

注意到在时间8任务3完成的时候，直接过渡到任务1，而不是被任务1抢占

有数据相关性

举例1

执行时间分别为1，2，2，周期分别为4，5，10，优先级和任务名分别为1，2，3

在时间点4，本来1应该抢占3，但是由于数据相关性，交给3继续运行，在时间点5，任务3完成的时候，任务1再开始运行

举例2

执行时间分别为1，3，4，周期分别为3，6，9，优先级和任务名分别为1，2，3

由于任务1和任务3的数据相关性，会导致两个任务不能在该执行周期内完成任务

总结

  • 可以继续在SchedNew中实现新的算法，例如EDF之类的，系统里面有一个实时修改优先级的函数，记不到了
  • debug那里好折磨，看了好久