「 マ ル チ メ デ ィ ア 通 信 と 分 散 処 理 ワ ー ク シ ョ ッ プ
J
平成5年1
1
月リアルタイム分散システムにおける
スケジュール性の考察
荒 井 兼 秀 * 斎 藤 正 史 料 *三菱電機(株)産業システム研究所 林三菱電機(株)情報システム研究所 リアルタイム分散システムにおける、システムのフォーJレトトレラント性とタスクの応答 性とについて考察した。分散システムにおいていくつかの計算機が処理を継続できなく なった場合、他の計算機がその処理を継続しなければならない。そのような場合に処理を 受 け 持 つ 計 算 機 が 過 負 荷 状 態 に な っ て も 、 優 先 度 の 低 い タ ス ク に 対 す る イ ベ ン ト を キ ュ ー イ ン グ す る こ と で 、 イ パ ン ト を 取 り の が き ず 、 再 び 定 常 状 態 に 戻 る ま で の 時 間 を 見 積 も れ ることを示した。 1 はじめに プラントシステムや電力システムなどにおけ る計算機システムでは、処理のリアルタイム性 とフォーJレトトレラント性とが重要な課題であ る。 このようなシステムでは、制御計測機器から 周期的に発生する外部要求としてのイベントに 対して、それを処理するタスクが存在し、イベ ント処理を行なう。この周期的に起動されるタ スクには、ある一定時間以内に、一般には、次 のイベント発生までに、その処理が終了するこ と要求される。すなわち、デッドラインを守る ことが必要であるロ このようなリアルタイム性が要求されるシス テムで動イ乍するタスクのスケジューリングアル ゴリズムが研究されているo また、計算機の小型化高性能化にともなって、 分散システムを構築し、システム全体としての 処理速度を向上させるとともに、フォーJレトト レラント性を向上させるようになってきた。 A SLudy or Schedula.biliLy for Distribu.ted Rea.l -time SystemsKanehide ARAI*.M笛 出hiSAITO
“
*Mitsubishi Electric Corpor.ation， Industrial and Elec -tronics Systems La.bora.tory
・
・
MitsubishiElectric Corpora.tion. Compuler a.nd In -forma.tion Systems La.bora.tory フォールトトレラント性を高めるために、パッ クアップ処理用の計算織をもうけて、1
台の計 算機が処理出来なくなった場合に備えるか、各 計算般の処理能力に余裕を持たせてあらかじめ 負荷を軽くしておき、ある計算般に障害が発生 した場合には、その計算機で行なっていた処理 を他の計算機に実行させるという方法がとられ ている。 一般に、1
台の計算機の異常にはあらかじめ 十分な対応をとることが多いが、概数の計算機 が処理を継続できなくなった場合にはタスクを 他の計算機にマイグレートした結果、他の計算 機の負荷が上昇し、優先度の低いタスクから、 処理が行なわれなくなるo これにより、イベン トの取りこぼしが生じ、システム全体として安 全とはいえなくなる。 本報告では、リアルタイムスケジューリング されたタスクが動イ乍するシステムにおいて、過 負荷状態になった計算機の低優先度タスクに対 するイベントをキューイングすることで、イベ ントの取りこぼしをなくし、その処理をある程 度の遅延を見越して行った場合の、遅延時間の 見積りを行なうことで、システムの安全性を向 上させる方式を提案し、その方式について考察 を行なった。計測・制御系 図1:プラントシステムの構成
2
大規模システムでのタスクスケジュー リング2
.
1
プラントシステムのモデル 大規模制御システムの構成のモデルとして、 図1のようなシステムを取りあげる。広域なネ ットワークに各種計測制御機器と計算機とが接 続されており、プラントシステムの計測機器か らの情報がネットワークを経由して計算機に送 られ、逆に計算機からの制御命令がネットワー クを経由して制御機器に送られる。 一般に、計測機器からのデータは周期的にネ ットワークに送り出され、不ツトワーク上にあ る計算機が、それをイベントとして取り上げ、 計算機上の対応するタスクが処理を行なう。し たがって、計算機上で処理を行なうタスクは周 期的に起動される。 これらの周期的に発生するイベントを処理す るタスクには、ある決まった時刻、または、次 のイベントが発生する時刻までにその処理を終 らせることが要求される。2
.
2
タスクスケジューリング リアルタイムコンピューテイングの理論のも ととなるのカf、リアJレタイムスケジューリング アルゴリズムである。リアルタイムコンピュー ティングでは、あるスケジューリング方式にも とづいたタスクセットの各タスクのデッドライ ンを守るとき、そのタスク集合はスケジューラ プルであるという白 リアルタイムスケジューリングのアルゴリズ ムとしてRMA(RateM
o
n
o
t
o
n
i
c
A
l
g
o
r
i
t
h
m
)
は、1
9
7
3
年にLiuらによって提唱された[
1
]
0
これは、独立な周期タスクが動作する場合に、 計算機の負荷率によって、システムのスケジュー ラピリティを確かめるものであり、はじめてシ ステムのスケジューラピリテイを定式イt
したも のである。 さらに、優先度継承プロトコル[
4
]
、優先度上 限プロトコJレ、スポラデイツクサーパ[
5
)
など様々 な拡張がなされている。R
.
MA
では、タスクの優先度はそのタスクの 周期のみにもとづき、周期の短いタスクほど高 い優先度をもっo 独立なn個の周期タスクのセットからなるシ ステムにおいて、タスク η の周期、実行時聞を それぞれれ，
C
i
とすると、 タスクセットの計算機利用率Uは n 可 であり、.
.u=
乞 宗
(
1
)
一一
属
。
斗
I
う
m
]
1
$1仰
←
ィ
l
T
"
{(k，
l似
k~
n
，
l=
1，
.
.
.
，
L
与
J
}
ムk をみたす時、このタスクセットはスケジュー ラプルである[
2
][
3
]
0
タスクのマイグレーション 計測・制御系 図2:負荷分散方式による障害対策 プラント制御システムにおけるタスクスケジューない。 リングで、この
RMA
をもちいることで、リア さらに、複数の計算機に障害が発生するなど Jレタイム性を保証するシステムを構築すること して、マイグレート先の計算機での処理が過負 ができるo 荷な状態(式(1)でUとりになるか、または、3
分散システムにおけるリアルタイム 計算機の小型化、高性能化にともない、リア ルタイムシステムの分散化なされている。 分散システムでのフォールトトレラント性を 高める方法として、パックアップシステムを用 いる場合と、負荷分散により故障した計算機の 処理を継続させる場合とが考えられる。これら の両者を用いる場合も考えられる。 負荷分散によりフォールトトレラント性を高 めているシステムの計算機に陣害が発生した場 合、その計算機で動作していたタスクは、その 他の、正常動作をしている計算機が行なう。す なわち、そのタスクは、正常勤作をしている計 算機にマイグレートするoその動作を図2に示 す。 その際、効率良くしかも、マイグレート先の 計算機でもリアルタイム性が守られるようなタ スクマイグレーションアルゴリズム研究がなさ れている[
6
]
0
マイグレート先の計算機でも、すべてのタス クのデッドラインを守るためには、あらかじめ、 計算機の負荷率に余裕をみておかなければなら 低い優先度のタスクがデッドラインを守れなく なると、そのタスクが処理すべきイベントは捨 てられてしまう。 しかし、イベントによってはイベントをキュー イングしておき、あとからその処理を実行すれ ば良いものが多い白 そのような場合、計算機が過負荷状態になっ たとき、全てのタスクが必ずそのデッドライン を守るという戯しい条件を緩める方式を考えた。 イベントをキューイングしておき、ある保証さ れた一定時間の後に、キューにあるイベント処 理を行なえれば、イベントを取りこぼすことな く、システムは動作を続けることができる。図 2のシステムでの計算機は図 3のような状態遷 移を行なうo このように制約を緩めることで、システムの フォーJレトトレラント性が向上し、システム設 計の自由度が向上する。 以降では、障害が発生した場合に、イベント をキューイングし、障害が回復してから処理の デッドラインが守れるようになるまでの時間の 上限値が計算可能であることを示す。?中ち
￨定常状態宇中事
￨負荷上昇状態や 『 事
1:過負荷状態マ空想
￨負荷上昇状態?中ヲ
￨定常状態 Eコ:計算機 時間 図3
:
システムの状態遷移 4 イベントのキューイングによる過負荷 処理4
.
1
イベントのキューイング 分散システムにある計算機の陣害により、障 害の起きた計算機上で動作していたタスクが他 の正常勤作している計算機にマイグレートして くる。これにより、正常動作している計算機は 過負荷状態になるとするo この計算機上では、マイグレートしてきたタ スクを含めたタスクの再スケジューリングが行 なわれる。その結果、優先度の高いタスクから 処理が行なわれ、優先度の低いタスクの処理が 行なわれなくなる。 そのような、低い優先度のタスクに対するイ ベントをキューに入れておき、低い優先度のタ スクが実行できる時間があれば、順次取りだし、 処理を行なう。 さらに一定時後には、障害の起こった計算機 が復旧し、マイグレートしてきたタスクは再び もとの計算機に戻る。過負荷状態にあった計算 畿は、回復処理状態になり、定常状態で行なっ ていたイベント処理とイベントキューに残って いるイベント処理とを行なう白キューに残った イベント処理が終ると、再びこの計算機は定常 状態にもどり、全てのタスクがデッドラインを 守れる状態になる(図的。 以上のイベント処理では、低優先度のタスク のデッドラインは守れていないが、要求された 一定時間の後に擁実に定常状態にもどることが できる。4
.
2
回復処理時間 図5に、過負荷状態となる計算機(計算機A) のタイムチャートを示す。時刻tlで、他の計算 機(計算機E
)
に障害が発生し、そこで動作して いたタスクの一部が計算機A にマイグレートす る。それにより、計算機A は過負荷状態になっ たとする。 時刻t2で、障害の発生した計算犠が処理を再 開し、計算機A にマイグレートしてきたタスク は、ふたたび計算機E
にマイグレートする。時 刻t)から時刻t2の問、計算機Aは過負荷状態 にあり、処理すべきイベントはキューに保存さ れる。 時刻t2から、もともと計算機Aで動作して いたタスクとキューに保存されているイベント とを処理し、キューにある全てのイベント処理 が終了する時刻を t3とするo 過負荷H寺問TFと回復処理時間TRをそれぞれ TF=
t
2
-t
l
TR=
t3ーら とする。 時刻1.}以降のイベント処理時間を、それぞれ のデッドライン以内という条件から、最大で TF+TR以内の時間で終了できればよいという 条件に、制約を緩めるo4
.
3
利用率と回復時間 過負荷状態の計算機で動作している全てのタ スクのうち、デッドラインを守って動作してい る高優先度のタスクセット(
T
H
)
に対して式(1) から求めた負荷率を UH、それ以外の、デッド ラインを守れない低優先度のタスクセット(
T
L
)
h y
ス
D J・
H -九 日 酔 制 い み J守
ス
Jぜ h タン
い
，
A1 仇 ぽ -フ 主 cr E
咽 ， 、ツ
理
デ
処
n u
悶 悶 V れ 九 1 ν ' h r -LV グ J h J J A 1 ﹃ ︿マタ
-L R E V Jベ
，
A1ユ
キ ザ ・ ' h l 勺 Jベ
，
A， 園田砂イベント
ーー+
定常状態
過負荷状態
回復処理状態
定常状態
時
間
図4
:
剖-算機の負荷状態遷移 定常状態 TF TR 定常状態 ー同. ー : 時間 t I l2 t3 t].タスクセットが入ってくる時刻 t2 .タスクセットが出て行く時刻 t3.タスクセットの影響が終る時刻 TF マイグレートタスクが存在する時間 TR .マイグレートタスクの影響が残る時間 図5
:
時間経過 に対して式(
1
)
から求めた負荷率を ULとする と、 である。したがって、時間TFの閥に、 TLのう ち未処理となる時間は ULTF一
(1-UH)TF UH+ULさ 1 である。過負荷時間の聞に、 TLが処理を実行す るのに必要とする時聞は ULTF であり、実際にTLが動作できる時間は、(
1
-
UH)TF となる。 定常状態における計算機負荷事をUとすると、 回復処理時間の聞に定常状態で行なうべき処理 に要する時間は(1-
U)TRであり、その残りの時間にTLに対する、キュー にあるイベント処理を行なうとすると
(
1
-
U
)
T
R
=
U
L
T
F
一
(
1
-U
H
)
T
F
となる。したがって、回復処理時間TR
はUL+UH-1
TR=h n T F ( 3 ) 1-U となる。 これにより、定常状態が壊れてから、次の定 常状態に戻るまでの時間T
s
はT
s
=
TF+TR
UL+UH-U
=
~ lJ I .，，~TF
(4) 1-U となるo これで、過負荷時間T
F
に対する復 旧時間T
s
が求められた。 この時間T
s
の許される範囲は、システムに よって異なり、その値に応じたタスク設計をし なければならない。 また、時刻tlとらとの聞に処理しきれない イベントの数N
qは、最大で N rn Nq=
乞
l
子
J
(
.
5
)
i=N-j+l 曲 I となる。 ここで、N
は時刻tlとらとの聞に動作して いる全タスク数、 jは、そのうち、デツドライ ンを守れていない低優先度のタスクの数、T
i
は 優先度の高い順にi番目のタスクの周期であるo ある計算機が時間T
F
の問、過負荷状態になっ た場合、最大、時間T
s
の問、優先度の低いj個 のタスクがデッドラインを守れない状態になる が、全てのイベントは処理され、その後は、再 び定常状態にもどる。 このとき、 Nqのキューを用意すれば、すべ てのイベントを取りこぼすことなく処理できる。 5 イ ベ ン ト キ ュ ー イ ン グ 方 式 適 用 例 5.1復旧時間の見積もり
いま、表1
のようなタスクセットがl
台の計 算機で動作しているとする。 表 1:定常状態のタスクセット タスク 周期 処理時間 利用率3
(ms) (ms)(
%
)
Tl5
0
1
0
2
0
.
0
T21
0
0
1
0
1
0
.
0
T32
0
0
2
5
1
2
.
5
T42
5
0
2
0
8
.
0
TS3
0
0
4
0
1
3
.
3
T64
0
0
8
0
2
0
.
0
このタスクセットは 6C1+
3C2+
2C3+
2C4+
Cs+
C6 ::;6T1 で、式(
2
)
を満たしており、スケジューラプル であるo また、この時の計算機利用率は式(1)か らU
=
0
.
8
3
8
(
6
)
である。 ここで、表2のタスクセットがこの計算機に マイグレートしてきたとする。この状態で8つ のタスクがこの計算機で動作することになるo タスク行，
TSが動作することで、式(1)をこの 8つのタスクセットに適用すると 1<
U
となり、この計算機は過負荷状態となるo この8つのタスクに虫ずして再スケジューリン グを行ない、優先度の高いタスクから実行が行 なわれるo 式(
2
)
により、最も優先度の低いタスクT6以 外のタスクがデツドラインを守る。すなわち、 タスク T6より優先度の高いの7つのタスクは、デッドラインを守るが、タスク
T
6
はデッドライ ンを守れない。 高優先度タスクセットによる計算機利用率UH
は式(1)からUH
=
0.881 であり、低優先度タスク(
T
6
)
の利用率は式(1) から UL=
0.20 である。 したがって、式(
3
)
から、TR
は となる。 ー1TFー
一
】ー “ 1 -0.838=
0.47TF いま、 TFが105の場合、TR
=
4
.
7
3
Ts=
14.7s となる。このシステムで、複数の計算機が障害 を起こし、このようなタスクマイグレーション が起こったことにより、計算織が105の閥、過 負荷状態になると、最も優先度の低いタスクが1
4
.
7
8
の問、デッドラインを守れない状態となる。 ただし、その問もイベントの取りこぼしは発生 していない。5
.
2
むから許容される TFの見積もり あるイベント処理要求に対するタスク処理が デッドラインを守れなくなる許容範囲となる時 間Tsはシステムを運用する環境によって異な る。したがって、計算機システムを利用する状 況に応じて、 Tsの時聞を満たすようにシステ ム設計をする必要があるo 式(4)から 1-u
J.F=
rr rr J.. UL+UH-U-' となる。いま、 Ts=
308 という要求に対して、前節のタスク例を用いる とする。この時のTFは l-0.838 TF=O
ーー ーー与今 ーー=-::'X 303=
20.08 となる。 たとえば、このシステムで、何らかの状況で 計算機がリセット処理や各種診断処理を行なわ なければならないとする。さらに、このシステ ムでは、優先度の低いタスクがデッドラインを 守らなくてもよい最大時聞が308とする。その 場合、上記計算より、 208以内にリセット処理 などの必要な処理が終了できれば、続<105で 回復処理が行なわれ、システムは再ぴ定常状態 にもどることiJfできる。6
むすび 過負荷状態におけるタスクスケジューリング について検討を行なったo 過負荷状態になった計算機で処理のできない タスク処理を、過負荷状態が解消した後に行な うことで、イベントを取りこぼすことなくあら かじめ見積もった時間以内でイベント処理を終 了させることを示したo これにより、システムのフォールトトレラン ト性が向上し、システムデザインの指針を与え ることができるo また、システム設計の自由度 を向上させることもできる。 本検討の前提として、マイグレートしたタス クが新たにスケジューリングされることで、デッ ドラインを守らないタスクになることは考慮さ れていない。 もし、マイグレートしたタスクの優先度が低 〈、デツドラインを守れなくなり、マイグレー ト先でイベントがキューイングされた状態で、 計算機が復旧した場合、キューにあるイベント 処理が終了するまで、再マイグレートすること を遅らせるか、タスクとともにキューにあるイ ベントも計算機問で移動しなければならない。 これらは、有効なタスクマイグレーションアル ゴリズムと組み合わせることで、解決可能であ ると考・えているo また、 RMAでは、タスクが起動する周期の みによって、そのタスクの優先度が決定するが、デッドラインを守られない状態までを考慮した 場合、タスクの重要度を反映した優先度にする 必要があるo そのためには、タスクの周期を変 更するなどの処置が要求される。今後もシステ ムにとってさらに優れた障害処理を検討する予 定である。 参考文献 [1] C.L.LIU etal.:“Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment" J.ACM
，
VoI20，
No.l，
J3on 1973，
pp.46-61{
勾
J.P.Lehoczky，
L.Sh3oand Y.Ding :“TheRateMonotonic Scheduling AIgorithm -Exact Characterization and A verage Case Be -havior" Proceedings of IEEE Real-Time Systerns Symposiu
叫
1989)[3] Lui Sha et a
1
.
:“Real-Time Scheduling Theol'y alld Ada."IEEE Computer，
April，
1990
