FreeRTOS的任务调度算法优化实现

心不留意外尘 2016-09-06

展开全文

http://blog.csdn.net/wbwwf8685/article/details/51999668

2016

在前一篇博文实时操作系统的任务睡眠中提到，FreeRTOS在任务调度的流程中，会用一个循环遍历的方法查找最高优先级就绪态任务，这是一种较为简单的方案，有较大的优化空间。本文先对FreeRTOS的任务调度算法进行分析，接着借鉴了UCOSII系统的两级查表方法，对该流程进行优化，最后用两种方法测试同一测试用例，可以清楚的看到优化的效果。

FreeRTOS任务调度算法分析

FreeRTOS中默认将任务分为5个优先级（0~4，该值可以修改宏configMAX_PRIORITIES以配置），所以需要一个5个元素的数组pxReadyTaskList[configMAX_PRIORITIES]，数组的每个元素表示对应优先级链表头结点，处于就绪态的具有相同优先级的任务会挂接到相同的链表上。其数据结构如下图所示：

实时操作系统都是运行最高优先级的任务，所以调度器的一项重要任务就是查找最高优先级就绪态任务。为此，FreeRTOS定义了一个全局变量uxTopReadyPriority，它记录了当前系统里最高优先级的就绪态任务。每当有新的任务从其它状态如睡眠转为就绪态时，系统就会判断，新任务的优先级是否高于uxTopReadyPriority，如果是的话，将uxTopReadyPriority修改为当前的任务优先级。

可是如果高优先级的任务从就绪转为睡眠，uxTopReadyPriority没有做相应的更新。而是在执行任务调度时，从第

uxTopReadyPriority项数组开始遍历，优先级从高到底，直到找到下一个就绪态的任务为止。

[cpp] view plain copy

print?

while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )
--uxTopReadyPriority;

这种方法在系统最多只支持5个优先级的时候似乎效率很好，但是有个小漏洞。考虑一下，假设系统里只有两个任务，一个优先级是1，一个优先级是255。两个任务频繁的切换，这样，每次当255的任务从就绪态转为睡眠，调度器要查找到下一个可以执行的任务，需要循环255次！

快速查找最高优先级任务

基于前面的分析，我们知道，FreeRTOS在高优先级从就绪态移除时，并没有及时更新最高优先级变量uxTopReadyPriority，而是留到了下次调度时用遍历的方式再次确定下一个最高优先级。很明显，这种循环遍历的方法不是最优方案。参考之前的一篇博文ucosii实时操作系统的任务调度，我们可以引入几个全局变量，将系统里的就绪态任务以bit位图的形式保存起来并实时更新，在需要确定最高优先级时，只需要两步查表就可以得到结果，其查找时间是固定的，不随任务的多少，以及不受优先级的跨度的影响，非常高效。需要做的修改有以下几处：

1 增加查表所需的数据结构

[cpp] view plain copy

print?

static unsigned long OSRdyGrp;
static unsigned char OSRdyTbl[32];
static unsigned long const OSMapTbl[] = {0x1, 0x2, 0x4, 0x8,
0x10, 0x20, 0x40, 0x80,
0x100,0x200, 0x400, 0x800,
0x1000, 0x2000, 0x4000, 0x8000,
0x10000, 0x20000, 0x40000, 0x80000,
0x100000, 0x200000, 0x400000, 0x800000,
0x1000000,0x2000000, 0x4000000, 0x8000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000};
char const OSUnMapTbl[] = {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};

需要注意，我们这里是假设系统支持0~255一共256个优先级，OSRdyGrp需要256/8 =32位的数值来对应于OSRdyTbl的32个表项，

因为FreeRTOS默认是优先级数值越大，优先级就越高，所以这里的OSUnMapTbl表格和UCOSII的不同，它的生成方法为：

[cpp] view plain copy

print?

#include <stdio.h>
int bit_map(int n)
{
int i;
for (i = 7;i >= 0;i--)
if (n & (1 << i))
break;
if (i < 0)
return 0;
return i;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
int tab[256]={0};
for (n=0;n<=0xff;n++)
{
tab[n] = bit_map(n);
}
for(n=0;n<=0xff;n++)
{
if(n%0x10==0)
printf("\n");
printf("%3d," , tab[n]);
}
printf("\n");
return 0;
}

在vTaskStartScheduler里将ildetask的对应的bitmap置位

[cpp] view plain copy

print?

OSRdyGrp |= 1;
OSRdyTbl[0] |= 1;

在任务转为就绪态时要将对应的bitmap置位

[cpp] view plain copy

print?

#define prvAddTaskToReadyQueue( pxTCB ) \
traceMOVED_TASK_TO_READY_STATE( pxTCB ) \
if( ( pxTCB )->uxPriority > uxTopReadyPriority ) \
uxTopReadyPriority = ( pxTCB )->uxPriority; \
OSRdyGrp |= OSMapTbl[(( pxTCB )->uxPriority >> 3)];\
OSRdyTbl[(( pxTCB )->uxPriority >> 3)] |= OSMapTbl[(( pxTCB )->uxPriority & 7)]; \
vListInsertEnd( ( xList * ) &( pxReadyTasksLists[ ( pxTCB )->uxPriority ] ), &( ( pxTCB )->xGenericListItem ) )

在任务从就绪态移除时将对应bitmap清掉

[cpp] view plain copy

print?

void prvRemoveFromReadyQueue( tskTCB * pxTCB)
{
OSRdyTbl[(( pxTCB )->uxPriority >> 3)] &= ~OSMapTbl[(( pxTCB )->uxPriority & 7)];
if (!OSRdyTbl[(( pxTCB )->uxPriority >> 3)])
OSRdyGrp &= ~OSMapTbl[(( pxTCB )->uxPriority >> 3)];
vListRemove( &( pxTCB->xGenericListItem ) );
}

最后就是任务调度时的查表了，在vTaskSwitchContext里

[cpp] view plain copy

print?

if (listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopReadyPriority ] ) ))
{
OSRdyTbl[(( pxCurrentTCB )->uxPriority >> 3)] &= ~OSMapTbl[(( pxCurrentTCB )->uxPriority & 7)];
if (!OSRdyTbl[(( pxCurrentTCB )->uxPriority >> 3)])
OSRdyGrp &= ~OSMapTbl[(( pxCurrentTCB )->uxPriority >> 3)];
if (pxCurrentTCB->uxPriority == uxTopReadyPriority)
{
if (OSRdyGrp & 0xff000000)
row = 24;
else if (OSRdyGrp & 0x00ff0000)
row = 16;
else if (OSRdyGrp & 0x0000ff00)
row = 8;
row = row + OSUnMapTbl[((OSRdyGrp >> row) & 0x000000ff)];
column = OSUnMapTbl[OSRdyTbl[row]];
uxTopReadyPriority = (row << 3) + column;
}
}

实验结果对比

实验方法如下，在STM32F103VET6平台上，创建2个任务，一个优先级为255，它阻塞在一个消息队列上，每收到消息就做一点简单的计算处理，并再次进入阻塞；另一个任务优先级为1，它不停的想消息队列发送消息。这个实验目的就是频繁的切换任务，每循环0xffff次，打印一条消息

[cpp] view plain copy

print?

static int a,b,c;
void do_something() //一个简单而无实际意义的函数，只为说明做了一点事情
{
a = b;b = c; c = a;
}
void Task1Func(void* p)
{
static int cnt = 0,round = 0;
int val = 0xfe;
while (1)
{
do_something();
if (cnt++ % 0xffff == 0)
USART_OUT(USART1,"Task 1 round %d\n",++round);
xQueueSendToBack(xQueue,&val,0xfff);
}
}
void Task2Func(void* p)
{
static int cnt = 0,round = 0;
int rec;
while (1)
{
xQueueReceive(xQueue,&rec,( portTickType )0xffff);
do_something();
if (cnt++ % 0xffff == 0)
USART_OUT(USART1,"Task 2 round %d\n",++round);
}
}

[cpp] view plain copy

print?

xQueue = xQueueCreate(1,sizeof(int));
xTaskCreate(Task1Func,( const signed char * )"Task1",64,NULL,1,NULL);
xTaskCreate(Task2Func,( const signed char * )"Task2",64,NULL,255,NULL);

先看原始的FreeRTOS查找算法的效率如何，

每循环0xffff次，需要大约9.5秒

再看修改为查表算法的运行结果：

每循环0xffff次，需要大约2.45秒。很显然，要高效很多，虽然这是个设计的很极端的实验，但也能说明问题。

看到这里，你可能在有个疑问，FreeRTOS作为一个十分优秀的开源实时操作系统，为何会采用一个如此简单低效的调度查优办法，而不像其它的RTOS大多都是采用查表的方法，以提高效率。楼主认为，FreeRTOS的设计者这样做是增加灵活性，可移植性，因为在FreeRTOSConfig.h文件中，有一个宏configMAX_PRIORITIES,它定义了系统支持的优先级数量，这个宏理论上可以改为大于1的任意数字。但是如果要采用查表的方法，就很难兼容了，例如，某个项目需求特殊，就非要需要支持1000个任务，那该如果查表？