全部博文（404）
分类： LINUX
2008-10-06 12:59:36
第四章 任务管理
4.1任务概念与概述
很多操作系统的书籍对任务这个概念都没有定义，只是对进程作了定义，或者对进程的特点、特性作一番描述。刚学操作系统时，很多时候都只是在被概念，而且很抽象。后来，还是看了UCOS这本书，才发现任务就是一个函数，而且是个无限循环，这样的话任务的定义就很简单了。任务的样子可以如下面的代码所示：
Task1( ){
while(1){
….;
printf(“Task1 is running!”);
….;
osWait (10);
}
}
Task2( ){
for(;;){
…;
printf(“Task2 is running!”);
…
osWait(23);
}
}
对于操作系统内核而言，假如osWait(time)函数的功能为使任务等待time个时钟。那么，在正常系统运行的情况下，Task1和Task2会交替运行，会看到Task1 is running!和Task2 is running!的信息交替出现。
OK，问题来了，注意看上面两个程序Task1和Task2，他们都是两个无限循环，按照一般的思路，只要程序进入其中一个死循环，程序就跳不出来了。假如程序进入了Task1，那么Task2就没有机会会运行，那么Task2会运行吗？这是问题一。那好，假如问题一可以解决，那么我们应该做什么呢？这就是问题二了。把这两个问题回答了，任务管理部分就应该差不多了。
现在回到上面的问题，我们为什么产生问题一那样的问题呢？答案是我们用了单任务或者单进程的思路去思考问题。什么是单任务？什么是多任务？回答这个问题可以去查阅操作系统的书籍。多任务就是像上面的例子，当程序在一个死循环中运行，但是又可以跳到其他死循环中去运行，这样的系统可以叫做多任务系统。很神奇的技术，～_～。
好了，这里不去讨论那些基本术语了，书上太多了。问题一的答案是肯定的，关键是第二个问题我们需要做些什么，才能实现多任务。换句话说，操作系统内核应该定义什么样的数据结构，以及提供什么样的函数接口。下面的文字将描述ByCore的实现方式以及步骤。
首先描述一下ByCore任务管理的总体设计要求和结构，该部分实现了抢占特性。主要调度算法思想为：内核将所有任务按优先级高低分为64个组，并尽量保证高优先级的任务优先运行，对于同优先级的任务按照时间片的原则调度各个任务。同时，该部分还支持任务休眠功能。简单的说，整个任务管理部分就是在实现这几句话。
4.2 任务状态
在多任务状态中，任务要参与资源的竞争，只有在所需资源得到满足的情况下才能得到执行。然而，任务拥有的资源情况是不断变化的，这将导致任务状态也表现出不断变化的特性。不同的实时内核实现方式对状态的定义不尽相同，但都包括以下三种基本状态：
· 等待：任务在等待I/O完成或者等待某事件的发生；
· 就绪：任务已经得到需要运行的资源，并等待获得处理器资源；
· 执行：任务获得处理器和其他所有需要的资源，相关代码正在被运行。
在单处理器系统中，任何时候只有一个任务处于运行状态。如果没有任何任务需要运行，那么内核会运行一个空闲任务。任何一个可以执行的任务都必须处于就绪状态，实时内核会从所有就绪的任务中，使用合适的调度策略选择一个运行。当一个任务请求I/O操作，或者等待信号量将会处于等待状态。
在一定条件下，任务会在不同的状态之间进行转化，称为任务状态迁移。任务状态迁移情况如图4-1所示。对于处于就绪状态的任务，获得CPU后，处于运行状态。处于运行状态的任务如果被高优先级任务所抢占，或者执行的时间片期满，任务又回到就绪状态。运行的任务如果需要等待某些资源，任务被切换到等待状态。对于等待态的任务，如果等待的资源或事件满足，就会转换为就绪状态，等待被调度执行。
图4-2描述了三个任务状态迁移过程。图中包含三个任务和一个调度程序。调度程序确定下一个需要投入运行的任务，因此调度程序本身也占用一定的处理时间。
图4-2 任务状态迁移示意图
4.3 任务调度
调度是内核的主要职责之一，调度的主要任务就是要决定该轮到哪个任务运行。多数实时内核采用基于优先级调度的算法。基于优先级的调度算法是指，每个任务根据重要程度被赋予一定的优先级，CPU总是让处在就绪态的优先级最高的任务运行。然而，究竟何时让高优先级任务掌握CPU的使用权，有两种不同的情况，这取决于内核的类型（是可剥夺型的还是可剥夺型内核）。
当调度程序决定新的任务获得CPU的使用权时，这时内核将执行任务切换。任务切换过程为：首先保存当前任务的上下文，即CPU寄存器中的全部内容。这些内容可以保存在任务的自己的栈中，也可以保存在TCB中。然后，将需要运行的任务的上下文从该任务的栈中重新装入CPU的寄存器，并开始运行。任务切换过程增加了应用程序的额外负荷。CPU的内部寄存器越多，额外负荷就越重。
当两个或两个以上任务有同样优先级，内核允许一个任务运行事先确定的一段时间，该段时间叫做时间片，然后切换给另一个任务。内核在满足以下条件时，把CPU控制权交给下一个就绪态的任务：
· 当前任务运行的时间片到期；
· 当前任务在时间片还没结束时已经完成了。
每个任务都赋予优先级。任务越重要，赋予的优先级就越高。优先级的分配方式可分为静态分配和动态分配的方式。静态优先级是指应用程序执行过程中诸任务的优先级不变。在静态优先级系统中，各个任务以及它们的时间约束在程序编译时是已知的。动态优先级指应用程序执行过程中，任务的优先级是可变的。
对于一个实际的内核而言，常常会实现这三种调度方案，Linux是个很好的例子，Linux采取的调度策略结合了这几种调度方案。在Linux系统中，调度算法最基本的一类就是基于优先级的调度。优先级高的任务先运行，相同优先级的任务按照轮转方式进行调度。Linux也实现了基于动态优先级的调度方法。一开始，利用静态优先级的方法设置任务的优先级，然而它允许调度程序根据需要来提升、降低优先级。在另一类内核中，比如，μC/OS就只实现了静态优先级的分配方式。
给任务确定合适的优先级是件比较困难的事，因为实时系统相当复杂。许多系统中，并非所有的任务都至关重要。不重要的任务自然优先级可以低一些。实时系统大多综合了软实时和硬实时这两种需求。软实时系统只是要求任务执行得尽量快，并不要求在某一特定时间内完成。硬实时系统中，任务不但要执行无误，还要准时完成。优先级分配最基本的算法为单调速率调度法RMS(Rate Monotonic Scheduling)，用于分配任务优先级，在RMS基础上又有很多改进的算法。RMS方法原理是基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS做了一系列的假设：
· 所有任务都是周期性的；
· 任务间不需要同步，没有共享资源，没有任务间数据交换等问题；
· CPU必须总是执行那个优先级最高且处于就绪态的任务。也即，需要使用可剥夺型调度法。
如果给出n表示系统中的任务数，要使所有的任务满足硬实时条件，必须使不等式(3-1)成立，这就是RMS定理：
(4-1)这里Ei是任务i最长执行时间，Ti是任务i的执行周期。即Ei/Ti是任务i所需的CPU时间。表4-1给出n(21/n - 1 )的值，n是系统中的任务数。对于无穷多个任务，极限值是0.693。这就意味着，基于RMS，使任务都满足硬实时条件，所有有时间条件要求的任务i总的CPU利用时间应小于70%。当然，这是指有时间条件限制的任务，系统中当然还可以有没有时间限制的任务，使得CPU的利用率达到100%。使CPU利用率达到100%并不好，因为那样的话程序就没有了修改的余地，也没法增加新功能了。作为系统设计的一条原则，CPU利用率应小于60%到70%。RMS认为最高执行率的任务具有最高的优先级，在某些情况下，最高执行率的任务并非是最重要的任务。如果实际应用都真的像RMS说的那样，也就没有什么优先级分配方案可讨论了。
表4-1 基于任务的CPU最高允许使用率
|
任务数 |
n(21/n - 1 ) |
|
1 |
1.000 |
|
2 |
0.828 |
|
3 |
0.779 |
|
4 |
0.756 |
|
5 |
0.743 |
|
… |
… |
|
… |
… |
|
… |
… |
|
n |
0.693 |
4.4 内核时钟（部分摘自嵌入式实时操作系统及应用开发）
实时内核的事件管理以内核时钟为基础，系统时钟一般定义成整型或长整型，提供给内核和应用程序所有与时间相关的服务。内核时钟一般由处理器的定时器/计数器产生，定时器/计数器被设置成以一定的时间间隔产生中断，该中断的周期叫做一个“时钟滴答”，也称为时标或tick。
tick为系统的相对单位，也是整个系统的时基，它记录了系统开机以来定时器/计数器产生的中断次数，也可以说，一个中断就是一个tick。一个tick与具体时间的对应关系在初始化定时器/计数器时设定，也即tick所对应的时间是可以调整的。一般来说，内核都提供相应的调整机制，应用时可以根据实际的情况选择tick对应的时间长度。例如，使系统5ms对应一个tick，也可以10ms产生一个tick。tick的大小决定了整个系统时间粒度。
定时器/计数器的初始化工作主要包含以下内容：
· 确定tick的时间间隔，使定时器/计数器每隔一个确定的时间产生时钟中断；
· 初始化定时器/计数器相关的寄存器；
· 挂接系统时钟中断处理程序。
通常来说，内核提供以下主要的时间管理：
· 维持相对时间（以tick为单位）和日历时间；
· 任务有限等待的计时；
· 定时功能；
· 时间片轮转调度计时。
这些功能通过tick处理程序实现，如图4-3所示。当定时器发生中断后，执行系统时钟中断处理程序，并在中断处理程序中调用tick处理程序，实现系统中与时间和定时相关的操作。tick处理程序作为内核的一部分，与具体的定时器/计数器硬件无关，由系统时钟中断处理程序调用，使实时内核具有较好移植性。
图4-3 tick处理程序
上图中，相对时间即为系统时间，是指系统自启动以来的时间，以tick为单位，每发生一个tick对系统的相对时间进行一次加1操作。实时内核根据tick对应的时间长度，可以把相对时间转换为以s或其他时间单位格式。如果对任务设置了时间片处理方式，则需要在tick处理程序中对当前运行的任务的执行时间更新，使任务的执行时间片数加1。tick最后返回到系统时钟处理程序，系统时钟处理程序调用调度器进行任务调度。调度器选择一个合适任务运行。
现在为止，把一些比较基本的东西叙述了一遍，上面的内容有些是摘自其他书籍的。下面的文字将阐述ByCore的实现。Ok，see you next time！
To be continued……
------ anmnmnly
------ 2008.05.01
