Fiabilitatea în arhitectura calculatoarelor

Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/

decembrie 2001

Subiect:
fiabilitatea în sistemele de calcul
Cunoștințe necesare:
noțiuni elementare despre arhitectura calculatoarelor
Cuvinte cheie:
fiabilitate, redundanță, toleranța defectelor, cost


Cuprins




Introducere

În acest text voi prezenta arhitectura sistemelor de calcul dintr-un singur punct de vedere, și anume cel al fiabilității. Prezentarea nu va fi exhaustivă și nici matematizată; voi folosi mai ales exemple pentru a ilustra cum felurite considerații despre fiabilitate influențează design-ul sistemelor de calcul.

Principalul subiect al teoriei fiabilității (reliability theory) este construirea sistemelor fiabile din componente nefiabile. Dacă un sistem ar funcționa numai atunci toate componentele sale ar fi funcționale, ar fi virtual imposibil de construit un sistem complex, pentru că fiabilitatea ar descrește exponențial cu numărul de componente.

Principala unealtă folosită în construirea sistemelor complexe este abstracția. Un sistem este construit pe nivele; nivelul B este alcătuit din componente de nivel A. La rîndul lor, componente de nivel B sunt folosite ca și cum ar fi atomice, indivizibile, pentru a construi nivelul C, și așa mai departe. Acest proces este inspirat din matematică, unde lemele și teoremele sunt folosite drept componente elementare în demonstrațiile altor leme și teoreme. În acest text vom privi alcătuirea unor nivele din arhitectura sistemelor de calcul din punctul de vedere al fiabilității pe care o oferă nivelelor superioare. Astfel putem distinge:

  1. Nivele care măresc fiabilitatea, construind un tot mai fiabil din componente mai puțin fiabile. Acest lucru este obținut folosind redundanță în stocarea sau calculul informației. Acest tip de nivel este cel mai adesea folosit în construcția calculatoarelor contemporane. Secțiunea 3 discută multe astfel de exemple.
  2. Nivele care expun lipsa de fiabilitate nivelelor superioare, lăsîndu-le pe acestea să rezolve imperfecțiunile. Nivelele superioare au adesea informații suplimentare despre cerințele reale de fiabilitate ale sistemului, și ca atare pot construi fiabilitate pe măsura necesităților. Arhitectura Internetului, pe care o vom discuta sumar în secțiunea [*] din numărul viitor al revistei este unul dintre cele mai notorii exemple de acest gen.
  3. În fine, anumite nivele partiționează resursele în parți oarecum independente, izolate una de alta. Partiționarea are drept efect izolarea defectelor (fault containment / fault isolation), astfel încît o defecțiune într-o parte să nu afecteze celelalte părți. În calculatoare această tehnică este folosită în sistemele de operare și clustere-le de calculatoare.

La ora actuală circuitele integrate pe scară largă (Very Large Scale Integrated circuits, VLSI) au ajuns la nivele incredibile de fiabilitate. Ca atare arhitecții calculatoarelor în general privesc nivelul hardware ca fiind ``perfect'' și folosesc această abstracție foarte convenabilă în proiectarea nivelelor superioare. Anumite clase de aplicații însă au nevoie de o fiabilitate foarte ridicată (de exemplu, controlul de trafic aerian sau supervizarea centralelor nucleare). În astfel de sisteme critice arhitecții sistemelor de calcul iau în considerare și posibilitatea defectelor hardware, pe care le tratează în software.

Miniaturizarea continuă a circuitelor integrate va duce la schimbări în această stare de fapt; trebuie să ne așteptăm ca în viitor circuitele să conțină din ce în ce mai multe defecțiuni și să fie din ce în ce mai sensibile la fluctuații termodinamice și particule de înaltă energie din radiația cosmică sau chiar din degradarea radioactivă a circuitului integrat! Astfel de schimbări vor cere probabil o regîndire completă a arhitecturii sistemelor de calcul.

Fiabilitate

În această secțiune voi introduce terminologia folosită în restul articolului.

Definiție

Chiar dacă acest text nu este matematic, voi da o definiție precisă a noțiunii de fiabilitate.

Fiabilitatea unui obiect (o componentă sau un sistem) este o funcție de timp F(t), definită ca probabilitatea ca, în condiții de mediu specificate, obiectul să funcționeze adecvat în intervalul de timp [0,t).

Putem face cîteva observații foarte importante legate de această definiție:


Redundanță

Ingredientul cel mai folosit pentru a construi sisteme fiabile este redundanța. Putem distinge două genuri de redundanță, spațială și temporală:

Redundanța spațială
folosește mai multe componente decît strict necesar pentru a implementa un anumit sistem. Resursele adiționale fac calcule suplimentare și rezultatele sunt comparate între ele. În general, cu cît redundanța unui sistem este mai mare, cu atît poate detecta sau tolera mai multe erori.
Redundanța temporală
constă în folosirea aceluiași dispozitiv pentru a calcula același lucru în mod repetat, după care rezultatele sunt comparate între ele.

Erori tranziente și erori permanente

Putem clasifica defectele în două mari categorii:

Erori tranziente
sunt erori care se manifestă printr-o malfuncție temporară a unei componente, dar nu prin defectarea ei definitivă. În sistemele de calcul contemporane, cea mai mare parte a erorilor sunt tranziente.
Erori permanente:
se produc la un moment dat și persistă pînă cînd sistemul este reparat. În această categorie includem și defectele din fabricație.

După cum vă puteți imagina, redundanța temporală poate fi folosită numai pentru a tolera defecte tranziente. Pentru a tolera efecte permanente trebuie să avem o formă de redundanță spațială.

Costul fiabilității; sisteme echilibrate

Cînd proiectăm un sistem complex este foarte important să ``echilibrăm'' fiabilitatea părților. De exemplu, dacă memoria unui sistem are o fiabilitate mult mai mare decît procesorul, atunci sistemul se va defecta cel mai adesea cu probleme de procesor. Faptul că memoria este de foarte bună calitate nu ne ajută cu nimic; dimpotrivă, probabil că am plătit un preț mai mare pentru memorie decît ar fi fost strict necesar. În general, o componentă este ``destul de bună'' dacă nu are cea mai mare probabilitate de defectare.

Întotdeauna cînd discutăm despre fiabilitate trebuie să socotim nu numai costul componentelor fiabile, ci și costul întreținerii sistemului. Cît pierdem pe oră atunci cînd sistemul nu funcționează? Dacă cumpărăm componente foarte fiabile plătim prea mult pentru construcția sistemului, dar dacă cumpărăm componente cu fiabilitate prea redusă, ne va costa prea mult întreținerea sistemului. Numai contextul poate dicta cît de fiabil trebuie să fie un sistem: de exemplu, în aplicațiile critice descrise mai sus, costul ne-funcționării sistemului este uriaș, așa încît are sens să investim în componente extrem de fiabile.


Creșterea fiabilității

În această secțiune voi discuta cîteva tehnici folosite pentru a construi sisteme de calcul fiabile.

Evitarea defectelor

Evitarea defectelor este o metodologie idealizată, care presupune că toate componentele sunt perfecte. Pentru că hardware-ul de astăzi are o calitate excepțională, nivelul software în calculatoarele obișnuite adoptă o astfel de viziune idealizată. Programatorii presupun că sistemul pe care se rulează programele lor este lipsit de defecțiuni.

Fiabilitatea excelentă a dispozitivelor hardware este obținută printr-o combinație de tehnici, cum ar fi felurite forme de redundanță, proiectare și fabricație cu precizie foarte ridicată, și o fază agresivă de testare și ``ardere'' (burn-in).

Empiric s-a observat că sistemele tind să aibă o mortalitate care urmărește o curbă numită albie, ilustrată în figura 1: sistemele foarte tinere și cele foarte uzate se strică mult des decît sistemele ``mature''. ``Burn-in'' este o fază de testare care folosește componentele pînă devin mature; în acest fel, componentele cu mortalitate infantilă ridicată sunt eliminate.

În plus fabricanții proiectează și testează sisteme de calcul în condiții mai nefavorabile decît cele specificate. De exemplu, pe acest fapt se bazează cei care fac ``overclocking'': specificațiile unui procesor indică frecvența de ceas la care acesta poate opera. Dar în mod frecvent un procesor cu specificație de ceas de 1Ghz poate opera la 1.2Ghz, datorită marginilor de toleranță din fabricație.

Figura 1: Graficul ratei de eroare a unui dispozitiv în funcție de vîrsta sa are adesea forma de albie: dispozitivele foarte noi și foarte vechi au o probabilitate mai mare de a se defecta.
\begin{figure}\centerline{\epsfxsize=7cm\epsffile{albie.eps}}\end{figure}

Metoda evitării defectelor este cu adevărat extremă. În restul acestui text vom vedea metode mai pesimiste, care recunosc că fiecare din componente se poate defecta și încearcă se mențină sistemul în funcționare; această paradigmă se numește ``toleranța defectelor'' (fault-tolerance).

Scheme de votare

O metodă foarte simplă dar scumpă de a tolera erori este de a multiplica fiecare componentă. De exemplu, dacă duplicăm întreg sistemul de calcul, apariția unui defect poate fi detectată comparînd rezultatele celor două subsisteme.

Prima schemă de toleranță a defectelor a fost propusă de John von Neumann în 1956 și se numește ``redundanță modulară triplă'' (Triple Modular Redundancy). În această schemă trei module fac aceeași operație și un modul de ``vot'' alege rezultatul majoritar. Dacă fiecare componentă are o fiabilitate de peste 50%, fiabilitatea ansamblului este mai mare decît a componentelor. Există și scheme în care sistemul de votare este replicat, pentru a nu depinde de o singură componentă.

Un astfel de sistem de votare este folosit în calculatoarele care controlează naveta spațială: sistemul este compus din cinci calculatoare, din care patru fac aceleași calcule și al cincilea este folosit pentru operațiuni ne-critice. Rezultatele celor patru calculatoare se duc pînă la sistemele controlate (motoare), care calculează local rezultatul votului. În plus, fiecare calculator compară rezultatele cu celelalte trei; cînd unul dintre ele dă rezultate diferite este scos din funcțiune.

Dacă două calculatoare se defectează sistemul intră într-un mod de funcționare în care rezultatele sunt comparate și recalculate cînd diferă. Al cincilea calculator conține un sistem de control complet separat, dezvoltat de altă companie, care intră în funcțiune cînd un bug identic este detectat în celelalte patru programe (această metodă va fi prezentată în secțiunea 5.0.2).

Procesorul IBM G5 din sistemul S/390

În această secțiune vom discuta un tip de redundanță hibridă, care folosește redundanța spațială pentru a detecta erori tranzitorii și redundanța temporală pentru a le remedia. Acest sistem este asemănător cu modul de funcționare cu două defecțiuni folosit de naveta spațială, descris mai sus. Această tehnică e utilizată în multe sisteme comerciale, dar noi vom discuta microprocesorul G5 folosit de compania IBM în calculatoarele sale mainframe.

Microprocesorul G5 conține două benzi de execuție identice, care sunt controlate de același ceas. Toate instrucțiunile sunt executate în mod sincron de ambele benzi, iar la sfîrșitul benzii rezultatele sunt comparate. Dacă rezultatele sunt identice, rezultatul instrucțiunii este scris în registrul destinație sau în memorie. Dacă nu, se generează o excepție software, care de obicei se soldează cu re-execuția instrucțiunii-problemă. Erorile tranziente sunt astfel reparate în mod transparent. Această schemă este funcțională pentru că probabilitatea ca o eroare tranzientă să afecteze ambele benzi în același fel este foarte foarte mică.

Calculatorul S/390 folosește redundanța în multe alte feluri: toate sursele de curent, sistemele de răcire, discurile, etc., sunt duplicate. Sistemul nu are un singur punct critic. Acesta este deci un sistem echilibrat: ce sens ar avea un microprocesor deosebit de fiabil dacă sursa de curent se poate arde adesea?

Un procesor superscalar tolerant la erori tranziente

O schemă foarte originală care folosește doar redundanță temporală pentru a tolera erori tranziente a fost propusă anul acesta la conferința de microarhitectură MICRO 2001 de un grup de cercetători de la universitatea Carnegie Mellon. În această schemă, unui procesor superscalar obișnuit i se fac cîteva modificări simple, astfel încît fiecare instrucțiune citită să fie lansată în execuție în mod repetat. Mecanismele de redenumire a regiștrilor folosite în procesorul superscalar fac executarea unor instrucțiuni suplimentare, care nu afectează sistemul, un lucru foarte simplu. La sfîrșitul benzii de asamblare rezultatele copiilor lansate în execuție sunt comparate între ele. Robustețea depinde de gradul de redundanță: dacă fiecare instrucțiune este executată de două ori, o eroare se manifestă prin rezultate diferite și instrucțiunea trebuie re-executată; dacă o instrucțiune este executată de mai mult de două ori, se poate folosi o schemă de votare cu majoritate.

Un astfel de procesor poate fi proiectat să lucreze fie în mod normal, fie în mod cu fiabilitate crescută, depinzînd de tipul de program executat. Performanța în modul cu fiabilitate ridicată este invers proporțională cu gradul de redundanță; de exemplu, dacă fiecare instrucțiune este executată de două ori, ne-am aștepta la o scădere a vitezei de calcul la 50%. In realitate, penalizarea este ceva mai mică, din cauză că un program nu folosește toate resursele computaționale. De exemplu, dacă un program folosește 80% din resurse, cind executam programul duplicînd fiecare instrucțiune avem nevoie de 160% resurse, ceea ce se traduce într-o degradare a performanței cu 37,5% (100/160 = 62,5 = 100 - 37,5).

DIVA

O schemă deosebit de interesantă de redundantă spațială a fost propusă în aceeași conferință în 1999 de către Todd Austin, profesor la universitatea Michigan. Acest proiect e numit DIVA, de la Dynamic Implementation Verification Architecture: arhitectură cu verificare dinamică.

Spre deosebire de schemele anterioare, DIVA e proiectată pentru a tolera atît erori tranziente, cît și permanente (cele din urmă doar în anumite părți ale sistemului). Observația centrală pe care se bazează DIVA este că e mai ușor de verificat dacă rezultatul unui calcul e corect decît este de efectuat calculul însuși. Ca atare, arhitectura DIVA este compusă din două procesoare diferite:

Figura 2: Procesorul DIVA este compus dintr-un procesor performant care efectuează calculele și un procesor lent și foarte robust care le verifică corectitudinea.
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{diva.eps}}\end{figure}

Procesorul DIVA funcționează astfel:

Procesorul complex execută toate instrucțiunile și calculează rezultatele lor. Rezultatele însă nu sunt scrise, ci sunt transmise procesorului simplu.

Procesorul simplu merge ceva mai încet, și verifică în paralel toate detaliile rezultatelor primite. Deși acest procesor este mai simplu, are o treabă mai ușoară, și ca atare poate atinge aceeași performanță ca cel rapid (exprimată în instrucțiuni procesate pe secundă). Cînd verificarea descoperă o eroare, procesorul simplu calculează rezultatul corect și re-pornește procesorul complex de la instrucțiunea următoare.

Foarte interesant este că o arhitectură DIVA poate tolera chiar erori de proiectare în procesorul foarte complicat, pentru că acestea sunt detectate și corectate de procesorul lent și simplu. Poate fi chiar avantajos ca procesorul rapid să fie proiectat ``incorect'', dar extrem de rapid, în cazul în care nu produce rezultate eronate prea frecvent. De exemplu, într-un procesor normal foarte multe circuite suplimentare sunt introduse pentru a trata corect cazul programelor care se auto-modifică. În realitate, practic nici un program modern nu folosește această tehnică în mod curent; procesorul rapid fără aceste circuite poate fi făcut mult mai eficient. Corectitudinea va fi asigurată de procesorul lent.

Coduri detectoare și corectoare de erori

Am văzut deja mai multe exemple de folosire a redundanței spațiale pentru detectarea și corectarea erorilor. Costul schemelor prezentate mai sus este substanțial: ele cer o replicare identică a unui întreg sistem. De exemplu, redundanța modulară triplă are o eficiență de 33%, pentru ca hardware-ul este replicat de trei ori.

E interesant de explorat dacă nu putem obține aceleași beneficii cheltuind mai puține resurse suplimentare. Deschizători de drumuri au fost în această privință Claude Shannon și Richard Hamming, spre sfîrșitul anilor '40. Vom discuta despre metodele propuse de ei pentru a stoca informație în mod fiabil.

Să presupunem că vrem să stocăm niște informații codificate în baza doi într-un mod fiabil. Putem atunci de pildă face două copii ale informației. Dar o defecțiune a unui singur bit va face informația de nerecuperat, pentru că acel bit va fi diferit în cele două copii, și nu putem deduce care este valoarea originală. Slăbiciunea acestei metode constă în faptul că biții stocați nu sunt ``robuști'': fiecare bit din mesaj este reprezentat în doar doi biți din cod. Dacă ``amestecăm'' biții din mesaj putem face mult mai bine de atît.

Pentru a obține reziliență la erori trebuie să adăugăm redundanță în cod; astfel, vom codifica n biți de informație folosind m > n biți de cod. Cu cît m e mai mare ca n, cu atît mai robust va fi codul nostru. Cuvintele de m biți care reprezintă coduri corecte se numesc ``cuvinte de cod'' (code words). Observați că nu toate cuvintele de m biți sunt cuvinte de cod, ci numai 2n dintre ele.

Putem defini distanța Hamming între două șiruri de biți ca fiind numărul de diferențe între cele două șiruri. De exemplu, distanța Hamming dintre 1111 și 1010 este 2, pentru că cele două șiruri diferă în pozițiile a doua și a patra. Cea mai mică distanță Hamming dintre cuvintele unui cod este o măsură foarte bună a robusteții codului. De exemplu, dacă distanță Hamming între oricare două cuvinte este mai mare decît 3, atunci o schimbare de 1 bit poate fi întotdeauna corectată: cel mai apropiat cuvînt de cod este cel care a fost modificat de eroare, pentru că toate celelalte cuvinte de cod se vor afla la o distanță mai mare de 2 de cuvîntul eronat. Astfel, un cod cu distanță Hamming 3 poate corecta orice eroare de 1 bit, și poate detecta orice eroare de doi biți. Un astfel de cod va detecta și alte erori, de exemplu va detecta unele erori de trei biți, dar nu orice eroare de trei biți.

Există efectiv zeci de coduri diferite, fiecare potrivit în alte circumstanțe. Vom prezenta niște exemple în ceea ce urmează.

Memorii

Dacă ați cumpărat vreodată memorie pentru PC-ul dumneavoastră, v-ați lovit desigur de dilema ``care tip de memorie trebuie cumpărat''. Din punct de vedere al fiabilității, există trei tipuri de memorie pe piață: memorii neprotejate, memorii cu paritate și memorii ECC.

Memoriile neprotejate
stochează fiecare bit de date în mod separat și nu oferă nici o protecție împotriva erorilor. Ca atare sunt cele mai ieftine. Cum însă dimensiunea memoriilor a crescut foarte repede, la ora actuală această soluție este riscantă, căci probabilitatea ca nici un bit să nu se defecteze este foarte redusă.
Memoriile cu paritate
folosesc o metodă foarte simplă pentru a detecta erori de un bit în fiecare octet (și, în general, erori care schimbă un număr impar de biți). Pentru fiecare 8 biți de date aceste memorii stochează un al nouălea bit de paritate, a cărui valoare este calculată astfel încît oricare cuvînt de nouă biți are un număr par de biți ``1'' (de aici și numele schemei).

Cînd hardware-ul accesează memoria, automat verifică și paritatea. Dacă paritatea nu este corectă se declanșează o excepție și sistemul de operare decide cum trebuie să acționeze. O soluție este de a omorîprogramul care folosea acea memorie și de a marca memoria ca fiind defectă, astfel încît alte programe să nu o poată refolosi. Verificarea parității este o operație foarte rapidă, care se poate face foarte simplu în hardware în paralel cu transferul informației.

Memoriile ECC
sunt protejate cu un cod sofisticat de corecție a erorilor (Error Corecting Code). Acest cod poate corecta automat orice eroare de 1 bit care apare într-un cuvînt de 64 de biți. Pentru acest scop memoria stochează fiecare cuvînt de 64 de biți folosind cuvinte de cod de 72 de biți. Observați că ``risipa'' (overhead) acestei scheme este aceeași cu cea a parității (9/8 = 72/64); această schemă oferă corecție cu o robustețe mai mică, pentru că poate corecta o eroare la 64 de biți, spre deosebire de cealaltă schemă care poate detecta o eroare la 8 biți.

La fiecare acces la memorie hardware-ul verifică dacă cuvîntul de cod este corect; dacă nu automat calculează cel mai apropiat cuvînt de cod pe care apoi îl decodifică. Aceste operații sunt destul de complicate, astfel încît un sistem cu memorii ECC merge cu aproximativ 5% mai lent dec'it unul cu memorii cu paritate.


Discuri

Cel mai comun suport persistent de informație este discul, în multiplele lui încarnări: hard disc, dischetă, disc optic, compact-disc, etc. Informațiile din această secțiune sunt valabile pentru multe din aceste tipuri de discuri.

Discurile folosesc simultan două metode diferite de redundanță spațială; o protecție sporită este necesară din cauză că discurile funcționează într-un mediu mult mai aspru decît memoriile: discurile au părți mecanice în mișcare, care se uzează și se pot strica mai ușor.

Informația este stocată pe disc în sectoare. Un sector este relativ mare (comparat cu un cuvînt de memorie), fiind de ordinul a jumătate de kilooctet (512 octeți). Discurile folosesc sectoare mari pentru că la viteza lor de rotație (peste 5000 de revoluții pe minut) capetele de citire/scriere nu se pot plasa foarte precis pe suprafață. Astfel, unitatea elementară în care se scrie pe un disc este sectorul: chiar dacă vrem să modificăm un singur bit, trebuie să rescriem tot sectorul.

Figura 3: Formatul unui sector de disc: informația servo este folosită pentru controlul mișcării capului, identificatorul indică numărul sectorului curent, informația de sincronizare este folosită pentru a sincroniza poziția capului cu începutul sectorului; datele sunt stocate într-un șir compact, codificate folosind un cod detector de erori. Între două sectoare consecutive este o gaură, care-i dă capului ceva libertate cînd rescrie sectorul (niciodată nu va rescrie începînd chiar din același loc).
disc

Codurile folosite pentru discuri se numesc CRC, de la Cyclic Redundancy Check: coduri ciclice. Un cuvînt de cod constă din chiar cuvîntul de date urmat de informații de control; decodificarea codurilor CRC este foarte simplă: se extrage direct cuvîntul de date. Codul de control verifică dacă vreunul din biții stocați e incorect. Un cod ciclic are proprietatea că orice permutare a datelor este protejată de același cuvînt de control.

Cînd codul de control indică defectarea unui sector, discurile folosesc în mod automat a doua formă de redundanță spațială: sectoare de rezervă. Pe disc sunt ascunse sectoare invizibile, care sunt folosite atunci cînd sectoarele de date încep sa dea rateuri. În mod transparent software-ul alocă un sector de rezervă în locul unuia defect. Identificatorul de sector este folosit pentru a indica cine pe cine înlocuiește.

Discurile stochează o hartă de defecte care indică sectoarele înlocuite; asta le permite să funcționeze și după ce apar defecțiuni, și permite de asemenea un proces de fabricație mai imperfect și mai ieftin.

Turbo-coduri

Codurile detectoare și corectoare de erori sunt folosite pe larg în rețelele de calculatoare. Am scris cu alte ocazii în PC Report despre acest subiect, astfel încît în această secțiune voi discuta despre un caz extrem.

Depinzînd de caracteristicile canalului de comunicații (distanță, cost de transmisiune, viteza semnalului, zgomot) se pot folosi coduri mai mult sau mai puțin robuste. În anumite cazuri e preferabil ca erorile să fie detectate și datele incorecte să fie retransmise, în alte cazuri costul retransmisiei este prea mare, și ca atare se folosesc coduri corectoare. Folosirea unui cod corector în transmisiunea de date se mai numește și codare preventivă (Forward Error Correction).

Pentru comunicația cu sondele spațiale se folosesc coduri corectoare de erori extrem de robuste, pentru că la astfel de distanțe semnalul electromagnetic are nevoie de multe minute pentru a se propaga. În 1993 un grup de cercetători francezi a inventat o clasă de coduri extrem de robuste, numite Turbo-coduri, care folosind o redundanță relativ redusă, de 200% ob'tin o rezilien't'a excep'tional'a la zgomot, fiind foarte aproape de limitele maxime teoretice.

Turbo-codurile ilustrează un nou tip de compromis pe care arhitectul îl poate face în ecuația robustețe/cost: costul cel mare al unui turbo-cod nu este în cantitatea mare de informație suplimentară, ci în algoritmul de decodificare, care este foarte complicat și necesită multe iterații. După cum am văzut și în cazul memoriilor, cu aceeași redundanță putem obține garanții diferite de fiabilitate, în funcție de algoritmul de codificare folosit. În cazul comunicației interplanetare costul transmisiunii face costul decodificării insignifiant, deci turbo-codurile sunt potrivite.

RAID

În această secțiune voi ilustra un alt tip de sistem fiabil redundant, care, spre deosebire de alte soluții prezentate, are o performanță mai bună decît sistemul de bază. În plus, acest sistem adaugă o dimensiune nouă în spațiul opțiunilor fiabilității, și anume capacitatea de a fi reparat în timp ce funcționează (maintainability).

RAID este o prescurtare de la Redundant Array of Inexpensive Disks, sau set redundant de discuri ieftine. Ideea a fost introdusă în 1987 de cercetători de la universitatea Berkeley din California, și la ora actuală este obiectul unei industrii anuale de 12 miliarde de dolari.

Ideea centrală în RAID este de a stoca informație pe mai multe discuri simultan. Informația este codificată redundant, astfel încît să poată fi recuperată dacă oricare din discuri se defectează. Această proprietate este foarte utilă pentru sisteme care trebuie să funcționeze în foc continuu.

Observați că tipul de defecțiune pe care RAID o adresează este diferit de cel descris în secțiunea 3.6.2: aici vrem să operăm cînd un disc este complet distrus, acolo ne interesa să detectăm alterații ale informației stocate. Într-un sistem RAID toate aceste tehnici operează simultan: fiecare disc folosește coduri CRC și sectoare de rezervă, iar sistemul RAID folosește stocare a informației redundantă.

Există mai multe tipuri de sisteme RAID, dar aici vom discuta unul singur, în care informația este scrisă pe 5 discuri, din care 4 conțin date și unul paritate.

Un astfel de sistem RAID se poate afla într-unul din trei moduri de funcționare:

Funcționare normală:
operațiile de citire extrag date de pe cele patru discuri cu date. O operație de scriere însă strînge patru blocuri de informație și calculează un al cincilea bloc de paritate; fiecare bloc este stocat pe alt disc. Acest mod de scriere se numește ``striping'', adică ``feliere'', pentru că datele sunt scrise în paralel, cîte o felie pe fiecare disc.
Funcționarea degradată:
este începută cînd un disc se defectează. Atunci citirile și scrierile de pe discul stricat trebuie să acceseze celelalte patru discuri și să calculeze informația lipsă. Avantajul parității este că oricare din biții lipsă poate fi recalculat ca paritatea celorlalți patru biți.
Reconstrucția:
este începută cînd un disc defect este înlocuit. Un proces secundar recalculează informația lipsă și o scrie pe noul disc.

[Restul acestui articol va fi publicat în numărul din februarie]


Rezumat

În numărul anterior din Net Report am publicat prima parte a unui articol despre fiabilitatea sistemelor de calcul. Iată aici rezumatul ideilor importante:

Fiabilitatea programelor

Ne-am putea aștepta, în mod naiv, ca, spre deosebire de hardware, software-ul să nu aibă nici un fel de probleme de fiabilitate: în definitiv programele nu se uzează, și sunt executate într-un mediu foarte specializat; în plus, programele sunt obiecte deterministe, deci ar trebui să se comporte de fiecare dată în același fel cînd procesează aceleași date de intrare. Cu toate acestea, de fapt fiabilitatea programelor este mult mai scăzută decît a sistemelor hardware; este potrivit să modelăm deci programele ca sisteme cu fiabilitate imperfectă. În această secțiune discutăm în mod superficial unele dintre motivele lipsei de fiabilitate a programelor și menționăm unele tehnici care pot fi folosite pentru a ``întări'' programele.

Cea mai importantă cauză a malfuncțiilor programelor sunt bug-urile, adică implementări incorecte. Chiar și programatori foarte pricepuți produc programe cu defecte. Nu exagerăm deci dacă afirmăm că nu există nici un program substanțial fără bug-uri, așa cum nu există vreo carte tipărită care să nu aibă erori tipografice. Complexitatea componentelor software este pur și simplu prea mare pentru a putea fi stăpînită de către oameni, și cu tot progresul în tehnici de programare, cum ar fi descompunerea programelor în module mici, folosirea unor limbaje de programare evoluate și a unor scule complexe pentru dezvoltarea, testarea și analiza programelor, rezultatele sunt încă foarte departe de perfecțiune, și productivitatea programatorilor nu a crescut substanțial în ultimele două decenii.

Cel mai adesea problemele rezolvate în software sunt atît de complicate încît nici nu pot fi specificate în mod precis. În consecință programatorii întîlnesc tot felul de incertitudini cînd încearcă să implementeze soluțiile. O cauză fundamentală a lipsei de fiabilitate a programelor este deci specificația incompletă și imprecisă.

Cele mai insidioase defecțiuni software se manifestă numai cu ocazia unor anumite combinații de valori pentru datele de intrare sau pentru anumite succesiuni de evenimente externe, care nu au fost prevăzute de programator. Asemenea combinații apar cu probabilitate foarte mică în timpul procedurilor normale de testare, deci adesea supraviețuiesc pînă în faza operațională.

Biți ``putrezi''

A vedea programele software ca pe o entitate monolitică este o aproximare grosolană a realității: un program trece prin nenumărate revizii și îmbunătățiri, cum pot mărturisi cei care sunt forțați periodic să facă ``upgrades''. Versiunile noi sunt construite pe scheletul celor vechi, reparînd defecțiunile descoperite și adăugînd noi funcționalități. Cu toate acestea, procesul reparării defecțiunilor introduce adesea noi defecțiuni, pentru că efectele unei reparații au uneori consecințe nebănuite.

Uluitoarea creștere a performanței hardware-ului este o motivație constantă pentru reînnoirea sistemelor software. Pe măsură ce dispozitivele hardware devin mai ieftine și mai compacte, ele pot fi integrate în dispozitive electronice mai ``deștepte''. Toate aceste noi dispozitive au nevoie de nou software care să le manipuleze. Pe măsură ce costul dispozitivelor de stocare a informației scade, din ce în ce mai complexe și bogate tipuri de informație pot fi stocate și prelucrate. De exemplu, imagini și muzică sunt tipuri curent manipulate de PC-urile contemporane, și capacitatea lor de prelucrare a devenit de curînd suficient de puternică pentru a manipula în mod interactiv filme.

Un fenomen legat de acest ciclu permanent de înnoiri este ``putrezirea biților'' (bit rot). Acest fenomen se manifestă pe două planuri: datele stocate cu mult timp în urmă nu mai pot fi folosite în noile sisteme de calcul, pentru că dispozitivele periferice învechite nu mai sunt suportate de fabricanți, și programe vechi, care mergeau foarte bine, încep să manifeste erori. ``Boala'' programelor este legată de mediul în care programele se execută, și care este în continuă schimbare. De exemplu, multe programe vechi făceau anumite presupuneri despre cît de mari vor fi seturile de date pe care le vor prelucra. Cea mai faimoasă astfel de presupunere este cea care a cauzat bug-ul Y2K: programatorii din anii '60 au presupus că programele lor nu vor manipula niciodată date calendaristice al căror an nu va începe cu cifrele 19. Chiar dacă Y2K a făcut mai mult zgomot decît pagube, astfel de presupuneri se întîlnesc la tot pasul în programele de astăzi. De exemplu, auzim adesea despre dificultatea de a transporta programe de la procesoare pe 32 de biți la procesoare pe 64 de biți. Din moment ce orice valoare pe 32 de biți se poate reprezenta exact atunci cînd folosim 64 de biți, teoretic nu ar trebui să fie nici o problemă, și vechile programe ar trebui să funcționeze corect. În realitate multe programe depind în feluri subtile de precizia datelor pe care le manipulează. Cînd un astfel de program este mutat pe o platformă nouă toate aceste dependințe se transformă în bug-uri.


Programare cu N versiuni

Domeniul ingineriei programelor (software engineering) se ocupă de metode prin care se poate cuantifica și îmbunătăți calitatea programelor. Una dintre soluțiile studiate este foarte înrudită cu tehnicile de votare folosite pentru toleranța erorilor hardware, care au fost prezentate în prima parte a acestui text. Numele acestei soluții în lumea software este ``programare cu N versiuni''. Votarea folosește redundanță spațială: dispozitivul de calcul este replicat de N ori și rezultatul final este obținut prin votul majoritar al rezultatelor individuale.

Bug-urile software sunt persistente: aflat în aceleași condiții programul se va comporta în același fel. Tehnicile de votare sunt neputincioase dacă toate componentele fac aceeași eroare în același timp. Votarea este utilă pentru tratamentul erorilor tranziente. Programarea cu N versiuni se face deci prin executarea în paralel a N programe diferite, scrise de echipe diferite de programatori, dacă e posibil, folosind scule și tehnologii diferite. Toate cele N programe rezolvă aceeași problemă, dar în moduri diferite. Numai folosind o astfel de strategie tehnica votării poate funcționa în cazul programelor.

Specificații imprecise ale problemei pot fi detectate cu ușurință de această tehnică, pentru că implementările diferite pot lua decizii diferite pentru cazurile nespecificate clar. Din nefericire, programarea cu N versiuni este o metodologie foarte scumpă, folosită numai pentru aplicații critice, unde siguranța este fundamentală.

Întinerirea programelor

Diferența fundamentală între hardware și software este că un program poate avea o stare internă arbitrar de complicată. În general, dispozitivele hardware pot fi aproximate ca fiind automate finite (adică spațiul stărilor în care se pot afla, chiar dacă este foarte mare, este totuși finit). Chiar și cele mai simple programe au un spațiu de stări infinit, mai exact, nu putem pune nici o limită arbitrară dimensiunii spațiului lor.

Această diferență este foarte importantă și din punct de vedere teoretic: foarte multe proprietăți interesante ale automatelor finite sunt decidabile, adică se pot scrie algoritmi care, atunci cînd primesc descrierea unui automat finit, pot răspunde în mod exact la întrebări legate de orice evoluție viitoare a automatului. Din păcate, aceleași întrebări pentru un sistem cu stare infinită sunt adesea nedecidabile. Într-adevăr, matematicienii au arătat în anii '30 că foarte multe dintre proprietățile unui sistem software în general nu pot fi calculate de un alt sistem software.

O consecință practică a dimensiunii infinite a spațiului de stări al programelor este că, pe măsură ce un program se execută mai mult timp, cu atît mai complicată poate deveni starea sa internă. Dacă un program nu își întrerupe execuția, chiar dacă va primi aceleași date la intrare, ar putea calcula un răspuns diferit. Un bug în program poate corupe starea internă, dar efectele acestei stricăciuni pot deveni vizibile mult mai tîrziu în execuția programului, cînd programul ia o decizie bazată pe elementele de stare incorecte. Un tip faimos de problemă, în mod normal benignă, asociată cu programele care se execută un timp îndelungat, este scurgerea de memorie (memory leak).

Adesea programele alocă spațiu temporar de memorie, pe care îl eliberează după ce au terminat calculele care aveau nevoie de el. Dacă programatorul uită să elibereze această memorie se spune că memoria se scurge (leak). Aceasta este o eroare frecvent întîlnită în programare, relativ greu de descoperit. În mod normal o astfel de eroare nu afectează corectitudinea programului: rezultatele produse la final sunt corecte. Cînd programul își termină execuția, sistemul de operare recuperează automat memoria scursă. În cazul programelor care se execută timp îndelungat, cum ar fi sistemele de operare sau servere de web, dacă o scurgere se întîlnește în interiorul unei bucle, cu timpul memoria pierdută va crește pînă cînd toată memoria sistemului este pierdută. În astfel de cazuri de obicei sistemul își încetează execuția sau funcționarea sa devine extrem de lentă, din cauză că resursele rămase sunt insuficiente.

Utilizatorii sistemului de operare Windows de la Microsoft au descoperit și o soluție pentru această problemă: reboot-area calculatorului. Numele științific pentru această soluție este ``reîntinerirea programelor'' (software rejuvenation). Reîntinerirea este cauzată de repornirea periodică a programelor. Repornirea cauzează inițializarea stării interne la o aceeași valoare inițială. Tehnica aceasta este aplicabilă numai dacă starea internă a programului nu este importantă și poate fi pierdută; altfel, întinerirea trebuie să fie combinată cu ``checkpoint''-uri. Un checkpoint salvează informația importantă pe un mediu de memorie persistent, și o restaurează după ce programul este repornit.

Reîntinerirea se aplică cu precădere programelor de tip server, care execută tot timpul o buclă, acceptînd cereri de la clienți și răspunzîndu-le. Multe servere sunt lipsite de stare (stateless), adică nu păstrează nici un fel de informații despre o tranzacție cu un client după ce tranzacția s-a consumat. Reîntinerirea este eficace dacă costul repornirilor periodice este mai redus decît costul repornirii după o cădere catastrofică, care poate să implice o procedură sofisticată de recuperare a datelor pierdute. Reîntinerirea este de asemenea folosită cu succes cînd serverele care oferă serviciul au rezerve, astfel încît servere de rezervă pot răspunde clienților în timp ce altele se reinițializează.

Verificare formală

Verificarea formală este un nume generic pentru o serie întreagă de tehnici sofisticate care certifică corectitudinea, mai ales a sistemelor hardware, dar în ultima vreme și a unor sisteme software. Verificarea formală se ocupă de descoperirea și eliminarea bug-urilor, și în acest sens este o tehnică de creștere a fiabilității programelor.

Cheia metodelor de verificare formală este specificarea foarte precisă a comportării componentelor sistemului de analizat (folosind formule matematice) și verificarea automată a proprietăților sistemului în întregime. Dacă știm cum este construit sistemul, și dacă știm comportarea fiecăreia din componente, putem raționa despre comportarea ansamblului. Raționamentele pot fi făcute foarte precise folosind diferite variante de logici matematice. Fiecare raționament este o serie de derivări, în care din fapte știute ca fiind adevărate deducem alte adevăruri. Verificarea formală studiază aceste derivări, și verifică faptul că sunt corecte.

Două aspecte fac verificarea formală o tehnică foarte puternică: (1) calculele minuțioase sunt efectuate de către calculatoare, a căror atenție nu obosește niciodată, (2) certitudinea nu vine din faptul că demonstrăm ceva, ci din faptul că putem verifica dacă demonstrația este corectă! Am menționat și în prima parte a acestui articol, cînd am descris sistemul DIVA, că a verifica corectitudinea unui rezultat este mult mai simplu decît a demonstra rezultatul însuși. Acest fapt este extrem de folositor în contextul verificării formale, în care programul care face demonstrațiile este extrem de complicat, și ca atare poate conține erori (ca orice alt program complex) și deci genera demonstrații eronate. Un program care verifică dacă o demonstrație este corectă însă este mult mai simplu, și ca atare ne oferă mai multă încredere.

Expunerea defectelor

În secțiunile din numărul anterior al revistei, și în cele de mai sus, despre fiabilitatea programelor, am discutat despre tehnici care pot fi folosite în arhitectura calculatoarelor pentru a mări fiabilitatea pe care un nivel arhitectural o expune nivelelor superioare. Am observat că, cel mai adesea, nivelul hardware este perceput de nivelele superioare ca fiind ``perfect'', fără defecte. Am văzut o mulțime de mecanisme folosite în construcția hardware-ului pentru a oferi această iluzie.

În această secțiune voi discuta o metodă complet diferită, folosită cu mult succes în construcția a două sisteme complexe. Această tehnică pleacă de la asumpția că nivelul inferior este inerent nefiabil, și că în loc de a consuma resurse pentru a-i mări fiabilitatea, e preferabil să expunem lipsa sa de fiabilitate nivelelor superioare.

Raționamentul din spatele acestei decizii aparent paradoxale se bazează pe mai multe argumente:

Internetul

Una dintre cele mai uimitoare tehnologii a secolului douăzeci este cu siguranță Internetul. Acesta este o rețea de calculatoare, proiectată inițial pentru a conecta rețele militare de calculatoare și de a le permite să opereze chiar și în condițiile distrugerii unui mare număr de echipamente din rețea, în cazul unei conflagrații nucleare. Internetul a evoluat într-o rețea comercială care acoperă toate continentele, cu mai mult de 125 de milioane de calculatoare și peste 1 miliard de utilizatori.

Internetul nu este prima rețea de dimensiune globală; cu mai mult de un secol înainte de crearea Internetului a apărut telefonul; rețelele telefonice au cu siguranță întîietatea în acoperirea planetei. Ne-am aștepta ca proiectanții Internetului să fi folosit multe din tehnologiile folosite în construcția rețelelor telefonice, despre care există o cantitate mare de informații și o experiență substanțială. În realitate, nimic nu poate fi mai departe de adevăr: arhitectura Internetului pare a fi în mod deliberat opusă rețelei de telefonie. Nicăieri nu se vede mai bine diferența dintre cele două rețele decît în felul în care tratează fiabilitatea.

Rețeaua telefonică a fost proiectată dintru început pentru o fiabilitate excepțională. O centrală telefonică trebuie să însumeze mai puțin de trei minute de indisponibilitate în fiecare an. Numai în circumstanțe absolut excepționale o conversație inițiată poate fi întreruptă datorită unor probleme din rețea. Rețeaua telefonică va permite stabilirea unei legături numai după ce a rezervat toate resursele necesare pentru transmisiunea promptă a semnalelor vocale pe întregul traseu dintre cele două puncte care comunică. Standarde stricte dictează cît de mult timp poate dura faza de construcție a legăturii; dacă toate resursele nu pot fi obținute utilizatorul primește un ton de ocupat. Capacitatea rețelei este planificată atent pe baza unor statistici detaliate despre comportarea vorbitorilor astfel încît în condițiuni normale șansa obținerii unui ton de ocupat din cauza resurselor insuficiente din rețea să fie extrem de redusă.

Un factor crucial care garantează calitatea conexiunilor telefonice este prealocarea tuturor resurselor necesare înainte ca legătura să fie stabilită. Pornind de la numărul format, prima centrală telefonică calculează o secvență de centrale prin care semnalul trebuie să treacă pentru a lega apelantul cu apelatul; acest calcul se bazează pe tabele de rutare pre-calculate cu mare grijă și stabilite de către proiectanții rețelei. Fiecare centrală negociază apoi cu cea succesivă folosind un protocol sofisticat de semnalizare, și alocă capacitate pentru transportul datelor și pentru comutarea datelor (care în centrală leagă circuitul de intrare cu cel de ieșire). Cînd toate conexiunile punct-la-punct între centrale sunt stabilite se generează un ton de ``sunat''. Cînd conversația a fost inițiată, semnalul vocal este eșantionat și digitizat în prima centrală. Pentru fiecare bit din acest semnal s-a prealocat deja o cuantă periodică de timp pe fiecare din circuitele pe care le va traversa. Biții sunt transmiși unul cîte unul și traversează toate trunchiurile în aceeași ordine în care au fost generați, sosind la destinație la timp pentru a fi reasamblați și convertiți la loc într-un semnal auditiv. Din cauza prealocării, de îndată ce un bit intră în rețea, cu o probabilitate extrem de ridicată el va ajunge la celălalt capăt exact cînd trebuie. Cînd unul dintre vorbitori închide telefonul, protocolul de semnalizare intră din nou într-o fază complicată prin care eliberează toate resursele alocate la momentul apelului.

Internetul are o arhitectură fundamental diferită. Nu numai că nu există garanții despre timpul necesar pentru a ajunge de la emițător la receptor, dar nu există nici o garanție că datele nu sunt pierdute sau modificate în timpul transferului. Utilizatorii Internetului obțin un serviciu extrem de ``slab'', care poate fi enunțat pe scurt astfel: ``tu pui date în rețea și zici unde vrei să ajungă; rețeaua o să încerce să livreze datele acolo''.

Felul în care informația circulă în Internet este complet diferit de rețeaua telefonică: datele sunt divizate în pachete care sunt introduse în rețea în ordinea sosirii. Fiecare pachet poate călători pe o rută complet diferită pînă la destinație. Unele pachete se pot pierde, alte pot fi duplicate, și ele pot sosi la destinație în altă ordine decît au fost emise, sau chiar sparte în pachete mai mici.

Pachetele sunt plimbate prin Internet de un protocol numit IP, Internet Protocol. IP funcționează aproximativ astfel: cînd un calculator intermediar primește un pachet se uită întîi la adresa destinație înscrisă. Apoi el face niște calcule simple pentru a decide în ce direcție pachetul trebuie trimis, mai precis, căruia dintre vecinii săi trebuie să-i dea pachetul. Pachetul este apoi trimis vecinului. Dacă la un calculator intermediar pachetele vin mai repede decît apucă să le trimită mai departe, și dacă nici nu are unde să le stocheze pentru o vreme, are dreptul să le facă pierdute. Aceasta este principala cauză pentru care datele se pot pierde în Internet.

Spre deosebire de rețeaua telefonică, structura Internetului nu este controlată de un număr mic de companii, ci este în continuă schimbare, de la zi la zi și de la oră la oră, pe măsură ce noi calculatoare se conectează, noi utilizatori sună folosind modemuri, accidente întrerup conectivitatea și noi linii de transmisiune sunt instalate. Calculatoarele responsabile pentru transmiterea datelor, numite rutere, discută între ele permanent pentru a afla care este forma curentă aproximativă a rețelei. Aceste informații sunt utilizate în procesul de decizie care selectează vecinul folosit pentru transmisiunea fiecărui pachet spre destinație.

Dată fiind această infrastructură, este uimitor că Internetul funcționează cîtuși de puțin, și că informația ajunge cîteodată neperturbată la destinație. Fiabilitatea aplicațiilor din Internet este construită pe baza acestui mediu extrem de nefiabil, folosind două ingrediente:

Lipsa de stare (statelessness):
ruterele din Internet nu stochează nici un fel de informații despre traficul care le parcurge. (Prin contrast, în rețeaua telefonică, comutatoarele știu despre fiecare bit care le traversează de unde vine, unde se duce, și cînd succesorul lui va sosi.) Un ruter primește un pachet, calculează vecinul căruia să-i dea pachetul, și livrează pachetul. Starea internă a ruterului după livrarea pachetului este aceeași cu cea de dinainte. Așa cum am văzut în cazul reîntineririi programelor, lipsa stării interne face mult mai simplă repornirea unui ruter după o defecțiune. O defecțiune nu pierde informații vitale, care nu pot fi recuperate prin alte metode. De asemenea, lipsa stării face relativ ușoară sarcina altor rutere de a prelua traficul în cazul defectării unuia.

TCP:
este un protocol numit Transmission Control Protocol, care se execută deasupra protocolului IP. Dacă într-o rețea toate nodurile din interior execută IP, numai sursa și destinația execută TCP. TCP este protocolul care construiește o transmisiune fiabilă: el asigură că toate pachetele trimise ajung la destinație, fără lipsuri sau duplicate, în ordinea în care au fost trimise. TCP reușește această performanță folosind următoarele mecanisme:

Din cauză că pachetele cu confirmări se pot pierde la rîndul lor, unele pachete sunt injectate în mod repetat în rețea, ceea ce poate duce la livrarea unor duplicate; TCP trebuie le elimină folosind numerele de serie ale pachetelor.

Întregul Internet este construit pe nucleul nefiabil oferit de IP: nu numai datele și confirmările sunt trimise în mod nefiabil, dar chiar și mesajele de control schimbate între rutere, prin care află despre schimbările din topologia rețelei, și traficul folosit pentru monitorizarea și mentenanța rețelei folosesc aceleași mecanisme nefiabile de transmisiune.

În pofida structurii sale aparent șubrede, Internetul este un competitor formidabil al altor forme de distribuție a informației: radio, televiziune și telefonie. Costul transmisiunii vocii prin Internet este mult mai scăzut decît folosind rețelele specializate de telefonie. Multe companii importante de telefonie investesc în mod serios în echipamente care vor transporta voce peste protocolul IP.

De ce are Internetul atîta succes, în pofida lipsei sale de fiabilitate?

Răspunsul constă, în parte, în faptul că Internetul nu oferă un serviciu de fiabilitate costisitor de care poate aplicațtiile nu au nevoie. Rețeaua de telefonie face un efort substanțial pentru a oferi un serviciu de o fiabilitate foarte ridicată, dar sistemul folosit este foarte inflexibil și consumă o cantitate uriașă de resurse. Practic, fiabilitatea rețelei de telefoane costă prea mult.

Internetul mută problema fiabilității la un nivel superior, de la IP la TCP. TCP oferă o fiabilitate perfect adecvată pentru multe aplicații. TCP este executat numai de către calculatoarele terminale implicate în comunicație, și nu de către rutere. Ca atare algoritmii complicați folosiți de acest protocol nu taxează resursele rețelei, care scalează în mod natural la dimensiuni globale.

Mai mult: aplicații care nu au nevoie de livrarea fiabilă a datelor a lui TCP nu sunt obligate să folosească acest protocol. De exemplu, protocoalele folosite pentru posturile de radio din Internet folosesc coduri puternice de corecție a erorilor (discutate în prima parte a acestui articol) și nu au nevoie de retransmisii. Pachete pierdute sau întîrziate sunt pur și simplu ignorate. Acest lucru este acceptabil pentru că utilizatorul final, omul, tolerează semnale cu zgomot.

Figura:4 stînga: Procesul de plasare asociază fiecare poartă logică din circuitul de implementat cu o poartă universală. Procesul de rutare conecteaza' porțile universale folosind segmente de sîrmă legate cu comutatoare. dreapta: Dacă unele din porțile universale sunt defecte, plasarea și rutarea le pot ocoli, sintetizînd un circuit perfect funcțional.
\begin{figure}\centerline{\epsfxsize=12cm\epsffile{plasare-rutare.eps}}\end{figure}

Teramac

În această secțiune voi discuta pe scurt despre Teramac, un sistem de calcul dezvoltat de cercetători de la Hewlett-Packard care demonstrează o metodologie extremă în tratamentul fiabilității sistemelor. Acest calculator este construit din componente defecte: mai mult de 70% din circuitele sale componente au o malfuncție oarecare. Cu toate acestea, sistemul funcționează minunat și poate efectua calcule extrem de performante.

Să observăm că arhitectura Teramac tolerează numai defecțiuni permanente, care sunt prezente încă de la fabricație. Componentele Teramac sunt circuite hardware de un tip anume, numit hardware reconfigurabil. Înainte de a discuta sistemul Teramac voi face o prezentare succintă a structurii hardware-ului reconfigurabil și voi explica de ce un sistem fiabil poate fi construit din componente reconfigurabile nefiabile.

Hardware reconfigurabil

Într-o primă aproximație, circuitele digitale obișnuite sunt compuse din elemente computaționale simple, numite porți logice, conectate între ele prin sîrme. Porțile logice sunt construite din tranzistori. Fiecare poartă logică face calcule pe mai multe valori de 1 bit. Porțile logice sunt universale, în sensul că orice proces calcul poate fi exprimat în termeni de operații ale porților logice.

În hardware-ul reconfigurabil porțile logice nu au o funcționalitate fixată, iar sîrmele formează o grilă. Fiecare poartă este configurabilă, adică poate fi forțată să efectueze orice operație logică. La fiecare intersecție de sîrme se află un mic comutator configurabil, care poate fi de asemenea programat să conecteze sîrmele. Configurarea porților și a sîrmelor se face prin semnale electrice. Fiecare poartă și fiecare comutator are o mică memorie asociată, în care-și stochează configurația. Pentru că schimbînd conținutul acestor memorii putem schimba funcționalitatea hardware-ului, circuitele acestea se numesc ``reconfigurabile''.

Hardware-ul reconfigurabil este echivalent cu cel obișnuit, în sensul că orice circuit poate fi implementat folosind ambele tehnologii. Hardware-ul reconfigurabil tinde însă să fie mai ineficient: memoriile și porțile configurabile ocupă mult mai mult loc decît porțile obișnuite. Pe de altă parte, semnalele electrice care traversează doar sîrme într-un circuit obișnuit trebuie să treacă printr-o serie de comutatoare în hardware-ul reconfigurabil, ceea ce face circuitele mai lente. Un factor de 10 diferență în viteză și densitate este de așteptat între hardware obișnuit și cel configurabil de aceeași generație.

Pentru a programa un circuit reconfigurabil cu funcțiunea unui circuit obișnuit, trebuie să asociem fiecare poartă din circuit cu o poartă configurabilă; acest proces se numește ``plasare''; de asemenea, fiecare sîrmă trebuie asociată cu succesiuni de segmente legate prin comutatoare, în procesul de ``rutare''.

Fiabilitatea sistemului Teramac

Calitatea circuitelor reconfigurabile exploatată de Teramac pentru a obține fiabilitate este faptul că porțile logice configurabile sunt esențialmente interschimbabile. Cercetătorii proiectului Teramac au dezvoltat un program de plasare care folosește o hartă de defecte ale circuitelor reconfigurabile. Această sculă ocolește porțiunile inutilizabile și rutează conexiunile în jurul defectelor, exploatînd doar porțiunile funcționale ale fiecărui circuit. Cercetătorii au creat și o serie de scule care descoperă și cataloghează defectele. Sculele acestea folosesc chiar programabilitatea circuitelor pentru a le configura ca dispozitive care se auto-testează. Fiecare porțiune din fiecare circuit este programată se efectueze calcule simple și să verifice corectitudinea rezultatelor. Micile programe de test sunt ``plimbate'' pe suprafața circuitului, acoperind toate porțile logice. Proiectarea unor programe de auto-testare este o sarcină mai complicată decît ar putea părea la prima vedere. Programele trebuie să descopere o mulțime de defecte posibile și trebuie să nu poată fi păcălite de defecțiuni (de exemplu, dacă chiar partea care compară rezultatele cu cele corecte este defectă). Programele de testare aplică în mod repetat calcule care amestecă toți biții; astfel, apariția unei singure erori se va propaga rapid la toți biții din rezultat, fiind ușor de depistat.

Proiectul Teramac a avut un succes enorm, apărînd chiar pe prima pagină a unor ziare de mare tiraj. Principala sa contribuție a constat în a demonstra că defectele din hardware pot fi expuse nivelelor superioare, și pot fi tratate în întregime în software, fără ca costul plătit în performanță să fie prohibitiv. Această metodologie este o schimbare completă de paradigmă în arhitectura calculatoarelor, care probabil va avea din ce în ce mai multe aplicații în viitor.

Algoritmi aleatori

În această secțiune voi discuta o nouă direcție în gîndirea despre calculatoare, care acceptă lipsa de fiabilitate ca pe un lucru natural, chiar și la nivelele cele mai ridicate. E vorba de folosirea algoritmilor aleatori, care incorporează un element de șansă, și care, ca atare, nu se comportă întotdeauna la fel, ba chiar, cîteodată pot da răspunsuri eronate.

Teoria complexității ne învață că în general există un compromis între timpul de execuție al unui program și calitatea rezultatelor pe care le poate oferi. Pentru multe clase importante de probleme nu există algoritmi care să fie simultan rapizi și care găsesc soluția optimă.

Singura soluție în astfel de cazuri este să renunțăm la una dintre calități. Dacă nu avem suficient timp, va trebui să ne mulțumim cu soluții care nu sunt optime, dar poate sunt suficient de aproape de optim, presupunînd că le putem calcula rapid.

Cei mai spectaculoși algoritmi care au apărut folosesc evenimente aleatoare pentru a calcula răspunsurile rapid, dar pierd din precizie. Trebuie să ne imaginăm acești algoritmi ca avînd capacitatea să arunce un zar și în funcție de rezultat să facă o acțiune sau alta. Putem distinge două mari clase de astfel de algoritmi:

Algoritmii Monte Carlo
de obicei dau răspunsuri corecte, dar ocazional pot da un răspuns greșit. ``Ocazional'' trebuie citit ``cu probabilitate foarte mică''. Cu alte cuvinte, dacă ``zarurile'' nu ies mereu ``șase-șase'', algoritmul va da un răspuns corect, altfel rezultatul poate fi eronat. Algoritmii Monte-Carlo sunt folosiți pe larg în simularea fenomenelor fizice pe calculator, aproximînd calcule complicate prin eșantionare.
Algoritmii Las-Vegas
dau întotdeauna răspunsuri corecte. Cel mai adesea acești algoritmi se și execută rapid. Cu probabilitate foarte scăzută însă, ei ar putea să se execute pentru un timp foarte îndelungat. Un exemplu tipic de astfel de algoritm este ``quicksort'', care aranjează un șir de numere în ordine crescătoare. Quicksort alege (într-una din variantele sale) în mod aleator un ``pivot'', un element din șir, după care mută toate elementele mai mici decît pivotul la stînga și cele mai mari la dreapta și sortează în mod recursiv cele două șiruri obținute. Pentru cele mai multe alegeri ale pivotului timpul de execuție este scurt; dacă însă algoritmul are ghinion și alege mereu cîte un pivot aproape de valoarea maximă din șir, timpul de execuție este mult mai lung.

Amplificarea probabilităților

Foarte surprinzător este faptul că pentru unele probleme nu se cunoaște nici un algoritm eficient determinist, dar sunt cunoscuți algoritmi aleatori rapizi. Și mai surprinzător este faptul că astfel de algoritmi sunt folosiți pe scară foarte largă, fiind un pilon de bază al comerțului electronic!

Cum de ne bazăm pe algoritmi care știm că pot eșua?

Totul este o chestiune de valori ale probabilităților de eșec. Știm că orice sistem poate eșua; cu o probabilitate foarte mică se poate petrece un cutremur în următoarea oră, care poate strica un calculator oricît de solid. Dacă algoritmii aleatori au probabilități mai mici de atît, pînă la urma ei reprezintă un risc acceptabil.

Din fericire există metode pentru a scădea probabilitatea de eroare a unui algoritm aleator. Aceste metode sunt asemănătoare cu metodele care cresc fiabilitatea sistemelor hardware, prezentate în prima parte a acestui articol, folosind redundanța.

O metodă foarte similară cu redundanța temporală este folosită pentru a amplifica probabilitatea de succes a algoritmilor Monte-Carlo. Această metodă pur și simplu execută algoritmul în mod repetat și alege rezultatul folosind un vot majoritar. Probabilitatea ca majoritatea instanțelor algoritmului să eșueze scade foarte repede cu numărul de repetiții (exponențial de repede), și poate fi adusă practic la o valoare oricît de mică.

Criptografie

Importanța criptografiei pentru societatea modernă nu poate fi supraestimată. Timpurile cînd criptografia era apanajul armatelor este de mult apus. De fiecare dată cînd tastați o parolă într-un calculator, folosiți criptografie; de fiecare dată cînd faceți cumpărături prin Internet, browser-ul dumneavoastră folosește criptografie pentru a trimite numărul cărții de credit.

Cu atît mai interesant este faptul că nici unul dintre sistemele criptografice folosit pe scară largă este demonstrat în mod matematic ca fiind sigur! De fapt întreaga tehnologie a criptografiei se bazează pe niște probleme matematice al căror răspuns este încă necunoscut.

Una dintre aceste probleme este dacă întrebarea dacă un număr poate fi descompus rapid în factori primi. Deși ați învățat în școala primară cum se face asta, dacă veți încerca să aplicați algoritmul acela unor numere mari (de exemplu, cu cîteva sute de cifre), nu aveți nici o speranță. Nici măcar calculatoarele nu vă pot ajuta aici: la ora aceasta toți algoritmii cunoscuți pentru a descompune un număr în factori primi sunt foarte costisitori (ca timp de execuție). Unele dintre cele mai folosite criptosisteme sunt bazate pe presupunerea că descompunerea în factori este grea (adică că nu există nici un algoritm rapid).

Putem vedea siguranța unui sistem criptografic tot ca pe o formă de fiabilitate: dacă probabilitatea ca sistemul să fie înfrînt într-o perioadă lungă de timp este foarte scăzută, atunci sistemul criptografic este fiabil.

Un alt fapt surprinzător despre mulți dintre algoritmii folosiți în criptografie este că ei sunt de tip Monte-Carlo, cu alte cuvinte, ei pot funcționa incorect cu o probabilitate nenulă. De exemplu, mulți algoritmi încep calculele generînd un număr prim foarte mare. De exemplu, programul ssh, (secure shell) care este probabil cel mai folosit program sigur pentru acces la un calculator la distanță în mod interactiv, trebuie să asigneze calculatorului de pe care pornește conexiunea un identificator bazat pe un astfel de număr prim generat aleator. Generarea acestui număr prim poate eșua în mai multe feluri:

  1. Două calculatoare diferite ar putea genera același număr din întîmplare, și atunci unul ar putea să pretindă că este celălalt;
  2. Nu se cunoaște nici un algoritm eficient determinist care generează numere prime. Felul în care numărul prim este generat este următorul: un număr aleator impar este generat, după care se verifică dacă este prim. Procesul se repetă pînă cînd se obține un număr prim. Acest proces este un algoritm Las Vegas, pentru că probabilitatea de a genera într-una numere compuse este nenulă;
  3. Nu se cunoaște nici un algoritm eficient determinist pentru a verifica dacă un număr este prim! Toți algoritmii practici sunt de tip Monte-Carlo, pentru că ar putea declara (cu probabilitate mică) un număr compus ca fiind prim. Într-un astfel de caz securitatea oferită de ssh nu este garantată.

Cu toate acestea, în practică ssh funcționează foarte bine pentru că:

  1. Există aproximativ 10150 numere prime cu 512 cifre, adică mai multe decît numărul estimat de atomi din univers. Probabilitatea ca două calculatoare să aleagă același număr este infimă;
  2. Densitatea numerelor prime este relativ ridicată: între primele n numere întregi există aproximativ n/log n numere prime. Cu probabilitate mare algoritmul Las Vegas de generare a unui număr prim va găsi deci unul destul de repede (după un număr de repetiții proporțional cu numărul de cifre dorite);
  3. Probabilitatea de eroare a algoritmului Monte-Carlo de verificare a primalității poate fi micșorată în mod arbitrar folosind tehnica amplificării, descrisă mai sus.

Algoritmi aleatori în rețele

Dacă credeți că algoritmii aleatori sunt apanajul teoreticienilor, vă înșelați. Ei sunt folosiți în contexte extrem de aplicate. Voi ilustra cu un exemplu de folosire a unui algoritm Las-Vegas în rețelele de calculatoare. Acest algoritm este folosit cu variații în (cel puțin) două contexte:

În aceste protocoale algoritmul Las Vegas este folosit pentru a distruge simetria intrinsecă în algoritmii determiniști. Dacă doi algoritmi determiniști pleacă din același punct și fac mereu aceleași operații, ei vor fi mereu în aceeași stare. Dacă dorim cumva să diferențiem între cei doi algoritmi, simetria poate fi indezirabilă.

Voi ilustra această problemă cu protocolul Ethernet. Ethernet este cel mai folosit tip de rețea locală, inventat de Bob Metcalfe în 1973. În varianta originală de Ethernet, despre care discut aici, mai multe calculatoare sunt legate la un cablu coaxial. Acest cablu e folosit în mod asemănător cu televiziunea prin cablu pentru a transmite date: un calculator emite datele, iar celelalte ascultă cablul; calculatorul care este destinația finală a datelor (identificat în pachetul de date) preia datele din rețea, celelalte calculatoare le ignoră. Spre deosebire de televiziunea prin cablu, în care emițătorul este unul singur, în cazul Ethernet-ului oricare din calculatoarele conectate poate transmite. Problema este că două calculatoare diferite nu pot transmite simultan, pentru că atunci semnalul este bruiat. Algoritmul aleator este folosit pentru a decide cine transmite atunci cînd mai multe calculatoare vor simultan să folosească cablul, astfel:

  1. Cînd un calculator are date de transmis, el începe prin a asculta cablul, ca să vadă dacă este ocupat;
  2. Cînd transmisiunea curentă se termină, calculatorul începe să transmită el însuși datele, în speranța că nimeni altcineva nu mai dorește să facă același lucru;
  3. Dacă două calculatoare transmit simultan ele vor observa semnalul bruiat și atunci intră în faza aleatoare, care selectează cine transmite primul:
    1. Ambele calculatoare dau cu zarul, alegînd un număr între 1 și 2. Fiecare numără pînă la valoarea aleasă și apoi încearcă din nou să transmită;
    2. Dacă ambele au ales același număr se va petrece o nouă ``coliziune''; atunci ambele aleg un număr între 1 și 4 și repetă procedura;
    3. La fiecare nouă coliziune intervalul în care se aleg numerele aleatoare își dublează lungimea, pînă cînd un calculator alege un număr mai mic și ca atare emite primul.

Creșterea exponențială a intervalului în care se generează numerele aleatoare se numește ``exponential back-off''. Această creștere rapidă asigură faptul că probabilitatea de coliziune descrește exponențial de rapid cu timpul.

Algoritmul descris mai sus se mai numește și CSMA/CD, de la Carrier-Sense Multiple Access, Collision Detect, adică ``ascultarea mediului de transmisie pentru accese multiple cu detectarea coliziunilor''; este un algoritm Las Vegas relativ simplu. Rețelele moderne Ethernet sunt ceva mai complicate, dar continuă să se bazeze pe acest algoritm. Eficacitatea sa este demonstrată de succesul acestui tip de rețea.

Spre o nouă arhitectură a calculatoarelor

În acest text, întins pe două numere de revistă, am discutat mai multe feluri în care considerații privind fiabilitatea influențează construcția calculatoarelor. Un mesaj important al acestui text este că, deși fiabilitatea ridicată este dezirabilă, un arhitect întotdeauna trebuie să ia în considerație și costul plătit pentru a o obține.

Calculatoarele moderne sunt construite dintr-o serie de nivele abstracte, care oferă funcționalități din ce în ce mai puternice. Fiecare nivel are o fiabilitate diferită și folosește tehnici diferite pentru a oferi nivelelor superioare imaginea unei fiabilități sporite. În general hardware-ul oferă lumii software aparența perfecțiunii în această privință, adică o fiabilitate excepțional de ridicată.

Tendințele tehnologiei indică însă că arhitectura calculatoarelor viitorului va fi supusă unor schimbări radicale, unul dintre motive fiind chiar schimbarea majoră a fiabilității unora dintre nivele. De exemplu, miniaturizarea continuă a componentelor electronice va fi însoțită de o degradare a fiabilității însoțită de apariția tot mai frecventă a defecțiunilor permanente și tranziente. Costul plătit pentru a masca aceste defecte prin tehnici tradiționale crește extrem de rapid: costul extrem de ridicat al unei fabrici de semiconductoare de ultima generație, de ordinul a cîteva miliarde de dolari, este doar primul simptom al acestui fenomen.

Îmi permit să speculez că o schimbare de perspectivă în ceea ce privește abordarea fiabilității poate avea consecințe enorme. De exemplu, dacă renunțăm să mai construim hardware ``perfect'', putem reduce în mod absolut dramatic costul de fabricație. Proiectul Teramac a arătat o metodă prin care hardware cu defecte poate fi folosit cu succes.

Mai multe grupuri de cercetare lucrează în mod activ pentru a defini arhitecturile viitorului. Am prezentat de curînd în Net Report (mai-iunie 2001) eforturile grupului din care fac eu parte. Propunerea noastră poate fi rezumată astfel:

Știința calculatoarelor este relativ tînără; cu siguranță că viitorul ne rezervă o mulțime de surprize în ceea ce privește tehnologiile, arhitectura și algoritmii cei mai eficienți.

Alte surse de informație