周興銘

第３９卷第１０期 計算機研究與發展 Ｖｏ１．３９，Ｎ。．１０

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

一種基于延遲搶先的消息最大

響應時間算法

竇 強 周興銘

（國防科學技術大學計算機學院 長沙４１００７３）

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

摘 要 分布式實時系統是實時系統的一個重要研究方向，有著廣泛的應用背景．消息最大響應時間的定量分析

是該研究方向中的一個關鍵問題．在深入分析國內外相關研究的基礎上，針對采用ＴＤＭＡ協議的分布實時系統提

出了一種基于延遲搶先的消息最大響應時間算法，解決了現有消息最大響應時間算法中存在的正確性問題，對消

息的最大響應時間做出了完整、精確的分析．

關鍵詞 實時系統，分布式，可調度性分析，消息，最大響應時間，ＴＤＭＡ協議

中圖法分類號ＴＰ３１ ６．２

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

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

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

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

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

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

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

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

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

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

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

１ 引 言

分布式實時系統與單機實時系統相比在性能價

格比、系統可擴充性和容錯能力等許多方面都具有

一定優勢，目前許多關鍵性的控制領域，如航空航天

器與機動車輛的駕駛控制、工業的生產控制等，都已

經或正準備采用分布式實時系統，以降低造價、減輕

重量、提高系統的可靠性和快速反應能力．由于這些

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

關鍵領域對系統的實時特性、容錯能力等都有很高

的要求，并且一旦這些需求得不到滿足，會造成巨大

的且無法挽回的生命、財產損失以及環境危害．因此

需要有一種非常嚴謹的分析手段，即系統的可調度

性分析，來分析和驗證分布式實時系統在最大負載

下或部件失效的情況下是否仍能滿足應用的實時性

要求，這對保障系統的安全運行意義極為重大．例如

在Ｂｏｅｉｎｇ ７７７飛行控制軟件的開發過程中，其中超

過５Ｏ 的開發時間和精力都被投入到了系統的可

ｌＩ＿蓮瞧｜＿

維普資訊

１４００ 計算機研究與發展

調度性分析和軟件測試中．

分布式實時系統的一個重要特點是任務間的消

息通信，要分析系統整體的實時特性必須要考慮到

消息通信的時間開銷．因此，消息的最大響應時間分

析，即消息從源節點完整發送到目的節點所需最大

時間的定量分析，一直都是系統可調度性分析中的

一個重要研究課題．許多其它問題的解決如任務的

劃分方法、任務和消息的調度策略等都是以消息的

最大響應時間分析為基礎的．在這方面很多學者已

經進行了一些研究，如Ｔｉｎｄｅｌｌ［１］就針對ＴＤＭＡ協

議提出了一種消息的最大響應時間分析算法，但由

于消息模型比較簡單，未考慮消息的延遲搶先特性，

因此分析不夠精確．Ｂｕｒｎｓ等人［２ 提出了延遲搶先

的概念并提出了相應的基于延遲搶先的消息最大響

應時間分析算法，但該算法是針對點對點線路提出

的，不適用于分布式實時系統，而且更重要的是算法

的正確性存在問題，在某些情況下，該算法會低估消

息通信的時間開銷，從而可能會導致系統的可調度

性分析做出錯誤的結論．Ｔｉｎｄｅｌｌ Ｅ。 在Ｂｕｒｎｓ Ｅ 等人

工作的基礎上分別對Ｔｏｋｅｎ Ｒｉｎｇ和Ｐｒｉｏｒｉｔｙ Ｂｕｓ

兩種網絡協議進行了消息最大響應時間分析，

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

的基礎上進行了一些調度算法等方面的研究，但它

們均未解決上述Ｂｕｒｎｓ［２ 算法存在的正確性問題．

本文針對ＴＤＭＡ協議提出了一種基于延遲搶先的

消息最大響應時間算法，解決了上述問題，對采用

ＴＤＭＡ協議的分布式實時系統中的消息最大響應

時間做出了完整、精確的分析．

本文共分６節，第２節建立了一個分布式實時

系統的計算模型，并簡單介紹了ＴＤＭＡ協議；第３

節給出了一些基本概念的定義；第４節針對ＴＤＭＡ

協議提出了一種基于延遲搶先的消息最大響應時間

算法；第５節通過一個簡單實例將本文算法與

Ｂｕｒｎｓ＿２ 算法進行了對比；最后第６節對全文做出了

簡短的總結．

２ 系統模型

分布式實時系統一般由若干個節點和連接各節

點的互連網絡組成，文獻［１～３］中提出的節點構成

如圖１所示．系統中每個節點都由一個處理機和一

個網絡接口部件組成，處理機與網絡接口部件之間

共享一個報文發送隊列和一個報文接收隊列．

本文假定系統中各節點的任務集都是周期任務

集，且任務不會在節點之間遷移．各節點的消息集也

是一個周期消息集，它包括了由該節點上任務發送

給其它節點上任務的各種消息．消息的產生模型為

對于每種消息，消息的源任務每隔固定任務周期產

生一條該消息的消息實例；消息實例的長度對于每

種消息來說是固定的；在發送前，消息實例被分割為

若干報文，報文的長度是固定的；在下一個消息周期

開始前，該消息實例一定要發送完成．本文還假定消

息的發送采用固定優先級搶先式調度算法，高優先

級消息的報文優先得到發送．在本文中，我們并不關

心消息的優先級分配策略，但假定同一節點內各消

息的優先級是互不相同的．

圖１節點構成

ＴＤＭＡ協議是一種具有很強確定性的網絡通

信協議，具有較好的容錯性和時間響應特性，因此許

多分布實時系統中采用的通信協議都是在ＴＤＭＡ

協議的基礎上演變而來的，如ＴＴＰ／Ｃ，ＦｌｅｘＲａｙ以

及Ｂｙｔｅｆｌｉｇｈｔ等．ＴＤＭＡ協議中，每個節點都被分

配了固定長度的發送時隙，節點只能在自己的時隙

中發送數據．如果不考慮時鐘同步漂移的問題，各節

點的發送時隙在時間上是連續的．從第１個節點發

送時隙的開始時刻到最后一個節點發送時隙的結束

時刻之間的時間間隔稱為一個ＴＤＭＡ周期，當一

個ＴＤＭＡ周期結束后，下一個ＴＤＭＡ周期立刻開

始，如此循環反復．本文假定各節點發送時隙的長度

都是報文發送時間的整數倍．

３基本概念定義

定義１．消息產生的周期稱為消息周期．

根據第２節假設，消息周期是源任務周期的整

數倍．

定義２．消息的發送時間是指將消息的一個消

息實例發送到網絡上所需要的時間．

維普資訊

１０期 竇 強等：一種基于延遲搶先的消息最大響應時間算法

每種消息的消息實例都可分割為固定數量的報

文，因此每種消息的發送時間是固定的．

定義３．在一個消息周期中，源任務將消息實例

放入發送隊列的時刻稱為消息實例的釋放時刻，釋

放時刻與該消息周期起始時刻之間的差值稱為該消

息實例的釋放偏移．由于源任務運行條件的復雜性，

各消息實例的釋放偏移可能有所不同，其最小值為

０，最大值稱為該消息的釋放抖動．

定義４．從一個消息實例的釋放時刻開始，到該

實例中的第ｋ個報文發送完成時為止的這段時間稱

為該消息實例第ｋ報文的響應時間，所有消息實例

第ｋ報文的響應時間的最大值稱為該消息第ｋ報文

的最大響應時間．

定義５．從一個消息實例的釋放時刻開始，到該

實例發送完成時為止的這段時間稱為該消息實例的

響應時間，所有消息實例的響應時間的最大值稱為

該消息的最大響應時間．

定義６．從一個消息實例的釋放時刻開始，到該

實例中的第ｋ個報文開始發送時為止的這段時問稱

為該消息實例第ｋ報文的等候時間，所有消息實例

第ｋ報文的等候時間的最大值稱為該消息第ｋ報文

的最大等候時間．

定義７．消息的關鍵情形：消息的關鍵情形是指

在該種情形下該消息消息實例的響應時間將達到最

大值．

定義８．在網絡通信中，不論報文的優先級如

何，一個報文一旦開始發送就不能被任何其它報文

中斷，這種特性稱為報文的延遲搶先特性．

在消息的最大響應時間分析中，如果不考慮報

文的延遲搶先特性，即報文在發送過程中可被在其

問到達的任何高優先級報文搶先，則報文的響應時

間會因此增大，從而使分析結果不精確，高于實際的

消息最大響應時間，最終導致過于悲觀保守的系統

設計，浪費系統資源，增加系統造價．

４ 基于延遲搶先的ＴＤＭＡ協議的消

息最大響應時間算法

假定系統中某節點ＪＶ發送給其它節點的消息

集為｛ ．， ：，…， ｝，其中ｃ為消息種類數，消息

可用一個三元組（Ｌ廠 ，Ｘ ，Ｔ ）來表示，其中Ｌ廠 為消息

的釋放抖動；Ｘ 為消息 的發送時間，Ｘ 一Ｐ ×

Ｐ，Ｐ 指 ，的消息實例分割成的報文數量，Ｐ為報文

的發送時間；Ｔ 為 的消息周期．消息 的最大

響應時間記為Ｒ ，消息 第ｋ報文的最大響應時間

和最大等候時間分別記為 和 （１≤正≤Ｐ ），顯

然有Ｒ —ｒ』＇ ，此外根據報文的延遲搶先特性，不難

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

假定節點ＪＶ的發送時隙長度為Ｓ ，ＴＤＭＡ周

期記為７１ 。 ，根據ＴＤＭＡ協議，在每個ＴＤＭＡ周

期中，其它節點都要占用其中（７’ ｏ —Ｓ ）的時問，

不難看出，對于節點ＪＶ，其它節點對網絡資源的這

種周期性占用非常類似于一個周期性消息對網絡資

源的占用．因此，為便于分析節點ＪＶ的消息最大響

應時間，我們有如下定義．

定義９．對于節點ＪＶ，其它節點對網絡資源的

占用可看成是一個周期性消息對網絡資源提出的周

期性請求，這個周期性消息就被稱為是節點 的虛

擬消息．

我們將節點ＪＶ的虛擬消息記為 ，根據消

息模型，這個消息可用三元組（０，（７１ ｒ【 一Ｓ， ），

７ ｏ ）來表示．由于各節點時隙是固定的，需要嚴格

遵守，因此虛擬消息的優先級被設為最高．本文以下

的討論都是基于消息集｛ ．， 。，…，ｍ ， ， ｝進行

的，這個消息集我們記為 ，并將 中優先級高于

，的消息集合記為 聲（ ）．

定理１．消息 的關鍵情形出現在同時滿足以

下條件的情況下：

① （ ）中消息所產生的消息實例同ｍ 的消

息實例在同一時刻釋放；

②在消息實例同時釋放前，坳（ ）的消息實例

的釋放偏移分別為各自的釋放抖動；在這之后，所有

（ ）中的消息產生的后續消息實例的釋放偏移均

為０；

③一個低優先級報文在 的消息實例釋放時

剛好開始發送．

證明．圖２描繪了當這些條件滿足時的情況，

其中ｔ。表示共同的釋放時刻．

（１）對于Ｖ ∈ｈｐ（ ），假設 ，消息實例的釋放

時刻與 消息實例的釋放時刻不相等．當 消息

實例釋放時， ，有兩種可能，一種可能是 ，正在發

送一個消息實例，第２種可能是 ，已經發送完成上

一個消息實例，正在等待下一個實例的釋放．對于第

１種可能如圖３所示， 消息實例的釋放時刻為ｔ ，

消息實例的釋放時刻為ｔ：，由于在時間段Ｉｔ．，ｔ ］

內 ，要發送報文，因此即使將 消息實例的釋放

時刻提前為Ｉｔ．，ｔ：］中的任意值，該實例的發送完成

時間仍然保持不變，從而使 消息實例的響應時間

維普資訊

１４Ｏ２ 計算機研究與發展

增大．因此當 消息實例的釋放時刻提前至ｔ 時，

消息實例的響應時間取得最大值，此時 消息

實例的釋放時刻與 ，消息實例的釋放時刻相等．對

于第２種可能如圖４所示， ，消息實例的釋放時刻

為ｔ ， 消息實例的釋放時刻為ｆ ．顯然，如果將 ，

消息實例的釋放時刻提前， 的后續消息實例可能

會在 消息實例發送完成前被釋放，而且搶先于

消息實例之前得到發送，從而使 ，消息實例的

響應時間增大．因此當 ，消息實例的釋放時刻提前

到ｔ 時， 消息實例的響應時間取得最大值，此時

鞏消息實例的釋放時刻與 ，？肖息實例的釋放時刻

相等．

圖２消息 ，的關鍵情形

圖３第１種可能情況

ｌ

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

，

，

圖４第２種可能情況

（２）對于Ｖｍ ∈ｈｐ（ ），假定７．Ｕ 的一個消息實例

與 的一個消息實例在ｔ 時刻同時釋放，且該 ，

實例的釋放偏移為 （０≤ 矗≤Ｊ ）．通過計算可知，

ｍ，后續實例的到達時刻為ｔ ｊｉｔ＋丁 ，…，ｔｌ ｊｉｔ＋

Ｔ，，（ ＞０）．如圖５所示．顯然． 赴越大，且后續實例

的釋放偏移越小，后續實例的釋放時刻就越接近ｆ 。

ｍ 消息實例的響應時間也會隨之增大或保持不變

（因為可能會有更多的 ，的后續消息實例搶先于

消息實例之前得到發送）．因此，當ｆｉｔ—Ｊ，且 ，

后續實例的釋放偏移都為０時， ？肖息實例的響應

時間取得最大值．

圖５釋放抖動對 響應時間的影響

（３）在網絡通信中，由于報文具有延遲搶先特

性，因此消息 ，的一個消息實例可能會因為等待一

個低優先級報文發送完成而被阻塞。從而增大消息

實例的響應時間．假設一個低優先級報文的開始發

送時刻為ｔ ， 的一個消息實例的釋放時刻為ｔ！．如

果ｔ ＞ｆ。，根據消息調度策略，該報文的發送對 消

息實例的響應時間沒有影響．如果ｔ ≤ｆ：，該情況與

（１）中的第１種可能比較類似，因此當ｔ 一ｔ 時。

消息實例的響應時間取得最大值． 證畢．

定理２．在消息 的關鍵情形下，對Ｖｋ（１≤志

≤Ｐ ），鞏消息實例的第ｋ報文響應時問以及第ｋ

報文等候時間均達到最大值．

證明．證明過程與定理１的證明類似，不再贅

述．

根據定理２，若消息 在ｔ。時刻釋放的一個消

息實例滿足定理１所述條件，則對Ｖ志（１≤志≤Ｐ ），

該消息實例的第ｋ報文響應時間的值就是ｒｆ１ ，該消

息實例的第ｋ報文等候時間的值就是硼 ．該消息

實例的第ｋ個報文記為 ．

該消息實例的第ｋ報文等候時間即硼 是由３

部分構成的：第１部分是該實例發送前（志一１）個報

文本身所需的發送時間，記為Ｃ ，顯然Ｃ ：（矗

１） ；第２部分是該實例在前（志一１）個報文的發送過

程中因為等待一個低優先級報文發送完成而被阻塞

的時間，稱為阻塞時間，記為ＢⅢ，根據定理１中條

件③，顯然有Ｂ —ｌ０；第３部分是該消息實例在第ｋ

個報文開始發送前因高優先級消息實例的搶先發送

維普資訊

１０期 竇 強等：一種基于延遲搶先的消息最大響應時問算法

而被阻礙的時間，稱為阻礙時間，記為， ．

直接計算Ｉｉ．ｋ較為困難，因此我們采用迭代的方

式來計算叫Ⅲ和， ，我們將第ｑ次的迭代結果分別

記為ｚｕ…（ｑ）和， ，其中ｑ≥０．首先給定初值， 一０，

－

－ＣⅢ＋Ｂ ＋， ＝ｋｐ，這是不考慮阻礙時間時

的第ｋ報文等候時間．對Ｖ ∈ｈｐ（ ），根據定理ｌ中

條件①和條件②，ｍ，的一個消息實例也在ｔ。時刻釋

放，如圖６所示：

Ｉ

Ｉ、

ｍ｜ Ｊｉ ｌ Ｉ … ｌ ｌ

ｗ

： ｍ

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

，

，

圖６ ，消息實例對 ，消息實例的阻礙時Ｊ司

在時間段［ｆ。，ｔ。＋叫 ］內，消息 ，共釋放了

廠 Ｔ ］個消息實例，這些消息實例均要搶先

于戶 之前發送，此外，如果叫 ＋．，，一ｉＦ，，（＿廠＞０），

則消息 還會在ｔ。＋叫 時刻釋放一個消息實例，

因為該消息實例優先級比較高并且此時戶 正準備開

始發送，所以該實例也會優先于Ｐ 得到發送

（Ｂｕｒｎｓ＿２ 算法正是因為未考慮在ｔ。＋叫 時刻釋放的

高優先級消息實例對戶 的搶先，所以低估了消息的

最大響應時間），因此消息 ，在時間段［ｆ。，ｔ。＋叫 ］

內對 ，的阻礙時間應為ｆ Ｌ ＿Ｊ＋ １×ｘ ，總

阻礙時間 Ｉ

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

ｘ ，從而得到新的等候時間叫 —ＣⅢ＋ＢⅢ＋ ．

由于 ＞ＺＵ…（０），即等候時間增大，從而可能會使阻

礙時間進一步增大，通過與上面類似的分析可知，在

時間段 。，ｔ。＋叫 ］中，高優先級消息實例對ｍ。的

妨礙時間 ∑ ｆ Ｌ＿Ｊ＋ ］Ｘ Ｖ ｉＥ Ｐｈｐ（訂Ｉ一 一 Ｊ

ｘ，，從而又得到新的等候時間叫 ，如此反復迭代，

迭代公式為

ｗ 、 一Ｃ ＋Ｂｍ＋Ｉ ”一

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

其中ｑ≥０．

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

停止，此時叫 一是１０＋， ，該式表明在 ，￡。＋訓 ］

時間段內，該消息實例發送前（是一１）個報文用了長

為（是一１）１０的時間，被一個低優先級報文阻塞了長

為１０的時間，被高優先級消息實例阻礙了長為

的時間，最終在ｆ。＋ 時刻所有的高優先級消息實

例都已發送完成，可以開始發送戶 了，因此砌 一

叫 ．

根據上述計算結果，不難得出在延遲搶先條件

下的消息ｍ 的計算公式為：

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

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

’＝＝＝Ｐ ×１０＋

Ｊ＋１］ ，

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

５ 實例分析

本節將通過一個簡單實例將上節中提出的基于

延遲搶先的消息最大響應時間算法與Ｂｕｒｎｓ～糾算法

進行對比．在以下的討論中，我們將Ｂｕｒｎｓ－２］算法簡

稱為算法ｌ（注：由于Ｂｕｒｎｓ衛 算法是針對點對點線

路提出的，為使之適合于ＴＤＭＡ協議，這里對

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

法簡稱為算法２．

假設在一個僅包含兩個節點Ⅳ．和Ⅳ。的分布

式實時系統中，為節點Ⅳ．和Ⅳ 分配的時隙分別為

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

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

優先級從高到低的順序排列．

表１ Ｎ。的消息集

利用算法ｌ和算法２分別對Ⅳ．消息集中的消

息進行最大響應時間分析，結果如表２所示：

表２分析結果對比 ｓ

由表２可以看出，在對 。的分析中兩種算法產

維普資訊

１４０４ 計算機研究與發展 ２００２焦

生了不同的結果．由手工計算檢驗可知，算法２得出 ３

的結果是正確的．

６ 小 結

本文針對有廣泛應用前景的分布式實時系統提

出了一種基于延遲搶先的消息最大響應時間算法，解

決了現有消息最大響應時問算法中存在的問題，比原

有算法完整、精確，可適用于所有情況．對于采用其它

通信協議的分布式實時系統，該算法對其消息最大響

應時間分析也可起到很強的理論指導作用．

參 考 文 獻

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

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

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

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

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

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

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

１ ９９３．１】～２０

５

６

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

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

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

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

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

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

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

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

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

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

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

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

竇 強 男，１９７３年生，博士研究生

主要研究方向為實時系統．

周興銘 男，１９３８年生，中國科學院

院士，教授，博士生導師，主要研究方向為

高性能計算機體系結構、移動計算、數據

庫、實時系統等．

Ｉｌ口Ｉ

維普資訊