摘  要: 从进程和线程调度的角度出发,介绍了一种规范化的实时多任务系统软件设计方法,提出了“前向分支”的设计原则,给出了完整的系统模型。

　　关键词: 线程拆分  前向分支  实时多任务  单片机

　　在机电产品研制开发中,经常要涉及到基于嵌入式系统或基于单片机系统的程序设计。实时多任务是这类系统最基本的要求之一。在实践中通常采用以下两种解决方案:一是在商业化实时操作系统的基础上进行二次开发;二是用户自行设计系统软件。前者设计工作量小,设计周期短,系统的设计质量也容易得到保证。但由于商业化实时操作系统往往较多地考虑通用性,缺乏灵活性,对于一些特定的应用场合,其性能往往不能令人满意。同时,这种方案还存在着成本高,依赖于特定硬件等缺点。第二种方案可以从系统的实际要求和硬件的实际情况出发灵活地进行系统设计,易于满足一些特定场合的性能要求,成本也较低。但是,由于缺乏系统化、规范化的设计方法,缺少高层次抽象工具,使得系统的设计质量不容易得到保证,并严重地依赖于程序员的水平和经验。

　　本文针对上述第二种方案的局限,从进程和线程调度的角度出发,介绍了一种系统化、规范化和易于工程化实施的实时多任务系统软件设计方法,提出了“前向分支”的设计原则,并给出了完整的系统模型。

1 进程的划分

　　对复杂的系统需求进行模块化和层次化的划分是软件设计的基本方法。在实践中,复杂的系统需求通常被划分为一些功能相对独立的任务模块,每个任务模块被视作一个进程(process)。系统中如有多个进程并发(concurrent)运行,该系统就是一个多任务的系统。在图1所示的例子中,n个任务模块构成了宏观上并发运行的一组进程(即Proc_1～Proc_n)。Proc_5和Proc_9是两个具有代表性的进程结构。Proc_5是断续运行的进程,表示了某一顺序逻辑控制的流程。Proc_9是LCD汉字显示程序,其结构是典型的多重循环。其功能是将数组aDisplay中所描述的24×24点阵中文字符串送至LCD显示屏。aDisplay的结构参见图3(e)。Proc_9的基本工作原理如下:当cDisplay不为0时,依次从aDisplay中取出每个待显示汉字的点阵位置及其在LCD内部显存中的地址,根据这两个参数将一个汉字的点阵顺序发送到LCD内部显存中。直至全部汉字显示完,cDisplay减为0,Proc_9转入空闲状态,等待新的显示请求。

　　系统程序的主要任务之一就是对进程进行调度,包括启动和终止进程、管理进程之间的通讯、处理进程之间的优先级等。但是如果按图1的结构顺序调度进程、以进程为基本单位分配CPU时间的话,显然存在严重的问题。例如在Proc_5中,当程序处于等待K1闭合的状态时,其它任何进程都无法得到服务,尤其当K1出现故障时,系统将处于“挂起”状态。如果一个进程过多地占据了CPU时间,其他进程将不能得到公平、均匀的服务,响应时间无法得到保证,系统效率会降低。总之,只有将CPU时间的分配单位减小,才能解决上述问题。

2 线程的拆分

　　线程(Thread)是CPU的基本执行单位。一个进程可以由一个或多个线程构成。如前所述,单一线程的进程可能会存在诸多问题,而将一进程拆分为多个线程是解决上述问题的有效手段。由图1的Proc_5和Proc_9可以看出,一个进程过多地占据CPU时间，是因为其中含有次数不确定的等待循环、纯延时和较为耗时的多重循环。其中,纯延时可以用软件延时和中断定时两种方法实现,这两种方法在进程中又都可以归结为循环。因此,在拆分线程时应尽量遵循“前向分支”原则,使线程中不含有或少含有循环。

　　循环结构本质上是由一个分支判断和一个“反向”转跳构成的。所谓“前向分支”原则是指:在一次调度中,当程序发生分支时,应使程序跳向一段未被执行过的代码,而不得重复运行已运行过的代码。如果严格按“前向分支”原则拆分线程,循环结构将被完全消除。图2和图3分别是Proc_5和Proc_9严格按“前向分支”原则拆分为线程的结果。

　　如果进程设计遵循结构化程序思想,那么在对某一进程严格按“前向分支”原则进行线程拆分时,最小拆分数量可按如下方法确定:进程入口至第一个循环返回节点之间如无程序代码,最小拆分数量等于循环返回节点数Nback;进程入口至第一个循环返回节点之间如有程序代码,最小拆分数量等于Nback+1。实际拆分数量可以大于最小拆分数量,但不应小于该数,否则必然有一个以上的线程中含有循环。两个循环返回节点之间(或入口到第一个循环返回节点之间、最后一个循环返回节点到出口之间)的代码就构成了一个线程的主体。如果原进程中无循环,可将该进程当做单一线程对待。在图1中,Proc_9中共有4个循环返回节点(①～④),即Nback=4,按最小拆分数量拆分为4个线程(Proc_9Thread_1～Proc_9Thread_4)。Proc_5中循环返回节点数也为4,但其入口至第一个循环返回节点之间有代码,所以,Proc_5按最小拆分数量拆分为5个线程。

　　线程号变量tProc_n是系统中实现线程调度、在各相关线程间建立联系的核心。按“前向分支”原则进行线程拆分时,凡是遇到构成循环的“反向”分支时,就将该分支转向当前线程的出口,并在出口前为所在进程的线程号变量赋一新值指向要转去的线程。如果所要转去的线程与当前所在线程一致时,线程号变量赋值可以省略。

　　在按“前向分支”原则设计的线程中,“结构上”的循环可以完全消除,但进程设计中“逻辑上”的循环仍然是存在的,否则进程的原有功能将不能正确地实现。事实上,线程号变量中包含有“逻辑循环”的信息。只要在主循环中按图4的方法调度各线程就可以实现进程的“逻辑循环”。

　　为实现中断定时,Proc_5中设置了两个定时计数器cTimerAct_1和cTimerAct_2(以下称之为“动作定时器”),在启动定时时设置好其初值,由一个基础定时中断程序按一定的时间间隔(本例为1ms)减1。当动作定时器减为0时表示定时结束。

　　对于断续运行的进程(如Proc_5),结束任务时应将线程号变量指向任意一个不用的空线程。为统一和方便起见,本文约定所有进程的0号线程均为空线程,进程结束时线程号变量应置为0。

3 总体模型

　　综上所述,一个完整的、严格按“前向分支”原则进行线程拆分和进程调度的多任务系统模型可以归纳为图5所示的结构。该模型由三部分构成:主循环、分属于不同进程的“前向分支”的线程以及一个基础定时中断程序。该模型结构最大的特点是:除了主循环中最后一个回跳以外,其它任何地方都不存在循环结构。换言之,系统中所有的循环“反向”转跳,都被归并成了主循环中的一个回跳。这样的结构能使主循环在各进程间快速地切换,有利于提高CPU的利用率,改善系统的响应,使得各进程能够得到及时、均匀、公平的服务。同时,基础定时中断程序也完全是“前向分支”结构,有利于减少对CPU的占用。

考虑到各进程对响应时间和服务频度的不同要求,在该模型中设置了对各进程进行定时同步的功能。在基础定时中断服务程序中增加了同步定时器cTimerSyn_i和同步定时标志fTimerSyn_i。同步定时器和动作定时器构成了基础定时中断服务程序的主体。基础定时中断的中断间隔时间应按所有定时任务的最大公约数来选取,所选取中断间隔时间越大,对CPU的占用越少,越有利于系统效率的提高。

　　进程定时同步的本质是为不同响应时间需求的任务安排不同的服务频度。降低低优先级任务的服务频度相当于提高了高优先级任务的服务频度。在很多情况下,这样的优先级处理已令人满意。有一类进程出于功能(而不一定是优先级)的需要,也必须进行定时同步。

　　如前所述,严格按照“前向分支”原则拆分线程时,拆分数量不应小于进程中的循环返回节点数Nback或Nback+1。这是拆分线程时重要的参考依据。但是,在实际应用中,并不一定非要将线程中的循环彻底消除,应当根据具体情况和实际需求灵活掌握。

　　如果拆分粒度过细(即线程拆分数量过多),虽然对提高系统的响应速度有帮助,但由于进程切换过于频繁,进程切换所需的额外开销会导致系统效率下降(即有效的CPU机时占CPU总机时的比例下降)。粒度越细,这种情况也就越严重。另外,粒度越细,源程序和程序文档的可读性越差,为程序的调试和维护以及文档的维护带来困难。因此,在能够保证系统的响应速度和调度的均匀性等前提之下,拆分粒度倾向于粗一些。在多数情况下,倾向于将次数不确定的等待循环、较为耗时的循环和较长的纯延时拆分为线程。而那些循环次数确定且不太耗时的循环则建议保留。在这种情况下,线程拆分数小于Nback或Nback+1。

实时系统要求系统能够对输入做出快速的反应和处理。但是,“实时”只是一个相对的概念,响应时间快慢实际上是衡量一个系统是否“实时”的重要指标。由图5可以看出,对于本文所介绍的模型来说,由于进程都是确定的,响应时间可以大致按以下方法估算:各进程中最耗时线程的运行时间之和就是最不利的响应时间,平均响应时间应等于各进程中线程平均运行时间之和的二分之一。根据以上估算,还可以大致推断运行期间发生过几次定时中断。将基础定时中断所占用的CPU时间也估算进去,可以进一步提高响应时间估算的准确度。当然,响应时间也可以通过实验来测定。如果响应时间不能满足某一任务的要求,可以将长线程进一步拆分,或者应当考虑更换速度更高、能力更强的CPU。

　　子程序是程序设计中广泛应用的一种程序结构。在本模型的基础上,可以将子程序设计为子进程。子进程同样可按“前向分支”原则拆分为子线程,这样,系统中仍然可以消除所有的局部循环。子线程的拆分方法与上述线程的拆分方法类似,但需注意调用时的争用和重入问题。

　　以上介绍模型的调度算法简单、实现方法规范、对CPU资源没有特殊的要求。在实际应用中,该模型可以根据项目的具体情况灵活地变通和扩充。同时,该模型比较容易工程化实施,便于快速、低成本地构造系统程序的原型。但该模型没有对进程设置严格意义上的优先级,另外,源程序的可读性也不太令人满意。

　　与通用操作系统不同,该模型适用于静态内存分配和资源分配的确定性任务(多数的单片机应用项目和机电设备控制系统属于这种情形)。显然,该模型不适合那些在运行时动态加载、需要进行动态内存分配和资源分配的不确定性任务。

参考文献

1 Andrew S. Tanenbaum， Albert S. Woodhull.Operating System：design and implementation 2nd Ed.Prentice Hall，Inc.，1997

2 张海藩.软件工程导论(第三版).北京:清华大学出版社,1998