Modelování spolehlivost
Výkonnost a spolehlivost programových systémů – KIV/VSS
Richard Lipka 29.11.2016
Motivace
• Modely velmi obecné – Ne jen pro elektronické systémy – Založené na statistice – vždy jen pravděpodobnosti a rozdělení! (pravděpodobnost poruchy 0,1% neznamená že porucha nenastane) 29.11.2016
VSS - Spolehlivost
• Určení spolehlivosti nového HW – Jak dlouho vydrží CPU než se rozbije? – Vyplatí se připlatit si za prodloužení záruky? • Určení spolehlivosti HW složeného ze známých modulů – Jak dlouho vydrží fungovat směrovač / dron / satelit / … ? • Určení velikosti záloh – Kolik náhradních komponent potřebuji aby systém fungoval po zadanou dobu?
Základní úlohy • Měření spolehlivosti – Mám HW prvek / systém a potřebuji vědět jak často se s ním něco stane Podobný problém jako benchmarkování
• Zlepšování spolehlivost – Navrhuji nový systém a zjišťuji jak nastavit zálohy / vlastnosti abych dosáhl požadované spolehlivosti Založeno na modelových odhadech 29.11.2016
VSS - Spolehlivost
• Odhadování / předvídání spolehlivosti – Mám nový systém složený ze známých prvků a potřebuji odhadnout jak často se rozbije celý systém Analytické modely / simulace
Příklady selhání – HW i SW
29.11.2016
VSS - Spolehlivost
Přistávací modul EDM (Schiaparelli) (předběžná zpráva) • Přistávací manévr funguje jak má • Po aktivaci padáků selhává IMU (měření rotace a akcelerace) – Cca 1 sec je nad hranicí toho co dokáže měřit krátkodobý HW problém • Řídící systém usuzuje že sonda je pod úrovní terénu SW není dostatečně robustní ve 4 km sonda odhazuje padák a aktivuje brzdné trysky – Nestačí, určeny pro výšku cca 20 m
http://www.esa.int/Our_Activities/Space_Science/ExoMars/Schiaparelli_l anding_investigation_makes_progress
Příklady selhání – návrh SW
• Chyba téměř nezjistitelná testováním, kód je „dobře“ – Rychlým řešením je pravidelný restart (v manuálu byl) 29.11.2016
http://www.math.umn.edu/~arnold/disasters/patriot.html
VSS - Spolehlivost
Raketa Patriot • K sestřelování jiných raket, pokud letí kam má • Uplynulý čas počítán ve fixed point proměnné (je potřeba k výpočtům pohybu cíle) • Pokud běží dlouho, akumuluje se chyba (očekává se že běží jen pár minut) • Po 100 hodinách výpočtu zaokrouhlovací chyba 0,3433 𝑠 687 𝑚 rozdíl v poloze cíle (28 mrtvých)
Příklady selhání – souběhy
VSS - Spolehlivost
Therac 25 • Ozařovací přístroj pro léčbu rakoviny (1982) • Způsobuje předávkování (až 100x víc radiace popáleniny, rakovina) – Příliš rychlý operátor mohl spustit najednou Roentgen i elektronový paprsek větší ozáření (souběhové chyby) – Přetečení čítače vedlo ke spuštění jiné než plánované procedury
• Žádná indikace nastavení HW • Nedokumentovaná chybová hlášení, která šla ručně obejít
29.11.2016
http://users.csc.calpoly.edu/~csturner/courses/508/TheracPresentation.pdf
Příklady selhání – copy and paste
• Stejný SW v Ariane 4 vždy fungoval, proto převzat – Ariane 4 menší a pomalejší, pracoval s čísly co se ještě vešly
29.11.2016
http://www.math.umn.edu/~arnold/disasters/ariane5rep.html
VSS - Spolehlivost
Ariane 5 • Exploze prvního nosiče 40 s po startu • Všechny řídící systémy dvojmo (identický SW) • Přiřazení float integer vedlo k výjimce (hodnota aktuální rychlosti se nevešla) – Výjimka neodchycena, řídící počítač selhal
Definice spolehlivosti
• Norma velmi obecná (a placená – dá se stáhnout v knihovně) – Specifické normy pro různé oblasti (automobilový průmysl, vlaky, …)
• Obvykle multikriteriální problém – zavádějí se „ukazatele spolehlivosti“ které se dají kvantifikovat 29.11.2016
VSS - Spolehlivost
„Obecná vlastnost objektu spočívající ve schopnosti plnit požadované funkce při zachování hodnot stanovených provozních ukazatelů v daných mezích a v čase podle stanovených technických podmínek“ ČSN 010102 (Od roku 1993)
Spolehlivostní normy
29.11.2016
VSS - Spolehlivost
• IEEE 1633 – 2008 (Recommended Practice on Software Reliability) – Analýza a sledování SW procesu – Predikce spolehlivosti SW na základě dat měřených při vývoji SW, testování i po nasazení • CENELEC EN-50128, IEC 62279, IEC 61508 – Normy pro drážní řídící systémy (bezpečnost a spolehlivost řídících systémů) – Např. programy s cyklomatickou složitostí 1, žádné metody AI, … • MISRA-C – Podmnožina jazyka C a sada pravidel pro vývoj SW do automobilů – např. povinné deklarace proměnných, omezení použití ukazatelů (pointerová aritmetika jen pro pole, omezení pointerů na funkce, …), …
Spolehlivostní normy • MIL-HDBK-217x (poslední F – notice 2)
• Hradla, paměti, relé, různé typy komponent a obvodů • Koeficienty a odhady pro použití na zemi a ve vzduchu
– Založena na nasbíraných datech a měřeních 29.11.2016
VSS - Spolehlivost
– Vojenská příručka, dá se stáhnout (http://snebulos.mit.edu/projects/reference/MIL-STD/MILHDBK-217F-Notice2.pdf) – Výrazně orientována na HW – Konkrétní modely a tabulky pro různé prvky
Spolehlivostní normy • MIL-HDBK-217x (poslední F – notice 2) VSS - Spolehlivost
29.11.2016
Spolehlivostní normy • MIL-HDBK-217x (poslední F – notice 2) VSS - Spolehlivost
29.11.2016
Spolehlivostní normy • MIL-HDBK-217x (poslední F – notice 2) VSS - Spolehlivost
29.11.2016
Základní pojmy
29.11.2016
VSS - Spolehlivost
• Poruchy: – Systematické – chyby v návrhu systému (zapomenuté kontroly, chyby operátora, přehřívání, …) – v SW – Náhodné – vnější vlivy mimo kontrolu (nárazy, počasí, radiace, …) – v HW • Stavy: – Bezporuchový – systém normálně funguje – Poruchový – systém neposkytuje požadovanou službu (dokážu ho detekovat?) • Systémy: – Obnovované – mohu je nějak opravit – Neobnovované – po poruše jsou zničeny (neopravitelný HW, nedostupný systém, příliš nákladné, …)
Klasifikace chyb • Vznik a propagace chyby (různé terminologie) – Mistake – chyba operátora – Fault – domnělá příčina chyby (vnější vlivy, chyba v návrhu systému, …)
– Error – rozdíl mezi správným a získaným výsledkem – Failure – selhání systému – nedodržení specifikace
• Podle trvání – Stálé (permanent) – systém přestane fungovat – Přechodné (transient) – jednorázové selhání (zpráva nedorazí) – Opakující se (intermintent) – opakovaně se objevují a mizí 29.11.2016
VSS - Spolehlivost
• Bizantine fault – nevede k detekci selhání ale ke špatnému výsledku
Kategorie spolehlivosti • Nezabezpečené systémy – fault avoidance – „dělám vše co nejlépe“
– po poruše přepnutí do bezpečného stavu – Řízení křižovatky, drážní provoz, …
• Systémy odolné proti poruchám – fail tolerant – Neexistuje bezpečný stav porucha „nesmí nastat“ – Řídící systémy letadla, zabezpečení letového provozu 29.11.2016
VSS - Spolehlivost
• Zabezpečené systémy – fail safe
Zajištění odolnosti proti poruchám • Spolehlivostní normy
• Redundance – Obvodová (HW navíc) • Statická / horká záloha • Dynamická / studená záloha
– Programová (SW navíc) • Dva týmy, 2 jazyky a stejný SW
– Informační (data navíc) • Opakování zpráv
– Časová (čas navíc) • Opakování výpočtů
29.11.2016
VSS - Spolehlivost
– Sledování vývoje systému – Formální metody dokazování spolehlivosti (Java Pathfinder) – Automatické převody modelu na software (na modelu lze lépe dokazovat správnost)
Redundace • Bezpečnost výměnou za větší cenu (finanční, energetickou, prostorovou, …) – Ne vždy je možná
– Studená (cold) – záloha vypnutá, po výpadku se aktivuje – Teplá (warm) – záloha zapnutá ale neaktivní, po výpadku začne zpracovávat vstup – Horká (hot) – záloha běží paralelně s hlavním výpočtem 29.11.2016
VSS - Spolehlivost
• Dva (tři) základní typy záloh
Předpoklady využití záloh • Dokážu detekovat problém – Autodetekce uvnitř modulu – pozná že nefunguje (riziko byzantinských chyb – co když je selhání v této části?) – Detekce (horkou) zálohou
• Systémy lze přepnout – Potřebuji zajistit připojení periferií – další redundance – HW pro provedení vlastního přepnutí (může se porouchat) – V ukázkových případech většinou zanedbáno, ale má další vliv na spolehlivost (další prvky které se mohou rozbít)
29.11.2016
VSS - Spolehlivost
• 1 ze 2 – detekuji že něco je špatně • 2 ze 3 – detekuji kde jde chyba
Vlastnosti záloh Horká • Může sloužit jako detekce chyb • Aktivní celou dobu – může kdykoliv převzít řízení • Spotřebovává zdroje • Může se rozbít dřív než na ni dojde (pokud je odlišena)
Delší doba do celkového selhání, občasné výpadky
Celkové selhání přijde dřív, ale bez výpadků 29.11.2016
VSS - Spolehlivost
Studená • Potřebuje detekci chyb • Potřebuje dobu na aktivaci (po nějakou dobu nic nefunguje) • Neopotřebovává se • Nespotřebovává zdroje
Horká záloha – vlakový zastavovač Opakování výpočtu
• Náročné prostředí výpočet v CPU selhává • Několik jednotek, hlasují
Zpracování vstupu
1
1
1
1
Porovnání výsledků Řízení
29.11.2016
– Při souladu většiny výpočet použit (pravděpodobnost stejné chyby zanedbatelná) – Lze nastavit práh pro opakování výpočtu
VSS - Spolehlivost
1
Vstup z okolí
Ukazatele spolehlivosti 1
29.11.2016
VSS - Spolehlivost
• MTTF – střední doba do poruchy (v modelech často intenzita 𝜆 = ) 𝑀𝑇𝑇𝐹 – za jak dlouho se zapnutý systém rozbije • MTBF – střední doba mezi poruchami – jak často dochází k výpadkům 1 • MTTR – střední doba do opravy (v modelech často intenzita 𝜇 = ) 𝑀𝑇𝑇𝑅 – jak dlouho mi zabere celé to znovu spustit
Ukazatele spolehlivosti • Zaměřené na náhodné poruchy Obvykle chápány jako náhodné veličiny • Popis distribuční funkcí (nebo známým rozdělením) VSS - Spolehlivost
Pro zopakování: Veličina 𝜏, (𝜏 > 0), lze najít 𝐹 𝑡 𝐹𝜏 𝑡 = 𝑃(𝜏 < 𝑡), kde 𝑃(𝑎) je pravděpodobnost jevu 𝑎 a 𝑡≥0
29.11.2016
Ukazatele spolehlivosti – neobnovované objekty – Doba od zapnutí do porouchání 𝜏
• Distribuční funkce 𝑄(𝑡)
• Doplňková funkce do 1: 𝑅 𝑡 = 1 − 𝑄(𝑡) – pravděpodobnost bezporuchového stavu
• Hustota pravděpodobnosti 𝑓 𝑡 =
𝑑𝑄(𝑡) 𝑑𝑡
– hustota poruch – Prvd. poruchy v intervalu 𝑑𝑡 od času 𝑡 = 𝑓 𝑡 ∙ 𝑑𝑡 29.11.2016
VSS - Spolehlivost
– pravděpodobnost poruchy
Ukazatele spolehlivosti – neobnovované objekty • Poměr λ 𝑡 =
𝑓(𝑡) 𝑅(𝑡)
=
𝑓(𝑡) 1−𝑄(𝑡)
• Podmíněná pravděpodobnost – Pravděpodobnost že objekt bude v čase 𝑡 + 𝑑𝑡 porouchaný za předpokladu že před tím (v čase 𝑡) byl v pořádku - λ 𝑡 𝑑𝑡 29.11.2016
VSS - Spolehlivost
– intenzita poruch (není to pravděpodobnosti – může přesáhnout 1)
Exponencialita Intenzita poruch Intenzita poruch
6 4
𝑡2
𝑡1
2 0
0
2
4
6
8
10
12
Čas
𝑡
𝑅 𝑡 =𝑒
− 0 λ 𝜏 𝑑𝜏
Pro konstantní λ: 𝑡
− 0 λ𝑑𝜏
𝑅 𝑡 =𝑒 = 𝑒 −λ𝑡 𝑄 𝑡 = 1 − 𝑒 −λ𝑡 𝑓 𝑡 = 1 − 𝑒 −λ𝑡 ′ = λ𝑒 −λ𝑡
•
Empiricky zjištěná „vanová křivka“ – Po nějakou dobu lze λ považovat za konstantu, 𝑡1 a 𝑡2 obvykle zjištěny experimentálně (konstantní hodnotu nepřevádět na čas) – 𝑄 𝑡 - distribuční funkce exponenciálního rozdělení – 𝑓 𝑡 - hustota pravděpodobnosti exponenciálního rozdělení 29.11.2016
VSS - Spolehlivost
𝑑𝑅 𝑡 𝑑𝑡 𝑑𝑅(𝑡) 1 λ 𝑡 =− ∙ 𝑑𝑡 𝑅(𝑡) 𝑑𝑅(𝑡) −λ 𝑡 𝑑𝑡 = 𝑅(𝑡) 𝑓 𝑡 =−
Intenzita poruch
29.11.2016
VSS - Spolehlivost
• Pro další výpočty očekáváme konstantní λ – Pro integrované obvody někde mezi 10−8 1 ℎ − 10−5 1 ℎ, obvykle nižší pro paměťové obvody než pro logické obvody (empiricky zjištěno) • Modely v MIL-HDBK-217 ve stylu λ = (𝐶1 𝜋 𝑇 + 𝐶2 𝜋𝐸 ) 𝜋𝑄 𝜋𝐿 (sekce 5.1 – logický obvod) – 𝐶1 - koeficient podle počtu hradel – 𝐶2 - přibližný počet vývodů – 𝜋 𝑇 - vliv teploty (teplotních rozdílů), tabulka podle teploty a typu zařízení – 𝜋𝑄 - vliv kvality (norma podle které bylo zařízení vyrobeno) – 𝜋𝐿 - vliv stáří návrhu (čím starší tím spolehlivější) – 𝜋𝐸 - vliv okolních podmínek (příručka obsahuje tabulky s hodnotami)
Ukazatele spolehlivosti – neobnovované objekty • 𝑇𝑠 =
∞ 𝑅 0
𝑡 𝑑𝑡
λ
• Pozor, jen pro konstantní λ! potřebuji znát i 𝑡1 a 𝑡2
29.11.2016
VSS - Spolehlivost
– Střední hodnota náhodné veličiny - střední doba do první poruchy (MTTF) – Pro exponenciální rozdělení ∞ −λ𝑡 1 𝑇𝑆 = 0 𝑒 𝑑𝑡 = (očekávatelné )
Ukazatele spolehlivosti – obnovované objekty •
Dochází k přechodům mezi bezchybným a chybovým stavem (poruchy a opravy)
𝐴1 𝜏𝑝1
𝜏𝑝2
𝜏𝑜1 𝑝
𝑡1𝑜
𝑡1
𝑝
𝑡2
• MTTF lze určit jako střední hodnotu 𝜏𝑝𝑖 𝑡𝑝 1 𝑇𝑆 = = 𝑛 𝑛
𝑡2𝑜
𝜏𝑝4
𝜏𝑜3 𝑝
𝑡3
𝑡3𝑜
• Podobně i MTBF (střední doba cyklu) 𝑡 1 𝑇𝐶 = = 𝑛 𝑛
𝑛
𝑖=1
𝜏𝑝3
𝜏𝑜2
𝜏𝑝𝑖 29.11.2016
𝑛
(𝜏𝑝𝑖 + 𝜏𝑜𝑖 )
𝑖=1
VSS - Spolehlivost
𝐴0
Ukazatele spolehlivosti – obnovované objekty 𝐴1 𝜏𝑝1
𝐴0
𝜏𝑝2
𝜏𝑜1 𝑝
𝑡1𝑜
𝑝
𝑡2
𝑡2𝑜
𝜏𝑝4
𝜏𝑜3 𝑝
𝑡3
𝑡3𝑜
• Pravděpodobnost že bude v čase 𝑡 v provozuschopném stavu 𝐾𝑝 (𝑡) – 𝐾𝑝 = lim 𝐾𝑝 (𝑡) - stacionární součinitel pohotovosti (prvd. že systém bude 𝑡→∞ fungovat v libovolné době) – 𝐾𝑝 =
𝑡𝑝
𝑡𝑝 +𝑡𝑜
=
𝑛 𝑖=1 𝜏𝑝𝑖
𝑛 (𝜏 +𝜏 ) 𝑜𝑖 𝑖=1 𝑝𝑖
29.11.2016
VSS - Spolehlivost
𝑡1
𝜏𝑝3
𝜏𝑜2
Ukazatele spolehlivosti – obnovované objekty 𝐴1 𝜏𝑝1
𝐴0
𝑝
•
MTTR lze zavést jako 𝑇𝑜 =
𝜏𝑝3
𝜏𝑜2 𝑝
𝑡2
𝑡𝑜 𝑛
𝑡2𝑜
𝑝
𝑡3𝑜
𝑡3
1
– Pokud je náhodná s exponenciálním rozdělením lze také jako 𝑇𝑜 = 𝜇
Stacionární součinitel pohotovosti 𝑇
𝜇
𝑠 – 𝐾𝑝 = 𝑇 +𝑇 = λ+𝜇 𝑠
•
𝑞
Součinitel prostoje – doplněk do jedné (prvd. nedostupnosti systému) – 𝐾𝑛 𝑡 = 1 − 𝐾𝑝 (𝑡),
𝐾𝑛 = lim 𝐾𝑛 (𝑡) 𝑡→∞
29.11.2016
𝜏𝑝4
𝜏𝑜3
VSS - Spolehlivost
𝑡1𝑜
𝑡1
•
𝜏𝑝2
𝜏𝑜1
Systémy s nezávislými prvky
pak lze poruchy chápat jako nezávislé náhodné jevy
• Typické pro neobnovované systémy – Oprava podmíněna předchozí poruchou • Spojení prvků – logické, z hlediska spolehlivosti (nemusí být kopie reálného zapojení obvodu) 29.11.2016
VSS - Spolehlivost
• Systém složený z více prvků se známými vlastnostmi (hradla, CPU a RAM, počítače, … - podle úrovně modelu) • Poruchy jednotlivých prvků mohou být nezávislé – CPU se rozbije bez ohledu na to že je rozbitá paměť – Pozor, některé poruchy mohou podmínit vznik jiné poruchy, pak nelze mluvit o nezávislosti
Sériové zapojení 𝐴1
•
𝐴𝑛
Porucha jednoho prvku rozbije celý systém – Musíme znát 𝑅𝑖 𝑡 pro každý prvek („pravděpodobnost fungování“) Typicky pro výpočet spolehlivosti logického obvodu při znalosti jeho hradel (musí fungovat všechna) 𝑛 𝑖=1 𝑅𝑖 (𝑡) 𝑛 −λ𝑖 𝑡 𝑖=1 𝑒 1 1 = 𝑛 λ 𝑖=1 λ𝑖
𝑅 𝑡 = 𝑅 𝑡 = 𝑇𝑠 =
, respektive pro konstantní λ = 𝑒 −λ𝑡 , kde λ = 𝑛𝑖=1 λ𝑖 1
pokud mají prvky stejnou intenzitu poruch 𝑇𝑠 = 𝑛λ 29.11.2016
𝑝
VSS - Spolehlivost
•
𝐴2
Paralelní zapojení 𝐴1
𝐴𝑛
𝑛
𝑄 𝑡 = 𝑖=1
𝑄𝑖 (𝑡)
𝑅 𝑡 =1−𝑄 𝑡 =1−
𝑛
(1 − 𝑅𝑖 (𝑡))
𝑖=1
29.11.2016
VSS - Spolehlivost
• Porucha všech prvků rozbije celý systém (stačí aby jeden fungoval) – Potřebuji znát 𝑄𝑖 (𝑡) („pravděpodobnost poruchy“) pro každý prvek – Modelování horké zálohy (všechny prvky fungují zároveň ale stačí mi jen jeden)
Kombinované modely 𝐴2 , λ2 𝐴1 , λ1
𝐴3 , λ3
Typický příklad, jednotlivé části systému lze řešit odděleně Pro určení 𝑇𝑠 celého systému: – Analyzuji paralelní spojení 𝑄23 = 𝑄2 𝑄3 = 1 − 𝑅2 1 − 𝑅3 = 1 − 𝑅2 − 𝑅3 + 𝑅2 𝑅3 𝑅23 = 1 − 𝑄23 = 𝑅2 + 𝑅3 − 𝑅2 𝑅3 – Analyzují sériové spojení 𝑅 = 𝑅1 𝑅23 = 𝑅1 𝑅2 + 𝑅1 𝑅3 − 𝑅1 𝑅2 𝑅3 29.11.2016
VSS - Spolehlivost
• •
Kombinované modely 𝐴2 , λ2 𝐴1 , λ1
𝐴3 , λ3
𝑅 𝑡 = 𝑒 −(λ1 +λ2 )𝑡 + 𝑒 −(λ1 +λ3 )𝑡 − 𝑒 − ∞
𝑇𝑠 = 0
λ1 +λ2 +λ3 𝑡
1 1 1 𝑅 𝑡 𝑑𝑡 = + + λ1 + λ2 λ1 + λ3 λ1 + λ2 + λ3 29.11.2016
VSS - Spolehlivost
– Pro exponenciální doby poruch 𝑅𝑖 𝑡 = 𝑒 −λ𝑖 𝑡
Stavový graf • Složený model
• Potřebuji znát (obvykle empiricky zjistit) pravděpodobnosti jednotlivých stavů 𝑝𝑖 (𝑡) – Nezávislé, vzájemně se vylučující náhodné jevy – 𝑅 𝑡 = 𝑖 𝑝𝑖 (𝑡), 𝑖 přes všechny provozuschopné stavy
• Pro model situací které nelze převést na sériové ani paralelní spojení 29.11.2016
VSS - Spolehlivost
– může být v různých provozních a různých poruchových stavech – 𝑛 prvků označených 𝐴𝑛 , každý může být v provozu nebo porouchaný – přechod – 1 porucha nebo 1 oprava
Stavový graf - příklad • 3 prvky 𝐴1 , 𝐴2 , 𝐴3 , potřebuji aby fungovaly kterékoliv 2 z nich (je mi jedno které)
• • •
100
101
010
011
001
000
Neobnovované všechny přechody jsou poruchy Stav kóduje dílčí poruchy Pokud známe 𝑅𝑖 (𝑡) a 𝑄𝑖 (𝑡) jednotlivých prvků, lze určit celkové 𝑅(𝑡)
29.11.2016
VSS - Spolehlivost
111
110
Stavový graf - příklad 111
100
101
010
011
001
000
𝑅 = 𝑅1 𝑅2 𝑅3 + 𝑅1 𝑅2 𝑄3 + 𝑅1 𝑄2 𝑅3 + 𝑄1 𝑅2 𝑅3 = 𝑅1 𝑅2 𝑅3 + 𝑅1 𝑅2 (1 − 𝑅3 ) + 𝑅1 (1 − 𝑅2 )𝑅3 + (1 − 𝑅1 )𝑅2 𝑅3 = 𝑅1 𝑅2 + 𝑅1 𝑅3 + 𝑅2 𝑅3 − 2𝑅1 𝑅2 𝑅3
• Za R lze opět dosadit odpovídající distribuční funkci (obvykle exponenciální rozdělení) 29.11.2016
VSS - Spolehlivost
110
Strom poruch (Fault tree) • Klasický model založený na množině událostí (obvykle poruch) které se se systémem mohou stát • Logická funkce (určují boolovskou hodnotu následující události) • Aritmetická funkce (určují pravděpodobnostní úroveň následující události)
• • • •
Model lze přehledně znázornit stromem událostí Lze snadno zjemňovat přidáváním dalších úrovní detailů Podstromy lze řešit odděleně Pro konstantní intenzity základních událostí lze převést na Markovský model lze použít existující solvery 29.11.2016
VSS - Spolehlivost
– Znám události a jejich pravděpodobnosti (funkce v čase / konstanty) – Zadány operátory („hradla“ – obvykle AND a OR)
Strom poruch - příklad 𝑓 – porucha systému 𝑓1 - porucha CPU 𝑓2 - ztráta napájení 𝑓3 - porucha RAM 𝑓21 - porucha záložní baterie 𝑓22 - ztráta napájení hlavního zdroje • 𝑓221 - omylem vytažený kabel ze zásuvky (prvd. 0,00002) 29.11.2016
𝑓 OR 𝑓1
𝑓2
𝑓3
AND 𝑓21
𝑓22
𝑓221
VSS - Spolehlivost
• • • • • •
Strom poruch - hradla • Pro nezávislé události: – AND: 𝑃 𝐴 𝑎𝑛𝑑 𝐵 = 𝑃 𝐴 𝑃(𝐵) – OR: 𝑃 𝐴 𝑜𝑟 𝐵 = 𝑃 𝐴 + 𝑃 𝐵 − 𝑃 𝐴 𝑃(𝐵) – XOR: 𝑃 𝐴 𝑥𝑜𝑟 𝐵 = 𝑃 𝐴 + 𝑃 𝐵 − 2𝑃 𝐴 𝑃(𝐵)
• Strom sestaven pro každou nežádoucí událost zvlášť – Analýza shora dolů – vím jak vypadá porucha a hledám co k ní může vést 29.11.2016
VSS - Spolehlivost
• 𝑃 𝐴 𝑃 𝐵 → 0 pro velmi malé 𝑃 𝐴 , 𝑃 𝐵
Systémy se závislými událostmi • Studená záloha vs. horká záloha
• Opravy – Opravuji až po tom co se něco rozbilo
Markovské modely (stav systému závislý na předchozím stavu) • Potřebuji konstantní intenzity poruch (λ) a oprav (𝜇) • Předpokládám exponenciální rozložení dob poruch i oprav 29.11.2016
VSS - Spolehlivost
– Poruchy horké zálohy nezávislé – Studená záloha se může porouchat až po zapnutí její porucha závislá na poruše primárního systému
Markovské modely - neobnovované • Model s absorpčními stavy
• Řešení soustavy lineárních diferenciálních rovnic – neexistují ustálené pravděpodobnosti (viz druhá přednáška)
29.11.2016
VSS - Spolehlivost
– Po poruše se už systém nevrátí do provozuschopného stavu acyklický graf markovského procesu
Markovský model bez diferenciálních rovnic 𝐴2
𝐴1′
𝐴′2
λ2
3.
λ1
2
1
λ1
4.
λ2 4
λ1 + λ2
5
λ1 λ2
1. 2.
3
λ2 29.11.2016
5.
Vše v pořádku Modul 𝐴1 nahrazen zálohou Modul 𝐴2 nahrazen zálohou Oba moduly nahrazeny zálohou Systém je nefunkční
VSS - Spolehlivost
𝐴1 λ1
Stavy modelu:
Markovský model bez diferenciálních rovnic 𝐴1 λ1
𝐴2
𝐴1′
𝐴′2
λ2
2 λ2
1
4
λ1 λ1 + λ2
5
λ1 λ2
3
λ2 29.11.2016
• Nalezení všech cest z 1 do 5 (4 možnosti) • Určení dílčích 𝑇𝑐𝑖 (dob trvání cesty) a jejich pravděpodobností 𝑝𝑐𝑖 • 𝑇𝑠 = 4𝑖=1 𝑇𝑐𝑖 𝑝𝑐𝑖 - vážený průměr jejich délek
VSS - Spolehlivost
λ1
Určení 𝑇𝑠 (střední doby provozu):
Markovský model bez diferenciálních rovnic λ1
2 λ2
4
λ1 + λ2
λ1
λ2
3
λ2
Střední doba setrvání ve stavu: 1 𝑇𝑖 = 𝑜𝑑𝑐ℎ𝑜𝑧í λ Pravděpodobnost přechodu 𝑝𝑖𝑗 = 𝑇𝑖 λ𝑖
Určení 𝑇𝑐1 pro cestu 1-2-4-5: 5
1 1 1 𝑇𝑐1 = + + λ1 + λ2 λ1 + λ2 λ1 + λ2 λ1 λ2 λ1 + λ2 𝑝𝑐1 = ∙ ∙ λ1 + λ2 λ1 + λ2 λ1 + λ2
29.11.2016
VSS - Spolehlivost
1
λ1
Markovské modely – obnovované • Grafy obsahují cykly
• Místo diferenciálních rovnic dostanu lineární
• „availability models“ (místo „reliability models“) • Koeficienty lze určit na základě analýzy pravděpodobnosti stavů modelu 29.11.2016
VSS - Spolehlivost
– Poruchy jedním směrem, opravy druhým – Stále mohou obsahovat absorbční stavy (něco opravit nejde) – Model pro nekonečně dlouhou dobu života pokud jde vše opravit, lze pracovat s ustálenými pravděpodobnostmi
Příklad bez absorbčních stavů • 2 moduly, stačí mi jeden
1
2λ𝑝1 = 𝜇𝑝2 2λ𝑝1 + 2𝜇𝑝2 = (λ + μ)𝑝1 λ𝑝2 = 2𝜇𝑝3 𝑝1 + 𝑝2 + 𝑝3 = 1
2λ
𝜇
2 2𝜇
λ
𝐾𝑝 = 𝑝1 + 𝑝2 𝑝1 + 𝑝2 𝑇𝑠 = λ 𝑝2
3 29.11.2016
VSS - Spolehlivost
– Mohu opravovat jeden nebo oba zároveň (neomezená kapacita oprav) – Intenzita poruch λ, intenzita oprav 𝜇
Využití simulací Pro složité systémy (podobně jako u sítí front) Lze zachytit libovolnou logiku zapojení modulů, pravidla pro aktivace záloh i pro fungování oprav Výpočetní složitost úměrná počtu prvků
•
Simulační pokus: – – – – –
Systém se 2 prvky, každý má studenou zálohu a obecnou (ne exponenciální) hustotu poruch Chci vědět jestli se systém porouchá do času 𝑡 Generuji 4 čísla – dobu do poruch obou modulů i jejich záloh (𝜏1 ,𝜏1′ , 𝜏2 ,𝜏2′ ) Doba do poruchy:𝜏𝑠𝑖 = 𝑚𝑖𝑛 𝜏1 + 𝜏1′ , 𝜏2 + 𝜏2′ Pokud 𝜏𝑠𝑖 < 𝑡 inkrementuji čítač 𝐾, vždy inkrementuji celkovou dobu 𝑆 = 𝑆 + 𝜏𝑠𝑖 𝐴1 𝐴2 – Opakuji 𝑁 krát – dostatečný počet pokusů! 𝑆
𝐾
𝑇𝑠 ≅ 𝑁, 𝑃 𝜏𝑠𝑖 < 𝑡 ≅ 𝑁 𝐴1′ 29.11.2016
𝐴′2
VSS - Spolehlivost
• • •
Spolehlivý software • •
Modelování řádově obtížnější než u HW – Příliš složitá primitiva, příliš komplexní struktury Spolehlivostní normy zaměřené na
• Důraz na dokumentaci rozhodnutí sledovatelnost vývoje, pochopení důvodů problémů
– Formální modely • Lze dokazovat jejich správnost a následně generovat program
• •
Code review zkušenými programátory Důkladné testování Celkem vzato viz ASWI, ZSWI, OKS – už znáte
29.11.2016
VSS - Spolehlivost
– Metriky (řádky kódu, cyklomatická složitost, Halsteadova složitost, pokrytí testy, hustota komentářů, parametry na metodu, proměnné na metodu, provázanost, …) – Metodika práce (raději RUP než SCRUM)
Námitky a kritika •
Metriky – Poznám kdy SW nefunguje lze hledat korelace s hodnotou metriky (ne vždy najdu, korelace není kauzalita) metriky oblíbené v akademické obci (je co měřit) metriky (někdy) oblíbené u managementu (je jak hodnotit)
•
Pokrytí testy – 100% pokrytí ≠ 100% spolehlivost Metodiky práce – Zásadní pro státní zakázky, zakázky z některých druhů průmyslu (zákon) – Papír snese ledacos – jsou dodržené opravdu?
•
Formální metody – Fungují celkem dobře pro některé typy problémů – Obecně příliš výpočetně složité
29.11.2016
VSS - Spolehlivost
•
W. E. Deming „zakladatel hodnocení kvality“ Řízení kvality v japonském průmyslu 1950 – 1960 Výrazné zlepšení pozice Fordu v 70. letech
•
14 zásadních bodů (viz Internet )
VSS - Spolehlivost
• •
3. - Zbavte se kontrol kvality a zabudujte ji do produktu 9. – zbavte se hranic mezi odděleními, vývoj, návrh, výroba a prodej musí spolupracovat 10. – zbavte se proklamací, výzev, sloganů a podobných věcí na pracovišti; zbavte se číselných norem a vedení na základě čísel 12. – zbavte se výročních hodnocení a hodnocení podle dosažených číselných cílů
•
Celkově zaměřené na přesvědčování lidí aby dělali věci zodpovědně a dobře, protože kontrolní mechanismy stejně nefungují – Lidé se přizpůsobí a naplní metriky tak aby vyšly co nejlépe, ne aby skutečně zlepšily stav věcí
29.11.2016
W. E. Deming (1900 - 1993)
Komunikace se zákazníky • Je lepší problémy neskrývat a nebagatelizovat – Viz Intel a FDIV bug (1994) • Chyba v dělení, šance na výskyt 1 : 9 000 000 000 • Intel o ní věděl, po odhalení přesvědčoval že „o nic nejde“
• Snaha dopátrat se příčiny může vést k dalším potížím – dotčení hledají co se děje
• Empirické studie ukazují že (odhadem) – Je 5x dražší sehnat nového zákazníka než udržet stávajícího • Cena oprav a požadovaných úprav a ladění nad rámec dohodnuté smlouvy • Ne vždy funguje „vendor lock“ (SAP)
– Nespokojený zákazník řekne o problému 7 lidem z 20 • A navíc po sociálních sítích se katastrofy šíří lépe a rychleji
– Spokojený zákazník 3 lidem z 20 29.11.2016
VSS - Spolehlivost
– Problémy výpadku vzdálených služeb
Výkon software • Obtížně měřitelný – Lze měřit jak dlouho co trvá – Není jak zjistit jak dlouho by to mohlo trvat optimálně
• Lidé rádi věří že mají na věci vliv hledají chyby tam kde je mohou snáz napravit
• Velmi často lze zlepšit jeden parametr na úkor jiného 29.11.2016
VSS - Spolehlivost
• Pro algoritmy koncept složitosti – Lineární, kvadratická, … – Obtížné určit pro celý systém – Ne vždy jsou „algoritmy“ hlavní problém
Výkon SW „Něco za něco“
•
Čas vs Paměť – Nahradím data výpočtem / výpočet daty
•
Výkon vs Cena – Zaplatím vývoj lepších algoritmů, využiji hotové obecné frameworky
Spolehlivost vs Cena – Důkladnější ladění, vydání nehotové verze (alfa verze na steamu – zaplatím si za to být tester)
• Merge sort
• Radix sort (cca 1885?)
– Časová složitost 𝑂 𝑁 ∙ 𝑙𝑜𝑔 𝑁 – Paměťová náročnost 𝑁 + 1
29.11.2016
– Časová složitost přibližně 𝑂 𝑁 – Paměťová složitost až 𝑁 ∙ 𝑤 , 𝑤 počet znaků / přihrádek – Nepotřebuje porovnání dvou prvků
VSS - Spolehlivost
•
Sledování aplikace • Řada problémů se objeví jen v produkčním prostředí
• Hlášení o výjimce velmi často nevede ke skutečné příčině
– Uživatel není tester (obvykle) snažit se testovat při zátěži
• Manuální zpracování logů náročné – Vybrat si vhodný nástroj (Splunk, Stash, Sumo Logic)
29.11.2016
VSS - Spolehlivost
– Mít možnost sledovat aplikaci online (Jconsole, JMC, …) – Alespoň logování pokud nelze sledovat (hodí se logování v paměti – posledních x zpráv s největší úrovní podrobnosti – menší overhead)
Frameworky a výkon • Obecné frameworky
• Typicky ORM, serializace dat, obecné cache frameworky, …
29.11.2016
Cca 200 metod pro zápis 1 řádku do DB (de facto převod jednoho Stringu na jiný)
VSS - Spolehlivost
– Výrazně šetří čas programátorů – Odladěné a spolehlivé, udržované třetí stranou – Obecné dělají věcí složitěji než je nutné (využití reflexe, čtení konfigurací, …)
Příklad: webový server „EET“ • REST API pro příjem dat dostane JSON text • GSON / Jackson / JSONP převede data mám doménové objekty • Hibernate / OJB / XORM generuje SQL získám SQL stringy • SQL odesláno do DB (cesta zpět obdobná)
DB a výkon – četné dotazy
• Počítat počty požadavků na DB a počty transakcí (užitečných operací) v aplikaci
29.11.2016
VSS - Spolehlivost
• Příliš přístupů do DB najednou – při ruční práci s DB: – SELECT id FROM table WHERE … – SELECT * FROM table WHERE id = ? • Při použití ORM (Hibernate) eager a lazy načítání – Eager – čtu data co nejdříve (např. včetně závislých objektů) méně složitých dotazů, přenáší ihned více dat – Lazy – čtu data až když je potřebuji více jednoduchých dotazů, přenáší méně dat Potřebuji vědět jak budou data využívána
DB a výkon - cache •
Je rychlejší číst data z paměti než ze vzdálené DB – Žádná cache jen pokud je pro to dobrý důvod – Cache musí mít maximální velikost (jinak riskuji že se do ní nastěhuje celá DB a objeví se OutOfMemoryException)
•
Data pro cache serializovatelná
•
Distribuovaná cache složitá – Je nutné řešit konzistenci – Je přípustné aby nějaký uzel měl jiná data než ostatní? – Za udržení konzistence platím ztrátou výkonu
29.11.2016
VSS - Spolehlivost
• Nastavení velikosti empirické – sledování aplikace při zátěži • Měření poměrů úspěšných čtení (hit) a dotazů do DB (miss) (velikost cache tak abych využil dostupnou paměť s co nejlepším hit poměrem) • Strategie pro odstraňování objektů („levná“ – rychlá, přizpůsobená úloze) • Při správném nastavení nevzrůstá zátěž DB se zátěží aplikace – data v cache
DB a výkon - pooling
• Měření – kde transakce čekají – Čekají na připojení nejspíš příliš malý pool připojení – Čekají na výsledek dotazu přetížená DB, nejspíš moc připojení najednou (projev „zvenku“ vždy stejný – aplikace zpomalí měření v aplikaci nebo profilerem) • Podobný přístup pro obslužná vlákna – pool vláken (často není potřeba nechat běžet víc vláken než je jader) 29.11.2016
VSS - Spolehlivost
• Nejdražší operace – tvorba nového připojení – tvorba všech připojení hned při startu aplikace – V aplikaci lze řídit kolik spojení existuje DB je neodmítá server si drží pool hotových připojení – Je třeba ho vhodně dimenzovat
DB a výkon – složité dotazy
• Slučovat tabulky tříd při ORM – Šetřím JOINy – Ve skutečnosti ani neplýtvám daty – DB stejně velká (záznamy v „nadřízených“ tabulkách obvykle nejde smysluplně sloučit) 29.11.2016
Prapředek
Předek
Potomek
VSS - Spolehlivost
• SELECT nezabere tolik času jako jakýkoliv JOIN (= kartézský součin) – Vhodně navrhnout strukturu tabulek a dotazy – Relační databáze se rozšířily dřív než OOP (OOP o něco starší) nejsou „vhodný model“ pro ORM
DB a výkon - indexy •
!!! Index není jen primární/cizí klíč !!! – Bohužel v DP to tak často vypadá
29.11.2016
VSS - Spolehlivost
• Při návrhu nemusí být jasné kde a jaké indexy tvořit Sledovat využívání databáze • Indexy mají režii nedělat je tam kde nejsou potřeba – Výrazně urychlí hledání (bez indexu sekvenční!) – Zpomalí vkládání nových dat (řazení do indexů – B stromů) • Index může být obvykle nad více sloupci – Podle toho jak vypadají dotazy • Při velké změně DB (import dat) lze index vypnout / zrušit a vybudovat znovu po dokončení transakce
Timeouty • Server bez timeoutů vyčerpává zdroje – Zhoršuje se dostupnost pro funkční klienty / server zcela zablokován
29.11.2016
VSS - Spolehlivost
• Příklad – server má pool DB připojení (i kdyby neměl, DB má limit na počet připojení) – Pro každého klienta spuštěn proces s vlastním DB připojením – Pokud klient zanikne bez odhlášení / začne se zpožďovat, obsluha a připojení stále aktivní mohou se vyčerpat povolená připojení přibývá procesů a jejich režie na straně serveru Zpožďují se i ostatní klienti a problém narůstá • V extrémním případě server plně vytížen, ale nic nedělá
Paměť a výkon •
V běhových prostředích (JRE, .NET) paměť řízena – Existují metody GC, GC potřebuje výpočetní výkon – Vede ke stabilnějším aplikacím (nejsou memory leaky)
Minor GC – mark and sweep v Eden Major GC – zastaví JVM (Stop-the-world), mark and sweep nad celým heapem (pro heap 30 GB může jít až od desítky sekund) – Existuje concurrent mark and sweep – Vhodně nastavit velikosti jednotlivých sekcí (podle činnosti aplikace – potřebuje velký Eden nebo velký Tenured space?)
•
From space
Nemusí být problém pokud Major GC netrvá moc dlouho – Uživatel nezaregistruje zastavení kratší než 200 ms (pokud není moc časté)
•
To space
Alokace drahé, stojí čas sledovat co se vytváří
29.11.2016
Eden
VSS - Spolehlivost
• •
Tenured space (Old generation)
Memory bloat • Zaplňování paměti „nepotřebnými“ daty – Užitečná data – primitivní typy, zrcadlí se v DB – „Nepotřebná data“ – režie datových struktur, reference, …
• Zdroje bloatu: – Frameworky – načítají a udržují řadu režijních objektů – Kolekce – předem připravené null pozice zabírají místo • Velké množství předpřipravených map může zabrat většinu paměti
– Spojové struktury dražší než pole – reference – Složité struktury z malých objektů zabírají víc místa než velké objekty 29.11.2016
VSS - Spolehlivost
• Lze určit poměr mezi daty a režií – měl by být ve prospěch dat
„Memory leak“ • •
V Javě ve skutečnosti nejde vytvořit (pokud není bug v JVM nebo nativním kódu) Problém – „zapomenuté“ reference
• mapa s objektem jako klíčem, v equals() porovnání přes ==
– Zapomenutá vlákna • V mapě uložené session které skončily
– Zapomenutí posluchači • Objekt GUI zůstává v paměti, zaregistrován jako posluchač dat která už nepotřebuji má na ně referenci
•
Slabé reference – GC je ignoruje – Class WeakReference
- reference přímo z objektu – Class WeakHashMap - mapa která neudrží objekty v paměti 29.11.2016
VSS - Spolehlivost
– Načtené řetězce (parsování XML, dotazy do DB, …) (navíc – char má 16 b – UTF 16) – Do nekonečna nafukované kolekce
Souběh • •
Synchronizace vynucuje čekání Zmenšuje skutečnou paralelizaci Nejlépe nepotřebovat
•
Vyhnout se synchronizovaným jádrům
•
– ReentrantLock lock – ReadWriteLock lock
– Vynutí seřazení všech vláken na úzkém místě •
•
Lze zamykat – lock(), unlock() – writeLock(), readLock()
Synchronizovaný blok – Nemusím synchronizovat celou metodu •
synchronized(this) { do something }
Zámky
Lze testovat stav – tryLock() – neblokuje vlákno
29.11.2016
VSS - Spolehlivost
– Immutable objekty není třeba synchronizovat při změně musím tvořit nové – tvorba + zátěž GC (tvorba objektu drahá, ale synchronizace dražší)
Děkuji za pozornost
VSS - Spolehlivost
• Příště předtermín
29.11.2016