実时间设计効率解析.doc

11章 並行実時間設計効率解析11章 並行実時間設計効率解析Performance Analysis of Concurrent and Real-Time Softweare Designs9/911.1 導入設計数量的解析（quantitive analysis of a softweare design）： 与構成元、与負荷概念的実行。効用： 効率上潜在的問題早期発見、別設計別構成調査。章l 効率化（performance modeling）対l 実時間理論(real-time scheduling theory)適用通設計効率解析対概観提供。実時間理論、厳時間制約持実時間（hard real-time system）特適。11.2 効率11.2.1概念効率（performance model）： 効率観点実際計算機抽象化。実在否問。形式数学的（mathematical model）：数学的表現（例：待行列、Petri、回帰）（simulation model）：構造挙動的表現）。種類静的（static model）：時間経過全加味、定常状態関（例：回帰、定常状態扱多待行列）動的（dynamic model）：時間経過考（例：）回帰幾（回帰（regression model）経験的）、計測多集既存分析向。標本対統計的曲線当（例： 効率関対最小二乗法等）基回帰既存分析有用。、存在、化対象回帰向。11.2.2 待行列待行列（queueing model）： 限資源取合様子解析効率予測。l 解析的問題数学的表現解直接推論。l 通常、解析仮定置。仮定例： 記憶（”memory-less”）属性最後要求経過時間独立新要求発生。要求時間間隔分布指数分布（最高確率密度最小時間間隔多計算環境最小時間間隔。）。（定常状態解析限簡単化仮定置。）l 待行列、計算機概観提供、要求達成高有用。詳細効率解析他化技法必要。11.2.3 （simulation model）：実世界構造挙動抽象化。l 設計健全時間的要求達成検証効果的方法。l 開発中、開発前稼動中同様。l 内作仮定現実的注意。l 動的（時間経過明示的取扱。）。l 一定期間渡挙動解析。離散（discrete event simulation model）： 全状態変化離散的表現。間時間飛所要時間圧縮。計算機（computer system simulation model）： 実際計算機挙動上設計実行化。入力抽象化負荷（workload）、出力計算機挙動示評価結果。負荷方法： 負荷確率分布（probability distribution、負荷関正当化仮定置）化。別方法： 負荷系列（event trace、種類時刻組表、到着時間順並）化。（既存、系列実際計算機監視得。存在稼動実世界観測得。）11.2.4 計算機化際問題費用対効果数多要素考慮入必要。例：開発費用、詳細度合、完成早、精度。一般忠実費用。（最詳細高精度一方化掛費用高適切詳細度選必要。）解決策： 混合（hybrid model）利用。1以上化技法組合。例：待行列、回帰。中特詳細知部分技法他相対的興味部分待行列技法回帰技法検定較正実世界整合性較正（calibration）検証（validation）必要。l 既存場合、実効率計測得利用。l 通常、較正検定過程予測実世界効率大違統計的反復過程。l 一旦較正検定終上（”what if”）検討。l 実在効率較正検証過程、間違含勝（error-prone）。l OS（切替間通信要求所要時間）腫対象実測可能。l 実行時間推定。l 効率推定精度精度依存。11.3 Petri有限状態機械（finite state machine、起種類以前何起依存有限個状態依存動作）列利用逐次的制約強並列性表現。別化手法： Petri（Petri net）直接的並列性表現、有限状態機械逐次的含。図 1： 示Petri一部l Petri(place、円表)（transition、線表）呼2種類持有向表。l （token）呼目印付。l 入力全揃発火（fire）。l 発火入力側各一取除出力側移。拡張様、特時間Petri（timed Petri net）実時間化有用。発火際0有限時間経過。用効率観点解析。応用、通信、解析役立。化事例： 同期、間通信、Ada並行解析事例： 可達性（reachability）（dead lock）検出、統計的Petri解析。以上応答時間重要実時間分散Petri魅力的。11.4 実時間理論11.4.1 導入l 時間制約持並行優先度基関理論。l 群個CPU利用率（CPU utilization）際時間制約満決定理論。l 優先度基先取仮定（3章）。l 節内容Software Engineering Institute実時間関Sha90, SEI93基、詳参照。l 実時間理論段階的複雑含進化。l 独立定期定期不定期（非同期）混在、間同期必要場合Ada並行段階的複雑内容含。11.4.2 定期的対象独立（通信同期）定期的群定義周期T一回実行CPU時間CCPU利用率U=C/T （1周期対稼働時間比）可能性可能 時間制約満 （1周期終前1周期分完了）群可能 各時間制約満。rate monotonic algorithm（monotonic単調、比例単調？）、周期基固定優先度（短周期程優先度高）持。例： 周期ta=10, tb=20, tc=30優先度a, b, c順。11.4.3 利用率束縛定理n個独立時間制約満利用率合計制限。定理利用率束縛定理（UTILIZATION BOUND THEOREM）rate monotonic algorithmn個独立時間制約満C1/T1 + +Cn/Tn n(21/n 1) = U(n)。ti実行時間Ci周期Ti。l U(n)ln 2、約69%収束。l 9計算例本文表11.1示。l 選最悪場合、Lehoczky89上限88例示。l 周期調和（周期倍数関係）場合、上限高。l rate monotonic algorithm場合、過負荷陥場合挙動安定。即高優先度持（周期短）含部分集合時間制約満。負荷上低優先度持時間制約満可能性出。例： 以下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含仮定。l 使用率合計0.7定理上限0.799上群時間制約守。一方、t3: C3 = 90; T3 = 200; U3 = 0.45場合：l 使用率合計0.85定理合計超群時間制約守可能性。l 場合t1、t2利用率合計0.42個場合上限0.828下回、rate monotonic algorithm安定性必時間制約守。l 定理悲観的定理、t3実際時間制約守正確定理確。11.4.4 完了時間定理利用率合計定理1上限超、可能性、正確規準与定理検査。対象定理1同様、独立定期考。最悪（Liu73, Lehoczsky89）全同時実行開始要求場合考。可能性各最初周期終前完了、時間制約満。（定理2各ti順最初周期内実行終了見。）定理2 完了時間定理（COMPLETION TIME THEOREM）1群独立、同時開始各最初周期時間制約守、時間組合時間制約守。l 行、与ti周期終調同時、全高優先度（短周期ti制御奪1回以上実行）、関係全周期調必要。例：（前節後半同）t1: C1 = 20; T1 = 100; U1 = 0.2t2: C2 = 30; T2 = 150; U2 = 0.2t3: C3 = 90; T3 = 200; U3 = 0.45本文図11.1参照。1. 同時3開始。(0msec)2. 優先度高t11回目実行開始-完了。(0-20msec)3. 次t21回目実行開始-完了。(20-50msec)4. t31回目実行開始（50msec実行）。(50-100msec)5. 優先度高t1周期回t3割込回目実行開始-完了。(100-120msec)6. t31回目実行続行(30msec実行)。(120-150msec)7. t2周期回t3割込回目実行開始-完了。(150-180msec)8. t31回目実行続行(10msec実行)-完了（次周期残10msec）。(180-190msec)l 以上3時間制約満。l 200msec時点CPU残時間10msec、CPU利用率合計95%。l 利用率単純合計85%l 3周期公倍数時間（例600msec）利用率85%（平均）。11.4.5 完了時間定理数学的定式化完了時間定理以下定理3数学的表現。定理3rate monotonic algorithm1群定期時間制約守以下式成立、限。、Cj、Tjtj実行時間周期。解説l x以下最大整数。x以上最小整数。l Ri、優先度i優先度表各k、優先度i周期間優先度k繰返回数p対集合。i、(p,k)Ri関：l pTk、優先度i周期間開始優先度k各周期合計時間。l 優先度i1周期間開始優先度k全周期合計時間優先度j実行開始回数。l 一項分、優先度i1周期間開始優先度k全周期合計時間優先度jCPU利用率。l 総和、優先度i1周期間開始優先度k全周期合計時間、優先度i以上優先度持全利用率合計。以上条件全体：l 全時間制約満。i関利用率合計（i以下全k関）最小値1小適用例例：（前節同）t1: C1 = 20; T1 = 100; U1 = 0.2t2: C2 = 30; T2 = 150; U2 = 0.2t3: C3 = 90; T3 = 200; U3 = 0.45i=1: R1=(1,1)(1,1): C1/T1 = 0.2 1i=2: R2=(1,1),(2,1)(1,1): C1/T1+C2/T1 = 0.5(2,1): C1/T2+C2/T2 = 0.33 1i=3: R3=(1,2),(2,),(3,1)(1,2): C1/T1+C2/T1+C3/T1 = 1.4(2,1): 2C1/T2+C2/T2+C3/T2 = 1.066(3,1): 2C1/T3+2C2/T3+C3/T3 = 0.95 1以上t1、t2、t3可能。11.4.6 定期的不定期rate monotonic algorithm拡張l 非定期処理周期Ta持論理的周期内一度行仮定。l 周期Ta起間隔中最小値。l CPU時間Ca以下決：周期毎値Ca予約。1. 周期内到着場合、周期内消費単位時間CaCPU時間消費。2. 周期内到着場合、周期内単破棄。l 以上仮定基利用率Ca/Ta決定。毎回要求評価最悪時評価。sporadic server algorithm（sporadic散発的、散発的？）多非定期場合利用。可能性解析立場、以下考。l 非定期、起間隔中最小値周期定期同一視。l 周期Ta起間隔中最小値。l 各単位CPU時間Ca蓄割当。l 割当Ca周期Ta内任意時点消費。l 方法非定期、周期従異優先度置、定期同様扱。11.4.7 同期実時間理論間同期含拡張。優先度逆転（priority inversion）問題：入、入高位優先度持得。無制限優先度逆転：高低、別高得。大変短、内先取止回避可能。priority ceiling protocol（ceil天井張、上限付優先度？）自分高位高相互回避、優先度逆転制限設。以下、簡単1場合考。l 調整可能優先度： 自分高優先度優先度一連上上。目的実行早終、時間縮。長時間高優先度止。l priority ceiling P操作付二値S： S獲得全中最高優先度持。従得低優先度優先度応優先度上。l 相互： 2、実行完了互必要場合。priority ceiling protocol取扱。11.4.8 一般化実時間理論実時間問題、rate monotonic前提成立。基本的rate monotonic 理論拡張必要例1：前節優先度逆転問題例2：非同期同期手法場合、非同期見上周期短（優先度）同期以下、非同期駆動発生後実行必要。用語本文中優先度（priority）優先度逆転（priority inversion）使意味以下通：rate monotonic優先度（rate monotonic priority）周期基優先度、重要度基優先度。実際優先度通知。rate monotonic 優先度逆転（rate monotonic priority inversion）実際優先度一致場合、rate monotonic優先度優先度逆転起場合。rate monotonic優先度逆転例2考：25msec定期最短50msec間隔呼非定期rate monotonic優先度定期方高実際優先度駆動実現非定期高。非定期先取、逆転発生。拡張目標：l 低優先度取扱。l rate monotonic優先度従高優先度取扱。rate monotonic従場合、後者前者似。ti ：周期Ti間単位CPU時間Ci消費。考。以下条件考、時間制約最初行当考。a) 短周期先取時間：何度ti先取j個群Hn、Hn内tj（周期Tj、CPU時間Cj）TjTi、tj利用率Cj/Tjb) ti実行時間：tiTi間一度実行、単位時間CiCPU時間消費。c) 長周期高優先度先取時間：H1属rate monotonic従優先度持k個、消費CPU時間Ck、最悪場合tk利用率Ck/Tid) 低優先度時間：長周期持回数1。遅個状況（priority ceiling protocol与）基解析。与ti最悪時間Bi、時間利用率Bi/Ti。以上定理一般化利用率制限定理（条件上述）説明l 最初項和a)後項（）内最初項b)、次c)、最後項和d)条件対応。l 求Ui最悪時（本文表11.1）上限下回時間制約満。l rate monotonic安定性保証、各Ui計算必要注意。l 判定失敗場合、一般化完了時間定理正確判定可能。上記条件考慮上、完了時間検討。定理図的図説明。11.4.9 実時間設計設計段階後、実時間理論一群並行対適用。（本書設計段階適用重点置。）l 設計段階CPU時間推定値注意。l 実時間厳時間制約、悲観的CPU利用率制限定理（最悪上限0.69）信頼安全（実時間理論上限値上）。l 上限値満場合別方法探必要。l 悲観的設計者観点、0.69超利用率上限深刻時間制約（守深刻）受入。設計時優先度決定問題：l 一般rate monotonic優先度付用。l rate monotonic優先度付定期簡単適応。l 非定期頻度推定、定期場合見上周期求優先度、駆動側面考最高優先度望。l 複数同一優先度同一周期場合設計者決定下解決必要。一般重要優先度上。11.4.10 一般化実時間定理適用例周期t1：C1=20;T1=100;U1=0.2非定期t2：C2=15;T2=150;（最悪時）U2=0.1割込駆動非定期ta：Ca=4;Ta=200;Ua=0.02定期t3：C3=30;T3=300;U3=0.1条件l ta200msec以内終取。l t1、t2、t3守同一。l 切替各CPU時間先頭含。優先度厳密rate monotonic優先度t1、t2、t3 、ta順。ta関条件実際優先度、ta、t1、t2、t3順。解析l CPU利用率単純合計0.42上限0.69下回、rate monotonic優先順位破個検討必要。tal ta最高優先度必要CPU利用上、CPU時間0.02必時間制約守。t1a. 周期短先取時間：。b. 自身実行時間：利用率U1=0.2。c. 長周期高優先度先取時間：ta該当。利用率Ca/T1=0.04。d. 低優先度時間：t2、t3可能性。優先度打切従、実際高、最悪場合CPU時間長t3場合考。B3=C3仮定利用率B3/T1=0.3。以上最悪場合利用率合計0.54上限0.69下回、t1時間制約守。t2a. 周期短先取時間：t1該当。U1=0.2。b. 自身実行時間：利用率U2=0.1。c. 長周期高優先度先取時間：ta該当。利用率Ca/T2=0.03。d. 低優先度時間：t3可能性。B3=C3仮定利用率B3/T2=0.2。以上最悪場合利用率合計0.53上限0.69下回、t2時間制約守。t3a. 周期短先取時間：t1 、t2 、ta該当。U1 +U2 +Ua=0.32。b. 自身実行時間：利用率U3=0.1。c. 長周期高優先度先取時間：。d. 低優先度時間：。以上最悪場合利用率合計0.42上限0.69下回、t2時間制約守。l 以上4全時間制約守。11.4.11 Ada実時間Ada概念的、厳時間制約持実時間対適合性由来。例：Ada：l 優先度待行列