软件学报
JOURNAL OF SOFTWARE
1999年　第10卷　第9期　Vol.10　No.9　1999



DRT-UNIX系统的任务调度*
庞丽萍　吕文安　韩宗芬
摘要　任务调度是分布式实时系统的核心问题之一.文章概述了实时系统的任务调度，结合DRT-UNIX系统的实际情况，提出了一种任务调度算法，并对算法的优点进行了分析.
关键词　分布式实时操作系统，实时任务，调度．
中图法分类号　TP316
Task Scheduling in DRT-UNIX System
PANG Li-ping,Lü,Wen-an HAN Zong-fen
(School of Computer Science and Technology Huazhong University of Science and Technology　Wuhan　430074)
Abstract　Task scheduling is one of the key problems in distributed real-time systems. The task scheduling in real-time systems is introduced in this paper. Having taken some practical circumstances in DRT-UNIX system into account, an algorithm of task scheduling is proposed and the merits of the algorithm are analysed. 
Key words　Distributed real-time operating system, real-time task, scheduling.
　　随着微电子技术和计算机科学技术的发展，计算机已被广泛应用于科学研究和工业生产的许多领域.分布式实时系统在实时性、可靠性、可扩展性、容错性、自治性和并行性等方面较一般的实时系统更为突出和强大，能够满足许多复杂实时应用的需要，因此，分布式实时系统的支撑软件——分布式实时操作系统是当今计算机科学领域的研究热点之一.DRT-UNIX系统是我们研制的基于UNIX的分布式实时操作系统.
　　分布式实时系统最本质、最关键的特征是实时性和可预测性.实时系统的正确性不仅与计算结果的逻辑正确性有关，还与产生计算结果的时间有密切关系，因此，实时系统的首要目标是满足系统内实时任务的时间约束，合理地调度并执行它们，使其能在各自的限期(deadline)之前完成.任务调度是分布式实时系统的核心问题之一，已证明在不加任何限制条件的情况下，分布式实时系统的任务调度问题是一个NP难度问题［1］.本文将讨论DRT-UNIX系统的任务调度问题.
1 基本概念及定义
　　定义1. 一个周期任务Tpi可用如下四元式描述.
Tpi=〈Ci,Pi,Ri,Di〉,　　　0<Ci≤Di，0<Pi，0≤Ri,
其中Ci表示最大计算时间（在通常情况下，周期任务Tpi的计算时间要小于Ci），Pi表示周期，Ri表示到达时间，Di表示期限.
　　对于Tpi的第k次执行（fk≤1）有：就绪时间为Ri+(k-1)*Pi；最大计算时间为Ci;期限为Ri+(k-1)*Pi+Di.周期任务在每个周期的一次执行可称为该周期任务的一个实例或一次执行请求.
　　定义2. 一个非周期任务Tapj可用如下三元式描述.
Tapj=〈Cj,Rj,Dj〉,　　　0<Cj，0≤Rj，0<Rj+Cj≤Dj,
其中Cj表示最大计算时间，Rj表示到达时间，Dj表示期限.
　　定义3. 给定一个实时任务集M={Tp1,Tp2,...,Tpi,Tap1,Tap2,...,Tapj}，多处理机任务调度即是求M的一组子集Mi(i=1,2,...,k)，使得
　　〈a〉 Mi(i=1,2,...,k)两两不相交，且；
　　〈b〉 对于每一个Mi(i=1,2,...,k)中的周期任务与非周期任务，当将它们分配在一台处理机上执行调度时，能满足各自的时间约束条件.
　　满足上述〈a〉、〈b〉条件的调度称为有保证调度［2］，它能保证每个实时任务在其限期前完成，其中k为这种调度所需的处理机数目.在这里，假定除处理机外，其他所有的资源都是可以满足的.显然，这里的解不是唯一的，甚至子集的个数k也不唯一，当然希望子集Mi的个数k越小越好.当具有有保证调度子集Mi的个数k是最小时，就称这个解为该问题的最优解，求这种最优解的问题是一个NP难度问题.
2　实时系统任务调度概述
　　任务是分布式实时系统中可被调度及保证的实体，在处理机上以进程的形式运行.分布式实时系统任务调度要考虑的因素很多，如果兼顾所有的因素，将使调度问题变得异常复杂，导致失去实用价值.因而在实际应用中，为了简化问题，往往只考虑部分因素.在许多时候都假设系统除处理机之外的其他资源是足够多的，并且不考虑任务之间复杂的同步问题，而仅考虑任务的时间约束.我们在本文中的叙述也是以此为前提的.
　　实时任务包括周期任务和非周期任务.通常在一个实时系统中这两类任务并存.一般来说，周期任务是系统要处理的主要任务，占用处理机时间较多；而非周期任务则是系统为了处理一些意外情况或紧急事件所需执行的任务，占用处理机时间较少，而且非周期任务的数目也很小.因而任务调度的常见处理过程是先调度周期任务，在能保证周期任务时间约束条件的基础上，再考虑如何调度非周期任务，并保证其期限. 
　　虽然分布式实时系统的任务调度要比单处理机实时系统复杂得多，但前者是以后者为基础的，因此我们有必要先讨论一下单处理机实时系统的任务调度.单处理机实时系统通常采用基于优先级的可抢占调度.到目前为止，已提出了许多比较成熟的基于优先级的调度算法，比较有代表性的算法有:最早期限优先算法、最小松弛时间优先算法和速率单调算法.其中最早期限优先算法和最小松弛时间优先算法属于动态优先级调度算法，速率单调算法属于静态优先级调度算法.现已证明,在单处理机实时系统中，速率单调算法和最早期限优先算法分别是最优的静态和动态优先级调度算法［3］.从一般意义上来说，动态优先级调度算法在性能上要优于静态优先级调度算法.例如,对于周期任务的调度，最早期限算法所能取得的处理机利用率在理论上可高达100%，而速率单调算法一般为88%［4］.相对而言，动态优先级调度本身所需开销过大，而静态优先级调度则简单得多，并且速率单调算法是最优的静态优先级调度算法，它还具有其他的一些优点，如对其稍加变化就可有效地处理调度算法的稳定性、对非周期任务的响应及优先级反向等问题［5］，所以，速率单调算法及其变种在国外是实时任务调度研究领域的热点之一，已有人推导出在单处理机实时系统中速率单调算法调度的充分必要条件［4］.
　　 分布式实时系统的任务调度是NP难度问题，因此很多人尝试用不同的启发式算法寻找次优解.在分布式实时系统中，通常将同一个周期任务的每个实例放在同一台处理机上运行，对周期任务不存在动态迁移，但允许非周期任务动态迁移，实际上对周期任务采取的是一种静态调度策略.常常采用如下调度方案［6］：每个处理机上有局部调度器和全局的分布式调度器.
系统中的每个节点确保完成本节点上的周期任务，同时允许非周期任务随机到达任何节点，当局部调度器无法保证该非周期任务的时间约束时，提交分布式调度，将其迁移到一个合适的节点上去.各种不同调度算法只是在非周期任务的迁移时机、迁移策略等方面有所不同，从而导致实际运行的性能有所区别，但总的来说所付出的开销也是比较大的.
　　分布式实时系统的任务调度是国内外研究的热点之一.但这些研究有的仅仅局限于理论上的探讨，考虑实际的因素较少，因而实用性不强;有的则完全从实用的角度出发，为了使问题简化，尽量用一些简单的调度算法，导致在理论上无可取之处;因此有必要在这方面作进一步的研究，并结合一些实际因素，为DRT-UNIX系统设计一个有效、实用的有保证调度算法.
3　DRT-UNIX系统的任务调度
　　实时系统的首要目标是满足任务的时间约束，从这个角度来说，对实时任务最好采用静态调度.在只考虑任务的时间约束的条件下，已提出了许多静态调度算法，例如,RMNF［7］,RMFF［7］,FFDUF,RMBF等，它们都是基于速率单调算法的，但这类算法有一个不足之处是,要求周期任务的周期等于其期限.而在实际中，许多实时应用的期限往往小于其周期.本文将针对这类问题提出相应的处理方案，这样可满足更多问题的需要.为了方便地说明问题，我们先作如下假设和说明.
　　(1) 系统是同构的；
　　(2) 每台处理机上采用基于固定优先级的可抢占调度策略；
　　(3) 提交的实时任务包括周期任务和非周期任务；
　　(4) 周期任务只能在系统开始工作之前一次性提交，系统在运行过程中不再接收任何周期任务；
　　(5) 对于周期任务Tpi而言，Ri=0，Di≤Pi；
　　(6) 不考虑任务之间复杂的同步问题，在调度时将任务之间的同步、通信等作为一种开销考虑进来，将有交互关系的多个任务尽量分配到同一台处理机上；
　　(7) 通过测量任务调度的各部分系统开销，将这些开销平摊到各任务的计算时间中去，这样,在任务调度时就考虑了系统开销.
3.1　对非周期任务的处理
　　在一个分布式实时系统中，周期任务在系统开始运行时就已确定，而非周期任务则在系统整个运行过程中随时都有可能到达.因此,对于周期任务可以采用静态调度的方式来保证其期限，而对于非周期任务,由于其到达的随机性,用静态调度的方式很难保证其期限.不管在什么时候，非周期任务实际上要由节点上的局部调度器（即通常所说的进程调度）来明确保证其期限，在任务调度这一级很难既达到较好的调度性能又能绝对保证各非周期任务的期限.在允许任务（一般是指非周期任务）动态迁移的分布式实时系统中，如果一个节点发现自己不能保证某一非周期任务的期限，可以将其迁移到系统中另外一个适当的节点上运行，以保证其期限.在DRT-UNIX系统中，由于采用静态调度，不存在任务迁移，所以只好采用一定的冗余措施，即增设周期任务，由它参与调度，代表非周期任务去竞争处理机资源.
　　虽然非周期任务是随机到达的，但分布式实时系统一般都有其具体的应用背景.在这一应用背景下，非周期任务最大计算时间C、到达的最小间隔时间P等是可以预先知道的，可根据这些信息在系统内增设周期服务器来响应非周期任务的请求.周期服务器实质上也是一个周期任务.一般来说，在一具体应用背景下，如果非周期任务的数目不多，则只需增设一个周期服务器，否则可以多增设几个；周期服务器的计算时间置为非周期任务的最大计算时间C，周期和期限均置为非周期任务到达的最小间隔时间P，到达时间置为0.
　　周期服务器S可简单地表示为S=〈C,P〉，用周期服务器S响应非周期任务的基本思想是由S代替各非周期任务去竞争处理机资源.假设周期服务器S管理的时间为STA，其初始值为0，每当系统调度到周期服务器S运行时，具体操作如下：
　　(1) STA=STA+C；
　　(2) 如果存在非周期任务正在等待或刚到达，则系统响应非周期任务，并从STA中减去用掉的时间；
　　(3) 如果没有非周期任务在等待，也没有非周期任务到达，却有周期任务在等待，则假设正在等待的优先级最高的周期任务为Tpi，系统就将本该分配给周期服务器S的处理机时间用于运行Tpi，直到Tpi被新来的非周期任务抢占，或者是运行完毕，或者是系统分配给S的处理机时间用完，相应地从STA中减去用掉的时间；在随后调度到Tpi时，Tpi向S归还刚才所用的时间(加在STA中)，S可用这部分时间继续响应非周期任务或“借给”当前优先级最高的周期任务，依此类推.
　　实际上,周期服务器S管理的时间并非系统在每个周期分配给它的计算时间C，最初分配给它的处理机时间是C，但随着系统的运行，S管理的时间可能被分割成一段段的时间片，但实际上，系统在每个周期分配给它的处理机时间总量仍为C.将该周期服务器S与用户提交的任务集中的周期任务一起调度并分配处理机，然后把所有的非周期任务分配给周期服务器S所在的处理机.这样，任务集中的非周期任务可由该周期服务器S在系统中的某一台处理机上代它们去竞争处理机资源，对整个实时任务（包括周期任务和非周期任务）的调度则可转化为对单一的周期任务的调度，既简化了调度本身的工作，又增加了系统行为的可预测性.
3.2　对周期任务的处理
　　定理. 设在一台处理机上有一组周期任务，按优先级从高到低的顺序排列,依次为Tp1，Tp2，...,Tpn，对于其中的周期任务Tpm，定义

Nm=min{k|Wm(k,k*Pm)≤1},
其中m≤1，k≥0，x>0，如果满足，则这组周期任务在该处理机上存在可行调度.
　　证明：假设分配给周期任务Tpj的优先级为j，j越小则其对应的优先级越高.先考查任务组中任意一周期任务Tpi期限的满足情况：
　　Cj*［t/Pj］+Ci是时间区间［0,t］内周期任务Tp1，Tp2，...,Tpi-1的所有执行请求和Tpi的第1次执行请求对处理机的累积需求量，这时可以忽略周期任务Tpi+1，Tpi+2，...,Tpn的执行请求，因为它们的优先级比Tpi低，能够被抢占.当且仅当Cj*［t/Pj］+Ci≤t（t<Dn）时才能保证Tpi的第1次执行请求的期限，因为在t时刻处理机已完成Tpi的第1次执行请求及优先级比它高的其他计算；显然,满足Cj*［t/Pj］+Ci=t的最小t值就是Tpi的第1次执行请求的完成时刻.如果没有优先级为i或更高优先级的计算要处理，则开始于时刻0的i级忙周期将在Tpi的第1次执行请求完成时结束.
　　如果Wi(1,Di)≤1，则Tpi的第1次执行请求的期限能得到保证；若Wi(1,Pi)≤1，则i级忙周期结束.如果Wi(1,Di)≤1而Wi(1,Pi)>1，则Tpi的第1次执行请求的期限能得到保证，但是在超过时刻Pi时，i级忙周期却未结束.现在,我们考查Tpi的第2次执行请求，如果用周期任务Tpi′（其最大计算时间为2*Ci，期限为Pi+Di）代替Tpi，则当且仅当Wi(2,Pi+Di)≤1时Tpi的第2次执行请求的期限能得到保证，此时若Wi(2,2*Pi)>1，就必须检查周期任务Tpi后面的执行请求期限的满足情况；实际上，Tpi的前Ni个执行请求是i级忙周期的一部分（因为总的处理机利用率不会超过1，所以Ni的值是有限的），这样，如果Wi(k,(k-1)*Pi+Di)≤1，则Tpi的期限能得到保证.依此类推，如果对于任务组中每一个周期任务Tpj都有Wj(k,(k-1)*Pj+Dj)≤1，即Wj(k,(k-1)*Pj+Dj)≤1，则任务组中每一个周期任务的期限都能得到保证，也就是这组周期任务在该处理机上存在可行调度.
　　说明：任务组中的周期任务可根据需要选择一种优先级分配策略，例如，按其周期、重要性等分配优先级，但是要注意，任务的优先级一旦分配就保持不变.
　　算法. 
　　(1) 对周期任务排队，将有交互关系的任务按周期非减的顺序排在一起，位于队列的前面，其他任务按周期非减的顺序挂在队列的后面，假设重排后的顺序为Tp1，Tp2，...,Tpm；
　　(2) 初始化：i=1，M=1；
　　(3) 将周期任务Tpi分配给处理机M，i=i+1；
　　(4) (4.1) j=1；
　　　　(4.2) 若周期任务Tpi与其他某些任务有交互关系，如果Tpi是这些有交互关系的任务中最先被调度到的，则M=j+1，转(3)，否则，j等于与Tpi有交互关系的任务所在的处理机号；
　　　　(4.3) 如果Tpi和已分配到处理机j上的任务一起在该处理机上存在可行调度，即：
　　若将Tpi和已分配到处理机j上的任务按周期非减顺序排列，任务编号为1,2,...,n，满足：该处理机利用率小于或等于1且Wy(k,(k-1)*Py+Dy)≤1,则将Tpi分配到处理机j上去，转(5)；
　　否则，如果j=M，则M=j+1，转(3)；否则，j=j+1,转(4.3)；
　　(5) 若所有的周期任务都已分配完毕，则算法终止；否则，i=i+1，转(4).
　　注：M的最终值是调度该周期任务集所需的处理机数.
4　算法性能分析与说明
　　为了简化问题，许多文献在讨论多处理机实时系统的任务调度时，往往假设周期任务的周期与期限重合，即在一个周期内，周期任务的期限就是本次周期的结束时间.与同类算法（如RMNF,RMFF,FFDUF,RMBF等）相比，本文提出的调度算法最大的优点是允许周期任务的期限小于周期，这在一定程度上会扩大算法的应用范围.作为本算法处理的一种特殊情况，当周期任务的期限等于周期时，通过模拟实验比较本算法与RMNF,RMFF,FFDUF,RMBF等算法的性能,发现:对于同一组实时任务，用本文的算法调度所需的处理机数不会多于后面几种算法调度所需的处理机数，也就是说，相对于一些同类算法来说，本文的算法不仅适用范围宽，而且性能不比它们差.
　　在模拟实验中，根据本文开始的定义，每个周期任务Tpi包括4个参数：最大计算时间Ci,周期Pi,到达时间Ri及期限Di.此外，本算法还作了如下假设：Ri=0，Di≤Pi.在满足这些条件的情况下，随机生成若干组周期任务(每组任务不少于10个)，依次以其中的每一组周期任务作为输入，同时用RMNF,RMFF,FFDUF,RMBF等算法及文献［6］中提出的新算法和本文的算法分别进行处理，确定能否将所有的周期任务都分配完毕，若存在一个调度，就得到该周期任务集所需的处理机数.调度结果显示：对于同一组周期任务，用本算法调度所需的处理机数不比其他几种算法需要的多，这实际上意味着本算法与其他几种算法相比较，适用范围要广一些，性能也较好.
　　其次，本算法能够同时保证周期任务和非周期任务的期限，增强了系统的可预测能力.目前的文献中，很少讨论到同时保证多处理机系统的周期任务和非周期任务的期限这个问题；有的文献仅专门讨论如何调度周期任务，从而保证其期限，根本未涉及调度非周期任务的问题；另外还有一些文献研究了在假设已保证了周期任务期限的情况下，对于非周期任务，只能在不影响对周期任务的调度的前提下设法加快其响应时间，却不能事先绝对地保证其期限，从而降低系统的预测能力.本文的算法能同时保证周期任务和非周期任务的期限，增强了系统的预测能力.
　　此外，相对于有些文献中提出的许多任务调度算法而言，本算法还考虑了有交互关系的任务的调度.调度原则是：将有交互关系的多个任务尽量分配到同一台处理机上.如果这样做与确保任务的期限有矛盾、可以将它们分在不同的处理机上，同时将任务之间的同步、通信等开销考虑进来，并作适当的处理.
5　结束语
　　分布式实时系统的任务调度是一个很复杂的问题，不存在一个对所有情况都适用的通用解，许多学者在研究这类问题时往往先作一些假设和限制.本文在已提出的一类算法的基础上，为DRT-UNIX系统提出了一种任务调度算法，虽然该算法有一些改进之处，但是所考虑的因素还是有限的.我们下一步的研究将考虑包括处理机.I/O以及通信信道等存在任务竞争的常用资源的调度，对存在复杂同步关系任务的调度也将进行研究.
*　本文研究得到国防预研基金资助.
本文通讯联系人：庞丽萍,武汉430074,华中理工大学计算机科学与技术学院
作者简介：庞丽萍，女，1944年生，教授，主要研究领域为并行/分布式程序设计，分布式实时操作系统.
　　　　　吕文安，1973年生，硕士生，主要研究领域为分布式实时操作系统，UNIX系统.
　　　　　韩宗芬，女，1950年生，副教授，主要研究领域为分布式实时操作系统，软件工程.
作者单位：华中理工大学计算机科学与技术学院　武汉　430074
参考文献：
［1］Burns A. Scheduling hard real-time systems: a review. Software Engineering Journal, 1991,6(3)：116～128
［2］刘键.分布式计算机系统基础．北京：人民邮电出版社，1990
(Liu Jian. Distributed Computer Systems. Beijing: People's Posts & Telecommunications Publishing House, 1990)
［3］Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of ACM, 1973,20(1):46～61
［4］Lehoczky J P, Sha L, Ding Y. The rate-monotonic scheduling algorithm: exact characterization and average case behavior. In: Doug Locke ed. Proceedings of IEEE Real-time Systems Symposium. Los Alamitos, CA: IEEE Computer Society Press, 1989. 166～181
［5］Sha L, Lehoczky J P, Rajkumar R. Solutions for some practical problems in prioritized preemptive scheduling. In: Kang Shin ed. Proceedings of IEEE Real-time Systems Symposium. 1986. 181～191
［6］Burchard A, Liebeherr J, Oh Y F et al. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Transactions on Computers, 1995,44(12):1429～1442
［7］Dhall S K, Liu C L. On a real-time scheduling problem. Operations Research, 1978,26(1):127～140
收稿日期：1998-06-15，修改日期：1998-09-21
