実時間設(shè)計効率解析

1、11 章 並行 ? 実時間設(shè)計効率解析Performance Analysis of Concurrent and Real-Time Softweare Designs11.1 導(dǎo)入設(shè)計數(shù)量的解析（quantitiveanalysis of asoftweare design）：與構(gòu)成元、與負(fù)荷概念的実行。効用： 効率上潛在的問題早期発見、別設(shè)計別構(gòu)成調(diào)査。章効率化 （performance modeling ）対実 時間 理 論 ( real-timeschedulingtheory)適用通設(shè)計効率解析対概観提供。実時間理論、厳時間制約持 実時間（hard real-time system

2、）特適。11.2 効率概念効率 （performance model）：効率観點(diǎn)実際計算機(jī)抽象化。実在否問。形式數(shù)學(xué)的 （mathematical model ）：數(shù)學(xué)的表現(xiàn)（例：待行列、Petri ?、回帰） ?（simulation model）：構(gòu)造挙動的表現(xiàn)）。種類靜的 （static model）：時間経過全加味、定常狀態(tài)関（例：回帰、定常狀態(tài)扱多待行列）動的 （dynamic model）：時間経過考（例： ?）回帰幾（回帰 （regression model）経験的）、計測多集既存分析向。? 標(biāo)本対統(tǒng)計的曲線當(dāng)（例： 効率関対最小二乗法等）基回帰既存分析有用。? 、存在、化対象回

3、帰向。待行列待行列 （queueing model）：限資源取合様子解析効率予測。解析的問題數(shù)學(xué)的表現(xiàn)解直接推論。通常、解析仮定置。仮定例： 記憶（”memory-less”）屬性最後要求経過時間獨(dú)立新要求発生。 ?要求時間間隔分布指數(shù)分布（最高確率密度最小時間間隔 ?多計算環(huán)境最小時間間隔 ?。）。（定常狀態(tài)解析限簡単化仮定置。）待行列、計算機(jī)概観提供、要求達(dá)成高有用。 ?詳細(xì)効率解析他化技法必要。? ?（simulation model）：実世界構(gòu)造挙動抽象化。設(shè)計健全時間的要求達(dá)成検証効果的方法。開発中、開発前稼動中同様。內(nèi)作仮定現(xiàn)実的注意。動的（時間経過明示的取扱。）。一定期間渡挙動解

4、析。離散 ? ? （discrete eventsimulationmodel）：全狀態(tài)変化離散的表現(xiàn)。?間時間飛所要時間圧縮。計算機(jī) ? ?（computer systemsimulation model ）：実際計算機(jī)挙動上設(shè)計実行化。入力抽象化負(fù)荷（workload ）、出力計算機(jī)挙動示評価結(jié)果。負(fù)荷方法：負(fù)荷確率分布 （probability distribution 、負(fù)荷関正當(dāng)化仮定置）化。別方法： 負(fù)荷系列（event trace 、種類時刻組表、到著時間順並）化。（既存、系列実際計算機(jī)監(jiān)視得。存在稼動実世界観測得。）計算機(jī)化際問題費(fèi)用対効果數(shù)多要素考慮入必要。例：開発費(fèi)用、詳細(xì)

5、度合、完成早、精度。一般忠実費(fèi)用 ?。（最詳細(xì)高精度一方化掛費(fèi)用高適切詳細(xì)度選必要。）解決策： 混合 （hybrid model）利用。1 以上化技法組合。例：待行列 ?、回帰。中特詳細(xì)知部分 ? ?技法他相対的興味部分 ?待行列技法回帰技法検定較正実世界整合性 較正（calibration ）検証（validation ）必要。既存場合、実効率計測得利用。通常、較正検定過程予測実世界効率大違統(tǒng)計的反復(fù)過程。一旦較正検定終上 （”what if ”）検討。実在効率較正検証過程、間違含勝 （error-prone ）。OS （切替間通信要求所要時間）腫対象実測可能。実行時間推定。効率推定精度精度

6、依存。11.3 Petri 有限狀態(tài)機(jī)械 （finite state machine、起種類以前何起依存有限個狀態(tài)依存動作）列利用逐次的制約強(qiáng)並列性表現(xiàn)。?別化手法：Petri（Petri net）直接的並列性表現(xiàn)、有限狀態(tài)機(jī)械逐次的?含。. （利用可能）（P操作）（利用）.（利用中）（V操作）図1：示 Petri 一部Petri ( place、円表)（transition 、線表）呼2 種類持有向表。 （token）呼目印付。入力全揃発火 （fire ）。11.4.2 定期的発火入力側(cè)各対象一取除出力側(cè)獨(dú)立（通信 ?同期）定期的群移。定義拡張周期 T 一回実行 CPU 時間 C 様、特時間

7、 Petri （timed Petri net ）実時 CPU 利用率 U=C/T （1 周期対稼働時間比）間化有用。発火可能性際 0 有限時間経過。用効可能 ? 時間制約満率観點(diǎn)解析。 （1 周期終前 1 周期分完了）応用群可能 ? 各時間制約満 ?、通信、? 。解析役立?；吕?同期、間通信、 Ada 並行 ? 可達(dá)性 （reachability ） ?（deadlock）検出、統(tǒng)計的 Petri 解析。 ?分散 Petri 魅力的。11.4 実時間理論導(dǎo)入時間制約持並行優(yōu)先度基関理論。群個CPU利用率（CPUutilization ）際時間制約満決定理論。優(yōu)先度基先取仮定（3 章）。節(jié)

8、內(nèi)容 Software Engineering Institute 実時間関Sha90, SEI93基、詳參照。実時間理論段階的複雑含進(jìn)化。獨(dú)立定期定期不定期（非同期）混在、間同期必要場合 Ada 並行段階的複雑內(nèi)容含。rate monotonicalgorithm （monotonic ?単調(diào)、比例単調(diào)？）、周期基固定優(yōu)先度（短周期程優(yōu)先度高）持。例：周期 ta=10, tb=20, t c=30 優(yōu)先度a, b, c 順。利用率束縛定理n 個獨(dú)立時間制約満利用率合計制限。定理 利用率束縛定理（UTILIZATIONBOUND THEOREM）rate monotonic algorithm

9、 n 個獨(dú)立時間制約満C1/T1 + +C n/T n n(21/n 1) = U(n)。ti 実行時間Ci 周期 Ti 。U(n) ln 2、約 69%収束。9 計算例本文表11.1 示。選最悪場合、 Lehoczky89 上限 88例示。周期調(diào)和（周期倍數(shù)関係）場合、上限高。rate monotonic algorithm 場合、過負(fù)荷陥場合挙動安定。即高優(yōu)先度持（周期短）含部分集合時間制約満。負(fù)荷上低優(yōu)先度持時間制約満可能性出。例： 以下3 利用率束縛定理適用。単位 msec. Ui = Ci /T i 。t1 : C1 = 20; T 1 = 100; U 1 = 0.2t2 : C2

10、 = 30; T 2 = 150; U 2 = 0.2t3 : C3 = 60; T 3 = 200; U 3 = 0.3開始、終了時切替時間 CPU 含仮定。使用率合計0.7 定理上限 0.799 上群時間制約守。一方、t3 : C3 = 90; T 3 = 200; U 3 = 0.45場合：使用率合計0.85 定理合計超群時間制約守可能性。場合t1、t2 利用率合計0.4 2 個場合上限0.828 下回、rate monotonic algorithm 安定性必時間制約守。定理悲観的定理、t3 実際時間制約守正確定理確。完了時間定理利用率合計定理1上限超、可能性、正確規(guī)準(zhǔn)與定理?xiàng)蕱?。対?/p>

11、定理 1 同様、獨(dú)立定期考。最悪（Liu73,Lehoczsky89 ）全同時実行開始要求場合考?？赡苄愿髯畛踔芷诮K前完了、時間制約満。（定理2 各ti 順最初周期內(nèi)実行終了見。）定理2 完了時間定理（COMPLETIONTIMETHEOREM ）1 群獨(dú)立、同時開始各最初周期時間制約守、時間組合時間制約守。行、與ti周期終調(diào)同時、全高優(yōu)先度（短周期t i 制御奪 1 回以上実行）、関係全周期調(diào)必要。例：（前節(jié)後半同）t1: C 1 = 20; T 1 = 100; U 1 = 0.2t2: C 2 = 30; T 2 = 150; U 2 = 0.2t3: C 3 = 90; T 3 = 2

12、00; U 3 = 0.45本文図11.1 參照。1. 同時 3 開始。(0msec)2. 優(yōu)先度高 t1 1 回目実行開始 -完了。(0-20msec)3. 次 t2 1 回目実行開始 -完了。(20-50msec)4. t3 1 回目実行開始（ 50msec 実行） ?。(50-100msec)5. 優(yōu)先度高 t1 周期回 t3 割噫回目実行開始 - 完了。(100-120msec)6. t3 1 回目実行続行 (30msec 実行 ) ?。(120-150msec)7. t2 周期回 t3 割噫回目実行開始- 完了。(150-180msec)8. t3 1 回目実行続行 (10msec

13、実行 )- 完了（次周期殘10msec）。(180-190msec)以上 3 時間制約満。200msec 時點(diǎn)CPU 殘時間 10msec 、CPU 利用率合計95%。利用率単純合計85%3 周期公倍數(shù)時間（例 600msec）利用率85%（平均）。完了時間定理數(shù)學(xué)的定式化完了時間定理以下定理3 數(shù)學(xué)的表現(xiàn)。定理 3rate monotonic algorithm 1 群定期時間制約守以下式成立、限。1inimini1pTkC j1,pTkTj(k, p) Rij 1Ri( k, p) | 1 k i , p 1, ,Ti Tk、Cj 、Tj t j 実行時間周期。解説x x 以下最大整數(shù)。x

14、 x 以上最小整數(shù)。Ri 、優(yōu)先度 i 優(yōu)先度表各k 、優(yōu)先度 i周期間優(yōu)先度 k 繰返回數(shù) p 対集合。? i ?(p,k) Ri 関：pTk 、優(yōu)先度 i 周期間開始優(yōu)先度 k 各周期合計時間。pTk T j 優(yōu)先度 i 1 周期間開始優(yōu)先度 k 全周期合計時間優(yōu)先度 j 実行開始回數(shù)。一項(xiàng)分、優(yōu)先度 i 1 周期間開始優(yōu)先度 k 全周期合計時間優(yōu)先度 j CPU 利用率。総和、優(yōu)先度 i 1 周期間開始優(yōu)先度k 全周期合計時間、優(yōu)先度 i 以上優(yōu)先度持全利用率合計。以上條件全體：全時間制約満。 ?i 関利用率合計（i 以下全 k 関）最小値 1 小適用例例：（前節(jié)同）t1 : C1 =

15、20; T 1 = 100; U 1 = 0.2t2 : C2 = 30; T 2 = 150; U 2 = 0.2t3 : C3 = 90; T 3 = 200; U 3 = 0.45i=1: R 1=(1,1)(1,1): C 1/T1 = 0.2 1i=2: R 2=(1,1),(2,1)(1,1): C 1/T 1+C 2/T 1 = 0.5(2,1): C 1/T 2+C 2/T 2 = 0.33 1i=3: R 3=(1,2),(2, ),(3,1)(1,2): C 1/T 1+C 2/T 1+C3 /T1 = 1.4(2,1): 2C 1/T2 +C2/T 2+C3/T 2 =

16、1.066 (3,1): 2C 1/T3 +2C2 /T 3+C3/T3 = 0.95 1以上 t1、t2、t3 可能。定期的不定期rate monotonic algorithm拡張非定期処理周期 Ta 持論理的周期內(nèi)一度行仮定。周期 Ta 起間隔中最小値。CPU 時間 Ca 以下決：周期毎値 Ca 予約。1. 周期內(nèi)到著場合、周期內(nèi)消費(fèi)単位時間 Ca CPU 時間消費(fèi)。2. 周期內(nèi)到著場合、周期內(nèi)単破棄。以上仮定基利用率 Ca/T a 決定。毎回要求評価最悪時評価。sporadic server algorithm（sporadic?散発的、散発的？）多非定期場合利用?？赡苄越馕隽觥⒁韵?/p>

17、考。非定期、起間隔中最小値周期定期同一視。周期 Ta 起間隔中最小値。各単位 CPU 時間 Ca 蓄割當(dāng)。割當(dāng) Ca 周期 Ta 內(nèi)任意時點(diǎn)消費(fèi)。方法非定期、周期従異優(yōu)先度置、定期同様扱。同期実時間理論間同期含拡張。優(yōu)先度逆転 （priorityinversion ）問題： ?非同期見上周期短（優(yōu)先度）同期以下、非同期駆動発生後実行必要。用語本文 中 優(yōu)先 度 （priority ）優(yōu) 先度 逆転 （priorityinversion ）使意味以下通：rate monotonic優(yōu)先度 （rate monotonic priority ）入、?入 周期基優(yōu)先度、重要度基優(yōu)先度高位優(yōu)先度持得。実

18、際優(yōu)先度通知無制限優(yōu)先度逆転：高低。、別高得。ratemonotonic優(yōu) 先 度 逆 転 （ratemonotonicpriority ?大変短、? inversion ）內(nèi)先取止回避可能。priority ceiling protocol（ceil ?天井張、上限付優(yōu)先度？）自分高位高相互?回避、優(yōu)先度逆転制限設(shè)。以下、簡単?1場合考。調(diào)整可能優(yōu)先度：自分高優(yōu)先度優(yōu)先度一連上上。目的実行早終、時間縮。長時間高優(yōu)先度止。priority ceiling P操作付二値 S： S獲得全中最高優(yōu)先度持。従得低優(yōu)先度優(yōu)先度応優(yōu)先度上。相互?2：、実行完了互必要場合。priorityceiling p

19、rotocol 取扱。一般化実時間理論実時間問題、 rate monotonic 前提成立。?基本的rate monotonic理論拡張必要例 1：前節(jié)優(yōu)先度逆転問題例 2：非同期同期手法場合、実際優(yōu)先度一致場合、 rate monotonic 優(yōu)先度優(yōu)先度逆転起場合。rate monotonic優(yōu)先度逆転例2 考：25msec 定期最短 50msec 間隔呼非定期rate monotonic優(yōu)先度定期方高実際優(yōu)先度駆動実現(xiàn)非定期高。 ?非定期先取、逆転発生。拡張目標(biāo)：低優(yōu)先度取扱。rate monotonic 優(yōu)先度従高優(yōu)先度取扱。rate monotonic従場合、後者前者似。ti ：周期

20、T i 間単位CPU 時間 Ci 消費(fèi)?？肌Ｒ韵聴l件考、時間制約最初行當(dāng)考。a) 短周期先取時間：何度 ti 先取 j 個群 Hn、Hn 內(nèi) t j（周期 Tj 、CPU 時間 Cj）Tj <T i 、tj 利用率Cj/T jb) t i 実行時間：ti Ti 間一度実行、単位時間Ci CPU時間消費(fèi)。c) 長周期高優(yōu)先度先取時間：H1 屬 rate monotonic 従優(yōu)先度持k 個、消費(fèi)CPU 時間 Ck 、最悪場合tk 利用率 Ck/T id) 低優(yōu)先度時間：長周期持回數(shù) 1。遅個狀況（priority ceiling protocol 與）基解析。與 ti最悪時間Bi 、時間利

21、用率Bi/T i。以上 ?定理一般化利用率制限定理（條件上述）U i (C j )1 (Ci BiCk )j H nT jTik H n説明最初項(xiàng)和a)後項(xiàng)（）內(nèi)最初項(xiàng) b)、次 c)、最後項(xiàng)和 d)條件対応。求U i 最悪時（本文表 11.1）上限下回時間制約満。rate monotonic 安定性保証、各 Ui 計算必要注意。判定失敗場合、一般化完了時間定理正確判定可能。上記條件考慮上、完了時間検討。定理図的図説明。実時間設(shè)計設(shè)計段階後、実時間理論一群並行対適用。（本書設(shè)計段階適用重點(diǎn)置。）設(shè)計段階 CPU 時間推定値注意。実時間厳時間制約、悲観的 CPU 利用率制限定理（最悪上限0.69

22、）信頼安全（実時間理論上限値上）。上限値満場合別方法探必要。悲観的設(shè)計者観點(diǎn)、 0.69 超利用率上限深刻時間制約（守深刻）受入。設(shè)計時優(yōu)先度決定問題：一般 rate monotonic 優(yōu)先度付用。rate monotonic 優(yōu)先度付定期簡単適応。非定期頻度推定、定期場合見上周期求優(yōu)先度、駆動側(cè)面考最高優(yōu)先度望。複數(shù)同一優(yōu)先度同一周期場合設(shè)計者決定下解決必要。一般重要優(yōu)先度上。一般化実時間定理適用例周期t1： C1=20;T1=100;U 1=0.2非定期t2： C2=15;T2=150;（最悪時） U 2=0.1割噫駆動ta： Ca=4;Ta=200;U a=0.02非定期定期t3： C

23、3=30;T3=300;U 3=0.1條件ta 200msec 以內(nèi)終取。t1、t2、t3 守同一?。切替各 CPU時間先頭含。優(yōu)先度厳密 rate monotonic 優(yōu)先度t 1、t2、t3 、ta 順。ta 関條件実際優(yōu)先度、ta、t1、t2、t3 順。解析CPU 利用率単純合計0.42 上限 0.69 下回、rate monotonic 優(yōu)先順位破個検討必要。t a ta 最高優(yōu)先度必要CPU 利用上、CPU 時間 0.02 必時間制約守。t 1a. 周期短先取時間：。b. 自身実行時間： 利用率 U1=0.2。c. 長周期高優(yōu)先度先取時間： t a 該當(dāng)。利用率 Ca/T 1=0.0

24、4。d. 低優(yōu)先度時間：t2、t3 可能性。優(yōu)先度打切従、実際高、最悪場合CPU 時間長 t 3 場合考。B3=C3 仮定利用率B3/T1=0.3。以上最悪場合利用率合計0.54 上限 0.69 下回、t1 時間制約守。t 2a. 周期短先取時間： t1 該當(dāng)。U1 =0.2。b. 自身実行時間： 利用率 U2=0.1。c. 長周期高優(yōu)先度先取時間： t a 該當(dāng)。利用率 Ca/T 2=0.03。d. 低優(yōu)先度時間：t3 可能性。B 3=C3 仮定利用率B3/T2=0.2。以上最悪場合利用率合計0.53 上限 0.69 下回、t2 時間制約守。t 3a. 周期短先取時間： t1 、t2 、ta該當(dāng)。U 1 +U 2 +U a=0.32。b. 自身実行時間： 利用率 U3=0.1。c. 長周期高優(yōu)先度先取時間： 。d. 低優(yōu)先度時間：。以上最悪場合利用率合計0.42 上限 0.69 下回、t2 時間制約守。以上 4 全時間制約守。実時間Ada 概念的、厳時間制約持