Cap. 10. Planificarea multiprocesor i de timp real. 1. Enumerai i descriei succint cinci categorii diferite de granulariti ale sincronizrii.a. Fine: paralelism intrinsec ntr-un singur ir de instruciuni. Medium: procesare paralel sau multitasking n cadrul unei singure aplicaii. Coarse: mutiprocesarea proceselor concurente ntr-un mediu cu multiprogramare. Very Coarse: procesarea distribuit ntre nodurile unei reele pentru a forma un singur mediu de calcul. Independent: procese multiple fr interdependene.b. Coarse: paralelism intrinsec ntr-un singur ir de instruciuni. Medium: procesare paralel sau multitasking n cadrul unei singure aplicaii. Fine: mutiprocesarea proceselor concurente ntr-un mediu cu multiprogramare. Very Coarse: procesarea distribuit ntre nodurile unei reele pentru a forma un singur mediu de calcul. Independent: procese multiple fr interdependene.c. Fine: paralelism intrinsec ntr-un singur ir de instruciuni. Independent: procesare paralel sau multitasking n cadrul unei singure aplicaii. Coarse: mutiprocesarea proceselor concurente ntr-un mediu cu multiprogramare. Very Coarse: procesarea distribuit ntr nodurile unei reele pentru a forma un singur mediu de calcul. Medium: procese multiple fr interdependene.d. Fine: paralelism intrinsec ntr-un singur ir de instruciuni. Medium: procesarea distribuit ntr nodurile unei reele pentru a forma un singur mediu de calcul. Coarse: mutiprocesarea proceselor concurente ntr-un mediu cu multiprogramare. Very Coarse: procesare paralel sau multitasking n cadrul unei singure aplicaii. Independent: procese multiple fr interdependene.

2. Enumerai i descriei succint patru tehnici pentru planificarea taskurilor.a. Load Sharing: Procesele nu sunt asignate unui anumit procesor. Este meninut o coad global cu firele gata de execuie, i fiecare procesor cnd ajunge n idle, delecteaz un fir din coad. Termenul load sharing este utiliza pentru a distinge aceast strategie de schemele de tip load-balancing unde sarcinile sunt alocate pe o baz mai permanent. Gand scheduling: un set de fire asociate este planificat pentru a rula pe un set de procesoare n acelai timp, utiliznd o relaie de tip unul-la-unul. Dedicated processor assignment: Fiecare program este alocat unui numr de procesoare egal cu numrul firelor sale de execuie. Cnd se termin programul, procesoarele revin la grupul general pentru o posibil alocare a altui program. Dynamic scheduling: Numrul de fire dintr-un program poate fi alterat pe durata execuiei.b. Load Sharing: Procesele nu sunt asignate unui anumit procesor. Este meninut o coad global cu firele gata de execuie, i fiecare procesor cnd ajunge n idle, delecteaz un fir din coad. Termenul load sharing este utiliza pentru a distinge aceast strategie de schemele de tip load-balancing unde sarcinile sunt alocate pe o baz mai permanent. Dedicated processor assignment: un set de fire asociate este planificat pentru a rula pe un set de procesoare n acelai timp, utiliznd o relaie de tip unul-la-unul. Gand scheduling: Fiecare program este alocat unui numr de procesoare egal cu numrul firelor sale de execuie. Cnd se termin programul, procesoarele revin la grupul general pentru o posibil alocare a altui program. Dynamic scheduling: Numrul de fire dintr-un program poate fi alterat pe durata execuiei.c. Load Sharing: Procesele nu sunt asignate unui anumit procesor. Este meninut o coad global cu firele gata de execuie, i fiecare procesor cnd ajunge n idle, delecteaz un fir din coad. Termenul load sharing este utiliza pentru a distinge aceast strategie de schemele de tip load-balancing unde sarcinile sunt alocate pe o baz mai permanent. Gand scheduling: un set de fire asociate este planificat pentru a rula pe un set de procesoare n acelai timp, utiliznd o relaie de tip unul-la-unul. Dynamic scheduling: Fiecare program este alocat unui numr de procesoare egal cu numrul firelor sale de execuie. Cnd se termin programul, procesoarele revin la grupul general pentru o posibil alocare a altui program. Dedicated processor assignment: Numrul de fire dintr-un program poate fi alterat pe durata execuiei.d. Load Sharing: Procesele nu sunt asignate unui anumit procesor. Este meninut o coad global cu firele gata de execuie, i fiecare procesor cnd ajunge n idle, delecteaz un fir din coad. Termenul load sharing este utiliza pentru a distinge aceast strategie de schemele de tip load-balancing unde sarcinile sunt alocate pe o baz mai permanent. Dynamic scheduling: un set de fire asociate este planificat pentru a rula pe un set de procesoare n acelai timp, utiliznd o relaie de tip unul-la-unul. Dedicated processor assignment: Fiecare program este alocat unui numr de procesoare egal cu numrul firelor sale de execuie. Cnd se termin programul, procesoarele revin la grupul general pentru o posibil alocare a altui program. Gand scheduling: Numrul de fire dintr-un program poate fi alterat pe durata execuiei.

3. Enumerai i descriei succint trei versiuni de partajare a ncrcrii.a. First Come First Serve (FCFS): Atunci cnd apare un job, acesta este plasat ntotdeauna la sfritul cozii. Cnd procesorul devine idle, acesta preia urmtorul fir gata de execuie din capul cozii, i-l execut pn se termin sau se blocheaz. Smallest Number of Threads First: Coada ready partajat este organizat ca o coad cu prioriti, cu prioritatea cea mai mare dat firelor din job-ul cu numrul cel mai mic de fire neplanificate. Job-urile cu prioritate egal sunt ordonate n funcie de care a sosit primul. Ca i la FCFS, un fir planificat se execut pn se termin sau se blocheaz. Preemtive Smallest Number of Threads First: Prioritatea cea mai mare este dat job-ului cu cel mai mic numr de fire neplanificate. Dac soste un job cu un numr de fire mai mic dect job-ul care se execut acesta va suspenda firele aparinnd job-ului curent n execuie.b. Load Sharing: Procesele nu sunt asignate unui anumit procesor. Este meninut o coad global cu firele gata de execuie, i fiecare procesor cnd ajunge n idle, delecteaz un fir din coad. Termenul load sharing este utiliza pentru a distinge aceast strategie de schemele de tip load-balancing unde sarcinile sunt alocate pe o baz mai permanent. Dynamic scheduling: un set de fire asociate este planificat pentru a rula pe un set de procesoare n acelai timp, utiliznd o relaie de tip unul-la-unul. Dedicated processor assignment: Fiecare program este alocat unui numr de procesoare egal cu numrul firelor sale de execuie. Cnd se termin programul, procesoarele revin la grupul general pentru o posibil alocare a altui program.c. Fine: paralelism intrinsec ntr-un singur ir de instruciuni. Medium: procesare paralel sau multitasking n cadrul unei singure aplicaii. Coarse: mutiprocesarea proceselor concurente ntr-un mediu cu multiprogramare.

4. Care este diferena ntre hard i soft real-time tasks?a. Un hard real time task (task cu constrngeri dure) trebuie s-i respecte deadline-ul (timpul maxim de execuie); altfel va cauza stricciuni nedorite sau erori fatale n sistem. Un soft real time task (task cu constrngeri uoare) are un deadline asociat care este de dorit a fi ndeplinit dar nu este indezirabil; are nc sens de a planifica i a completa execuia taskului chiar dac s-a depit deadline-ul su.b. Un hard real time task (task cu constrngeri dure) este aperiodic, iar un soft real time task (task cu constrngeri uoare) este periodic.c. Nu exist diferene majore.d. Un hard real time task (task cu constrngeri dure) este utilizat pentru aplicaii, iar un soft real time task (task cu constrngeri uoare) este utilizat pentru kernel.e. Un hard real time task (task cu constrngeri dure) este utilizat pentru kernel, iar un soft real time task (task cu constrngeri uoare) este utilizat pentru aplicaii.

5. Care este diferena ntre taskurile de timp real periodice i cele aperiodice?a. Un task aperiodic are un deadline pentru care trebuie s porneasc sau s se termine, sau poate avea o constrngere att pentru timpul de start ct i pentru timpul de stop. n cazul unui task periodic, cerina poate fi definit ca unul pe period sau exact la T uniti.b. Un task periodic are un deadline pentru care trebuie s porneasc sau s se termine, sau poate avea o constrngere att pentru timpul de start ct i pentru timpul de stop. n cazul unui task aperiodic, cerina poate fi definit ca unul pe period sau exact la T uniti.c. Un task periodic este utilizat pentru aplicaii, iar un task aperiodic este utilizat pentru kernel.d. Un task aperiodic este utilizat pentru aplicaii, iar un task periodic este utilizat pentru kernel.

6. Enumerai i descriei succint cinci arii generale de cerine pentru sistemele de operare de timp real.a. Determinism: un sistem de operare este determinism dac poate realiza operaii la momente fixe i determinate de timp, sau ntr-un interval de timp predeterminat. Responsiveness: se refer la ct de mult, dup recunoatere, i va lua sistemului de operare s serveasc o ntrerupere. User control: utilizatorul trebuie s fie capabil s disting ntre taskurile hard i soft i s specifice prioriti relative pentru fiecare clas. Un RTS poate de asemenea s permit utilizatorului s specifice unele caracteristici cum ar fi ce pagini sau procese pot fi comutate, ce procese trebuie s fie ntotdeauna rezidente n memoria principal, ce algoritm s fie utilizat pentru transferul cu discul, ce drepturi are un proces n diferite zone de prioriti, i altee. Reliability: fiabilitatea trebuie oferit ntr-un mod pentru a oferii continuu ndeplinirea deadline-ului. Fail-soft operation: este o caracteristic care se refer la abilitatea unui sistem de a-i ntrerupe execuia (fail) ntr-un astfel de mod nct s prezerve ct mai multe date i capabiliti posibile.b. User control: un sistem de operare este determinism dac poate realiza operaii la momente fixe i determinate de timp, sau ntr-un interval de timp predeterminat. Responsiveness: se refer la ct de mult, dup recunoatere, i va lua sistemului de operare s serveasc o ntrerupere. Determinism: utilizatorul trebuie s fie capabil s disting ntre taskurile hard i soft i s specifice prioriti relative pentru fiecare clas. Un RTS poate de asemenea s permit utilizatorului s specifice unele caracteristici cum ar fi ce pagini sau procese pot fi comutate, ce procese trebuie s fie ntotdeauna rezidente n memoria principal, ce algoritm s fie utilizat pentru transferul cu discul, ce drepturi are un proces n diferite zone de prioriti, i altele. Reliability: fiabilitatea trebuie oferit ntr-un mod pentru a oferii continuu ndeplinirea deadline-ului. Fail-soft operation: este o caracteristic care se refer la abilitatea unui sistem de a-i ntrerupe execuia (fail) ntr-un astfel de mod nct s prezerve ct mai multe date i capabiliti posibile.c. Determinism: un sistem de operare este determinism dac poate realiza operaii la momente fixe i determinate de timp, sau ntr-un interval de timp predeterminat. Responsiveness: se refer la ct de mult, dup recunoatere, i va lua sistemului de operare s serveasc o ntrerupere. User control: utilizatorul trebuie s fie capabil s disting ntre taskurile hard i soft i s specifice prioriti relative pentru fiecare clas. Un RTS poate de asemenea s permit utilizatorului s specifice unele caracteristici cum ar fi ce pagini sau procese pot fi comutate, ce procese trebuie s fie ntotdeauna rezidente n memoria principal, ce algoritm s fie utilizat pentru transferul cu discul, ce drepturi are un proces n diferite zone de prioriti, i altele. Fail-soft operation: fiabilitatea trebuie oferit ntr-un mod pentru a oferii continuu ndeplinirea deadline-ului. Reliability: este o caracteristic care se refer la abilitatea unui sistem de a-i ntrerupe execuia (fail) ntr-un astfel de mod nct s prezerve ct mai multe date i capabiliti posibile.d. Determinism: un sistem de operare este determinism dac poate realiza operaii la momente fixe i determinate de timp, sau ntr-un interval de timp predeterminat. Fail-soft operation: se refer la ct de mult, dup recunoatere, i va lua sistemului de operare s serveasc o ntrerupere. User control: utilizatorul trebuie s fie capabil s disting ntre taskurile hard i soft i s specifice prioriti relative pentru fiecare clas. Un RTS poate de asemenea s permit utilizatorului s specifice unele caracteristici cum ar fi ce pagini sau procese pot fi comutate, ce procese trebuie s fie ntotdeauna rezidente n memoria principal, ce algoritm s fie utilizat pentru transferul cu discul, ce drepturi are un proces n diferite zone de prioriti, i altele. Reliability: fiabilitatea trebuie oferit ntr-un mod pentru a oferii continuu ndeplinirea deadline-ului. Responsiveness: este o caracteristic care se refer la abilitatea unui sistem de a-i ntrerupe execuia (fail) ntr-un astfel de mod nct s prezerve ct mai multe date i capabiliti posibile. 7. Enumerai i descriei succint patru clase de algoritmi de planificare pentru timpul real.a. Static table-driven approaches: aceasta realizeaz o analiz static a fiabilitii a planificrii pentru dispecerizare. Rezultatul analizei este o planificare care determin, n timpul execuiei, cnd trebuie un task s-i nceap execuia. Static priority-driven preemptive approaches: din nou, are loc o analiz static, dar planificarea nu este decis. Mai degrab, analiza este utilizat pentru a asigna prioriti taskurilor, astfel nct se poate utiliza un planificator cu suspendare tradiional bazat prioriti. Dymanic planning-based approaches: fezabilitatea este determinat n execuie (dinamic) i nu offline nainte de nceperea execuiei (static). Un task care sosete este acceptat pentru execuie numai dac este fezabil ndeplinirea constrngerilor sale de timp. Ca rezultat al analizei fezabilitii este o planificare sau un plan care se utilizeaz pentru a decide cnd s se dispecerizeze acest task. Dynamic best efforts approaches: nu se realizeaz nici o analiz de fezabilitate. Sistemul ncearc s ndeplineasc toate deadline-uril i abandoneaz orice proces lansat n execuie pentru care s-a pierdut deadline-ul.b. Static priority-driven preemptive approaches: aceasta realizeaz o analiz static a fiabilitii a planificrii pentru dispecerizare. Rezultatul analizei este o planificare care determin, n timpul execuiei, cnd trebuie un task s-i nceap execuia. Static table-driven approaches: din nou, are loc o analiz static, dar planificarea nu este decis. Mai degrab, analiza este utilizat pentru a asigna prioriti taskurilor, astfel nct se poate utiliza un planificator cu suspendare tradiional bazat prioriti. Dymanic planning-based approaches: fezabilitatea este determinat n execuie (dinamic) i nu offline nainte de nceperea execuiei (static). Un task care sosete este acceptat pentru execuie numai dac este fezabil ndeplinirea constrngerilor sale de timp. Ca rezultat al analizei fezabilitii este o planificare sau un plan care se utilizeaz pentru a decide cnd s se dispecerizeze acest task. Dynamic best efforts approaches: nu se realizeaz nici o analiz de fezabilitate. Sistemul ncearc s ndeplineasc toate deadline-uril i abandoneaz orice proces lansat n execuie pentru care s-a pierdut deadline-ul.c. Static table-driven approaches: aceasta realizeaz o analiz static a fiabilitii a planificrii pentru dispecerizare. Rezultatul analizei este o planificare care determin, n timpul execuiei, cnd trebuie un task s-i nceap execuia. Dymanic planning-based approaches: din nou, are loc o analiz static, dar planificarea nu este decis. Mai degrab, analiza este utilizat pentru a asigna prioriti taskurilor, astfel nct se poate utiliza un planificator cu suspendare tradiional bazat prioriti. Static priority-driven preemptive approaches: fezabilitatea este determinat n execuie (dinamic) i nu offline nainte de nceperea execuiei (static). Un task care sosete este acceptat pentru execuie numai dac este fezabil ndeplinirea constrngerilor sale de timp. Ca rezultat al analizei fezabilitii este o planificare sau un plan care se utilizeaz pentru a decide cnd s se dispecerizeze acest task. Dynamic best efforts approaches: nu se realizeaz nici o analiz de fezabilitate. Sistemul ncearc s ndeplineasc toate deadline-uril i abandoneaz orice proces lansat n execuie pentru care s-a pierdut deadline-ul.d. Static table-driven approaches: aceasta realizeaz o analiz static a fiabilitii a planificrii pentru dispecerizare. Rezultatul analizei este o planificare care determin, n timpul execuiei, cnd trebuie un task s-i nceap execuia. Static priority-driven preemptive approaches: din nou, are loc o analiz static, dar planificarea nu este decis. Mai degrab, analiza este utilizat pentru a asigna prioriti taskurilor, astfel nct se poate utiliza un planificator cu suspendare tradiional bazat prioriti. Dynamic best efforts approaches: fezabilitatea este determinat n execuie (dinamic) i nu offline nainte de nceperea execuiei (static). Un task care sosete este acceptat pentru execuie numai dac este fezabil ndeplinirea constrngerilor sale de timp. Ca rezultat al analizei fezabilitii este o planificare sau un plan care se utilizeaz pentru a decide cnd s se dispecerizeze acest task. Dymanic planning-based approaches: nu se realizeaz nici o analiz de fezabilitate. Sistemul ncearc s ndeplineasc toate deadline-uril i abandoneaz orice proces lansat n execuie pentru care s-a pierdut deadline-ul.

8. Care informaie referitoare la task poate fi util n planificarea de timp real? a. Ready time, Starting deadline, Completion deadline, Processing time, Resource requirements, Prority, Subtask structure.b. Program Counter, Timer register, Stack pointer, General registers.c. Static table-driven, Static priority-driven preemptive, Dynamic best efforts approaches, Dymanic planning-based.

Problems9. Considerai un set de trei taskuri periodice cu profilul de execuie dat n tabelul 10.6 . Dezvoltai pentru aceste taskuri o diagram de execuie similar aceleia din figura 10.5.

a.AABBAACCAABBAACCAA

AABBACCACAABBAACCCAA

Pentru planificarea cu prioriti fixe, procesul C ntotdeauna i pierde deadline-ul.b.AABBAACCCABBAACCAA

AABBACCACAABBAACCCAA

Pentru planificarea cu prioriti fixe, procesul C ntotdeauna i pierde deadline-ul.c.AABBAACCAABBAACCAA

AABBACCACBABBAACCCAA

Pentru planificarea cu prioriti fixe, procesul C ntotdeauna i pierde deadline-ul.d.AABBAACCAABBAACCAA

AABBACCACAABBAACCAAA

Pentru planificarea cu prioriti fixe, procesul C ntotdeauna i pierde deadline-ul.e.AABBAACCAABBAACCAA

AAABACCACAABBAACCCAA

Pentru planificarea cu prioriti fixe, procesul C ntotdeauna i pierde deadline-ul.10. Considerai un set de cinci taskuri aperiodice cu profilul de execuie dat n tabelul 10.7. Dezvoltai pentru aceste taskuri o diagram de execuie similar aceleia din figura 10.6.

a.Fiecare dreptunghi reprezint 10 uniti.

Earliest deadlineAACCEEDD

Earliest deadline with unforced idle timesBBCCEEDDAA

FCFSAACCDD

b.Fiecare dreptunghi reprezint 10 uniti.

Earliest deadlineAACCEEDD

Earliest deadline with unforced idle timesBBCCEDDDAA

FCFSAACCDD

c.Fiecare dreptunghi reprezint 10 uniti.

Earliest deadlineAACCCEDD

Earliest deadline with unforced idle timesBBCCEEDDAA

FCFSAACCDD

d.Fiecare dreptunghi reprezint 10 uniti.

Earliest deadlineAACCEEDD

Earliest deadline with unforced idle timesBBCCEEDDAA

FCFSAACCDE

e.Fiecare dreptunghi reprezint 10 uniti.

Earliest deadlineAACCCEEDD

Earliest deadline with unforced idle timesBBCCEEDDAA

FCFSAACCDD

11. Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed)LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Presupunei c un task are timpul de relaxare curent t. Pentru ct timp poate planificatorul ntrzia pornirea acestui task astfel nct s respecte nc deadline-ul su?a. Taskul poate fi ntrziat pn la un interval t i totui i va menine deadline-ul.b. Taskul poate fi ntrziat pn la un interval t i nu i va menine deadline-ul.c. Taskul poate fi ntrziat pn la un interval 2t i totui i va menine deadline-ul.d. Taskul poate fi ntrziat pn la un interval 3t i totui i va menine deadline-ul.

12. Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed)LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Presupunei c un task are timpul de relaxare curent t. Presupunei c taskul curent are timpul de relaxare 0. Ce nseamn aceasta?a. laxitate 0 nsemn c taskul trebuie executat acum or va eua n a-i ndeplini deadline-ul.b. laxitate 0 nsemn c taskul a euat n a-i ndeplini deadline-ul.c. laxitate 0 nsemn c taskul trebuie executat imediat dup t or va eua n a-i ndeplini deadline-ul.

13. Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed)LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Ce nsemn un timp de relaxare negativ?a. Un task cu laxitate negativ nu i poate ndeplini deadline-ul.b. Un task cu laxitate negativ i poate ndeplini deadline-ul.c. Un task cu laxitate negativ este fr semnificaie.

14. Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed) LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Considerai un set de trei taskuri periodice cu profilul de execuie dat n tabelul 10.8a. Dezvoltai o diagram de planificare similar cu aceea din figura 10.4 pentru acest set de taskuri care s compare rate monotonic, earliest deadline first, i LLF. Presupunei c suspendarea poate s apar la intervale de 5 ms. Comentai rezultatul.

a.

b.

c.

d.

15. Repetai problema 10.3d (Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed)LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Considerai un set de trei taskuri periodice cu profilul de execuie dat n tabelul 10.8a. Dezvoltai o diagram de planificare similar cu aceea din figura 10.4 pentru acest set de taskuri care s compare rate monotonic, earliest deadline first, i LLF. Presupunei c suspendarea poate s apar la intervale de 5 ms. Comentai rezultatul.) pentru profilul de execuie din tabelul 10.8b . Comentai rezultatul.

a.ncrcarea total depete acum 100 %. Niciuna dintre metode nu poate gestiona ncrcarea. Taskul care va eua n ndeplinirea deadline-ului variaz n funcie de metod.

b.ncrcarea total depete acum 100 %. Niciuna dintre metode nu poate gestiona ncrcarea. Taskul care va eua n ndeplinirea deadline-ului variaz n funcie de metod.

c.ncrcarea total depete acum 100 %. Niciuna dintre metode nu poate gestiona ncrcarea. Taskul care va eua n ndeplinirea deadline-ului variaz n funcie de metod.

d.ncrcarea total depete acum 100 %. Niciuna dintre metode nu poate gestiona ncrcarea. Taskul care va eua n ndeplinirea deadline-ului variaz n funcie de metod.

16. Maximum urgency first (MUF) este un algoritm de planificare de timp real pentru taskurile periodice. Fiecare task are asignat o urgen care se definete ca o combinaie a dou prioriti fixe i a uneia dinamice. Una din prioritile fixe, starea critic (the criticality), are preceden peste prioritatea dinamic. n acelai timp, prioritatea dinamic are preceden peste cealalt prioritate fix. Prioritatea dinamic este invers proporional cu relaxarea unui task. MUF poate fi explicat dup cum urmeaz: Prima dat, taskurile sunt ordonate de la perioada cea mai scurt la perioada cea mai lung. Se definete setul critic de taskuri ca fiind primele N taskuri, astfel nct utilizarea pentru cazul cel mai defavorabil a procesorului s nu depeasc 100 %. Dintre setul de takuri critice care sunt gata de execuie planificatorul selecteaz taskul cu relaxarea cea mai mic. Dac nici un set de taskuri critice nu este gata de execuie, planificatorul alege dintre taskurile non-critice pe acela cu relaxarea cea mai mic. Mai departe taskurile sunt aranjate pentru execuie pe baza unei prioriti opionale date de utilizator i mai apoi pe baza algoritmului FCFS. Repetai problema 10.3d, adugnd MUF la diagram. Presupunei c prioritile definite de utilizator sunt A cea mai mare, B urmtoare i C cea mai mic. Comentai rezultatul.

a. Pe acest profil de taskuri, comportarea MUF este identic cu RM. De notat c EDF are mai puine comutri de context (11) fa de celelalte care au 13.

b.Pe acest profil de taskuri, comportarea MUF este identic cu RM. De notat c EDF are mai puine comutri de context (11) fa de celelalte care au 13.

c.Pe acest profil de taskuri, comportarea MUF este identic cu RM. De notat c EDF are mai puine comutri de context (11) fa de celelalte care au 13.

d.Pe acest profil de taskuri, comportarea MUF este identic cu RM. De notat c EDF are mai puine comutri de context (11) fa de celelalte care au 13.

17. Repetai problema 10.4 (Repetai problema 10.3d (Least laxity first (LLF) este un algoritm de planificare n timp real pentru taskurile periodice. Timpul de inactivitate (Slack time) sau relaxare (laxity), este cantitatea de timp dintre momentul cnd un task se termin dac ar fi pornit acum i urmtorul deadline. Aceasta este mrimea ferestrei disponibile pentru planificare. Relaxarea (Laxity) poate fi exprimat ca:Laxity = (deadline time) - (current time) - (processor time needed)LLF selecteaz pentru execuia viitoare taskul cu timpul minim de relaxare. Dac dou sau mai multe taskuri au acelai timp de relaxare, atunci acestea sunt servite pe baza unui algoritm FCFS. Considerai un set de trei taskuri periodice cu profilul de execuie dat n tabelul 10.8a. Dezvoltai o diagram de planificare similar cu aceea din figura 10.4 pentru acest set de taskuri care s compare rate monotonic, earliest deadline first, i LLF. Presupunei c suspendarea poate s apar la intervale de 5 ms. Comentai rezultatul.) pentru profilul de execuie din tabelul 10.8b . Comentai rezultatul.), adugnd MUF la diagram. Comentai rezultatul.

a. Setul critic de taskuri conine A i B. De observat c MUF este singurul algoritm care execut setul critic la timp.

b.Setul critic de taskuri conine A i B. De observat c MUF este singurul algoritm care execut setul critic la timp.

c.Setul critic de taskuri conine A i B. De observat c MUF este singurul algoritm care execut setul critic la timp.

d.Setul critic de taskuri conine A i B. De observat c MUF este singurul algoritm care execut setul critic la timp.

18. Aceast problem demonstreaz c dei ecuaia ( 10.2 ) pentru planificarea rate monotonic este o condiie suficient, nu este i o condiie necesar (se poate realiza o planificare cu succes chiar dac nu este satisfcut ecuaia ( 10.2 ) ). Considerai un set de taskuri cu urmtoarele taskuri periodice independente : Task P 1 : C1 = 20 ; T1 = 100 Task P 2 : C2 = 30 ; T2 = 145Pot fi planificate cu succes aceste taskuri utiliznd planificarea rate monotonic?a. Utilizarea total este de 0, 41 mai mic dect marginea de planificabilitate de 0,828, deci taskurile sunt planificabile.b. Utilizarea total este de 0, 41 mai mic dect marginea de planificabilitate de 0,828, deci taskurile nu sunt planificabile.c. Utilizarea total este de 0, 91 mai mare dect marginea de planificabilitate de 0,828, deci taskurile nu sunt planificabile.d. Utilizarea total este de 0, 43 mai mic dect marginea de planificabilitate de 0,428, deci taskurile nu sunt planificabile.19. Aceast problem demonstreaz c dei ecuaia ( 10.2 ) pentru planificarea rate monotonic este o condiie suficient, nu este i o condiie necesar (se poate realiza o planificare cu succes chiar dac nu este satisfcut ecuaia ( 10.2 ) ). Considerai un set de taskuri cu urmtoarele taskuri periodice independente : Task P 1 : C1 = 20 ; T1 = 100 Task P 2 : C2 = 30 ; T2 = 145Adugai acum urmtoarele taskuri la set : Task P 3 : C3 = 68 ; T3 = 150Este satisfcut ecuaia ( 10.2 )?a. Utilizarea total este de 0,86 care excede marginea de planificabilitate de 0,779, deci nu este satisfcut.b. Utilizarea total este de 0,812 care excede marginea de planificabilitate de 0,679, deci nu este satisfcut.c. Utilizarea total este de 0,26 care excede marginea de planificabilitate de 0,579, deci nu este satisfcut.d. Utilizarea total este de 0,883 care excede marginea de planificabilitate de 0,579, deci nu este satisfcut.e. Utilizarea total este de 0,86 care excede marginea de planificabilitate de 0,679, deci nu este satisfcut.

20. Aceast problem demonstreaz c dei ecuaia ( 10.2 ) pentru planificarea rate monotonic este o condiie suficient, nu este i o condiie necesar (se poate realiza o planificare cu succes chiar dac nu este satisfcut ecuaia ( 10.2 ) ). Considerai un set de taskuri cu urmtoarele taskuri periodice independente : Task P 1 : C1 = 20 ; T1 = 100 Task P 2 : C2 = 30 ; T2 = 145Adugai acum urmtoarele taskuri la set : Task P 3 : C3 = 68 ; T3 = 150Presupunei c prima instan a celor trei taskuri sosete la momentul t = 0. Presupunei c deadline-urile pentru fiecare task sunt: D1 = 100; D2 = 145; D3 = 150Utiliznd planificarea rate monotonic, i vor respecta cele trei taskuri deadline-ul lor? Ce putei spune despre deadline n cazul unor repetri ulterioare ale fiecrui task? a. DA,b. NU,c. Doar P1 i P2d. Doar P1 i P3e. Doar P2 i P3f. Doar P3.

21. Trasai o diagram similar cu aceea din figura 10.9b care prezint secvena de evenimente care pentru acelai exemplu dar utiliznd plafonul maxim (priority ceiling).

a.Odat ce T3 intr n seciunea critic, i este asignat o prioritate mai mare ca T1. Cnd T3 prsete seciunea sa critic, acest este suspendat de T1.

b.Odat ce T1 intr n seciunea critic, i este asignat o prioritate mai mare ca T3. Cnd T1 prsete seciunea sa critic, acest este suspendat de T3.

c.Odat ce T2 intr n seciunea critic, i este asignat o prioritate mai mare ca T1. Cnd T3 prsete seciunea sa critic, acest este suspendat de T1.