引言
- 回顾一下上一章节内容，借助系统调用来实现销毁任务，那么销毁任务具体干了什么事呢？
- 销毁任务的本质就是释放任务所占用的资源，这个资源包括了两个方面，一个是内存资源，任务除了占用内存资源，还要占用处理器运行资源
- 想要搞清楚任务占用的处理器运行资源，那么就引出了任务状态
任务状态转换
- 一个任务从开始执行到执行结束肯定需要经历不同的状态，我们把进程划分 5 种状态
- 创建状态：进程在创建时需要申请一个任务对象，完成初始化的资源分配。把此时进程所处状态称为创建状态
- 就绪状态：进程已经准备好，已经分配到所需资源，只要分配到 CPU 就能够立即运行
- 运行状态：进程处于就绪状态被调度后，进程进入运行状态
- 阻塞状态：正在执行的进程由于某些事件（I/O 请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用
- 终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行
- 五种状态的状态转换图如下所示：
状态切换设计概要
- 在 进程调度预备开发 中，我们已经通过循环链表的方式实现了多任务并行执行，其特点是任务节点先进先出，这个其实是队列的特性，也就是说其实当时的任务其实是可以用任务队列实现的，然而我们却直接用链表实现，这么做的主要目的是想从本质上进行深入理解
- 今天，我们换成队列的方式（先进先出）思考任务的切换
- 原先我们只有一个任务队列的，但现在我们为每一种状态都准备一个队列（就绪队列、执行队列、等待队列）
- 任务状态切换的本质其实是任务节点在不同队列间的迁移
任务队列操作流程图
- 有了上面的状态切换的概要认知，接下来思考具体实现的详细过程，参见下图
- 首先，我们创建一个任务节点，任务节点创建成功并初始化后，将其加入空闲队列
- 如果该任务需要被执行，则将其从空闲队列中取出，加入就绪队列，等待调度
- 就绪队列中的任务节点就会被调度到执行队列中
- 在执行队列中的任务也可以被调度回就绪队列
- 有的任务因为需要等待外部事件或者时间，于是我们把它从执行队列中取出，放到等待队列中
- 待满足条件后又从等待队列中取出放到就绪队列中，等待调度执行，等待队列中的任务必须进入就绪队列才能被调度执行（任务只能从就绪状态转换成运行状态，不能从其它状态转换成运行状态）
- 在执行队列中的任务也可能执行结束，销毁，释放其占用资源
代码初步实现
- 关键：代码实现核心就是参考上面的任务切换流程图
- 任务切换的核心在于队列，所以我们要先创建各状态对应的队列（空闲队列、就绪队列、执行队列、等待队列）
- 因为前面任务切换使用的是链表，我们先将其改成队列方式实现，熟悉一下队列的使用，完整代码见：main.c、schedule.c、task.c、task.h。其中主要关键点如下
- 创建任务节点并插入任务队列
QueueInit(&TASK_QUEUE); static TASK_QUEUE_NODE taskQueueNodeA; taskQueueNodeA.task = &taskA; QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeA); static TASK_QUEUE_NODE taskQueueNodeB; taskQueueNodeB.task = &taskB; QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeB); static TASK_QUEUE_NODE taskQueueNodeC; taskQueueNodeC.task = &taskC; QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeC); static TASK_QUEUE_NODE taskQueueNodeD; taskQueueNodeD.task = &taskD; QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeD);
- 调度
void schedule(void) { if(TASK_QUEUE.length) { // 从 TASK_QUEUE 队列中取出一个任务节点 QUEUE_NODE* nodeTmp = QueueRemove(&TASK_QUEUE); current_task = (volatile TASK *)((TASK_QUEUE_NODE *)QUEUE_NODE(nodeTmp, TASK_QUEUE_NODE, QueueNode)->task); // 再把取出的任务节点重新放入队列 QueueAdd(&TASK_QUEUE, nodeTmp); TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR); // 找到 TSS tss->esp0 = (U32)(&(current_task->reg)) + sizeof(current_task->reg); // TSS.esp0 指向任务上下文数据结构 reg 的末尾 current_reg = (U32)(¤t_task->reg); // current_reg 指向任务上下文数据结构 reg 的起始位置 } }
- 熟悉了任务队列后，让我们继续本次实验，实验代码见：task.c、task.h、schedule.c、main.c
- 这次我们不光需要以前实现过的 4 个任务，从程序严谨设计，我们还需要实现一个空闲任务，用于保证在任何情况下，系统都有至少一个任务（空闲任务）执行，由于空闲任务比较特殊，我们把它放到 “task.c” 中实现
static TASK taskIdle = {0}; // 任务对象 #define IDLE_STACK_SIZE 512 static U08 taskIdle_stack[IDLE_STACK_SIZE]; // 任务私有栈 #include <print.h> static void TaskIdleFunc(void) // 任务执行函数 { static U32 count = 0; while(1) { if(count++ % 100000 == 0) { static U32 j = 0; asm volatile("cli"); SetCursorPos(0, 14); printk("TASK Idle: %d\n", j++); asm volatile("sti"); } } }
- 熟悉了一下任务队列的操作，接下来定义各个状态的任务队列，不过在此之前先在 “task.h” 中定义几个相关宏用于限制队列节点数量
#define MAX_RUNNING_TASK 3 // 最大运行状态任务数量 #define MAX_READY_TASK 3 // 最大就绪状态任务数量
- 在 “task.c” 中定义各个状态的任务队列，并在 “task.h” 中 extern 外部声明以供使用
QUEUE TASK_FREE_QUEUE; // 空闲任务队列 QUEUE TASK_READY_QUEUE; // 就绪任务队列 QUEUE TASK_RUNNING_QUEUE; // 执行任务队列 QUEUE TASK_WAIT_QUEUE; // 等待任务队列
- 在 “task.c” 中，实现一个任务初始化函数 TaskInit，初始化任务相关队列并传创建第一个任务节点，放到执行任务队列中
void TaskInit(void) { QueueInit(&TASK_FREE_QUEUE); // 空闲任务队列初始化 QueueInit(&TASK_READY_QUEUE); // 就绪任务队列初始化 QueueInit(&TASK_RUNNING_QUEUE); // 执行任务队列初始化 QueueInit(&TASK_WAIT_QUEUE); // 等待任务队列初始化 TaskCreat(&taskIdle, TaskIdleFunc, taskIdle_stack, IDLE_STACK_SIZE, "Idle"); // 创建第一个任务（空闲任务） taskIdleQueueNode.task = &taskIdle; QueueAdd(&TASK_RUNNING_QUEUE, (QUEUE_NODE *)&taskIdleQueueNode); // 将空闲任务节点添加到执行任务队列中 }
- 任务初始化之后，下面将前面实现过的 4 个任务节点放入空闲任务队列中
static TASK_QUEUE_NODE taskQueueNodeA; taskQueueNodeA.task = &taskA; QueueAdd(&TASK_FREE_QUEUE, (LIST_NODE *)&taskQueueNodeA); static TASK_QUEUE_NODE taskQueueNodeB; taskQueueNodeB.task = &taskB; QueueAdd(&TASK_FREE_QUEUE, (LIST_NODE *)&taskQueueNodeB); static TASK_QUEUE_NODE taskQueueNodeC; taskQueueNodeC.task = &taskC; QueueAdd(&TASK_FREE_QUEUE, (LIST_NODE *)&taskQueueNodeC); static TASK_QUEUE_NODE taskQueueNodeD; taskQueueNodeD.task = &taskD; QueueAdd(&TASK_FREE_QUEUE, (LIST_NODE *)&taskQueueNodeD);
- 原先的启动任务的第一个任务要由 taskA 变成 taskIdle，此时不需要参数 task0 了，第一个任务固定为空闲任务 taskIdle
void TaskStart(void) { current_task = &taskIdle; // 当前任务指针指向空闲任务 TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR); // 找到 TSS tss->esp0 = (U32)¤t_task->reg + sizeof(current_task->reg); // TSS.esp0 指向空闲任务 taskIdle 的上下文数据结构 reg 的末尾 current_reg = (U32)¤t_task->reg; // current_reg 指向空闲任务 taskIdle 上下文数据结构 reg 的起始位置 enable_int0x20(); // 取消屏蔽 0x20 号时钟中断 asm volatile("sti"); // 执行任务前必须开中断 SWITCH_TO(current_task); // 切换到空闲任务 taskIdle 执行 }
- 梳理一下现在的代码进度，目前我们已实现 4 个普通任务 ABCD 以及一个特殊空闲任务，普通任务 ABCD 已被添加到就空闲列中，特殊空闲任务被加入到执行队列中，最后跳转到空闲任务 taskIdle 执行
- 显而易见，这个时候如何运行程序，只会执行空闲任务 taskIdle，而 4 个普通任务 ABCD 并没有参与调度执行（调度函数 schedule 还是使用原来的 TASK_QUEUE 队列，而此队列为空，已被抛弃），于是我们先删除原来的任务队列 TASK_QUEUE 相关代码
- 接下来实现将空闲任务队列中的任务节点迁移到就绪任务队列中，就把这个函数放到 “schedule.c” 中吧
static void Free2Ready(void) { QUEUE_NODE* node = NULL; // 当空闲任务队列不为空 且 就绪任务队列长度 < 就绪任务队列最大长度 while((QueueLength(&TASK_FREE_QUEUE) > 0) && (QueueLength(&TASK_READY_QUEUE) < MAX_READY_TASK)) { // 取空闲任务队列中一个任务节点 node = QueueRemove(&TASK_FREE_QUEUE); // 放到就绪任务队列中 QueueAdd(&TASK_READY_QUEUE, node); } }
- 接下来实现将就绪任务队列中的任务节点迁移到执行任务队列中，函数依旧放到 “schedule.c” 中
static void Ready2Running(void) { QUEUE_NODE* node = NULL; // 当就绪任务队列不为空 且 执行任务队列长度 < 执行任务队列最大长度 while((QueueLength(&TASK_READY_QUEUE) > 0) && (QueueLength(&TASK_RUNNING_QUEUE) < MAX_RUNNING_TASK)) { // 取就绪任务队列中一个任务节点 node = QueueRemove(&TASK_READY_QUEUE); // 放到执行任务队列中 QueueAdd(&TASK_RUNNING_QUEUE, node); } }
- 这两个函数都实现好了，接下来我们就可以修改调度程序 schedule 函数了，实现思路如下，先将空闲任务队列中的任务节点迁移到就绪任务队列中，再将就绪任务队列中的任务节点迁移到执行任务队列中，接下来从执行任务队列中取出一个任务节点并执行该任务，再将该任务节点重新添加到执行任务队列中
void schedule(void) { QUEUE_NODE* node = NULL; Free2Ready(); // 将空闲任务队列中的任务节点迁移到就绪任务队列中 Ready2Running(); // 将就绪任务队列中的任务节点迁移到执行任务队列中 // 从执行任务队列中取出一个任务节点并执行该任务，再将该任务节点重新添加到执行任务队列中 node = QueueRemove(&TASK_RUNNING_QUEUE); current_task = (volatile TASK *)((TASK_QUEUE_NODE *)QUEUE_NODE(node, TASK_QUEUE_NODE, QueueNode)->task); QueueAdd(&TASK_RUNNING_QUEUE, node); TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR); // 找到 TSS tss->esp0 = (U32)(¤t_task->reg) + sizeof(current_task->reg); // TSS.esp0 指向任务上下文数据结构 reg 的末尾 current_reg = (U32)(¤t_task->reg); // current_reg 指向任务上下文数据结构 reg 的起始位置 }
- 好了，代码先实现到这里，运行一下看看效果
实现真正的任务销毁
- 本次实验代码见：task.c、task.h、queue.c、queue.h、syscall.c、main.c
- 上一章节中，到了最后我们都没实现销毁任务功能，仅仅使用打印字符串替代，现在，我们来实现真正的任务销毁函数
- 其原理就是将当前任务节点从执行任务队列中删除，我们将该函数实现放到 “task.c” 中，具体实现如下：
E_RET TaskDestory(void) { QUEUE_NODE* node = NULL; // 把当前任务节点从执行任务队列中取出 node = QueueTailRemove(&TASK_RUNNING_QUEUE); if(NULL == node) return E_ERR; return E_OK; }
- 由于在调度函数 schedule 中当前任务节点已经被重新添加到队列尾，所以此时我们实际要删除的是队列尾节点，不过队列操作中并没有删除队列尾节点的接口函数，需要补充实现
QUEUE_NODE* QueueTailRemove(QUEUE* queue) { QUEUE_NODE* ret = NULL; if(queue->length > 0) { ret = queue->list.prev; ListDelNode(ret); queue->length--; } return ret; }
- 任务销毁函数 TaskDestory 实现后，把它放到 “syscall.c” 中调用
void Int0x80Handle(U32 eax) { if(0 == eax) { TaskDestory(); } }
- 整个任务销毁过程都已经实现了，想要测试代码实现是否 OK，还需要如下改动，其目的是模拟 task A 结束运行
void TaskAFunc(void) // 任务执行函数 { static U32 count = 0; while(1) { if(count++ % 100000 == 0) { static U32 j = 0; asm volatile("cli"); SetCursorPos(0, 6); printk("TASK A: %d\n", j++); asm volatile("sti"); } if(count > 1000000) // 执行一定时间后跳出 while(1) 循环 break; } }
- 完毕，来看看效果，如下图，原本共三个同时执行（任务 A B 以及空闲任务），后来任务 A 执行结束，于是新增执行任务 C
引入任务优先级
- 前面的调度策略有个非常大的问题，那就是如果先被调度的任务不执行结束，那么后面的任务就永远无法得到执行
- 这显然是一个无法忽视的问题，那么，如何解决这个问题呢？
- 解决方案：为每个任务提供优先级，使得每个任务都有机会执行；优先级的高低决定任务执行时间的长短
- 首先，我们给 struct TASK 结构体新增三个成员：priority(优先级)、current(记录当前已执行的时间片数)、total(每次任务执行的总时间片数)
typedef struct TASK { U32 id; // 任务 id U08* name; // 任务名称 U08* stack_addr; // 任务栈基址 U16 stack_size; // 任务栈大小 REG reg; // 任务上下文，即任务执行状态下所有寄存器的值 TASK_FUNC task_entry; // 任务函数入口 U08 priority; // 优先级 U32 current; // 记录当前已执行的时间片数 U32 total; // 每次任务执行的总时间片数 } TASK;
- 如下图所示，我们基于优先级重新设计一下调度策略。
- 首先，创建任务后，用 256 减去 任务优先级 priority, 得到的结果赋值给 total, priority 的取值范围是 [0, 255], 那么 total 的范围就是 [1, 256], 而 total 就决定着每次任务执行的总时间片数，priority 值越小，即 total 值越大，任务每次执行的时间就越长
- 在任务进入就绪队列时，我们将 current 初始化设置为 0
- 在进入执行队列被调度执行时，如果 current < total, 就让 current 每个时钟中断累加一次
- 直到 current 值累加到与 total 值相等，那么就将该任务放回就绪队列中，并从就绪队列重新取一个任务执行
基于任务优先级的代码实现
- 完整代码见：task.c、task.h、schedule.c、main.c
- 精简一下流程，取消空闲任务队列，创建任务后可以直接放入就绪任务队列中，那么也省去了调度 schedule 函数中的将空闲任务队列中的任务节点迁移到就绪任务队列中这一步操作
- 原先的执行队列是用于多任务同时执行，现在的调度策略并不需要再借助执行任务队列，每次只执行一个任务，当 current == total 时，就可以从就绪任务队列中重新取任务执行了（原先的调度策略无法判断一个任务何时需要切换到另一任务，只能强行在执行队列中循环执行，每个任务执行时间片数固定）
- 于是，删除执行任务队列和空闲任务队列
// QUEUE TASK_FREE_QUEUE; // 空闲任务队列 // QUEUE TASK_RUNNING_QUEUE; // 执行任务队列
- 删除这两个队列需要带来下面一系列的改动
- 任务初始化，原空闲任务创建后放到执行任务队列，现在放到就绪任务队列中
void TaskInit(void) { QueueInit(&TASK_READY_QUEUE); // 就绪任务队列初始化 QueueInit(&TASK_WAIT_QUEUE); // 等待任务队列初始化 // 创建第一个任务（空闲任务） TaskCreat(&taskIdle, TaskIdleFunc, taskIdle_stack, IDLE_STACK_SIZE, "Idle", 255); // 将空闲任务节点添加到就绪任务队列中 static TASK_QUEUE_NODE taskIdleQueueNode; // 空闲任务队列节点 taskIdleQueueNode.task = &taskIdle; QueueAdd(&TASK_READY_QUEUE, (QUEUE_NODE *)&taskIdleQueueNode); }
- 调度，删除 Free2Ready 函数和 Ready2Running 函数，调度函数 schedule 中原先从执行队列中获取任务改为从就绪队列中获取任务
void schedule(void) { QUEUE_NODE* node = NULL; // 从执行任务队列中取出一个任务节点并执行该任务，再将该任务节点重新添加到执行任务队列中 node = QueueRemove(&TASK_READY_QUEUE); current_task = (volatile TASK *)((TASK_QUEUE_NODE *)QUEUE_NODE(node, TASK_QUEUE_NODE, QueueNode)->task); QueueAdd(&TASK_READY_QUEUE, node); TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR); // 找到 TSS tss->esp0 = (U32)(¤t_task->reg) + sizeof(current_task->reg); // TSS.esp0 指向任务上下文数据结构 reg 的末尾 current_reg = (U32)(¤t_task->reg); // current_reg 指向任务上下文数据结构 reg 的起始位置 }
- 任务销毁，任务销毁也由原来的从执行队列中删除当前任务节点改为从就绪任务队列中删除
E_RETTaskDestory(void)
{ QUEUE_NODE* node = NULL; // 把当前任务节点从就绪任务队列中取出，当前任务节点在队列尾 node = QueueTailRemove(&TASK_READY_QUEUE); if(NULL == node) return E_ERR; return E_OK; }
- 该删的都删掉了，接下来就是针对新增功能的实现
- 创建任务函数 TaskCreat，加入优先级 priority 传参
E_RET TaskCreat(TASK* task, TASK_FUNC pFunc, U08* stackAddr, U16 stackSize, U08* name, U08 priority) { ... task->priority = priority; task->total = 256 - priority; current_task->current = 0; ... }
- 修改调度实现
void schedule(void) { QUEUE_NODE* node = NULL; if(current_task->current < current_task->total) current_task->current++; else { current_task->current = 0; // 从就绪任务队列中取出一个任务节点并执行该任务，再将该任务节点重新添加到就绪任务队列中 node = QueueRemove(&TASK_READY_QUEUE); current_task = (volatile TASK *)((TASK_QUEUE_NODE *)QUEUE_NODE(node, TASK_QUEUE_NODE, QueueNode)->task); QueueAdd(&TASK_READY_QUEUE, node); TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR); // 找到 TSS tss->esp0 = (U32)(¤t_task->reg) + sizeof(current_task->reg); // TSS.esp0 指向任务上
下文数据结构 reg 的末尾
current_reg = (U32)(¤t_task->reg); // current_reg 指向任务上下文数据结构 reg 的起始位置 } } void Int0x20Handle(void) { schedule(); write_m_EOI(); }
- 想要测试，依旧还需要模拟几个任务
TaskCreat(&taskA, TaskAFunc, taskA_stack, 512, "Task A", 50); // 创建任务 TASK A TaskCreat(&taskB, TaskBFunc, taskB_stack, 512, "Task B", 100); // 创建任务 TASK B TaskCreat(&taskC, TaskCFunc, taskC_stack, 512, "Task C", 150); // 创建任务 TASK C TaskCreat(&taskD, TaskDFunc, taskD_stack, 512, "Task D", 200); // 创建任务 TASK D static TASK_QUEUE_NODE taskQueueNodeA; taskQueueNodeA.task = &taskA; QueueAdd(&TASK_READY_QUEUE, (QUEUE_NODE *)&taskQueueNodeA); static TASK_QUEUE_NODE taskQueueNodeB; taskQueueNodeB.task = &taskB; QueueAdd(&TASK_READY_QUEUE, (QUEUE_NODE *)&taskQueueNodeB); static TASK_QUEUE_NODE taskQueueNodeC; taskQueueNodeC.task = &taskC; QueueAdd(&TASK_READY_QUEUE, (QUEUE_NODE *)&taskQueueNodeC); static TASK_QUEUE_NODE taskQueueNodeD; taskQueueNodeD.task = &taskD; QueueAdd(&TASK_READY_QUEUE, (QUEUE_NODE *)&taskQueueNodeD);
- OK，成功展示，ABCD 四个任务执行逻辑完全相同，仅优先级不同，优先级 A > B > C > D，其执行结果符合我们的预期，任务执行时间 A > B > C > D
优化
- 虽然调度策略实现没啥问题了，但是从实际情况来看，单个任务执行时间过长
- 解决这个问题有两个思路，一个是提高时钟中断频率，另一个就是任务 total 不能过大
- 经过实际测试发现目前时钟中断默认频率大概 100Hz，即每个时间片约 10ms，这个频率还比较合适，如果不合适，那么就得实现时钟频率设置驱动函数了，幸好目前不用该改，主要也是因为我懒得研究时钟外设
- 那么接下来我们对任务 total 进行设计，具体实现就是对优先级 priority 取值范围做限制，比如把优先级 U08 类型改为枚举类型，提前定义好比较合适的值
typedef enum E_TASK_PRI { E_TASK_PRI0 = 240, E_TASK_PRI1 = 241, E_TASK_PRI2 = 242, E_TASK_PRI3 = 243, E_TASK_PRI4 = 244, E_TASK_PRI5 = 245, E_TASK_PRI6 = 246, E_TASK_PRI7 = 247, E_TASK_PRI8 = 248, E_TASK_PRI9 = 249, E_TASK_PRI10 = 250, E_TASK_PRI11 = 251, E_TASK_PRI12 = 252, E_TASK_PRI13 = 253, E_TASK_PRI14 = 254, E_TASK_PRI15 = 255, } E_TASK_PRI;
- 修改任务创建函数的传参 U08 priority 改为 E_TASK_PRI priority，这样子在创建任务时就不会传入不合适的 priority 参数了
E_RET TaskCreat(TASK* task, TASK_FUNC pFunc, U08* stackAddr, U16 stackSize, U08* name, E_TASK_PRI priority)
关于优先级的一些扩展
- 决定任务是否被调度执行的因素可能不止一个
- 需要将各个因素综合考虑后计算任务优先级
- 优先级的高低只能决定处理器获取资源的多少
- 任何设计方案都需要保证每个任务都有机会执行
