嵌入式操作系统的任务调度原理
1、先了解任务的状态(也可以认为任务的种类):
running:运行状态,任务获取到cpu资源,正在运行.系统中某一时刻只能有一个任务在运行.
ready:任务准备就绪,可以同时又多个ready任务.ready中拥有最高优先级的任务,下一个运行的任务就是它.
delay:任务主动延迟,放弃cpu的资源.
pend:阻塞状态,由于任务运行中,缺少必要条件,导致任务不能运行,需要等待某个条件,进入pend状态.
suspend:挂起状态,不参与任务调度,比如某个任务只需要开机执行一次,之后再也用不到.则可以在执行完成后让它进入到suspend状态.
2、下面谈一下ready状态,
在任务调度里面,最重要的就是从众多的准备好的任务中,挑选一个紧急的任务去执行.
众多任务:出在就绪(ready)状态的很多任务.
紧急任务:优先级最高的任务.
这需要我们在程序中逐个查询那个ready任务是最高的优先级,为了便于查询,在程序中设立了一个ready表.(如下图)
ready表中,是按照优先级区分的,比如下面有8个优先级:优先级0,优先级1,优先级2,,,,,,每个优先级下面又会挂载0个或多个任务.所以在程序中把每个优先级设置成一个链表,便于管理.
比如处在优先级0下面的任务,会统一存入一个链表中.
比如处在优先级1下面的任务,会统一存入一个链表中.
......
3、关于链表结构,不再补充,至于原因引用一个名人的话:这里地方太小,写不下.
比如:没有优先级为0的任务,那么优先级为0的任务所对应的链表就是空的,
这时,链表的头指针和尾指针都是空的.
4、比如:
优先级为5的任务有一个,
优先级为7的任务有两个,
那么他们对应各自的链表分别有一个节点和两个节点.
这里的链表采用的是双向链表.之所以采用双向链表是因为可以方便的从头到尾遍历,可以在知道某个节点后,找到它上一个或下一个节点.
5、有了对应的链表,就需要有操作链表的函数,
比如:
在链表中插入一个节点,
在链表中删除一个节点,
查看链表是否为空.
......
每个功能都对应一个函数,
这里是常规操作,就不写了.
6、因为有8个优先级,
通过上面就可以建立8个链表,
但是这样链表是独立的没有联系,为了把他们联系起来,建立了一个数组,
astrChain[8],把每个链表的根节点存入到这个数组中.
即8个链表的根节点,对应填入astrChain[0]~astrChain[7].
7、通过上面,ready表的组织形式大体确认.
然后就是如何从这么多链表中找到最紧要的任务,即找到优先级最高的任务.
可以依次查询数组astrChain[8]里面哪个不为空.
为了方便查询,设立了一个标志位.这样不仅方便,而且快捷.
下面图中的第二行就是标志位,这个标志位是一个变量,每个位为一个bit.
1、查找最紧急的ready任务.
上面我们说到设立了一个标志位,这个变量是U8类型的ucPrioFlag.
它有8个位,每一位代表了链表是否为空.
下面列举这个变量的几种情况,以及所对应的优先级:
2、列出所有的情况,共2的8次方,即256种.
3、我们把256种情况,及所对应的优先级写到一个数组中,
对应关系是,标志的值作为下标,优先级作为数组的内容.
通过搜索这个数组,就可以知道每种情况下ready所对应的最高优先级是哪个.
方便快捷.
在程序中的表现形式是:
typedef struct m_tasksched tab //任务调度表
{
M_CHAIN astrChain[PRIORI TYNUM]; //各优先级根节点
M_PRIOFLAG strFlag; //优先级标志
}M_TASKSCHEDTAB;
上面程序只是一个大概讲解,以后会有整体程序清单.
4、大家可能会问,这里是8个优先级,
如果是16个优先级,32个优先级或者更大256个的优先级会怎样呢?
大了不说,当优先级是16的时候,就有2的16种组合即65536,
要存储65536这样大的数组,显然是巨大的.
而且随着优先级数量的增加,这个存储空间是呈现指数形式增长的.
为解决这个问题,将ready表的标志进行分级.以256个优先级为例.
256可以分解为4*8*8.
所以如下图,
第三级4个位
第二级8个位
第一级8个位
同样,每一个优先级,与每个位之间也存在对应关系.
以优先级为143为例,转化对应的位:
143除以8再除以8=2 (舍弃小数) ,所以对应于第三极的bit2,把它置为1;
143除以8=17,对应第二级的bit17, 17除以8=2,对应第二级的Bite2,17-8*2=1,
对应Bite2的bit1,将第二级Byte2中的bit1置为1.
143除以8=17,对应第一级的Byte17,143-8*17=7,对应Byte17的bit7,将第一级Byte17中的bit7置为1.
查询ready表中的最高优先级办法,
分成4步,第一步是在第三级4bits里查询出第二优先级中拥有最高优先级的Byte,
第二步在第二级的这个Byte里查询出第一级中拥有最高优先级的Byte,第三步,从第一级的这个Byte里查询出拥有最高优先级的bit,最后一步,通过上面3步,找到第一级,第二级,第三级中所在的位置,计算出最高优先级.
查找到最高优先级后,就可以找到最高优先级链表的根节点,通过根节点遍历链表,可以找到最高优先级的任务节点.任务的节点是和TCB相互关联的,因此就可以找到对应的任务.
1、任务之间的切换是用汇编语言写成的.
每个任务都有一个寄存器组.里面装有这个任务的一些运行参数.
只要把任务的寄存器组恢复到cpu的寄存器中,就可以运行该任务了.
如果要停止运行该任务,需要把cpu的寄存器备份到任务的寄存器组中.
一般的任务调度是通过定时器中断实现的,
也就是定时器每进入中断,就会检测一下有没有需要切换的任务.
如果是用arm处理器,就需要学习arm寄存器相关的汇编语言.
如下面的例子:
MDS_TickContextSwitch:
@保存接口寄存器
STDMB R13!,{R0-R3,R12,R14}
@调用C语言TICK中断处理函数
LDR R0,=MDS_Ticklsr
MOV R14,PC
BX R0
@保存当前任务的堆栈信息
LDR R0,=gpstrCurTaskSpAddr
LDR R14,[R0]
MRS R0,SPSR
STMIA R14!,{R0}
LDMIA R13!{R0-R3,R12}
STMIA R14,{R0-R14}^
ADD R14,R14,#0X3C
LDMIA R13!,{R0}
STMIA R14,{R0}
@任务调度完毕,恢复将要运行任务现场
LDR R0,=gpstrNextTaskSpAddr
LDR R14,[R0]
LDMIA R14,{R0}
MSR SPSR,R0
LDMIB R14,{R0-R14}^
NOP
ADD R14,R14,#0X40
LDMIA R14,{R14}
SUBS PC,R14,#4
1、关于操作系统的任务切换,是核心的思想.
实现原理也很简单,就是用汇编写的一段调度程序.
cpu中有一组寄存器,
各个任务都有自己的寄存器组,
把响应的寄存器组复制到cup的寄存器中,就会运行对应的任务.