Alocarea si planificarea in timp real - Algoritmi de planificare clasif , alg simpli, non-preemtivi

Alocarea si planificarea in timp real - Algoritmi de planificare clasif , alg simpli, non-preemtivi

Problema alocarii resurselor in STR distribuite creaza o dimensiune suplimentara alocarii conventionale prin prisma constringerilor de timp impuse (deadline). Aceste resurse pot fi resurse hardware (procesoare, memorie, dispozitive de I/O, etc.) sau software (o baza de date comuna). Problema alocarii poate fi vazuta ca o problema de partitionare a proceselor pe procesoare, in timp ce planificarea forteaza o ordine partiala a proceselor din cadrul fiecarei partitii. Separarea alocarii de planificare permite simplificarea planificatorului la un planificator local, chiar static.

Definitia generala a alocarii si planificarii:

Dindu-se un set de procese P=, se pune problema cum pot un set de procesoare U= si un set de alocari de procese pe procesoare V= sa fie alese astfel incit setul de constringeri C= sa fie satisfacut si U respectiv V sa fie optime. O problema asociata este urmatoarea: dindu-se P, U si V, se pune intrebarea daca se poate dovedi ca toate constringerile

C= sunt satisfacute.

In particular, constingerile pot implica timp (deadline impus), excludere mutuala (task-urile impart resurse, deci un task nu poate sa se execute cit timp alt task utilizeaza resursa) sau precedenta (generata in general de nevoia de informatii generate de catre un alt task). De asemenea, trebuie evitata aparitia situatiei de deadlock si livelock.

Definitie:

Deadlock = conditia in care un set de task-uri sunt intr-o astfel de stare incit este imposibil pentru oricare dintre ele sa se execute. CPU este libera, dar nu exista task-uri gata de executie (pregatite).

De exemplu, task-ul A a obtinut resursa X in excludere mutuala si are nevoie de resursa Y pentru a continua, dar, intre obtinerea lui X si cererea lui Y, task-ul B a obtinut resursa Y in regim de excludere mutuala si la rindul sau cere resursa X. Nici unul dintre cele doua task-uri nu isi poate continua executia, deoarece A asteapta resursa Y detinuta de B respectiv B asteapta resursa X detinuta de A.

Detectarea si prevenirea deadlock-urilor cade in responsabilitatea sistemului de operare si trebuie prevazuta inca din faza de proiectare a acestuia.

Definitie:

Livelock = conditia in care task-urile care cer acces exclusiv la un set de resurse intra in asteptare in bucla unele dupa altele; in acest caz CPU lucreaza, dar task-urile nu pot iesi din bucla de asteptare.

Problemele legate de planificare sunt in principal doua:

alegerea unui algoritm de planificare

aprecierea planificabilitatii = daca sunt suficiente resurse pentru ca toate procesele sa se execute in limitele deadline-ului impus; in general, planificabilitatea unui set de procese este legata de timpul de executie pentru fiecare task (computational time), calculat in valoare medie, sau pentru cazul cel mai defavorabil. In acest ultim caz, timpul calculat de executie al task-ului T_C este egal cu timpul t_WCET din figura 1.2.

Scopul unui algoritm de planificare este sa asigure ca planificatorul dispecerizeaza procesele gata de executie intr-o astfel de ordine incit toate constringerile de timp (deadline-uri) sa fie realizate. De fapt, algoritmul controleaza ordinea din coada de asteptare a proceselor. O grupare algoritmilor de planificare utilizati in prezent este reprezentata schematic in Figura 6.7.

a). Algoritmi simpli

Figura 6.7: Politici de planificare in sistemele timp real

a). algoritmi simpli - in cadrul carora toate task-urile au importanta egale, nu se tine cont de prioritate. Pot fi non-preemptivi (ex: First-Come-First-Served FCFS) sau preemptivi (ex: Round-Robin).

Non-preemptivi:

First Come First Served FCFS - este cea mai simpla politica de planificare, nu implica nici o constringere asupra task-urilor: toate task-urile au aceeasi prioritate si ele nu pot fi intrerupte. Astfel, task-urile se executa secvential, pina la terminare. VRTX este un executiv de timp real care adopta aceasta politica pentru planificarea task-urilor care au aceeasi prioritate. Acesta politica de planificare poate fi utilizata eventual in combinatie cu alti algoritmi. Pentru sistemele timp real utilizarea acestui algoritm de planificare poate induce timpi de asteptare prea mari, intrucit un task trebuie sa astepte terminarea tuturor task-urilor care il preced in ordinea aparitiei. In plus, timpul de asteptare este i general nepredictibil, chiar daca estimari pentru cazul cel mai defavorabil pot fi realizate.