文章写作背景为《实时系统设计》课程实验二。写这篇东西掉了好多头发🤬。

源码在文章后。

实验介绍

实验目的：

  1. 熟悉嵌入式实时操作系统 μC/OS 代码结构。
  2. 理解、设计和实现 RM 和 EDF 等算法，调研相关技术。
  3. 在 μC/OS 上使用 VC 运行和调试设计的程序。

实验环境：

  1. 操作系统：μC/OS-II
  2. 软件：Microsoft Visual C++ 6.0

实验原理：

  1. RM 算法。RM(Rate Monotonic) 算法根据周期任务的释放频率，即周期的长短来分配任务的优先级，周期越短的任务优先级越高。当 Di=Ti 时，RM 算法是最优的固定优先级调度算法。如有两个实时任务τA（TA=25，CA=10）、τB（TB=40，CB=10）和τC（TC=100，CC=20），采用 RM 算法调度如下图所示：

image.png

  1. EDF 算法的实现。EDF(Earliest Deadline First) 算法按照实时任务的绝对截止时间来分配优先级，截止时间越近的优先级越高。EDF 算法是最优的动态优先级调度算法。如有两个实时任务τ1（C1=1，D1=3,T1=4）和τ2（C2=2,D2=4,T2=6），采用 EDF 算法调度如下图所示：

image.png

步骤

基本认识

熟读课件和相关源码片段，我们有以下基本认识：

  • 任务在 main.c 中创建，新建任务后会生成对应的 TCB 程序控制块（定义在 ucos-ii.h 中的 OS_TCB），并链接到 TCB 链表头中，链表尾是程序创建的空闲任务。
  • 实验程序我们需要手动模拟时间中断，以触发 OSTimeTick()
  • OSTimeTick() 会遍历任务链表，检查它们的延时。
  • OS_SchedNew() 是用来设定最高优先级的。默认实现是找就绪组就绪表。我们可以在里面动手脚，直接写我们的调度算法。
  • OSTimeTick() 调用 OSIntExit()，OSIntExit() 中又 OS_SchedNew()。所以每一次 OSTimeTick() 到来时，都有机会判断当前最高优先级的任务是什么。

为 TCB 块添加扩展

无论是 RM 算法还是 EDF 算法，都需要使用扩展的 TCB 块存储任务优先级数据。统一的扩展数据结构为不同算法的实现方式进行简化。

1
2
3
4
5
6
7
8
9
10
11
// ucos_ii.h
typedef struct tcb_ext_info{
	INT32U c;      // 保存C
	INT32U t;      // 保存T 周期
	INT32U d;      // 保存D 截止时间（EDF算法）
	INT32U rest_c; // 保存剩余工作时间
	INT32U rest_t; // 保存周期内剩余的事件
	INT32U rest_d; // 保存当前时间与截至时间的差值（EDF算法）
	INT32U task_id;// 任务ID
	INT8U is_pend; // 判断任务是否挂起（需要手动设置的标记位）
} tcb_ext_info;

任务创建

main 函数中首先要求输入一个任务数量 TasksNum，根据 TasksNum 进行迭代，持续获取每个任务的基本信息：

  1. C 计算时间
  2. T 周期
  3. D 截止时间（EDF 算法）

并对其余记录进行填充：

  1. 剩余计算时间
  2. 周期内剩余时间
  3. 剩余截止时间（EDF 算法）
  4. 任务 id
  5. 初始化 is_pend 为 0

timeSetEvent 将模拟时钟中断。

宏 LAB2_EDF 决定当前使用的是 EDF 算法还是 RM 算法。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int main(int argc, char **argv)
{
	int TasksNum,i,C,T;
#ifdef LAB2_EDF
	int D;
#endif

	tcb_ext_info* task_info_array = (tcb_ext_info*)malloc(sizeof(tcb_ext_info)*TasksNum);

	VCInit();

	// 输入提示
#ifdef LAB2_EDF
    printf("EDF算法实验。请输入任务数：\n");
#else
	printf("RM 算法实验。请输入任务数：\n");
#endif

	scanf("%d",&TasksNum);
    if (TasksNum<0)
	{
		printf("无效的输入!");
        return(1); 	
	}
	OSInit();
	
	for(i=0;i<TasksNum;i++){
#ifdef LAB2_EDF
		// EDF 每个任务三个参数
		scanf("%d %d %d",&C,&D,&T);
#else
		// RM 每个任务两个参数
		scanf("%d %d",&C,&T);
#endif
		
		task_info_array[i].c = C;
		task_info_array[i].t = T;

		task_info_array[i].rest_c = C;
		task_info_array[i].rest_t = T;

		task_info_array[i].task_id = i;
		task_info_array[i].is_pend = 0;  // 初始为不挂起

#ifdef LAB2_EDF
		task_info_array[i].d = D;
		task_info_array[i].rest_d = D;
#endif
			
		OSTaskCreateExt(
			FirstTask, 
			0, 
			&TaskStk[i+5][TASK_STK_SIZE-1], 
			i+5,  //设置互不冲突的数即可
			i,  // 任务ID
			&TaskStk[i+5][0], 
			TASK_STK_SIZE,
			(void *)&task_info_array[i],
			OS_TASK_OPT_NONE  // opt
		);
	}

	// 模拟时钟中断
	timeSetEvent(1000/OS_TICKS_PER_SEC, 0, OSTickISRuser, 0, TIME_PERIODIC);

	OSStart();	       
	return(0);
}

使用 OSTaskCreateExt 创建任务，传入扩展信息块的指针。

FirstTask 中为死循环，什么也不用做。

1
2
3
4
5
6
7
int FirstTask(void *pParam)
{
	for(;;)
	{
	}
	return(0); 
}

时钟中断

每次时钟嘀嗒到来时，完成以下操作：

  • 将当前运行任务的计算时间减 1
    • 如果任务计算完毕则挂起
  • 遍历 TCB 链表，将剩余周期减 1
  • 遍历 TCB 链表，将剩余截止时间减 1（EDF 算法）
  • 遍历 TCB 链表，检查是否有任务需要恢复。如果需要恢复则重置一下参数。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void  OSTimeTick (void)
{
    OS_TCB    *ptcb;
    /*********** 此位置源码省略 ***************/
	if (OSRunning == OS_TRUE) {
	
	/*********** 此位置源码省略 ***************/

		ptcb = OSTCBList;  /* Point at first TCB in TCB list               */

		// lab2 c--;
		if(OSTCBCur->OSTCBPrio != OS_TASK_IDLE_PRIO){
			if(((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->rest_c > 0){
				// 剩余有计算时间则减减
				((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->rest_c--;

				printf("%-10d 任务%d compute... 执行计算工作\n",OSTimeGet(),((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->task_id);
				if(((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->rest_c == 0){
					// 任务的计算时间归零，设置任务为挂起状态
					((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->is_pend = 1;
					printf("%-10d 任务%d complete! 挂起 \n",OSTimeGet(),((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->task_id);
					OSTaskSuspend(OSTCBCur->OSTCBPrio);
				}
			}
		}
        
        while (ptcb->OSTCBPrio != OS_TASK_IDLE_PRIO) {     /* Go through all TCBs in TCB list              */
            OS_ENTER_CRITICAL();

			// Lab2 所有的任务的剩余周期和剩余截止时间都减1（除了空闲任务后的两个任务）
			if(ptcb->OSTCBPrio<OS_TASK_IDLE_PRIO-2 ){ 
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->rest_t--;
#ifdef LAB2_EDF
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->rest_d--;
#endif
			}
			// 恢复任务（除了空闲任务后的两个任务）
			if( ptcb->OSTCBPrio<OS_TASK_IDLE_PRIO-2 && OSTimeGet() % ((tcb_ext_info*)ptcb->OSTCBExtPtr)->t == 0){
				// 当前时间为任务周期整数倍时恢复任务
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->rest_c=((tcb_ext_info*)ptcb->OSTCBExtPtr)->c;
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->rest_t=((tcb_ext_info*)ptcb->OSTCBExtPtr)->t;
#ifdef LAB2_EDF
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->rest_d=((tcb_ext_info*)ptcb->OSTCBExtPtr)->d;
#endif
				// 设置任务为未挂起状态
				((tcb_ext_info*)ptcb->OSTCBExtPtr)->is_pend = 0;

				OSTaskResume(ptcb->OSTCBPrio);
			}

			/*********** 此位置源码省略 ***************/
        }
    }
}

遍历的时候不要处理一些无关的任务，比如空闲任务，甚至统计任务等莫名奇妙的任务。所以有类似 ptcb->OSTCBPrio<OS_TASK_IDLE_PRIO-2 这种判定条件。

任务抢占输出

任务抢占将调用 OSIntExit()，如果最高优先级不是当前任务的优先级时判定为任务抢占。

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
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 */
					printf("%-10d Preempt 即将发生任务抢断\n",OSTimeGet());
#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 */
                    OSIntCtxSw();                          /* Perform interrupt level ctx switch       */
                }
            }
        }
        OS_EXIT_CRITICAL();
    }
}

调度算法实现

替换调度策略

OSStart 中通过 OS_SchedNew 获取当前最高优先级的任务。通过修改 OS_SchedNew 实现函数可进行调度算法的替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void  OSStart (void)
{
    if (OSRunning == OS_FALSE) {
        OS_SchedNew();  /* Find highest priority's task priority number   */
        OSPrioCur     = OSPrioHighRdy;
        OSTCBHighRdy  = OSTCBPrioTbl[OSPrioHighRdy]; /* Point to highest priority task ready to run    */
        OSTCBCur      = OSTCBHighRdy;
        OSStartHighRdy();   /* Execute target specific code to start task     */
    }
}

static  void  OS_SchedNew (void)
{
	Sched_Algorithm();
	// 把OS_SchedNew的内容注释掉
}

RM 算法与 EDF 算法

两种算法使用同一种扩展的数据结构 tcb_ext_info 好处在于代码改动非常小。与 RM 的区别在于找出的是距离截止时间最近的任务作为最高优先级任务。

算法基本流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
start
:获取TCB链表;
:初始化最小值min_prio;
while (优先级是否符合要求?)
	:进入临界区;
	if (该任务延迟时间为0?) then (yes)
		if (需要比较的优先级参数是否比当前存储的优先级min_prio小?) then (yes)
			:min_prio更新为最小值;
			:最高优先级任务更改为此任务;
		endif
	endif
	:退出临界区;
	:ptcb指向下一个TCB;
endwhile (no)
stop

以下代码通过宏 LAB2_EDF 切换使用不同的算法。

本文源码中涉及宏 LAB2_EDF 的文件

激活 EDF 算法记得在以下文件定义宏 LAB2_EDF：

  • main.c
  • os_core.c

问：为什么不单独引入一个独立的头文件方便激活或取消宏？
答：因为我电脑里的古董 VC6 做不到，它会崩溃🤬

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
void Sched_Algorithm(void){
	OS_TCB *ptcb;
	INT32U min_prio;
	tcb_ext_info* task_info;
	INT32U tmp;

	ptcb = OSTCBList;

	OS_ENTER_CRITICAL();
	min_prio = 2147483647; // INT32U MAX
	OSPrioHighRdy = OS_TASK_IDLE_PRIO;
	OS_EXIT_CRITICAL();


	while(ptcb->OSTCBPrio<OS_TASK_IDLE_PRIO-2){ //  && ptcb->OSTCBPrio != 1
		OS_ENTER_CRITICAL();
		if(ptcb->OSTCBDly==0 && ((tcb_ext_info*)ptcb->OSTCBExtPtr)->is_pend == 0 ){
			task_info = (tcb_ext_info*)ptcb->OSTCBExtPtr;
#ifdef LAB2_EDF
			tmp = task_info->rest_d;
#else
			tmp = task_info->t;
#endif
			if(tmp<min_prio){
				min_prio = tmp;
				OSPrioHighRdy = ptcb->OSTCBPrio;
			}

		}
		
		ptcb = ptcb->OSTCBNext;
		OS_EXIT_CRITICAL();
	}
}
改进提示

为了节省代码编写，RM 和 EDF 采用了同样的遍历链表的逻辑，但对于 RM 来说还可以进一步改进——不使用遍历的方式找到最高优先级，从而提高运行效率。

运行结果

RM 算法

image.png

案例 1 示例输出：

image.png

EDF 算法

image.png

案例 1 的示例输出：

image.png

后记

本实验的重要 参考文章 中的思路是：每次 OSTimeTick 计算该时刻任务剩余的周期数 rest_t，然后让任务自己延迟（OSTimeDly）自己，在下一个任务周期就绪。比如它的任务函数是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 任务函数
int FirstTask(void *pParam)
{
	// 此处位置代码省略
	for(;;)
	{
        while(((tcb_ext_info*)OSTCBCur->OSTCBExtPtr)->rest_c > 0){}
		OS_ENTER_CRITICAL();		
		// 此处位置代码省略
		OS_EXIT_CRITICAL();
		OSTimeDly(task_info->rest_t);
		
	}
	return(0); 
}

🐢⭐：这种实现会有点怪。

这样虽然会实现目的，但是我感觉这是任务自己参与去做调度这件事情。而且 OSTimeDly 还不准，一开始输出很正确，运行一会就陷入死循环或程序卡死了，甚至每次编译运行的结果都不一样🤬。

本篇文章通过 OSTimeTick 统一决定任务的挂起与恢复就绪，让任务函数本身更纯粹一些。当然，拓展的数据结构 tcb_ext_info 中可能会遗留一些没有用到的变量，读者可视情况删除。

实验源码

GitHub：uuanqin/ucosii-rm-edf-experiment: ucosii中实现RM和EDF任务调度算法实验源码。 (github.com)

Readme Card

本文参考