[Date]

Protocoale de sincronizare pentru scheduling în sisteme embedded multicore în timp real

Sisteme de Operare Avansate

Student: Ștefan Miruna Maria Cristina

Profesor îndrumător: Stăncescu Ștefan

Universitatea Politehnica din București - Ian 2017

CuprinsI. Introducere: Terminologie și context..................................................................................................2

a. Context............................................................................................................................................2

b. Accesul al resurse comune..............................................................................................................2

c. Tipuri de strategii de planificare......................................................................................................4

d. Task-uri............................................................................................................................................5

e. Resurse............................................................................................................................................5

II. Strategii de sincronizare......................................................................................................................7

1. Priority Ceiling Protocols.................................................................................................................7

a. M-PCP și D-PCP............................................................................................................................7

b. OSEK-PCP.....................................................................................................................................9

2. FMLP..............................................................................................................................................11

3. PWLP.............................................................................................................................................15

4. M-BWI............................................................................................................................................19

III. Comparații. Concluzii.....................................................................................................................24

IV. Bibliografie.....................................................................................................................................25

I. Introducere: Terminologie și contexta. Context

Tehnologiile multicore au avut și au în continuare un impact imens asupra capacității de procesare și sunt la momentul actual produse de toate firmele importante de profil. Ele sunt incluse în sisteme din ce în ce mai complexe și utilizate într-o mare varietate de domenii și aplicații. Aceste platforme sunt folosite din ce în ce mai mult și în sisteme în timp real, dedicate, pentru care timpul de răspuns este esențial. Este vital ca unitatea de calcul/computerul să reacționeze la stimuli într-un timp limită dat deoarece în multe cazuri de aceste sisteme nu depind doar resurse materiale ci și vieți umane. Dintre sistemele în timp real cu rol critic se pot enumera sisteme de monitorizare a pacienților în unitățile de terapie intensivă, autopilotul aeronavelor sau (mai nou) al automobilismelor și controlul roboților industriali în fabrici automatizate. [1] Adoptarea arhitecturilor cu mai multe nuclee în sistemele dedicate este avantajoasă dacă luăm în considerare echilibrul dintre frecvența procesorului și numărul de nuclee. Un număr mai mare de nuclee permite utilizarea unei frecvențe mai mici reducând astfel consumul de putere; aspect crucial dacă hardware-ul pe care rulează aplicația este alimentat cu baterii. [2]

Pentru a oferi capacitatea de funcționare corectă și eficientă aplicațiilor dedicate în timp real au fost dezvoltate tehnici din ce în ce mai eficiente de organizare în timp (scheduling) și sincronizare în timp real a task-urilor. [3] Astfel mai multe thread-uri, ce sunt eventual distribuite pe mai multe nuclee, pot accesa simultan aceleași resurse fără a fi afectat caracterul serial al procesului. [2] Scheduling-ul proceselor în sisteme multicore a fost inițial mai intens studiat decât partea de sincronizare. Planificarea task-urilor este un proces mai puțin cooperativ și spontan ce are ca principal scop utilizarea echitabilă și eficientă a resurselor. O bună sincronizare a job-urilor aflate în execuție permite o planificare mai avantajoasă de a proceselor. Sincronizarea încercă se evite conflictul în accesul la resurse, blocarea sistemului înlesnind îndeplinirea task-urilor conform criteriului de prioritate existent. [3]

Task-uri pot fi definite drept procese secvențiale cu limitări de timp și în majoritatea sistemelor în timp real acestea sunt recurente (adică invocate în mod repetat). Se întâlnesc două tipuri de task-uri : periodice și sporadice. Putem spune ca fiecare task periodic are o serie de parametrii caracteristici:

Faza – momentul invocării (numit și timp de eliberare) Perioada – intervalul constant(numărul de unități de timp) la care este (re)invocată Deadline-ul relativ – măsurat în raport cu timpul la care a fost eliberată (îl putem presupune

egal cu perioada) Timpul necesar de execuție – Numărul de unități de timp necesare execuției neîntrerupți pentru

ca aceasta să își atingă scopul

Figura 1 Ilustrarea conceptului de task periodic (a) și respective sporadic(b) [4]

Fiecare job (o instanță/invocare a unui task) al unui task periodic trebuie să iți finalizeze execuție înainte de începutul următorului. Task-urile sporadice pot fi considerate o generalizare a task-urilor periodice prin faptul ca intervalul între invocări consecutive poate fi mai mare decât perioada sa.

b. Accesul al resurse comuneÎn cazul sistemelor multi-core simetrice (toate nucleele sunt la fel) cu memorie partajată, cel mai

uzual exemplu de resursă împărțită este o structură de date aflată în memoria partajată, utilizată pentru comunicarea între componente și pentru realizarea sincronizării. Pentru a evita eventuale neconcordanțele datorate concurenței și paralelismului, accesul la resursă trebuie protejat corespunzător printr-o schemă de acces. Există mai multe abordări prin care se atinge acest scop, ele putând fi împărțite în două mari categorii: cu și fără blocare/încuiere. Tehnicile „tradiționale” bazate pe blocarea/încuierea resursei (lock-based) garantează excluderea mutuală între secțiunile de cod care cer accesul simultan la același date. [2] Momentul în care o parte de program accesează o resursă partajată ce nu permite accesul concurent se numește regiune critică. [1]

Metodele fără încuiere („lock-free”) se referă la cazul în care suspendarea sau eșuarea executării unui thread nu duce la eșuarea sau suspendarea execuției unui alt thread, cum se întâmplă la funcționarea celor cu încuiere. În aceste cazuri se menține continuitatea sistemului la prețul unor thread-uri care rămân fără resurse (prin negarea repetată a accesului la acestea).Cu alte cuvinte se consideră că un algoritm este „lock-free” atunci când măcar unul din firele de execuție progresează dacă i se conferă suficient timp de rulare. Cea mai puternică subcategorie a algoritmilor „lock-free” sunt cei „wait-free” care, teoretic, garantează atât finalitatea globală cât și satisfacerea nevoilor de resurse ale tuturor proceselor. Strategia urmărită impune ca fiecare operație realizată să fie limitată din punct de vedere al numărului de pași necesari până la finalizare. Această combinație de trăsături ar fi ideală pentru sistemele real-time dar din păcate se dovedește în multe cazuri prea costisitoare. În plus, gama de situații în care algoritmii „wait-free” sunt la fel de eficienți cu cei cu încuierea resurselor este limitată.[5] Paradigma de programare care utilizează memoria tranzacțională este un mecanism de control al coocurenței în accesul la resurse partajate ce presupune executarea unui grup de instrucțiuni în mod atomic, analogul funcționării bazelor de date. Această variantă a devenit mai populară deoarece înlesnește scrierea de cod pentru anumite interacțiuni în programarea paralelă. [2]

Metoda cea mai folosită de control al accesului simultan rămâne în schimb utilizarea mutex-urilor (semafoare mutual exclusive) . Aceasta presupune că înainte de accesarea unei zone partajate de memorie, un task trebuie să blocheze un semafor („lock”) pe care mai apoi să îl deblocheze când

termină de utilizat resursa („unlock”). Un mutex poate fi încuiat de un singur task odată, dacă un alt task încercă să îl descuie în acest timp el va fi blocat („blocked”) iar execuția sa normală va fi sistată. Task-ul blocat va fi deblocat doar atunci când mutex-ul va fi descuiat de cel care îl deține. În sistemele cu un singur nucleu de procesare, task-ul blocat este înlăturat din lista de așteptare pentru a nu ține pe loc întreg șirul de instrucțiuni. În sisteme multicore poate fi avantajos ca task-ul blocat să fie menținut într-o stare de așteptare activă („busy-wait”) în care interoghează constant semaforul resursei pentru a verifica dacă acesta a fost descuiat („spin-lock”).

Protocolul de acces la resurse este un set de reguli conform cărora sistemul de operare gestionează task-urile blocate. Acestea impun maniera d ordonare a listei de task-uri blocate pe un mutex. Dacă apar modificări de prioritate ale task-urilor atunci când intră în posesia unui semafor sau respectiv care task-uri blocate rămân în așteptare și care sunt suspendate.

Scopul care trebuie avut în vedere atunci când se pune la punct un astfel de protocol pentru sisteme în timp real este reducerea timpului pe care task-urile importante îl petrec blocate. Offline, trebuie ca acest timp să poată fi estimat și gestionat astfel încât să poată fi analizată capacitate de organizare corectă a sistemului (schedulability analysis). Sistemele în timp real cel mai adesea întâlnite în practică, inclusiv în situații cruciale, sunt deschise și dinamice, adică task-uri pot intra în sistem sau îl pot părăsi la orice moment de timp. Din motive ce țin de robustețe, securitate și siguranță, comportamentul temporal al fiecărui task trebuie izolat și protejat de celelalte și vice-versa, spre exemplu nu este permis ca task-urile nou apărute să distruge echilibrul celor deja existente. În acest mod pot exista simultan în sistem diferite nivele de criminalitate temporală a sarcinilor în desfășurare.[2]

În afară de evitarea întârzierilor nedorite, toate aceste scheme de acces și planificare au ca scop minimizarea pe cât posibilă a inversiunilor de prioritate și evitarea deadlock-urilor. Inversiunile de prioritate sunt situațiile în care un task cu prioritate mare nu poate executa din cauza faptului că un task cu prioritate mai mică deține resursa de care acesta are nevoie sau din cauză că cel din urmă nu este preemptibil. O resursă este preemptibilă atunci când poate fi luată de la procesului care o deține fără consecințe negative. Deadlock-urile reprezintă situații în care măcar două task-uri/fire de execuție ajung să își nege reciproc și infinit accesul la una din resursele deținute deja așteptând celălalt fir de execuție să elibereze resursa de interes. Exemple de cauze ale deadlock-urilor sunt modul eronat de modificare a valorilor semafoarelor, sau mai adesea accesul simultan, dar în ordine diferită, a mai multor procese la aceleași resurse. Aceste paradoxuri se pot dovedi devastatoare pentru sistemul de operare, mai ales pentru cele în timp real, pentru că vor determina depășirea deadline-urilor tuturor job-urilor care urmează dacă nu este impusă o strategie de gestionare a situațiilor ( cum ar fi limitarea timpilor de așteptare pentru o resursă). [1]

Sistemele în timp real se pot împărți în hard real time și soft real time. Ele diferă prin faptul că în cazul soft real time depășirea deadline-ului unei sarcini este tolerabilă deși nu este de dorit, pe când în sistemele hard real-time depășirea limitelor de timp este absolut inacceptabilă. Acest lucru se obține prin descompunerea programelor care rulează într-un număr de procese al căror comportament este cunoscut a priori și care , ideal , sunt de scurtă durată ( considerabil mai puțin de o secundă). [1]

c. Tipuri de strategii de planificareOrganizarea task-urilor pe multiprocesoare se poate face în două modalități : global sau

partiționat. Planificarea partiționată presupune că un task este alocat static unul procesor pentru executare și fiecare nucleu are o coadă de așteptare proprie, independentă, gestionată de un algoritm pentru uniprocesoare. Planificarea globală impune existența unei singure cozi pentru toate nucleele de procesare astfel încât task-urile pot migra de la un procesor la altul. Aceasta din urmă la rândul său poate prezenta două abordări diferite Pfair și non-Pfair. Varianta non-Pfair este cea în care fiecare iterație a unui task este considerată un eveniment ce trebuie planificat. Modelul Pfair împarte timpul disponibil în cuante (ferestre) și execuția task-urilor în subtask-uri astfel încât fiecare subtask trebuie să execute în fereastra alocată. Fiecare task primește un număr de sloturi de timp proporțional cu utilizarea sa. Dacă acest principiu se respectă atunci teoretic planificarea este optimă. [3] [6] [4]

Figura 2 Ilustrarea diferențelor între funcționarea de tip Pfair și cel Non-Pfair: Pe primul rând sunt marcate ferestrele Pfair ale celor două job-uri de timp de execuție 3 și perioadă 8, etrebuie ca subtask-urile să se realizeze pe durata lor ăemtru a se respecta principiul Pfair [4]

Foarte important este criteriul de stabilire al priorității. În mod uzual în sistemele în timp real prioritatea crește cu apropierea timpului limită impus până la finalizarea execuției task-ului. Strategia poartă numele de EDF (Earliest Deadline First) și de fiecare dată când se pornește o nouă execuție planifică în mod dinamic sarcina care trebuie finalizată prima. Algoritmul este optimal pe uniprocesoarele cu task-uri care pot fi întrerupte și înlocuite. Problema este că atunci când sistemul este suprasolicitat nu se poate estima/limita numărul de task-uri care își vor depăși deadline-urile. În situația planificării partajate cu acest criteriu (P-EDF) fiecare nucleu are propria listă de procese pe când în varianta globală (G-EDF) se alege task-ul cu termenul cel mai apropiat dintre toate. [3]

d. Task-uriFie un sistem de task-uri T , atunci T idenumește task-ul cu numărul/identificatorul i iar T i

jeste job-ul cu numărul j al taskului T i( este o instanță/execuție a acestuia) și este ordonat conform timpului său de eliberare r ¿). Costul pesimist de execuție (worst-case execution cost) e (T i)și perioada sa p(T ¿¿ i)¿si deadline-ul său sunt parametrii descriptivi ai task-ului. Se prezintă următoarea relație timpul de eliberare, perioada și deadline-ul iterației job-ului: d (T ¿¿ i)=(T ¿¿ i j)+ p (T ¿¿ i)¿¿¿

Se consideră ca T ijeste în desfășurare la momentul t câtă vreme t ≥ r ¿) dar T i

j nu și-a finalizat execuția. Acestea pot fi în 3 stări:

Suspendate dacă nu poate fi planificat pe niciun procesor Executabile („Runnable”)

o Preemtibil: dacă poate fi programată pe un procesor dar poate fi înlăturată de un job cu prioritate mai mare

o Nepreemptibil: situație în care odată planificat va executa până la finalizare când va ieși Se numește că un job al care încetează a mai fi suspendat și trece într-una din cele două stări executabile este reluat.

e. ResurseCând un job T i

jcere acces la o resursă l trimite cerea Rl care se consideră a fi satisfăcută în

momentul în care T ijdeține l și îndeplinită după ce task-ul eliberează resursa. T i

j poate deține l pentru o durată de maxim |Rl| și devine blocată pe aceasta atunci când Rlnu poate fi satisfăcută imediat (adică resursa este deținută de un alt task). O resursă este considerată locală unui procesor atunci când toate task-urile care cer acces la ea execută pe respectivul procesor dar global atunci când aceasta nu este necesară.

Dacă T ijmai trimite o cerere R ' înainte ca R să fie satisfăcută aceasta se numește înglobată în R

- „nested” |R | include în aceste cazuri costul blocării din cauza solicitărilor din interior dar posibilitatea organizării de acest tip nu este permisă de toate protocoalele de planificare (Figura 3). Se consideră că înglobarea este corectă( „proper nesting”) dacă R ' se finalizează înaintea lui R. Se pot descrie două cazuri speciale de solicitări înglobate: cele extrem exterioare („outermost”) care nu sunt incluse în nicio altă cerere, și respectiv cele extrem interioare, care nu conțin nicio altă solicitare. [2] [7]

Figura 3 a) Legendă b) Fazele îndeplinirii unei solicitări de acces la o resursă.T ijinițiază Rl și se blochează deoarece nu este

satisfăcută imediat. T ijdeține resursa asociată Rl pentru o durată de unități de timp care include timpul de blocare ¿ Rl∨¿

datorat imbricării cererilor [7]

Apar așadar două surse de întârzieri care pun în pericol corectitudinea temporală a planificării și execuției. Prima dintre acestea fiind inversiunile de prioritate ,care presupun ca un task de prioritate mare este blocat de unul de prioritate mai mică ce este sau non-preemptibil sau are deja acces la resursa cerută de acesta. O altă problemă este blocarea la distanță. Când un protocol nu poate avea acces la o resursă din cauza că ea este în uz pe un alt procesor.

II. Strategii de sincronizare 1. Priority Ceiling Protocols

a. M-PCP și D-PCPM-PCP (Multiprocessor Priority Ceiling Protocol) și D-PCP (Distributed Priority Ceiling Protocol)

sunt două dintre protocoale pentru planificarea task-urilor pe multiprocesoare gestionate partiționat și cu priorități statice(P-SP - partitioned static-priority) care rulează aplicații în timp real. Dezvoltarea lor a avut loc în perioada în care acestea erau considerate preponderent cu rol academic motiv pentru care, odată cu aplicarea lor practică s-au dovedit a pierde teren în fața altor abordări. În ambele cazuri task-urile blocate sunt suspendate dar la utilizarea D-PCP un set de resurse este alocat unui anume procesor. [7]

În cazul D-PCP, un job accesează o resursă printr-un protocol de tip RPC ( „Resource Procedure Call” ) care presupune invocarea agentului de gestionare al procesorului alocat resursei. Acest agent este de fapt cel care accesează resursa. În cazul M-PCP este în schimb folosit un semafor global fără realizarea unor corelații între resurse și agenți și respectiv fără instanțe de tip agent. În nici unul din aceste protocoale cererile pentru resursele globale nu pot sa apară în secvențe cu înglobări (cereri „nested” ). De altfel ele sunt menținute la nivele înalte de prioritate pentru a fi executate cât mai rapid și ordonate după acest criteriu.

Un exemplu de P-SP este algoritmul RM ( „Rate Monotonic” ), care acordă priorități mai mari task-urilor de durată mai scurtă. Considerăm în cazurile ce urmează ca un task de notație T i are prioritatea de bază i, aceste fiind ordonate de la 1 la n cu 1 prioritatea maximă alocată. Prioritatea efectivă este cea folosită în realizarea planificării și poate fi mai mare sau egală cu ce de bază.

Pentru D-PCP accesul la resursele globale este mediat, după cum am spus, de agenții locali A jq ,

proprii procesorului q și care realizează accesul la resurse pentru slujbele task-ului T j. Astfel pentru accesarea resursei globale l, job-ul va trimite solicitarea R la A j

q după care se suspendă. Când agentul îndeplinește cererea, T j. este reluat. Diferența dintre un agent și un task normal este aceea că agentul are prioritate mult mai mare fața de job-urile obișnuite. În schimb, în cadrul categoriei intermediarilor, agenții task-urilor cu prioritate (efectivă) mai are pot lua locul celor care servesc task-uri cu priorități mai mici. Atunci când task-ul care cere acces la resursele alocate unui procesor este propriu acelui procesor atunci acesta va fi propriul său agent nemaifiind necesară o a trei instanță. [7]

M-PCP se bazează pe memoria comună aflată la îndemâna resurselor globale iar acestea sunt accesate direct fără a fi alocate unui nucleu de calcul. Nu sunt folosiți agenți locali iar solicitările la o anumită resursă sunt satisfăcute în ordinea priorităților . Atunci când o cerere nu este satisfăcută prompt aceasta se suspendă până când i se permite accesul la resurse. În cadrul acestui protocol job-urile care deja dețin resurse execută cu prioritate mai mare decât orice task normal.

Solicitările „nested” nu sunt permise nici de D-PCP și nici de M-PCP; cererile de acces la resurse globale nu pot fi Înglobate sau nu pot îngloba nicio altă solicitare de acces la o resursă.

Un exemplu concret de funcționare al celor două protocoale se întâlnește în figura 4 , prima situație prezentând accesul la resurse comune prin D-PCP iar segmentul b) gestionarea prin M-PCP. Patru job-uri rulând pe două procesoare :T1 până la T4, împart resursele l1,l2 , amândouă aparținând de

procesorul 1. A21 și A4

1 sunt agenții ce țin de procesorul 1 și lucrează pentru T2 și respectiv T4 care rulează pe procesorul 2. Când T4 cere la momentul de timp 2 acces la l1 , A4

1 devine activ dar se blochează deoarece T3 deja deține resursa. La fel și A2

1 devin activ și se blochează la momentul 4 . Primul dintre cei doi agenți care obține accesul la l1 este A2

1 deoarece T2 are prioritate mai mare decât T4. . De remarcat că, deși job-ul cu prioritatea de bază maximă este T1 , acesta nu este programat de-abia la timpul 7 deoarece task-urile care dețin deja resursele și agenții locali au o prioritate efectivă mai mare. În situația de la momentul de timp 9 când T2 cere acces la l2, A2

1 devine activ dar se blochează până la t=10 deoarece T1 este deja în desfășurare ( deține accesul la l1 ), așadar are prioritate mai mare. [7]

Figura 4 Ilustrarea modului de planificare a 4 task-uri care impart două resurse globale prin a) D-PCP și b) M-PCP [7]

În situația b), guvernată de M-PCP, T2 și T4 accesează neintermediat resursele globale motiv pentru care T4 se blochează la t=2 deoarece T3 deja deține resursa l1 dorită; similar T2 se suspendă pentru un moment de timp până când primește acces la l1 înaintea lui T4 datorită priorității sale mai mari. Odată ce T3 eliberează respectiva resursă și revine la prioritatea normală, începe la momentul 5 și T1. Un moment de timp mai târziu (t=6) T1 solicită acces la l1 iar cererea sa, deși inițiată mai târziu, o surclasează ca prioritate pe cea emisă de T4 și se satisface prima. La momentul de timp 8 se observă că T4 o blochează pe T2 deoarece deține deja o resursă globală.comparison(all of it) [7]

b. OSEK-PCPÎn mod deosebit în industria auto și a transportului feroviar aflate în permanentă evoluție este

deja comună planificarea pe bază de priorități OSEK în combinație cu protocolul de limitare a priorităților OSEK-PCP. Varianta clasică a acestui protocol se bazează pe lucrul cu priorități statice ceea ce este incompatibil cu funcționarea Pfair. Protocoalele Pfair alocă în mod dinamic importanța job-urilor pe baza unor ponderi și a pseudodeadline-urlor task-urilor activate. Din păcate atunci când se lucrează cu resurse care pot fi accesate coocurent acest protocol nu garantează evitarea deadlock-urilor. [6] [8]

Pentru a se reuși totuși acest evitarea deadlock-urilor, chiar și pe platformele cu un sigur nucleu unde există totuși resurse puse la comun proceselor, se adoptă modelul resurselor propus de Block et a[3] care asigură evitarea acelor situații nefaste. OSEK-PCP este o variantă a SRP – Stack Resource Policy adaptată pentru priorități statice. Nu este doar o combinație a priorităților OSEK cu modelul de împărțire a resurselor în lungi și scurte, ci implică și anumite tipuri de semafoare în încercarea de a genera o soluție completă și corectă. [6]

Modelul presupune un sistem multiprocesor cu m nuclee identice și memorie partajată. Task-urile pot fi nu doar periodice și sporadice, ci și declanșate de motor (tip specific domeniului automobilelor, având prioritate imediată). Un job poate fi activat, în curs de rulare, blocat, pregătit sau terminat.

Figura 5 Diagrama stărilor și tanzițiilor pentru un job J i , j CITATION Alf13 \l 1048 [6]

Jobul J i , j este activat (stare:„activated”) va emite o cerere către semafor pentru resurse. Dacă acestea sunt scurte, conform modelului FMLP, jobul va fi blocat (stare:„blocked”) dacă solicitarea nu poate fi satisfăcută imediat și așteaptă în mod activ până când se înregistrează progres. Altfel va începe să ruleze (stare:„running”). Dacă un job în curs de execuție este suspendat de unul cu prioritate mai mare va trece în starea de „pregătit” (stare:„ready”)și își va relua rularea(„resume”) când procesul mai prioritar se va finaliza. Când execuția jobului se încheie acesta este terminat („Terminated”). Ilustrare in figura 5. [6]

Modelele de semafoare

1. Toate semafoarele sunt binare și doar un singur proces îl poate deține la un moment dat și deci poate accesa exclusiv resursa l protejată de acesta

2. Se introduc și semafoare de numărare, unde valoarea contorului denotă numărul de procese cărora li se poate permite să acceseze o resursă. Se poate face o analogie a semafoarelor descrise cu situațiile de scriere-citire astfel, semafoarele binare sunt folosite pentru a permite scrierea iar cele de numărare gestionează procesele de citire. Accesarea acestora se bazează pe modelul task-fair.

Este utilizat în acest caz doar modelul resurselor scurte care așteptă în mod activ și deși sunt adoptate categoriile de resurse de la FMLP pentru evitarea deadlock-urilor, diferența principală dintre OSK-PCP și acesta și lucrul cu priorități statice.

Simul[rile au demonstrat că semafoarele de numărare reduc overhead-ul de sincronizare și ca deadlock-urile sunt într-adevăr evitate cu succes.

2. FMLPExistă și variante modificate pentru îndeplinirea unor scopuri concrete, cum este GSN-EDF -

pentru job-uri suspendabile și non-preemptibile. Este necesară o variantă a G-EDF care garantează că un job poate fi blocat de un alt job nepreemptibil decât când acesta este eliberat sau reluat și că durata unui astfel de eveniment este menținută în limite rezonabile. Așadar putem spune că un job este blocat în mod ne-preemptobil la timpul t dacă acesta este unul din cele mai prioritare m joburi executabile dar nu este planificat la timpul t deoarece un job ne-preemptil de prioritate mai mică este programat în locul său. Pentru ca job-urile să aibă secțiuni nonpreemptibile trebuie respectată următoarea regulă: Fie m numărul maxim de job-uri care pot rula simultan șiq (¿m) numărul de task-uri non-preemptibile existente; la un moment de timp dat vor fi planificate în primul rând aceastea iar capacitatea rămasă va rula până la m-q joburi preemptibile în ordinea priorităților. Problema acestei stategii este că un job T i

j poate fi blocat nepreemptibil ori de câte ori alte joburi sunt eliberate sau reluate.

Comportamentul descris mai sus poate fi evitat dacă se presupune că fiecare job executabil este legat la un procesor, cu posibilitatea de a fi dezelgat de acesta. În condițiile în care toate job-urile sunt privite ca preemptibile, un job este definit ca fiind alocat unui procesor la timpul t dacă, conform funcționării G-EDF acesta ar fi planificat la momentul de timp t pe respectivul procesor.

Așadar la momentul de timp t dacă există măcar m job-uri executabile, primele m în ordine priorității vor fi legate la un procesor.

Dacă un job este legat de unul din procesoare dar nu este programat efectiv pe acesta, job-ul este blocat ne-preemptibil.

Dacă un job este programat la timpul t dar este nu este legat de un procesor atunci acesta nu se numără printe cele mai prioritare m job-uri dar este totuși planificat la t deoarece este ne-preemptibil.

Se conturează două teoreme caracteristice GSN-EDF care pot fi utilizate pentru intuirea timpilor de blocare pentru acest sistem [9]

Teorema 1: Dacă un job în așteptare T ij este legat de un procesor dar nu programat la momentul t ,

atunci acesta s-a aflat continuu în această stare de la ultimul moment de timp la care T ij a fost eliberat

sau reluat.

Teorema 2: Fie job-ul T ij legat la procesorul k la momentul de timp t și presupunând că T i

j nu este

programat la t . Notăm cu tD intervalul maxim de timp pentru care un job T ab de prioritate mai mică

decât T ij care este programat la momentul de timp t pe procesorul k poate executa ne preemptibil.

Conform GSN-EDF, până la momentul de timp t+ tD, T ijva fi planificat pentru execuție sau dezlegat de

procesorul k .

FMLP -Flexible Multiprocessor Locking Protocol Protocol flexibil de blocare pentru multiprocesoare, poartă numele de flexibil deoarece poate fi aplicat atât pe sistemele cu planificare globală cât și pe cele cu planificare partiționată. Problema pe care o adresează acest protocol este ce se petrece cu o solicitare de acces la resurse atunci când aceasta nu poate fi satisfăcută imediat. Dacă task-ul se suspendă cum se întâmplă în cazurile M-PCP/D-PCP atunci timpul maxim de blocare este afectat negativ. În schimb, dacă job-urile intră într-o stare de așteptare activă din care nu pot fi preemptate

atunci numărul de task-uri care pot fi blocate simultan la orice moment de timp pe aceeași resursă se limitează la m-1. Această strategie va pro duce și scăderea, posibil dramatică , a volumul de activitate utilă pe care sistemul este capabil să o realizeze într-un timp dat. Performanțele sistemului pot fi deteriorate și prin alegerea unei metode prea pesimiste de evitare a deadlock-urilor care va inactiva inutil procesoarele

Pentru asigurarea unui paralelism adecvat în desfășurarea calcului și stabilirea echilibrului între așteptarea activă și suspendarea task-urilor sunt folosite trei metode. Prima idee presupune diferențierea între resurse în funcție de durata pentru care acestea pot fi deținută de un job (orice job). Resursele sunt împărțite deci în lungi și scurte iar categoria în care este repartizată o resursă este specificată de utilizator (și cunoscută dinainte). Așteptarea activă se va folosi numai pentru resursele care sunt eliberate rapid (scurte). A doua idee presupune executarea acestora non-preemptibil pentru a minimiza timpul de așteptare activă. Singura limitare impusă privește înglobarea solicitărilor, prin faptul că cererile de acces la resurse lungi nu pot fi incluse în cele care vizează resurse scurte. A treia cerință respectată asigură gruparea resursele în așa fel încât solicitările pentru resursele scurte , independente („non-nested”) sunt rezolvate rapid și eficient. Aceste tactici asigură evitarea deadlock-urilor și reducerea suprasolicitărilor.

Grupurile de resurse sunt fundamentul strategiilor de blocare în FMLP, fiecare grup conținând exclusiv resurse de timpul său (lungi/scurte). Un grup este protejat de o metodă de încuiere pe întreg grupul („group lock”) care este un semafor în cazul resurselor lungi și o încuietoare tip coadă pentru resursele scurte. Se consideră că două resurse l1 și l2 , fac parte din același grup dacă există un job care emite o solicitare pentru l1 care este conținută într-o cerere de acces la l2 iar l1 și l2 sunt de același tip.# Algoritmul gestionează eficient solicitările pentru resurse ce nu pot fi înglobate prin gruparea individuală ceea ce îmbunătățește paralelismul. [9]

De remarcat că în cazul FMLP termenii descriși anterior de solicitare non-nestable și extrem exterioară sunt mai nuanțați după cum urmează:

Cererile de acces la resurse lungi non-nestable pot conține solicitări de acces la resurse scurte Cererile de acces la resurse scurte sunt considerate extrem exterioare dacă nu mai sunt

conținute într-o altă cerere pentru resurse scurte (pot fi incluse în solicitări pentru resurse lungi)

În cazul resurselor scurte c un job să aibă acces la o resursă l aceasta trebuie să intre în posesia Group lock-ului corespunzător grupului din care face parte l. Am spus că „încuierea” resurselor scurte de face cu ajutorul unei cozi în care așteptarea se va face activ în ordine FIFO(„First-In-First-Out”). Ca job-ul să poată intra în posesia cheii aceasta trebuie să devina non-preemptibil și să rămână astfel până când eliberează resursa( după ce a achiziționată și folosit-o). Dacă mai există solicitări înglobate în cea extrem externă ele vor fi satisfăcute imediat întrucât ele obligatoriu vizează resurse din același grup ca prima accesată iar întregul grup de resurse se află la dispoziția job-ului din momentul în care a achiziționat group lock-ul. Group lock-ul este eliberat când este satisfăcută cererea extrem exterioară. [9]

Și pentru resursele lungi este necesară obținerea group lock-ului pentru a accesa o resursă din acel grup. Se folosește o „încuiere” tip semafor conform căreia obiectele blocate sunt adăugate unei cozi FIFO și apoi suspendate. Un job care deține accesul la un grup de resurse lungi va moșteni prioritatea maximă a oricăreia dintre celelalte task-uri blocate pe grupul respectiv de resurse și va fi planificat preemtibil. Dacă solicitările înglobate în acestea sunt lungi atunci accesul va fi acordat imediat întrucât

întreg grupul de resurse este deținut de job. În schimb, dacă sunt incluse și solicitări pentru resurse scurte atunci job-ul trebuie să demareze protocolul de obținere a accesului la resurse scurte. Job-ul revine la prioritatea inițială (proprie) când termină de utilizat resursele cerute inițial și eliberează grup lock-ul iar primul job din coada FIFO (dacă acesta există) este reluat și eliminat din coadă. [9]

Se remarcă o consecința subtilă care reiese din mecanismul de moștenire a priorității prezent în GSN-EDF: dacă la timpul t un job T i

j care este programat pe procesorul k moștenește prioritatea lui T ab,

atunci era inițial planificat pentru execuție pe un procesor q dar a fost suspendat la timpul t. Dacă există și un job T x

y (în afară de T ij ) care este legat tot la procesorul k, atunci algoritmul FMLP va muta acest

task pe procesorul q eliberat permițându-i lui T ij să își continue execuția pe nucleul k de care și devine

legat. Acest mecanism va preveni schimbarea inutilă a procesoarelor.

Teorema : FMLP este un algoritm de blocare și sincronizare în care nu apar situații de tip deadlock. Demonstrația acestei teoreme se face prin reducere la absurd (principiul terțului exclus) după cum urmează.

Fie : Considerăm o slujbă oarecare T ijcare face parte dintr-un lanț de job-uri blocate într-un

deadlock care a ajuns în această stare prin solicitarea R ce nu poate fi satisfăcută. Un deadlock poate să apară numai atunci când există un lanț închis de job-uri, circular, în care fiecare verigă este blocată pe o resursă din grupul deținut de job-ul următor din lanț. Pentru ca T i

jsă fie parte dint-un lanț de blocare job-ul trebuie să dețină deja o resursă așadar cerea R este obligatoriu înglobată într-o alta

Dacă: Din modul de definire a resurselor cunoaștem că R nu poate fi o solicitare internă, înglobată, (nici pentru resurse lungi , nici pentru unele scurte) deoarece acestea nu pot pune niciodată un job în situația de a fi blocat. Având în vedere că cererile de acces la resurse lungi nu pot fi conținute în cereri de acces la resurse scurte iar solicitarea care a dus la blocarea task-ului nu este conținută într-o alta de același tip, este obligatoriu ca R să fie prima solicitare a resurselor de tip scurt conținută într-un șir de cereri de acces la resurse lungi.

Atunci: T ij nu deține încă accesul la niciun fel de resurse scurte. Extrapolând, putem spune că

într-un lanț de job-uri blocate niciunul dintre acestea nu deține resurse scurte dar în același timp toate s-au blocat în încercarea de a achiziționa resurse scurte. Acest lucru este o contradicție. [9]

Blocarea în contextul GSN-EDF cu FMLP

Termenul de blocare se referă, după cum am spus, la întârzierile suferite de un job T ij din cauza

așteptării active și a suspendărilor care nu apar din cauza preemtării acesteia de job-uri cu prioritate mai mare. Având în vedere că în această configurație la orice moment de timp primele m job-uri în ordinea priorității sun legat la un procesor, un job se consideră a fi blocat la un moment de timp dacă este unul din cele mai prioritare m instanțe dar nu poate și planificat sau se află în așteptare activă. Blocarea poate fi realizată atât de job-uri cu prioritate mai mică , cât și de unele cu prioritate mai mare.

Așteptarea activă („busy-wait”) este intervalul în care un job așteaptă obținerea unei resurse scurte. Notăm timpul maxim pe care un job îl poate petrece în așteptare activă cu BW(T i)

Blocarea directă: Apare atunci când un job aflat printre cele mai prioritare cere acces la o resursă lungă deja deținută de un job în desfășurare și se suspendă. Notăm timpul maxim pe care un job îl poate petrece blocat în mod direct cu NPB(T i)

Blocarea ne-preemptivă: Se petrece atunci când un job ne-preemptibil de prioritate mai mică nu permite planificarea și execuției instanței unui task cu prioritate mai mare. Notăm timpul maxim pe care un job îl poate petrece blocat ne-preemptiv cu DB(T i)

Așadar timpul maxim în care job-ul unui task poate fi blocat B(T i) este

B(T i)= BW(T i)+ NPB(T i)+ DB(T i)

FMLP poate fi adaptat și sistemelor partiționate și în continuare vor fi descrise pe scurt modul de funcționare în aceste cazuri particulare. Pentru ca implementarea FMLP pe P-EDF să fie avantajoasă sunt necesare mici modificări care să permită unui job să devină non-preemptibil sau să se suspende la orice moment de timp. Algoritmul rezultat se numește PSN-EDF și decide ca dacă există la timpul t un job non-preemptibil în așteptare , alocat unui procesor k atunci acesta este programat la timpul t pe procesorul k. În lipsa job-urilor ne-preemptibile, pe procesorul k va fi planificat(dacă există) la timpul t jobul de cea mai mare prioritate dintre cele care îi sunt alocate acestui procesor. Un task îi este vecin („local”) unui alt task dacă sunt alocate aceluiași procesor și respectiv îndepărtată („remote”) în caz contrar. O resursă este numită locală atunci când toate job-urile care cer accesul la ea sunt alocate aceluiași procesor iar în caz contrar sunt globale. [9]

Clasificarea resurselor ca scurte și lungi se aplică doar celor globale, această distincție fiind și principala diferență dintre PSN-EDF și GSN-EDF. Complicația care apare în acest caz este faptul că se poate ajunge în situația în care un job care deține o resursă nu este cel mai prioritar pe nucleul său. Nu există nicio modalitate clară de rezolvare a acestei probleme întrucât compararea priorităților unor job-uri aflate pe procesoare diferite este lipsită de sens. Acest lucru se datorează încărcării diferite a celor două nuclee de procesare; astfel o resursă care are un deadline îndepărtat și ar avea prioritate mică pe un procesor încărcat poate fi printre cele mai prioritare pe un procesor cu puține task-uri la momentul respectiv de timp. Nici moștenirea priorității nu este o soluție bună pentru această problemă deoarece s-a demonstrat ca nu poate micșora timpii de așteptare.

O variantă de gestionare a problemei presupune că un job care este programat și deține o resursă devin nepreemptibil până la eliberarea resursei, indiferent dacă aceasta este lungă sau scurtă. La fel ca și în cazul GSN-EDF cererile de acces la resurse sunt procesate după regulile FIFO. Adaptarea la varianta partiționată de planificare a task-urilor prevede o modalitate de rezolvare a conflictelor care apar între job-urile locale și cele globale. Un job global blocat de unul local poate ține pe loc întreg sistemul așadar trebuie deblocată cât mai rapid. Din acest motiv instanța locală a unui task care blochează în mod direct o instanță de task globală va moșteni prioritatea celei globale. [9]

3. PWLPAcest protocol de partiționare a resurselor bazat pe „încuieri” se bazează pe modelul așteptării

active care acceptă atât planificarea globală cât și pe cea partiționată cu priorități fixe( de job sau task) sau alocate dinamic. Protocolul permite preemptarea task-urilor de prioritate inferioară de către cele cu prioritate mai mare în perioade de așteptare activă motiv pentru care a fost denumit PWLP – Preepmtable Waiting Locking Protocol. În schimb job-urilor aflate în perioada critică sunt ne-preemptibile.

În descrierea acestui protocol se folosesc 4 stări corelate conform schemei de mai jos:

Figura 6 Diagrama stărilor pentru un job . Cercurile albe reprezintă sterile active(când job-ul este planifict pe un nucleu) cele gri stările pasive (când job-ul este susăendat) [9]

Un job T ijaflat inițial în starea „ready” – pregatită deci se află în așteptare pentru a fi prorgamată

pe un nucleu. În momentu ăn care acest job este programat și începe sa ruleze se afă în execuție . Dacă din această stare este suspendată de un alt job cu prioritate mai mare se întoarce în starea de pregătire și reintră în execuție atunci când instanța cu prioritate mai mare și-a finalizat execuția. În timpul execuției este foarte probabil ca job-ul să necesite accesul la resurse partajate, caz în care va emite o solicitare de acces la respectiva resursă/respectivul grup de resurse. Dacă cererea este satisfăcută imediat atunci job-ul intră în secțiunea critică și rămâne în execuție; în caz contrar trece în starea de sondare – „polling” ce înseamnă ca job-ul rămâne planificat și așteaptă activ eliberarea resursei. Odată eliberată resursa T i

j îsi reia execuția. Dacă, în schimb, job-ul aflat în curs de sondare este preemptat de

un job de prioritate mai mare el este suspendat și devine parcat. Dacă T ij este planificat imediat atunci

când celălalt job iși încheie execuția atunci va reveni în starea de sondare, altfel, la eliberarea resursei el automat trece în starea activă pregătit și așteaptă să fie programat pentru a trece în stare de execuție. [9] [3]

Figura 7 Structura de bază a fazelor prin care trece o solicitare pentru o resursă scurtă conform FMLP â. Atât perioada de așteptare activă cât și cea critică sunt nepreemptibile. [9]

Figura 8 Structura de bază a fazelor prin care trece o solicitare pentru o resursă scurtă conform PWLP. Doar perioada critică este nepreemptibilă, cea de așteptare activă fiind preemptibilă [9]

Acest protocol este cel mai bine ilustrat prin modul în care se aplică pe resurse de tip scurt din modelul descris de autorii FMLP deoarece pentru acest tip de resurse se folosește așteptarea activă. Sunt permise cererile de acces la resurse înglobate cu anumite restricții pentru evitarea deadlock-urilor și semafoarele folosite sunt de tip mutex (dar pot fi folosite și cele de tip coadă). Principala diferență a PWLP față de FMLP este modul în care sunt gestionate solicitările pentru resurse în perioada de așteptare activă. După cum am descris anterior, FMLP nu permite preemptarea în această etapă și servirea job-urilor se face în ordinea emiterii cererii de acces. Acest lucru poate determina apariția unui număr neplăcut de mare de inversiuni de prioritate. PWLP încercă evitarea situației descrise și permite ca job-urile cu prioritate mai mică să fie preemptate de unele cu prioritate mai mare atunci când mai multe job-uri sondează simultan pentru o resursă. Conform ambelor protocoale secțiunile critice sunt ne-preemptibile.

Se construi o listă de reguli care guvernează tratarea solicitărilor de acces la resurse. Se menționează că există o coadă de tip FIFO pentru fiecare resursă/grup de resurse în parte.

1. cerere de acces la o anumită resursă este adăugată cozii FIFO a resursei 2. Atunci când o solicitare este satisfăcută job-ul care a emis-o trebuie să se afle în capul cozii,

altfel accesul la resursă nu va fi permis3. Dacă accesul job-ului la resursă nu este permis atunci job-ul trece din starea de execuție în stare

de sondare și așteaptă în mod activ.4. Atunci când o resursă este eliberată de job-ul care a deținut-o acesta este șters din coada FIFO.5. Dacă un job cu prioritate mai mare determină suspendarea unui job în curs de sondare acesta

intră în execuție iar job-ul preemptat devine parcat.6. Dacă un job de prioritate mai mică decât cel aflat în sondare este activat atunci demersul

acestuia nu va fi întrerupt iar instanța task-ului de prioritate mai mică va rămâne doar în stare activă.

7. Atunci când o resursă este eliberată de job-ul care a deținut-o , aflat încă în execuție, și mai există joburi în așteptare activă care doresc accesul la resursă , job-ul din fruntea cozii FIFO va trece doar în stare pregătită dacă are prioritate mai mică decât cel aflat încă în rulare iar solicitarea sa de acces la resursă va fi ștearsă.

8. Atunci când un job-ul care a redevenit activ conform regulii anterioare este programat și intra în execuție acesta nu are acces imediat la resursa dorită ci va trebui să inițieze din nou protocolul de obținerea a acesteia.

Se poate demonstra că utilizând aceste strategii deadlock-urile pot fi evitate în totalitate dacă demonstră imposibilitatea cazurilor în care aceste blocări apar. O situație se definește prin momentul în care un job este preemptat în timp ce deține o resursă și cel puțin un alt job de prioritate mai mare, aflat

în execuție, așteaptă pentru acea resursă. Acest caz este exclus din start deoarece în perioada critică instanțele task-urilor nu sunt preemptibile. Altă variantă posibilă este dată de momentul în care cerea de acces este satisfăcută pentru o resursă aflată într-o stare pasivă: pregătită sau parcată ( marcate cu gri în figura 6). Conform regulii 7 acest caz este evitat de faptul că solicitările de resurse sunt șterse din coada FIFO atunci când trec din stare parcată în pregătită. ( conform definirii stării pregătite, job-urile din această categorie nu au emis vreo cerere de acces la resurse încă iar cel aflate în stare parcată nu au cum să fie în capul listei FIFO). Aceste scenarii fiind excluse mai rămâne doar posibilitatea apariției unui deadlock ca urmare a unor erori de înglobare a cererilor de acces sau în urma încălcării altor constrângeri de model. Modul în care este construit modelul de date adoptat , cel propus pentru FMLP și descris mai sus, nu permite apariția unor astfel de situații.

Blocarea în PWLP poate să apară ca urmare a așteptării active pe un nucleu sau poate fi blocare non-preemptivă datorată unui job de prioritate mai mică dar care își execută secțiunea critică. Dacă se notează cu T spin i , j timpul maxim pe care un job îl poate petrece în așteptare activă fără a fi preemptat de un alt job. Numărul maxim de situații în care un job în așteptare este preemptat de task-uri cu prioritate este notat cu A. Limita sa superioară ține numărul de task-uri cu prioritate mai mare care pot fi eliberate în timp ce job-ul considerat așteaptă. Astfel putem defini mBWB ca fiind timpul maxim petrecut de un job în așteptare activă pentru jobul task-ului T i. [9]

mBWB (T i )≤ A ∙∑R∈Q

T spini , j

Timpul maxim de blocare nepreemptivă în cazul PWLP este dată de durata de execuție a celui mai lungi perioade critice posibile a unui job de prioritate mai mică. Notăm cu B setul de task-uri existente ce au prioritate mai mică decât cea de interes și cu np timpul de execuție nepreemptibilă secțiunii critrice.

NP (T i )≤max {np (B ) }

Figura 9 Exemplu de planificare(partiționată) cu ajutorul variantei cu resurse scurte a FMLP.

Figura 10 Exemplu de planificare (partiționată) cu PWLP pentru resurse scurte

În figura 11 task-ul 2 este activat pe nucleul 1 la timpul 2 și începe să sondeze pentru acces la resursa partajată. La momentul de timp 3 când se este eliberat task-ul 1, de prioritate mai mare acesta preemptează task-ul 2 care întră în starea de „parcat” - așteptare pasivă. Când task-ul de prioritate mare se finalizează la t=6 celălalt devine activ și începe să execute și cum task-ul 3 de pe procesorul 2 a eliberat între timp resursa acesta își poate continua lucrul neîntrerupt. Dacă resursa nu era disponibilă atunci task-ul 2 intra în stare de sondare – așteptare activă. În acest mod task-ul de prioritate maximă

este finalizat primul. Dacă procesul era gestionat cu FMLP atunci task-ul 2 se bloca la momentul 2 când nu reușea să obțină acces la resursa dorită și neputând fi preemptat îl ținea pe loc și pe task-ul 1 de prioritate mare . Astfel timpul de finalizare al task-ului 1 ar fi fost 10 în loc de 6, iar timpul necesar finalizării tuturor proceselor ar fi fost mai lung cu o unitate. [9]

Este important că folosind PWLP se pot evita cu certitudine dealock-urile , chiar și atunci când se permite înglobarea solicitărilor de acces. Avantajul acestui protocol este că limitează perioadele de inversiuni de priorități la durata secțiunilor critice. Putem așadar spune că pentru sistemele în timp real, care de obicei au timpi de execuție și dealine-uri scurte și pentru sistemele care pot să devine critice la declanșarea anumitor evenimente, sincronizarea cu PWLP este preferabilă alternativei FMLP. [9]

4. M-BWIScopul acestor protocoale este să garanteze izolarea temporală intre task-urile ce nu

interacționează. Un mod eficient de a obține acest lucru în sistemele în timp real este utilizarea paradigmei de rezervare a resurselor. Principiul de funcționare presupune „ambalarea” task-urilor în niște entități planificabile numite servere care monitorizează și limitează utilizarea resurselor de resursele conținute.

Un server Si are un buget maxim Qi și o perioadă Pi și deservește un singur task. Serverul este tratat de către planificator ca un task și poate fi programa la un anumit moment de timp, primind o prioritate conform criteriilor în vigoare. Serverul poate genera job-uri ce au deadline și o durată maximă de rulare limitată la bugetul serverului. Aceste deadline-urile pe care le au job-urile lansate de servere sunt un pic diferite de deadline-urile absolute ale task-urilor și vor fi numite deadline-uri de planificare. Ele sunt calculate conform algoritmului de rezervare de resurse și sunt utilizate doar pentru planificarea task-urilor (ex. ordonarea cozilor de așteptare). Se remarcă că în utilizarea acestui algoritm priorotățile nu sunt alocate task-urilor în mod direct, ci serverelor. Un set de server este considerat programabil printr-o strategie dacă toate task-urile din set pot fi planificat astfel încât să își respecte timpul limită. Dacă un set de servere poate fi planificat conform metodei alese și există o relație logică și coerentă în construirea acestora în jurul task-urilor, atunci va rezulta automat și posibilitatea de a programa cu succes task-urile. Reguli minime ale construcției corecte a unui server sunt ca bugetul său să nu fie mai sub timpul maxim pesimist prezis de execuție a task-ului iar perioada sa nu are trebui să depășească timpul minim ce poate separa inițierea a două task-uri consecutive. [2]

Algoritmii de rezervare de resurse sunt în mare regulile aplicate în recalcularea bugetelor, reportarea acestuia și respectiv de strategia de suspendare a task-urilor. Task-urile sunt așadar conținute în parametrii serverului astfel: task-ului i se garantează un tip de rulare de minim Qi momente de timp odată la Pi unități de timp. Consecințele sunt separarea task-urilor între ele ; cu alte cuvinte fiecare task este protejat de celelalte iar capacitatea sa de a se încadra cu succes în limita sa de timp depinde exclusiv de propriul comportament. Trăsătura algoritmului de a asigura fiecărui task cantitatea necesară de putere de calcul fără niciun fel de interferențe de la celelalte procese care rulează în mediu se numește izolare temporală. [2]

Constant Bandwidth Server și Sporadic Server sunt doi algoritmi de rezervare de resurse ce folosesc priorități alocate dinamic și respectiv fix în planificarea task-urilor. Și un astfel de algoritm poate fi descris cu ajutorul unei mașini de stări iar diagrama se observă în figura 12. un server are un buget curent, care se consumă ce task-ul servit execută. Din starea inițială de inactivitate „idle”, un server trece în stare activă când un job al task-ului său este activat iar planificatorul îl adaugă în coada de procese pregătite. Prioritatea și bugetul serverului sunt de asemenea recalculate conform algoritmului guvernant. Când task-ul începe să ruleze serverul în execuție și își consumă bugetul . Dacă din starea de execuție este preemptat el va redeveni activ, dacă se task-ul se suspendă de la sine el se va inactiva ar dacă bugetul său se termină atunci va intra într-o stare particulară, de reîncărcare. Pentru a putea reintra în stare activă , la venirea din „idle” sau din perioada de reîncărcare se va verifica dacă trebuie actualizate bugetul și prioritatea.

Figura 11 Diagrama stărilor unui server conform M-BWI

În situațiile în care se folosesc algoritmi de rezerva a resurselor poate apărea un tip specific de inversiune de prioritate datorat faptului ca un server i-a epuizat bugetul atunci când job-ul task-ului său executa secțiunea critică. În această situație job-ul va fi suspendat și va trebui să aștepte ca serverul să își refacă bugetul. Nu li se poate permite serverelor să ruleze cu bugete negative deoarece vor apărea anormalități în comportamentul întregului sistem. Pentru procesoarele simple problema a fost rezolvată prin moștenirea bugetului cumulat al tuturor job-urilor care așteaptă la o anumită resursă de către job-ul care deține resursa la momentul respectiv. Pe multiprocesoare problemele apar atunci când un job aflat pe un anume procesor solicită acces la resurse deținute de un job care rulează pe un alt procesor. Nu se justifică executarea task-ului deținător pe mai multe nuclee simultan iar suspendarea sa ar crea probleme algoritmului de rezervare de resurse deoarece protocolul cere ca job-ul suspendat să fie tratat ca și cum s-ar fi finalizat cu succes iar repornirea să fie tratată ca un job nou, ambele presupuneri fiind inexact. [2]

Soluția găsită pentru multiprocesoare se numește M-BWI - multiprocessor BandWidth Inheritance pentru care mecanismul de moștenire a lățimii de bandă intră în acțiune atunci când serverul unui job care deține deja resursa nu mai execută din cauză că a fost preemptat sau i s-a epuizat bugetul. În acest caz job-ul ce deține resursele va rula în serverului task-ului aflat în așteptare reducându-se timpul care ar fi fost irosit prin așteptarea refacerii bugetului. Conform M-BWI task-urile care nu pot obține imediat accesul la resurse intră într-o stare de așteptare activă până la eliberarea resurselor. Se remarcă importanța catalogării corecte a status-ului job-ului și serverului ce dețin resursa și respectiv relevanța mecanismului de ordonare a task-urilor aflate în așteptare. [2]

Figura 12 Diagrama stărilor și tranzițiilor pentru un server conform M-BWI

Varianta pentru multiprocesoare a protocolului cu moștenirea lățimii de bandă are o serie mai complexă de stări și tranziții posibile. Toate stările descrise în figura 13 sunt grupate într-o stare compusă denumită stare de rezervare – „Reservation”. Serverul rămâne în domeniul acesta atâta timp cât nu încearcă să obțină accesul la o resursă partajată, la emiterea cererii de lock va trece într-o fază a stării complexe notate cu BWI.

Notăm cu λ j setul de task-uri al căror acces la o resursă este blocat se taskul T j; ρkva reprezenta toate task-urile în așteptare pentru resursa Rk , inclusiv task-ul care o deține. S jeste serverul task-ului T j iar Λ j este mulțimea serverelor moștenite de acesta, inclusiv S j.

Se vor explica regulile de funcționare a protocolului îmbunătățit

Regula de blocare: Când task-ul T iexecută pe serverul Si și încearcă să obțină acces la resursa Rk , serverul trece în starea de funcționare - Running a stării compuse BWI, care se observă că este la rândul sau alcătuită sin starea de execuție - Executing și cea de Așteptare activa - spinning . T i va face acum parte din ρk și vor fi posibile două situații:

Resursa este disponibilă și serverul trece direct în starea de execuție și rulează secțiunea critică. Resursa nu este disponibilă, așadar se urmărește lanțul de blocaj până la descoperirea celei care

nu este blocată , notată T j. Serveul Si este moștenit de task-ul în rulare și se adaugă mulțimii Λ j

. Dacă T j este deja în execuție pe un alt server pe un procesor, atunci T i trece în stare de aștepatre activă. Altfel intră în stare de execuție și rulează T j, operație care poate însemna migrarea task-ului și între procesoare.

Indiferent care din variante se îndeplinește serverul Sinu se suspendă. [2]

Regula de preemptare : Există două cazuri și pentru situația în care serverul Si este preemptat cât timp se află în stare de funcționare, trecând în stare activă. Dacă sub-starea de funcționarea era cea de așteptare activă atunci Si trece pur și simpli în stare activă. [2]

Dacă starea de funcționare de plecare era cea de execuție task-ului T j atunci Λ j, lista serverelor moștenite de acesta, este parcursă în căutarea unu alt server Sk care se află de

asemenea în stare de funcționare. Acesta poate fi doar în așteptare activă și este mutat în sub-starea de execuție pentru a lucra la task-ul T j.

Dacă sunt mai multe servere în așteptare activă va fi ales doar unul din ele pe baza unui anumit criteriu cum ar fi bugetul rămas cel mai mare sau termenul limită cel mai apropiat temporal. Această operație pate presupune migrarea de pe un nucleu de calcul pe altul.

Regula de reîncărcare: Dacă un server își epuizează bugetul, el trece în starea de reîncărcare după același mecanism ca și cel de preemptare descris anterior. [2]

Regula de emitere/trimitere: Dacă serverul Si aflat în stare activă ( a BWI) este angrenat el trece în stare de funcționare și comportamentul este asemănător celui pe care task-urile îl au la blocare. [2]

Dacă task-ul care deține resursa este deja în desfășurare pe un alt server pe un procesor atunci Si intră în stare de așteptare activă.

Dacă task-ul care deține resursa nu rulează deja atunci Si va trece în stare de execuție și va deservi acel task.

Regula de blocare intern ă: Atunci când un task care deține deja o resursă Rk și încearcă să obțină acces la o altă resursă Rh (în cazul solicitărilor de acces înglobate) , procedeul respectat este foarte asemănător celor de blocare simplă. Mai exact, dacă resursa este ocupată este identificat deținătorul și acesta moștenește serverul Si iar dacă task-ul respectiv este deja în rulare, serverul intră în așteptare activă. [2]

Regula de deblocare: Un task T j care termină de executat secțiunea critică ce implică o resursă Rk ce a fost cerută printr-o solicitare extremă extern eliberează resursa (Serverul task-ului S j se află în stare de execuție BWI). Dacă în mulțimea ρk se află task-uri blocate pe Rk , primul în ordinea cozii FIFO:T i este activat. Aceasta va moșteni toate serverele deținute inițial de T j , iar T j le va pierde pe toate mai puțin pe cel propriu. S j nu mai deține niciun fel de legătură cu resursa, așa că va ieși din starea compusă BWI și va reveni în rezervația sa, în sub-stare de execuție („running”). Este posibil ca la acest ultim pas să se producă o migrațiune de pe un procesor pe un altul. [2]

Regula de deblocare internă: Se referă la situația în care există solicitări de resurse înglobate și una din cele interne s-a finalizat. Resursa Rkeste eliberată de task-ul T j iar serverul său se află încă în starea BWI de execuție. Dacă în mulțimea ρk se află task-uri blocate pe Rk , primul în ordinea cozii FIFO:T i este activat. Task-ul terminat este scos din ρk iar T jpierde toate serverele pe care le dețiena mai puti pe cel propriu. T i moștenește toate serverele pe care le avea T j anterior, mai puțin pe S j . [2]

Regula suspendării: Într-un sistem deschis unde nu toate aspectele sunt strict controlate se poate întâmpla ca un task T j care deține o resursă din cele manageriate cu M-BWI să se suspende singur sau să se blocheze pe o resursă care nu face parte din cele guvernate de M-BWI. Acest lucru este inacceptabil în sistemele în timp real „hard” deoarece va duce la rezultate ce nu pot fi prezise și poate dezechilibra întregul sistem. La întâlnirea acestei situații toate serverele din Λ j trec în stare BWI inactivă și sunt șterse din cozile de așteptare până când task-ul blocat T jse trezește din nou. Când acesta se activează toate servele din Λ j intră în starea M-BWI activă și se reiau regulile algoritmului de rezervare a resurselor pentru a recalcula bugetele serverelor și prioritățile acestora. [2]

Pentru a înțelege mai bine funcționarea M-BWI este prezentat următorul exemplu:

În figura 14 este prezentat un exemplu de situație cu două procesoare și 3 task-uri; A, B și C cu SA , SB și SC serverele lor inițiale. Cum conform acestui protocol task-urile pot executa și pe alte servere, task-ul aflat în execuție la un moment de timp dat este specificat prin litera scrisă în dreptunghiul task-ului. Indicele literei specifică ce resursă este acționată de respectivul task. Culoarea albă a dreptunghiului marchează execuția unor bucăți de cod necritice, nuanța deschisă de gri marchează execuția regiunilor critice iar nuanțele de gri închis marchează perioadele de așteptare activă. Săgețile punctate orientate în sus reprezintă evenimentele de moștenire. [2]

Figura 13 Trei task-uri pe 2 procesoare cu o resursă pusă la comun [2]

La momentul de timp 6, T B încearcă să abțină accesul al R1 care este deja în posesia lui T C, motiv pentru care T C moștenește SB și începe să execute în el secțiune critică asupra R1. Când T A încearcă de asemenea să obțină acces la resursă la timpul 9, atât T C cât și T C moștenesc SA . Atât SB cât și SA pot să execute T C așa că unul din ele trebuie să intre în stare de asșteptare activă; este ales SB pentru continuarea execuției. La momentul de timp 14 când este finalizată execuția lui T C șiR1 este eliberată, T B va intra în posesia resursei și nu T A. [2]

Se pot defini câteva teoreme de funcționare a acestui protocol: [2]

Teorema 1: Dacă M-BWI este folosit drept un protocol de acces la resurse, un task nu execută niciodată pe ai mult de un server la un moment de timp.

Teorema 2: Dacă se consideră contextul unui set de rezervații de resurse partiționate gestionate de M-BWI și un task T i și toate celelalte care interacționează cu acesta nu se suspendă niciodată în timpul execuției unui segment critic și nu acceseze resurse din afara BWI. În aceste condiții serverul Si are întotdeauna exact un task ne-blocat pe care să îl servească și nu ajunge niciodată în starea „idle”.

Teorema 3: Dacă considerăm un set de rezervații de resurse partajate care este planificabil pe un sistem care folosește M-BWI ca protocol de acces la resurse atunci toate serverele își vor respecta deadline-urile.

III. Comparații. Concluzii1. Recapitulare

Evoluția constantă a capacității de calcul și stocare s-a produs în încercarea de a îndeplini cât mai eficient, cu un consum cât mai mic de energie, spațiu și resurse nevoile din ce în ce mai complexe și exigente ale aplicațiilor din ziua de astăzi. Soluțiile software care guvernează hardware-ul existent trenuie de asemenea să se adapteze modificărilor pentru ca soluția finală să de o calitate satisfăcătorae. Gestiunea proceselor pe sisteme multicore aduce cu sine o serie de dificultăți în special în ceea ce privește accesul coocurent la resurse partajate pentru a îndeplini o serie de criterii specifice sistemelor în timp real.

Pentru sistemele dedicate în timp real pot fi extrem de periculoase situațiile conflictuale de tipul inversiunilor de prioritate și deallock deoarece consecințele resimțite pot produce daune mari în mediul fizic în care funcționează aplicația. În această lucrare au fost prezentați câțiva algoritmi care propun strategii diferite de gestiune a accesului la resurse comune pentru a minimiza pe cât posibil situațiile în care un job își ratează deadline-ul și pentru a scurta timpii de răspuns.

PCP-urile sunt printre primele protocoale de sincronizare propuse și deși s-au dovedit a fi impractice în realitate ele stau la baza soluțiilor performante descoperite ulterior. Deoarece sunt inspirate din programarea uniprocesoarelor, acești pionieri ai sincronizării multiprocesoarelor nu permit migrarea task-urilor între procesoare ceea ce automat limitează capacitările sistemului. Ele se bazează pe suspendarea task-urilor, abordare care s-a dovedit a nu fi mai puțin avantajoasă în comparație variantele de „busy-waiting”. D-PCP implică distribuirea resurselor la procesoare și accesarea celor care nu țin de procesorul propriu unui task prin agenți locali de prioritate superioară job-urilor native pe procesoul respectiv. M-PCP folosește doar semafoare globale și acordă task-urilor externe unui procesor prioritate mai mare decât a celor proprii. Niciunul din aceste protocoale nu permite înglobarea cererilor ceea ce este inadecvat situațiilor reale.

OSEK-PCP este o variantă modificată a PCP bazată pe priorității OSEK care este foarte folosit în domeniul transportului, fie el feroviar sau auto. El utilizează modelul de resurse categorisite în lungi și scurte propus de Block și echipa sa odată cu FMLP; astfel poate fi garantată evitarea deadlock-urilor și permisă înglobarea solicitărilor la resurse. Aceste trăsături explică și adoptarea sa cu încredere în practică.

Protocolul FMLP este un nivel de referință în domeniul de embedded real-time deoarece a adus în discuție împărțirea resurselor în scurte și lungi în funcție de durata de timp în care un job trebuie să le deține pentru a își îndeplini execuția. Regulile impuse modului de organizare a solicitărilor de acces la resurse elimină posibilitatea apariției deadlock-urilor în sistemele astfel guvernate. Așteptarea dobândirii accesului pentru resursele scurte se face prin așteptare activă pe când cererile pentru resurse lungi duc la suspendare job-ului. Protocolul este numit flexibil deoarece poate fi aplicat atât planificării globale cât și celei partiționate; prioritățile sunt alocate în funcție de deadline . Job-urile blocate pe o resursă sunt tratate în ordinea emiterii solicitărilor de acces (FIFO) iar execuția zonei critice, ca și așteptarea activă (în cazul resurselor scurte) sunt nepreemptibile.

PWLP este o altă abordare a FMLP care folosește exact același model de resurse cu diferența ca pune mai mult acces pe priorități. Mai exact, job-urile pot fi preemptate de tas-uri cu prioritate mai

mare în perioada de așteptare activă. Acest lucru promovează respectarea deadline-urilor pentru job-uri cu importante și modfică subțil funcționarea sistemului în comparație cu FMLP. Ambele protocolae au peformanșe foarte bune în ceea ce privește capacitate de planificare cu succes a task-urilor.

M-BWI este varianta adaptată pentru multiprocesoare a BWI și este o strategie care se concertează pe limitarea interacțiunii între task-uri prin încapsularea lor temporală. Acest lucru este realizează prin îmbrăcarea task-urilor în niște instanțe numite servere care vor fi de fapt elementul planificat de algoritm. Serverele deservesc un singur task și au priorități pentru ordonare care influențează bugetele acestora. Bugetele sunt practic contoare temporale care se consumă atunci când un job al serverului respectiv se află în execuție. Un buget consumat înseamnă suspendarea serverului task-ului pe timpul necesar reîncărcării (atunci când nu există în spatele task-ului alte instanțe blocate pe resursele deținute de acesta). Bugetul poate moștenești între servere ceea ce asigură întreg lanțul de job-uri aflate în interacțiune nu vor fi blocate până la refacerea bugetului serverului din capăt. Aceste principii asigură alocarea timpului proporțional necesității/priorității și ciclic tuturor task-urilor. Ele au un rol important și în implementarea modalității de abordare a priorității, aceasta fiind de asemenea moștenită între servere la blocarea unui nou job pe resursă deținută de cel în execuție. Astfel, job-ul care are la un moment de timp acces la resursa comună va avea întotdeauna prioritatea maximă dintre cele pe care le ține pe loc. Astfel se asigură execuția sa cât mai promptă și progresul ansamblului.

2. Comparații ale comportamentului și performanțelorD-PCP , M-PCP vs.FMLP

Figura 14 Capacitatea de planificare corectă în funcție de (stânga) lungimea secțiunii critice (L) și (dreapta) numărul de accesări ale resursei per job. Regimul experimental este de grad mic de împărțire a resurselor pe 4 procesoare [7]

Figura 15 Capacitatea de planificare corectă în funcție de (stânga) procentul de utilizare a procesorului (dreapta) și numărul de procesoare [7]

O serie de trenduri s-au observat în urma testării comparative a acestor protocoale variind numeroși parametrii. O primă concluzie este că niciodată nu este mai avantajoasă suspendare task-urilor prin comparație cu așteptarea activă. Întotdeauna, indiferent de caz, cele mai bune rezultate le-a avut varianta pentru resurse scurte de FMLP. Într-un număr mare de cazuri prin planificare cu cele două PCP nu s-a reușit îndeplinirea niciunui task. În schimb, FMLP pe resurse lungi a avut întotdeauna performanțe mai bune decât M-PCP care la rândul său a depășit rezultatele D-PCP la rularea pe un număr mic de procesoare(4). În situațiile în care puține resurse sunt puse în comun chir și varianta lungă de FMLP atinge un grad de planificare corectă aproape perfect , M-PCP este în jurul valorii de 75% iar D-PCP eșuează total. [7]

D-PCP depinde foarte tare de numărul de resurse puse la comun: atunci când numărul acestora este considerabil mai mare decât cel al proceselor, protocolul nu face față. În schimb, D-PCP nu este sensibil la numărul total de task-uri tocmai datorită naturii sale distribuite. Singurele job-uri care pot afecta performanțele comportamentului său sunt cele ale task-urilor alocate pe respectivul procesor. Invers, protocoalele M-PCP și FMLP permit oricărui job din sistem să îl afecteze pe cel în curs de rulare. [7]

În ceea ce privește scalabilitatea, creșterea numărului de task-uri și resurse determină scăderea rapidă a performanțelor tuturor protocoalelor bazate pe suspendarea proceselor. Din acest punct de vedere, FMLP lung și M-PCP evoluează negativ peste un număr de 6 procesoare având trenduri asemănătoare. În mod surprinzător D-PCP, nu are o involuție atât de stridentă deoarece depinde mult mai puțin de numărul total de task-uri. Blocarea cu suspendarea task-urilor nu devine mai avantajoasă pe 16 procesoare dar se schimbă puțin performanțele relative ale acestor strategii. Mai exact D-PCP devine favorabil față de M-PCP într-un număr mai mare de situații iar FMLP lung va avea performanțe mai slabe. Nici FMLP cu resurse scurte nu își păstrează scalabilitatea perfectă pentru mai mult de 6 procesoare dar va rămâne deasupra celorlalte din punct de vedere al performanțelor. [7]

Comparație de performanțe între tipurile de FMLP

Figura 16 Capacitatea de planificare corectă pentru diverse tipuri de FMLP pentru 4 procesoare și în funcție de „nesting factor” pentru o probabilitate de utilizare a fiecărei instrucțiuni de 0.1 a) și 0.3 b) [3]

Figura 17 Capacitatea de planificare corectă pentru diverse tipuri de FMLP pentru 8 procesoare și în funcție de „nesting factor” pentru o probabilitate de utilizare a fiecărei instrucțiuni de 0.1 a) și 0.3 b) [3]

Se remarcă din graficele rezultate în urm acestor simulări că pentru task-uri multe, cu factor de utilizare mic(coloana a) ) indiferent de creșterea factorului de înglobare capacitatea sistemului de a respect dealine-uri rămâne foarte aproape de 100%. Pentru situația task-urilor cu utilizare mai mare(coloana b) ) performanțele sunt puțin afectate dar rămân de calitate în cazul ambelor protocoale FMLP. L creșterea numărului de procesoare, poate părea contra-intuitiv că factorul de respectare a dealine-urilor scade mai rapid decât pentru un număr mai mic de procesoare. Creșterea nesting factor-ului determină creșterea timpului de blocare prin faptul că împrăștierea job-urilor pe mai multe procesoare induce o probabilitatea mai mare ca task-ul aflat în rulare este blocat și ține pe loc procesorul. Cu alte cuvinge, sunt mai multe task-uri care accesează simultan același set de resurse. [3]

Varianta partiționată a FMLP nu permite migrarea task-urilor între procesoare ceea ce scade performanțele globale Acest lucru se remarcă în primul rând în figura 18 b). Protocolul FMLP aplicat global își menține cele mai bune performanțe indiferent de factorii implicați în definirea sistemului. [3]

PWLP vs. FMLP

În urma testării PWLP în comparație cu FMLP nu se poate spune că unul din protocoale are universal performanțe mai bune decât celălalt. Task-urile cu importante, cu priorități ridicate ,sunt programabile cu succes conform ambelor strategii. Prin analiza situațiilor în care PWLP nu reușește să respecte deadline-urile unor job-uri se observă că acestea sunt exclusiv task-uri cu prioritate mică (adică deadline-uri îndepărtate). Justificarea acestui comportament să în faptul că PWLP permite preemptarea job-urilor „neimportante” în perioada de așteptare activă motiv pentru care aceste vor fi des suspendate pe când prin FMLP ele sunt tratate în ordinea în care emit cererile pentru resurse. În același timp, atunci când protocolul flexibile este cel folosit, task-urile cu deadline-uri apropiate nu le pot urni pe cele care au inițiat cereri de acces a resurse înaintea lor, motiv pentru care își vro depăși timpul limită într-un număr mai mare de cazuri. [9]

Figura 18 Experiment pentru 8 resurse împărțite(stânga) și doar 2 resurse împărțite(dreapta), K este numărul de accesări/resursă și în funcție de acesta se reprezintă procentul/100 de task-uri care si-au respectat corect deadline-ul. Pentru primul grafi(stânga) niciunul din protocoale nu mai poate planifica corect toate task-urile după la mai mult de 5 și respective 6 accesări/resursă pentru FMLP și respective PWLP. Atunci când sunt mai puține resurse puse la comun, idealul nu mai poate fii respectat la mai mult de o accesare/resursă. PWLP se dovedește a fi subtil mai eficient în ambele cazuri [9]

În concluzie, strategia folosită trebuie aleasă în funcție de natura aplicației și caracteristicile sistemului. FMLP se dovedește mai prolific atunci când task-urile au deadline-uri mai îndepărtate și sunt de durată mai lungă. Prin contrast, atunci când se vorbește de un sistem cu task-uri scurte, cu limite de timp situate apropiat, atunci aceste sunt ai bine organizate cu ajutorul PWLP. [9]

M-BWI vs FMLP

Figura 19 Probabilitatea ca toate task-urile să își respecte deadline-urile în funcție de durata maximă a resurselor pentru un număr de taskuri dublu față de numărul procesoarelor și un număr de resurse egal cu dublul numărului de task-uri [2]

Figura 20 Probabilitatea ca toate task-urile să își respecte deadline-urile în funcție de durata maximă a resurselor pentru un număr de taskuri de 4 ori mai mare decât numărul procesoarelor și un număr de resurse egal cu de 4 ori mai mare decât numărului de task-uri [2]

Simularea prezentată în graficele de mai sus are de suferit în ceea ce privește ilustrarea performanțelor FMLP deoarece ia în considerare timpul de așteptare la o resursă pentru toate task-urile și modul în care protocolul funcționează în cazul resurselor lungi se traduce într-o formă de blocare indirectă pentru toate task-urile intermediare chiar dacă nu sunt implicate în interacțiune. În cadrul M-BWI datorită moștenirii de prioritate nu există conceptul de inversiune de prioritate. În plus, se ca număra de mai multe ori timpul de blocare deoarece utilizarea per total include atât timpul de blocare cât și timpul necesar proceselor computaționale. Astfel se explică performanțele foarte scăzute ilustrate în imaginile de mai sus. Discordanța așadar se datorează modului forte diferit în care cele două rotocoale acționează atunci când FMLP include albele categorii de resurse. [2]

În cazul a) cu doar 4 procesoare performanțele M-BWI sunt un pic mai proaste decât ala FMLP, cel mai probabil datorită eficienței mai mari ea mecanismului de moștenire a probabilității al FMLP. În ambele situații performanțele celor două protocoale sunt aproape 100% , ambele fiind extrem de indicate pentru operații secțiuni critice scurte. [2]

Figura 21 Probabilitatea ca toate task-urile să își respecte deadline-urile în funcție de durata maximă a resurselor pentru

3. Probleme actuale și direcții viitoare. O problema de actualitate și care aduce o dimensiune în plus planificării și sincronizării pe

multiprocesoare este situația sistemelor heterogene de sisteme de calcul. Acestea denumite și sisteme multi & many core sunt unități de procesare cu mai multe nuclee de tipuri diferite și cu puteri de calcul diferite. Un exemplu banal de asemenea sistem este o placă grafică integrată pe același tip cu un procesor multi-core. Lipsa omogenității între nuclee ridică mari probleme spre exemplu în modelarea sistemului, motiv pentru care nu pot fi evaluate corect performanțele și siguranța sistemului.

De altfel, este impresionantă evoluția algoritmilor din acest subdomeniu de embedded real-time deoarece fiecare nouă soluție a încercat păstrarea punctelor tari ale variantelor deja existente simultan cu adăugarea unor noi trăsături care să crească performanțele și robustețea. Deși s-a reușit eliberarea sistemelor de problema fatală a deadlock-urilor, între protocoalele de sincronizare moderne nu există unul care să aibă performanțe ideale în orice situație. Posibilitățile vaste de variere a manierei de abordare au generat numărul mare de strategii propuse și în continuă dezvoltare. Rezultatul este o flexibilitate imensă raportat la tipicul aplicației întrucât soluția cea mai avantajoasă pentru un anumit caz depinde de parametrii ce caracterizează task-urile, resursele, hardware-ul și evident, scopul sistemului.

Figura 21 Probabilitatea ca toate task-urile să își respecte deadline-urile în funcție de durata maximă a resurselor pentru

IV. Bibliografie

[1] A. H. Tanenbaum and H. Bos, Modern Operating Systems, Pearson, 2015.

[2] D. Faggioli, G. Lipari and T. Cucinotta, "Analysis and Implementation of the Multiprocessor BandWidth Inheritance Protocol," Real-Time Systems, vol. 48, no. 6, p. 789–825, 2012.

[3] A. Block, H. Leontyev, B. B. Brandenburg and J. H. Anderson, "A Flexible Real-Time Locking Protocol for Multiprocessors," in Proceedings of 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Daegu, 2007.

[4] A. Srinivasan, "Eficient and Flexible Fair Scheduling of Real-time Tasks on Multiprocessors," University of North Carolina at Chapel Hill, Chapel Hill, 2003.

[5] Wikipedia, "Non-blocking Algorithm," Wikipedia, [Online]. Available: https://en.wikipedia.org/wiki/Non-blocking_algorithm. [Accessed 01 2017].

[6] M. Alfranseder, M. Mucha and S. Schmidhuber, "A Modified Synchronization Model for Dead-Lock Free Concurrent Execution of Strongly Interacting Task Sets in Embedded Systems," in Proceedings of 18th COnference of Applied Electronics, Pilsen, 2013.

[7] B. B. Brandenburg and J. H. Anderson, "A Comparison of the M-PCP, D-PCP, and FMLP on LITMUS RT," in Lecture Notes in Computer Science - Proceedings of 12th International Conference OPODIS, Luxor, Springer Berlin Heidelberg, 2008, pp. 105-124.

[8] T. Wagemann, T. Langer, J. Mottok, L. Osinski, F. Stappert and R. T. Kolagari, "Models for Dependable Heterogenous Multi- and Many-Core System Software Design Revisited," in Proceedings of ARCS 2016, 2016, 2016.

[9] M. Alfranseder, M. Deubzer, B. Justus, J. Mottok and C. Siemers, "An Efficient Spin-Lock Based Multi-Core Resource Sharing Protocol," in 33rd International Performance Computing and Communications Conference (IPCCC), Austin, 2014.