创建一个超级简单的多任务调度器.docx
《创建一个超级简单的多任务调度器.docx》由会员分享，可在线阅读，更多相关《创建一个超级简单的多任务调度器.docx（25页珍藏版）》请在冰点文库上搜索。
创建一个超级简单的多任务调度器
创建一个超级简单的多任务调度器（buildasupersimpletasker）
创建一个超级简单的多任务调度器
（Samek博士的这篇文章描叙了一个非常优秀的多任务调度器，我将把它全部翻译过来，包括原文后面的读者评论。
这些讨论将加深对SST的理解。
原文在
BuildaSuperSimpleTaskerByMiroSamekandRobertWard EmbeddedSystemsDesign （07/12/06,11:
26:
00HEDT）
----------------
几乎所有的嵌入式系统都是事件驱动式的；绝大多数时间里这类系统在等待某些事件，比如一个时钟节拍，一次按键输入，一次鼠标点击，或者某个数据包的到达。
在确认这个事件后，系统通过执行适当的计算来反应。
这个反应也许包括操作硬件，或者生成可以触发其他内部软件构件的次级“软”事件。
一旦这个事件处理动作被完成，这类反应系统（reactivesystem）进入到一个蛰伏状态，等待下一个事件。
具讽刺性的是，绝大多数嵌入式系统的实时内核或者RTOS迫使程序员使用构造成连续的无限循环的任务（task）来为这些简单的离散事件反应建模。
对我们来说，这是一个严重的不匹配——这个差异主要归结于大家熟知的传统的实时内核的复杂性。
在这篇文章里，我们将展示如何把绝大多数嵌入式系统的离散事件的自然特性同一个简单的运行到完成（runtocompletion）RTC内核或者“多任务调度器”相匹配，这个内核可以生成一个更加干净，更小，更快，并且更加自然的执行环境。
事实上，我们将展示给你如何（如果你把事件建模成一个离散的，运行到完成的动作）创造基于优先级的，完全可抢占的，可确定的实时内核，我们把它称为SuperSimpleTasker（SST），它只有很少的几条可移植的C代码。
这个实时内核不是新技术；类似的内核已经被广泛用于行业中。
即使这样，简单的RTC调度器也很少在商业刊物上被描叙。
我们希望这篇文章为那些对这类轻量级的调度器感兴趣的人士提供一个方便的参考。
但是更重要的是，我们希望解释为什么一个简单的类似SST的RTC内核，对建立在包括高级的UML状态图的状态机上的执行系统来说，是一个完美配合。
因为状态机普遍的假设RTC执行语义，它们只有和某个要求并利用RTC执行模型的调度器结合，才是合理的。
我们先描叙SST是如何工作的，并解释为什么它仅需要为所有任务和中断准备一个堆栈。
然后我们把这个方法和传统的实时内核比较，这样我们有机会去审查一些基本的实时概念。
接着，我们描叙一个微型的SST实现，它使用可移植的ANSIC，带有一个简单的可执行实例，你可以在任何基于X86的PC上运行它。
我们最后谈论一个工业级的单堆栈内核，它包含一个开源的基于状态机的框架，它们一起为UML状态机提供了一个可确定的执行环境。
我们将假设你熟悉基本的实时概念，比如中断处理，上下文切换，互斥和阻塞，事件队列记忆有些状态机。
使用单一堆栈的可抢占型多任务系统
常规的实时内核为每个运行中的线程或任务维护相对复杂的执行上下文（包括分离的堆栈空间），这在JeanLabrosse的优秀的MicroC/OS-II:
TheReal-TimeKernal书中有详细的解释。
保持对这些上下文细节的跟踪并在它们之间切换，需要大量的记录和尖端的机制来实现上下文切换魔法。
我们将要描叙的内核可以是极度简单，因为它不需要管理多个堆栈以及与之相关的大量记录工作。
由于需要所有任务运行到完成并且实施固定优先级调度，我们可以使用机器的原生堆栈协议来管理所有的上下文信息。
每次当某个任务被某个更高优先级的任务抢占时，SST调度器使用一个常规的C函数调用，在被抢占任务的上下文顶部上面创建较高优先级任务的上下文。
每次当某个中断抢占了一个任务，SST再次使用常规的C函数调用，在这个较高优先级任务上下文的顶部上面，使用公认的中断堆栈框架。
这个简单的上下文管理形式是足够的，因为我们已经坚持让每个任务，就像每个中断一样，运行到完成。
因为这个抢占的任务也必须运行到完成，在抢占任务（和任何可能抢占它的较高优先级任务）执行完成前，不会需要使用较低优先级任务的上下文--执行完成后，被抢占任务将自然的在堆栈的顶部，并预备被恢复运行。
这种执行方式的第一个后果是，一个SST任务不能是一个像在其他传统内核上的绝人任务大多数任务一样的无限循环。
相反，仅能通过SST调度器发出的常规C函数调用才能激活一个SST任务，并且它完成后，总是返回调度器。
SST调度器本身也是一个常规的C函数，在每次某个抢占事件发生时，它被调用，并运行到完成，当所有比当前被抢占任务的优先级任务都完成后，它就返回。
这种执行方式的第二个后果是，和较低优先级相联系的事件必须被排队，直到较高优先级的那些任务完成为止。
调度算法可以和很多优先级机制一起工作，这里我们先讨论它们中间最简单的情况。
出于讨论的目的，我们将假设一个SST的优先级编号方案，从1到（含）SST_MAX_PRIO，较大的数字表示较高的紧迫性。
我们为SST空闲循环保留优先级0，这是在SST里唯一被构筑成一个无限循环的部分。
为每个抢占层简单的调用某个任务函数也许看上去太天真而不能工作，但是在下一节里的分析将表明，它将完美的工作，就像每个基于优先级的硬件中断系统的工作方式一样。
在SST里的任务和中断的优先级
有趣的是，我们可以观察到，在绝大多数基于优先级的中断控制器里（例如，在x86PC里面的8259A，在ATMEL公司的AT91类ARM里的AIC，在PHILIPS的LCP2XXX的VIC，在RENESAS的M16C的中断控制器里，还有其他控制器），在硬件上实现了异步调度策略，策略和SST为任务而使用软件上实现的策略是完全一样的。
特别的，任何基于优先级的中断控制器仅允许较高优先级中断抢占当期的活动中断。
所有中断不想运行到完成，并且不能阻塞。
所有中断在一个堆栈上嵌套。
在SST执行模型里，任务和中断是相似的，任务和中断服务程序都是一次性的，运行到完成的任务。
事实上，SST把中断看出”超级高“优先级的任务，如图1所示，只不过中断（通过中断控制器）在硬件上进行中断排序，而SST在软件里进行优先级排序。
（tobecontinued2010-07-30
创建一个超级简单的多任务调度器2
同步抢占和异步抢占
作为一个完全可以抢占式内核，SST必须确保在所有时刻CPU在执行已经预备运行的最高优先级任务。
幸运的是，仅有2个场景可以导致让一个更高优先级的任务处于预备状态：
一个较低优先级的任务给一个较高优先级任务发送一个事件：
STT必须立即较低优先级任务的执行，并启动较高优先级任务。
我们把这称为抢占（同步抢占），因为它在一个事件被发给某个任务的事件队列时同步发生。
在某个被中断的任务里发生的一个中断ISR给某个更高优先级的任务发送一个事件：
在ISR完成时，SST必须启动更高优先级任务，而不是去恢复那个较低优先级的任务。
我们把它称为异步抢占，因为它可以在任何时候中断没有被锁住时发生。
图2描绘了同步抢占的场景，较低优先级的任务给较高优先级任务发送了一个事件。
起初，一个较低优先级任务在执行中
（1）。
在自然执行的某一刻，较低优先级任务发送了一个事件给某个较高优先级任务，使较高优先级任务处于预备运行状态。
发送事件会启动SST调度器
（2）。
调度器探测到一个高优先级任务现在是预备运行状态，它调用（文本意义上的C函数调用）这个高优先级任务（3）。
注意因为SST调度器在它自己的线程启动了这个任务，调度器直到较高优先级结束运行后才会返回。
较高优先级任务在运行（4），但是在某时刻它也可以给其他任务发送事件。
如果它不是给自己而是给某个较低优先级任务发送事件（5），SST调度器将又一次被调用（5），但如果它没有找到一个预备运行的更高级任务它会立即返回。
当第二次的调度器调用返回时，高优先级任务运行到结束（6），并自然的返回SST调度器（7）。
SST调度器再次检查是否有更高优先级任务预备执行（8），但它没有找到。
SST调度器返回到第优先级任务，后者继续执行（9）。
显然，同步抢占并没有被限制到仅为一层。
如果高优先级任务给某个在图2的第5步的某个更高优先级任务发送一个事件，高优先级任务将被同步抢占，这个场景将在更高一级优先级上递归的重复它自己。
图3描绘了由中断导致的异步抢占的场景。
起初一个低优先级任务在执行，中断没有被锁住
（1）.一个异步事件中断了处理器
（2）.处理器立即中断任何在执行的任务并启动ISR。
ISR执行SST的入口代码（3），它提升会在栈上保存被中断任务的优先级，并把当前优先级提升到ISR层次。
ISR执行它自己的（4），包括给一个高优先级任务发送一个事件（5）.发送事件会启动SST调度器，但是由于当前的优先级（ISR）太高，SST调度器会立即返回，而不是去找某个预备运行的更高优先级和任务。
ISR继续运行（6）并最终执行SST的退出代码（7）.退出代码给中断控制器发送EOI指令（end-of-interrupt），恢复被中断任务的被保留的优先级，并调用SST调度器（8）。
现在，调度器探测到一个高优先级任务预备运行，因此它使能中断，并调用这个新的预备运行的高优先级任务（9）。
注意SST调度器没有返回。
高优先级任务运行到完成除非它也被中断（10）。
在完成后，高优先级任务自然的返回到调度器（11）。
调度器检查是否有一个更高优先级的任务预备要运行（12），但它没找到，于是返回。
最初的中断返回到低优先级任务（13），它一直被异步抢占。
注意中断返回（13）和中断调用
（2）是匹配的。
最终，低优先级任务运行到完成（14）。
这里着重指出，在概念上中断例程在SST退出代码（8）处结束，即使中断栈框架还在栈上而且IRET指令没有执行.（IRET指令是一般意义上的硬件中断返回指令）。
因为EOI指令被发送给中断控制器，中断被结束，在SST调度器里中断被使能。
在EOI指令前，中断控制器仅允许比当前中断更高的中断。
在EOI和对SST调度器的调用之后，中断被解锁，中断控制器允许所有的中断，这就是在任务层期待的行为。
因此，异步抢占也不会仅限于一层。
高优先级任务在中断解锁时运行，如图3的（10）所示，因此它也可以被某个中断异步抢占，包括在（9）处启动这个任务的同层中断。
如果这个中断给某个更高优先级任务发送一个事件，这个高优先级任务也将会被异步抢占，这个场景将在更高层优先级上重复它自己
创建一个超级简单的多任务调度器3
SST和传统内核的对比
通过在单一堆栈上管理所有上下文，SST可以使用比典型的阻塞式内核显著少的RAM运行。
因为任务没有单独的堆栈，被暂停的任务没有私有的未被使用的堆栈空间。
SST的任务切换也导致更少的运行开销；一个传统的内核不会区分同步和异步抢占，对2者它需要一样的上下文切换开销。
最后，SST使用更加简单的更加小的任务控制块（taskcontrolblock）TCB。
因为这个简单特性，SST的上下文切换（特别是同步抢占）需要的堆栈空间和CPU开销比任何传统内核少的多。
但即使SST的异步抢占也需要比传统内核少的栈空间和CPU开销。
原因如下。
在中断时，传统内核必须在每个任务的私有堆栈上建立一个严格定义的堆栈框架，保留所有的CPU寄存器。
SST使用编译器的自然的寄存器管理策略，而传统内核必须准备好在它继续运行被抢占任务时，恢复所有的寄存器。
通常这些堆栈框架的建构和解构必须使用汇编语言来编写，因为传统内核无法让C编译器来做这个上下文切换魔法。
相反，SST并不关心任何特别的堆栈框架或在ISR进入或退出时是否被立即恢复。
唯一有关的是CPU状态被恢复到和发生中断前完全一样，而这和如何发生没有关系。
这意味着绝大多数嵌入式C编译器生成的中断代码可以被SST使用，而这些代码通常无法被传统内核使用。
SST不仅不需要任何汇编语言编程，而且在这种情况下编译器生成的中断进入和退出代码比手写的汇编代码要好，因为C编译器对中断堆栈框架的全局优化做的更好。
在这方面，SST允许你利用C编译器的能力，而传统的内核常常无法利用这种能力。
最后一点也许最好的使用一个例子来说明。
所有的ARM处理器的C编译器，遵守ARM程序调用标准（APCS），它规定在C函数调用时哪些寄存器必须被保存，哪些寄存器可以被改写。
C编译器产生的ISR入口代码仅保留在C函数里可能被改写的寄存器，大约是所有ARM寄存器的一半。
在ISR里被调用的C函数里，当且仅当剩下的那些寄存器确实被使用时，才会保留它。
这种逐步保留上下文的例子完美的适合SST。
相反，传统内核必须在进入ISR时一次保留所有的ARM寄存器，而且如果ISR汇编代码调用C函数时（通常会），许多其他寄存器又被保留一次。
不用说，这些策略需要更多的RAM给每个私有堆栈，和比SST更多的CPU开销（可能是2倍）。
在附注里，我们想强调，工业界里所有的传统阻塞式内核都有我们刚描叙的问题。
我们在这里提及UC/OS-II，不是因为UC/OS-II在这方面有什么特别的不足，而是因为他的书是传统内核的一个优异的解决方案，并且许多嵌入式系统程序员都熟悉它。
附注2：
在传统内核和SST的中断持续时间
如果你有使用传统内核的经验，你也许会注意到SST看来鼓励程序员去违反那些使用ISR的时间建议。
我们绝大多数被告知，ISR必须尽可能的短，主要的工作必须总是在任务层完成。
然而在SST里，每件事看来都在ISR上下文里发生，任务上下文里没有事情发生。
这看起来很奇怪。
但实际上，问题出在对一个中断和一个任务的区分上。
SST迫使我们改变对中断持续时间的理解，这种理解认为，中断持续时间从在堆栈上保持中断上下文开始，到恢复中断上下文并执行IRET结束。
因为这种定义在传统内核里也是有问题的。
图4展示了传统抢占内核维护的任务数据结构，每个任务有它自己的堆栈，每个任务有它自己的控制块TCB来运行上下文。
一般来说，一个中断例程在某个任务的栈上保存中断上下文，在另一个任务的栈上恢复中断上下文。
在把任务的上下文恢复到CPU寄存器后，传统调度器总是执行RET指令。
关键点是，中断上下文保存在被抢占的任务堆栈上，因此被保留的中断上下文在中断例程运行期间被保留。
从而，把中断运行时间定义为从保留到恢复上下文是有问题。
在像SST这样的单堆栈内核里这种情况也没什么很大不同。
ISR在堆栈保存中断上下文，对所有任务和中断代码都一样。
在某些代码运行后，ISR调用调度器，它解锁中断。
如果没有更高优先级任务预备运行，调度器立即退出，这种情况下ISR从堆栈里恢复上下文，并返回最初的被抢占的任务。
否则，SST调度器调用更高优先级的任务，中断上下文保留在堆栈上，就像传统内核一样。
这里的要点是，ISR被定义为从保存中断上下文的时间到发送EOI指令给中断控制器然后调用调度器并使能中断的时间，而不是到恢复中断上下文的时间。
这个定义更加准确和通用，因为在任何内核里，中断上下文保留在一个堆栈里，并在中断处理时间持续。
当然你必须尽量让ISR代码最小，但是在SST，你应该记住，对SST调度器的最终调用在概念上不是ISR的一部分，而是组成任务层的一部分。
ISR持续时间的定义不是纯粹学术性的，而是有实用性的含义。
特别的，调试ISR比调试任务更加有挑战性。
实际上，在SST里，调试ISR到它运行到发送EOI指令给中断处理器这时刻并调用SST调度器，和在任何传统内核里是一样困难的，特别是通过一个ROM监视器来做这种调试时。
然而，调试一个SST任务和调试main（）函数一样容易，即使是一个从ISR里调用的任务。
这是因为SST调度器在CPU层在中断解锁时启动每个任务，并且中断控制器使能了全部中断。
创建一个超级简单的多任务调度器4
SST的实现
我们首先实现一个最小的SST的独立实现。
这里展示的代码使用可移植的ANSIC，所有CPU和编译器相关的部分被清楚的分离出来。
然而，这个实现忽略了实际应用程序的某些特征。
现在的主要目的是清楚的展示关键的概念，并让你在任何Windows上执行代码。
我们使用古老的TurboC++1.01来编译这个实例，它可以从BorlandMuseum下载。
SST实例程序演示了SST的多任务和抢占能力。
图5的代码，由3个任务和2个ISR组成。
时钟节拍ISR每5毫秒产生一个节拍事件（tickevent），键盘ISR在每次某个按键被按下或释放是产生一个按键事件（keyevent），当某个键被按下不放时，它按自动重复速率产生。
2个节拍任务（ticktasks）：
tickTaskA（）和tickTaskB（）分别接受tickevent，在屏幕的右手边的随机位置打印字母A或B。
键盘任务kbdTask（），它的优先级在tickTaskA（）和tickTaskB（）之间，接受键盘的扫描码，给节拍任务发生颜色事件（colorevent），它改变要打印字母的颜色。
还有，kbdTask（）在用户按下ESC键时结束应用程序。
图5左边部分展示了运行中应用程序的基本统计数据。
开始的2列显示了任务的名字和优先级。
注意还有很多未用的优先级。
”Calls“列展示了调用的次数（3位数精度）。
最后"Preemptions"列显示了某个任务或ISR的异步抢占次数。
SST实例应用程序特意使用2个独立的中断（时钟节拍和键盘）来创立异步抢占。
为了增加某个中断抢占一个任务，以及一个中断抢占另一个中断的可能性，代码会调用busyDelay（）函数，它在一个计数循环里扩大运行到完成的时间。
你可以通过一个传递给应用程序的命令行参数来指定循环的次数。
请小心不要极端的增多这个参数，因为较大的值将会让一个任务没法调度，系统也许会开始丢失事件。
后面开始解释SST代码和应用程序的结构。
完整的SST源代码有头文件sst.h，在include\目录下，和实现文件sst.c，在source\目录下，。
实例文件在example\目录下，它也包括了TurboC++项目文件，用来创建和调试应用程序。
（注意，因为标准的键盘ISR被用户代码取代，使用TurboC++IDE调试这个应用程序也许会变困难。
）
创建一个超级简单的多任务调度器5
SST的临界区
SST和其他内核一样，需要执行某些不可分割的操作。
保护代码的某部分不被分裂的最简单最有效的方式就是，在进入这部分代码时锁住中断，在退出这部分代码时解锁中断。
这种代码部分被称为临界区（criticalsection）。
处理器一般会提供指令来上锁/解锁中断，你的C编译器必须有方法从C里执行这些操作。
一些编译器允许你在C源代码里包含汇编指令。
其他的编译器提供了语言扩展，或至少是C可调用的函数从C里来上锁/解锁中断。
为了隐藏实际使用的实现方法，SST提供了2个宏来上锁和解锁中断。
这里是给TurboC++编译器使用的宏定义：
#defineSST_INT_LOCK（）\
disable（）
#defineSST_INT_UNLOCK（）\
enable（）
在这个最小的SST版本里，我们假设最简单的可能临界区：
在进入时无条件的上锁中断，在退出时无条件的解锁中断。
这种临界区绝不能嵌套，因为从临界区退出时中断总是被解锁，无轮在进入前中断是否被锁住。
SST调度器被设成绝不嵌套临界区。
但你必须小心使用宏SST_INT_LOCK（）和SST_INT_UNLOCK（）来保护在应用程序里你自己的临界区。
为了避免这种限制，你可以使用更聪明的方法（更多开销）来上锁和解锁中断。
请注意，不能嵌套临界区并不必需意味着你不能嵌套中断。
在一个具备内部或外部中断控制器的处理器上，比如x86型的电脑上的8259APIC，或AT91ARM的AIC，你可以在处理器层次在ISR内部解锁中断，从而避免在ISR内部嵌套临界区，让中断控制器在中断到达CPU前，来处理优先级安排和嵌套。
创建一个超级简单的多任务调度器6
SST的中断处理
SST的一个最大的优点是简单的中断处理，和在一个简单的"超级循环“（也叫main+ISR）的中断相比，它并不会更复杂。
因为SST不依赖任何中断堆栈框架布局，在绝大多数嵌入式C编译器里，ISR可以完全由C编写。
简单的超级循环和SST之间，ISR的最大不同是，SST需要程序员在每个ISR的进入和退出部分插入一些简单的动作。
这些动作在SST里使用宏SST_ISR_ENTRY（）和SST_ISR_EXIT（）。
在清单1里展示了在节拍和键盘ISR里如何使用这些宏来，它们的定义在文件example\bsp.c里。
清单1：
SSTISR中断例程
voidinterrupttickISR（）{ /*everyISRisenteredwithinterruptslocked*/
uint8_tpin; /*temporaryvariabletostoretheinitialpriority*/
SST_ISR_ENTRY（pin,TICK_ISR_PRIO）;
SST_post（TICK_TASK_A_PRIO,TICK_SIG,0）; /*posttheTicktoTaskA*/
SST_post（TICK_TASK_B_PRIO,TICK_SIG,0）; /*posttheTicktoTaskB*/
SST_ISR_EXIT（pin,outportb（0x20,0x20））;
}
/*..........................................................................*/
voidinterruptkbdISR（）{ /*everyISRisenteredwithinterruptslocked*/
uint8_tpin; /*temporaryvariabletostoretheinitialpriority*/
uint8_tkey=inport（0x60）;/*getscancodefromthe8042kbdcontroller*/
SST_ISR_ENTRY（pin,KBD_ISR_PRIO）;
SST_post（KBD_TASK_PRIO,KBD_SIG,key）; /*posttheKeytotheKbdTask*/
SST_ISR_EXIT（pin,outportb（0x20,0x20））;
}
注意，在清单1里，编译器的关键字interrupt告诉Turbo-C编译器生成合适的上下文保存，恢复和中断返回前置和后置代码。
还请注意，SST中断进入和中断退出宏在每个ISR的开始和结束处。
（如果中断源需要清除，必须在调用SST_ISR_ENTRY（）前执行清除代码）。
宏SST_ISR_ENTRY（）和SST_ISR_EXIT（）在文件includes\sst.h定义，展示在清单2里。
（围绕宏的do...while（0）循环只是用来正确的组织这些指令。
）
清单2：
SST中断进入/退出宏定义
#defineSST_ISR_ENTRY（pin_,isrPrio_）do{\
（pin_）=SST_currPrio_;
升级会员 