写在前面
本文开始为 RTOS 加入考虑任务优先级的自动调度算法，代码大部分参考野火。
本文主要是一篇学习笔记，加入了笔者自己对野火代码的梳理和理解。
一、基本思路
- 首先我们要知道，在 RTOS 中，优先级越高、越需要被先执行的的任务的优先级的数字越大。比如优先级数字为 5 的任务就要比 优先级数字为 1 的任务先执行。
- 在之前我们定义过就绪列表。所谓就绪列表，就是一个包含多条链表的数组，其中的每条链表又包含多个 TCB 作为列表的多个节点。现在，我们要把相同优先级的任务放入同一条链表中，而优先级越高的链表在就绪列表中下标越大。如图：
- 所以，我们需要把不在延时中的任务放进就绪列表中，然后按照优先级的大小进行切换执行；而如果任务进入了就绪状态，就将其从就绪列表中剔除。
二、代码实现
依据上面的思路，我们需要：
- 一个记录就绪任务的最高优先级的变量
- 一个设置就绪任务的最高优先级的变量的函数
- 一个清除记录就绪任务的最高优先级的变量的函数
- 一个让当前任务指针切换到最高优先级任务的函数
- TCB 中要增加一个优先级的参数
- 修改了 TCB 后，相关的任务创建函数需要修改
- 如果任务进入延时，把它的就绪状态清除
- 修改任务切换函数，使其找到优先级最高的任务执行
- 修改计时函数，当有任务的延时结束，使其变回就绪状态
1. 记录就绪任务的最高优先级的变量
初始化为空闲任务的优先级，也就是最低的优先级 0：
#define tskIDLE_PRIORITY ( ( UBaseType_t ) 0U )
static volatile UBaseType_t uxTopReadyPriority = tskIDLE_PRIORITY;
2. 设置、清除、选择就绪任务的最高优先级的变量的函数
① 通用方法
一种很朴素的想法是，使用上面定义的变量 uxTopReadyPriority 直接记录当前可执行的最高优先级。
- 设置函数：
#define taskRECORD_READY_PRIORITY( uxPriority ) \
{ \
if( ( uxPriority ) > uxTopReadyPriority ) \
{ \
uxTopReadyPriority = ( uxPriority ); \
} \
} /* taskRECORD_READY_PRIORITY */
- 选择优先级最高任务的函数：
#define taskSELECT_HIGHEST_PRIORITY_TASK() \
{ \
UBaseType_t uxTopPriority = uxTopReadyPriority; \
\
/* 寻找包含就绪任务的最高优先级的队列 */ \
while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) ) \
{ \
--uxTopPriority; \
} \
\
/* 获取优先级最高的就绪任务的TCB，然后更新到pxCurrentTCB */ \
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
/* 更新uxTopReadyPriority */ \
uxTopReadyPriority = uxTopPriority; \
} /* taskSELECT_HIGHEST_PRIORITY_TASK */
② 优化方法
下面这段话是野火教程的解释：
所谓优化方法，就是使用Cortex-M 内核一个计算前导零的指令
CLZ，所谓前导零就是计算一个变量（Cortex-M 内核单片机的变量为 32位）从高位开始第
一次出现 1 的位的前面的零的个数。比如：一个 32 位的变量 uxTopReadyPriority，其位 0、
位 24 和 位 25 均 置 1 ， 其 余 位 为 0 ， 具 体 见 。 那 么 使 用 前 导 零 指 令 __CLZ
(uxTopReadyPriority)可以很快的计算出 uxTopReadyPriority 的前导零的个数为 6。
如果 uxTopReadyPriority 的每个位号对应的是任务的优先级，任务就绪时，则将对应
的位置 1，反之则清零。那么图 10-2 就表示优先级 0、优先级 24 和优先级 25 这三个任务
就绪，其中优先级为 25的任务优先级最高。利用前导零计算指令可以很快计算出就绪任务
中的最高优先级为：( 31UL - ( uint32_t ) __clz( ( uxReadyPriorities ) ) ) = ( 31UL - ( uint32_t )
6 ) = 25。
- 设置函数
#define taskRECORD_READY_PRIORITY( uxPriority ) portRECORD_READY_PRIORITY( uxPriority, uxTopReadyPriority )
#define portRECORD_READY_PRIORITY( uxPriority, uxReadyPriorities ) ( uxReadyPriorities ) |= ( 1UL << ( uxPriority ) )
- 清除函数
#define taskRESET_READY_PRIORITY( uxPriority ) \
{ \
portRESET_READY_PRIORITY( ( uxPriority ), ( uxTopReadyPriority ) ); \
}
#define portRESET_READY_PRIORITY( uxPriority, uxReadyPriorities ) ( uxReadyPriorities ) &= ~( 1UL << ( uxPriority ) )
- 选择函数
#define taskSELECT_HIGHEST_PRIORITY_TASK() \
{ \
UBaseType_t uxTopPriority; \
\
/* 寻找最高优先级 */ \
portGET_HIGHEST_PRIORITY( uxTopPriority, uxTopReadyPriority ); \
/* 获取优先级最高的就绪任务的TCB，然后更新到pxCurrentTCB */ \
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
} /* taskSELECT_HIGHEST_PRIORITY_TASK() */
3. 修改 TCB 和相关的 TCB 创建函数
① 修改 TCB
增加 UBaseType_t uxPriority; /* 用于优先级 */ 参数：
typedef struct tskTaskControlBlock
{
volatile StackType_t *pxTopOfStack; /* 栈顶 */
ListItem_t xStateListItem; /* 任务节点 */
StackType_t *pxStack; /* 任务栈起始地址 */
/* 任务名称，字符串形式 */
char pcTaskName[ configMAX_TASK_NAME_LEN ];
TickType_t xTicksToDelay; /* 用于延时 */
UBaseType_t uxPriority; /* 用于优先级 */
} tskTCB;
typedef tskTCB TCB_t;
② 修改静态任务创建函数：
调用任务初始化函数并将任务添加到就绪列表：
TaskHandle_t xTaskCreateStatic( TaskFunction_t pxTaskCode, /* 任务入口 */
const char * const pcName, /* 任务名称，字符串形式 */
const uint32_t ulStackDepth, /* 任务栈大小，单位为字 */
void * const pvParameters, /* 任务形参 */
UBaseType_t uxPriority, /* 任务优先级，数值越大，优先级越高 */
StackType_t * const puxStackBuffer, /* 任务栈起始地址 */
TCB_t * const pxTaskBuffer ) /* 任务控制块 */
{
TCB_t *pxNewTCB;
TaskHandle_t xReturn;
if( ( pxTaskBuffer != NULL ) && ( puxStackBuffer != NULL ) )
{
pxNewTCB = ( TCB_t * ) pxTaskBuffer;
pxNewTCB->pxStack = ( StackType_t * ) puxStackBuffer;
/* 创建新的任务 */
prvInitialiseNewTask( pxTaskCode, pcName, ulStackDepth, pvParameters,uxPriority, &xReturn, pxNewTCB);
/* 将任务添加到就绪列表 */
prvAddNewTaskToReadyList( pxNewTCB );
}
else
{
xReturn = NULL;
}
/* 返回任务句柄，如果任务创建成功，此时xReturn应该指向任务控制块 */
return xReturn;
}
③ 修改任务初始化函数
主要是初始化了任务的优先级：
static void prvInitialiseNewTask( TaskFunction_t pxTaskCode, /* 任务入口 */
const char * const pcName, /* 任务名称，字符串形式 */
const uint32_t ulStackDepth, /* 任务栈大小，单位为字 */
void * const pvParameters, /* 任务形参 */
UBaseType_t uxPriority, /* 任务优先级，数值越大，优先级越高 */
TaskHandle_t * const pxCreatedTask, /* 任务句柄 */
TCB_t *pxNewTCB ) /* 任务控制块 */
{
StackType_t *pxTopOfStack;
UBaseType_t x;
/* 获取栈顶地址 */
pxTopOfStack = pxNewTCB->pxStack + ( ulStackDepth - ( uint32_t ) 1 );
//pxTopOfStack = ( StackType_t * ) ( ( ( portPOINTER_SIZE_TYPE ) pxTopOfStack ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
/* 向下做8字节对齐 */
pxTopOfStack = ( StackType_t * ) ( ( ( uint32_t ) pxTopOfStack ) & ( ~( ( uint32_t ) 0x0007 ) ) );
/* 将任务的名字存储在TCB中 */
for( x = ( UBaseType_t ) 0; x < ( UBaseType_t ) configMAX_TASK_NAME_LEN; x++ )
{
pxNewTCB->pcTaskName[ x ] = pcName[ x ];
if( pcName[ x ] == 0x00 )
{
break;
}
}
/* 任务名字的长度不能超过configMAX_TASK_NAME_LEN */
pxNewTCB->pcTaskName[ configMAX_TASK_NAME_LEN - 1 ] = '\0';
/* 初始化TCB中的xStateListItem节点 */
vListInitialiseItem( &( pxNewTCB->xStateListItem ) );
/* 设置xStateListItem节点的拥有者 */
listSET_LIST_ITEM_OWNER( &( pxNewTCB->xStateListItem ), pxNewTCB );
/* 初始化优先级 */
if( uxPriority >= ( UBaseType_t ) configMAX_PRIORITIES )
{
uxPriority = ( UBaseType_t ) configMAX_PRIORITIES - ( UBaseType_t ) 1U;
}
pxNewTCB->uxPriority = uxPriority;
/* 初始化任务栈 */
pxNewTCB->pxTopOfStack = pxPortInitialiseStack( pxTopOfStack, pxTaskCode, pvParameters );
/* 让任务句柄指向任务控制块 */
if( ( void * ) pxCreatedTask != NULL )
{
*pxCreatedTask = ( TaskHandle_t ) pxNewTCB;
}
}
④ 增加将新创建的任务添加到就绪列表的函数
- 修改任务个数计数器
- 调用任务插入就绪列表函数
static void prvAddNewTaskToReadyList( TCB_t *pxNewTCB )
{
/* 进入临界段 */
taskENTER_CRITICAL();
{
/* 全局任务计数器加一操作 */
uxCurrentNumberOfTasks++;
/* 如果pxCurrentTCB为空，则将pxCurrentTCB指向新创建的任务 */
if( pxCurrentTCB == NULL )
{
pxCurrentTCB = pxNewTCB;
/* 如果是第一次创建任务，则需要初始化任务相关的列表 */
if( uxCurrentNumberOfTasks == ( UBaseType_t ) 1 )
{
/* 初始化任务相关的列表 */
prvInitialiseTaskLists();
}
}
else /* 如果pxCurrentTCB不为空，则根据任务的优先级将pxCurrentTCB指向最高优先级任务的TCB */
{
if( pxCurrentTCB->uxPriority <= pxNewTCB->uxPriority )
{
pxCurrentTCB = pxNewTCB;
}
}
uxTaskNumber++;
/* 将任务添加到就绪列表 */
prvAddTaskToReadyList( pxNewTCB );
}
/* 退出临界段 */
taskEXIT_CRITICAL();
}
⑤ 修改将任务添加到就绪列表的函数
- 修改优先级就绪变量
- 将任务按照优先级大小插入对应的列表下标链表中：
/* 将任务添加到就绪列表 */
#define prvAddTaskToReadyList( pxTCB ) \
taskRECORD_READY_PRIORITY( ( pxTCB )->uxPriority ); \
vListInsertEnd( &( pxReadyTasksLists[ ( pxTCB )->uxPriority ] ), &( ( pxTCB )->xStateListItem ) ); \
3. 修改任务阻塞延时函数
- 把任务从就绪列表中移除（因为我们现在还没有延时链表，所以先不做这个）
- 将任务的优先级就绪变量清除
void vTaskDelay( const TickType_t xTicksToDelay )
{
TCB_t *pxTCB = NULL;
/* 获取当前任务的TCB */
pxTCB = pxCurrentTCB;
/* 设置延时时间 */
pxTCB->xTicksToDelay = xTicksToDelay;
/* 将任务从就绪列表移除 */
//uxListRemove( &( pxTCB->xStateListItem ) );
taskRESET_READY_PRIORITY( pxTCB->uxPriority );
/* 任务切换 */
taskYIELD();
}
4. 修改任务切换函数
- 寻找优先级最高的就绪任务执行即可：
/* 任务切换，即寻找优先级最高的就绪任务 */
void vTaskSwitchContext( void )
{
/* 获取优先级最高的就绪任务的TCB，然后更新到pxCurrentTCB */
taskSELECT_HIGHEST_PRIORITY_TASK();
}
- taskSELECT_HIGHEST_PRIORITY_TASK() 在上文已经定义
5. 修改计时函数
当有任务的延时结束，使其变回就绪状态：
void xTaskIncrementTick( void )
{
TCB_t *pxTCB = NULL;
BaseType_t i = 0;
const TickType_t xConstTickCount = xTickCount + 1;
xTickCount = xConstTickCount;
/* 扫描就绪列表中所有线程的remaining_tick，如果不为0，则减1 */
for(i=0; i<configMAX_PRIORITIES; i++)
{
pxTCB = ( TCB_t * ) listGET_OWNER_OF_HEAD_ENTRY( ( &pxReadyTasksLists[i] ) );
if(pxTCB->xTicksToDelay > 0)
{
pxTCB->xTicksToDelay --;
/* 延时时间到，将任务就绪 */
if( pxTCB->xTicksToDelay ==0 )
{
taskRECORD_READY_PRIORITY( pxTCB->uxPriority );
}
}
}
/* 任务切换 */
portYIELD();
}
三、结果展示
/* 创建任务 */
Task1_Handle = xTaskCreateStatic( (TaskFunction_t)Task1_Entry, /* 任务入口 */
(char *)"Task1", /* 任务名称，字符串形式 */
(uint32_t)TASK1_STACK_SIZE , /* 任务栈大小，单位为字 */
(void *) NULL, /* 任务形参 */
(UBaseType_t) 1, /* 任务优先级，数值越大，优先级越高 */
(StackType_t *)Task1Stack, /* 任务栈起始地址 */
(TCB_t *)&Task1TCB ); /* 任务控制块 */
/* 将任务添加到就绪列表 */
//vListInsertEnd( &( pxReadyTasksLists[1] ), &( ((TCB_t *)(&Task1TCB))->xStateListItem ) );
Task2_Handle = xTaskCreateStatic( (TaskFunction_t)Task2_Entry, /* 任务入口 */
(char *)"Task2", /* 任务名称，字符串形式 */
(uint32_t)TASK2_STACK_SIZE , /* 任务栈大小，单位为字 */
(void *) NULL, /* 任务形参 */
(UBaseType_t) 2, /* 任务优先级，数值越大，优先级越高 */
(StackType_t *)Task2Stack, /* 任务栈起始地址 */
(TCB_t *)&Task2TCB ); /* 任务控制块 */
/* 将任务添加到就绪列表 */
//vListInsertEnd( &( pxReadyTasksLists[2] ), &( ((TCB_t *)(&Task2TCB))->xStateListItem ) );
/* 启动调度器，开始多任务调度，启动成功则不返回 */
vTaskStartScheduler();
创建两个任务，在两个任务中分别对两个标志变量进行 电平变换-延时-电平变换 的循环操作，结果如下：
可以看到，两个标注变量几乎同时进行电平切换，CPU 没有被延时阻塞。
而且任务 2 由于设置的优先级比任务 1 高，所以电平先切换为高，优先级切换的功能添加成功。
后记
如果您觉得本文写得不错，可以点个赞激励一下作者！
如果您发现本文的问题，欢迎在评论区或者私信共同探讨！
共勉！
