Sisteme de operare pentru aplicatii de timp real

In general, aplicatiile de timp real trebuie sa execute diverse sarcini diferite, unele in paralel si altele la momente de timp aleatoare. Asemenea aplicatii sunt constituite din programme activate de intreruperi. Pentru a usura sarcina scrierii unor asemenea programe se utilizeaza sistemele de operare de timp real care gestioneaza intreruperile, timerele, conversia analog-numerica, pentru o functionare sigura si eficienta.

O aplicatie de timp real este compusa din mai multe sarcini (taskuri). Sistemul de operare trebuie sa asigure suport pentru:

structurarea aplicatiilor in sarcini (taskuri),

executia concurenta (in paralel) a sarcinilor,

utilizarea resurselor sistemului la momente predeterminate,

utilizarea resurselor sistemului la momente aleatoare,

implementarea sarcinilor ca unitati logice separate.

Sistemul de operare trebuie sa decida cand si ce sarcina sa execute (planificarea sarcinilor).  In unele cazuri sarcinile nu comunica unele cu altele. Dar ele pot avea nevoie sa utilizeze in comun resursele sistemului (accesul concurrent la resurse, partajarea resurselor). Pentru a evita conflictele de acces este nevoie de excludere mutuala care sa impiedice un proces sa acceseze un obiect in curs de utilizare de catre un alt proces.

1.1      Procese

Un proces este un program in executie. El consta din programul executabil, datele, stiva, registrele si toate informatiile necesare executiei programului.

In sistemul de operare, informatiile referitoare la procese sunt memorate intr-o lista numita tabele cu procese.

Periodic, sistemul de operare decide intreruperea unui proces in curs de executie si de a lansa in executie un alt proces, deoarece primul proces a epuizat timpul sau de unitate centrala alocat.

Cand un proces a fost suspendat temporar, el trebuie relansat in executie exact din starea in care a fost interrupt. Trbuie deci, ca toate informatiile necesare pentru reluarea procesului sa fie salvate cat timp el este in asteptare (de exemplu, pozitiile tuturor fisierelor deschise).

Un proces este o functie de timp: el poate fi creat, executat sau distrus. Un proces are in general trei parti:

o zona de program ce contine instructiunile programului. Sistemul de operare considera zona de program o zona doar de citire,

o zona de date ce contine variabilele programului. Aceasta zona poate fi citita sau scrisa,

stiva ce contine informatii temporare, variabile locale, etc. Stiva poate fi citita sau scrisa.

La lansarea In executie a unui proces, accesul la cele trei zone se face prin scrierea in registre speciale a adreselor celor trei zone.

Contextul procesului este memorat intr-un obiect numit descriptorul procesului. Pentru gestiunea proceselor de catre planificator, descriptorii proceselor sunt memorati intr-o lista.

Figura 1. Lista cu descriptori de proces.

Functiile sistem cele mai importante ale sistemului de operare pentru gestionarea proceselor sunt cele de creare si terminare a unui proces. Aceste functii sunt:

creare unui proces. Functia are ca rezultat un identificator al procesului, care in identifica unic (PID),

distrugerea unui proces. Functia are ca parametru PID,

activarea unui proces. Trecerea preocesului identificat de PID in starea pregatit,

dezactivarea unui proces. Trecerea procesului identificat de PID in starea blocat,

terminarea procesului asigura un sfarsit normal al procesului.

1.2      Starile unui proces

Figura 2. Starile unui proces.

Starile unui proces sunt:

• Executie,
• Pregatit,
• Blocat.

Tranzitia 1. Procesul trece in starea Blocat cand nu mai poate continua executia, de exemplu cand asteapta date, deoarece a lansat o operatie Intrare / Iesire. Procesul a cerut o resursa a sistemului de operare si asteapta sa primeasca aceasta resursa.

Tranzitia 2. Procesul trece in starea Pregatit deoarece sistemul de operare a decis lansarea unui alt proces, deoarece procesul curent a epuizat partea sa de timp de unitate centrala. Procesorul a fost preluat de un alt proces. Preluarea  a fost decisa de algoritmul de planificare.

Tranzitia 3. Procesul trece in starea Executie, deoarece sistemul de operare a decis lansarea lui. Procesorul a fost alocat din nou procesului.

Tranzitia 4. Procesul trece in starea Pregatit deoarece operatia Intrare / Iesire s-a terminat si datele sunt disponibile. Evenimentul asteptat de proces s-a produs.

O parte din procesele din sistemul de operare executa programe utilizator. Aceste procese fac parte din sistemul de operare si ele gestioneaza operatiile Intrare / Iesire. La cererea unei operatii Intrare / Iesire, sistemul de operare intrerupe procesul in curs si lanseaza procesul ce gestioneaza perifericul Intrare / Iesire necesar. Procesul in curs de executie trece in starea Blocat. Dupa ce procesul ce gestioneaza perifericul a citit / scris datele, procesul ce a cerut operatia Intrare / Iesire trece in starea Pregatit.

Gestiunea proceselor, comunicatia intre procese si gestiunea intreruperilor este realizata de un planificator de procese (scheduler).

Sistemul de operare are o tabela cu procese, fiecare element din tabela corespunde unui anumit proces. Fiecare periferic Intrare / Iesire are in memorie un vector de intreruperi. Acest vector contine adresele procedurilor de tratare a intreruperilor. La aparitia unei intreruperi se executa urmatoarele:

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

• se salveaza registrele procesului in curs de executie,
• se executa procedura de la adresa de tratare a intreruperii respective,
• se refac registrele procesului ce a fost in curs de executie si acesta este relansat in executie.

Exemplu. Un proces ce asteapta citirea datelor de pe disc este Blocat. El asteapta un semnal de interrupere de la unitatea de disc, ca operatia Intrare / Iesire s-a terminat.

La aparitia unui semnal de intrerupere de la disc, se executa urmatoarele:

1.     se salveaza registrele procesului in curs de executie,

2.     se executa procedura de la adresa procedurii de tratare a intreruperii disc. Procesul ce asteapta citirea datelor de pe disc trece in starea pregatit,

3.     se refac registrele procesului ce a fost in executie si se relanseaza executia acestuia,

4.     planificatorul analizeaza procesele si poate dispune trecerea in starea Executie a procesului ce asteapta citirea a datelor de pe disc.

1.3      Comunicarea intre procese

In anumite cazuri, diverse procese utilizeaza un spatiu comun de date, de exemplu o zona de memorie comuna, un fisier, etc.

Exemplu. Pentru listarea fisierelor exista un tabel in care fiecare proces completeaza o linie cu numele unui fisier ce trebuie listat. Exista o variabila cu indicele liniei libere. Fiecare proces scrie numele fisierului in linia libera si creste indicele cu unu.

3 4 5

Se poate intampla ca un proces A scrie numele fisierului in linia cinci dar nu mareste indicele cu unu din cauza ca a fost pus in starea Pregatit. Procesul B ce este lansat scrie numele fisierului de listat in linia cu indicele cinci dat de variabila indice (nemodificata) si apoi modifica variabila indice la valoarea sase. La relansare in executie, procesul A mareste variabila indice cu unu, dar in linia cinci se afla numele fisierului scris de procesul B.

Aceasta situatie se numeste accesul concurent la resurse.

Pentru a evita conflictele de acces este nevoie de excludere mutuala care sa impiedice un proces sa acceseze un obiect in curs de utilizare de catre un alt proces. Partea din program in care se pot produce conflicte de acces la resurse se numeste sectiune critica.

1.3.1     Semafoare

Semaforul este o variabila care are valoarea zero daca nici un proces nu asteapta sa intre in sectiunea critica, si o valoare pozitiva daca unul sau mai multe procese asteapta sa intre in sectiunea critica.

Exista doua operatii asupra unui semafor:

• DOWN descreste cu unu valoarea semaforului daca acesta este mai mare ca zero, apoi continua executia normala, iat daca valoarea semaforului este zero procesul este pus in asteptare. Testul semaforului, schimbarea valorii si punerea in asteptare sunt efectuate ca o operatie atomica indivizibila,
• UP creste valoarea semaforului cu unu. Daca unul sau mai multe procese asteapta pentru acest semafor, (sunt blocate), sistemul de operare alege un proces pentru a termina operatia UP si il lanseaza in executie. Dupa efectuarea unui operatii UP asupra unui semafor care bloca mai multe procese, valoarea semaforului este zero, dar cu un proces mai putin in asteptare. Operatia UP este indivizibla. Dupa operatia UP procesul nu se poate bloca.   

Operatiile UP si DOWN sunt implementate ca apeluri la functiile sistemului de operare, deoarece ele trebuie sa fie operatii indivizibile, iar sistemul de operare nu poate fi intrerupt.

Exemplu. Problema consumatorului si producatorului.

Doua procese utilizeaza o zona de memorie comuna, un vector cu N componente. Producatorul pune informatii in componentele vectorului, consumatorul le sterge.

Pot aparea probleme cand:

• producatorul vrea sa scrie o informatie in vector, dar vectorul este plin. El trebuie pus in asteptare, si repus in executie de consummator dupa ce acesta a sters informatii,
• consumatorul vrea sa stearga informatii, dar vectorul este vid. El terbuie pus in asteptare si repus in activitate de catre producator.

Se vor utiliza trei varibile:

plin, ce numara locurile ocupate din vector,

vid, ce numara locurile goale din vector,

mutex, ce asigura ca producatorul si consumatorul nu acceseaza in acelasi moment vectorul.

Initial avem plin = 0, vid = N, mutex = 1.

pentru excluderea mutuala, fiecare proces executa functia down(mutex) inainte de a intra in sectiunea critica si apoi up(mutex) dupa iesirea din sectiunea critica.

Programul este urmatorul.

N = 100;

semaphore mutex = 1;

semaphore vid = N;

semaphore plin = 0;

Semafoarele initializate la unu si utilizate pentru ca dintre mai multe procese doar unu sa intre in sectiunea critica se numesc semafoare binare.

Daca se modifica ordinea operatiilor  down() in producator, cand vectorul este plin, producatorul se blocheaza cu mutex = 0. Cand consumatorul incearca sa citesca vectorul, el se va bloca deoarece mutex = 0; Procesele se vor bloca pentru totdeauna.

1.3.2     Contoare de evenimente

Pentru controla accesul concurent se utilizeaza o variabila E numita contor de evenimente. Pentru un contor de evenimente E sunt definite trei operatii:

read(E); da valoarea curenta a lui E,

advance(E); creste pe E cu unu de o maniera atomica,

await(E, n); asteapta ca E >= n.

Valoarea contorului creste mereu, nu poate scadea.

Pentru a rezolva problema producator  - consumator se utilizeaza doua contoare:

in numara obiectele puse in memorie de producator de la inceputul programului,

out numara obiectele pe care consumatorul le-a sters.

Trebuie ca in >= out, dar diferenta nu poate depasi dimensiunea vectorului.

N = 100;

contorev in;

contorev out;

1.3.3     Monitoare

Pentru a evita interblocarea proceselor, se utilizeaza o primitiva de sincronizare numita monitor.

Un monotor este un ansamblu de proceduri, de variabile si de structuri de date grupate intr-un modul special. Un proces poate face apel in orice moment la procedurile monitorului, dar nu poate accesa structura interna a datelor monitorului in procedurile exeterne.

Monitorul are urmatoarea proprietate importanta: un singur proces poate fi activ intr-un monitor la un moment dat.

Cand un proces apeleaza o procedura a monitorului, primele instructiuni din procedura verifica daca nici un alt proces nu este activ in monitor. Daca este cazul procesul apelant este suspendat pana cand procesul activ in monitor paraseste monitorul. Daca nici un proces activ nu utilizeaza monitorul, procesul apelant poate intra in monitor.

Excluderea mutuala se realizeaza cu un semafor binar.  

In programe, toate sectiunile critice sunt grupate intr-un monitor.

Pentru a realiza operatiile de punere in asteptare a unui proces si de reluare a executiei, se utilizeaza variabile de conditie. si doua operatii asociate lor, wait() si signal().  

Daca un proces din monitor nu poate continua executia sa (de exemplu, producatorul gaseste stiva plina), el executa operatia wait() asupra unei variabile conditionale. Acesata actiune antreneaza blocarea procesului apelant si autorizeaza alt proces caruia I s-a refuzat accesul mai inainte in monitor.

Un alt proces (de exemplu consumator), poate activa procesul blocat executand o operatie signal() asupra unei variabile conditionale utilizate de procesul pus in asteptare. Dupa efectuarea unei operatii signal() trebuie sa determinam ce se intampla pentru a evita ca doua procese sa fie active in monitor. Exista doua reguli:

sa se relanseze procesul ce trebuie relansat si sa se suspende celalalt proces,

procesul ce a executat functia signal() trebuie sa paraseasca imediat monitorul. Operatia signal() trebuie sa fie ultima dintr-o procedura. Daca operatia signal() se aplica asupra unei variabile conditionale pentru care asteapta mai multe procese, un singur proces poate fi reactivat.

Exemplu.

monitor ProdCons

procedure retrage()

procedure prod()

procedure cons()

1.3.4     Schimbul de mesaje intre procese

Comunicarea intre procese ce nu ruleaza pe aceeasi masina se face prin mesaje. Metoda utilizeaza doua primitive:

send(destinatie, & mesaj);

receive(sursa, & mesaj);

Mesajele se pot pierde in retea. Pentru a semnala aceasta, receptorul trebuie sa trimita un mesaj de confirmare. cre emitator. Daca emitatorul nu primeste mesajul de confirmare intr-un timp stabilit, el retransmite mesajul. Se poate intampla ca mesajul sa fie primit corect, dar mesajul de confirmare sa se piarda. In acest caz transmitatorul retransmite mesajul. Pentru ca receptorul sa distinga mesajul retransmis de unul nou, mesjele au un numar de identificare.

1.3.5     Apelarea procedurilor la distanta

Pentru un client, trimiterea unui mesaj la un server si asteptarea unui raspuns revine la apelarea unei proceduri si asteptarea ca ea sa se execute.

Comunicarea intre procese se realizeaza prin apelarea procedurilor la distanta. (remote procedure call, RPC).

Cand un proces client vrea sa citeasca un bloc de date dintr-un fisier la distanta, el apeleaza o procedura (stub) read() pe propria masina printr-un apel clasic (1). Procedura read() transmite o cerere serverului de fisiere si asteapta raspunsul (2).

Figura 3. Etapele apelarii unei proceduri la distanta.

Pe server, mesjul este primit de o procedura stub a serverului. Aceasta apeleaza serverul printr-o procedura standard (3). Cand aceasta se termina, ea trimite datele catre procedura stub in mod clasic (4), care transmite mesajul de raspuns cre procedura stub a clientului (5). Aceasta procedura trimite clientului rezultatul in mod standard (6).

1.4      Planificarea proceselor

Sistemul de operare trebuie sa aleaga un proces de executat din mai multe procese pregatite. Calculatoarele au un timer care genereaza periodic un semnal de intrerupere. La fiecare intrerupere sistemul de operare decide daca procesul curent continua executia sau daca el a consumat timpul alocat si alt proces va fi lansat in executie. Aceasta strategie se numeste planificare cu preluare (preemptive scheduling).

Planificarea proceselor se face dupa schema urmatoare

Figura 4. Planificarea proceselor.

Planificatorul (scheduler) asigura comutarea intre procesele blocate si cele pregatite. El gestioneaza coada proceselor pregatite si cozile proceselor blocate.

Dispatcherul alege din coada proceselor pregatite procesul ce va fi lansat in executie si schimba contextul asociat. Coada proceselor pregatite este astfel organizata incat dispatcherul ia primul proces din coada. Schimbarea contextului consta in:

1. salvarea starii procesului curent,
2. restaurarea starii noului proces.

Comutarea proceselor se poate face din urmatoarele cauze:

crearea procesului insusi: punerea in asteptare din cauza unei conditii, sfarsitul procesului,

decizia planificatorului (procesul in curs de executie este mai pu tin prioritar decat un altul pregatit),

necesitatea de a raspunde la un fenomen extern.

1.4.1     Planificare circulara (round robin)

Fiecare proces are un interval de timp in care este executat. Dupa ce un proces a executat intervalul sau de timp, procesorul este alocat altui proces. Daca procesul se blocheza sau se termina inainte de timpul acordat, procesorul este alocat imediat altui proces.

Figura 5. Planificarea circulara a proceselor.

1.4.2     Planificare cu prioritati

In aceasta metoda fiecare proces are o prioritate si se lanseaza procesul cu cea mai mare prioritate. Pentru ca procesele cu prioritare ridicata sa nu execute la infinit, planificatorul scade prioritatea procesului ales la fiecare semnal de intrerupere.

Prioritatile pot fi statice sau dinamice. Prioritatile statice sunt alocate initial. Prioritatile dinamice sunt alocate de sistemul de operare. Ele pot fi atribuite in functie de cate operatii intrare / iesire efectueaza procesul.

Figura 6. Planificarea cu prioritati.

De exemplu, anumite procese fac multe operatii intrare / iesire si asteapta mult timp termonarea unei operatii intrare / iesire. Trebuie deci sa li se aloce procesorul cand il cer pentru a efectua urmmmatoare aoperatie intrare / iesire. Aceasta intrare / iesire se va executa in timp ce un alt proces face calcule. Daca procesul ce face multe operatii intrare / iesire nu obtine rapid procesorul, el ocupa inutil memoria.

Un algoritm este de a aloca acestui proces prioritatea 1 / f unde f este fractiunea de timp utilizata de proces la ultima activare. Un proces ce utilizeaza 2 ms din 100 ms va avea prioritatea 50, un proces ce utilizeaza 50 ms din 100 ms va avea prioritatea 2, un proces ce utilizeaza tot timpul va avea prioritatea 1.

1.4.3     Implementarea planificarii

Exista o coada pentru procesel pregatite si o coada pentru procesele blocate. In practica, exista mai multe cozi pentru procesele blocate:

procese ce trebuie deservite rapid (fast service),

procese suspendate pana la aparitia unui eveniment, (event),

procese rulate la intervale regulate, predeterminate (time tabled), de exemplu pentru citirea traductoarelor,

procese executate cand este timp (base level).

Figura 7. Planificarea proceselor.

Procesele sunt suspendate din executie din urmatoarele motive

Figura 8. Suspendarea unui proces.