搜索
11章並行・実時間ソフトウェア設計の効率解析1/911章並行・実時間ソフトウェア設計の効率解析PerformanceAnalysisofConcurrentandReal-TimeSoftweareDesigns11.1導入ソフトウェア設計の数量的解析（quantitiveanalysisofasoftwearedesign）：与えられたハードウェア構成の元、与えられている負荷で概念的にソフトウェアを実行してみること。効用：効率上の潜在的な問題の早期発見、別のソフトウェア設計や別のハードウェア構成の調査。この章では効率のモデル化（performancemodeling）とそれに対する実時間スケジューリング理論(real-timeschedulingtheory)の適用を通じてソフトウェア設計の効率解析に対する概観を提供する。実時間スケジューリング理論は、厳しい時間制約を持つハードな実時間システム（hardreal-timesystem）に特に適する。11.2効率モデル11.2.1概念効率モデル（performancemodel）：システムの効率の観点から実際の計算機システムを抽象化したもの。システムが実在するか否かは問わない。形式数学的なモデル（mathematicalmodel）：システムの数学的表現（例：待ち行列モデル、Petriネット・モデル、回帰モデル）シミュレーション・モデル（simulationmodel）：システムの構造と挙動のアルゴリズム的表現）。種類静的モデル（staticmodel）：時間経過を全く加味しない、あるいは定常状態に関するモデル（例：回帰モデル、定常状態を扱う多くの待ち行列モデル）動的モデル（dynamicmodel）：時間経過を考えるモデル（例：シミュレーション・モデル）回帰モデルについて幾つかのモデル（たとえば回帰モデル（regressionmodel）のような経験的なモデル）は、計測して多くのデータが集めることができる既存のシステムの分析に向く。⇒標本に対する統計的な曲線の当てはめ（例：効率に関するデータに対する最小二乗法等）に基づく回帰モデルは既存のシステムの分析に有用。⇒しかし、まだ存在していない、これからモデル化しようとしている対象には回帰モデルは向かない。11.2.2待ち行列モデル待ち行列モデル（queueingmodel）：限りある資源の取り合いの様子を解析してシステムの効率を予測するモデル。解析的なモデルでは問題の数学的表現から解が直接推論できる。通常は、解析しやすいように仮定が置かれる。仮定の例：「記憶なし」（”memory-less”）属性＝最後の要求からの経過時間とは独立に新たな要求が発生する。⇒要求の時間間隔の分布は指数分布（最高の確率密度を最小の時間間隔である０とする・・・多くの計算環境における最小の時間間隔はそうなっていないが・・・。）になる。（定常状態の解析に限ればさらに簡単化のための仮定が置かれる。）待ち行列モデルは、計算機システムの概観を提供し、システムが要求を達成できるかどうかについての高レベルなモデルとして有用。⇒より詳細な効率の解析には他のモデル化技法が必要。11.2.3シミュレーション・モデルシミュレーション・モデル（simulationmodel）：実世界におけるシステムの構造と挙動をアルゴリズムとして抽象化したもの。設計が健全で時間的要求を達成できるかどうかを検証する効果的な方法。開発中、さらには開発前のシステムを稼動中と同様にシミュレートできる。モデル内に作りこむ仮定が現実的なものになるように注意。動的なモデル（時間経過を明示的に取り扱う。）である。一定期間に渡ってシステムの挙動を解析できる。離散イベント・シミュレーション・モデル（discreteeventsimulationmodel）：システムの全ての状態変化をそれぞれ19/09/042/9離散的なイベントとして表現。⇒イベント間の時間を飛ばしてシミュレーションの所要時間を「圧縮」できる。計算機システム・シミュレーション・モデル（computersystemsimulationmodel）：実際の計算機の挙動やハードウェア上での設計ソフトウェアの実行をモデル化。入力＝抽象化された負荷（workload）、出力＝計算機の挙動を示す評価結果。負荷についてよくある方法：負荷を確率分布（probabilitydistribution、しばしば負荷に関して正当化されてはいない仮定を置く）でモデル化する。別の方法：負荷をイベント系列（eventtrace、イベントは種類と時刻の組で表され、到着時間順に並べられる）でモデル化する。（既存のシステムについては、イベント系列は実際に計算機を監視して得る。存在していないシステムについては稼動させる実世界を観測して得る。）11.2.4計算機システムをモデル化する際の問題費用対効果数多くの要素を考慮に入れる必要。例：モデル開発の費用、詳細さの度合い、完成したモデルの早さ、精度。一般にモデルの忠実さと費用にはトレード・オフがある。（シミュレーションは最も詳細に高精度にできる一方モデル化に掛かる費用が高いので適切な詳細度を選ぶ必要がある。）１つの解決策：混合モデル（hybridmodel）の利用。1つ以上のモデル化技法を組み合わせる。例：待ち行列／シミュレーション・モデル、シミュレーション／回帰モデル。システム中で特に詳細に知りたい部分⇒シミュレーション・モデル技法その他の相対的にあまり興味がない部分⇒待ち行列モデル技法や回帰モデル技法検定と較正実世界との整合性を較正（calibration）し検証（validation）する必要。既存のシステムの場合、実システムの効率を計測して得られたデータが利用できる。通常、較正と検定の過程はモデルの予測が実世界での効率と大きく違わないようにする統計的な反復の過程。一旦較正と検定が終わればシミュレーション上で「もし～だったら（”whatif”）」シナリオの検討ができる。まだ実在しないシステムの効率モデルについて較正と検証の過程は、より間違いを含み勝ち（error-prone）。OSのオーバーヘッド（コンテキスト切り替えやタスク間通信要求へのサービスの所要時間）のようなある腫のパラメータは対象となるシステムで実測可能。タスクの実行時間などは推定するしかない。効率にかかわるパラメータの推定精度にシミュレーションの精度が依存する。11.3Petriネット有限状態機械（finitestatemachine、起こったイベントの種類だけでなくそれ以前に何が起こったかに依存する有限個の状態に依存して動作する）がイベント列のモデルに利用されてきたが逐次的な制約が強すぎるので並列性を表現できない。⇒別のモデル化手法：Petriネット（Petrinet）は直接的に並列性を表現し、有限状態機械を逐次的なサブ・セットとして含む。図1：セマフォを示すPetriネットの一部Petriネットはプレース(place、円で表される)ととトランジション（transition、線で表される）と呼ばれる2種類のノードを持つ有向グラフとして表される。プレースにはトークン（token）と呼ばれる目印が付けられている。トランジションに入力のある全てのプレースにトークンが....（P操作）（V操作）（利用）（利用可能３つ）（利用中１つ）11章並行・実時間ソフトウェア設計の効率解析3/9揃うとトランジションは発火（fire）する。トランジションが発火するとトランジションの入力側の各プレースからトークンが一つずつ取り除かれて出力側のプレースに移される。拡張様々にあるが、特に時間Petriネット（timedPetrinet）は実時間システムのモデル化に有用。これはトランジションの発火の際に0でない有限の時間が経過する。これを用いれば効率の観点から解析できる。応用ハードウェア・システム、通信プロトコル、ソフトウェア・システムについてモデリングツールとしてだけでなく解析ツールとしても役立つ。モデル化の事例：タスクの同期、タスク間のメッセージ通信、Adaの並行タスク・アプリケーション解析の事例：可達性（reachability）とデッド・ロック（deadlock）の検出、統計的Petriネットによるスループットの解析。以上から応答時間とスループットが重要となる実時間・分散システムではPetriネットは魅力的。11.4実時間スケジューリング理論11.4.1導入ハードな時間制約を持った並行タスクの優先度に基づくスケジューリングに関する理論。タスク群について個々のCPU利用率（CPUutilization）がわかっている際に時間制約を満たすかどうかをどのように決定するかについての理論。優先度に基づく先取りスケジューリングを仮定（3章）。この節の内容はSoftwareEngineeringInstituteの実時間スケジューリングに関するレポート[Sha90,SEI93]に基づいているので、より詳しくはそちらを参照。実時間スケジューリング理論は段階的に複雑なものを含むように進化してきた。独立した定期タスク→定期タスクと不定期（非同期）タスクの混在、タスク間の同期が必要な場合→Adaにおける並行タスクのスケジューリングというように段階的に複雑な内容を含む。11.4.2定期的なタスクのスケジューリング対象独立した（通信・同期なし）定期的なタスク群定義周期Tで一回あたりの実行CPU時間がCであるようなタスクのCPU利用率U=C/T（1周期に対する稼働時間の比）スケジュール可能性タスクがスケジュール可能⇒タスクが時間制約を満たすこと（＝1周期が終わる前に1周期分のタスクが完了すること）タスク群がスケジュール可能⇒各タスクが時間制約を満たすこと。ratemonotonicalgorithm（monotonic・・・単調、「比例単調アルゴリズム」？）によれば、タスクは周期に基づく固定した優先度（短周期のもの程優先度高）を持つ。例：周期がta=10,tb=20,tc=30であるタスクの優先度はタスクa,b,cの順。11.4.3利用率束縛定理n個の独立したタスクがいつも時間制約を満たすためには利用率の合計に制限があります。定理１利用率束縛定理（UTILIZATIONBOUNDTHEOREM）ratemonotonicalgorithmでスケジュールされたn個の独立タスクが時間制約をいつも満たすためにはC1/T1+…+Cn/Tn≦n(21/n–1)=U(n)であればよい。ここでタスクtiの実行時間はCiと周期はTi。U(n)はln2、約69%に収束する。9つまでの計算例を本文の表11.1に示す。これはランダムにタスクを選んだ最悪の場合で、[Lehoczky89]では上限が88％にもなる例が示されている。周期が調和している（タスクの周期が倍数の関係になっている）場合、いっそう上限は高くなる。ratemonotonicalgorithmでスケジュールされている場合、過負荷に陥った場合の挙動が安定している。即ち高い優先度を持つ（周期が短い）タスクだけを含む部分集合は時間制約を満たす。プロセッサの負荷が上がると低い優先度を持つものから時間制約を満たせなくなる可能性が出てくる。19/09/044/9例：以下のような3つのタスクについて利用率束縛定理を適用する。単位はmsec.でUi=Ci/Tiである。t1:C1=20;T1=100;U1=0.2t2:C2=30;T2=150;U2=0.2t3:C3=60;T3=200;U3=0.3タスクの開始、終了時のコンテキスト切り替え時間はCPUタイムに含まれると仮定。使用率の合計は0.7で定理１による上限は0.799なので上のタスク群はいつでも時間制約を守れる。一方、t3:C3=90;T3=200;U3=