嵌入式操作系统内核实现（九）（转载）

4.4 ByCore任务管理实现

       上面的诸小节描述了操作系统任务管理的一般知识，但是这些知识不全面，有兴趣的话可以阅读基本著名的操作系统的书籍。这里所描述的内容只与ByCore实现的功能有关，在此简单说明一下。

       本节将实现本章上几节所论述的内容，包括任务状态迁移、任务控制块、内核中各种队列、调度算法和内核时钟等内容。在内核的设计过程中，最先应考虑的是任务的状态以及迁移时序，然后根据此状态设计相应的队列，如就绪队列、等待队列等。内核时钟也依赖任务的状态。可以看出，任务管理实现的核心和基础是任务状态和迁移时序。

4.4.1任务状态及转换时序

       在上面的章节中，描述了任务的三种基本状态，一般在实现时会基于这三种转态添加新的状态。图4-4描述了实际实现的任务状态转换图。在给定的时刻，任务的状态一定处在这六种状态之一，下面的论述只是对本系统实现的描述，不同的内核对这些部分的实现有很大差异，但基本原理不变。

图4-4 实际实现的任务状态转换图

图4-4在描述任务状态迁移的同时，也描述了任务的生存周期，任务的生命期从新建态时开始直到结束态时结束。在不同的操作系统中，这些状态的实现是有差异的，有的内核还有其他状态。新建状态是指任务被创建的过程，在这个过程中主要工作有：为任务分配TCB和栈空间以及其他资源。当任务创建完成以后，任务就具备运行的能力了，与此同时，任务进入就绪状态，并等待调度器为它分配运行的机会。当任务得到运行的机会，任务开始执行。处于运行态的任务会在任意时刻由运行态进入休眠态、就绪态或结束状态。其中进入休眠态是任务的主动过程，这主要是任务调用了内核提供的休眠函数，任务在休眠状态，如果没有其他任务唤醒它，它将永远休眠下去直到系统关闭，这种方式也可用于任务同步。等待状态主要由两种原因引起，一种是等待某事件的发生，如等待信号量；第二种为任务主动等待多少个tick。最后，任务可以将自己杀死进入结束态。

4.4.2任务控制块

任务控制块（TCB）唯一地描述了一个任务的属性。一旦任务建立了，任务控制块中的各个值将被赋值。任务控制块是一个数据结构，当任务的CPU使用权被剥夺时，TCB保存了该任务的状态和其他信息。当任务重新得到CPU使用权时，TCB能确保任务从被中断的点丝毫不差地继续执行。TCB全部驻留在RAM中。TCB在任务初始化的时候被建立。任务控制块数据结构如下所示：

typedef struct task_ctrl_blk{

stk_t *pstack;

stk_t *pstk;

list_t link;

uword_t id;

uword_t prio;

uword_t slice_time;

uword_t exe_time;

word_t delay_time;

uword_t status;

list_t task_link;

}tcb_t;

其中：

· pstack：指向当前任务的栈顶。每个任务有自己的栈，尤为重要的是，每个任务的栈的容量可以是任意的。有些商业内核要求所有任务栈的容量都一样，除非用户写一个复杂的接口函数来改变之。这种限制浪费了RAM，当各任务需要的栈空间不同时，也得按任务中预期栈容量需求最多的分配栈空间。pstack是TCB数据结构中唯一一个能用汇编语言来处置的变量（在任务切换段的代码之中使用）把pstack放在数据结构的最前面，使得从汇编语言中处理这个变量时较为容易；

· pstk：指向任务的栈顶，在任务结束而回收任务栈空间时使用，这主要由内存管理部分的缺陷所引起的；

· link：用于连接任务控制块。内核在运行时，除了任务控制块外，系统中存在很多类型的链表，比如信号量链表。为了对这些链表有一个统一的操作，所以定义了list_t类型来统一这些操作。如果不使用list_t，TCB链表操作需要实现一组链表操作函数，信号量需要另外一组链表操作函数，这样使程序变得冗长；

· id：任务的ID号，用于唯一标识一个任务。每个任务都有一个唯一的ID号，需要在任务创建的时候指定ID，如果指定的ID号已经存在，则此任务不能被创建；

· prio：任务的优先级，此值范围为0～63，值越小代表优先级越高。内核将尽力保证高优先级的任务优先运行，并且允许任务可以是相同的优先级；

· slice_time：表示任务应该运行的时间片数。虽然内核保证高优先级的任务优先得到运行的机会，但对于相同优先级的任务来说，时间片方式是比较好的调度策略；

· exe_time：保存了任务已经运行的时间片个数。这个变量在每次系统时钟中断产生时被累加1，如果exe_time的值达到slice_time，则说明该任务已经运行了给定时间片的时间，这时，内核将把运行机会让给其他的，且优先级等于此任务的其他任务。如果此优先级上没有其他任务，且此任务没有自己放弃运行机会，此任务将继续运行；

· delay_time：用于记录任务等待的时间片数，每个系统时钟中断产生时，此值自减1，如果delay_time的值为0，说明该任务的等待时间已经超时。内核将此任务从等待队列中删除，并移动就绪队列中，这样该任务就会被调度器在适当的时候调度；

· status：指示了任务的运行状态，目前，此值表示的含义有就绪，休眠，等待和阻塞，在任务状态转换图4-4中的运行态未能表示出来，这是因为在实现时，就绪态同时也表示了运行态；

· task_link：用于将系统中所有的任务连接成循环双链表。

4.4.3 ByCore中的各种队列

       在图4-4中描述的每个状态都对应一个或一组队列。如处于就绪状态中的就绪队列，处于等待态中的等待队列等等。

4.4.3.1 就绪队列

       就绪队列中的任务已经得到除CPU以外的所有资源。调度器也将在它们中按照优先级和时间片结合的策略选择一个就绪任务获得CPU。在实现中，任务被分成64（0～63）种优先级，且不同的任务又会有相同优先级。内核将相同优先级的任务组成一个双链表。为了在调度过程中能快速的检索出最高优先级的任务队列，将整个就绪队列用一个全局数组list_t ptask[MAX_PRIO]（其中MAX_PRIO＝64）来作为不同优先级就绪队列的队头，如ptask[i]为优先级是i的就绪队列的队头。整个就绪队列如图4-5所示。

4.4.3.2 等待和休眠队列

       当任务处于等待或休眠态时，内核必须将该任务的TCB从就绪队列中删除，然后插入到等待或者休眠队列。在当前的实现中，内核只分别维持一个等待队列和休眠队列，这两个队列不像就绪队列按照优先级的高低被分组，换句话说，等待队列和休眠队列将所有的任务TCB连成一个双链表，如图4-6所示。

图4-5 就绪队列

图4-6 等待和休眠队列

       pdelay和psleep分别为等待队列和休眠队列的对头指针。这两个队列的组织虽然一样，但是它们各自队列中的任务被激活的时机却不同，pdelay所指队列中的任务会被内核的tick激活，而处在psleep队列中的任务只能由其他的任务将其唤醒。利用这两种队列配和信号量等任务同步、通信机制可以实现较为复杂、灵活的任务控制机制。

       当任务处在等待态时，任务还可能处在另外的队列中，这个队列就是为等待某个信号量而组织成的队列。这个队列将在信号量实现的内容中论述。

4.4.4调度器实现

       在整个任务管理中，任务调度无疑是系统的核心，任务调度通常由内核中的调度器实现。调度器的实现与任务运行状态迁移，任务队列有密切的联系，可以说任务运行状态迁移和任务队列决定了调度器的实现。调度器的主要作用是在就绪队列中选择优先级最高的任务运行，如果优先级最高的任务不止一个，则选择队头的任务运行。虽然整个调度器的功能可以用上面的几句话概括，但调度器的实现远远没有那么简单，主要困难来源下面的原因：

1．确定调度器运行的时机；

2．中断处理程序完了后，是执行当前任务，还是马上调度；

3．调度器的性能；

4．调度中伴随着任务上下文的切换，尤其对处理器架构有关的上下文，应该设计良好的接口以便移植。

以上这些基本问题都是应该考虑的，随着内核功能的扩充和完善，调度器可能会在原先没涉及到的地方被调用，虽然在这些新地方不要求能正确调度，但至少不能引起系统崩溃。对于实时系统来说，中断处理程序执行完毕后，应该马上执行调度，这是因为中断常常伴随着有新的任务处于就绪队列中，在这些任务中可能会有高优先级的任务就绪，所以在实时内核中要求必须支持在中断后马上进行任务调度。不管是在实时系统，还是在其他系统中，调度器性能显得非常重要，常常要求调度器的时间复杂度至少应该为线性，当然常数是最好的。对于不同的处理器架构，其提供的寄存器，状态寄存器都有很大的区别，调度器应该留出良好的接口给不同的处理器，以便以后方便移植。

在实现调度器时，基本上考虑了上面的几个基本问题。根据上两节论述的任务状态迁移、内核队列等方面的内容，在byCore中实现了一个叫scheduler( )的调度程序。在scheduler( )中调用几个与硬件相关的函数，这几个函数主要用于实现任务硬件上下文的切换，这部分代码用汇编完成，并且与处理器有关。在现代操作系统中，会有很少一部分使用汇编语言实现，这是因为各种处理器架构的寄存器都没有被映射到可见的位置，也即象C这样的高级语言不能直接对其操作，然而，在任务切换时，硬件上下文会保存到任务堆栈中，这种操作使得高级语言无能为力。

图4-7描述了scheduler( )的算法流程图。

图4-7 scheduler( )算法流程图

该调度程序的算法非常简单，首先，在允许调度的情况下，如果有高优先级任务就绪，则进行任务切换。任务切换会发生在两种处理器模式下，一种是处理器处于正常的运行态，另一种发生在中断态中。因此，内核使用两组函数分别处理这两种情况。在两种处理器状态下都有“启动新任务”和“新旧任务切换”函数接口实现最后的任务切换工作，这两组函数与处理器有关，并由汇编实现。在后面的内核移植一节将详细论述这些函数接口的实现。

启动新任务的主要功能是将任务的初始上下文复制给处理器的各个寄存器，这包括通用寄存器、堆栈指针寄存器、状态寄存器和指令指针寄存器等。这些初始值在新任务创建时被初始化。启动新任务发生的时机有两种情况，第一种情况是内核初始化完毕后，启动第一个任务；第二种情况为任务主动结束后，当前任务指针被置位NULL时。

       任务切换发生在两个任务之间，一个是被换切换出去的任务，另一个是将要执行的任务。任务切换函数也由汇编代码实现。它所要完成的工作主要有两个，第一是将旧任务（被换切换出去的任务）的上下文保存到自己的栈中，第二是新任务（将要执行的任务）将保存在栈中的上下文复制到处理器的相关寄存器中。任务切换的发生时机有：

       · 当前任务执行时间到；

       · 当前任务被高优先级任务抢占；

       · 当前任务休眠，或等待某事件发生。

由于任务切换与处理器关系紧密，本章只介绍与处理器无关部分的实现，与处理器有关的部分将在内核移植一章中详细论述。

4.4.5 内核时钟实现

       在内核时钟一节中，论述了内核时钟的作用以及功能。但在当前实现中，根据实际的情况对内核时钟的功能做了裁减，内核时钟功能主要由systick( )函数实现，systick( )需要完成的工作如图4-8所示。

图4-8 systick( )流程图

4.4.6 任务管理API实现

任何内核都应该提供一组丰富的API函数供用户使用。像UNIX、Linux、Windows这些大型操作系统提供了大量的API。当然这些API的数量、种类，用法等都会随着系统的不同而不同。但在任务管理方面下面几个API是必不可少的：任务创建、撤销、休眠、等待和唤醒等操作。下面将描述各个API的实现算法。

4.4.6.1 任务创建

       当用户调用任务创建函数时，内核应该完成哪些工作呢？这和内核的实现方式，复杂程度密切相关。当前任务管理实现中，提供两个任务创建函数osInitTask( )和osCreateTask( )。这两个函数的原型如下所示：

void osInitTask(void (*pTask)()， uword_t TaskID， uword_t Prio， uword_t Time， uword_t StkSize);

void osCreateTask(void (*pTask)()， tcb_t *pTcb， uword_t TaskID， uword_t Prio， uword_t Time， stk_t *pStk， uword_t StkSize);

       这两个函数的主要区别为任务需要的TCB和栈空间是否为动态创建。osInitTask( )函数只需要传递任务起始地址((*pTask)())，任务ID(TaskID)，优先级(Prio)，运行时间片(Time)和栈大小(StkSize)，任务的栈和TCB空间都为动态创建，栈和TCB空间处于系统的堆区。osCreateTask( )函数除了以上的参数外还格外需要*ptcb和*pstk两个参数，这两个参数分别指向任务的TCB起始地址和栈起始地址，这个函数的空间需要在编译时制定，栈和TCB空间属于内核区。虽然它们需要的参数不同，但它们的实现算法是相同的。

在描述算法之前需要对任务栈做简单的论述，栈的作用是保证任务正常运行，它保存了任务中各个函数的调用轨迹和返回地址。对于处理器来说都提供一个独立的寄存器或者其他空间保存着栈顶的位置，各种处理器架构对栈顶和栈底的定义也不相同，这主要有两种，一是栈顶的地址值大于栈底，其二相反。第一种伴随着栈往下增长，第二种栈往上增长。为了便于移植内核，内核应该处理这两种情况。除了这两种情况，栈还分为满栈和空栈两种，所以内核必须考虑这几种栈方式。因此在实现中提供一组宏来应对这些情况，如下所示：

#define   UP                       1

#define   DOWN                 0

#define   FULL                   1

#define   EMPTY                0

#define   STACK                 DOWN

#define   STACK_STYLE    FULL

       UP和DOWN定义了栈的增长方向，FULL和EMPTY说明了是满栈还是空栈。最后用STACK和STACK_STYLE联合说明真正的栈工作方式。

       论述完了任务创建方面需要注意的一些问题，下面论述任务创建的算法。任务创建过程主要包含初始化TCB和栈区，如果调用osCreateTask( )函数，在初始化前还需要向内核申请TCB和栈空间。图4-9为osInitTask( )函数创建新任务的流程图。

图4-9 osInitTask( )算法的流程图

4.4.6.2 任务撤销

       每个任务都有一个生命周期，包括任务创建、运行与撤销。任务撤销也可称为在多任务系统中，任务也可以被任何用户杀死，也可以有特殊用户杀死。比如，杀死任务。任务撤销的方式有很多种实现方式。一般情况下，任务可以被内核杀死。在Linux下有些任务可以被任何用户杀死，有些则只能由root用户杀死。在单用户系统中，用户任务能被内核杀死，也可以被其他用户任务杀死，但后种情况不多见。根据实际的情况，当前对任务撤销的实现为只有任务自己主动杀死自己。

在当前实现中，任务撤销的函数为osKill( )，如果当前任务完成了自己的使命，可以调用该函数。osKill( )会释放掉该任务的相关资源，如TCB和栈空间等。osKill( )只释放掉内核分配的资源，如果任务的运行过程中申请了其他资源，应该在调用osKill( )前释放掉这些资源。任务在创建时有两个创建函数osInitTask( )和osCreateTask( )，osKill( )只能释放osInitTask( )的资源，而osCreateTask( )的资源会被保留下来。这是因为osCreateTask( )所使用的空间属于内核空间，而不属于系统动态内存管理的堆区，这部分区域没有相关的数据结构管理，一旦释放系统就会崩溃。根据上面的描述可以设计出osKill( )的算法，该算法如图4-10所示。

图4-10 osKill( )算法流程图

图中，当前任务从就绪队列删除后，然后判断该任务是否由osInitTask( )创建，这通过判断任务的栈起始地址与内存堆起始地址实现，如果堆起始地址大于内存堆

起始地址，则说明任务有osInitTask( )创建，若小于则说明任务由osCreateTask( )静态创建，当然不会出现相等的情况，如果相等则系统根本不能运行。

4.4.6.3 任务休眠与唤醒

       当任务需要等待某些资源的时候，可以将自己设为休眠状态，把运行的机会让给其他任务，当所等待的资源或者事件发生时，任务再被唤醒继续运行。这种方式也是解决任务同步的一种办法，如任务A与任务B合作完成某项任务，且A完成后B才能运行，休眠与唤醒机制可以很容易地解决此问题。内核实现了两个函数分别完成这两项工作，他们是osSleep( )和osWakeUp( )，osSleep( )是任务的主动行为，因此不需要参数，osWakeUp( )需要一个参数TaskID，该参数指定了需唤醒任务的ID号。

       当任务调用osSleep( )后，该任务的TCB从就绪队列中删除，并插入到休眠队列（如图4-6所示），然后重新调度。如果任务A需要唤醒正在休眠的任务B，那么A可以调用osWakeUp( )函数，并传入B的ID。osWakeUp( )就会查找休眠队列，如果找到任务B，则将它的状态置为就绪，并从休眠队列删除插入就绪队列，最后调用scheduler( )。osSleep( )和osWakeUp( )的算法流程图如图4-11和4-12所示。

图4-11 osSleep( )算法流程

图4-12 osWakeUp( )算法流程图

4.4.6.4 任务等待

       任务等待与任务休眠的实现原理都一样，当任务需要等待某些资源的时候，可以将自己设为休眠状态，把运行的机会让给其他任务。任务在等待一段时间后再获得运行的机会，这个时候它所等待的事件或者资源有可能不可用，这点和任务休眠是有差异的。例如任务A需要与串口I/O通信，由于串口速度相对较慢，任务A大部分时间都需要等待，如果任务A在没有数据传输的时候进入等待状态，将会显著提高CPU利用率。

       内核提供了osWait( )函数来实现此功能，该函数接受一个时间参数，该参数说明当前任务等待时间长短，该时间以系统tick为单位。当前任务调用此函数后，任务状态被置为等待态，TCB从就绪队列中删除，并插入到等待队列，最后调度scheduler( )。等待队列与休眠队列相同，见图6-7所示。osWait( )函数的流程图与osSleep( )算法相似，这里不再赘述。

       每次系统tick发生中断时，内核时钟中断处理程序更新等待队列上任务的等待时间域，也就是任务控制块TCB的delay_time域作减1操作，当此域减少到0时，表示该任务的等待时间已到，这时它将从等待队列中删除，并插入到就绪队列中。这些工作也是内核时钟中断当前唯一需要做的事情。

 

To be continued……

------ anmnmnly 

------ 2008.05.04