Algoritmi bazati pe prioritate, preemptivi

Algoritmi bazati pe prioritate, preemptivi

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.

algoritmi bazati pe prioritate - comportarea sistemului in cazul in care se utilizeaza prioritati depinde de natura structurii de prioritati:

Ø      asignarea prioritatii task-urilor se realizeaza functie de importanta task-ului

Ø      asignarea prioritatilor se realizeaza in functie de perioada task-ului, de obicei cel cu o perioada mai mica fiind cel mai prioritar

In practica, proiectantii utilizeaza de obicei o combinatie intre abordarile de mai sus; de exemplu, in conditii de functionare normala task-ul cel mai scurt este si cel mai important si deci cel mai prioritar, astfel incit cele doua abodari coincid de multe ori.

Algoritmii bazati pe prioritate sunt larg utilizati atit in sistemele uniprocesor cit si in sistemele multiprocesor. O schema de prioritate este statica daca prioritatea unui anumit task este asignata o singura data (initial) si nu se mai modifica ulterior; o schema de prioritate este dinamica daca ea permite schimbarea prioritatii task-urilor in timpul executiei acestora. Si algoritmii bazati pe prioritate pot fi ne-preemptivi (ex: shortest-job-first, highest-response- ratio-next) sau preemptivi (ex: rate-monotonic, earliest-deadline-as-soon-as-possible, earliest-deadline-as-late-as-possible).

Preemptivi:

planificare euristica - este o politica de planificare bazata pe prioritati statice, care sunt evaluate si setate de proiectantul sistemului in mod arbitrar, initial, si din acest motiv este o politica subiectiva

rate-monotonic - in cadrul acesteia fiecarui task i se asociaza o prioritate functie de perioada acestuia (static!), task-ul cu perioada cea mai scurta fiind cel mai prioritar. Algoritmul de planificare rate-monotonic se bazeaza pe citeva presupuneri:

Ø      toate task-urile se considera a fi periodice si independente (de exemplu, nu exista relatii de precedenta intre task-uri)

Ø      toate task-urile au importanta egala

Ø      deadline-ul unui task se considera a fi perioada acestuia

Ø      task-urile care nu sunt periodice nu au deadline-uri hard

Unul din avantajele pretinse ale algoritmului rate-monotonic este acela ca se poate obtine o rata relativ ridicata a utilizarii procesorului indeplinind totodata si constringerile impuse (deadline). Astfel, s-a demonstrat ca, atita timp cit utilizarea procesorului ramine sub un anumit nivel, algoritmul de planificare poate asigura respectarea deadline-urilor pentru toate task-urile, conditie esentiala pentru STR. Utilizarea maxima permisa a procesorului pina la care se poate asigura acest lucru poate fi calculata cu formula:

unde T_WCETi = timpul de executie pentru cazul cel mai defavorabil WCET al task-ului i, f_i = frecventa task-ului i, n = numarul de task-uri de planificat. U obtinut in acest caz reprezinta limita atinsa pentru utilizarea procesorului pentru cazul cel mai defavorabil, si valoarea acestuia creste monoton de la 0.83 pentru n=2 catre 0.693 cind n tinde la infinit.

Daca gradul de utilizare al procesorului satisface relatia de mai sus, procesele sunt planificabile utilizind algoritmul rate-monotonic.

earliest-deadline-as-soon-as-possible EDS - in cazul acesta prioritatea este definita ca fiind timpul ramas pina la deadline pentru task-ul respectiv. Evident, prioritatile calculate in acest mod se modifica in timp, deci politica de planificare este dinamica. Conditia necesara si suficienta pentru o planificare fezabila utilizind acest algoritm este data tot de Liu & Layland pentru o performanta la nivel mediu:

unde T_WCETi reprezinta timpul de executie pentru cazul cel mai defavorabil al task-ului i, iar T_Peri reprezinta perioada task-ului i.

earliest-deadline-as-late-as-possible EDL - utilizeaza in procesul de planificare notiunea de laxity a task-ului (timpul intre momentul finalizarii executiei task-ului si deadline). Adica, daca doua task-uri sunt gata de executie in acelasi moment, cel care are laxity-ul mai mic, este mai prioritar.