Aritoni Ovidiu Sisteme de operare 1 Introducere

E. Administrarea garantata

O abordare complet diferita a temporizarii o constituie promisiunile realiste facute utilizatorului in ceea ce priveste performanta si apoi indeplinirea lor. O promisiune realista si usor de realizat este aceasta: daca exista n utilizatori conectati in momentul in care lucrati dvs., veti beneficia de aproximativ 1/n din capacitatea procesorului. La fel intr-un sistem cu un singur utilizator care are n procese ruland, toate avand aceeasi importanta, fiecare ar trebui sa primeasca 1/n din ciclurile procesorului.

Pentru a tine aceasta promisiune, sistemul trebuie sa tina o evidenta in ceea ce priveste timpul alocat de procesor fiacarui proces inca de la initierea acestuia. Apoi calculeaza cantitatea de procesor la care fiecare proces are dreptul, adica timpul scurs de la initierea sa impartit la n. De vreme ce timpul alocat de catre procesor fiecarui proces este deja cunoscut este usor de calculat raportul dintre cantitatea de procesor avuta si cea la care are dreptul. Un raport de 0.5 inseamna ca procesul a avut doar jumatate din timpul la care avea dreptul, iar un raport de 2.0 arata ca procesul a folosit de doua ori mai mult timp decat avea alocat. In acest caz algoritmul spune sa se ruleze procesul cu cel mai mic raport pana cand acest raport este mai mare decat al celui mai apropiat competitor.

F. Administrarea aleatorie

Desi promisiunile facute utiliziatorilor si indeplinirea lor este o idee buna, ea este greu de implementat. Totusi, un alt algoritm poate fi utilizat; acesta are rezultate aproape la fel de previzibile si este foarte usor de implementat. Aceasta este temporizarea aleatorie (Waldspurger si Weihl, 1994).

Ideea de baza este acordarea de bilete de loterie proceselor, pentru diferite resurse ale sistemului, cum ar fi timpul de utilizare a procesorului. De fiecare data cand trebuie luata o decizie de temporizare este ales la intamplare un bilet de loterie si procesul caruia i-a fost atribuit acel bilet primeste resursa respectiva. Cand acest lucru se aplica la temporizarea procesorului extragerea se poate face de 50 de ori pe secunda, fiecare castigator primind ca premiu 20 de msec. din timpul procesorului.

Pentru a-l parafraza pe George Orwell: "Toate procesele sunt egale, dar unele sunt mai egale." Proceselor mai importante le pot fi atribuite bilete suplimentare pentru a le mari sansele de castig. Daca exista 100 de bilete restante si un proces detine 20 dintre ele, acesta va avea sanse de 20% sa castige fiecare extragere. Pe termen lung, va obtine 20% din timpul procesorului. Spre deosebire de un temporizator prioritar unde este foarte greu de stabilit ce inseamna exact o prioritae de 40, aici regula este clara: un proces care detine o fractiune f din totalitatea biletelor va obtine o fractiune f din totalitatea resurselor in chestiune.

Temporizarea aleatorie are cateva proprietati interesante. De exemplu, daca apare un nou proces si ii sunt acordate cateva bilete, la urmatoarea extragere sansele de castig vor fi direct proportionale cu numarul de bilete pe care le detine. Cu alte cuvinte, temporizarea aleatorie este foarte darnica.

Daca se doreste se pot schimba bilete intre procese cooperante. De exemplu daca un proces-client trimite un mesaj unui proces-server si apoi se blocheaza poate sa cedeze toate biletele serverului pentru a creste sansele serverului de a castiga runda urmatoare. Cand serverul a terminat inapoiaza biletele, astfel incat clientul sa poata rula din nou. De fapt, in absenta clientilor serverele nici nu au nevoie de bilete.

Temporizarea aleatorie poate fi folosita pentru a trata probleme mai greu de rezolvat prin alte metode. Un exemplu este un server video in care mai multe procese trimit fluxuri video clientilor lor, dar la rate diferite de frame-uri. Sa presupunem ca procesele au nevoie de frame-uri la o rata de 10, 20 si 25 frame-uri/sec. Alocand acestor procese 10, 20 si respectiv 25 de bilete timpul procesorului va fi impartit automat in mod corespunzator.

G. Administrara in timp real

Un sistem in timp real este unul in care timpul joaca un rol esential. In general,

unul sau mai multe dispozitive fizice, externe computerului genereaza stimuli la care computerul trebuie sa reactioneze corespunzator intr-un interval de timp bine stabilit. De exemplu, computerul dintr-un compact disc player primeste bitii si trebuie sa-i converteasca in muzica intr-un interval de timp foarte scurt. Daca este depasit acest interval, muzica va suna ciudat. Alte sisteme in timp real sunt monitorizarea pacientilor din sectiunea de tratament intensiv a unui spital, pilotul automat al unui aparat de zbor si controlul de siguranta dintr-un reactor nuclear. In toate aceste cazuri, obtinerea unui raspuns bun dar prea tarziu este adesea la fel de grav ca si cum nu l-am fi primit deloc.

Sistemele in timp real sunt in general impartite in "timp real dur", insemnand ca exista termene limita care trebuie neaparat respectate si "timp real bland", ceea ce inseamna ca se poate tolera o nerespectare a termenului impus. In ambele cazuri comportamentul de timp real se realizeaza prin divizarea programului intr-un numar de procese al caror comportament este previzibil si stiut dinainte. Aceste procese sunt in general scurte si pot fi duse la capat in mai putin de o secunda. Cand un eveniment extern este detectat, temporizatorul este cel care trebuie sa temporizeze astfel procesele incat termenul limita sa fie respectat.

Evenimentele carora trebuie sa le raspunda sistemele in timp real pot fi impartite in periodice (cele care apar la intervale regulate) si aperiodice (cele a caror aparitie nu poate fi prevazuta). Se poate ca un sistem sa trebuiasca sa raspunda mai multor fluxuri de evenimente periodice. Este posibil sa nu se poata raspunde tuturor, acest lucru depinzand de timpul de care ficare eveniment are nevoie pentru procesare. De exemplu, daca exista m evenimente periodice, iar evenimentul i apare cu o frecventa Pi si necesita Ci secunde din timpul procesorului pentru a trata fiecare eveniment, atunci incarcarea poate fi facuta doar daca FORMULA 

Daca un sistem in timp real poate sa indeplineasca acest criteriu inseamna ca acel sistem poate fi temporizat.

De exemplu, ganditi-va la un sistem "timp real bland" cu trei evenimente periodice cu perioade de 100, 200 respectiv 500 msec. Daca aceste evenimente necesita 50, 30 respectiv 100 msec. din timpul procesorului pentru fiecare eveniment, inseamna ca sistemul este temporizabil deoarece 0.5+0.15+0.2<1. Daca este adaugat un al patrulea eveniment cu o perioada de 1 secunda, sistemul va ramane temporizabil atata vreme cat acest ultim eveniment nu necesita mai mult de 150 msec. din timpul procesorului pentru fiecare eveniment. In acest calcul se presupune ca schimbarea de context se face intr-un interval atat de scurt incat poate fi ignorat.

Algoritmii de temporizare in timp real pot fi dinamici sau statici. Primii iau deciziile de temporizare in timpul rularii; cei din urma iau aceste decizii inainte ca sistemul sa inceapa sa ruleze. Haideti sa vedem pe scurt cativa algoritmi dinamici de temporizare in timp real. Algoritmul clasic este "algoritmul cu rata monotona" (Liu si Layland, 1973). Acest algoritm atribuie dinainte fiecarui proces o prioritate proportionala cu frecventa cu care apare evenimentul sau de tragere. De exemplu, un eveniment care trebuie sa ruleze la fiecare 20 msec. primeste prioritate 50, iar un proces care trebuie sa ruleze o data la 100 msec. primeste prioritate 10. Atunci cand procesul cu cea mai mare prioritate este pregatit sa ruleze, temporizatorul il ruleaza tot timpul pe acesta, chiar daca trebuie sa intrerupa alt proces care inca ruleaza in momentul respectiv. Liu si Layland au dovedit ca acest altgoritm este fiabil.

Un alt algoritm de temporizare reala foarte des intalnit este "intai primul termen limita" De fiecare data cand este detectat un eveniment, procesul sau este adaugat pe lista proceselor pregatite pentru a fi rulate. Lista se tine aranjata in functie de termenul limita, care pentru un eveniment periodic inseamna urmatoarea aparitie a sa. Algoritmul va rula primul proces de pe lista, cel care are termenul limita cel mai apropiat.

Un al treilea algoritm calculeaza cantitatea de timp pe care o are in plus fiecare proces, adica neglijenta sa. Daca un proces are nevoie de 200 msec. pentru a se finaliza si trebuie sa fie terminat in 250 msec., inseamna ca neglijenta sa este de 50 msec. Algoritmul, numit si "cea mai mica neglijenta" alege procesul cu cel mai putin timp in plus.

Desi teoretic este posibil sa transformam un sistem de operare general intr-un sistem in timp real prin utilizarea unuia dintre acesti algoritmi de programare, in practica, in sistemele generale schimbarea de context dureaza atat de mult incat performanta unui sistem in timp real poate fi atinsa doar pentru aplicatiile cu termene limita destul de mari. In consecinta, pentru majoritatea lucrarilor in timp real se utilizeaza sisteme speciale pentru operare in timp real, care au anumite proprietati foarte importante. De obicei printre acestea se numara o marime mica, timp de intrerupere foarte scurt, schimbarea rapida a contextelor, un interval foarte scurt in care intreruperile nu functioneaza si posibilitatea de administrare a mai multor cronometre la intervale de milisecunde sau microsecunde.