Fire de executie si procese

1.3.5 Variabila de condiție

Variabilele condiție pun la dispoziție un sistem de notificare pentru fire de execuție, permițându-i unui fir să se blocheze în așteptarea unui semnal din partea unui alt fir. Folosirea corectă a variabilelor condiție presupune un protocol cooperativ între firele de execuție.

Mutexurile (mutual exclusion locks) și semafoarele permit blocarea altor fire de execuție. Variabilele de condiție se folosesc pentru a bloca firul curent de execuție până la îndeplinirea unei condiții.

Variabilele condiție sunt obiecte de sincronizare care-i permit unui fir de execuție să-și suspende execuția până când o condiție (predicat logic) devine adevărată. Când un fir de execuție determină că predicatul a devenit adevărat, va semnala variabila condiție, deblocând astfel unul sau toate firele de execuție blocate la acea variabilă condiție (în funcție de intenție).

O variabilă condiție trebuie întotdeauna folosită împreună cu un mutex pentru evitarea race-ului care se produce când un fir se pregătește să aștepte la variabila condiție în urma evaluării predicatului logic, iar alt fir semnalizează variabila condiție chiar înainte ca primul fir să se blocheze, pierzându-se astfel semnalul. Așadar, operațiile de semnalizare, testare a condiției logice și blocare la variabila condiție trebuie efectuate având ocupat mutexul asociat variabilei condiție. Condiția logică este testată sub protecția mutexului, iar dacă nu este îndeplinită, firul apelant se blochează la variabila condiție, eliberând atomic mutexul. În momentul deblocării, un fir de execuție va încerca să ocupe mutexul asociat variabilei condiție. De asemenea, testarea predicatului logic trebuie făcută într-o buclă, deoarece, dacă sunt eliberate mai multe fire deodată, doar unul va reuși să ocupe mutexul asociat condiției. Restul vor aștepta ca acesta să-l elibereze, însă este posibil ca firul care a ocupat mutexul să schimbe valoarea predicatului logic pe durata deținerii mutexului. Din acest motiv celelalte fire trebuie să testeze din nou predicatul pentru că altfel și-ar începe execuția presupunând predicatul adevărat, când el este, de fapt, fals.
Inițializarea/distrugerea unei variabile de condiție:

// initializare statica a unei variabile de condiție cu atribute implicite

// NB: variabila de conditie nu este eliberata,

// durata de viata a variabilei de condiție este durata de viata a programului.

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

// semnaturile functiilor de initializare si eliberare de variabile de condiție:

int pthread_cond_init (pthread_cond_t *cond, pthread_condattr_t *attr);

int pthread_cond_destroy(pthread_cond_t *cond);

Ca și la mutex-uri:

• 
  dacă parametrul attr este nul, se folosesc atribute implicite
  
• 
  trebuie să nu existe nici un fir de execuție în așteptare pe variabila de condiție atunci când aceasta este distrusă, altfel se întoarce EBUSY.
  

Blocarea la o variabilă condiție
Pentru a-și suspenda execuția și a aștepta la o variabilă condiție, un fir de execuție va apela:

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

Firul de execuție apelant trebuie să fi ocupat deja mutexul asociat, în momentul apelului. Funcția pthread_cond_wait va elibera mutexul și se va bloca, așteptând ca variabila condiție să fie semnalizată de un alt fir de execuție. Cele două operații sunt efectuate atomic. În momentul în care variabila condiție este semnalizată, se va încerca ocuparea mutexului asociat, și după ocuparea acestuia, apelul funcției va întoarce. Observați că firul de execuție apelant poate fi suspendat, după deblocare, în așteptarea ocupării mutexului asociat, timp în care predicatul logic, adevărat în momentul deblocării firului, poate fi modificat de alte fire. De aceea, apelul pthread_cond_wait trebuie efectuat într-o buclă în care se testează valoarea de adevăr a predicatului logic asociat variabilei condiție, pentru a asigura o serializare corectă a firelor de execuție. Un alt argument pentru testarea în buclă a predicatului logic este acela că un apel pthread_cond_wait poate fi întrerupt de un semnal asincron (vezi laboratorul de semnale), înainte ca predicatul logic să devină adevărat. Dacă firele de execuție care așteptau la variabila condiție nu ar testa din nou predicatul logic, și-ar continua execuția presupunând greșit că acesta e adevărat.
1.3.6 Monitoare
Monitor (Hoare, 1974; Hansen, 1975) este un pachet de proceduri, variabile şi structuri de date:

Procesele pot apela procedurile unui monitor, dar nu pot accesa variabile şi structurile de date interne ale monitorului.

Doar un singur proces poate fi activ în monitor, la un moment dat (se poate executa doar o singură procedură din monitor).

Excluderea mutuală a mai multor procese: plasarea tuturor secţiunilor critice într-un monitor

Variabile condiţie, cu operaţiile wait şi signal

1. 
   
   

• 
  Când o procedură din monitor nu poate continua ea va executa un wait pe o variabilă condiţie.
  
• 
  Această acţiune blochează procesul apelant şi permite altui proces să intre în monitor
  
• 
  Acest alt proces poate debloca primul proces executând signal pe variabila condiţie aşteptată de acesta.
  
• 
  Al doilea proces trebuie apoi să părăsească monitorul, pentru a permite procesului deblocat să-şi continue execuţia în monitor.
  
• 
  Variabilele condiţie nu acumulează semnale pentru a fi prelucrate ulterior.
  
• 
  Dacă o variabilă condiţie este utilizată într-un apel signal şi nu există nici un proces care să aştepte acest semnal, atunci semnalul este pierdut.
  
• 
  Un apel wait trebuie să preceadă un apel signal.
  

Structura de tip monitor trebuie să fie suportată de limbajul de programare (Java).

monitor ProducerConsumer

condition full, empty;

integer count;

procedure insert(item: integer);

begin

if count = N then wait(full);

insert _item(item);

count := count + 1;

if count = 1 then signal(empty)

end;

function remove: integer;

begin

if count = 0 then wait(empty);

remove = remove_item;

count := count - 1;

if count = N - 1 then signal(full)

end;

count := 0;

end monitor;

procedure producer;

begin

while true do

begin

item = produce _item;

ProducerConsumer.insert(item)

end

end;

procedure consumer;

begin

while true do

begin

item = ProducerConsumer.remove;

consume_item(item)

end

end;

1.3.7 Fenomenul de Deadlock

Un set de procese este în deadlock dacă fiecare proces aşteaptăun eveniment care poate fi generat doarde un alt proces din set.

De obicei, în SO, evenimentele aşteptate sunt reprezentate de eliberarea unor resurse.

Exemple deadlock


\

Exemplul celebru “Cina filosofilor”

Dacă fiecare filozof ia băţul din stânga sa, nici unul dintre ei nu va putea lua şi băţul din dreapta ajungându-se în deadlock.

Condiţii de apariţie a deadlock-ului
4 condiţii necesare pt. apariţia deadlock-ului într-un sistem:

1. 
   Excludere mutuală: fiecare resursă este deţinută de cel mult
   

un proces

2. 
   “Hold & wait”: procesele care încă deţin resurse primite
   

anterior pot solicita/aştepta alte resurse.

c) Resurse ne-preemptive: Resursele primite de un proces nu pot fi luate forţat de la proces. Ele trebuie eliberate explicit de procesul care le deţine.

d)Aşteptare circulară: Există un lanţ circular de două sau mai multe procese, unde fiecare aşteaptă eliberarea unei resurse deţinută de următorul proces din lanţ.

Neîndeplinirea unei condiţii duce la neapariţia fenomenului de deadlock.

Deadlock-ul nu poate fi terminat fără o intervenţie externă entităţilor implicate.

Condiţiile de deadlock pot fi modelate cu un graf bipartit, denumit graful resurselor

Tehnici de tratare a deadlock-ului
1) Se permite apariţia deadlock-ului, se detectează şi se iau măsuri

2) Se evită dinamic deadlock-ul prin alocarea cu atenţie a resurselor

3) Se previne apariţia deadlock-ului prin negarea la nivel structural a uneia din cele 4 condiţii de deadlock

4) Ignorarea deadlock-ului (simplu, des întâlnit – Win, Unix – efecte ...)

Observaţii:

Deadlock-ul apare prin interacţiunea mai multor procese şi resurse, şi nu poate fi rezolvat prin strategii individuale

Deadlock-ul nu apare mereu pt. o aceeaşi secvenţă de cod/operaţii; poate să apară datorită unei anumite sincronizări întâmplătoare.
Refacerea sistemului din deadlock

Refacerea prin preempţie

1. 
   
   

• 
  preemptarea unei resurse de la procesul proprietar, şi suspendarea acestui proces
  
• 
  atribuirea acelei resurse unui alt proces
  
• 
  când al doilea proces îşi încheie execuţia, resursa este redată vechiului proprietar
  

Dezavantaj: preemptarea unei resurse este puternic dependentă de tipul acesteia

Refacerea prin rollback

1. 
   
   

Se creează periodic puncte de verificare pentru toate procesele din sistem (checkpoints), prin salvarea stării proceselor într-un fişier. Fişierele nu sunt suprascrise.

La dedectarea unui deadlock, se verifică resursele necesare refacerii. Un proces deţinând o astfel de resursă este readus la o stare anterioară solicitării resursei respective (resetat la un moment anterior de timp)

Resursa este atribuită unui proces aflat în deadlock
Refacerea prin distrugere de procese

Se distruge un procesul şi se eliberează resursele deţinute, în vederea ieşirii din deadlock.

Alegerea procesului distrus...

Race Condition

Situaţia în care două sau mai multe procese citesc sau scriu date partajate, iar rezultatul final este dictat de ordinea acestor operaţii se numeşte competiţie între procese (race condition).

Soluţia la problema competiţiei trebuie să satisfacă următoarele condiţii:

C1. Două procese nu pot fi simultan în SC.

C2. Nu se pot face presupuneri în legătură cu vitezele şi numărul proceselor.

C3. Nici un proces care se află în afara SC nu poate bloca alte procese.

C4. Nici un proces nu trebuie să aştepte la infinit să intre în SC.

Procesul B ar trebui să fie blocat până în momentul în care procesul A părăseşte secţiunea sa critică.

Excludere mutuală între cele două procese

Jitaru Claudiu (433 A)

Bibliografie – Partea de windows , Documentaţie : http://msdn.microsoft.com/en-us/library/ms685100%28v=VS.85%29.aspx

1.4.1 Gestiunea proceselor şi a firelor de execuţie în Windows

În cazul sistemului de operare Windows resursele necesare pentru execuţia unui program sunt furnizate de fiecare proces.Printre caracteristicile procesului se numără un spaţiu de adrese virtuale , cod executabil , handle-uri la obiecte de sistem , un context de securitate , un identificator de proces unic , variabilele de mediu , o prioritate de clasă , dimensiuni de lucru minime şi maxime şi cel puţin un fir de execuţie.Fiecare proces este pornit cu un singur fir de execuţie , numit adesea firul principal.De-a lungul execuţiei acesta poate crea alte fire de execuţie.

Entitatea din cadrul unui proces care poate fi programată pentru execuţie poartă numele de thread sau fir de execuţie.Toate firele de execuţie al unui proces împart spaţiul de adrese virtuale şi resurse ale sistemului din cadrul procesului.Pe lângă aceastea fiecare thread prezintă mecanisme de tratare a excepţiilor ,locaţia de stocare,o programare în funcţie de priorităţi , un identificator unic şi un set de structuri care vor fi folosite de sistem pentru a salva contextul firului de execuţie până cănd acesta este executat.Contextul firului de execuţie cuprinde stiva kernel,setul de registre maşină a thread-ului, un bloc de mediu al thread-ului şi un utilizator stivă în spaţiul de adresă a procesului firului de execuţie respectiv.

Un obiect de tip job permite grupurilor de procese să fie gestionate ca o unitate.Acestea prezintă avantajul de a fi securizabile.Toate procesele asociate cu obiectul de tip job sunt afectate de operaţiile efectuate pe acesta.‘Thread pool’-ul este folosit de o aplicaţie pentru a reduce numărul de fire de execuţie de tip aplicaţii şi să asigure gestionarea thread-urilor aflate în desfăşurare.

User mode scheduling (UMS) este un mecanism pe care aplicaţiile îl pot utiliza pentru a-şi programa propriile thread-uri.O aplicaţie poate comuta între thread-uri UMS în modul user fără să implice planificatorul de sistem şi să preia controlul procesorului dacă un bloc thread de tip UMS pătrunde în kernel.Posibilitatea de a comuta între fire de execuţie în modul user face ca UMS-ul sa fie o soluţie mai eficientă decât thread pool-urile pentru muncă de scurtă durată ce necesită puţine apeluri de sistem.

Un ‘fiber’ este o unitate de execuţie care trebuie să fie programată manual de aplicaţie.Fiber-urile pot rula în contextul thread-urilor care le-au programat iar fiecare thread poate programa mai multe fiber-uri. În majoritatea cazurilor , fiber-urile nu asigură avantajele faţă de o aplicaţie multithread bine concepută.Utilizarea fiber-urilor pot să uşureze aplicaţiile care au fost concepute de a programa propriile threaduri.

Multitasking-ul este prezent şi în sistemul de operare Microsoft Windows şi creează efectul de execuţie simultană a mai multor fire de execuţie de la multiple procese.Pe un sistem multiprocesor , acesta poate executa simultan atâtea thread-uri câte procesoare are sistemul.Un sistem de operare multitasking împarte timpul procesorului valabil între procesele sau thread-urile care au nevoie de el.Acesta alocă o durată de timp de procesor format din cuante de timp pentru fiecare thread ce se execută.Firul de execuţie curent este suspendat atunci când durata de timp se scurge , lăsând alt thread de a rula.Când sistem trece de la un thread la altul ,se salvează contextul threadului anterior şi se restaurează contextul salvat al următorului thread din coada de aşteptare.

Durata de timp a unui thread depinde de sistemul de operare şi procesor.Deoarece aceasta în general este foarte mică în majoritatea cazurilor,aproximativ 20 de milisecunde, mai multe fire de execuţie par să fie executate în acelaşi timp.Aceasta este situaţia pe un sistem multiprocesor unde thread-urile executabile sunt distribuite între procesoarele valabile.Cu toate aceastea , thread-urile trebuie folosite prudent într-o aplicaţie deoarece performanţele sistemului pot scădea dacă sunt prea multe threaduri.

Programarea priorităţilor

Execuţia thread-urile sau firelor de execuţie se realizează pe baza priorităţilor lor.Fiecărui fir de execuţie îi este atribuită o prioritate de planificare.Nivele de prioritate variază de la zero(prioritatea cea mai mică ) la 31 (prioritatea cea mai mare ).Prioritatea de zero îi este rezervată doar thread-ului zero-page.Acesta este un thread de sistem responsabil pentru reducerea la zero oricărei pagini libere atunci când nu există alte thread-uri pentru execuţie.

Sistemul tratează toate firele de execuţie cu aceeaşi prioritate ca şi cum ar fi egale.Acesta atribuie durate de timp într-un mod round-robin tuturor thread-urilor cu prioritatea cea mai mare.Dacă nici una dintre aceastea nu sunt pregătite pentru a rula , sistemul atribuie durate de timp într-un mod round-robin tuturor thread-urilor cu prioritatea cea mai mare următoare.În cazul în care un thread cu prioritate mai mare devine valabil pentru rulare , sistemul încetează să execute thread-ul cu prioritate mai mică ( fără a îi permite acestuia să îşi finalizeze cuantele de timp ) si atribuie o durată întreagă de timp thread-ului cu prioritatea mai mare.

Factorii ce determină prioritatea fiecărui thread sunt:

*Prioritatea de clasă a procesului său.

*Nivel de prioritate a thread-ului din prioritatea de clasă a procesului său.

Prioritatea de clasă şi nivelul de prioritate sunt combinate pentru a forma prioritatea de bază a thread-ului.

Prioritatea de clasă

Fiecare proces face parte din una din categoriile prioritare:

• 
  IDLE_PRIORITY_CLASS
  
• 
  BELOW_NORMAL_PRIORITY_CLASS
  
• 
  NORMAL_PRIORITY_CLASS
  
• 
  ABOVE_NORMAL_PRIORITY_CLASS
  
• 
  HIGH_PRIORITY_CLASS
  
• 
  REALTIME_PRIORITY_CLASS
  

În mod implicit, clasa de prioritate a unui proces este NORMAL_PRIORITY_CLASS.Procesele care monitorizează sistemul , cum ar fi screen saver-urile sau aplicaţiile care updatează periodic un afişaj ar trebui să folosească IDLE_PRIORITY_CLASS.Acest lucru previne ca firele de execuţie al acestui proces , care nu au prioritate mare să intervină cu fire de prioritate mai mare.

Utilizarea HIGH_PRIORITY_CLASS presupune mai multă atenţie.Modul prin care thread-urile sistemului nu mai primesc timp de procesor este dată de prezenţa în sistem a unui thread de prioritate mare pentru perioade lungi de timp..Dacă mai multe thread-uri sunt setate la prioritatea cea mai mare la acelaşi moment de timp , firele de execuţie îşi pierd din eficacitatea lor.Clasa de prioritatea cea mai mare ar trebui rezervată pentru thread-uri care trebuie să răspundă la evenimente critice de timp.Este esenţial ca un thread de prioritate mare să se execute pentru o scurtă perioadă de timp şi numai atunci când are muncă ce necesită un timp critic.

REALTIME_PRIORITY_CLASS întrerupe thread-uri care gestionează input-urile de la mouse , tastatură şi background disk flushing.De aceea această prioritate de clasă nu trebuie să fie folosită .REALTIME_PRIORITY_CLASS poate fi folosită de aplicaţii pentru a “discuta” direct cu hardware-ul sau de a executa sarcini scurte care ar trebui să aibă întreruperi limitate.
Nivelurile de prioritate

Nivelurile de prioritate din cadrul fiecărei priorităţi de clasă sunt următoarele:

• 
  THREAD_PRIORITY_IDLE
  
• 
  THREAD_PRIORITY_LOWEST
  
• 
  THREAD_PRIORITY_BELOW_NORMAL
  
• 
  THREAD_PRIORITY_NORMAL
  
• 
  THREAD_PRIORITY_ABOVE_NORMAL
  
• 
  THREAD_PRIORITY_HIGHEST
  
• 
  THREAD_PRIORITY_TIME_CRITICAL
  

Toate thread-urile sunt create folosind THREAD_PRIORITY_NORMAL.În cazul acesta prioritatea thread-ului este aceeaşi cu cea a procesului cu clasa de prioritate.

O strategie tipică este de a folosi THREAD_PRIORITY_ABOVE_NORMAL sau THREAD_PRIORITY_HIGHEST pentru thread-ul input al procesului , pentru a se asigura că aplicaţia este receptivă la utilizator. THREAD_PRIORITY_BELOW_NORMAL sau THREAD_PRIORITY_LOWEST sunt folosite în cazul thread-urilor de background în particular consumatoare de procesor.

Prioritatea de clasă si prioritatea de thread sunt combinate pentru a forma prioritatea de bază a fiecărui fir de execuţie.

Boost-uri de prioritate (Mecanism cu bonusuri de prioritate)

Fiecare thread are o prioritate dinamică.Aceasta este prioritatea planificatorului pe care o foloseşte pentru a determina care thread să se execute.Iniţial , prioritatea dinamică a thread-ului este aceeaşi ca prioritatea de bază.Sistemul poate stimula în a micşora prioritatea dinamică , pentru a se asigura ca este receptiv.Acesta nu măreşte prioritatea thread-urilor cu o prioritate de bază între 16 şi 31.Doar thread-urile cu prioritatea de bază între 0 şi 15 poate primii bonusuri de prioritate.

Sistemul favorizează prioritatea dinamică a thread-ului pentru a spori capacitatea sa după cum urmează :

• 
  Atunci când un proces care foloseşte NORMAL_PRIORITY_CLASS este adus în prim plan , planificatorul sporeşte prioritatea de clasă a procesului asociat cu fereastra de prim-plan , pentru a se asigura că este mai mare sau egal cu prioritatea de clasă al oricărui proces care rulează în planul secund.Prioritatea de clasă se returnează la setarea sa iniţială atunci când procesul nu mai este în prim plan.
  
• 
  Atunci când o fereastră aşteaptă date de intrare , cum ar fi mesajele de tip timer , mesaje de la mouse sau tastatură , planificatorul creşte prioritatea thread-ului care deţine fereastra.
  
• 
  În cazul în care condiţiile de wait pentru un thread blocat sunt satisfăcute , planificatorul creşte prioritatea thread-ului.De exemplu, atunci când o operaţie de aşteptare asociate cu floppy disc-ul sau tastatura I/O se termină , thread-ul primeşte un bonus de prioritate.
  

După creşterea priorităţii dinamice a unui thread , planificatorul reduce prioritatea cu câte un nivel de fiecare dată când thread-ul îşi completează durata de timp asociată, până când ajunge la prioritatea de bază.Un prioritate dinamică de thread nu este niciodata inferioară priorităţii de bază a acesteia.
Bibliografie – Partea de thread-uri LINUX , Documentaţie : http://tldp.org/FAQ/Threads-FAQ/Types.html

1.4.2.Gestiunea proceselor şi firelor de execuţie in Linux

În cazul sistemului de operare Linux thread-urile sunt privite ca fiind “procese uşoare” (light weight processes – LWPs).Ideea de bază este că un process prezintă 5 părţi fundamentale : data (VM) , stivă , fişiere I/O , cod(“text”) şi tabele de semnal.

În linux există 2 tipuri de thread-uri : user-space şi kernel-space.

Thread-uri user-space

Aceste tipuri de thread-uri evită kernel-ul şi gestionează tabelele ele însuşi.Deseori,aceasta se mai numeşte “multitasking cooperativ” unde sarcina defineşte un set de rutine care pot fi comutate spre manipularea pointerul stivă.De obieci fiecare thread “renunţă” la CPU printr-o apelare explicită switch , trimiţând un semnal sau executând o operaţie ce implică switcher-ul.Totodată , un semnal de timp poate forţa switch-ul.Thread-urile user de obicei pot comuta mai repete decât cele kernel.

Dezavantajul thread-urilor user space o reprezintă problema ca un singur thread să monopolizeze durata de timp în schimbul servirii altor thread-uri sarcina sau task-ul acesteia.De asemenea , nu are nici o modalitate de a profita de SMPS(Symmetric MultiProcessor szstems , de exemplu dual-/-quad-Pentium).În cele din urmă atunci când un thread devine blocat I/O , toate celelalte thread-uri din componenţa task-ului pierd durata de timp asociată.

Unele librării user-thread au abordat aceste probleme cu numeroase work-arounds.În primul rând monopolizarea timpului poate fi controlată cu un monitor extern ce foloseşte propriile bătăi de ceas.În al doilea rand unele SMPs-uri pot suporta multithreading de tip user-space prin trimiterea task-urilor sau sarcinilor de lucru la CPU specifice şi pornirea thread-ului de acolo.În al treilea rand câteva librării rezolvă problema blocării I/O cu ‘wrappers’ speciali peste apeluri de sistem sau task-ul poate fi scris pentru nonblocking I/O.

Thread-uri Kernel Space

Acestea de obicei sunt implementate în kernel utilizând numeroase tabele ( fiecare task primeşte o tabelă de thread-uri).În cazul acesta kernel-ul programează fiecare thread în durata fiecărui proces.

Avantaje.Deoarece bătaia de ceas va determina timpii de comutare , un task este puţin probabil ca să ducă la capăt durata de timp de la alte threaduri din task-ul respectiv.Totodata blocările I/O nu mai reprezintă o problemă.În sfărşit dacă sunt corect codificate , procesul automatic poate profita de avantajele SMPs-urilor şi va rula mai rapid cu fiecare CPU adăugat.

Unele implementări prezintă thread-uri atât user cât şi kernel space .Acestea oferă avantajele fiecăruia task-ului respectiv.Totodată , deoarece firele de execuţie kernel-space prezintă performanţe asemănătoare cu cele user-space , singurul avantaj de a folosi thread-uri user ar fi multitasking-ul cooperativ.
Bibliografie : Partea de procese –Documentaţie : http://linux.die.net/Intro-Linux/sect_04_01.html

Tipuri de procese