Partea 3

Orice metodă de a păstra. în timpul execuţiei unui program, suficienţi informaţie pentru a putea executa programul în ordine inversă, instrucţiune cu instrucţiune, ar fi la fel de nepractică. Cum starea la care se revine este aceea dinaintea executării versiunii primare, singurele valori care trebuie restaurate sunt acelea ale variabilelor ne locale care sunt modificate în timpul execuţiei blocului cu restabilire. Aceste valon sunt păstrate într-o memorie rapidă numită "recursive cache"', care este împărţită în regiuni, câte una pentru fiecare bloc cu restabilire.

Regiunea "cache" păstrează valorile iniţiale ale variabilelor modificate în timpul executării blocului cu restabilire şi. în cazul manifestării erorilor, permite revenirea în punctul de reluare cel mai apropiat Regiunea respectivă este ştearsă după ce a fost utilizată pentru restaurarea stării anterioare, cu excepţia valorilor unor variabile care se referă la mediul înconjurător şi care vor fi consolidate. Evident, pentru selecţia variabilelor care trebuie memorate este necesară detectarea primei noi atribuiri a unei variabile nelocale în timpul executării blocului dc restabilire. Acest lucru se realizează parţial prin mijloace hardware, metodă rnai eficientă când programul prelucrează volume mici de dale. Din contra, dacă sc prelucrează man blocuri de date tablouri sau fişiere, restabilirea stării prin metode exclusiv software sc dovedeşte eficientă [4].

Structura dc tip bloc cu restabilire poate fi compusă, astfel încât fiecare variantă să fie ea însăşi un bloc cu restabilire, după cum se arată în figura 8.3. Testul de acceptare BT va fi executat după terminarea variantei primare BP. Dacă rezultatul este satisfăcător, blocul cu restabilire este părăsit în caz contrar, se readuce sistemul Ia starea dc dinaintea execuţiei lui BP şi se începe executarea variantei BQ. in momentul reuşitei, blocul cu restabilire esle părăsii lără a se restabili starea sistemului Dacă toate variantele BP. BQ şi BR eşuează, se cosideră că ansamblul variantei primare AP a eşuat, starea sistemului este restabilită la punctul fixat înainte de execuţia lui AP şi se trece la varianta AQ.

Se remarcă faptul că punctele de restabilire fixate la intrarea blocului A, respectiv B sau C sunt în general diferite, deoarece între ele poate avea loc executarea mai multor instrucţiuni (cele cuprinse în figură sub indicativul ). O analiză a fiabilităţii structurii descrise mai sus trebuie să luăm în considerare toate sursele posibile de erori sintetizate în figura 8.4, care conţine o variantă primară P şi o singură alternativă secundară S. Dacă specificaţiile generale ale blocului conţin o eroare, aceasta se poate regăsi în specificaţjilc comune ale variantelor (2). în specificatiile de acceptare (3) sau în ambele.

Fie q_PST probabilitatea de manifestare a unei erori care afectează doar specificaţiile variantelor primară şi secundară este qrs iar probabilităţile de manifestare ale erorilor independente care afectea/ă separat cele două variante şi testul de acceptare sunt respective qp , qr si qs.

Erorile menţionate pot fi clasificate conform tabelului 8.1

În continuare se admite că numai una din cele patru categorii de erori menţionate în tabelul 8.1 se poate manifesta în blocul cu restabilire şi că nu sunt posibile compensaţii intre erori. Deci, dacă oricare dintre variante (sau ambelej sunt surse de erori ma, infestate, acestea vor fi detectate cu siguranţă de testul dc accepure liste insă posibil ca testul de acceptare să nu admită în mod eronat corectitudinea rezultatelor furnizate dc P sau de S. Modelul fiabilităţii blocului cu restabilire, este. conform celor arătate în § 8. I. de tip semi-Markov (fig 8.5). în figura 8 5. starea I este starea initiala a blocului care este părăsită de îndată ce blocul este activat.

Săgeţile arată schimburi de informaţii între procese. Presupunem că o eroare se manifestă la momentul t în primul proces (P1). In acest caz starea lui P1 este restabilită la punctul de restabilire 4 şi varianta secundară intră în acţiune. Deoarece între timp nu au existat schimburi de mesaje cu celelalte procese, desfăşurarea acestora nu va fi afectată. Presupunând că al 2-lea proces (P2) manifestă o eroare la t, starea lui revine la punctul de restabilire 4, iar schimbul de mesaje derulat între timp cu primul proces (P1) trebuie anulat, ceea ce înseamnă că starea lui P1 trebuie restaurată la punctul de restabilire 3. Presupunând acum că P3 manifestă o eroare la t, restabilirea lui în punctul 4 impune anularea comunicării cu P2, deci acesta din urmă trebuie să revină în starea 3, ceea ce obligă pe P3 să revină în starea 3 s a.m d. In final, toate cele trei procese trebuie reiniţializate în starea 1. Această restaurare în cascadă a stărilor de referinţă poartă numele de efect domino [6]. O imagine mai simplă a efectului domino între 2 procese paralele este dată in fig. 8 7. Restabilirea primului proces la momentul t nu afectează al doilea proces. Restabilirea celui de-al doilea va iniţializa o cascadă de restabiliri până când ambele procese revin în stările lor iniţiale.

O modalitate de a evita efectul domino este extinderea structurii de bloc cu restabilire pentru a include mai multe procese de interacţiune într-o structura globală numită "conversaţie". Conversaţia este o modalitate de limitare a efectelor produse de activarea unei erori. Pentru descrierea acestei structuri se adoptă convenţia de reprezentare a blocului cu restabilire din fig 8,8, a. Săgeata reprezintă direcţia desfăşurării procesului, linia superioară reprezintă starea de referinţă care se restaurează la activarea alternativei iar linia inferioară starea acceptabilă a blocului cu restabilire, validată de testul de acceptare. Liniile laterale arată, că procesul este izolat de orice alte activităţi, astfel încât starea sa de referinţă să poată fi în întregime restaurată la nevoie. In cadrul unui bloc cu restabilire, se pot desfăşura mai multe procese în paralel, iar unele dintre acestea pot avea la rândul lor o structură internă de bloc cu restabilire (fig.8 8, b). Sa presupunem acum că între procesele paralele X şi Y din blocul cu restabilire din figura 8.8. b, trebuie sâ aibă o interacţiune în punctele E şi F.

Dacă, în punctul C, testul de acceptare invalidează procesul Y, starea acestuia din punctul A va fi restaurată şi alternativa secundară va fi activată. Procesul X trebuie însă şi el să fie reluat pentru a se putea realiza interacţiunea din E, astfel încât acest proces trebuie readus în starea lui din K. Aceasta înseamnă că şi procesul Y trebuie readus la starea K de la intrarea blocului comun de restabilire. Astfel, comunicarea, fie că înseamnă transmitere explicită de mesaje, fie doar o referinţă la variabile comune, face ca blocul intern de restabilire practic să nu funcţioneze. Această situaţie este evitată prin încadrarea ambelor procese paralele într-un bloc cu restabilire după cum se arată în figura 8.8. c Procesele intrate în conversaţie în cadrul unui astfel de bloc cu restabilire pot schimba informaţii intre ele dar toate trebuie să satisfacă testele respective de acceptare la sfârşitul conversaţiei şi nici unul nu poate continua până când toate celelalte nu au fost validate de test.

Dacă într-unul din aceste procese se manifestă o eroare, toate procesele trebuie readuse în stările de referinţa respective de la începutul conversaţiei.

Aşa cum se arată în fig.8.8. c şi 8.9. a este posibil ca procesele să intre în conversaţie la momente diferite, ele părăsesc însă conversaţia în acelaşi timp. astfel încât nici un punct de restabilire să nu fie şters din memorie înainte ca toate celelalte procese interactive să treacă de testul de acceptare. Aşa cum structura de bloc cu restabilire poate include o altă structură de bloc cu restabilire, conversaţiile pot conţine alte conversaţii.

Conversaţiile care se intersectează ca in figura 8.9, c. trebuie evitate, ele conducând tot la dificultăţile examinate anterior în figura 8.8, a. Procedeul de sincronizare a blocurilor cu restabilire prin structura dc conversaţie poate încetini prelucrarea datelor deoarece procesele trebuie să aştepte unele după altele, dar acesta este preţul de plătit pentru asigurarea controlului asupra restabilirilor.

8.3.2. Testele de acceptare

Testele de acceptare sunt concepute în conformitate cu două cerinţe: să detecteze deviaţii faţă de comportarea prevăzută a programului şi să prevină furnizarea unor rezultate potenţial periculoase. In primul caz au loc mai multe activări ale variantelor secundare dar, de obicei, întârzierile datorate reluării execuţiei prin alte variante nu sunt critice, în timp ce nedetectarea rezultatelor necorespunzătoare este mult mai gravă. Al doilea caz, care are în vedere doar situaţiile periculoase, este adecvat situaţiei când programul este utilizat de mult timp şi se doreşte un test de acceptare simplu care să evite reluări inutile. Deseori, se foloseşte un test de acceptare mai pretenţios pentru programe noi şi, ulterior, condiţiile de acceptare se relaxează după un anumit interval de maturizare.

Un prim tip de test de acceptare se referă la satisfacerea cerinţelor formulate în definirea problemei pe care programul trebuie să o rezolve De exemplu, într-un program de ordonare a unor elemente, un test de acceptare puternic ar consta în verificarea faptului că mulţimea de ieşire este o permutare a mulţimii de intrare. Cum un asemenea test ar fi prea complex, se preferă un test mai sumar, care verifică uniformitatea regulii de succesiune în mulţimea de ieşire şi faptul că mulţimile de intrare şi de ieşire au acelaşi număr de elemente [7].

Unele teste de acceptare constau din inversarea operaţiilor efectuate de program şi compararea rezultatelor obţinute cu datele de intrare. Aceste teste sunt practice când operaţia inversă este mai simplă decât cea directă. Astfel, corectitudinea extragerii rădăcinii pătrate se verifică foarte simplu prin ridicarea rezultatului la pătrat şi comparaţia cu valoarea iniţială, deoarece ridicarea la pătrat este mult mai simplă decât extragerea rădăcinii. Acest procedeu este limitat de faptul că multe funcţii realizate prin programe nu sunt inversabile. Testarea prin verificarea îndeplinirii cerinţelor este eficientă pentru segmente mici ale unui program de calcul, pentru care cerinţele pot fi simplu formulate. Pe de altă parte, structura de bloc cu restabilire este ea însăşi mai eficientă dacă testul de acceptare verifică un segment mai mare al programului. Testele bazate pe verificarea satisfacerii cerinţelor sunt utilizate cu succes în compilatoare şi programe de editare.

Un alt tip de teste de acceptare este bazat pe verificările contabile şi este util în programele care supervizează tranzacţii, cum ar fi rezervarea biletelor de avion sau serviciul de împrumut al unei biblioteci. Astfel, de fiecare dată când o serie de operării financiare este transmisă între diferite staţii de prelucrare se păstrează în memorie volumul tranzacţiilor. La recepţie se calculează noul total şi se compară cu cel vechi. Când se urmăreşte un volum foarte mare de tranzacţii, este aproape imposibil să se evite erorile datorate transcrierilor incorecte sau documentaţiei în mod greşit dirijate. Uneori, asemenea erori nu sunt inocente, si dând posibilitatea unor mari câştiguri materiale prin manipularea îndemânatică a informaţiei.

Contabilitatea dublă este o metodă de a detecta astfel de erori şi poate fi cu succes folosită ca principiu al testelor de acceptare. Procedeul este bazat pe ideea că totalul creditelor din toate conturile trebuie să fie egal cu totalul debitelor din toate conturile în orice interval de timp arbitrar, cu condiţia ca tranzacţiile dintre conturi să fi fost înregistrate. Un alt fel de verificare contabilă constă din confruntarea tranzacţiilor cu schimbările din inventarul fizic petrecute într-un anumit interval de timp Astfel, când se păstrează materialul nuclear, este posibil să se determine cantitatea existentă în inventar prin numărătoare de radiaţii care introduc datele direct în calculator. La intervale predeterminate de timp, schimbarea în nivelul radiaţiei poate fi comparată cu aceea calculată în mod independent pe baza îmbătrânirii materialelor şi a modificărilor de inventar datorate tranzacţiilor autorizate. In felul acesta se obţine o verificare globală care include şi erorile din sistemul de calcul. Verificările contabile sunt adecvate programelor cu aplicaţii comerciale care utilizează operaţii matematice simple.

O categorie mai largă de teste este bazată pe aprecierea caracterului rezonabil al rezultatelor furnizate de program. Aceste teste examinează dacă rezultatele se încadrează în gama de valori admisibilă, urmăresc deviaţiile variabilelor faţă de valoarea medie, corelaţiile între diverse variabile sau dintre creşterile, respectiv descreşterile, acestora.

Având în vedere că demarcaţia dintre un rezultat corect şi unul eronat nu este întotdeauna uşor de făcut, mulţimea rezultatelor eronate poate fi considerată o mulţime vagă. Testul de acceptare evaluează funcţia de apartenenţă a mărimii de ieşire la această mulţime şi ia decizia de invalidare dacă valoarea acestei funcţii depăşeşte un anumit prag. Funcţia de apartenenţă se trasează subiectiv pentru fiecare intrare posibilă şi se mediază pe mulţimea datelor de intrare in conformitate cu legea de distribuţie care descrie frecvenţa lor relativă de apariţie [8].

Un exemplu de test de rezonabilitate este oferit de calculul vitezei unui avion. în funcţie de caracteristicile structurale şi aerodinamice, viteza este cuprinsă între 140 şi 1 100 km/oră. O valoare calculată în afara acestei game indică o eroare grosolană a programului. Un test de acceptare în care limitele vitezei să fie mai apropiate poate fi construit dacă se ia în consideraţie configuraţia avionului. Un test de acceptare mai senzitiv examinează acceleraţia avionului, care trebuie să fie sub 6G în condiţii normale de zbor şi întotdeauna sub 6G, adică 213 km/h-s, care este acceleraţia maximă admisi- bilă pentru a se asigura integritatea structurală. Viteza este calculată de 10 on în fiecare secundă, iar creşterea între două valori succesive trebuie să fie sub 21.3 km/h.

Un exemplu similar de test de acceptare se referă la tranziţia stărilor unui sistem de comutaţie telefonică. După obţinerea legăturii nu se poate trece în starea de ..ocupat" sau "nu răspunde". Asemenea tranziţii inadecvate pot 6 folosite pentru detectarea erori- lor din program.

Testele de rezonabilitate sunt utile îndeosebi pentru programele care controlează variabile fizice în timp real. Este important ca varianta de rezervă a blocului cu restabilire să fie independentă de structura testului de acceptare şi de datele folosite de acesta.

Cele mai multe calculatoare oferă posibilităţi de testare continuă a stărilor anor- male ale sistemului, rezultate în urma împărţirii prin zero. a depăşirii valorilor limită (overflow şi underflow), a încercărilor de execuţie a unor operaţii nedefinite sau a scrierii în zone protejate ale memoriei etc Testarea se realizează prin mijloace hardware, utilizându-se un bit din registrul de stare, care semnalează necesitatea intervenţiei operatorului. Aceleaşi procedee pot fi adaptate pentru construcţia testelor de acceptare in structurile tolerante la defectări. Un exemplu este controlorul "walch dog" care asigură faptul că un rezultat acceptabil este obţinut într-un interval de timp specificat. Verificări în timpul execuţiei includ de asemenea structuri de date şi teste integrate în sistemul de operare. Verificarea indicilor tablourilor de variabile este în mod curent im- plementată. Autotestabilitatea şi rezistenţa la erori implică un număr de tehnici de mo- nitorizare speciale dintre care sc remarcă supervizorul de interacţiuni [9, 10].

Cea mai simplă, el cere declararea pentru flecare modul a apelurilor autorizate şi a surselor acestor apeluri. Supervizorul induce o decizie de respingere în testul de acceptare dacă accesul sau ieşirea dintr-un modul se referă la adrese neautorizate. Verificările in timp real controlează, de asemenea, încercările de scriere în zone protejate ale memoriei care au drept cauză posibilă un algoritm impropriu de inrJexare. Aceste verificări completează teslele de rezonabililate. testele contabile sau teste de satisfacere a cerinţelor şi sunt suficiente pentru segmentele necritice ale programelor.

8.3.3. Realizarea variantelor

Într-un bloc cu restabilire, toate modulele sunt disponibile la intrarea blocului, indiferent de erorile manifestate anterior, şi sunt executate într-o ordine strict definită. Intervenţia în modul la manifestarea unei erori nu este necesară deoarece este puţin probabil ca, într-o nouă execuţie să se repete condiţiile care au activat anterior eroarea. Variantele modulelor unui bloc cu restabilire trebuie să fie cât mai diferite între ele. Aceasta se poate realiza în următoarele trei strategii:

a) Variante independente neierarhizate

Fiecare modul este proiectat astfel incat să se asigure aceeaşi completă funcţionalitate, iar diversitatea este asigurată prin echipe diferite care elaborează modulele utilizând tehnici şi instrumente diferite. In acest caz, ordinea în care se execută modulele este arbitrară.

b) Variante ierarhizate

Fiecare modul asigură aceeaşi funcţionalitate, dar există o preferinţă privind ordinea execuţiei. Alternativele pot fi versiuni mai vechi, mai puţin sofisticate ale variantei primare şi, în consecinţă, mai puţin afectate de erori. Ele pot fi proiectate utilizând algoritmi mai puţin eficienţi, dar mai robuşti. Faptul că variantele secundare sunt rareori executate, compensează relativa lor ineficientă.

c) Variante funcţional degradate

Modulul primar asigură funcţionalitatea completă iar altenativele secundare au performanţe progresiv reduse Modulele secundare pot fi versiuni mai vechi, stângace dar robuste, ale variantei primare, sau pot fi deliberat proiectate astfel încât să aibă o complexitate redusă şi un timp de execuţie mic in dauna performanţelor. Ca urmare, contrar procedeului obişnuit, variantele secundare trebuie să fie validate de propriile lor teste de acceptare, diferit concepute. Alternativele funcţional degradate sunt în mod deosebit utile în sistemele în timp real deoarece, în acest caz, s-ar putea să nu existe suficient timp la dispoziţie pentru execuţia unei alternative complete, atunci când se manifesta o eroare în varianta primara. Un exemplu de bloc cu restabilire cu alternativă secundară degradată este dat în figura 8.10 în urmărirea prin radar a unui axion se utilizează drept parametri ultima poziţie măsurată in raport cu radarul, iar cu varianta primară se calculează noua poziţie şi viteză. Testul de acceptare verifică dacă rezultatele sunt rezonabile în raport cu parametrii constructivi ai avionului Dacă testul respinge rezultatele variantei primare, prima variantă secundară calculează doar noua poziţie şi preia valoarea anterioară a vitezei. In cazul unei noi respingeri, se activează a doua variantă secundară, care preia ca atare valorile anterioare ale poziţiei şi vitezei. Cazul limită al blocului cu variante degradate este cel cu o variantă primară şi o alternativă nulă în aceste condiţii, rolul blocului cu restabilire este doar de a detecta eroarea şi a ignora operaţia care a dus la manifestarea ei.

8.4. STRUCTURI N-VERSIONALE

O altă structură tolerantă la defectări utilizează un număr impar de versiuni concepute în mod independent conform aceluiaşi set de specificaţii şi oferind, fiecare, o completă funcţionalitate. Versiunile sunt activate de un modul supervizor numit driver care le furnizează acestora datele de intrare printr-o facilitate de citire (read only). Acelaşi driver colectează ieşirile variantelor şi le combină conform unei reguli care, în cel mai simplu caz, este de tipul votării majoritare. Rezultatul sintetic va corespunde deci majorităţii rezultatelor oferite de versiunile independente. In acest mod, erorile, care se presupune că afectează variantele minoritare, nu influenţează mărimea globală de ieşire.

Identificarea versiunilor afectate de erori este inerentă mecanismului de votare, prin care se constată disparitatea dintre rezultate şi se consideră eronate cele aflate în minoritate. Efectele acestor erori trebuie restrânse la versiunile în cauză pentru a nu afecta restul sistemului. Acest lucru poate fi realizat în mod ideal prin rularea fiecărei versiuni pe un suport hardware distinct sau, dacă se utilizează aceeaşi maşină de calcul pentru rularea tuturor versiunilor într-un regim de partajare (time-shanng). Atunci trebuie luate măsuri logice de protecţie între diferite zone. Faptul că manifestarea erorilor dintr-o versiune nu trebuie să afecteze operarea celorlalte versiuni este asigurat prin izolarea oferită de maşina virtuală pe care se execută programul şi nu se rezumă la eliminarea comunicărilor dintre versiuni.

Având în vedere că într-o structură N-versionalâ, toate versiunile sunt executate, ele reţin datele între apeluri şi, ca urmare, pot fi proiectate ca "obiecte" care-şi ascund structura internă. Acest lucru are avantajul de a mări independenţa dintre versiuni şi reduce volumul de date care trebuie transferat unei versiuni la apelarea ei. Este de remarcat faptul că, în cazul structurii de tip bloc cu restabilire, nu se execută toate modulele la apelarea blocului. Ca urmare, aceste module nu trebuie să reţină local date între două chemări succesive, deoarece altfel ar putea deveni reciproc inconsistente. Spre deosebire deci de modulele structurii N-versionale, versiunile blocului cu restabilire trebuie proiectate ca nişte componente fără memorie, şi nu ca "obiecte". Deoarece modulele structurii N-versionale reţin date, o versiune care a furnizat un rezultat eronat nu mai poate fi reutilizată. Având în vedere că starea ei internă a devenit incompatibilă cu a celorlalte Este deci necesar să se prevadă o posibilitate de restabilire a stării unei versiuni afectate de erori, o metodă simplă constând în revenirea în starea dinaintea ultimei operaţii.

Pentru a asigura consistenţa versiunilor, este necesar ca şi cele corecte să fie readuse la stările anterioare, pierzându-se astfel ceva din istoria sistemului. Dacă acest lucru nu este acceptabil, o strategie de restabilire mai elaborată va aduce versiunea eronată într-o stare care să corespundă stărilor actualizate ale versiunilor corecte. Procedeul este dificil de realizat, deoarece, versiunile fiind independente între ele, structurile lor interne de date sunt diferite. Un algoritm de translaţie este necesar pentru a face legătura între stările interne normale ale diferitelor versiuni.

Structura N-versională depinde de calitatea procesului de votare. Aceasta poate fi îmbunătăţită prin includerea în specificaţiile versiunilor a unor valori intermediare de control care vor fi furnizate driver-ului o dată cu rezultatele de ieşire. Confruntând aceste valori intermediare, driverul va detecta şi erori în stările interne ale versiunilor, nu numai în stările lor externe. Independenţa dintre versiuni va fi însă limitată de faptul că procesarea internă trebuie să conveargă în toate versiunile în punctele de control determinate de aceste valori intermediare. Vectorul trebuie să fie simplu pentru a nu fi el însuşi afectat de erori, dar proiectarea lui nu este banală. Dacă rezultatele prelucrării sunt numere reale, versiuni corecte dar diverse nu vor da ieşiri identice, astfel încât este necesară o votare inexactă. Pentru aceasta, se împarte domeniul valorilor de ieşire in clase de echivalenţă, inainte ca votarea să fie efectuată. Dacă cea mai mare clasă de echivalenţă contine mai mult dc N/2 rezultate neclare, dintre acestea poate fi considerat rezultatul global al sistemului, sau se adoptă drept rezultat global mediana clasei de echivalenţă celei mai mari. Dificultatea în definirea claselor dc echivalenţă nu este dc neglijat, deoarece variabilitatea rezultatelor între versiuni nu este constantă în timp.

Consideraţii practice pot complica, la rândul lor, mecanismul de votare. Modulul driver trebuie să ţină seama de duratele diferite de execuţie ale versiunilor, fie păstrând rezultatele unor versiuni în aşteptarea celorlalte, fie efectuând votarea în timp real. Pe măsură ce se obţin rezultatele, astfel încât un rezultat global poate fi obţinut înainte ca toate versiunile să-şi încheie execuţia în sistemele critice din punct de vedere al siguranţei, se preferă o decizie bazată pe unanimitate, nu pe majoritate, astfel încât, dacă rezultatele tuturor versiunilor nu sunt echivalente, sistemul este dus într-o stare de defectare nepericuloasă (fail-safe).

Structura N-versionala poate fi de tip compus, fiecare modul al unei structuri N-versionale fiind el însuşi conceput ca o structură N-versională. Limitarea compuneri structurilor este impusă de necesităţile de izolare a versiunilor care implică, în cazul cel mai de dorit, configuraţia multiprocesor. Astfel, fiecare versiune ar fi executată pe propriul său hardware, ceea ce, în cazul structurilor compuse, ar multiplica excesiv numărul de procesoare. Modelul semi-Markov al fiabilităţii structurii N-versionale va fi stabilit pentru N = =3 în două ipoteze:

a) versiunea afectată de erori nu este eliminată din structură, ci este reutilizată după revenirea într-o stare compatibilă cu a celorlalte;

b) versiunea afectată de erori este eliminată din structura N-versională.

Sursele de erori ale sistemului N-versional sunt prezentate în figura 8.11. O eroare în specificaţiile globale poate conduce la prezenta unei erori comune în cele trei versiuni şi în driver. Probabilitatea manifestării unei asemenea erori este qvy. Pot exista erori comune în oricare două versiuni sau în toate trei iar probabilităţile lor de manifestare sunt, respectiv, q2V şi q3V. Erorile individuale ale versiunilor se manifestă independent cu aceeaşi probabilitate q1V iar eroarea individuală a driverului se manifestă cu probabilitatea qD. Tabelul 8.2 prezintă categoriile de erori şi probabilităţile lor de manifestare.

Stările structurii 3-versionale sunt definite în tabelul 8.3 şi sunt reprezentate în fig. 8.12.

Dacă versiunile dai rezultate net distincte între ele, sau dacă driver-ul nu recunoaşte similaritatea lor, aiunge în starea de defectare B, recunoscută ca atare, iar starea iniţială a versiunilor este restabilită.

Starile Sistemului 3-versional

Tabelul 1.3

In condiţiile când versiunile dau două sau trei rezultate similare, dar eronate, driver-ul nu poate detecta incorectitudinea lor şi se ajunge în starea de defectare C, ignorată de sistem. Construcţia modelului semi-Markov din fig. 8.12 este bazată pe ipoteza că un singur tip de eroare din cele prezentate în tabelul 8.2 se poate manifesta în timpul execuţiei şi că nu există compensări ale erorilor.

Probabilitatea de tranziţie din starea V în starea D2 este egală cu 3q1v(l- q1v)2~ 3q1v, deoarece ea corespunde manifestării erorii doar într-una (oricare) din cele trei versiuni. Tranziţia din starea V în starea D3 se face cu probabilitatea ca oricare două versiuni, sau toate trei să manifeste erori independente, adică 3q21v(1-q1v)+q31v~3q21v- In sfârşit, tranziţia din f în D1 se face cu probabilitatea 3q2v + q3v + qvD de manifestare a erorilor comune în oricare două versiuni, în toate trei, sau în toate modurile.

Probabilitatea de defectare a structurii este proportional cu:

In general, raportul r este cuprins in intervalul (r_L,r_v). O valoarea cat mai mica a acestui raport, fapt care reflecta eficienta mascarii erorilor in structura 3-versionala, se obţine dacă elementul de decizie este mult mai fiabil decât oricare versiune (q_D« Fnr) şi dacă ponderea erorilor independente într-o versiune este cât mai mare (i -> 1).

Spre deosebire de structura bloc cu restabilire, în structura 3-versională se recurge uneori la eliminarea versiunii eronate după detectarea erorii latente pe care o conţine. Elementul de decizie identifică versiunea care nu este concordantă cu celelalte două şi o exclude de la prelucrările ulterioare de date. în continuare, driver-ul utilizează un test de rezonabilitate pentru a decide asupra corectitudinii rezultatelor furnizate de celelalte două versiuni rămase în sistem. Modelul semi-Markov al sistemului este reprezentat în figura 8,13. Se observă că secţiunea M, a structurii din figura 8.13 este similară cu cea din figura 8.12, cu deosebirea că, în cazul manifestării unei erori singulare, sistemul trece în noua stare iniţială I*, care corespunde la două versiuni aflate în aşteptarea datelor. La următorul apel, sistemul trece în starea V*, în care se execută în paralel cele două versiuni care nu au manifestat erori. La terminarea execuţiei se testează caracterul rezonabil al rezultatelor şi, în cazul acceptării lor, sistemul este readus în starea I*.

Daca se manifesta erori independente într-una sau în ambele versiuni, acestea sunt detectate şi sistemul ajunge în starea de detectare necatastrofică B*. cu probabilitatea 〖2q〗_1V+q_1V^2≈〖2q〗_1V . In aceeaşi stare se ajunge cu probabilitatea q_D dacă voter-ul nu recunoaşte corectitudinea rezultatelor furnizate de ambele versiuni, activând tranziţia D* -» B*. Sistemul ajunge în starea de defectare catastrofică C* când se manifestă erori comune ambelor versiuni şi nu sunt recunoscute ca atare de elementul de decizie, fapt ce se produce cu probabilitatea q_2V+q_VD.

Probabilitatea ca subsistemul M_1, (structura cu 3 versiuni) să ajungă într-o stare de defectare este proporţională cu:

Comparând expresiile (8.18) şi (8.19) rezultă că, dacă erorile independente sunt preponderente, adică q_1V≫q_2V,q_3V,q_VD atunci F_1F_2. De aici, se poate trage concluzia că utilizarea a trei versiuni în loc de două este avantajoasă numai dacă erorile independente depăşesc ca pondere erorile comune tuturor versiunilor.

Prin analizele efectuate asupra fiabilităţii sistemului s-a urmărit traiectoria acestuia până la atingerea oricărei stări de defectare. Dacă se urmăreşte în primul rând securitatea sistemului, trebuie avute în vedere numai stările de defectare critice C şi C* în care eroarea manifestată nu este detectată. Comparând probabilităţile de tranziţie în aceste stări, se constată că atingerea stării C în configuraţia M_1, este mai probabilă decât atingerea stării C* în configuraţia M_2. Prin urmare, reconfigurarea sistemului 3-versional prin eliminarea versiunii eronate îmbunătăţeşte întotdeauna securitatea sistemului.

Analizele cantitative anterioare permit şi o comparaţie între performanţele structurii bloc cu restabilire şi cele ale structurii 3-versionale. Pentru comparaţie, se va considera structura 3-versionalâ fără reconfigurare. iar în cazul structurii de tip bloc cu restabilire, se va considera că ambele versiuni - primară si secundară - pot fi afectate de erori independente cu aceeaşi probabilitate (q_P=q_S=q_(I,RB)). Ca urmare, relaţia (8.7), care exprima probabilitatea de atingere a stării de defectare în structura bloc cu restabilire, devine pentru q_T≪1

Pentru a compara expresiile (8.20) şi (8.21), se admite că probabilitatea manifestării unei erori independente într-o versiune este aceeaşi, indiferent de tipul structurii insensibile la erori (q_P=q_S=q_1V.deci q_(I,RB)=q_(I,NV)). De asemenea, se poate presupune că probabilitatea activării erorilor comune mai multor versiuni este aceeaşi în ambele structuri, adică q_PS=〖3q〗_2V+q_3V. Pe de altă parte, elementul de decizie din structura N-versională este mai simplu decât testul de acceptare din structura bloc cu restabilire, deoarece el este conceput conform principiului general al votării majoritare şi nu are o structură specifică dependentă de aplicaţie şi ca urmare q_D≪q_r. Din acelaşi motiv, este mai probabilă activarea unei erori comune atât versiunilor cât şi elementului de decizie în structura bloc cu restabilire decât în structura N-versională, adică q_PST≫q_VD.In concluzie, probabilitatea manifestării erorilor de mod comun este mai mare în structura bloc cu restabilire respectiv q_(C,RB)≫q_(C,NV). Erorile independente au un impact mai mare asupra structurii N-versionale (de trei ori mai mare conform relaţiei 8.21), în timp ce erorile dependente afectează în mai mare măsură structura bloc cu restabilire.

Decizia în privinţa tipului de structură adoptat se bazează pe evaluarea cât mai exactă a expresiilor (8.20) şi (8.21).

Alături de această comparaţie, trebuie avut in vedere faptul că blocul cu restabilire presupune întreruperea şi reluarea execuţiei. în timp ce structura N-versională funcţionează continuu. De asemenea, modalităţile de proiectare a versiunilor şi a elementelor de decizie sunt diferite pentru cele două structuri, fiecare cu avantajele şi dezavantajele sale. Din punct de vedere al securităţii (evitarea stării de defectare în care eroarea rămâne nedectată) structura bloc cu restabilire este superioară deoarece utilizează un test de acceptare mai sofisticat. Rezultatele similare, chiar eronate, dintr-o structură N-versională sunt considerate corecte de elementul de decizie al acesteia.

8.5. STRUCTURI N-AUTOTESTABILE

Structura N-autotestabiă este formată din două componente care cuprind fiecare, câte două versiuni distincte (fig. 8.14). Deşi toate versiunile sunt executate simultan, numai una din perechi este activă, adică furnizează rezultate la ieşire, cealaltă fiind uti lizată ca rezervă. Fiecare componentă conţine un comparator care acceptă buna functionare a componentei daca rezultatele furnizate de cele două versiuni sunt similare. Comparatoarele împreună cu comutatorul-de la ieşire constituie elementul de decizie privind furnizarea unui rezultat la ieşire şi selectarea acestuia dintre rezultatele oferite de cele două componente.

Datorită faptului că versiunile sunt executate simultan, precauţiile privind restabi- lirea stării după manifestarea erorii sunt aceleaşi ca în cazul structurii N-versionale. Sursele de erori în structura N-autotestabila rezultă din figura 8.15. Tipurile posibile de erori împreună cu probabilităţile lor de activare sunt date în tabelul 8.4.

Conform figurii 8.15, sursele de eroare sunt specificaţiile şt procesul de implemen- tare. O eroare latentă în specificaţiile tuturor versiunilor sau o aceeaşi eroare comisă în implementarea lor se manifestă cu probabilitatea q_4V. Erorile comune la 2 sau 3 versiuni sunt erori de implementare care se activează cu probabilităţile q_2V, respectiv q_3V, O eroare comună versiunilor şi comparatoarelor poate proveni din specificaţiile comune pe căile 1 -> 2 -> 3 sau 1 -> 3, sau poate fi o eroare comună de implementare. Ea se manifestă cu probabilitatea q_VD Se presupune că o eroare independentă într-o versiune este activata cu aceeaşi probabilitate q_1V.

Ea poate proveni din specificaţiile comune versiunilor prin implementarea lor separată, respectiv prin căile 2 -> 4, 2 -> 5, 2 -> 6 sau 2 -> 7. In sfârşit, erorile In comparatoare provin din specificaţiile elementului de decizie sau din implementarea lor pe calea 3 -> 8 şi au probabilitatea de manifestare q. Ca şi în analizele efectuate asupra structurilor precedente, se va presupune că n ornai un singur tip de eroare se poate manifesta în timpul execuţiei şi că nu au loc compensări între erori. In aceste condiţii, stările sistemului sunt cele din tabelul 8.5.

Sistemul trece din starea I în starea V cu probabilitatea 1, în momentul apelării sale. Stările D_1 şi D_2 sunt stări de bună funcţionare. In starea D_1, nu s-au manifestat erori de execuţie iar, în starea D_2 două versiuni ale aceleiaşi componente furnizează rezultate similare corecte. Probabilitatea manifestării unei erori independente în oricare versiune este 〖4q〗_1V (1-q_1V )^3≈〖4q〗_1V, iar probabilitatea manifestării erorilor independente in două versiuni ale aceleiaşi componente este 〖2q〗_1V^2 (1-q_1V )^2≈〖2q〗_1V^2. Ca urmare, probabilitatea de tranziţie din starea V în starea D_2 este 〖4q〗_1V+〖2q〗_1V^2+q_2V, ultimul termen corespunzând manifestării erorii comune versiunilor componentei de rezervă.

In starea D_3, ambele comparatoare au la intrare rezultate distincte, astfel încât nici un rezultat final nu este furnizat la ieşire ajungându-se în starea de defectare B, detectată ca atare de sistem. Probabilitatea de defectare independentă a două versiuni din componente diferite, respectiv a trei sau patru versiuni este 〖4q〗_1V^2 (1-q_1V )^2+〖4q〗_1V^3 (1-q_1V )+q_1V^4≈〖4q〗_1V^2+〖4q〗_1V^3+q_1V^4, iar probabilitatea mamfestarii unei erori comune în două versiuni din componente diferite este 〖4q〗_2V.Ca urmare, probabilitatea de tranziţie din V in D_3 este 4q_1V^2+〖4q〗_1V^3+q_1V^4+〖4q〗_2V.

În starea D_4, cel puţin una dintre componente furnizează comparatorului două rezultate similare, dar eronate, astfel încât sistemul este condus în starea de defectare catastrofică C, în care un rezultat eronat este transmis la ieşire.

Probabilitatea de tranziţie din starea V în starea D_4, este 〖4q〗_3V+q_4V+q_VD+q_2V ultimul termen corespunzând erorii comune versiunilor componentei active tinând seama de cele de mai sus. modelul semi-Markov al structurii N-autotestabile este ce din figura 8.16.

Se observă că. datorită ipotezei privind manifestarea unui singur tip de eroare, clementul de decizie funcţionează cu certitudine satisfăcător în toate stările cu excepţia lui D_1. Probabilitatea de a atinge o stare de defectare (B sau C) este:

Dimpotrivă, dacă domină erorile comune la doua versiuni, datorate implementării, avem: q_2V≫q_3V,q_4V,q_VD si raportul r devine:

Valoarea raportului r este cuprinsă în general între limitele r_L si r_U redate de (8.28). respectiv de (8,29). Pentru ca structura N-autotestabilâ să fie eficientă, r trebuie să fie cât mai mic, adică q_D≪F_nr si i→1. Aceasta înseamnă că elementul de decizie trebuie să fie mult mai fiabil decât o versiune oarecare şi că ponderea erorilor independente dintr-o versiune trebuie să fie ridicată. în cazul extreme i = 0, caz în care erorile comune domină hotărâtor, nu se obţine nici o îmbunătăţire prin recurgerea la structura autotestabilă. Pentru a compara structura N-autotestabilă cu structurile bloc cu restabilire şi N-versionala, reluăm expresiile probabilităţilor de defectare (8.20) şi (8.21) asociate acestora din urmă şi le comparăm cu probabilitatea (8.22), căruia îi adăugăm indicele AT semnificând "autotestabil". Rescriind cele trei expresii, obţinem:

unde: q_(C,AT)=q_D+〖5q〗_2V+〖4q〗_3V+q_4V+q_VD reprezintă probabilitatea defectării de mod comun în structura autotestabilă. iar q_(1,AT) este probabilitatea manifestării erorii independente într-o versiune din această structură.

Ca şi înainte. Ia comparaţia dintre structurile bloc cu restabilire şi N-versională. presupunem că probabilităţile de manifestare ale erorilor independente într-o versiune sunt aceleaşi în toate structurile (q_(1,RB)=q_(1,NV)=q_(1,AT)). Dacă, în plus. şi probabilităţile de manifestare a erorilor de mod comun ar fi aceleaşi, structura bloc cu restabilire ar fi cea mai avantajoasă, urmată, în ordine, de structura N-versională şi de cea autotestabilă. Această ierarhizare este însă discutabilă din mai multe motive. Pe de o parte, elemental de decizie din structura bloc cu restabilire este mai sensibil la erori decât cele din structurile N-versională şi N-autotestabila. Primul este un test absolut de acurateţe şi este gândit în funcţie de aplicaţie, în timp ce ultimele sunt mai robuste, fiind bazate pe principiile generale ale comparării şi votării. Ca urmare, atât probabilitatea de mani- festare a unei erori independentă în elementul de decizie, cât şi probabilitatea manifes- tării unei erori comune tuturor versiunilor şi elementului de decizie este mai mare în cazul structurii bloc cu restabilire:

Media (8.37) reprezintă şansa eşecului unui program atunci când se iau în considerare atât incertitudinea privitoare la metodele de elaborare ale acestuia, cât şi incertitudinea privind datele iniţiale furnizate programului. Fie acum două versiuni π_1 şi π_2 realizate independent pe baza aceloraşi specificaţii Ipoteza privind independenţa elaborării versiunilor implică

Pentru intrarea fixată x_j probabilitatea ca ambele versiuni să dea ieşiri eronate este θ^2 (x_j) astfel încât se poate afirma că versiunile elaborate independent unele de altele manifestă erori în mod independent atunci când sunt confruntate cu aceleaşi date iniţiale bine precizate. Probabiltatea ca ambele versiuni π_1 şi π_2 să dea rezultate eronate la orice date iniţiale posibile se obţine mediind pe θ^2 (x) pe mulţimea datelor iniţiale

Expresia (8.39) este momentul de ordinul 2 al variabilei θ, egal cu varianta lui θ la care se adaugă media pătratului său. Dar. conform expresiilor (8,37), media lui θ este probabilitatea ca orice versiune să manifeste erori la orice intrare. Ca urmare, din relaţia (8.39) rezultă că. media pătratului fiind mai mare decât pătratul mediei, probabilitatea ca două versiuni oarecare să dea rezultate eronate pentru orice date iniţiale este mai mare decât produsul probabilităţilor asociate unei versiuni pasibile. Altfel spus, versiuni elaborate în mod independent se defectează (manifestă erori) în mod dependent .sub impactul unor date iniţiale aleatoare. Argumentul este şi mai pregnant când se consideră probabilitatea defectării versiunii π_2 condiţionată de defectarea versiunii π_1:

Cazurile din figurile (8.17, b) şi (8.17, c) sunt intermediare faţă de situaţiile extreme prezentate mai sus. în figura (8.17, b) funcţia de corelaţie fiind pozitivă, iar în figura (8.17, c), negativă. în acest din urmă caz, este de dorit ca variabilitatea între versiunile elaborate prin aceeaşi metodologie să fie cât mai măre. într-adevăr, din relaţia (8.46) rezultă:

Dacă ρ_(θ_A,θ_B )<0 este de dorit ca ρ_(θ_A ) şi ρ_(θ_B ) să fie cât mai mari, astfel încât eronarea unei versiuni să micşoreze cât mai mult eronatea versiunii produsă prin altă metodologie. Astfel, dacă metodologiile sunt profund diferite, este bine ca fiecare să ofere o gamă cât mai largă de posibilităţi. Invers, dacă metodologiile sunt asemănătoare, este preferabil ca fiecare să sc restrângă la un număr de versiuni.

Metodologiile diversificate se aplică la proiectarea structurilor tolerante Ia erori. Se consideră structura bloc cu restabilire cu o versiune primară şi o versiune secundară şi două metodologii^ şi B disponibile pentru elaborarea lor Admitem că probabilitatea totală de defectare a sistemului este aceeaşi, atât în cazul când ambele versiuni sunt realizate în metodologia A cât şi în cazul când sunt realizate în metodologia B Aceasta implică relaţia:

O comparaţie detaliată între relaţiile (8.51) şi (8.52) arată că utilizarea metodologiilor diferite este uneori avantajoasă, alteori dezavantajoasă raţă de utilizarea unei singure metodologii [11]. Pe de altă parte, dacă s-ar considera un singur set de date iniţiale, un sistem N-versional omogen ar fi net preferabil. într-adevăr, se ştie din teoria fiabilităţii hardware că un sistem majoritar format din elementele identice este superior unui sistem format din elemente distincte din punct de vedere al fiabilităţii.

8.7. APLICAŢII

Primele aplicaţii ale toleranţei la erori au apărut la început sub forme mai puţin sofisticate decât structurile descrise în acest capitol. Acestea constau în detecţia erorii, evaluarea consecinţelor şi restabilirea funcţionării. Detecţia erorii se face în principiu prin metodele utilizate la realizarea testelor de acceptare descrise în § 8 3.2 şi folosesc atât mijloacele software cât şi verificări bazate pe maşina virtuală pe care se execută programul. O dată eroarea detectată, ea este tratată ca o excepţie, fie Ia nivelul componentei în care a apărut, fie la nivelul subsistemului care are componenta inclusă

Dacă există o întârziere între activarea şi detecţia erorii, este posibil ca o porţiune mai mică sau mai mare din sistem să fie afectată. O serie de teste determină extinderea consecinţelor erorii şi este o practică deja încetăţenită ca ele să fie incluse în sistem.

Reluarea execuţiei după manifestarea erorii se face prin două tehnici complementare, restabilirea stării anterioare (bockwards recovery) şi aducerea într-o stare standard (forward recovery). în primul caz, starea sistemului este înregistrată Ia intervale prestabilite, astfel încât se poate readuce sistemul într-o stare în care s-a aflat înainte de defectare. Problema complexă a restabilirii stării anterioare în cazul unei structuri redundante a fost tratată în § 8.3. Tehnica "forward recovery" este aplicată atunci când consecinţele erorilor pot fi prezise prin metode ca FMEA (failure modes and effects analysis). în asemenea cazuri sistemul este condus într-o stare nouă de funcţionare, aniuandu-se şi efectele interactive ale erorii detectate. Acest procedeu presupune o bună predicţie a erorilor posibile, de aceea este mai rar utilizat. O dată sistemul restabilit, el poate ignora operaţia care a generat eroarea sau poate furniza un răspuns prestabilit şi foarte sumar în raport cu aşteptările. Aceasta este comportarea sistemelor robuste, care sunt înzestrate cu forme incipiente de toleranţă la erori, capabile doar să evite defectările catastrofice.

Dezvoltarea aplicaţiilor critice din punct de vedere al fiabilităţii şi al securităţii au impus depăşirea fazei sistemelor robuste şi utilizarea structurilor software redundante.' Astfel, sistemul de control al traficului, al Căilor Ferate Suedeze, utilizează structuri de tip 2-versional. Neconcordanţa dintre ieşiri implică aducerea sistemului într-o stare sigură, cum ar fi aprinderea luminilor roşii. Aceeaşi structură este utilizată în sistemul de control al avionului Airbus 310, dar versiunile sunt executate pe sisteme de calcul distincte.

Un pas înainte 1-a constituit sistemul de control al mălţimu al avionului teleghidat A 320, care utilizează structuri de programe 4-versionale executate pe hardware cu rezervă activă. Pentru sistemul de protecţie al reactoarelor s-au elaborat versiuni diferite de către colective independente din Anglia, Norvegia şi Finlanda, iar aceste versiuni au fost înglobate într-o structură N-versionalâ. Blocurile cu restabilire au fost aplicate în Marea Bntanie la sistemul de comandă şi control al navelor, bazat pe maşina virtuală MASCOT. Experimentările au arătat că în acest fel au fost neutralizate 74% din defectele potenţiale ale sistemului. Aplicaţii similare au fost incluse în sistemul de control al traficului aerian din Londra.

BIBLIOGRAFIE

1. Leclerq, Ph. R.. A Software - Reliability Assessment Modei. Proceedings of the Annual R & Symposium, Las Vegas, Nevada, January 1992, pag. 294-298.

2. Little iv ood, B., Software reliability model for modular program structure. lEEETrana. Reliab., R-28, 1(1979), pag. 241-245.

3. C i t uneanu, V. M_, Bacivarof, A., Structuri electronice detnaltă fiabilitate. Toleranţa la defectări. Editura Militari, Bucureşti, 1989, pag. 181-190.

4. R a n d e 11, B. System structure for software fault tolerance Proceedings of the bit Conf. on Reliable Software, Los Angeles, 1973, pag. 437-449. î. Ari al, J., Kanoun, K-, Laprie, J. C, Dependability modeling and evaluation of Software fault tolerance. ESPRIT project PDCS, research raport, may 1990.

5. Moulding, M R., Designing/or High integrity: The software fault tolerance approach In: Sawed, C, High integrity Software, Pitman, London, 1989

6. THecht, H., Fault Tolerant Software. IEEE Trans. Reliab., R-28,3 (1979), pag. 227-232. 7. Mihalacbe, A., A fuzzy set approach to software reliability modeling. Proceeding! of the ESRC, Copenhigoi 1992, pag. 724-730.

8.Yan, S. S., Cheng, R. C., Design of self-checking software. Proc. 1975 tat. Conf Reliable Software, pag, 450-457.

9. Yan, S. S., Cheng, R. C, Cochr«oe, D. C., An approach to error-rtsistent software design. Proc, 1976 bn_ Conf Software Engnmg. pag. 429-436.

10. Lilt I ew ood, B., Miller, D. R_, Conceptual modeling of coincident failures in multiversion software. IEEE Trans. Software Engnmg. vol. SE - 1Î, 12 (1989), pag. 1596-1614.

11. Humphreys, P., Diversity by Design-Reliability aspects of systems with embedded software in Littlewood. B. (edX Software Reliability, BlackweU, London, 1987, pag. 96-112.