multi threading
TRANSCRIPT
1 Conceptul de thread
11
1 Proiectarea programelor multithreading
1.1 Taskuri candidate pentru threading
Pentru a gsi n program locurile unde se pot folosi threaduri trebuie depistate proprietile:
Paralelism
Operaii I/O suprapuse
Evenimente asincrone
Planificare real-time
Oricnd un task are una dintre aceste proprieti, el este un candidat pentru a rula ntr-un thread. Un astfel de task se poate identifica folosind urmtorele criterii:
Este independent de alte taskuri. Folosete resurse diferite de cele folosite de alte taskuri? Execuia sa depinde de rezultatele altor taskuri? Cu ct taskurile sunt mai strnse n interdependen, cu att crete ansa ca ele s sfreasc prin a se bloca n ateptare reciproc.
Poate fi blocat n ateptri lungi. Poate taskul s rmn suspendat un timp ndelungat? Un program poate efectua milioane de operaii cu ntregi n timpul n care face o singur operaie de I/O. Dedicarea unui thread pentru I/O poate spori considerabil performanele unui program.
Poate folosi multe cicluri CPU. Execut taskul calcule complexe (asupra matricelor, dispersie, criptare)? Calculele consumatoare de timp i indepenente de alte activiti sunt buni candidai pentru threading.
Trebuie s rspund la evenimente asincrone. Trebuie taskul s trateze evenimente asincrone ce apar la intervale de timp aleatorii ,ca, de exemplu, comunicarea n reea? threadurile sunt soluia pentru a ncapsula i sincroniza serviciile acestor evenimente.
Operaille executate n thread au mai mic sau mai mare importan dect operaiile efectuate n alte threaduri. Sarcina trebuie executat ntr-un timp specificat? Trebuie s se execute la intervale precizate? Consideraiile legate de planificare sunt adesea motive bune pentru mulithreading. De exemplu, o aplicaie window manager va asigna o prioritate mai mare operaiilor de input de la utilizator dact threadului garbage collection.
Programele server care rspund continuu la evenimente asincrone sunt aplicaii ideale pentru threading. Aplicaiile de calcul i semnalizare (signal-processing) sunt alte candidate pentru multithreading. Ele conin taskuri care pot fi executate pe mai multe procesoare. n sfrit, aplicaiile n timp real sunt i ele ideale pentru multithreading. Ele sunt mult mai eficiente dect soluiile oferite de multi-proces. Modelul cu threaduri permite stabilirea de prioriti i elimin din complexitatea ce apare la programerea asincron.
1.2 Modele de programare multithreading
Nu exist reguli fixe pentru programarea multithreading. Fiecare program are propriul lui specific. Totui, de-a lungul timpului, au aprut cteva modele care specific n ce fel o aplicaie multithreading mparte sarcinile threadurilor i cum comunic acestea. In cele ce urmeaz se vor discuta:
modelul boss / worker
modelul de la egal la egal (peer)
modelul pipeline
1.3 Modelul Boss/Worker
Fig. ? Modelul boss-worker
Boss-ul creeaz pe fiecare din threadurile worker, le asigneaz taskuri, i eventual ateapt s se termine execuia lor. n pseudocodul din Exemplul ? boss-ul creeaz n mod dinamic cte un worker atunci cnd primete o nou cerere. n procedura pthread_create boss-ul specific rutina legat de taskul ce l va executa threadul. Dup creare boss-ul ateapt o nou cerere.
Exemplul ? Modelul boss/worker
main() {
forever {
primeste o cerere
switch cerere
case cerereX: thread_create(..taskX);
case cerereY: thread_create(..taskY);
- - -
}
}
taskX() {
execut taskul, iar n caz de acces la resurse partajate
f sincronizare
}
- - - Dac boss-ul creeaz threadurile n mod dinamic, atunci vor exista attea threaduri concurente cte cereri concurente au sosit. Ca o alternativ, boss-ul poate economisi suprancrcarea (overhead) ce apre la execuie,dac creeaz n prealabil taskurile. Soluia poart denumirea de thread pool (Exemplul ?) Boss-ul creeaz threadurile la iniializare. Aceste se suspend imediat i vor fi repornite de apeluri de la boss. Boss-ul folosete o coad unde pune cererile primite. Ele vor fi tratate de ctre threaduri.
Exemplul ? Modelul boss/worker cu pool
main() {
for numrul de workers
thread_create(. . .pool_base . . .)
forever {
primete o cerere
plaseaz cererea n coad
semnaleaz threadurile n ateptare c este de lucru
}
}
pool_base() {
sleep until boss semnaleaz c este de lucru
scoate o cerere din coad
switch cerere {
case cerereX: taskX();
case cerereY: taskY();
- - -
}
}
Modelul boss/worker funcioneaz foarte bine pentru servere. Complexitatea tratrii cererilor asincrone este ncapsulat n boss. Este important s se minimizeze frecvena cu care boss-ul i worker-ii comunic. Boss-ul nu poate pierde timp n sincronizri cu subalternii (s-ar acumula cereri) De asemenea se dorete reducerea comunicrii ntre subalterni.
1.4 Modelul de egalitate (peer)
Spre deosebire de primul model prezentat, aici threadurile lucreaz concurent asupra taskurilor fr s existe un leader. Un thread este rspunztor cu crearea celorlalte threaduri (egale) la pornirea programului, apoi acest thread se va comporta ca un thread obinuit devenind egal cu celelalte. El va trata cereri sau va atepta terminarea celorlalte threaduri.
Fig. ? Modelul peer to peer
Fiecare thread este rspunztor pentru datele de intrare proprii. Un peer tie de la nceput ce fel de input va avea i are mijloace proprii de a i-l obine. (eventual partajeaz cu celelalte threduri un punct de intrare)
Exemplul ? Modelul peer
main() {
thread_create(thread1task1)
thread_create(thread2task2)
- - -
Anun toi workers s execute start
Ateapt s se termine toi workers
F eventuale aciuni de terminare
}
task1() {
Ateapt semnal de start
execut taskul, iar n caz de acces la resurse partajate
f sincronizare
}
- - -
Modelul peer este adecvat pentru aplicaii care au o mulime fix sau bine definit de date de intrare, cum ar fi nmulirea de matrice, generatoare de numere prime, maini de cutare paralel. Pentru c nu exist un bos, threadurile peer threbuie s i sincronizeze accesul la sursele de input comune. Ca i n cazul precedent, poate aprea ncetinire (slowdown) dac sincronizarea se face prea de des.
Fie o aplicaie n care un plan sau un spaiu este divizat pe mai multe threaduri astfel nct s poate calcula schimbrile de temperatur n timp ce este radiat cldur pe suprafa. Fiecare thread poate calcula un delta de schimbare. Pentru c rezultatele calculelor fiecrui thread necesit o ajustare a limitelor pentru threadul urmtor, toate threadurile threbuie s se sincronizeze i s compare rezultatele. Acesta este un exemplu clasic pentru o aplicaie peer.
1.5 Modelul pipeline
Acest model presupune:
un stream de input lung
serie de operaii (filtre) prin care trebuie s treac fiecare unitate de input
fiecare filtru poate trata o unitate diferit la un moment dat
Un exemplu clasic l constituie asamblarea unei maini. La fiecare moment o main se afl ntr-un anumit stadiu. Un procesor RISC se potrivete, de asemenea, acestei desrieri. Inputul este un stream de instruciuni. Fiecare trece prin stadiul de decodificare, aducere operanzi, calcul, stocare rezultate. Dei timpul pentru asamblarea unei maini, respectiv pentru executarea unei instruciuni ia acelai timp, timpul global pentru un set de maini (instruciuni) este mbuntit considerabil.
Dup cum ilustreaz pseudocodul din Exemplul ?, un thread primete inputul pentru ntregul program i l trimite primului filtru. De asemenea un singur thread colecteaz rezultatul i produce outputul programului. Fiecare thread proceseaz inputul primit de la threadul anterior lui (ca ordine). Modelul este util n prelucrearea de imagini i de texte.
Fig. ? Modelul pipeline
Exemplul ? Modelul pipeline
main() {
thread_create(stage1)
thread_create(stage2)
- - -
wait s se termine toate threads
}
stage1() {
forever {
citete intrarea pentru program
execut stadiul 1 al prelucrrii intrrii
trece rezultatele ieirii lui spre stadiul 2
}
}
stage2() {
forever {
citete intrarea primit de la stagiul 1
execut stagiul2 al prelucrrii
trece rezultatele ieirii lui spre stagiul 3
}
}
- - -
Se poate multiplexa sau demultiplexa pipeline-ul, permind ca mai multe threaduri s lucreze n paralel ca un singur filtru. Performanele unui pipeline sunt date de threadul care ruleaz (execut) cel mai ncet. Celelalte threaduri sunt condiionate de lucrul acestuia. n proiectarea unui program pipeline este de dorit o balansare a lucrului ce trebuie executat la fiecare pas.
1.6 Exemplu: nmulire de matrice
Programul exemplific folosirea modelului peer.
Se vor nmuli dou tablori bidimensionale de n*n: ci,j = ai,1 * b1,j + + ai,n * bn,j
Un program care nmulete matrici trebuie s calculeze valoarea fiecrui element din matricea rezultat. Dac programul nu conine threaduri, timpul necesar va fi timpul n care se calculeaz un element nmulit cu numrul de elemente. Programele din aceast categorie au caracteristic faptul c repet o operaie de baz pe subseturi diferite de date. Performanele acestor programe pot fi nbuntite cu threaduri n dou feluri: prin I/O suprapus i prin procesare paralel.
Programul nu va demonstra tehnica I/O suprapus, ci doar procesarea paralel. Se vor folosi dou tablouri de dimensiuni mici, stocate n memorie.
Pentru fiecare element rezultat se va crea cte un thread (peer). Va exista i un thread principal (main) pentru setup i cleanup: face iniializri, creeaz threaduri, ateapt s se termine i apoi afieaz rezultatele.
Observaie: Pentru matrice foarte mari, numrul de threaduri va fi egal cu numrul de procesoare disponibile.
Exemplul 2-10 Rutina main a programului
typedef struct {
int id;
int n;
int Ai;
int Bj;
matrix_t *MA, *MB, *MC;
} matrix_work_order_t;
int main(int argc, char **argv)
{
int i, j, n = ARRAY_SIZE;
matrix_t MA, MB, MC;
matrix_work_order_t *work_orderp;
pthread_t peer[size*size];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
id = j * i *10;
work_order_p = (work_order_t *)malloc(sizeof(work_order_t));
work_order_p->id = id;
work_order_p->size = n;
work_order_p->i = i;
work_order_p->j = j;
work_order_p->MA = &MA;
work_order_p->MB = &MB;
work_order_p->MC = &MC;
pthread_create(&(peer[id]), NULL, (void *)peer_mult, (void *)work_orderp);
}
}
/* Asteapta dupa peers sa se termine */
for(i=0; i < (n * n); i++) {
pthread_join(peer[i], NULL);
}
- - -
In exemplul serial programul principal apela o rutin mult care facea nmulirea. Ea avea mai multe argumente, iar pthread_create poate fi aplelat doar asupra unei rutine cu un singur argument. Soluia const n folosirea unei structuri pentru transmitera de paramentrii i a unei rutine auxiliare. Toate datele ce trebuie transmise threadurilor sunt mpachetate ntr-o structur , matrix_work_order_t. Fiecrui thread trebuie s i se transmit o structur unic! Exist pericolul a dou abordri greite: folosirea unei structuri statice i plasarea lui malloc n afara ciclului. Aceasta ar cauza suprascrierea structurii. Rutina auxiliar are ca parametru structura menionat i apeleaz rutina mult care are mai muli parametrii (i deci nu poate fi folosit n pthread_create).
Exemplul ? rutina peer_multvoid peer_mult( matri_work_order_t *word_orderp)
{
mult(work_orderp->i,
work_orderp->j,
*(work_orderp->MA),
*(work_orderp->MB),
*(work_orderp->MC);
}
Sincronizare n programul de nmulire:
Threadul main trebuie s atepte terminarea threadurilor peer Nu este necesar sincronizare de date, pentru c threadurile nu scriu n locaii partajate
Threadurile citesc valori din tablourile din input, deci nu trebuie cercetat cazul n care se fac pe parcurs modificri asupra datelor
Calculul unui element din tabloul rezultat este complet independent de celelalte calcule, deci nu este necesar nici o ordonare a threadurilor.
2 Sincronizarea firelor de execuie
2.1 Instrumente de sincronizare
In vederea sincronizrilor se pot alege mai multe soluii din numeroase funcii Pthread disponibile.
Pthread_join. Aceast funcie suspendeaz execuia unui thread pn la terminarea unui alt thread.
Variabile Mutex. O variabil mutex acioneaz ca o blocare exclusiv, mutual, permitnd threadului s controleze accesul la date. La un moment dat numai un singur thread poate s blocheze i s aib acces la data protejat.
Variabile condiionale. O variabil condiional ne d o posibilitate de denumire a evenimentelor n care thread-urile sunt interesate. Un eveniment poate fi chiar i faptul c un contor ajunge la o valoare prestabilit, sau un flag este setat sau anulat; dar poate fi i mai complex implicnd o coinciden specific a mai multor evenimente. Thread-urile sunt interesate n aceste evenimente, deoarece asemenea evenimente nseam c s-a mplinit o condiie, care le permite s continue cu o anumit faz a execuiei lor. Biblioteca de funcii Pthreads asigur ci pentru thread-uri att penru a exprima interesul lor n mplinirea unei condiii, ct i pentru a semnaliza mplinirea condiiei ateptat.
Pthread_once. Funcia este o unealt specializat de sincronizare care garanteaz c rutinele de iniializare se execut o dat i numai o dat, cnd sunt apelate de thread-uri multiple.
Aceste unelte de sincronizare ne asigur tot ce este necesar pentu a scrie aproape orice program care se poate imagina. Mai mult, se pot creea instrumente de sincronizare orict de complexe folosind numai aceste elemente de construcii. Cteva dintre aceste mecanizme de sincronizare sunt:
Excludere Reader/Writer. Blocrile Reader/Writer permit mai multor thread-uri s citeasc date n mod concurent, dar asigur c thread-ul care scrie are acces exclusiv la date.
Structuri de date independente de threaduri Ar fi folositor s putem stoca primitive de sincronizare n structuri complexe de date, astfel nct ori de cte ori accesm datele nu trebuie s avem grij de sincronizarea accesrilor concurente. De exemplu ntr-o bibliotec de fuincii care implementeaz o structur tip coad, putem include funcii tip push-pop care includ apeluri de sincronizare.
Semafoare. Dac platforma suport extensia POSIX n timp real (POSIX.1b), se poate avea acces la nc o primitiv de sincronizare pentru sisteme concurente - semafoarele. Un semafor de contorizare este ca un mutex, dar este asociat cu un contor. Dac platforma suport POSIX n timp real i Ptreads, se pot folosi semafoare pentru thread-uri individuale n acelai fel ca i cum s-ar folosi un mutex.
Dac biblioteca nu detecteaz o eroare n modul implicit, atunci putem verifica i n modul debug, cu detectori adiionale.
2.2 Utilizarea funciei pthread_mutex_trylock
Aceast funcie, asemntoare funciei pthread_mutex_lock, blocheaz un mutex iniializat. Spre deosebire de aceast funcie, pthread_mutex_trylock nu ateapt pn cnd mutex-ul este eliberat, ci ntoarce imediat. Aceast funcie poate fi folositor, dar nu este aa se simplu cum credem.
Teoretic vorbind, utilizarea funciei pthread_mutex_trylock nu este tocmai conform cu principiile programelor multithreading. Se apeleaz pthread_mutex_trylock pentru a preveni threadurile s fie blocate. De fapt, se creaz threadurile n program nct unele threaduri s se blocheze n timp ce altele s continu s lucreze.
Cnd vedem un apel pthread_mutex_trylock ne ntrebm de ce programatorul nu a blocat pur i simplu thread-ul i de ce nu a creat un alt thread pentru a continua lucrul, astfel programul ar fi mai simplu de neles.
Practic, un apel pthread_mutex_trylock reprezint un mod de a ncerca i de a se retrage n mod repetat pn cnd resursa este obinut. Acest lucru poate duce la o lips potenial al accesului la resurs. Dac cererea pentru o resurs este foarte mare, un thread care utilizeaz aceast metod este posibil s nu primeasc acces niciodat. Este la fel ca i cum am ncerca s lum bilete la un concert, coada se formeaz cu mult timp inainte de nceperea vnzrii biletelor i se menine pn la sfritul vnzrii. Dac nu i ii locul n coad, s-ar putea s nu primeti bilete niciodat. Similar, un thread, care nu este destul de rbdtor pentru a se bloca i atepta, poate c niciodat nu v-a gsi resursa disponibil.
2.3 Sunt mai bune alte instrumente?
Mutex-urile sunt foarte bune la controlul accesului direct la date i resurse. Cu toate c putem folosi mutex-urile pentru a construi blocuri complexe pentru mecanisme de sincronizare, Pthread ofer adesea instrumente mai potrivite pentru acesta.
n caz particular, un task n programarea thread este alctuit din sincronizri de evenimente. Fiecare thread din program poate s ajung ntr-un punct unde trebuie s atepte pn la terminarea altor threaduri. n asemenea cazuri putem folosi variabile condiionale sau contoare prin care definim nite bariere pentru threaduri. Nu fiecare thread trebuie s decrementeze aceste contoare cnd blocheaz un mutex, dar uneori este necesar s folosim mai multe blocri pentru un mutex ca acest contor s ajunge la zero. Dac vrem s folosim contoare pentru a determina dac un thread este sincronizat cu nu eveniment, atunci putem folosi variabile condiionale.
Mutex-urile sunt cele mai restrictive tipuri ale controlului de acces. Cnd un thread blocheaz un mutex pe o resurs, interzice celorlalte thread-uri accesul la resurs. n unele cazuri nu aceast metod este cea mai eficient pentru sincronizare.
Sunt cazuri n care avem mai multe thread-uri care citete data respectiv, i un singur thread care scrie. n asemenea situaii este mai bine s folosim blocri normale la citiri i mutex-uri la scriere.
Exist cazuri cnd avem nevoie de blocri recursive. Mutex-urile nu sunt pregtite pentru asemenea situaii. Putem imagina un contor intern, care se incrementeaz la fiecare blocare recursiv i se decrementeaz la fiecare deblocare, iar deblocarea definitiv se ntmpl n momentul cnd acest contor interior ajunge la zero.
Cnd mai multe thred-uri ateapt pentru deblocarea unui mutex, ce thread are acces la acesta imediat dup deblocare? Soluia este acordarea de prioriti pentru threaduri. Threadul cu cea mai mare prioritate primeste acces la blocare. Exist programe n care accesarea este fcut n mod aleator.
Folosirea prioritiilor n programea multithreading poate conduce la o problem multiprocesor clasic: inversia prioritiilor. Aceast situaie apare cnd un thread cu prioritate inferioar deine blocarea unei resurse pe care o ateapt un thread cu prioritate superior. Pentru c threadul cu prioritate mare nu poate s continu activitatea, ateptnd deblocarea, fiecare thread este tratat cum ar avea prioritatea inversat. Mutexurile pot controla asemea situaii.
3 Planificarea execuiei la threaduri
SO. selecteaz n mod continuu un singur thread care s se execute la un moment dat, o perioad de timp. Pthreads ofer utilizatorului posibilitatea de a planifica n mod propriu execuia threadurilor. Pentru a putea folosi aceast facilitate, dac se lucreaz n conjuncie cu extensia POSIX real-time, trebuie setat constanta _POSIX_THREAD_PRIORITY_SCHEDULING la TRUE.
Modul de recepionare a unui mod special de planificare de ctre un thread e determinat de setrile fcute asupra a dou atribute specifice threadurilor:
Scheduling priority := determin care thread va primi accces preferenial la CPU la un moment dat
Scheduling policy := exprimarea modului n care threaduri de aceeai prioritate se execut i partajeaz procesoarele disponibile.
Scheduling scope exprim totalitatea activitii de planificare (scheduling) la care particip un thread. Asadar, determin cte threaduri -i care- trebuie concurate pentru execuie de ctre un thread dat. Domeniul pe care se face planificarea threadurilor depinde de abilitatea implementrii SO. O anumit implementare
permite ca planificarea threadurilor s fie facut att la nivel de proces, ct i la nivel de sistem.
n cazul planificarii la nivel de proces, threadurile concureaz ntre ele n cadrul aceluiai program. Dac planificarea se face la nivel de sistem, threadurile concureaz cu altele(active) din cadrul sistemului. Pentru a stabili nivelul la care se face planificarea, exist pentru un thread un atribut care permite setarea acestuia.
Planificarea threadurilor devine mai complicat n cazul n care sunt implicate sisteme multiprocesor. Gruparea logic a mai multor procesoare n scopul planificrii threadurilor se constituie, dup standardele Pthreads, ntr-un domeniu de alocare (Allocation Domain). Dimensiunile acestor domenii nu sunt nsa stabilite strict (pot fi stabilite de programatori).
Figura ? arat modul n care lucreaz un sistem care utilizeaz planificarea la nivel de sistem, cu un singur domeniu de alocare.
Fig ?. Planificarea la nivel de sistem, cu un singur domeniu de alocare
Pe de o parte, avem procese care contin unul sau mai multe threaduri care trebuie planificate. Pe de alt parte, planificatorul (scheduler) combin procesoarele ntr-un singur domeniu de alocare. Planificatorul compar prioritile tuturor threadurilor aflate n starea run din toate procesele sistemului, pentru a-l alege pe cel care va fi lansat pe primul procesor disponibil. Ctigul de cauz l va avea threadul cu cea mai mare prioritate, indiferent de procesul n care se desfsoar.
O situatie puin diferit apare n cazul planificrii la nivel de proces. E nevoie de un planificator care s respecte planificarea doar n zona procesului, i care s compar prioritile unui thread cu a altora doar la nivelul unui singur proces. Ca rezultat, s-ar putea ca prioritile stabilite la un moment dat la nivel de proces s nu mai aib acelasi sens in la nivel de sistem.
Urmrind figura ?, se poate observa modul de lucru n acest caz. Presupunem c procesul A are trei threaduri, unul de prioritate maxim, celelalte cu prioritate medie. Planificatorul poate plasa threadul cu prioritate maxim unui procesor disponibil, i astfel se rezolv problema n cel mai simplu mod. n procesul A, n timp ce acesta se execut prin threadul cu prioritate maxim, celelate doua asteapt momentul n care vor intra i ele n execuie. ns planificatorul nu mai caut alte threaduri din afara acestui proces, care sunt n faza de rulare i care ar avea prioritate mai mic, pentru a elibera procesoarele alocate lor i pentru a rula aceste threaduri, care au o prioritate mai mare (dei nu maxim). Aceasta nseamn o folosire inadecvat a resurselor sistemului, care poate dezavantaja uneori execuia programelor.
Fig.? Planificarea la nivel de proces, cu un singur domeniu de alocare.
ntr-un sistem care suport planificarea att la nivel de proces, ct i la nivel de sistem, s consideram cel putin doua procese, A i B, a caror planificare este urmtoarea:
- threadurile procesului A sunt toate planificate la nivel de proces, avnd i un acces exclusiv pe un anumit domeniu de alocare;
- threadurile procesului B sunt planificate la nivel de sistem i au , de asemenea, propriul lor domeniu de alocare;
- presupunem c toate celelalte procese care ar mai putea exista n sistem au threadurile planificate la nivel de sistem i le e alocat domeniul ramas disponibil.
Deoarece procesele A i B nu mpart nici un domeniu de alocare cu alte procese, ele se vor executa cel mai probabil. Threadurile lor nu vor atepta niciodat dup alte procese sau threaduri ale acestora. n plus, pentru aceste dou procese sunt valabile toate proprietile specifice tipului lor de planificare (amintite mai sus).
Threaduri n execuie i threaduri blocate
n momentul n care se selecteaz un thread, planificatorul trebuie s tie despre el dac se poate executa imediat sau este blocat. Dup ce au fost determinate threadurile blocate, planificatorul trebuie s selecteze un thread care se poate executa imediat. Algoritmul de planificare trebuie aplicat doar n cazul n care numarul sloturilor de procesare disponibile este mai mic dect numarul threadurilor.
Scheduling Priority
Algoritmul de selecie folosit de planificator depinde de prioritatile de planificare i de scheduling policy a fiecarui thread.
Planificatorul cerceteaz pentru nceput un ir de cozi de prioritate(vezi figura ?). Se gestioneaz o coada pentru fiecare prioritate de planificare i, la un nivel dat de prioritate, threadurile asignate acelui tip de prioritate. n momentul n care planificatorul caut un thread pentru a-l pune n executie, ncepe cu coada prioritii celei mai mari, continund ca nivelele prioritilor inferiore, pn gsete primul thread.
Fig. 3 Cozi de prioritate
n figura 3, doar 3 dintre cozile de prioritate gestioneaz threaduri executabile.Dac unul din threadurile de o anumit prioritate i suspend execuia, el va fi automat trecut la sfritul cozii de prioritatea respectiv. n timp, numrul threadurilor dintr-o coada poate crete. n momentul n care un thread de prioritate mai mare dect cel care se execut devine executabil, el l va ntrerupe pe cel cu prioritate mai mic i l va nlocui n procesor. Aceast actiune se mai numete i schimbare involuntara de context.
Scheduling Policy
Determin , la nivel de thread, intervalul de timp n care va rula din momentul trecerii pe procesor. Atributele principale sunt :
- SCHED_FIFO : acest stil de policy permite unui thread s se ruleze pn la terminare normal, sau pn la blocare. (dup ce se deblocheaza, este trecut la sfritul cozii prioritii asignate.)
- SCHED_RR : (round robin) permite rularea unui thread pentru un interval fixat de timp, dup care procesorul va fi folosit de un alt thread de aceeai prioritate. La terminare, va fi plasat n coada prioritii asignate.
- SCHED_OTHER : ca i celelalte, specifica threadurilor quantumul de timp n care se execut, ns modific automat prioritile acestora (fr a mai fi nevoie de aciunea utilizatorului), permind i celor cu prioritate mai mic s se execute oarecum echitabil.
Utilizarea prioritilor i a modurilor de policy
ntr-o aplicaie real-time se mpart taskurile n cele care trebuie s-i termine execuia ntr-un timp finit i cele care nu necesit un regim urgent de execuie. Primele necesit un regim SCHED_FIFO i o prioritate mare, celelalte, SCHED_RR i o prioritate mai mic, dar toate acestea trebuie s aiba prioriti mai mari dect restul taskurilor din sistem. n plus, n momentul n care astfel de threaduri se execut, nu pot fi ntrerupte (dect dac se blocheaz - ceea ce nu e indicat), spre deosebire de threadurile non-real-time, care se execut doar ntr-un anumit quantum de timp, chiar dac au si ele o prioritate mare.
Setarea planificarii modului de policy i a prioritilor
Se poate face prin setarea obiectului atribut, specificat ca parametru al proc. de creare pthread_create a threadului (vezi exemplul 2 al anexei). Setarea se poate face i runtime, prin procedua pthread_setschedparam, care poate seta att prioritatea, ct i tipul de policy pentru un thread.
Motenirea
Setrile descrise mai sus se pot face si prin motenire, fr a fi nevoie de o setare explicit pt. fiecare thread creat. Setrile se pot moteni de la threadul printe(ex. ?).
Mutex Scheduling AttributesO problem real i deloc placut este aceea a inversrii prioritilor a doua threaduri. Pthreads standard permite (dar nu e neaprat necesar) crearea de mutexuri care pot da priority boost threadurilor de mica prioritate care le blocheaz(pe mutexuri). Mutexului i poate fi asociat oricare din urmtoarele doua protocoale de prioritate pe care le ofer acest mecanism : stabilirea unui plafon de prioritate sau motenirea de prioritate.
Plafonul de prioritate
Acest protocol asociaza unui mutex o prioritate planificabil. Astfel echipat, un mutex i poate asigna threadului care l deine o prioritate efectiv egal cu a lui, dac threadul respectiv avea o prioritate mai mic la nceput. Iata i secventele de creare a unui astfel de mutex.
- se creaz nti un obiect atribut al mutexului (pthread_mutex_attr_t) i se iniializeaz cu pthread_mutexattr_init.
- se obine protocolul de prioritate asociat implicit mutexului. Acesta poate fi:
PTHREAD_PRIO_NONE : mutexul nu are un protocol de prioritate;
PTHREAD_PRIO_PROTECT : mutexul utilizeaz protocolul plafonului de prioritate;
PTHREAD_PRIO_INHERIT : mutexul utilizeaz protocolul motenirii de prioritate;
- daca mutexul nu folosete protocolul plafonului de prioritate, acesta va fi setat (pthread_mutexattr_setprotocol);
- se apeleaz pthread_mutexattr_setprioceiling pentru a seta atributul de prioritate n cadrul obiectului mutex;
- se iniializeaz mutexul prin specificarea i a obiectului atribut al mutexului;
Motenirea de prioritate
Acest protocol permite unui mutex s schimbe prioritatea threadului care l-a blocat la aceea a threadului cu cea mai mare prioritate care se afla n coada de ateptare.
Task Y
main()
Task Z
Task X
Workers:
Boss
Resurse:
Fiiere
Baze de date
Diskuri
Device-uri speciale
Input Stream
Input
(static)
Program Workers
Resurse:
Fiiere
Baze de date
Diskuri
Device-uri speciale
Task X
Task Y
Task Z
Filtru 1
Fiiere
Baze de date
Diskuri
Device-uri speciale
Fiiere
Baze de date
Diskuri
Device-uri speciale
Filtru 2
Fiiere
Baze de date
Diskuri
Device-uri speciale
Scheduler
Domeniu de alocare
Threadurile Considerate
Thread(uri) selectate
CPUs
CPUs
Thread(uri) selectate
Domeniu de alocare
Scheduler
Threadurile considerate la nivel de sistem
Threadurile considerate la nivel de proces
Planificator
Threaduri executabile
Threaduri blocate
Max
Procesor
Min
Filtru 3
Filtre
....
Input Stream
Resurse
_913141342.doc
Procesul B
_913149671.doc
Procesul A
_913150546.doc
Procesul B
_913150564.doc
Procesul C
_913141346.doc
Procesul C
_913141004.doc
Procesul A