RTOS系列4——任务调度

大家好，欢迎来到IT知识分享网。

任务调度

任务调度指的是操作系统内核根据某种方法，在多个用户任务中找到一个最佳任务进行运行。我们通过现实生活中的例子来理解。

例1：现在我们去买一杯茶颜悦色的奶茶，到了店门口发现有很多人，作为文明市民我们肯定是要排队的。在这种情况下奶茶店就是“内核”，每个客户就是“任务”。奶茶店的调度策略就是：不管你是帅哥还是美女，都排好队一个一个来。

这种调度策略优点是简单，缺点就是重要的事情不能优先处理。

例2：现在由于脚受伤去医院外科急诊科看病，挂号后开始排队。这时突然来了一个头部受重视的患者，此时医生会让轻微患者先等待一下，优先处理重视患者。在这种情况下医院就是“内核”，每个患者就是“任务”。医院的调度策略就是：优先处理重症患者，轻微患者排队轮流诊治。

这种调度策略优点是重要的任务可以优先处理保证了关系任务的实时性，缺点是调度算法较复杂。

根据上面的两个例子，大家认为任务操作系统内核调度策略更倾向于哪一种？

为了保证实时性，操作系统内核根据任务的优先级进行调度，这就意味着内核总是在当前的多个任务中选择优先级最高的任务运行。如果最高优先级存在多个任务，内核将轮流运行这个任务。

这就像一个人相亲一样，先相亲长得漂亮的，相亲对象同样漂亮就轮流相亲。由此可见内核还是个“势利眼”。

任务状态

操作系统中的任务有3种常见状态：

1、运行状态

2、就绪状态

3、等待状态

运行状态指的是处理器正在运行的任务，在单核处理器使用场景中，只有一个任务处在运行状态。由于任务在高速切换，用户感觉所有任务在并行，这就是微观串行宏观并行。

就绪状态指的是任务处在就绪状态，等待内核调度，一旦内核调度了该任务，该任务就处于运行状态。

等待状态指的是任务在等待某个事件，只有当事件发生后，任务才切换到就绪状态，如果等待的事情未发生，任务将不会被内核调度。

举个例子让大家理解一下任务的状态：驾校学车。驾校里有车，教练，学员。车就是“处理器”，教练就是内核，学员就是任务。我们假设驾校教练只有一辆车，进入车内练习的人就是处在运行状态，在旁边等待的学员就处在就绪状态，临时家里有事的学员请假了就是处在等待状态（只有把家里的事情处理完了才能来驾校）。此时由于报名费不一样学员分为VIP等级和普通等级，教练在调度学员上车时优先考虑VIP学员，等VIP学员都练完了，在轮到普通学员。（不知道有多少人的梦魇是科二科三）

事实上等待状态分为两种情况：

1、等待时间，延时等待

2、等待事件，等待信号，通知等事件。

由于这两种等待的实现策略不一样，一个是时间驱动，一个是事件驱动。我们把等待时间叫做等待状态，把等待事件叫挂起状态。

因此操作系统中的任务有4种常见状态：

任务调度如何实现

操作系统总是运行最高优先级任务，一旦有更高优先级任务就绪，操作系统将立即暂停当前任务运行更高等级任务，这种现象叫做任务抢占。

操作系统如何实现这种调度策略的呢？我们继续用驾校的例子来说明，教练根据报名费的不同将学员分成了VIP等级和普通等级，每个等级有若干个学员，然后制定了3张表格。

教练为正在排队的学员做了一张排队表：

有些学员会因为身体原因需要休息一定时间，教练为需要休息的学员做了一张休息表：

有些学员会因为家里有事处理需要请假，教练就还为请假的学员做了一张请假表：

教练只需要关注排队表，让排队表中的学员上车练习。

首先教练在排队表种检查优先等级，判断VIP等级中有没有学员，如果VIP等级有学员，教练优先让VIP的学员上车练习，等VIP学员都练习了（暂时放弃练习），才轮到普通学员上车练习。

如果有一个学员需要去厕所20分钟，教练就把这个学员的名字从排队表中移除，把他的名字放入休息表中(在此期间不会考虑让改学员上车练习)，20分钟后学员上完厕所回来，教练就把这个学员的名字从休息表中移除，把他的名字加入排队表中。假设此时正在练车的是普通学员，而这位休息的学员是VIP学员（并且希望练车），敬业的教练就要立即让普通学员停止练习，让高优先级学员优先练习。如果这位休息的学员事普通等级，那就让这个他继续等待，相同等级的学员轮流执行。

如果这时有一个学员家里有事要请假，教练就把这个学员名字从排队表中移除，把他的名字放入请假表中(在此期间不会考虑让改学员上车练习)。假设现在有一个普通学员正在练车，有一个请假的学员处理完事情来到驾校，教练会将这个学员的名字从请假表中移除，并根据其加入排队表中的相应等级中。如果这个新来学员事VIP等级，敬业的教练就要立即让普通学员停止练习，让高优先级学员优先练习。如果新来的学员事普通等级，那就让这个他继续等待，相同等级的学员轮流执行。

上面这个例子中提到了以下关键词：

1、排队表——教练只用关注排队表，在排队表中选择学员上车练习。

2、休息表——需要定时休息的学员，放入休息表，完成休息后放入排队表。

3、请假表——需要请假的学员，放入请假表。

4、优先等级——根据学员的报名费用，将学员分不同等级。

5、检查优先等级——教练只用在排队表中的最高等级中选择学员。

6、从排队表中移除，加入休息表——教练将需要定时休息的学员放入休息表。

7、从休息表中移除，加入排队表——教练将完成定时休息的学员放入排队表。

8、从排队表中移除，加入请假表——教练将需要请假的学员放入请假表。

9、从请假表中移除，加入排队表——教练将完成请假的学员放入排队表。

10、高优先级学员优先练习——高优先级的学员先练习，等高优先级学都暂时放弃练习，才轮到低优先级学员练习

11、相同等级的学员轮流执行——相同优先级的学员每人练习十分钟，轮流练习。

我们把上面关键词转换成操作系统中的关键词：

1、就绪表——操作系统内核会将就绪的任务存放在就绪表，内核总是从就绪表中找出最高优先级任务，并执行该任务。就绪表中存在优先级，同一个优先级的任务放在同一个列表项中。

2、等待表——操作系统内核会将需要延时等待的任务存放到等待表中，系统节拍会更新延时时间，内核会将完成延时等待的任务从等待表中移除，并将其加入到就绪表中。

3、挂起表——操作系统内核会将等待事件的任务放入挂起表，当等待的事件发生时操作系统内核会将该任务从挂起表中移除，并将其加入到就绪表中。

4、优先级表——操作系统中每个一任务优先级都对应优先级表中的一项，当该优先级下的任务数量不为0时，优先级表的该优先级为1 。

5、查找最高优先级——操作系统内核从优先级表中查找出最高优先级。

6、就绪表中移除，加入等待表——操作系统内核将任务从就绪状态改变成等待状态。

7、从等待表中移除，加入就绪表——操作系统内核将任务从等待状态改变成就绪状态。

8、从就绪表中移除，加入挂起表——操作系统内核将任务从就绪状态改变成挂起状态。

9、从挂起表中移除，加入就绪表——操作系统内核将任务从挂起状态改变成就绪状态。

10、高优先级的任务先运行——操作系统内核总是从就绪表中找出最高优先级任务，并执行该任务。

11、相同优先级的任务轮流运行——操作系统内核会轮流运行相同优先级的任务。

操作系统调度关系图如下：

就绪表是存放就绪任务信息的列表，就绪表通常有两个项目：优先级，任务成员。内核根据任务等级将任务放入就绪表中，就绪表内的任务成员的数据结构是一个双向链表。内核调度任务时，只需要关注就绪表，从就绪表中最高优先级项中选择任务并执行。就绪表框架如下：

等待表是存放等待任务信息的列表，等待表通常有两个项目：时间，任务成员。内核根据任务延时等待时间将任务放入等待表，等待表内的任务成员的数据结构是一个双向链表。就绪的任务如果需要延时，内核就将任务的状态从就绪状态改为等待等待，并把任务从就绪表移除加入到等待表。等待表中的任务延时时间完成后，内核就将任务从等待状态改为就绪状态，并把任务从等待表中移除加入到就绪表。等待表框架如下：

挂起表是存放挂起任务信息的列表，挂起表通常有两个项目：事件，任务成员。内核根据任务等待的事件将任务放入挂起表，挂起表内的任务成员的数据结构是一个双向链表。就绪任务如果需要等待某个事件时，内核就将任务从就绪状态改为挂起状态，并把任务从就绪表中移除加入到挂起表，当等待的事情发生后，内核将任务从挂起状态改为就绪状态，并把任务从挂起表移除加入到就绪表。挂起表框架如下：

内核根据任务的等级制定一个优先级表，根据该等级下是否有任务，来填充该优先级的状态，内核总是在最高优先级中选择任务执行，优先级表框架如下：

后面的文章将重点讲解优先级表，就绪表，等待表，挂起表。描述它们如何用C语言实现，已经它们的工作机制。

TCB设计

我们增加任务的TCB结构：

TCB中包含了栈指针，优先级。增加了任务状态列表，任务名。

任务状态列表用于维护任务的就绪状态和等待状态。任务名用于向用户显示任务的名称。

TCB结构和寄存器堆，任务栈的关系图如下：

静态区定义的任务TCB对象中的栈指针指向任务栈区的栈顶，任务栈区保存着寄存器堆的数据，寄存器堆中的PC值指向任务的代码区。

未完待续…
实时操作系统系列将持续更新

创作不易希望朋友们点赞，转发，评论，关注。

您的点赞，转发，评论，关注将是我持续更新的动力

作者：李巍

Github：liyinuoman2017