11章 并行実时间ソフトウェア设计の効率解析
Performance Analysis of Concurrent and Real-Time Softweare Designs
导入
ソフトウェア设计の数量的解析（quantitive analysis of a softweare design）： 与えられたハードウェア构成
の元、与えられている负荷で概念的にソフトウェアを実行してみること。
効用： 効率上の潜在的な问题の早期発见、别のソフトウェア设计や别のハードウェア构成の调査。 この章では
効率のモデル化（performance modeling）
とそれに対する
実时间スケジューリング理论(real-time scheduling theory)
の适用を通じてソフトウェア设计の効率解析に対する概観を提供する。
実时间スケジューリング理论は、厳しい时间制约を持つハードな実时间システム（hard real-time system）に特に适する。
効率モデル
効率モデル（performance model）： システムの効率の観点から実际の计算机システムを抽象化したもの。システムが実在するか否かは问わない。
形式
数学的なモデル（mathematical model）：システムの数学的表现（例：待ち行列モデル、Petriネットモデル、回帰モデル）
シミュレーションモデル（simulation model）：システムの构造と挙动のアルゴリズム的表现）。
种类
静的モデル（static model）：时间経过を全く加味しない、あるいは定常状态に関するモデル（例：回帰モデル、定常状态を扱う多くの待ち行列モデル）
动的モデル（dynamic model）：时间経过を考えるモデル（例：シミュレーションモデル）
回帰モデルについて
几つかのモデル（たとえば回帰モデル（regression model）のような経験的なモデル）は、计测して多くのデ
ータが集めることができる既存のシステムの分析に向く。 标本に対する统计的な曲线の当てはめ（例： 効率に関するデータに対する最小二乗法等）に基づく回帰モデルは
既存のシステムの分析に有用。 しかし、まだ存在していない、これからモデル化しようとしている対象には回帰モデルは向かない。 待ち行列モデル
待ち行列モデル（queueing model）： 限りある资源の取り合いの様子を解析してシステムの効率を予测するモデル。
解析的なモデルでは问题の数学的表现から解が直接推论できる。
通常は、解析しやすいように仮定が置かれる。
仮定の例： 「记忆なし」（”memory-less”）属性＝最後の要求からの経过时间とは独立に新たな要求が発生する。要求の时间间隔の分布は指数分布（最高の确率密度を最小の时间间隔である０とする多くの计算环境における最小の时间间隔はそうなっていないが。）になる。（定常状态の解析に限ればさらに简単化のための仮定が置かれる。）
待ち行列モデルは、计算机システムの概観を提供し、システムが要求を达成できるかどうかについての高レベルなモデルとして有用。より详细な効率の解析には他のモデル化技法が必要。 シミュレーションモデル
シミュレーションモデル（simulation model）：実世界におけるシステムの构造と挙动をアルゴリズムとして抽象化したもの。
设计が健全で时间的要求を达成できるかどうかを検证する効果的な方法。
开発中、さらには开発前のシステムを稼动中と同様にシミュレートできる。
モデル内に作りこむ仮定が现実的なものになるように注意。
动的なモデル（时间経过を明示的に取り扱う。）である。
一定期间に渡ってシステムの挙动を解析できる。
离散イベントシミュレーションモデル（discrete event simulation model）： システムの全ての状态変化をそれ
ぞれ离散的なイベントとして表现。イベント间の时间を飞ばしてシミュレーションの所要时间を「圧缩」できる。 计算机システムシミュレーションモデル（computer system simulation model）： 実际の计算机の挙动やハー
ドウェア上での设计ソフトウェアの実行をモデル化。入力＝抽象化された负荷（workload）、出力＝计算机の挙动を示す评価结果。
负荷について
よくある方法： 负荷を确率分布（probability distribution、しばしば负荷に関して正当化されてはい
ない仮定を置く）でモデル化する。
别の方法： 负荷をイベント系列（event trace、イベントは种类と时刻の组で表され、到着时间顺に并べられる）でモデル化する。（既存のシステムについては、イベント系列は実际に计算机を监视して得る。存在していないシステムについては稼动させる実世界を観测して得る。） 计算机システムをモデル化する际の问题
费用対効果
数多くの要素を考虑に入れる必要。例：モデル开発の费用、详细さの度合い、完成したモデルの早さ、精度。 一般にモデルの忠実さと费用にはトレードオフがある。（シミュレーションは最も详细に高精度にできる一方モデル化に挂かる费用が高いので适切な详细度を选ぶ必要がある。）
１つの解决策： 混合モデル（hybrid model）の利用。1つ以上のモデル化技法を组み合わせる。例：待ち行列／シミュレーションモデル、シミュレーション／回帰モデル。
システム中で特に详细に知りたい部分シミュレーションモデル技法
その他の相対的にあまり兴味がない部分待ち行列モデル技法や回帰モデル技法
検定と较正
実世界との整合性を较正（calibration）し検证（validation）する必要。
既存のシステムの场合、実システムの効率を计测して得られたデータが利用できる。
通常、较正と検定の过程はモデルの予测が実世界での効率と大きく违わないようにする统计的な反复の过程。
一旦较正と検定が终わればシミュレーション上で
「もし～だったら（”what if”）」シナリオの検讨ができる。
まだ実在しないシステムの効率モデルについて较正と検证の过程は、より间违いを含み胜ち（error-prone）。
OSのオーバーヘッド（コンテキスト切り替えやタスク间通信要求へのサービスの所要时间）のようなある肿のパラメータは対象となるシステムで実测可能。 タスクの実行时间などは推定するしかない。
効率にかかわるパラメータの推定精度にシミュレーションの精度が依存する。
Petriネット
有限状态机械（finite state machine、起こったイベントの种类だけでなくそれ以前に何が起こったかに依存する有限个の状态に依存して动作する）がイベント列のモデルに利用されてきたが逐次的な制约が强すぎるので并列性を表现できない。别のモデル化手法： Petriネット（Petri net）は直接的に并列性を表现し、有限状态机械を逐次的なサブセットとして含む。
... （利用可能３つ） （P操作） （利用） . （利用中１つ） （V操作） 図 1： セマフォを示すPetriネットの一部
Petriネットはプレース(place、円で表される)ととトランジション（transition、线で表される）と呼ばれる2种类のノードを持つ有向グラフとして
表される。
プレースにはトークン（token）と呼ばれる目印が付けられている。
トランジションに入力のある全てのプレースにトークンが揃うとトランジションは発火（fire）する。
トランジションが発火するとトランジションの入力侧の各プレースからトークンが一つずつ取り除かれて出力侧のプレースに移される。
拡张
様々にあるが、特に时间Petriネット（timed Petri net）は実时间システムのモデル化に有用。これはトランジションの発火の际に0でない有限の时间が経过する。これを用いれば効率の観点から解析できる。
応用
ハードウェアシステム、通信プロトコル、ソフトウェアシステムについてモデリングツールとしてだけでなく解析ツールとしても役立つ。
モデル化の事例： タスクの同期、タスク间のメッセージ通信、Adaの并行タスクアプリケーション
解析の事例： 可达性（reachability）とデッドロック（dead lock）の検出、统计的Petriネットによるスループットの解析。
以上から応答时间とスループットが重要となる実时间分散システムではPetriネットは魅力的。
実时间スケジューリング理论
导入
ハードな时间制约を持った并行タスクの优先度に基づくスケジューリングに関する理论。
タスク群について个々のCPU利用率（CPU utilization）がわかっている际に时间制约を満た
すかどうかをどのように决定するかについての理论。
优先度に基づく先取りスケジューリングを仮定（3章）。
この节の内容はSoftware Engineering Instituteの実时间スケジューリングに関するレポート[Sha90, SEI93]に基づいているので、より详しくはそちらを参照。
実时间スケジューリング理论は段阶的に复雑なものを含むように进化してきた。
独立した定期タスク→定期タスクと不定期（非同期）タスクの混在、タスク间の同期が必要な场合→Adaにおける并行タスクのスケジューリングというように段阶的に复雑な内容を含む。
定期的なタスクのスケジューリング
対象
独立した（通信同期なし）定期的なタスク群
定义
周期Tで一回あたりの実行CPU时间がCであるようなタスクのCPU利用率U=C/T （1周期に対する稼働时间の比）スケジュール可能性
タスクがスケジュール可能 タスクが时间制约を満たすこと （＝1周期が终わる前に1周期分のタスクが完了すること）
タスク群がスケジュール可能 各タスクが时间制约を満たすこと。
rate monotonic algorithm（monotonic単调、「比例単调アルゴリズム」）によれば、タスクは周期に基づく固定した优先度（短周期のもの程优先度高）を持つ。 例： 周期がta=10, tb=20, tc=30であるタスクの优先度はタスクa, b, cの顺。 利用率束缚定理
n个の独立したタスクがいつも时间制约を満たすために
は利用率の合计に制限があります。
定理１ 利用率束缚定理（UTILIZATION BOUND THEOREM）
rate monotonic algorithmでスケジュールされたn个の独立タスクが时间制约をいつも満たすためには C1/T1 + …+Cn/Tn ≦ n(21/n
– 1) = U(n)
であればよい。ここでタスクtiの実行时间はCiと周期はTi。 U(n)はln 2、约69%に収束する。 9つまでの计算例を本文の表に示す。
これはランダムにタスクを选んだ最悪の场合で、[Lehoczky89]では上限が88％にもなる例が示されている。
周期が调和している（タスクの周期が倍数の関系になっている）场合、いっそう上限は高くなる。
rate monotonic algorithmでスケジュールされている场合、过负荷に陥った场合の挙动が安定している。即ち高い优先度を持つ（周期が短い）タスクだけを含む部分集合は时间制约を満たす。プロセッサの负荷が上がると低い优先度を持つものから时间制约を満たせなくなる可能性が出てくる。
例： 以下のような3つのタスクについて利用率束缚定理を适用する。単位はmsec.でUi = Ci/Tiである。 t1: C1 = 20; T1 = 100; U1 = t2: C2 = 30; T2 = 150; U2 =
t3: C3 = 60; T3 = 200; U3 =
タスクの开始、终了时のコンテキスト切り替え时间はCPUタイムに含まれると仮定。
使用率の合计はで定理１による上限はなので上のタスク群はいつでも时间制约を守れる。 一方、
t3: C3 = 90; T3 = 200; U3 =
であったとする场合：
使用率の合计はとなり定理１の合计を超えるのでタスク群は时间制约を守れなくなる可能性がある。
しかしこの场合でもタスクt1、t2について利用率の合计はタスクが2个の场合の上限を下回っているので、rate monotonic algorithmの安定性からこの２つのタスクは必ず时间制约を守れる。
この定理１は悲観的な定理であり、タスクt3が実际に时间制约を守れるかどうかはより正确な定理２で确かめることができる。 完了时间定理
利用率の合计が定理1の上限を超えたならば、スケジュール可能性について、より正确な规准を与える定理２によって検査できる。
対象
定理1同様、独立な定期タスクについて考える。 最悪のケース（[Liu73, Lehoczsky89]）として全タスクが同时に実行开始を要求した场合を考える。
スケジュール可能性
各タスクが最初の周期を终わる前に完了できれば、时间制约は満たされる。（定理2では各タスクtiについて顺に最初の周期内に実行を终了できるかを见る。）
定理2 完了时间定理（COMPLETION TIME THEOREM）
1群の独立タスクについて、同时に开始された各タスクが最初の周期で时间制约を守れるならば、それらをどのような时间にスタートするように组み合わせても时间制约は守られる。
このチェックを行うには、与えられたタスクtiの周期の终わりについて调べるのと同时に、全てのより高い优先度の（＝より短い周期でtiから制御を夺って1回以上実行されている）タスクについても、関系のある全ての周期について调べる必要がある。 例：（前节の後半と同じ） t1: C1 = 20; T1 = 100; U1 =
t2: C2 = 30; T2 = 150; U2 =
t3: C3 = 90; T3 = 200; U3 =
本文のタイミング図参照。 1. 同时に3つのタスクが开始。(0msec) 2.
优先度の高いt1が1回目の実行开始-完了。(0-20msec) 3. 次いでt2が1回目の実行开始-完了。(20-50msec)) 4. t3が1回目の実行开始（50msec実行）。(50-100msec) 5.
优先度の高いt1の周期が回ってきてt3に割り込んで２回目の実行开始-完了。(100-120msec) 6.
t3が1回目の実行続行(30msec実行)。(120-150msec) 7.
t2の周期が回ってきてt3に割り込んで２回目の実行开始-完了。(150-180msec) 8.
t3が1回目の実行続行(10msec実行)-完了（次の周期まで残り10msec）。(180-190msec) 以上から3つのタスクは时间制约を満たす。 200msecの时点でCPUの残り时间は10msecであり、CPUの利用率は合计95%。 利用率の単纯合计は85%
3タスクの周期の公倍数にあたる时间（例えば
600msec）での利用率は85%（平均）となる。 完了时间定理の数学的定式化
完了时间定理は以下の定理3のように数学的に表现できる。
定理3
rate monotonic algorithmでスケジュール された1群の定期タスクが时间制约を守れるのは 以下の式が成り立つときで、かつそのときに限る。 ここで、Cj、Tjはそれぞれタスクtjの実行时间と周期である。
解説
?x?はx以下で最大の整数。?x?はx以上で最小
の整数。
Riは、优先度iまでの优先度を表す各kと、优先度iであるタスクの１周期の间に优先度kであるタスクが缲り返される回数pの対からなる集合。
i、(p,k)∈Riに関して：
pTkは、优先度iのタスク１周期の间に开始された优先度kのタスクの各周期の合计时间。
?pTkTj?は优先度iのタスク1周期の间に开始
された优先度kのタスクの全周期の合计时间に优先度jのタスクが実行开始される回数。
Σの一项分は、优先度iのタスク1周期の间に开始された优先度kのタスクの全周期の合计时间における优先度jのタスクのCPU利用率。
Σであらわされる総和は、优先度iのタスク1周期の间に开始された优先度kのタスクの全周期の合计时间における、优先度iのタスク以上の优先度を持つ全タスクの利用率合计。
以上から条件全体について：
全タスクが时间制约を満たす。iに関して利用率合计の（i以下の全てのkに関する）最小値が1より小さいこと
适用例
例：（前节と同じ） t1: C1 = 20; T1 = 100; U1 =
t2: C2 = 30; T2 = 150; U2 =
t3: C3 = 90; T3 = 200; U3 =
i=1: R1={(1,1)}
(1,1): C1/T1 = ≦1
i=2: R2={(1,1),(2,1)} (1,1): C1/T1+C2/T1 =
(2,1): C1/T2+C2/T2 = … ≦1
i=3: R3={(1,2),(2,１),(3,1)} (1,2): C1/T1+C2/T1+C3/T1 = (2,1): 2C1/T2+C2/T2+C3/T2 = …
(3,1): 2C1/T3+2C2/T3+C3/T3 = ≦1
以上よりt1、t2、t3はスケジュール可能。
定期的なタスクと不定期なタスクのスケジューリング
rate monotonic algorithmの拡张
非定期タスクの処理はある周期Taを持つ论理的な周期タスク内で一度に行われると仮定する。
このタスクの周期Taはこのタスクを起こすイベントの间隔の中で最小の値とする。
このタスクのCPU时间Caは以下のように决まる：周期毎に値Caのチケットが予约される。 1.
周期内でイベントが到着し场合、周期タスク内でチケットが消费され単位时间CaのCPU时间が消费される。 2.
周期内にイベントが到着しなかった场合、周期タスク内でチケットは単に破弃される。
以上の仮定に基づいてこのタスクの利用率をCa/Taと决定する。しかしチケットは毎回要求されるわけではないのでこの评価は最悪时の评価となる。
sporadic server algorithm
（sporadic散発的、「散発的サーバアルゴリズム」） 多くの非定期タスクがある场合に利用できる。スケジュール可能性を解析する立场からは、以下のように考えられる。
非定期タスクは、このタスクを起こすイベントの间隔の中で最小の値が周期であるような定期タスクと同一视される。
このタスクの周期Taはこのタスクを起こすイベントの间隔の中で最小の値とする。
各タスクは単位CPU时间としてCaを「蓄え」として
実时间设计効率解析
