周兴铭

第３９卷第１０期 计算机研究与发展 Ｖｏ１．３９，Ｎ。．１０

２００２年１０月 ＪＯＵＲＮＡ１ ＯＦ ＣＯＭＰＵＴＥＲ ＲＥＳＥＡＲＣＨ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ Ｏｃｔ．２００２

一种基于延迟抢先的消息最大

响应时间算法

窦 强 周兴铭

（国防科学技术大学计算机学院 长沙４１００７３）

（ｄｏｕｑ＠ｓｉｎａ．ｃｏｒｎ）

摘 要 分布式实时系统是实时系统的一个重要研究方向，有着广泛的应用背景．消息最大响应时间的定量分析

是该研究方向中的一个关键问题．在深入分析国内外相关研究的基础上，针对采用ＴＤＭＡ协议的分布实时系统提

出了一种基于延迟抢先的消息最大响应时间算法，解决了现有消息最大响应时间算法中存在的正确性问题，对消

息的最大响应时间做出了完整、精确的分析．

关键词 实时系统，分布式，可调度性分析，消息，最大响应时间，ＴＤＭＡ协议

中图法分类号ＴＰ３１ ６．２

Ａ ＷｏＲＳＴ—ＣＡＳＥ ＲＥＳＰｏＮＳＥ ＴＩＭＥ ＡＮＡＬＹＳＩＳ ＡＬＧ０ＲＩＴＨＭ ｏＦ

ＭＥＳＳＡＧＥＳ ＷＩＴＨ ＤＥＦＥＲＥＤ ＰＲＥＥＭＰＴＩｏＮ

ＤＯＵ Ｑｉａｎｇ ａｎｄ ＺＨＯＵ Ｘｉｎｇ—Ｍｉｎｇ

（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ ４１００７３）

Ａｂｓｔｒａｃｔ Ｉｎ ａ ｄｉｓｔｒｉｂｕｔｅｄ ｒｅａｌ—ｔｉｍｅ ｓｙｓｔｅｍ，ｗｏｒｓｔ—ｃａｓｅ ｒｅｓｐｏｎｓｅ ｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ｍｅｓｓａｇｅｓ ｉｓ

ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｔｏ ｓｙｓｔｅｍ ｓｃｈｅｄｕｌａｂｉ¨ｔｙ ａｎａｌｙｓｉｓ．Ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ ｉｓ ａ ｗｏｒｓｔ—ｃａｓｅ ｒｅｓｐｏｎｓｅ

ｔｉｍｅ ａｎａｌｙｓｉｓ ａｌｇｏｒｉｔｈｍ ｏｆ ｍｅｓｓａｇｅｓ ｗｉｔｈ ｄｅｆｅｒｒｅｄ ｐｒｅｅｍｐｔｉｏｎ ｉｎ ａ ｄｉｓｔｒｉｂｕｔｅｄ ｒｅａｌ ｔｉｍｅ ｓｙｓｔｅｍ

ｕｓｉｎｇ ｔｈｅ ＴＤＭＡ ｐｒｏｔｏｃｏ１．Ｂｙ ｓｏｌｖｉｎｇ ａ ｃｏｒｒｅｃｔｎｅｓｓ ｐｒｏｂｌｅｍ ｅｘｉｓｔｉｎｇ ｉｎ ｆｏｒｍｅｒ ａｌｇｏｔｈｒｉｍｓ，ｔｈｉｓ

ａｌｇｏｒｉｔｈｍ ｃａｎ ｐｒｅｃｉｓｅｌｙ ｄｅｒｉｖｅ ｔｈｅ ｗｏｒｓｔ—ｃａｓｅ ｒｅｓｐｏｎｓｅ ｔｉｍｅ ｏｆ ｍｅｓｓａｇｅｓ．

Ｋｅｙ ｗｏｒｄｓ ｒｅａｌ—ｔｉｍｅ ｓｙｓｔｅｍ，ｄｉｓｔｒｉｂｕｔｅｄ，ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ，ｍｅｓｓａｇｅ，ｗｏｒｓｔ—ｃａｓｅ ｒｅｓｐｏｎｓｅ

ｔｉｍｅ．ＴＤＭＡ ｐｒｏｔｏｃｏｌ

１ 引 言

分布式实时系统与单机实时系统相比在性能价

格比、系统可扩充性和容错能力等许多方面都具有

一定优势，目前许多关键性的控制领域，如航空航天

器与机动车辆的驾驶控制、工业的生产控制等，都已

经或正准备采用分布式实时系统，以降低造价、减轻

重量、提高系统的可靠性和快速反应能力．由于这些

原稿收到日期：２００１—０７—０６；修改稿收到日期：２００２—０６—１０

关键领域对系统的实时特性、容错能力等都有很高

的要求，并且一旦这些需求得不到满足，会造成巨大

的且无法挽回的生命、财产损失以及环境危害．因此

需要有一种非常严谨的分析手段，即系统的可调度

性分析，来分析和验证分布式实时系统在最大负载

下或部件失效的情况下是否仍能满足应用的实时性

要求，这对保障系统的安全运行意义极为重大．例如

在Ｂｏｅｉｎｇ ７７７飞行控制软件的开发过程中，其中超

过５Ｏ 的开发时间和精力都被投入到了系统的可

ｌＩ＿莲瞧｜＿

维普资讯

１４００ 计算机研究与发展

调度性分析和软件测试中．

分布式实时系统的一个重要特点是任务间的消

息通信，要分析系统整体的实时特性必须要考虑到

消息通信的时间开销．因此，消息的最大响应时间分

析，即消息从源节点完整发送到目的节点所需最大

时间的定量分析，一直都是系统可调度性分析中的

一个重要研究课题．许多其它问题的解决如任务的

划分方法、任务和消息的调度策略等都是以消息的

最大响应时间分析为基础的．在这方面很多学者已

经进行了一些研究，如Ｔｉｎｄｅｌｌ［１］就针对ＴＤＭＡ协

议提出了一种消息的最大响应时间分析算法，但由

于消息模型比较简单，未考虑消息的延迟抢先特性，

因此分析不够精确．Ｂｕｒｎｓ等人［２ 提出了延迟抢先

的概念并提出了相应的基于延迟抢先的消息最大响

应时间分析算法，但该算法是针对点对点线路提出

的，不适用于分布式实时系统，而且更重要的是算法

的正确性存在问题，在某些情况下，该算法会低估消

息通信的时间开销，从而可能会导致系统的可调度

性分析做出错误的结论．Ｔｉｎｄｅｌｌ Ｅ。 在Ｂｕｒｎｓ Ｅ 等人

工作的基础上分别对Ｔｏｋｅｎ Ｒｉｎｇ和Ｐｒｉｏｒｉｔｙ Ｂｕｓ

两种网络协议进行了消息最大响应时间分析，

Ｉａｉｎ［ ，Ｈｅｎｒｉｋ［ ］以及Ｐａｕｌ［ ］也在Ｂｕｒｎｓ［ 等人工作

的基础上进行了一些调度算法等方面的研究，但它

们均未解决上述Ｂｕｒｎｓ［２ 算法存在的正确性问题．

本文针对ＴＤＭＡ协议提出了一种基于延迟抢先的

消息最大响应时间算法，解决了上述问题，对采用

ＴＤＭＡ协议的分布式实时系统中的消息最大响应

时间做出了完整、精确的分析．

本文共分６节，第２节建立了一个分布式实时

系统的计算模型，并简单介绍了ＴＤＭＡ协议；第３

节给出了一些基本概念的定义；第４节针对ＴＤＭＡ

协议提出了一种基于延迟抢先的消息最大响应时间

算法；第５节通过一个简单实例将本文算法与

Ｂｕｒｎｓ＿２ 算法进行了对比；最后第６节对全文做出了

简短的总结．

２ 系统模型

分布式实时系统一般由若干个节点和连接各节

点的互连网络组成，文献［１～３］中提出的节点构成

如图１所示．系统中每个节点都由一个处理机和一

个网络接口部件组成，处理机与网络接口部件之间

共享一个报文发送队列和一个报文接收队列．

本文假定系统中各节点的任务集都是周期任务

集，且任务不会在节点之间迁移．各节点的消息集也

是一个周期消息集，它包括了由该节点上任务发送

给其它节点上任务的各种消息．消息的产生模型为

对于每种消息，消息的源任务每隔固定任务周期产

生一条该消息的消息实例；消息实例的长度对于每

种消息来说是固定的；在发送前，消息实例被分割为

若干报文，报文的长度是固定的；在下一个消息周期

开始前，该消息实例一定要发送完成．本文还假定消

息的发送采用固定优先级抢先式调度算法，高优先

级消息的报文优先得到发送．在本文中，我们并不关

心消息的优先级分配策略，但假定同一节点内各消

息的优先级是互不相同的．

图１节点构成

ＴＤＭＡ协议是一种具有很强确定性的网络通

信协议，具有较好的容错性和时间响应特性，因此许

多分布实时系统中采用的通信协议都是在ＴＤＭＡ

协议的基础上演变而来的，如ＴＴＰ／Ｃ，ＦｌｅｘＲａｙ以

及Ｂｙｔｅｆｌｉｇｈｔ等．ＴＤＭＡ协议中，每个节点都被分

配了固定长度的发送时隙，节点只能在自己的时隙

中发送数据．如果不考虑时钟同步漂移的问题，各节

点的发送时隙在时间上是连续的．从第１个节点发

送时隙的开始时刻到最后一个节点发送时隙的结束

时刻之间的时间间隔称为一个ＴＤＭＡ周期，当一

个ＴＤＭＡ周期结束后，下一个ＴＤＭＡ周期立刻开

始，如此循环反复．本文假定各节点发送时隙的长度

都是报文发送时间的整数倍．

３基本概念定义

定义１．消息产生的周期称为消息周期．

根据第２节假设，消息周期是源任务周期的整

数倍．

定义２．消息的发送时间是指将消息的一个消

息实例发送到网络上所需要的时间．

维普资讯

１０期 窦 强等：一种基于延迟抢先的消息最大响应时间算法

每种消息的消息实例都可分割为固定数量的报

文，因此每种消息的发送时间是固定的．

定义３．在一个消息周期中，源任务将消息实例

放入发送队列的时刻称为消息实例的释放时刻，释

放时刻与该消息周期起始时刻之间的差值称为该消

息实例的释放偏移．由于源任务运行条件的复杂性，

各消息实例的释放偏移可能有所不同，其最小值为

０，最大值称为该消息的释放抖动．

定义４．从一个消息实例的释放时刻开始，到该

实例中的第ｋ个报文发送完成时为止的这段时间称

为该消息实例第ｋ报文的响应时间，所有消息实例

第ｋ报文的响应时间的最大值称为该消息第ｋ报文

的最大响应时间．

定义５．从一个消息实例的释放时刻开始，到该

实例发送完成时为止的这段时间称为该消息实例的

响应时间，所有消息实例的响应时间的最大值称为

该消息的最大响应时间．

定义６．从一个消息实例的释放时刻开始，到该

实例中的第ｋ个报文开始发送时为止的这段时问称

为该消息实例第ｋ报文的等候时间，所有消息实例

第ｋ报文的等候时间的最大值称为该消息第ｋ报文

的最大等候时间．

定义７．消息的关键情形：消息的关键情形是指

在该种情形下该消息消息实例的响应时间将达到最

大值．

定义８．在网络通信中，不论报文的优先级如

何，一个报文一旦开始发送就不能被任何其它报文

中断，这种特性称为报文的延迟抢先特性．

在消息的最大响应时间分析中，如果不考虑报

文的延迟抢先特性，即报文在发送过程中可被在其

问到达的任何高优先级报文抢先，则报文的响应时

间会因此增大，从而使分析结果不精确，高于实际的

消息最大响应时间，最终导致过于悲观保守的系统

设计，浪费系统资源，增加系统造价．

４ 基于延迟抢先的ＴＤＭＡ协议的消

息最大响应时间算法

假定系统中某节点ＪＶ发送给其它节点的消息

集为｛ ．， ：，…， ｝，其中ｃ为消息种类数，消息

可用一个三元组（Ｌ厂 ，Ｘ ，Ｔ ）来表示，其中Ｌ厂 为消息

的释放抖动；Ｘ 为消息 的发送时间，Ｘ 一Ｐ ×

Ｐ，Ｐ 指 ，的消息实例分割成的报文数量，Ｐ为报文

的发送时间；Ｔ 为 的消息周期．消息 的最大

响应时间记为Ｒ ，消息 第ｋ报文的最大响应时间

和最大等候时间分别记为 和 （１≤正≤Ｐ ），显

然有Ｒ —ｒ』＇ ，此外根据报文的延迟抢先特性，不难

看出，Ｊ 一 Ⅲ＋Ｐ，因此Ｒ 一 ＋Ｐ．

假定节点ＪＶ的发送时隙长度为Ｓ ，ＴＤＭＡ周

期记为７１ 。 ，根据ＴＤＭＡ协议，在每个ＴＤＭＡ周

期中，其它节点都要占用其中（７’ ｏ —Ｓ ）的时问，

不难看出，对于节点ＪＶ，其它节点对网络资源的这

种周期性占用非常类似于一个周期性消息对网络资

源的占用．因此，为便于分析节点ＪＶ的消息最大响

应时间，我们有如下定义．

定义９．对于节点ＪＶ，其它节点对网络资源的

占用可看成是一个周期性消息对网络资源提出的周

期性请求，这个周期性消息就被称为是节点 的虚

拟消息．

我们将节点ＪＶ的虚拟消息记为 ，根据消

息模型，这个消息可用三元组（０，（７１ ｒ【 一Ｓ， ），

７ ｏ ）来表示．由于各节点时隙是固定的，需要严格

遵守，因此虚拟消息的优先级被设为最高．本文以下

的讨论都是基于消息集｛ ．， 。，…，ｍ ， ， ｝进行

的，这个消息集我们记为 ，并将 中优先级高于

，的消息集合记为 声（ ）．

定理１．消息 的关键情形出现在同时满足以

下条件的情况下：

① （ ）中消息所产生的消息实例同ｍ 的消

息实例在同一时刻释放；

②在消息实例同时释放前，坳（ ）的消息实例

的释放偏移分别为各自的释放抖动；在这之后，所有

（ ）中的消息产生的后续消息实例的释放偏移均

为０；

③一个低优先级报文在 的消息实例释放时

刚好开始发送．

证明．图２描绘了当这些条件满足时的情况，

其中ｔ。表示共同的释放时刻．

（１）对于Ｖ ∈ｈｐ（ ），假设 ，消息实例的释放

时刻与 消息实例的释放时刻不相等．当 消息

实例释放时， ，有两种可能，一种可能是 ，正在发

送一个消息实例，第２种可能是 ，已经发送完成上

一个消息实例，正在等待下一个实例的释放．对于第

１种可能如图３所示， 消息实例的释放时刻为ｔ ，

消息实例的释放时刻为ｔ：，由于在时间段Ｉｔ．，ｔ ］

内 ，要发送报文，因此即使将 消息实例的释放

时刻提前为Ｉｔ．，ｔ：］中的任意值，该实例的发送完成

时间仍然保持不变，从而使 消息实例的响应时间

维普资讯

１４Ｏ２ 计算机研究与发展

增大．因此当 消息实例的释放时刻提前至ｔ 时，

消息实例的响应时间取得最大值，此时 消息

实例的释放时刻与 ，消息实例的释放时刻相等．对

于第２种可能如图４所示， ，消息实例的释放时刻

为ｔ ， 消息实例的释放时刻为ｆ ．显然，如果将 ，

消息实例的释放时刻提前， 的后续消息实例可能

会在 消息实例发送完成前被释放，而且抢先于

消息实例之前得到发送，从而使 ，消息实例的

响应时间增大．因此当 ，消息实例的释放时刻提前

到ｔ 时， 消息实例的响应时间取得最大值，此时

巩消息实例的释放时刻与 ，？肖息实例的释放时刻

相等．

图２消息 ，的关键情形

图３第１种可能情况

ｌ

Ｗ 。。。。。。●。。●。。。。。●＿－＿。。。。。。。。＿＿。。——

，

，

图４第２种可能情况

（２）对于Ｖｍ ∈ｈｐ（ ），假定７．Ｕ 的一个消息实例

与 的一个消息实例在ｔ 时刻同时释放，且该 ，

实例的释放偏移为 （０≤ 矗≤Ｊ ）．通过计算可知，

ｍ，后续实例的到达时刻为ｔ ｊｉｔ＋丁 ，…，ｔｌ ｊｉｔ＋

Ｔ，，（ ＞０）．如图５所示．显然． 赴越大，且后续实例

的释放偏移越小，后续实例的释放时刻就越接近ｆ 。

ｍ 消息实例的响应时间也会随之增大或保持不变

（因为可能会有更多的 ，的后续消息实例抢先于

消息实例之前得到发送）．因此，当ｆｉｔ—Ｊ，且 ，

后续实例的释放偏移都为０时， ？肖息实例的响应

时间取得最大值．

图５释放抖动对 响应时间的影响

（３）在网络通信中，由于报文具有延迟抢先特

性，因此消息 ，的一个消息实例可能会因为等待一

个低优先级报文发送完成而被阻塞。从而增大消息

实例的响应时间．假设一个低优先级报文的开始发

送时刻为ｔ ， 的一个消息实例的释放时刻为ｔ！．如

果ｔ ＞ｆ。，根据消息调度策略，该报文的发送对 消

息实例的响应时间没有影响．如果ｔ ≤ｆ：，该情况与

（１）中的第１种可能比较类似，因此当ｔ 一ｔ 时。

消息实例的响应时间取得最大值． 证毕．

定理２．在消息 的关键情形下，对Ｖｋ（１≤志

≤Ｐ ），巩消息实例的第ｋ报文响应时问以及第ｋ

报文等候时间均达到最大值．

证明．证明过程与定理１的证明类似，不再赘

述．

根据定理２，若消息 在ｔ。时刻释放的一个消

息实例满足定理１所述条件，则对Ｖ志（１≤志≤Ｐ ），

该消息实例的第ｋ报文响应时间的值就是ｒｆ１ ，该消

息实例的第ｋ报文等候时间的值就是硼 ．该消息

实例的第ｋ个报文记为 ．

该消息实例的第ｋ报文等候时间即硼 是由３

部分构成的：第１部分是该实例发送前（志一１）个报

文本身所需的发送时间，记为Ｃ ，显然Ｃ ：（矗

１） ；第２部分是该实例在前（志一１）个报文的发送过

程中因为等待一个低优先级报文发送完成而被阻塞

的时间，称为阻塞时间，记为ＢⅢ，根据定理１中条

件③，显然有Ｂ —ｌ０；第３部分是该消息实例在第ｋ

个报文开始发送前因高优先级消息实例的抢先发送

维普资讯

１０期 窦 强等：一种基于延迟抢先的消息最大响应时问算法

而被阻碍的时间，称为阻碍时间，记为， ．

直接计算Ｉｉ．ｋ较为困难，因此我们采用迭代的方

式来计算叫Ⅲ和， ，我们将第ｑ次的迭代结果分别

记为ｚｕ…（ｑ）和， ，其中ｑ≥０．首先给定初值， 一０，

－

－ＣⅢ＋Ｂ ＋， ＝ｋｐ，这是不考虑阻碍时间时

的第ｋ报文等候时间．对Ｖ ∈ｈｐ（ ），根据定理ｌ中

条件①和条件②，ｍ，的一个消息实例也在ｔ。时刻释

放，如图６所示：

Ｉ

Ｉ、

ｍ｜ Ｊｉ ｌ Ｉ … ｌ ｌ

ｗ

： ｍ

ｉ ●＿＿＿＿—— ＿。●。－。。－●＿－＿＿＿＿＿＿＿＿＿—— … 厂＿］

，

，

图６ ，消息实例对 ，消息实例的阻碍时Ｊ司

在时间段［ｆ。，ｔ。＋叫 ］内，消息 ，共释放了

厂 Ｔ ］个消息实例，这些消息实例均要抢先

于户 之前发送，此外，如果叫 ＋．，，一ｉＦ，，（＿厂＞０），

则消息 还会在ｔ。＋叫 时刻释放一个消息实例，

因为该消息实例优先级比较高并且此时户 正准备开

始发送，所以该实例也会优先于Ｐ 得到发送

（Ｂｕｒｎｓ＿２ 算法正是因为未考虑在ｔ。＋叫 时刻释放的

高优先级消息实例对户 的抢先，所以低估了消息的

最大响应时间），因此消息 ，在时间段［ｆ。，ｔ。＋叫 ］

内对 ，的阻碍时间应为ｆ Ｌ ＿Ｊ＋ １×ｘ ，总

阻碍时间 Ｉ

Ｅ ｈｐ ｆ Ｌ＿Ｊ＋ ］× Ｖ （ｆ）【一 一 Ｊ

ｘ ，从而得到新的等候时间叫 —ＣⅢ＋ＢⅢ＋ ．

由于 ＞ＺＵ…（０），即等候时间增大，从而可能会使阻

碍时间进一步增大，通过与上面类似的分析可知，在

时间段 。，ｔ。＋叫 ］中，高优先级消息实例对ｍ。的

妨碍时间 ∑ ｆ Ｌ＿Ｊ＋ ］Ｘ Ｖ ｉＥ Ｐｈｐ（订Ｉ一 一 Ｊ

ｘ，，从而又得到新的等候时间叫 ，如此反复迭代，

迭代公式为

ｗ 、 一Ｃ ＋Ｂｍ＋Ｉ ”一

¨ Ｌ ＿Ｊ＋ １ ，Ｙ ｍ，∈ｈｐ（ｆ）（一 』

其中ｑ≥０．

迭代直至砌 ”一叫 ，即等待时间不再增加时

停止，此时叫 一是１０＋， ，该式表明在 ，￡。＋训 ］

时间段内，该消息实例发送前（是一１）个报文用了长

为（是一１）１０的时间，被一个低优先级报文阻塞了长

为１０的时间，被高优先级消息实例阻碍了长为

的时间，最终在ｆ。＋ 时刻所有的高优先级消息实

例都已发送完成，可以开始发送户 了，因此砌 一

叫 ．

根据上述计算结果，不难得出在延迟抢先条件

下的消息ｍ 的计算公式为：

Ｒ —ｒ．｝ —ｗ＿．１ ＋ｐ—ｗ ＋ｐ．

其中，叫 ”一叫 ，“≥ｌ；

’＝＝＝Ｐ ×１０＋

Ｊ＋１］ ，

其中ｑ≥０，叫 一Ｐ ×１０．

５ 实例分析

本节将通过一个简单实例将上节中提出的基于

延迟抢先的消息最大响应时间算法与Ｂｕｒｎｓ～纠算法

进行对比．在以下的讨论中，我们将Ｂｕｒｎｓ－２］算法简

称为算法ｌ（注：由于Ｂｕｒｎｓ卫 算法是针对点对点线

路提出的，为使之适合于ＴＤＭＡ协议，这里对

Ｂｕｒｎｓ＿２ 算法略微做了一些修改），上节中提出的算

法简称为算法２．

假设在一个仅包含两个节点Ⅳ．和Ⅳ。的分布

式实时系统中，为节点Ⅳ．和Ⅳ 分配的时隙分别为

３０Ｏｔｉｓ和ｌ００／￣ｓ，因此Ｔ¨）ＭＡ＝４０Ｏｔｉｓ，１０设为ｌ００／￣ｓ．

其中Ⅳ．的消息集如表ｌ所示，各消息在表中按照

优先级从高到低的顺序排列．

表１ Ｎ。的消息集

利用算法ｌ和算法２分别对Ⅳ．消息集中的消

息进行最大响应时间分析，结果如表２所示：

表２分析结果对比 ｓ

由表２可以看出，在对 。的分析中两种算法产

维普资讯

１４０４ 计算机研究与发展 ２００２焦

生了不同的结果．由手工计算检验可知，算法２得出 ３

的结果是正确的．

６ 小 结

本文针对有广泛应用前景的分布式实时系统提

出了一种基于延迟抢先的消息最大响应时间算法，解

决了现有消息最大响应时问算法中存在的问题，比原

有算法完整、精确，可适用于所有情况．对于采用其它

通信协议的分布式实时系统，该算法对其消息最大响

应时间分析也可起到很强的理论指导作用．

参 考 文 献

１ Ｋ Ｔｉｎｄｅｌ１．Ｈｏｌｉｓｔｉｃ ｓｃｈｅｄｕｌａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｈａｒｄ

ｒｅａｌ ｔｉｍｅ ｓｙｓｔｅｍｓ．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，

Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｙｏｒｋ，Ｔｅｃｈ Ｒｅｐ：ＹＣＳ ９３ １９７，１９９３

２ Ａ Ｂｕｒｎｓ，Ｍ Ｎｉｃｈｏｌｓｏｎ，Ｋ Ｔｉｎｄｅｌｌ，Ｎ Ｚｈａｎｇ．Ａｌｌｏｃａｔｉｎｇ ａｎｄ

ｓｃｈｅｄｕｌｉｎｇ ｈａｒｄ ｒｅａｌ——ｔｉｍｅ ｔａｓｋｓ ｏｎ ａ ｐｏｉｎｔ—ｔｏ—ｐｏｉｎｔ ｄｉｓｔｒｉｂｕｔｅｄ

ｓｙｓｔｅｍ．Ｉｎ：Ｐｒｏｃ ｏｆ ｔｈｅ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ

Ｄｉｓｔｒｉｂｕｔｅｄ Ｒｅａｌ—Ｔｉｍｅ Ｓｙｓｔｅｍｓ．Ｃａｌｉｆｏｒｎｉａ：ＩＥＥＥ Ｐｒｅｓｓ，

１ ９９３．１】～２０

５

６

Ｋ Ｔｉｎｄｅｌ１． Ａｎａｌｙｓｉｓ ｏｆ ｈａｒｄ ｒｅａｌ—ｔｌｎｌｅ ＣＯＵｌｎｌＵｎｌｃａｔｌＯｒｌＳ．

１）ｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｙｏｒｋ． ｌ＇ｃｃｈ

Ｒｅｐ：ＹＣＳ一９４ ２２２，ｌ９９４

Ｊ Ｂ ｌａｉｎ．Ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｔｉｍｉｎｇ ａｎａｌｙｓｉｓ ｆｏｒ ｓａｆｅ ｃｒｉｔｉｃａｌ ｒｅａｌ

ｔｉｍｅ ｓｙｓｔｅｍｓ［Ｐｈ Ｉ）ｄｉｓｓｅｒｔａｔｉｏｎ］．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ

Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｙｏｒｋ，Ｕｎｉｔｅｄ ｋｉｎｇｄｏｍ，１９９８

Ｈｅｎｒｉｋ １．ｏｎｎ． Ｓｙｎｃｈｒ０ｎｉｚａｔｉ０ｎ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｒｅｓｕｌｔｓ ｉｎ

ｓａｆｅｔｙ ｃｒｉｔｉｃａｌ ｒｅａｌ—ｔｉｍｅ ｓｙｓｔｅｍｓ［Ｐｈ Ｄ ｄｉｓｓｅｒｔａｔｉｏｎ］．Ｃｈａｌｍｃｒｓ

Ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｌ＇ｅｃｈｎｏｌｏｇｙ，Ｓｗｅｄｅｎ．１ ９９９

Ｐａｕｌ Ｐｏｐ．Ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｓｙｎｔｈｅｓｉｓ ｆｏｒ

ｄｉｓｔｒｉｂｕｔｅｄ ｒｅａｌ—ｔｉｍｅ ｓｙｓｔｅｍ［Ｐｈ Ｄ ｄｉｓｓｅｒｔａｔｉｏｎ］．１ｎｓｔｉｔｕｔｃ ｏｆ

Ｔｅｃｈｎｏｌｏｇｙ，Ｉ ｉｎｋｏｐｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｗｅｄｅｎ，２００Ｏ

窦 强 男，１９７３年生，博士研究生

主要研究方向为实时系统．

周兴铭 男，１９３８年生，中国科学院

院士，教授，博士生导师，主要研究方向为

高性能计算机体系结构、移动计算、数据

库、实时系统等．

Ｉｌ口Ｉ

维普资讯