首页 > 代码库 > Nucleus PLUS任务调度

Nucleus PLUS任务调度

概述

Nucleus Plus内核(Kernel)的主要目的是管理实时任务的竞争执行(共享CPU),为应用提供各种便利,高速响应外部事件。Nucleus Plus的系统结构如图1所看到的,能够看出线程控制是整个内核的核心,通过邮箱、队列、管道来实现任务之间的通信,通过信号量、事件组和信号实现任务间的同步。


线程控制部件用来管理实时任务和高级中断服务的运行,它是Nucleus 嵌入式实时操作系统最核心的部分。为了控制运行过程,任务通常被分配一个优先级。任务优先级的范围从0到255,优先级0的优先权最高。除非抢占标示位被置为无效,否则低优先级的任务将被高优先级就绪的任务抢占。为保证对外部事件的实时性响应,Nucleus设计了高级中断服务HISR,它的优先级范围从0到2,当中优先级0的级别最高。

任务调度线程就负责抢占式实时任务和HISR的调度管理。每一个用户应用由多个任务组成,一个任务就是具有特定目的的半独立程序片段,任务处于五种状态之中的一个--执行、就绪、挂起、终止、完毕,如表1所看到的。任务具有不同的优先级,高优先级任务可以抢占低优先级任务,同优先级任务依照进入”就绪状态“的顺序调度,优先级从0-255递减。

表1 Nucleus任务的五种状态


状态意义

执行Executing

任务当前正在被CPU运行。

就绪Ready

任务就绪,可是还有一个任务当前正在执行。

挂起Suspended

任务由于服务等待需求而体眠。当需求满足时,任务变为就绪状态。默认情况下,新创建的任务都处于

终止Terminated

任务被终止。当任务处于这样的状态时,它将不再运行直到它被复位。

完毕Finished

任务完毕了.从入口函数中退出。任务处于这样的状态时,它将不再运行直到受到复位。

(一)任务调度算法

Nucleus调度程序用来决定是否要进行任务切换,假设须要切换的话,切换到哪个进程等。Nucleus实时操作系统的任务调度算法很easy,它包含时间片轮转算法和轮询算法。

时间片轮转算法是将同样优先级的任务都分配同样的时间片,当时间片用完后再转到下一个任务,轮流运行直到这个优先级的所有任务所有运行完成,然后再转到下一个优先级。轮询算法是在本优先级内的所有任务依照就绪时间的先后 顺序运行,当这个优先级的所有任务都运行完成后,再运行下一个优先级的任务。

再者,Nucleus实时操作系统具有可抢占性,进程调度的根据就是依照优先级从高到低顺序进行调度。当低优先级任务在运行时,高优先级任务就绪准备运行时则会抢占运行,迫使低优先级任务挂起。

Nucleus的调度时机包含:

(1)进程状态转换的时刻,即进程终止、进程睡眠;

(2)可执行队列中新添加一个进程时;

(3)当前进程的时间片用完;

(4)进程从系统调用返回到用户态;

(5)内核处理完中断后,进程返回到用户态。

(二)Nucleus PLUS任务管理

1,主要任务控制结构

Nucleus PLUS每个任务都有一个控制结构体称为线程控制块Thread Control Block(TCB),任务支持动态的创建和删除,TC通过一个双向链表TCD_Created_Tasks_List管理全部的任务,全局变量TCD_Total_Tasks表示已创建的总任务数。

TCD_Priority_List是一个大小为256的TCB指针数组TC_TCB (*TCD_Priority_List)[256](数组大小与Nucleus PLUS优先级数同样),数组元素按任务优先级索引。数组中的每一个元素都是某个优先级就绪任务链表的头。若某元素为空则表明那个优先级没有就绪任务。 对于每一个优先级的就绪任务列表,TCB是以双向列表的形式存储。即Nucleus PLUS维护一个指针数组来调度不同优先级的任务链表。

图2 TCD_Priority_List

2,任务优先级管理

Nucleus在进行任务切换时须要计算最高优先级,为了高速的计算就绪任务中最高的优先级,Nucleus PLUS引入了一种优先级分组+查找表机制。

2.1 TCD_Priority_Groups

任务的优先级从0到255,0的优先级别最高,255的优先级别最低。256个优先级分成32组,每组相应8个级别。比如第0组相应优先级0~7、第1组相应 8~15、...。用32位整型变量TCD_Priority_Groups的每一位标示优先级组是否有任务进入就绪状态,某位为1表示改组至少有一个任务就绪。

图3 TCD_Priority_Groups

2.2 TCD_Sub_Priority_Groups[]

子优先级数组TCD_Sub_Priority_Groups[32]标示一个组内详细的8个优先级,数组元素为8位整型,每一位相应组内一个优先级。如TCD_Sub_Priority_Groups[0]表示第0组(优先级0-7)任务的就绪状态,第0位为1表明优先级0的任务就绪、第7位为1表明优先级7的任务就绪。

图4 TCD_Sub_Priority_Groups

若任务的优先级为Tc_priority,   
该任务的子优先级掩码为:tc_sub_priority=1<<(tc_priority&7)。   
该任务的优先级组掩码为:tc_priority_group=1<<((tc_priority)>>3)。

2.3 TCD_Lowest_Set_Bit[]

TCD_Lowest_Set_Bit[]是一个查找表(元素预先已计算出),该表是8位整型数据的序号和数据8个位中第一个为1的位的位置(从高往底数)的,比如TCD_Lowest_Set_Bit[n]=value,n指8位整型数的值(就是序号),value指的是8个位中第一个为1的位置(从低往高数)。如Unsigned Char 7的二进制是0000 0111,第一个为1的位位0,value=http://www.mamicode.com/0,TCD_Lowest_Set_Bit[7] = 0。

如此便能够求得表TCD_Lowest_Set_Bit[256]。举例,8位整型数中位0为1的数据包含1、3、5、7、9、11、13、15,...,253,255,所以有:

TCD_Lowest_Set_Bit[1]= 0,   
TCD_Lowest_Set_Bit[3]= 0,   
TCD_Lowest_Set_Bit[5]= 0,   
TCD_Lowest_Set_Bit[7]= 0,   
...,   
TCD_Lowest_Set_Bit[253]= 0,   
TCD_Lowest_Set_Bit[255]= 0。  

 

2.4 任务创建和优先级管理的基本过程

任务优先级管理全局变量

UNSIGNED        TCD_Priority_Groups;   
DATA_ELEMENT    TCD_Sub_Priority_Groups[TC_MAX_GROUPS];   
UNSIGNED_CHAR  TCD_Lowest_Set_Bit[256] = {0,   
 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,   
 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1,   
 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,   
 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,   
 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,   
 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1,   
 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,   
 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3,   
 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0,   
 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1,   
 0, 2, 0, 1, 0};   
INT             TCD_Highest_Priority;//就绪状态任务的最高优先级  
i.创建一个task时(tcc.c)--TCC_Create_Task funtion

extern UNSIGNED         TCD_Priority_Groups;   
extern DATA_ELEMENT     TCD_Sub_Priority_Groups[TC_MAX_GROUPS];   
extern UNSIGNED_CHAR    TCD_Lowest_Set_Bit[];   
extern INT              TCD_Highest_Priority;      
task -> tc_priority = priority;   
task -> tc_priority_head = &(TCD_Priority_List[priority]);   
task -> tc_sub_priority = (DATA_ELEMENT) (1 << (priority & 7));//组内子优先级计算,0-7   
priority =  priority >> 3;//优先级组计算,有32个组   
task -> tc_priority_group = ((UNSIGNED) 1) << priority;//优先级组响应组标示位置1   
task -> tc_sub_priority_ptr = &(TCD_Sub_Priority_Groups[priority]);//指向子优先级起始  

ii. 恢复执行一个task时(tcc.c)--TCC_Resume_Task fuction

TCD_Priority_Groups = TCD_Priority_Groups | (task -> tc_priority_group);
//组号保存到全局变量      
*(task -> tc_sub_priority_ptr) = (*(task -> tc_sub_priority_ptr)) | task -> tc_sub_priority;
//组内值保存到全局变量   

iii.获取当前最高优先级(tcc.c)

if (TCD_Priority_Groups & TC_HIGHEST_MASK)   
      index =  0;   
else if (TCD_Priority_Groups & TC_NEXT_HIGHEST_MASK)   
  index =  8;   
else if (TCD_Priority_Groups & TC_NEXT_LOWEST_MASK)   
  index =  16;   
else  
  index =  24;   
  index =  index + TCD_Lowest_Set_Bit[(INT)((TCD_Priority_Groups >> index) & TC_HIGHEST_MASK)];//获取组号中1的最低排位,取值范围0~31   
  temp =  TCD_Sub_Priority_Groups[index];//与priority_group相应,有32个Sub_Priority_Groups,通过index查找到相应的Sub_Priority_Groups   
  TCD_Highest_Priority = (index << 3) + TCD_Lowest_Set_Bit[temp];//获取到实际的最高优先级  
获取到实际的最高优先级后,将最高优先级的任务挂入Tcd_priority_list[]、完毕调度后,该任务位会被清空,接着再次循环获取下一个任务优先级。