数理解析研究所講究録
1489 巻 2006 年 8-14

8時間オートマトンによる Value-Density

スケジューリングアルゴリズムの性能解析手法
金沢大学・自然科学研究科 坂倉賢昭 (Masaaki Sakakura)

山根智 ($\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}$Yamane.)Graduate School of Natural Science&Technology,
Kanazawa University

1Introduction

リングアルゴリズムも提案されている. そこで本研究では, wangらによって提案されたタスク$\mathrm{Y}\mathrm{i}$現在, リアルタイムシステムは高性能かつ高信頼付き時間オートマトンを価値関数によって拡張し,性を要求されるシステムに多く利用されているが,ソフトリアルタイムシステムに対するスケジこれらのシステムは複雑で開発や検証を行うのはリングアルゴリズムの性能をモデル解析する手法を提案する.
本文の下野は, 2 章で本研究の対象となるリアルタイムシステムの概要について説明し, 3 章で今回用いる解析モデルについて, 4 章でその解析方法について説明し, 簡単な例を用いて実際に解析を行う.

大変難しいことである. デッドライン (時間制約)を守ることが絶対とされるハードリアルタイムシ
ステムにおいては, 近年, 一般的な解析方法として時間オートマトンが用いられている. 時間オー

トマトンを用いてタスクの到着パターンを表すことにより, 周期的なタスクだけでなく非周期的な$\mathrm{I}^{-}$タスクも扱うことができるようになり, これによってタスクの周期性にかかわらず時間オートマトンの到達可能性解析を行うことによってシステムの性質をモデル解析できるようになった. 例として,

2

ソフトリアルタイムシステム
本章では本研究の対象となるソフトリアルタイ

Wang Yi らによってタスク付き時間オートマトンムシステムについて説明する.

によるハードリアルタイムシステムのスケジュ $-$2.1

ラビリティ解析手法が提案されている $[1][2]$ . 11, かし現在では, デッドラインを守ることが最善ではあるが, 多少のデッドラインミスを許容する, ソ
フトリアルタイムシステムも増加しており, 重要視されてきている. 典型的な例としては, 画像や音声通信などのマルチメディアデータ処理, または分散データベースなどがある. ソフトリアルタ

イムシステムの解析分野では主に 2 種類の方法が提案されている.

1 つは,ソフトリアルタイムシ

ステムのタスクの時間的性質を関数で現す方法であり, その価値関数 (value function) を用いてス
ケジ ーリングアルゴリズムの性能を統計的に解析している. [4] もう 1 つの方法はタスクがデッドリアルタイムシステム

リアルタイムシステムとはシステムの品質が,論理的正確さと同様に, 結果を出す時間に依存しているシステムである. よって,リアルタイムのモデルはタスクがサービスを完了する完了時刻が厳格であるかどうかによって大きく次の 2 つに分けることができる. (図 1)

ソフトリアルタイムシステム処理の完了が時間要求を満たさなくても結果は有意義であるが,時間とともに価値が下がる.
ハードリアルタイムシステム処理の完了が時聞$\mathrm{n}$ラインをどれだけの確率で満たせるかを統計的に解析する方法が提案されている. また価値関数を使った方法ではその価値関数を用いたスケジ $=-$

要求を満たさなければシステム全体に致命的な影響を与える.

9Fig. 1: リアルタイムシステムの種類

2.2

価値関数の導入

リアルタイムシステムとその他のシステムの最も大きな違いはプロセスの処理の価値が時間によって変化するということである.

Fig. 2: 価値関数の例

リアルタイムシス

テムでは, システムの応答時間はシステムの正確さのなかで最も重要な部分である. よって, それを表現するためにタスクごとに価値関数 (value3

拡張時間オートマトンfunction) を導入する. 価値関数というのはタス

Wang Yi の手法ではタスクの到着パターンを表クの実行価値の時間的変化を関数で表したものですのに拡張された時間オートマトンが用いられてある. 価値関数の例をここで挙げておくいる [2]. 今回はそのタスク付き時間オートマトン$\bullet$.
.

$\bullet$(図 2).

Vl: カーナビの位置更新などのタスク.

V2: センサーの入力などのタスク.

V3: ソフトリアルタイムのように価値が落ちていき負になるタスク.

V4

2.3

: 衛星の発射などのタスク.

$=$ーリングアルゴリズ

ムを説明する. 価値関数を用いたスケジ$:\mathrm{x}$ーリン

グアルゴリズムに以下の 2 つのものが提案されている.

して用いる.

3.1

syntax

まずタスクについて定義する.

価値関数を用いたスケジューリング
アルゴリズム

価値関数を用いたスケジを価値関数を用いて拡張したものを解析モデルと$[4][5]$

HVF (Highest Vlue First)

イムシステムを扱うためタスクの要素として価値関数を持つ. 価値関数はタスクがリリースされてからの時間からタスクの価値を計算する関数である.

Deflnition 3.1.1
タスク疏

果$d_{i}$$V_{:}(t_{1})$高いタスクから実行していく。

は (果,$d_{1},$$V_{\dot{*}}(t:)$) の要素からなる

タスク疏の残り計算時間
タスク$P_{1}$の相対デッドライン

タスク$P_{1}$の現在の価値 (ちはタスク昂がリリースされてから経過した時間,HVDF(Highest Value Density First)$\ovalbox{\tt\small REJECT}$

は$t_{1}$を受けてちの時点の$P_{*}$の価値を返す価値関数)

タスクの婦 ue density (価値/計算時間) をつタスクから実行していく.

$\in \mathrm{P}$(タスク)とする.

タスクの処理終了後の価値が待ち行列で最も求め, 待ち行列で最も高い value density をもソフトリアルタ

また,タスクの情報として以下のものが与えられているとする.

10

3.2

$C_{1}$

タスク鳥の計算時間$D_{:}$

タスク昂の相対デッドライン(リリースしてからデッドラインまでの時間)

semantics

次に拡張時間オートマトンの semantics について説明していく. まず task queue の変化を計算するために次の関数を定義する.

から始まってだ
つまりタスクの要素果はんだん減っていき, 果 $=0$ になったら処理が終了

Deflnition S.2.1

したことを表す. 口$Sch(q)$$c_{i}=C_{1}$

次に拡張時間オートマトンの定義について述べ
action と呼ばれるアルる. 正式に定義するため,ファベットの有限集合 Act, clo 磁と呼ばれる実数値の変数の有限集合 $C$ を定義する. $a,b,\cdots$ は Actの要素であり, xl,x2, は $C$ の要素である. $B(C)$は g などで表され, 形式的には clodc の制約式の連言で示す.

$B(C)$ の要素は clock constraints と呼ばれる. また,$m,n$ は自然数である.

(関数 Sch, 関数 Run)task queue のあるスケジューリングア
ルゴリズムでソーティングする関数

Run $(q, t)$

実数 が与えられたときに, 時間 後$t$$t$のtask queue を返す関数

口関数 Run $(q, t)$ は次のような計算を行う.

全てのタスクを実行した場合$(t\geq c_{P^{1}}+c_{P}’+\cdots+c_{P^{n}})$Deflnition 3.1.2 (拡張時間オートマトン)
action の集合 Act とクロックの集合 , タスクのRun $(q, t)=$$[P^{1}(0, d_{P^{1}}-c_{P^{1}}, V_{P^{1}}(t_{P^{1}}+c_{P^{1}}))$

$C$

集合

..
.

上のオートマトンは $\langle N, l_{0}, E, I, M\rangle$ の組$\mathrm{P}$である.
$N$$P^{2}(0, d_{P^{2-}}(c_{P^{1}}+c_{P^{2}}),$ $V_{P^{2}}(t_{P},+c_{P^{1}}.+c_{P^{2}}))$.
$c_{P^{1}}+c_{P^{\mathrm{a}+\cdots+\mathrm{C}_{P^{\mathfrak{n}}}}}))]$

は最初のロケーション$E\subseteq N\cross B(C)\mathrm{x}$Act$\mathrm{x}2^{C}\mathrm{x}N$はエッジのタスク集合: $N\mapsto B(C)$ はロケーションを dockconstmint に割り当てる関数$M$
はロケーションをタスクに割:$N‘arrow \mathrm{P}$$\bullet$り当てる部分関数($l,$$g,$ $a,$ $r,$ $l’\rangle\in E$

まで実行した場合のとき.

$l\underline{g,a,r_{\iota}}$$l’$と書$\text{く}$$\nu$$[P^{1}(0, d_{P^{1}}-c_{P^{1}}, V_{P^{1}}(t_{P^{1}}+c_{P^{1}}))$:.

で示す. 口拡張時間オートマトンの状態は$(l, \sigma, q)$

...

. また,

$C$

assignment の集合を

Run $(q, t)=$,$P^{1}(0, d_{P}:-(c_{P^{1}}+\cdots+c_{P}:),$ $V_{P^{i}}(t_{P^{\dot{l}}}+c_{P^{\iota+}}$から非負の実数への関数 (clock assignment と呼ばれる) によって clock の値を示し, dock

通常,$P^{:}$$(c_{P^{1}}+\cdots+\mathrm{c}_{P^{\ell}}\leq t\leq c_{P^{1}}+\cdots+c_{P}:+c_{P}):+1$$I$$\bullet$,$P^{n}(0,d_{P^{n-}}(c_{P^{1}}+Cp\mathrm{r}+\cdots+c_{P^{\mathrm{n}}}),$ $V_{P^{n}}(t_{P^{n}}+$はロケーションの有限集合$l\mathit{0}\in N$,で表す.

$+c_{P}:$)),$P^{1+1}(c_{P}:+1-(t-(c_{P^{1}}+ \cdot .
$t,$:.

$V_{P^{l+1}}(t_{P^{:+1}}+t))$.

+c_{P}:)),$ $d_{P}:+1-$,$p^{n}(c_{P^{n}}-(t-(c_{P^{1}}+\cdots+c_{P}:)),$ $d_{P^{n-}}$$t,$ $V_{P^{n}}(t_{P^{\mathfrak{n}}}+t))]$$l$$\sigma$$q$

現在操作しているノード

clo 磁の現在の値を示す clock$\mathrm{a}\epsilon \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$

現在の task queuetask queue は$\mathrm{O}\mathrm{S}$の待ち行列のようなものでここにタスクが加えられ, 先頭から実行され処理が終$f$

するとそのタスクは task queue から取り除かれる.

ここではタスクを$P^{1},$ $P^{2},$$\cdots,$$P^{n}$$\mathrm{t}\mathrm{a}8\mathrm{k}$で表し,過前のタスク戸はqueue の先頭から順に$1\leq i\leq n$とし, 時間経$P^{:}(c_{P}‘, d_{P^{\ell}}, V_{P^{i}}(t_{P}:))$で表している.

関数 Sc んは次のような処理を行う. 従来の (価値関数を用いない) スケジューリングアルゴリズ

11

ムでは次のような計算をしてタスク昂をタスク
耳より task queue の前に並べ替える.

HVDF. Highestpriority first(FPS):$P_{i}\in q,\forall P_{k}\in qPr(P_{i})\geq Pr(P_{k})$ここで $Pr(P)$ は $P$ の固定優先度を示す. Earliest deadline flrst(EDF):. First come flrst served(FCFS):$Sch(q)=|P_{\dot{\mathrm{t}}}..q,P_{k}V_{*1}+\cdot)/(tSc([P(c_{\mathrm{j}}-:_{n\geq 2\text{の場合次のタスク}^{}n=.01\text{の場合}\int \text{もしない_{残}}りのタスクを次ようにする}q\text{の先頭にてきて}P(c_{k}])V_{\mathrm{j}}())V_{k}())\mathrm{p}$$P_{j}\in q,\forall P_{k}\in qd:\leq d_{k}$$P_{i}\in q,\forall P_{k}\in qD:-d_{i}\geq D_{k}-d_{k}$. Least laxity flrst(LLF):$P_{1}\in q,\forall P_{k}\in qd:-c_{\mathrm{t}}\leq d_{k}-c_{k}$しかし,HVF や HVDF ような価値関数を用いた場合, 時間経過中にタスクの優先度の高低が入れ替わることがある. 後述するが, 従来のアルゴリズムを用いた解析と同じく, 今回もタスクが新しく加えられたときに関数 $Sch$ で task queue を並べ替えるようにしている. そこで, まず実行中のタスクが新しく加わったタスク以外にプリエンプトされる事のないように価値関数を単調減少の関数のみとする. 単調減少でないタスクの例とは

このように, 実行中のタスクの処理後の状態のタスクを考えて, タスクを再帰的に並べ替えていくことにより,み関数 $Sch$ で task queue を並べ替えればよいようにしている.

この関数を用いて拡張時間オートマトンの se-mantics 定義する.

Definition 3.2.2
初期状態 (価値が高くなるような価値関数である. このようの,なタスクは特別な例であるため今回は対象外とす

マトン

また, タスク実行中 (時間経過中) に次に優義する.

る.

.
.

先度の高いタスクが変わることを考えて HVF とHVDF の関数 Sch は次のようにする. n は task

queue

$q$の中のタスクの数とする.

HVF$n=0,1$ の場合 : 何もしない$n\geq 2$

を$q$の場合 : 次のタスク

りのタスクを次のようにする$\sigma$$P_{k}(c_{k}-c_{*}.,$ $d_{k}-\mathfrak{g}$$V_{k}(t_{k}+\mathrm{q}))$,$q))$$q\rangle$if(の遷移体系を次のように定$m,\sigma[rrightarrow$$larrow mg,a,\mathrm{r}$and$0|,$ $Sc\text{ん}(M(m)$$(l, \sigma, q)arrow t(l, \sigma+t, Run(q,t))$::(遅延遷移)$\sigma\models g$

if$(\sigma+t)\models I(l)$(離散遷移)

像する $C$ の assignment であり,$\sigma$,$arrow a$$\sigma,$のタスク付き時間オートを値 $\sigma(x)+d$ に写像する clock $ass|gnment$ である.
rC であり, [r\mapsto O]\mbox{\boldmath $\sigma$} は r の各 clock を値 O に写

Sc ん (q) $=\{$ $V_{l}(t:+c_{1})\geq V_{k}(t_{k}+c_{k})$$V_{j}(t_{j}+\mathrm{q}))$$l,$$\langle N, l_{0}, E, I, M\rangle$

d は非負の実数であり, \mbox{\boldmath $\sigma$}+d は変数 C の各 c80c 辷$P_{j}\in q,\forall P_{k}\in q$

ー院,($\iota_{0,\sigma_{0},q\mathrm{o})}$$\ovalbox{\tt\small REJECT}$の先頭にもってきて, 残$Sc\text{ん}([P_{j}(c_{j}-c_{\mathrm{t}},d_{j}$(semantic8)

スケジューリング関数 Sc んが与えられたとき2 の V4 のようなデッドライン付近で最も図 2.

タスクが新しく加えられたときのと –致する.

$\sigma\in g$$r$を除く $C$ 上のであるなら dock assignmentは制限 9 を満たすことになる. ここで $M(m)::q$に挿入した task queue. 口とは $M(m)$ を$q$,3.3

動作例$\ldots])$

図 3 の動作例の 1 つを示す.

12取り除かれる. また, 5 行目では HVDF の方針に従って value density の高い新しく来たタスクが task queue の先頭に並べ替えられている.

$P_{2}$

このように拡張時間オートマトンは動作していく.

4

解析手法
本章では性能解析の手法を説明していく.

4.1

解析方針

本解析では, あるスケジューリングアルゴリズ
ムに対し, 拡張時間オートマトンの初期状態から到達可能な全状態を調べ, それぞれのタスクにつFig. 3: 拡張時間オートマトンの例 1

いて処理を完了した時の価値の値の最大値と最小値を求め, それをシステムに対するスケジューリ$(m, [x=0, y=0]\mathrm{I})$ングアルゴリズムの評価とする. また, 本解析で.
.
.

$arrow(m, [x=3, y=3], \mathrm{I})3$

はシステムに対して次の仮定を設ける.

$arrow a(n, [x=0, y=3], [P_{2}(2,8, V_{2}(0))])$$arrow a(n,$ $[x=0, y=\mathit{0}],$ $[P_{2}(2,8, V_{2}(0))$,$P_{2}(2,8, V_{2}(O))])$$arrow 3(n, [x=3, y=3], [P_{2}(1,\bm{5}, V_{2}(3))])$$arrow a(n,$$[x=3, y=0],$ $[P_{2}(2,8, V_{2}(0))$ ,$P_{2}(1,5, V_{2}(3))])$$arrow 1(n,$システムは正常に動作し続ける (タスクが処理されずに task

queue に溜まっていき, 延々

本解析では拡張時間オートマトンの解析に時間$[x=4, y=1],$ $[P_{2}(1,7, V_{2}(1))$ ,automaton を用いる. zone automaton の succes-sor (ある状態から到達可能な状態) は次のように$[x=5, y=2],$ $[P_{2}(1,4, V_{2}(5))$ ,求めることができる. 詳しくは [3] に示されている.

$P_{1}(3,6, V_{1}(1))])$$arrow a(n,$ $[x=\mathit{0}, y=2],$ $[P_{2}(1,4, V_{2}(5))$

ンプト

オートマトンの解析で–般的に用いられる zone

$P_{2}(1,4, V_{2}(4)),$ $P_{1}(3,7, V_{1}(0))])$$arrow 1(m,$扱うスケジユーリングアルゴリズムはプリエ伸びていく可能性がない)$[x=4, y=1],$ $[P_{2}(1,7, V_{2}(1))$ ,$P_{2}(1,4, V_{2}(4))])$$arrow b(m,$価値関数は単調減少

Deflnition 4.1.1(Zone Successor)
時間オートマトン $A$ の clock zone , 遷移,$e$に$(\varphi, e)$は$\varphi$clock interpretation の集合 succ
clock zone である.
zone automaton$P_{1}(3,6, V_{1}(1)),$ $P_{1}(3,7, V_{1}(0))])$

おいて,$1\mathrm{h}zone(l, \varphi)k(s^{l}, succ(\varphi, e))$

まず最初にノード $m$ で 3 の遅延遷移が起こり時の間に遷移を加えると得ることができる. オート間が経過する. 時間が経過するとリリースされてマトン $A$ において,からの経過時間ちが加算されていく. 次にノードへの離散遷移が起こり task queue にタスクような遷移体系である.

$n$$\ovalbox{\tt\small REJECT}$が加えられ, 続いて同様に離散遷移が起こり taskqueue にタスク疏が加えられる. そして 3 の遅延遷移が起こると時間が経過するので task queue の先頭のタスクが実行され終了し, task queue から.

$\bullet$zone automatonZ(A) は次の$Z(A)$ の状態は $A$ の$A$zone である.の初期ロケーション 毎において, $(l,$ $[X:=$$0])$$s$は $Z(A)$ の初期ロケーションである.

13$\bullet$$A$の遷移 $e=(l, a, \psi, \lambda, l’)$ 毎と clock zone$\varphi$毎に, 遷移 $((l, \varphi),$ $a,$ $(s’, succ(\varphi, e)))$ がある.

&(l’, succ$(\varphi,$$e,$ $\rho|),$$Sch(M(l’)$:: Run $(q,$)$\text{の}$間に遷移を加えることで得ることができる.
拡張時間オー トマトン口$t_{\iota}))$

zoneの

$A$

automatonZ $(A)$ は次のような遷移体系で4.2

拡張時間オートマトンの successor

.

ある.

.

通常 zone automaton (7) successor はその zoneの入力シンボルに対して最大でも 1 っしか持たない. しかし, 拡張時間オートマトンを計算$(l, \varphi)$$Z(A)$ の状態は $A$ の$A$の初期ロケーショ$0],$ $q)$

するためには task queue の状態が時間とともに変化するため経過した時間の値が重要になってくる.

$\bullet$$A$zone である.

$\nearrow^{\backslash }l$毎において,$[X:=$は $Z(A)$ の初期ロケーションである.の遷移 $e=(l,a,\psi, \lambda, l’)$ と dock zone$\varphi$

そのときの時間経過 $i=0,1$ 毎に, 遷移そこで次のものを定義する. そして拡張時間オー
トマトンでは通常の clock に clock を追加し, 通$(l’,$ $succ(\varphi, e, \rho_{i})$$((l, \varphi, q),$ $a,$$t_{\iota}$

常の succoesor を$(l,$($Sch$ $M(l’)$の値で場合分けしたものを拡張時間オートマトンの successor とする.
$t_{\iota}$:: Run$(q,$.

,$t\iota)$)$)$がある.

拡張時間オートマトンの succesgor を計算する
ため新し$\langle$

clock と変数を定義する.

口

Deflnition 4.2.1

時間経過を測る clock

ロケーション

で経過した時間を表す clock$t_{\iota}$

$l$

4.3

解析アルゴリズム

拡張時間オートマトンの zone automatonn の初期状態を
口とする.

$n$

は現在 taek queueにあるタスクの数とする.
まず, 時間経過$t_{\mathrm{t}}$を, いくつタスクを実行したかについて successor を以下のように場合分けす1.

$t_{\mathrm{t}}$の値は zone で与えられ,$t_{l}$の状態を厳密に場合分けできない. しかし tl を定.

全て処理されるまで)

guard を満たし次第すぐに遷移する場合(lard がない場合即時遷移)

この長くとどまる場合の clock zone をく遷移する場合の clock zone を$\rho 0$$\rho_{1}$とし, 早とする.

について( $M(l)$::$(l,$Run $(q,$$e$$=$$\varphi$$t_{l})$)$)$

2. 求めた全ての successor に対して, そこから遷移可能な全てのいて successor ( $l’,$は次の二つに successor を場合分けする.

invariant を満たす限り長く状態に留まる場合(invariant がない場合 task queue のタスクが$\rho 0,$$\rho_{1}$を求める

めなければ task queue を計算できないので, 今回$\bullet$から遷移可能な全ての$succ(\varphi 0, e, \rho:),$ $Sc\text{ん}$の値は定数ではわからない. よってクロック t\sim だけでは task queue$(l_{0}, \varphi_{0}, q)$と時間経過

る. オートマトンの動作は zone で計算していくので$(l_{0}, \varphi_{0}, q)$Run$(q, t_{\mathrm{t}})))$$e$と時間経過$s\mathrm{u}cc(\varphi, e, \rho_{i}),$$\rho_{0},$$\rho_{1}$につ$Sch(M(l’)$ ::を求める

3. 2 を新しい状態が出力されなくなるまで行う
4. 各タスクに対して処理が完了したときの価値関数の値の最大値, 最小値を求める

4.4

ExamPle例として図 4 のシステムを考える. 初期状態$(m_{1}, x=0, \mathrm{I})$ から上記の successor で到達可能Deflnition 4.2.2 (Extend Zone Successor)
拡張時間オートマトン の clock zOne\mbox{\boldmath $\varphi$}, 遷移な状態を求めると図 5 のようになる. 矢印の先の, 時間経過

各タスクの価値の最大, 最小値は次の表のように

$A$

$e$

$\rho_{0},$$\rho_{1}$における,clock interpretationの集合 8uCC(\mbox{\boldmath $\varphi$}, e,\rho i) は cloCk zone である. 拡張時
間オートマトンの zone automaton は zone $(l, \varphi, q)$ないものは, 既に求めた状態と同じ状態になる.
なる.

145

結論
まとめとしてソフトリアルタイムシステムの性質を表現できるようにタスク付き時間オートマトンを拡張し, ソフトリアルタイムシステムに対するスケジ $=$ ーリングアルゴリズムの性能解析を行う方法を提案することができた. 今後の課題としては, 今回時間経過によって 2 つに場合分けしたが,クロックの数を増やすなどしてもっと厳密に場合分けすることによって価値の平均などを導出できるようにする. また, タスクが処理されずにtask queue に溜まっていく可能性がないとしたが,Fig. 4: 拡張時間オートマトンの例 2

その可能性ないかを検証できるようにすることがある. そして実際のシステム, 分散データベースなどを対象に解析を行えるようにしていきたい.

参考文献[1] C.Norstrom,A.Wall,Wang Yi, Timed Au-tomata as Task Models for Event-Driven Systems , RTCSA,pp.182-189,IEEE CS,1999.
[2] E.Fersman,Wang Yi, A Generic Approach to
Schedulability Analysis of Real Time Tasks,
In Nordic Journal of Computing, Volume 11,2006(to appear).
Alur , Timed Automata.,LNCS 1633, pp.
8-22, Springer-Verlag, 1999.
[4] D.Jensen,C.D.Locke,H.Tokuda , A TimeDriven Scheduling Model for Real-Time Operating Systems,pp. 112-122,IEEE Real-Time
Systems Symposium,1985.
[5] Y.Ronen,D.Mosse,M.E.Pollack ,Value
Density Algorithms for the Deliberation-[3]$\mathrm{R}$Problem. SIGART Bulletin,ACM,1996.
[6] Mark K.Gardner,Jane W.-S.Liu , Analyzing
Stochastic Fixed-Priority Real-Time Systems, LNCS 1579, pp.44-58, springerScheduling$7(2),\mathrm{p}\mathrm{p}.41- 49$

Fig. 5: 計算木

Verlag,1999.