Nut/OS和μC/OS―II的实时调度算法比较

如果说CPU是计算机系统的心脏，那么进程调度就是计算机系统的灵魂，因为它决定了如何使用CPU。例如，Linux是一个多任务操作系统，它的理想状况是保持CPU有效运行。如果某个正在运行的进程转入等待系统资源，操作系统就调度其他进程运行，从而保证CPU的最大利用率。如何使系统能够保证较短的响应时间和较高的吞吐量，使得多个进程竞争CPU时保持公平、高效，是通用操作系统所追求的目标。但对于实时操作系统而言，它的调度算法是基于POSIX规定的基于事件驱动优先级的调度算法，为了及时响应高优先级进程，它宁愿牺牲整体效率。

调度的实现可以分为2步来完成：
①何时启动调度，即解决调度启动时机的问题；
②怎么调度，按优先级调度就是要找到系统当前优先级最高的进程，然后进行上下文切换。

在实时系统中，只有当就绪进程集合发生变动时才有调度的需要，而就绪进程集合的变动只可能发生在几种情况下：
①运行中的进程受阻或自动放弃CPU；
②系统中新建了进程；
③运行中的进程“自杀”或“被杀”；
④运行中的进程唤醒了某个线程；
⑤中断服务子程序结束时唤醒了其他进程。

理想情况下，实时系统在有高优先级的进程转入就绪态时，就应该立即启动调度程序，响应高优先级进程。但实际上却存在着不可调度的时隙，称为不可调度窗口：
①正在进行进程切换，不能进行调度；
②中断响应期间，不能进行调度；
③进入临界区，不能进行调度；
④DMA期间CPU已被挂起，不可能进行调度。

在实时系统里，必须努力缩小不可调度窗口。

在调度启动的时机上，所有的实时操作系统基本一致。

那么接下来要做的就是寻找系统中当前最应该得到运行机会的进程，下面分别看一个最简单的和比较复杂的实现。

1 μC/OS-Il的实现
在μC／OS-II里。只允许有64个优先级且不同进程优先级互不相同。把64个优先级分成8组，数据结构位图OSRdyGrp反映着哪一些进程组中有就绪进程。另外，各个进程组的标志位在位图中的位置也是有规律的，位置靠右边的标志位代表优先级较高的进程组，只要从右到左扫描位图OSRdyGrp，碰到第一个非0的标志位就代表当前优先级最高的就绪进程所在的进程组。这样，就可以预先编制一个对照表，即数组。此数组就是OStJnMapTbl[](该表的详细描述可参阅参考文献的88～90页)，以位图OSRdyGrp的数值为下标，就可以直接得到优先级最高者所属组号。

8个标志位共有256种不同组合，所以这个数组大小是256。为了便于与μC／OS-II源代码对照，把以OSRdyGrp的数值为下标，在OSTJnMapTbl[]数组中查得的值称为组号y。知道组号y以后，就可以以此为下标在OSRdyTbl[]中得到相应的组内位图。同理，以这个位图的数值OSRdyThl[y]为下标，又可以在OSUnMapTbl[]内查得该组内优先级最高者进程号。将组号和组内号拼合在一起，就得到了目标进程完整的进程号，即优先级。再以此为下标，就可以从OSTcBPrioTbl[]中得到指向目标进程控制块的OSTCBHighRdy。以下就是进程切换的工作了。

通过上面的分析，不难理解下面这样的语句了：

这个过程如此简洁，其根本原因是μC／OS-II严格按优先级调度，并且每个优先级只有一个进程。如果优先级的使用并非唯一，多个线程可以使用相同的优先级，那就还有个相同优先级的就绪进程之间怎样调度的问题，这就使调度过程复杂化了。一些商品的实时操作系统，例如VxWorks，允许多个进程具有相同的优先级，因为不支持不同进程可以有相同优先级的系统，无法采用优先级继承算法来解决实时系统里令人讨厌的优先级反转现象，但它不公开源代码。下面选择一个公开源代码的实时操作系统Nut/OS进行分析。它有256个优先级且允许不同进程具有相同的优先级。在这样的系统里，是不可能采用类似于位图这样的机制来实现调度的。

2 Nut／OS的实现
为了叙述方便，设计一个完整的进程运行的情景来说明。另外Nut／0S中采用了线程的概念，在不分系统空间和用户空间的系统中，进程等价于线程。而进程和任务本来就是同一个概念的不同叫法。Nut／Os是一个嵌入式实时操作系统，不分系统空间和用户空间，所以以下的叙述中，线程、进程和任务混用，意思完全一样。

在Nut／OS中，可以通过下面的函数创建一个线程：

创建一个线程的过程，实际上就是从堆栈空间中申请一个放置线程控制块的空间，在这个空间中建立线程控制块并完成对控制块的赋值的过程。为了更好地说明线程控制块的作用，下面用一个图表来说明，如图1所示。

如果创建成功，NutThreadCreate()将返回一个指向新创建的线程控制块的指针，新创建的线程控制块将放置在线程控制块链表前面，nutThreadList指针总是指向这个链表的第一个控制快。现在假设某一个应用中只有3个线程，1个隐藏线程、1个主线程和1个应用线程。其中隐藏线程(threads3)中创建了主线程(Threads2)，主线程中又创建了应用线程(Threadsl)。由于一开始只有一个隐藏线程，因此nutThreadList链表指向了隐藏线程。当隐藏线程创建了主线程时，主线程控制块添加在隐藏线程控制快链表的前面，因此nutThreadList链表指向主线程。当主线程创建了应用线程，应用线程控制块添加在主线程控制块的前面，因此nutThreadList链表改为指向应用线程。这就组成了一个如图2所示的链表。

由图2可知，Nut/OS采用4个链表来管理系统中的全部线程，其中runQuene总是指向全部就绪线程链表，这个链表由td_qnxt指针链成。td_qnxt链表与td_next链表形成机制不同。在td_next链表中，新创建的线程总是简单地放在链表的前面，这个链表包括所有的线程控制块；而td_qnxt链表是根据优先级顺序排序的，一个线程只有处于就绪态(TDs_READY)或者运行态(TDS_RUNNING)才能包括在这个链表中。

隐藏线程的优先级为254，并且总是将该线程的td_next和td_qnxt设为空指针。线程的退出机制就是将要退出的线程的优先级设为255。由于这个线程的优先级比隐藏线程还低，而隐藏线程又没有指向该线程的指针，因此这个退出线程永远也不可能被运行。

按优先级调度是通过mnQuene链表来实现的。Nut/OS提供了2个API来操作这个链表，其中插入操作的代码如下：

该API函数表明，runQuene链表是一个按优先级排序的链表，优先级高的线程控制块总是在最前面，当发现有相同优先级的线程控制快时，总是把后来的插到相同优先级线程控制块的最后面。这就自然实现了对相同优先级线程按先来先服务的算法进行调度。

当就绪进程集合发生变动时，则调用NutThreadRemoveQueue()、NutThreadAddPriQueue()完成链表的更新让runQuene指向更新后的链表头。接下来的事就是上下文切换了。

通过链表这个简单的数据结构，Nut/OS也很简洁地实现了实时调度算法。阅读过Linux源代码的人对链表的重要性可能更是感同身受，虽然Linux操作系统堪称完美，但源代码却并不怎么规范，事实上造成了Linux源代码复杂难懂；而同是开源的Nut/OS，代码却相当规范，给我们提供了非常好的学习资料。笔者在这里感谢该系统的开发人员Harald Kipp和沈文先生等，以及那些热爱开源并热心奉献的工程师。

结语
μC/OS-II的实时性已经通过了非常严格的测试，事实上成了笔者比较其他系统实时性能的一个基准。在这次毕业设计工作中，采用Nut/OS实现8位机接入以太网，运行良好。不妨推测，在一些商品实时操作系统里，对优先级调度算法的实现采用的机制和Nut／OS是类似的。