cuprins: - ingineria sistemelor de calculstst.elia.pub.ro/news/teme_soiii_2010/prfirex/fire...

Fire de executie si procese

Cuprins:Adrian Pop(434Aa)

1 Principiile ale gestiunii de procese si fire de executie:

1.1 Concepte generale

1.1.1 Procese

1.1.2 Fire de executie

1.2 Mecanisme de comunicare interproces

1.2.1 Pipe-uri

1.2.2 Semnale

Vutan Gheorghe Adrian (433 A)

1.3 Mecanisme de sincronizare

1.3.1 Semafoare

1.3.2 Mutexuri

1.3.3 Evenimente

1.3.4 Sectiuni critice

1.3.5 Variabile de conditie

1.3.6 Monitoare

1.3.7 Probleme de sincronizare: deadlock, race condition

Jitaru Claudiu(433 A)

1.4 Functii API de gestiune a proceselor si firelor de executie

1.4.1 Gestiunea proceselor si a firelor de executie in Windows

1.4.2 Gestiunea proceselor si a firelor de executie in Linux

Andrei Stefanescu(433 A)

2 Algoritmi de gestiune de procese si de fire de executie

2.1 Algoritmi de alocare a timpului de procesor

2.1.1 Algoritmi “standard”

2.1.1.1 Round-Robin

2.1.1.2 Shortest job first

2.1.1.3 Priority scheduling

2.1.1.4 Multiple priority queues

2.1.1.5 Inheritance scheduling

2.1.1.6 Lottery scheduling

Cotoc Ginel Dragos(433 A )

2.1.2 Algoritmi folositi in sistemele de operare moderne

2.1.2.1 Multilevel feedback queue (Windows NT)

2.1.2.2 O(1) (Linux)

2.1.2.3 Completely Fair Scheduler(Linux)

Petre Marian-Alin(434Aa)

2.2 Algoritmi de alocare a resurselor in sistem multiprocesor

Sindrilaru Florian(433 A)

2.2.1 Algoritmi “one-shot”

2.2.1.1 Min-min

2.2.1.2 Chaining

2.2.1.3 Highest level first with estimated times (HLFET)

2.2.1.4Insertion scheduling heuristic (ISH)

2.2.1.5 Duplication scheduling heuristic (DSH)

Petre Marian-Alin(434Aa)

2.2.2 Algoritmi de cautare iterativa

2.2.2.1 Algoritmi genetici

2.2.2.2 A*

2.2.2.3 Simulated anealing

2.2.2.4 Tabu search

2.2.3 Concluzii

Pop Adrian Cristian (434 Aa)

1.1.1.Procese:

Toate calculatoarele moderne , deseori fac mai multe lucruri in acelasi timp , insa oamenii care lucrau cu calculatoare personale nu erau constienti de acest lucru, asa ca vom considera cate exemple pentru a clarifica acest lucru. De exemplu , pentru un Server de Web ,cererile pot veni din diverse directii , solicitand o anumita pagina Web. Atunci cand o cerere soseste , serverul verifica daca are pagina ceruta in memoria tampon( cache).Daca aceasta exista , este returnata solicitantului , daca nu , se incepe procedura de aducere a paginii de pe disc. Insa , din perspectiva procesorului , aceste cereri de aducere de pe disc dureaza o eternitate. In timp ce asteapta ca aceasta cerere sa se finalizeze , pot aparea alte cereri de acest gen. Daca avem mai multe discuri la dispozitie , unul sau toate pot fi pornite inainte ca prima cerere sa fie solutionata. Evident este nevoie de un mod de control ale acestor cereri simultane. Aici intervin procesele (si in special firele de executie).

Sa luam de exemplu un PC. Atunci cand sistemul se porneste , multe dintre procese sunt pornite silentios de multe ori fara stirea utilizatorului. De exemplu , un proces poate fi pornit in asteptarea e-mailurilor ce trebuie sa soseasca. Alt proces poate functiona pentru antivirus , pentru a verifica daca nu au aparut definitii noi despre virusi. In plus , pot rula si diferite procese pornite de utilizator, printari de fisiere , scrieri pe un CD-ROM , toate concomitent cu navigarea pe internet a utilizatorului. Toate aceste activitati trebuie sa fie gestionate si un sistem multiprogram ce suporta mai multe procese in paralel ar fi foarte indicat.

In orice sistem multiprogramare , UCP trece de la un proces la altul foarte rapid , rulandu-le pe fiecare timp de zeci sau sute de milisecunde. Desi , in realitate UCP ruleaza doar un singur proces la fiecare moment de timp, in durata a unei secunde acesta poate lucra la multe din ele , dand iluzia de paralelism.Unele persoane definesc acest lucru ca fiind pseudoparalelism , in contrast cu paralelismul real bazat pe posibilitati hardware ale unor sisteme multiprocesor (care au doua sau mai multe CPU-uri ce impart aceeasi memorie fizica). Urmarirea acestor activitati multiple si paralele este apropape imposibila pentru oameni de facut.

De aceea , creatorii de sisteme de operare au folosit un model conceptual , pe care l-au dezvoltat pentru a face fata paralelismului. Acest model va fi tratat in continuare.

Modelul de proces:

In acest model , orice aplicatie executabila de pe calculator precum si sistemul de operare este organizat intr-un numar de procese secventiale, sau pe scurt procese. Un proces este o instanta a unui program aflat in executie , continand valorile curente ale contorului de program , registrii si variabile. Conceptual , fiecare proces are CPU-ul lui propriu. In realitate insa , CPU-ul real trece de la un proces la altul, insa pentru a intelege mai bine acest sistem , e mai usor sa ne gandim la aceste procese ca ruleaza intr-un pseudo-paralelism, in loc de a incerca sa urmarim saltul procesorului de la program la program. Acest salt rapid de la un proces la altul este numit multiprogramare .

In continuare , vom considera existenta unui singur CPU, insa mai nou aceasta presupunere nu este realista pentru ca apar cipuri cu mai multe core-uri ,continand doua , patru sau mai multe CPU.Deci atunci cand zicem ca un procesor poate rula un proces in acelasi moment de timp , daca exista doua core-uri(sau procesoare) fiecare dintre ele va rula un singur proces in acelasi timp.

Cu trecerea rapida a procesorului de la un proces la altul , rata la care aceste procese vor face calculele nu va fi uniforma si probabil nereproductibila daca aceleasi procese ar rula din nou. Deci , procesele nu pot fi programate cu anumite presupuneri legate de timpii de executie.

Diferenta dintre un proces si un program este subtila dar cruciala.Un proces reprezinta o activitate anume. El are un program , intrare , iesire , si o stare. Un singur procesor poate fi impartit intre mai multe procese , cu ajutorul unui algoritm care va fi folosit pentru a stabili cand sa se opreasca din executia unui proces si sa treaca la altul.

Este inutil ca un program sa ruleze de doua ori , ar exista doua procese. De exemplu , de multe ori se intampla sa porniti un program de doua ori , sau sa printati doua fisiere in acelasi timp, daca dispuneti de doua imprimante.Faptul ca doua procese in derulare se intampla sa ruleze acelasi program nu conteaza pentru ca ele sunt doua procese distincte. Sistemul de operare poate fi capabil sa imparta codul intre cele doua astfel incat in memorie sa existe doar o singura copie , insa acest lucru este un detaliu tehnic ce nu schimba situatia conceptuala a doua procese in derulare.

Crearea Proceselor:

Sistemele de operare trebuie sa poata crea procese. In sistemele cele mai simple , sau in sistemele create pentru a rula o singura aplicatie ( de ex: controllerul dintr-un cuptor cu microunde) , este posibil ca sa avem toate procesele necesare vreodata pornite atunci cand sistemul se deschide. Insa , in sisteme de uz general , avem nevoie de un mod prin care sa creem si inchidem procese , dupa necesitate.

Exista patru evenimente principale care necesita crearea unui proces:

1) Initializarea sistemului2) Executia cererii de creare a unui proces de catre un alt proces in derulare3) Cererea de catre utilizator pentru crearea unui nou proces4) Initializarea unei sarcini multiple

Atunci cand sistemul porneste , sunt create diferite procese. Unele dintre aceste procese sunt procese de fundal , care au ca scop interactionarea cu utilizatorul si de a lucra pentru el. Alte procese sunt ascunse , nefiind asociate unui utilizator anume , insa au fiecare cate o functie specifica. De exemplu , un proces ascuns poate fi creat pentru acceptarea e-mailurilor ce vor sosi, care sta intr-o stare latenta in mare parte a zile , insa se trezeste la viata in momentul sosirii unui nou e-mail.

Pe langa procesele create la incarcarea sistemului , noi procese pot fi create de asemenea si dupa aceea.De multe ori un proces in derulare va cere sistemului sa creeze unul sau mai multe procese pentru a-si usura munca.Un exemplu unde acest lucru ar fi eficient , este intr-un sistem in care o cantitate mare de informatii este transferat printr-o retea , atunci ar fi mai bine sa existe un proces care primeste fiecare pachet , si il pune in memorie , iar alt proces ia informatia din memorie si o proceseaza secvential. Intr-un multiprocesor , permiterea rularii unui proces pe un CPU diferit poate face ca sarcina sa se finalizeze mai rapid.

In toate aceste cazuri , un nou proces este creat prin intermediul unui alt proces care face un apel de creare la sistem. Acel proces poate fi unul rulat de un utilizator , un proces de sistem invocat de tastatura sau mouse sau un manager de sarcini multiple.Acel apel la sistem ii spune sistemului sa creeze un nou proces si ii indica , direct sau indirect , in care program sa il ruleze.

In UNIX , exista un singur apel de sistem pentru crearea unui nou proces : fork. Acest apel creaza o clona a procesului apelant. Dupa fork , cele doua procese , parintele si copilul (denumiri pentru cele doua procese, ce rezulta din ierarhie) au aceeasi imagine de memorie, aceleasi variabile de mediu , si aceleasi fisiere deschise. De obicei , noul proces creat , copilul , executa comanda execve sau un alt apel de sistem similar pentru a-si schimba imaginea de memorie si sa ruleze un alt program.

In Windows , avem un singur apel de functie Win32 , CreateProcess , care creaza procesul si de asemenea incarca programul corect in acesta. Acest apel are 10 parametrii , incluzand programul care urmeaza a fi executat , parametrii liniei de comanda pentru acel program , diferite atribute de securitate , biti de control pentru fisierele mostenite, informatie despre prioritate , informatii despre fereastra ce urmeaza a fi creata pentru acest proces (daca este cazul) , si un pointer catre o structura in care informatia despre noul proces este returnata apelantului. In plus , pe langa acest apel CreateProcess , WIN32 mai are 100 alte functii pentru gestionarea si sincronizarea proceselor si a altor subiecti asemanatori.

Atat in UNIX cat si in Windows , dupa ce un proces este creat , parintele si copilul au spatiile lor de memorie distincte.Daca oricare dintre ele modifica un cuvand din spatiul de adrese , aceasta modificare nu este vizibila pentru celalalt proces. In UNIX , spatiul initial al copilului este practic o copie a parintelui , insa exista doua spatii de adresare distincte, nefiind partajata nici un fel de memorie inscriptionabila. E posibil insa ca un proces nou creat sa isi imparta cateva din resursele creatorului, cum ar fi fisiere deschise. In Windows , adresa parintelui si a copilului sunt diferite de la bun inceput.

Terminarea proceselor:

Dupa crearea unui proces , acesta este rulat si executa ce are de facut, dupa care trebuie sa dispara. Acesta poate poate disparea datorita urmatoarelor conditii:

1) Iesire normala (voluntara)2) Iesire pe baza de eroare(voluntara)3) Eroare fatala (involuntara)4) Terminat de catre un alt proces (involuntar)

Majoritatea proceselor dispar pentru ca si-au terminat treaba . De exemplu , atunci cand un compilator termina de compilat un program, acesta executa un apel in sistem pentru a-i semnaliza sistemului de operare ca a terminat. Acest apel se numeste exit in UNIX si ExitProcess in Windows. Exista si modalitati de terminare voluntara in mediile vizuale , ca de exemplu o iconita pe care utilizatorul poate da click ,fapt care anunta procesul sa isi stearga toate fisierele temporare pe care le are deschise si sa se inchida.

Un al doilea motiv de inchidere este atunci cand procesul descopera o eroare fatala. De exemplu , daca un utilizator incearca sa compileze un program foo.c , si nu exista acest fisier , atunci compilatorul iese pur si simplu. Procesele interactive vizuale , nu se inchid de obicei atunci cand primesc parametrii gresiti , ci afiseaza o fereastra prin care ii cer utilizatorului sa incerce din nou.

Un al treilea motiv pentru care se termina este reprezentat de erorile cauzate de proces , din cauza unui bug de program. Aici putem mentiona executarea unei instructiuni ilegale sau referirea la un spatiu de memorie inexistent precum si divizarea prin 0. In unele sisteme ( de ex UNIX ) , un proces ii poate transmite sistemului de operare ca doreste sa trateze unele erori pe cont propriu , iar acest proces este intrerupt si nu terminat , la aparitia unei erori.

Un al patrulea motiv pentru care un proces poate termina este ca acest proces executa un apel catre sistem prin care ii cere sa termine un alt proces, apel denumit in UNIX , kill , iar in Win32 TerminateProcess. In ambele cazuri , solicitantul trebuie sa aiba drepturile necesare pentru a inchide procesul.

Ierarhii in procese:

In unele sisteme , atunci cand un proces creaza un alt proces, parintele si fiul pot fi asociate in anumite feluri. Procesul creat poate avea la randul sau alte procese , astfel formandu-se o ierarhizare.

In UNIX , un proces si toti copii sai , precum si ceilalti descendenti formeaza un grup de procese. Atunci cand un utilizator trimite un semnal de la tastatura , acesta este transmis tuturor membrilor grupului asociati tastaturii. Individual , fiecare dintre procese poate alege sa trateze , sa ignore semnalul sau sa fie terminate de catre acest semnal.

In contrast , Windows nu foloseste aceasta ierarhizare a proceselor , toate procesele fiind egale. Singura asemanare cu aceasta este ca atunci cand un proces este creat , parintele primeste un token (drept denumit handle) care poate fi folosit pentru a controla descendentul sau. Insa acesta poate transmite acest drept oricarui alt proces , astfel invalidand ierarhia. Procesele din UNIX nu pot dezmosteni descendentii lor.

Starile proceselor:

Desi fiecare proces este o entitate independenta , cu stare interna , contor de program , si stare interna , procesele trebuie sa interactioneze cu alte procese.Un proces poate genera date de intrare pentru un alt proces.

Atunci cand un proces se blocheaza, acest lucru se intampla evident din cauza ca nu mai poate continua , si asteapta de obicei niste date de intrare. De asemenea se poate intampla ca un proces sa fie pregatit pentru a fi rulat si oprint deoarece sistemul de operare a considerat sa aloce timpul CPU pentru alt proces.

Un proces poate avea trei stari distincte:

1) In rulare ( foloseste timpul CPU in acest moment)2) Pregatit (capabil de a fi rulat , dar oprit temporar pentru a permite altui proces sa fie rulat)3) Blocat(incapabil de a fi rulat pana la o interventie externa)

Primele doua stari sunt similare, in ambele cazuri , procesul este rulabil insa doar in al doilea nu se poate intampla acest lucru deoarece procesorul executa un alt proces.O a treia stare este diferita de primele doua pentru ca procesul nu poate fi rulat , chiar daca CPU nu are nimic altceva de facut.

1) Procesul se blocheaza in asteptarea datelor de intrare2) Gestionarul alege un alt proces3) Gestionarul alege acest proces4) Datele de intrare sunt primite

Fig. 1 Un proces poate fi in stare de rulare , blocat , sau pregatit. Tranzitiile intre aceste stari se desfasoara conform graficului.

Asa cum rezulta si din grafic , sunt posibile 4 tranzitii intre aceste stari. Prima tranzitie apare atunci cand sistemul de operare descopera ca un proces nu poate continua in acest moment , iar in unele sisteme acesta poate executa un apel prin care cere intra in pauza sau starea blocata. In UNIX , daca de exemplu un proces citeste dintr-un terminal , si nu exista date de intrare , acesta este blocat automat.

Tranzitiile 2 si 3 sunt cauzate de catre gestionarul de procese , ca parte a sistemului de operare , fara ca

In derulare

1 3 2

Blocat Pregatit 4

procesul sa stie acest lucru. Tranzitia 2 apare atunci cand gestionarul decide ca un proces in derulare si-a epuizat timpul alocat si e nevoie ca alt proces sa fie tratat.Tranzitia 3 apare atunci cand toate celelalte procese au fost tratate partial , si e timpul sa se revina la primul proces.

Tranzitia 4 apare atunci cand un eveniment extern apare , pentru care un alt proces astepta (era in asteptarea datelor de intrare). Daca nici un proces nu este rulat in acest moment se va trece in prin tranzitia a 3-a.

1.1.2 Fire de executie:

In sistemele de operare traditionale , fiecare proces are spatiul sau propriu de adrese si un singur fir pentru control. De fapt , aceasta este aproape definitia unui proces, insa exista situatii frecvente in care este necesar sa existe mai multe fire de control in acelasi spatiu de adrese , care ruleaza in cvasiparalel, ca si cum ar fi fost procese separate ( cu exceptia faptului ca au un spatiu de adrese partajata).

Motivul principal pentru a avea fire este ca in multe aplicatii se intampla multe lucruri simultan. Multe dintre acestea se vor bloca din cand in cand , iar prin descompunerea aplicatiilor in mai multe fire secventiale care ruleaza in cvasiparalel, modelul de programare se simplifica.

Firele de executie aduc un element nou fata de procese, si anume posibilitatea de partajare a unui spatiu de adrese precum si a datelor.Aceasta este o proprietate esentiala pentru diferite aplicatii , astfel folosirea proceselor multiple ( cu spatii de adresa diferite) este ineficient.

Un al doilea argument este faptul ca ele sunt mai simple decat procesele , astfel si crearea si distrugerea lor se manifesta mult mai repede. In multe sisteme crearea unui fir se intampla de 10-100 de ori mai rapid decat crearea unui proces.Atunci cand numarul de fire trebuie modificate rapid si dinamic , aceasta proprietate este esentiala. Trebuie mentionat faptul ca firele de executie sunt extrem de utile in sistemele cu mai multe CPU-uri, unde paralelismul real este posibil.

De exemplu , daca un utilizator doreste sa isi scrie o carte intr-un procesor de documente si doreste sa editeze prin pagina 30 , iar apoi sare la pagina 400 sa mai editeze ceva , procesorul de text trebuie sa reformateze fiecare pagina in parte pana sa afiseze pagina 400. Acest lucru duce la o intarziere mare , pana la afisarea paginii ceea ce ar putea nemultumi utilizatorul. Folosirea firelor de executie ar fi de folos aici , pentru ca daca ar exista un fir pentru reformatare si unul de afisare , tot procesul de prelucrare si afisare ar fi mai rapida. De asemenea s-ar putea adauga un nou fir , pentru salvarea periodica a muncii.

Folosirea a trei procese in loc de fire de executie nu ar fi fezabila pentru ca toate cele trei fire trebuie sa lucreze cu acelasi document. Prin folosirea a trei fire in loc de trei procese , ele partajeaza memoria si astfel au acces la documentul ce trebuie editat.

Un alt exemplu concret este acela al unui server Web care ar fi scris fara fire de executie, sau cu doar un singur fir de executie. Ciclul principal al acestui server primeste o cerere , o studiaza , si o indeplineste inainte de a putea accepta o alta.In timp ce asteapta pentru disc , serverul este latent si nu proceseaza orice alta cerere nou venita.Rezultatul este ca mai putine cereri/secunda pot fi procesate. Astfel prin folosirea firelor, performanta este mult crescuta.

Un fir de executie are un contor de program prin care tine evidenta instructiunilor ce trebuie executata ulterior, are registrii in care stocheaza variabilele de lucru , are o stiva in care stocheaza istoricul executiilor cu un cadru pentru fiecare procedura apelata care insa nu a returnat nici un rezultat. Desi un fir trebuie sa se execute in interiorul unui proces , cele doua sunt concepte diferite si pot fi tratate diferit. Procesele sunt folosite pentru a grupa resursele , iar firele sunt entitati programate pentru a fi executate de CPU.

Firele de executie aduc noutatea pentru modelul proceselor , ca permit executiile multiple independente in interiorul unui proces . Folosirea mai multor fire in interiorul unui proces este aidoma cu existenta mai multor procese ce ruleaza in paralel intr-un calculator. Deoarece firele de executie au proprietati asemanatoare cu cele ale proceselor , acestea sunt numite deseori procese usoare.Termenul multithreading este folosit pentru a descrie situatia in care este permisa alocarea fiecarui fir catre un CPU separat.

Atunci cand avem posibilitatea de multithreading , procesele incep de obicei cu un singur fir . Acest fir are posibilitatea de a crea mai multe fire noi prin apelul unei proceduri de exemplu thread_create. Un parametru al thread_create specifica numele unei proceduri pe care sa o ruleze noul fir.Nu este necesar sa specificam nimic despre spatiul de adrese al noului fir, deoarece acesta ruleaza automat in spatiul de adrese al firului creator.

Atunci cand un fir si-a terminat treaba , acesta poate disparea prin apelul unei functii din librarie , de exemplu thread_exit, astfel nu va mai fi gestionabila.

1.2 Metode de comunicare intre procese:

Frecvent procesele trebuie sa comunice intre ele . De exemplu intr-un pipeline de shell , datele de iesire de la primul proces trebuiesc furnizate catre al doilea proces si tot asa. Asftel aici este necesara o comunicare intre procese , preferabil una structurata astfel incat sa nu se foloseasca intreruperi.

Pe scurt apar trei probleme ce trebuiesc discutate. Prima este legata de modul in care un proces transmite informatia catre un altul, a doua este legata de faptul ca doua sau mai multe procese nu trebuie sa se incurce unele pe altele ( De exemplu daca doua procese vor sa rezerve acelasi ultim bilet de avion pentru doi clienti diferiti).A treia problema mentionabila este legata de secventierea corecta atunci cand avem dependente. Daca procesul A introduce date si procesul B le printeaza , B trebuie sa astepte pana A are niste date pentru printare.

Intr-o perioada de timp un proces poate fi ocupat cu calcule interne sau alte lucruri care nu duc la concurenta intre doua procese. Insa cateodata un proces trebuie sa acceseze memoria partajata sau fisiere , sau sa faca diferite lucruri critice ce pot duce la concurenta. Portiunea programului unde memoria partajata este accesata se numeste regiunea critica . Se incearca aranjarea lucrurilor astfel incat doua procese sa nu fie in regiunile lor critice simultan, pentru a evita concurenta dintre ele.

Desi aceasta conditie previne concurenta intre procese , nu este suficient sa existe procese ce coopereaza corect si eficient folosing memoria partajata . Avem nevoie de patru conditii sa fie indeplinite pentru a avea o solutie buna:

1) Nu pot exista doua procese care sa se afle simultan in regiunile lor critice2) Nu se pot face nici un fel de presupuneri asupra numarului sau vitezei CPU-urilor.3) Nici un proces care nu ruleaza in regiunea sa critica nu poate bloca un alt proces4) Nici un proces nu poate astepta la infinit pentru a intra in regiunea sa critica.

1.2.1 Pipe-uri:

Asa numitele pipe-uri permit ca doua procese distincte sa comunice intre ele. Ele sunt numite si FIFO-uri si pot fi folosite pentru stabilirea unei comunicatii unidirectionale (half-duplex)

Pipe-urile sunt identificate prin punctul lor de acces , adica un fisier din sistemul de fisiere. Deoarece pipe-urile cu nume au calea unui fisier asociat cu ele , este posibil ca doua procese neasociate sa comunice intre ele; Cu alte cuvinte , doua procese neinrudite pot deschide fisierul asociat pipe-urilor si sa initieze comunicatia. Spre deosebire de pipe-urile anonime , care sunt procese ce insista pe obiecte , pipe-urile denumite sunt obiecte persistente in sistem, si exista chiar dupa terminarea procesului. Acestea trebuie sterse explicit de catre un proces , prin apelul de “unlink” sau sterse din sistemul de fisiere prin linia de comanda.

Pentru a comunica prin pipe-uri denumite , procesele trebuie sa incarce fisierul asociat cu pipe-ul respectiv. Prin deschiderea fisierului respectiv pentru a fi citit , un proces are acces prin citirea capatului pipe-ului si prin deschiderea fisierului de scris , procesul avand acces la capatul de scriere a pipe-ului.

Un pipe numit suporta operatii de blocare a scrierii si citirii : De exemplu , daca un proces deschide un fisier pentru citire , acesta este blocat de un alt proces care deschide fisierul pentru scriere, si invers. Insa , este posibil sa creem pipe-uri numite care suporta ne-blocarea operatiilor prin specificarea fanionului O_NONBLOCK in timpul deschiderii lor. Un pipe numit trebuie deschis in modul scriere sau citire exclusiva. El nu poate fi deschis in modul scriere/citire simultana datorita faptului ca este half-duplex, adica un canal unidirectional.

Exemplu de creare a unui pipe din linia de comanda:

% mknod npipe p

sau

% mkfifo npipe

De asemenea se pot specifica caile absolute ale pipe-ului numit , ce trebuie creat.Daca se observa fisierul cu ajutorul comenzii ls ?| vom primi urmatorul raspuns:

prw-rw-r-- 1 secf other 0 Jun 6 17:35 npipe

Caracterul p din prima coloana denota faptul ca este un pipe denumit. La fel ca in orice sistem de fisiere , acesta are permisiuni care definesc modul in care utilizatorii pot accesa un pipe denumit, daca pot scrie , citi sau ambele .

Citirea si scrierea intr-un Pipe:

Citirea sau scrierea intr-un pipe este foarte similara cu citirea sau scrierea intr-un fisier normal. Functiile standard ale librariilor C read() si write() pot fi folosite pentru scrierea si citirea dintr-un pipe.

Beneficii ale utilizarii Pipe-urilor denumite:

• sunt foarte usor de utilizat.

• mkfifo este o functie nedaunatoare firelor de executie• nu avem nevoie de un mecanism de sincronizare pentru pipe-uri denumite• scrierea intr-un pipe este foarte precisa, chiar si atunci cand pipe-ul este deschis in starea fara

blocare.• pipe-urile numite au permisiuni de scriere si citire asociate , spre deosebire de pipe-urile

anonime. Aceste permisiuni pot fi impuse pentru comunicatii securizate.

Limitatii ale pipe-urilor denumite:

• pipe-urile denumite pot fi folosite doar pentru comunicatia intre procese de pe acelasi calculator

• pipe-urile denumite pot fi create doar de catre sistemul de fisiere local, si nu se pot crea pe sistemul de fisiere NFS.

• datorita naturii lor de blocare , este necesara de o programare riguroasa pentru client si server , in vederea evitarii incurcaturilor.

• pipe-urile denumite este un flux de octeti , insa nu au nici un identificator.

1.2.2 Semnale:

Semnalele sunt un mod de trimitere a mesajelor simple catre procese. Majoritatea acestor procese au fost definite deja . Insa , semnalele pot fi procesate atunci cand procesul este in modul utilizator.

Daca un semnal este trimis unui proces aflat in modul kernel , acesta este tratat dupa revenirea la modul de utilizator.

Semnalele sunt cea mai veche metoda de comunicare intre procese folosita de sistemele UNIX. Acestea sunt folosite pentru a semnala evenimente asincrone unui sau mai multor procese . Un semnal poate fi generat de o intrerupere de la tastatura cum ar fi o conditie de eroare cauzata de un proces ce face referire la un spatiu de memorie inexistent in memoria sa virtuala. Semnalele sunt folosite de catre sistemele de operare pentru a semnaliza comenzile de control catre descendentii proceselor.

Exista un set fix de semnale definite pe care kernelul le poate genera sau care pot fi generate de catre alte procese din sistem , daca au privilegiile necesare.La o listare a acestor semnale cu ajutorul comenzii kill -l puteti observa :

1)SIGHUP 2) SIGINT 3) SIGQUIT 1) SIGILL 5) SIGTRA 6) SIGIOT 1) SIGBUS 8) SIGFPE 9) SIGKILL10) SIGUSR1 11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM17) SIGCHLD 18) SIGCONT 19) SIGSTOP20) SIGTSTP 21) SIGTTIN 22) SIGTTOU23) SIGURG 24) SIGXCPU 25) SIGXFSZ 26) SIGVTALRM 27) SIGPROF 28) SIGWINCH27) 29) SIGIO 30) SIGPWR

Procesele pot alege sa ignore majoritatea semnalelor generate , cu doua exceptii importante: nici SigStop care obliga procesul sa se opreasca sau Sigkill care obliga semnalul sa termine , nu pot fi ignorate. In caz contrar un proces poate alege cum doreste sa interpreteze diferite semnale. Procesele pot bloca diferite semnale , si daca nu le blocheaza pot alege sa le trateze ele insile sau kernelul. Daca kernelul trateaza aceste semnale , el va adopta actiunea generica cand un proces primeste Sigfpe va initializa o copie de siguranta si va iesi. Semnalele nu au prioritati relative . Daca doua semnale sunt generate pentru un proces in acelasi timp , atunci el le poate trata in orice ordine. De asemenea , nu exista nici un mecanisc de distinctie prin care procesul sa isi dea seama daca daca a primit unu sau mai multe semnale de acelasi fel.

Semnalele nu sunt prezentate procesului imediat dupa generare , in schimb ele trebuie sa astepte pana cand procesul va rula inca o data . De fiecare data cand un proces termina printr-un apel de sistem , campurile de signal si blocked sunt verificate , si daca exista semnale deblocate , ele pot fi acum transferate. Aceasta metoda poate parea ca una ineficienta deoarece ea depinde de faptul ca procesele verifica semnalele , insa fiecare proces din sistem face apeluri la sistem , de exemplu pentru a scrie un caracter in terminal , tot timpul. Procesele pot alege sa astepte semnale daca vor , si sunt suspendate intr-o stare neintreruptibila pana semnalul dorit soseste. Procesorul de semnale din linux studiaza structura sigaction pentru fiecare dintre semnalele deblocate.

Multe semnale ( la fel ca semnalul 9 SIGKILL ) au posibilitatea de terminare imediata a procesului, insa multe din aceste semnale pot fi ignorate sau tratate de catre proces.Daca nu se intampla asa , kernelul va lua masura implicita pentru acel semnal. Utilizatorul poate trimite semnale proceselor prin comanda kill, sau ctrl+alt+delete in Windows. Insa , el poate trimite semnale proceselor pe care le detine, in cazul in care nu are drepturi depline.

Este posibil ca procesul caruia i se trimite semnalul sa fie in stare latenta , iar daca el este intr-o stare cu prioritate intreruptibila , el este trezit la viata pentru a reactiona la semnal.

Kernelul urmareste toate semnalele in asteptare intr-o structura de procese.Aceasta este o valoare de 32 de biti in care fiecare bit reprezinta un semnal singular.Deoarece exista doar un singur bit/semnal , pot exista doar cate un semnal din fiecare fel. Daca exista mai multe semnale de tipuri diferite in asteptare , kernelul nu poate stabili ordinea de sosire a lor , astfel prioritatea de procesare a semnalelor este crescatoare corespunzator numarului semnalului.

Vutan Gheorghe Adrian (433 A)

1.3 Mecanisme de sincronizare

Introducere

Pentru sincronizarea firelor de execuție avem la dispoziție:

secțiuni critice (excludere mutuală în cadrul aceluiași proces) – doar Win32 mutex: POSIX, Win32 semafoare: POSIX, Win32 variabile de condiție: POSIX, Win32 (începând cu Vista)

evenimente: doar Win32 timere: doar Win32.

Standardul POSIX specifică funcții de sincronizare pentru fiecare tip de obiect de sincronizare. API-ul Win32, fiind controlat de o singură entitate, permite ca toate obiectele de sincronizare să poată fi utilizate cu funcțiile standard de sincronizare: WaitForSingleObject, WaitForMultipleObjects sau SignalObjectAndWait.

Mecanismele de sincronizare oferite de sistemul de operare Windows sunt mai multe şi mai complexe decât cele din Linux. Pentru sincronizare sunt necesare:

unul sau mai multe obiecte de sincronizare (Synchronization Objects) o funcţie de aşteptare (Wait Functions).

1.3.1 Semafoare POSIX

Semafoarele sunt resurse IPC folosite pentru sincronizarea între procese (e.g. pentru controlul accesului la resurse). Operaţiile asupra unui semafor pot fi de setare sau verificare a valorii (care poate fi mai mare sau egala cu 0) sau de test and set. Un semafor poate fi privit ca un contor ce poate fi incrementat şi decrementat, dar a cărui valoare nu poate scădea sub 0.

Semafoarele POSIX sunt de 2 tipuri: cu nume, folosite în general pentru sincronizare intre procese distincte; fără nume (bazate pe memorie), ce pot fi folosite doar pentru sincronizarea între firele de

execuţie ale unui proces.

În continuare vor fi luate în discuție semafoarele cu nume. Diferențele față de cele bazată pe memorie constă în funcțiile de creare și distrugere, celelalte funcții fiind identice. ambele tipuri de semafoare sunt reprezentate în cod prin tipul sem_t.semafoarele cu nume sunt idenficate la nivel de sistem printr-un şir de forma ”/nume”.fişierele antet necesare sunt <fcntl.h>, <sys/types.h> şi <semaphore.h>.

Operațiile care pot fi efectuate asupra semafoarelor POSIX sunt:

/* SEMAFOARE CU NUME */

// deschiderea unui semafor identificat prin nume. // folosit pentru a sincroniza procese diferitesem_t* sem_open(const char *name, int oflag);sem_t* sem_open(const char *name, int oflag, mode_t mode, unsigned int value);

// închiderea unui semafor cu numeint sem_close(sem_t *sem);

// stergerea din sistem a unui semafor cu numeint sem_unlink(const char *name);

/* SEMAFOARE FARA NUME */

/** initializarea unui semafor fara nume * sem - semaforul nou creat * pshared - 0 daca semaforul nu este partajat decat de firele de executie ale procesului curent - non zero: semafor partajat cu alte procese in acest caz 'sem' trebuie alocat intr-o zona de memorie partajata * value - valoarea initiala a semaforului */int sem_init(sem_t *sem, int pshared, unsigned int value);

// distrugerea unui semafor fara numeint sem_destroy(sem_t *sem);

/* OPERATII PE SEMAFOARE */

// incrementarea (V) int sem_post(sem_t *sem);

// decrementarea blocantă (P)int sem_wait(sem_t *sem);

// decrementarea neblocantăint sem_trywait(sem_t *sem);

// citirea valoriiint sem_getvalue(sem_t *sem, int *pvalue);

Operaţii:

down decrementează un semafor doar dacă valoarea lui este strict mai mare decât 0 dacă semaforul are valoarea 0, atunci procesul se blochează (intră în sleep)

up incrementează valoarea unui semafor dacă unul sau mai multe procese sunt blocate pe respectivul semafor (nu au putut continua o operaţie down anterioară pe semafor cu valoarea 0), se va debloca unul dintre ele, pentru a-şi încheia operaţia down operaţia up nu poate bloca un proces

Operaţiile iniţiate asupra unui semafor sunt indivizibile Problema producător-consumator rezolvată cu ajutorul a trei semafoare:

semaforul full numără poziţiile ocupate din buffer semaforul empty contorizează poziţiile libere din buffer

semaforul mutex ce împiedică accesul simultan la buffer (excluderea mutuală)

Iniţial: full = 0, empty = N (dimensiunea bufferului) şi mutex=1

a) empty = 0; full = N; mutex = 1 şi se execută producer( )

b) empty = N; full = 0; mutex = 1 şi se execută consumer( )

c) empty != 0; full != 0; mutex = 1 şi cele două procese încearcă să intre simultan în SC

full nu permite consumatorului să extragă informaţii din buffer dacă acesta este gol, empty nu permite producătorului să introducă informaţii în buffer dacă el este plin, iar mutex nu permite celor două procese să acceseze simultan bufferul (excludere mutuală) #define N 100 /* number of slots in the buffer*/

typedef int semaphore; /* semaphores are a special kind of int */

semaphore mutex = 1; /* controls access to critical region */

semaphore empty = N; /* counts empty buffer slots */ semaphore full = 0; /* counts full buffer slots */ void producer(void) { int item; while (TRUE) { /* infinite loop */

item = produce_item(); /* generate something to put in buffer */ down(&empty); /* decrement empty count */ down(&mutex); /* enter critical region */ insert_item(item); /* put new item in buffer – Crit. Sect.*/ up(&mutex); /* leave critical region */ up(&full); /* increment count of full slots */ } } void consumer(void) { int item; while (TRUE) { /* infinite loop */ down(&full); /* decrement full count */ down(&mutex); /* enter critical region */ item = remove_item(); /* take item from buffer – Crit. Sect.*/ up(&mutex); /* leave critical region */ up(&empty); /* increment count of empty slots */ consume_item(item); /* do something with the item */ } }

Procesul producer se va bloca pe instrucţiunea down(&empty) deoarece empty = 0. Deblocarea procesului va avea loc abia după ce procesul consumer va executa

instrucţiunea up(&empty).

Semafoare(Win32)Un semafor (semaphore) este un obiect de sincronizare care are intern un contor ce ia

doar valori pozitive. Atât timp cât semaforul (contorul) are valori strict pozitive el este considerat disponibil (signaled). Când valoarea semaforului a ajuns la zero el devine indisponibil

(nonsignaled) şi următoarea încercare de decrementare va duce la o blocare a threadului de pe care s-a făcut apelul (şi a procesului, dacă acesta foloseşte un singur thread) până când semaforul devine disponibil.

Operaţia de decrementare se realizează doar cu o singură unitate (la fel ca în API-ul POSIX, dar spre deosebire de API-ul SysV unde se poate face decrementarea atomică a unui semafor cu mai multe unităţi o dată), în timp ce incrementarea se poate realiza cu orice valoare în limita maximă.

Crearea şi deschiderea

Funcţia de creare a semafoarelor este CreateSemaphore şi are sintaxa :

HANDLE CreateSemaphore(

LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,

LONG lInitialCount,

LONG lMaximumCount,

LPCTSTR lpNAME

);

Se observă că funcţia se poate folosi şi pentru deschiderea unui semafor deja existent.

Alternativ, pentru a folosi un semafor deja existent este necesară obţinerea HANDLE-ului semaforului, operaţie ce se realizează folosind funcţia OpenSemaphore cu următoarea sintaxă :

HANDLE OpenSemaphore(

DWORD dwDesiredAccess,

BOOL bInheritHandle,

LPCTSTR lpNAME

);

Decrementarea/aşteptarea şi incrementarea

Operaţia de decrementare a semaforului cu sau fără aşteptare se realizează folosind una din funcţiile de aşteptare. Cea mai des folosită este funcţia WaitForSingleObject.

Incrementarea semaforului se realizează folosind funcţia ReleaseSemaphore cu sintaxa :

BOOL ReleaseSemaphore(

HANDLE hSemaphore,

LONG lReleaseCount,

LPLONG lpPreviousCount

);

Distrugerea

Operaţia de distrugere a unui semafor este similară cu cea de distrugere a unui mutex. Se foloseşte funcţia CloseHandle. După ce toate HANDLE-urile unui semafor au fost închise, semaforul este distrus şi resursele ocupate de acesta eliberate.

1.3.2 Mutex-uriUn mutex este un obiect de sincronizare care poate fi deţinut (posedat, acaparat) doar de un

singur proces (sau thread) la un moment dat. Drept urmare, operaţiile de baza cu mutex-uri sunt cele de obţinere şi de eliberare.

Odatǎ obţinut de un proces, un mutex devine indisponibil pentru orice alt proces. Orice proces care încearcǎ sǎ acapareze un mutex indisponibil, se va bloca (un timp definit sau nu) aşteptând ca el sǎ devinǎ disponibil.

Mutex-urile sunt cel mai des folosite pentru a permite unui singur proces la un moment dat sǎ acceseze o resursǎ.

În continuare vor fi prezentate operaţiile cu mutex-uri.

Crearea/deschiderea sunt operaţii prin care se pregǎteşte un mutex. Dupǎ cum am mai spus, pentru a opera cu orice obiect de sincronizare este necesar un HANDLE al acelui obiect. Scopul funcţiei de creare şi a celei de deschidere este acela de a obţine un HANDLE al obiectului mutex. Prin urmare, este necesar doar un singur apel, fie el de creare sau de deschidere (se presupune ca alt proces a creat deja mutex-ul). Acest apel este efectuat o singura datǎ la iniţializare; odatǎ ce avem HANDLE-ul putem obţine/elibera mutex-ul ori de câte ori avem nevoie.

Pentru a crea un mutex se foloseşte funcţia CreateMutex cu sintaxa :

HANDLE CreateMutex(

LPSECURITY_ATTRIBUTES lpMutexAttributes,

BOOL bInitialOwner,

LPCTSTR lpName

);

Pentru a deschide un mutex deja existent este definită funcţia OpenMutex cu sintaxa :

HANDLE OpenMutex(

DWORD dwDesiredAccess,

BOOL bInheritHandle,

LPCTSTR lpName

);

Încercarea de acaparare a unui mutex presupune următorii paşi :

verificarea daca mutex-ul este disponibil? daca da, îl pot acapara şi devine indisponibil, şi funcţia întoarce succes daca nu, aştept să devină disponibil, după care îl acaparez, şi funcţia întoarce succes la time-out funcţia întoarce eroare (atenţie! e posibil să nu existe time-out)

Încercarea de obţinere se poate face cu sau fară timp de expirare (time-out) în funcţie de parametrii daţi funcţiilor de aşteptare. Cea mai des folosită funcţie de aşteptare este WaitForSingleObject.

Folosind funcţia ReleaseMutex se cedează posesia mutex-ului, el devenind iar disponibil. Funcţia are următoarea sintaxa :

BOOL ReleaseMutex(

HANDLE hMutex

);

Funcţia va eşua dacă procesul nu deţine mutex-ul.

Atenţie pentru a putea folosi această funcţie HANDLE-ul trebuie să aibă dreptul de acces MUTEX_MODIFY_STATE.

Operaţia de distrugere a unui mutex este aceeaşi ca pentru orice HANDLE. Se foloseşte funcţia CloseHandle. După ce toate HANDLE-urile unui mutex au fost închise, mutexul este distrus şi resursele ocupate de acesta eliberate.

Atenţie La terminarea execuţiei unui program toate HANDLE-urile folosite de acesta sunt automat închise. Deci spre deosebire de semafoarele IPC din Linux, este imposibil ca un mutex (sau semafor) în Windows să mai existe în sistem după ce programele care l-au folosit/creat s-au terminat.

1.3.3 Evenimente

Evenimentele sunt obiecte de sincronizare al caror statut poate fi explicitat prin utilizarea functiei SetEvent.

Exista 2 tipuri de evenimente:

Cu resetare manuala: Un obiect eveniment a carui stare ramane “semnalizat” pana cand este resetat in mod explicit ca nesemnalizat prin utilizarea functiei ResetEvent. Deşi este semnalat, orice număr de fire de aşteptare, sau fire care specifică ulterior obiectul aceluiaşi eveniment într-una din funcţiile de aşteptare , acestea pot fi eliberate.

Cu resetare automata: Un obiect eveniment a cărei stare rămâne “semnalat” pana cand un singur fir de aşteptare este eliberat, moment în care sistemul seteaza automat starea acestuia nesemnalat. Dacă nu sunt fire de aşteptare, starea obiectului eveniment rămâne semnalat. Dacă mai mult de un fir este în aşteptare, un fir de aşteptare este selectat. Nu presupune un primul-intrat, primul-ieşit (FIFO). Evenimentele externe, cum ar fi TAB-uri de kernel-mode pot schimba ordinea aşteptarii.

Obiectul Eveniment este util în a trimite un semnal pe un fir care să indice că un anumit eveniment a avut loc. De exemplu, în suprapunerea de intrare şi de ieşire, sistemul stabileşte un anumit obiect eveniment la starea semnalat atunci când operaţiunea de suprapunere a fost finalizata. Un singur fir poate specificaobiecte eveniment diferite în mai multe operaţiuni simultane de suprapunere, apoi utilizaţi una dintre funcţiile de aşteptare pentru ca starea unuia dintre obiectele eveniment să fie semnalate.

Un fir utilizează CreateEvent sau CreateEventExpentru a crea un obiect eveniment. Firul creat specifică starea iniţială a obiectului şi dacă acesta este un obiecteveniment cu resetare manuala sau un obiect eveniment auto-resetare.

1.3.4 Secțiune critică

În Windows mai există un mecanism de sincronizare care este disponibil doar pentru firele de execuție ale aceluiași proces, și anume CriticalSection. Se recomandă folosirea CriticalSection pentru excluderea mutuală a firelor de execuție ale aceluiași proces, fiind mai eficient decât Mutex sau Semaphore.

Obiectele CriticalSection sunt echivalente mutexurilor POSIX de tip RECURSIVE. Obiectele CriticalSection sunt folosite pentru excluderea mutuală a accesului firelor de execuție ale aceluiași proces la o secțiune critică de cod care conține operații asupra unor date partajate. Un singur fir de execuție va fi activ la un moment dat în interiorul secțiunii critice, și dacă mai multe fire așteaptă să intre, nu este garantată ordinea lor de intrare, totuși sistemul va fi echitabil față de toate.

Operațiile care se pot efectua asupra unei secțiuni critice sunt: intrarea, intrarea neblocantă, ieșirea din secțiunea critică, inițializarea și distrugerea.

Pentru serializarea accesului la o secțiune de cod critică, fiecare fir de execuție va trebui să intre într-un obiect CriticalSection la începutul secțiunii și să-l părăsească la sfârșitul ei. În acest fel, dacă două fire de execuție încearcă să intre în CriticalSection simultan, doar unul dintre ele va reuși, și își va continua execuția în interiorul secțiunii critice, iar celălalt se va bloca pînă când obiectul CriticalSection va fi părăsit de primul fir. Așadar, la sfârșitul secțiunii, primul fir trebuie să părăsească obiectul CriticalSection, permițându-i celuilalt intrarea.

Pentru excluderea mutuală se pot folosi atât obiecte Mutex, cât și obiecte CriticalSection; dacă sincronizarea trebuie făcută doar între firele de execuție ale aceluiași proces este recomandată folosirea CriticalSection, fiind mai un mecanism mai eficient. Operația de intrare în CriticalSection se traduce într-o singură instrucțiune de asamblare de tip test-and-set-lock (TSL). CriticalSection este echivalentul futex-ului din Linux.

Inițializarea/distrugerea unei secțiuni critice

Alocarea memoriei pentru o secțiune critică se face prin declararea unui obiect CRITICAL_SECTION. Acesta nu va putea fi folosit, totuși, înainte de a fi inițializat.

// initializează o secțiune critică cu un contor de spin implicit = 0void InitializeCriticalSection(LPCRITICAL_SECTION pcrit_sect); // permite specificarea contorului de spinBOOL InitializeCriticalSectionAndSpinCount(LPCRITICAL_SECTION pcrit_sect, DWORD dwSpinCount); // modifică contorul de spin al unei secțiuni criticeDWORD SetCriticalSectionSpinCount(LPCRITICAL_SECTION pcrit_sect, DWORD dwSpinCount);

// distrugerea unei secțiuni criticevoid DeleteCriticalSection(LPCRITICAL_SECTION pcrit_sect);

Un obiect CRITICAL_SECTION nu poate fi copiat ori modificat după inițializare. De asemenea, un obiect CRITICAL_SECTION nu trebuie inițializat de două ori, în caz contrar, comportamentul său fiind nedefinit.

Contorul de spin are sens doar pe sistemele multiprocesor (SMP) (este ignorat pe sisteme uniprocesor). Contorul de spin reprezintă numărul de cicli pe care îi petrece un fir de execuție pe un procesor în busy-waiting, înainte de a-și suspenda execuția la un semafor asociat secțiunii critice, în așteptarea eliberării acesteia. Scopul așteptării unui număr de cicli în busy-waiting este evitarea blocării la semafor în cazul în care secțiunea critică se eliberează în intervalul respectiv, deoarece blocarea la semafor are impact asupra performanțelor. Folosirea contorului de spin este recomandată mai ales în cazul unei secțiuni critice scurte, accesate foarte des.

Utilizarea secțiunilor critice

Secțiunile critice Windows au comportamentul mutex-urilor POSIX de tip RECURSIVE. Un fir de execuție care se află deja în secțiunea critică nu se va bloca dacă apelează din nou EnterCriticalSection, însă va trebui să părăsească secțiunea critică de un număr de ori egal cu cel al ocupărilor, pentru a o elibera.

// similar cu pthread_mutex_lock() pentru mutexuri RECURSIVEvoid EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);// similar cu pthread_mutex_unlock() pentru mutexuri RECURSIVEvoid LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);// pentru a folosi TryEnterCriticalSection trebuie definit// _WIN32_WINNT >= 0x0400 înainte de a include prima dată

<windows.h>#define _WIN32_WINNT 0x0400#include <windows.h>// similar cu pthread_mutex_trylock() pentru mutexuri RECURSIVE// - întoarce FALSE (=0) dacă secțiunea critică este ocupată de

alt// fir de execuție și NU blochează firul curent de execuție// - întoarce o valoarea nenulă dacă secțiunea critică era liberă // sau ocupată tot de acest fir de execuțieBOOL TryEnterCriticalSection(LPCRITICAL_SECTION

lpCriticalSection);

În cadrul unui fir de execuție, numărul apelurilor LeaveCriticalSection trebuie să fie egal cu numărul apelurilor EnterCriticalSection, pentru a elibera în final secțiunea critică. Dacă un fir de execuție care nu a intrat în secțiunea critică apelează LeaveCriticalSection, se va produce o eroare care va face ca firele care au apelat EnterCriticalSection să aștepte pentru o perioadă nedefinită de timp.

1.3.5 Variabila de condițieVariabilele 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

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 DeadlockUn 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:a) Excludere mutuală: fiecare resursă este deţinută de cel mult

un procesb) “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ăsuri2) Se evită dinamic deadlock-ul prin alocarea cu atenţie a resurselor3) Se previne apariţia deadlock-ului prin negarea la nivel structural a uneia din cele 4 condiţii de deadlock4) 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 individualeDeadlock-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

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

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 ConditionSituaţ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

1.Procese automate

Procesele automate sau batch-urile nu sunt conectate către un terminal.Mai degrabă acestea sunt task-uri care pot fi puse într-o coadă de aşteptare în care îşi aşteaptă execuţia într-o ordine FIFO.Asemenea task-uri pot fi executate folosind una din următoarele criterii:

*La o anumită dată şi oră folosind comanda at.

*La perioade în care încărcarea sistemului este suficient de joasă pentru a accepta job-uri extra utilizând comanda batch.În mod implicit , sarcinile sunt puse într-o coadă de aşteptare până când încărcarea sistemului este mai joasă decât 0.8.

În medii mari, administratorul de sistem preferă prelucrarea pe loturi când cantităţi mari de date trebuiesc procesate sau când task-urile solicită multe resurse de sistem pe un sistem destul de încărcat.Prelucrarea pe loturi este totodată utilizat pentru opitimizarea performanţelor sistemului.

2.Daemon-urile

Daemonii sunt procese de tip server care rulează continuu.În majoritatea cazurilor ele sunt iniţializate la pornirea sistemului şi aşteaptă în background până când serviciul lor este solicitat.

3.Procesele interactive

Acestea sunt iniţializate şi controlate printr-o sesiune de terminal.Cu alte cuvinte trebuie să existe cineva conectat la sistem pentru a porni aceste procese.Nu sunt pornit automat şi nu fac parte din funcţiile sistemului.Aceste procese pot rula în prim plan , ocupând terminalul care a pornit programul şi nu poţi porni alte aplicaţii atâta timp cât aceste procese rulează în prim plan.

Controlul proceselor

(parte din) comandă Semnificaţie

regular_command Rulează această comandă în prim plan

command & Rulează această comandă în plan secundar

Jobs Arată procesele/comenzile ce rulează în background

Ctrl+Z Suspendă(stopează,dar nu termină) un proces care rulează în prim plan.

Ctrl+C Intrerupe(termină şi renunţă) un proces ce rulează în prim plan

%n Fiecare proces ce se exxecută în plan secundar primeşte un număr

asociat cu acesta.Utilizând % putem să ne referim la job folosind nr.

bg Reactivează un program suspendat din background

fg Pune jobul înapoi în prim plan.

Kill Termină un process

Crearea proceselor

Un nou proces este creat , deoarece un proces existent creează o copie a acestuia.Acest proces-copil (child process) prezintă acelaşi mediu ca al părintelui , doar ID-ul procesului este diferit.Această procedură poartă numele de bifurcare din englezul forking.

Dupa procesul de forking , spaţiul adresă a procesului copil este suprascris cu data noului proces.Aceasta se face printr-un apel exec la sistem.Mecanismul fork-şi-exec comută o veche comandă cu una nouă , în timp ce mediul în care noul program se execută rămâne acelaşi , incluzând configuraţia dispozitivelor de intrare şi ieşire , variabilele de mediu si priorităţile.Acest mecanism este folosit pentru a crea toate procesele UNIX , prin urmare se aplică tuturor sistemelor de operare linux.Chiar primul proces , init , cu ID-ul de 1 , este bifurcat în timpul procedurii de boot.

Mecanismul fork-şi-exec este ilustrat în următoarea schemă. Se observă că ID-ul procesului se schimbă după procedura de fork :

Există câteva situaţii când procesul init devine procesul părinte al unui proces din cadrul unui sistem chiar daca acesta nu a fost iniţializat de el.Multe programe , de exemplu, transformă procesele lor in procese de tip daemon astfel încât să poată continua să ruleze când procesul părinte îşi încetează activitatea sau este oprit din rulare.De exemplu cazul unui window manager.Porneşte un proces xterm care generează un shell ce acceptă comenzi.Astfel procesul este pasat câtre procesul init în felul acesta window managerul respinge orice fel de responsabilitate asupra procesului.În urma acestui mecanism este posibil să schimbăm window manager-ul fără a întrerupe aplicaţiile care rulează.

Terminarea proceselor

Atunci când un proces se termină în mod normal (nu este afectat de comanda kill sau interupt) programul returnează părintelui exit status-ul.Exit status-ul este un număr returnat de program oferind rezultatul execuţiei unui program.Acest sistem îşi are originea din limbajul de programare C în cadrul căreia UNIX-ul a fost scris.

Codurile returnate pot fi interpretate de părinte sau în scripturi.Valorile acestea sunt specifice fiecărui program.Această informaţie poate fi găsită de obicei în paginile man al unui

program specific., de exemplu comanda grep returnează -1 dacă nu au fost găsite nici un rezultat astfel putând fi afişat mesajul “No files found”.

Semnale

Procesele sfârşesc deoarece primesc un semnal.Există multiple semnale ce pot fi transmise unui proces.Comanda kill –l afişează o listă de semnale.Majoritatea semnalelor sunt pentru uz intern pentru sistem sau pentru programatori când scriu cod.Ca user , îţi vor trebui următoarele semnale :

Numele semnalului

Numărul semnalului

Semnificaţia

SIGTERM 15 Termină procesul într-un mod ordonat

SIGINT 2 Întrerupe procesul.Un proces poate ignora acest semnal

SIGKILL 9 Înterupe procesul.Un proces nu poate ignora acest semnal

SIGHUP 1 Semnal specific daemon-urilor.

Atributele procesului

Cu ajutorul comenzii ps pot fi vizualizate caracteristicile unui proces .

ID-ul procesului sau PID – reprezintă un număr unic de identificare care se referă la proces.Acel număr identifica procesul în sistem.

ID-ul procesului părinte sau PPID : numărul procesului (PID) care a determinat startul acestui proces.

Numărul ‘nice’ – gradul de prietenie al acestui proces referitor la alte procese ( a nu fi confundat cu prioritatea procesului , care este calculat bazat pe numărul ‘nice’ şi gradul de folosinţă CPU recentă a procesului).

Terminal sau TTY: terminalul la care este conectat procesul în sine.

Numele utilizatorului real şi utilizatorului efectiv (RUID şi EUID) : proprietarul procesului .Proprietarul real este userul care emite comanda , userul efectiv este cel care determină accesul la resursele sistemului.

RUID şi EUID sunt de obicei aceleaşi , şi procesul are aceleaşi drepturi de acces ca userului emitent .

Pentru a clarifica acest aspect explicăm următorul exemplu.

theo:~> ls -l /usr/bin/mozilla-rwxr-xr-x 1 root root 4996 Nov 20 18:28 /usr/bin/mozilla*

theo:~> mozilla &[1] 26595

theo:~> ps -afUID PID PPID C STIME TTY TIME CMDtheo 26601 26599 0 15:04 pts/5 00:00:00 /usr/lib/mozilla/mozilla-bintheo 26613 26569 0 15:04 pts/5 00:00:00 ps -af

Browser-ul mozilla din /usr/bin este deţinut de user-ul root.Când user-ul theo porneşte acest program , procesul în sine şi toate procesele pornite de către procesul iniţial , vor fi deţinute de user-ul theo şi nu de administratorul de sistem.Când mozilla necesită acces la anumite fişiere , acel acces va fi determinat de permisiunile lui theo si nu cele ale root-ului.

Proprietarul real şi cel efectiv al grupului (RGID şi EGID):Proprietarul grupului real al unui proces este grupul primar al utilizatorului care a pornit procesul.Proprietarul efectiv al grupului este de obicei acelaşi , exceptând atunci când modul de acces SGID a fost aplicat unui fişier.

De observat e că ps oferă un statu momentan al proceselor active , este o înregistrare la un singur moment de timp.Programul top afişează o imagine mult mai precisă prin actualizarea rezultatelor oferite de ps (cu o grămadă de opţiuni) , o dată la fiecare 5 secunde , generând o nouă listă de procese .

12:40pm up 9 days, 6:00, 4 users, load average: 0.21, 0.11, 0.0389 processes: 86 sleeping, 3 running, 0 zombie, 0 stoppedCPU states: 2.5% user, 1.7% system, 0.0% nice, 95.6% idleMem: 255120K av, 239412K used, 15708K free, 756K shrd, 22620K buffSwap: 1050176K av, 76428K used, 973748K free, 82756K cached

PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 5005 root 14 0 91572 15M 11580 R 1.9 6.0 7:53 X19599 jeff 14 0 1024 1024 796 R 1.1 0.4 0:01 top19100 jeff 9 0 5288 4948 3888 R 0.5 1.9 0:24 gnome-terminal19328 jeff 9 0 37884 36M 14724 S 0.5 14.8 1:30 mozilla-bin 1 root 8 0 516 472 464 S 0.0 0.1 0:06 init 2 root 9 0 0 0 0 SW 0.0 0.0 0:02 keventd 3 root 9 0 0 0 0 SW 0.0 0.0 0:00 kapm-idled 4 root 19 19 0 0 0 SWN 0.0 0.0 0:00 ksoftirqd_CPU0 5 root 9 0 0 0 0 SW 0.0 0.0 0:33 kswapd 6 root 9 0 0 0 0 SW 0.0 0.0 0:00 kreclaimd 7 root 9 0 0 0 0 SW 0.0 0.0 0:00 bdflush

2. Algoritmi de gestiune de procese si de fire de executie

2.1 Algoritmi de alocare a timpului de procesor

Andrei Stefanescu (433 A)

2.1.1 Algoritmi “standard”

2.1.1.1 Round-Robin (Ordonare circulara)

Este algoritmul cel mai vechi, cel mai simplu si cel mai fiabil. El nu este insă utilizabil in nucleele de timp real. Se studiaza doar pentru ca pune in evidenta problemele care apar in medii de timp real.

Fiecare task poseda o cuanta de timp, pe perioada careia el este autorizat sa ocupe procesorul. Cand cuanta se scurge, procesorul este rechizitionat si alocat altui task din coada. Daca taskul se termina inaintea sfarsitului cuantei sale, timpul ramas este alocat altui task. Atunci cand sistemul cuprinde procese cu frecventa mica sau cu probabilitatea mare de a se bloca, puterea procesorului este atribuita aproape in intregime taskului in executie. In caz contrar, daca sistemul are procese efectuand putine intrari/iesiri, puterea procesorului se imparte la numarul de taskuri prezente in coada.

Este asemănător cu algoritmul F.C.F.S (First Come First Served) dar procesul curent poate fi întrerupt oricând de către S.O. dacă ii expiră cuanta de timp).

2.1.1.2 Shortest job first

Algoritmul măsoară durata rafalei de instrucţiuni pentru fiecare proces şi încearcă să promoveze pe procesor procesele cu cea mai scurtă rafală. Poate fi şi preemptiv (procesul curent poate fi întrerupt oricând de către S.O. , dacă ii expiră cuanta de timp) şi nepreemptiv (procesul nu poate fi întrerupt oricând de către S.O., acesta cedează controlul de bunăvoie la terminarea rafalei de instrucţiuni sau la intrarea in zona de aşteptare; in cazul unor erori, un proces poate bloca întregul S.O.). Dar in mare parte este nepreemptiv

Duratele de execuţie a proceselor sunt cunoscute în avans si dacă mai multe procese sunt “gata de execuţie” simultan, planificatorul alege (pentru a trecere “în execuţie”) procesul cu cea mai mică durată de execuţie.

Exemplu:

Algoritmul SJF este optimal din punctul de vedere al duratei medii a unui ciclu de servire numai în cazul în care toate joburile care trebuie servite sunt disponibile simultan.

Exemplu de joburi nedisponibile simultan:

A(3) B(5) – disponibile la momentul 0

C(1) D(1) – disponibile la momentul 4

Dacă se foloseşte algoritmul SJF, se obţine mean turnaround time = 5,5.

Varianta preemptiva a algoritmului SJF este Shortest Remainning Time Next (SRTN. Durata totală de servire a unui proces trebuie să fie cunoscută în avans. Planificatorul de procese alege (pentru a trece în execuţie) procesul a cărui durată reziduală de servire este cea mai mică. La sosirea unui nou job, durata totală de servire a acestuia este comparată cu durata reziduală de servire a procesului aflat în curs de servire. Dacă durata totală de servire a noului job este mai mică, atunci procesul aflat în curs de servire este suspendat şi este trecut în execuţie noul proces.

Algoritmul SJF favorizează procesele de scurta durata in defavoarea celor de lunga durata. Dezavantajul acestui algoritm este ca necesita o cunoaştere precisa a timpului de rulare al unui proces , iar acesta informaţie nu este disponibila de obicei.

2.1.1.3 Priority scheduling (Ordonare bazata pe priorităţi)

Ordonarea circulara presupune ca toate taskurile au aceeaşi prioritate. In comanda unui proces industrial, aceasta situaţie este rareori un caz general. Adesea taskurile trebuiesc aranjate in funcţie de priorităţile sarcinilor de îndeplinit. Astfel apare ordonarea bazata pe priorităţi, având un singur task pe nivel de prioritate.

Principiul este simplu. Fiecare task primeşte, la crearea sa, un nivel de prioritate. Planificatorul lansează taskul cel mai prioritar, aflat in starea GATA DE EXECUTIE. Este conservat acest task atâta timp cat nu se blochează sau termina. Daca vreo întrerupere lansează un task material care activează la rândul sau un task logic, planificatorul trebuie apelat la sfârşitul taskului material pentru a compara priorităţile taskurilor in curs. Daca taskul curent este mai puţin prioritar, decât cel activat de rutina de întrerupere, o comutare trebuie sa aibă loc.

Asignarea priorităţilor:

-static: priorităţi asignate în conformitate cu ierarhia utilizatorilor proprietari

-dinamic: atunci când trebuie îndeplinite anumite obiective

ex: se setează prioritatea unui proces la 1/f, cu f = procentul consumat din cuanta anterioară

Variante combinate:-Procesele pot fi grupate în clase de priorităţi

-Se utilizează un algoritm de planificare bazat pe priorităţi la nivelul claselor

-Se utilizează un algoritm RR în cadrul fiecărei clase

Dacă nu se ajustează priorităţile claselor, există pericolul ca procesele din clasele mai puţin prioritare să nu se execute niciodată.

Are ca dezavantaj blocarea indefinită sau înfometare. O soluţie la problema înfometării ar fi îmbătrânirea= o metodă de a creşte prioritatea proceselor care aşteaptă de mult timp in coadă.

2.1.1.4 Multiple priority queues (Ordonare bazate pe priorităţi cu cozi multiple)

Este o varianta a ordonării pe baza de prioritate. Principiul consta in a combina ordonarea circulara (Round Robin) cu cea bazata pe prioritari (Priority scheduling). In acest mod, mai multe taskuri pot avea acelaşi nivel de prioritate. Daca mai multe taskuri sunt prezente in coada cea mai prioritara, aceste taskuri sunt in execuţie, după modelul round-robin, de fiecare data se rulează in maniera round-robin doar procesele din clasa de prioritate maxima (ignorându-se restul claselor); când aceasta nu mai conţine procese, se procedează la fel cu clasa următoare. Daca nu este decât un singur task pe nivel de prioritate, modelul este cel bazat pe priorităţi.

Procesele se împart pe mai multe categorii şi fiecare categorie are propriul ei algoritm de planificare şi propria coadă de procese. Exemplu: procese background, procese sistem,procese pe loturi.

Priorităţile proceselor trebuie ajustate din când in când (si mutateastfel dintr-o clasa in alta), altfel exista risc de înfometare pentru procesele din clasele inferioare.

Exemple:

1. Sistemul CTSS efectua lent comutarea intre procese, deoarece nu putea tine in memorie decât un proces; proiectanţii au constatat ca era mai eficient sa se dea proceselor limitate de calcule o cuanta mare de timp din când in când decât o cuanta mica frecvent, deoarece se reduce swapping-ul; nu se puteau da insa cuante mari tuturor proceselor, deoarece se marea prea mult timpul de răspuns pentru cererile scurte (am văzut).

Soluţia: S-au creat de clase de prioritate; procesele din clasa maxima erau rulate pentru 1 cuanta, cele din clasa următoare pentru 2 cuante, cele din clasa următoare pentru 4 cuante, etc; când un proces isi folosea in întregime cuanta, era mutat o clasa mai jos; când era apăsat Enter de la un terminal, procesul care ţinea de terminalul respectiv era mutat in prima clasa.

De ex. un proces care ar necesita 100 cuante pentru calcule ar primi prima data 1 cuanta, după care ar fi mutat pe disc, apoi 2 cuante, după care ar fi mutat pe disc, s.a.m.d. 4, 8, 16, 32 si in final 64 (din care ar mai folosi doar 37) cuante, fiind swapat in total de 7 ori in loc de 100 in cazul folosirii unui algoritm round-robin pur; totodată, pe măsura ce cobora in clasele de priorităţi, ar fi executat din ce in ce mai rar, păstrând procesorul pentru procese interactive scurte. A doua regula preîntâmpina situaţia când un proces era pedepsit constant daca la inceput avea nevoie sa execute mai mult timp calcule, chiar daca ulterior devenea interactiv

(apăsarea lui Enter implica presupunerea ca procesul e pe cale sa devina interactiv). La un moment dat insa un utilizator cu un proces puternic orientat pe calcule a observat ca apăsând Enter la întâmplare la interval de câteva secunde isi scurtează considerabil timpul de răspuns.

2. Sistemul XDS 940 (construit la Berkley) folosea 4 clase de priorităţi, numite (in ordinea descrescătoare a priorităţilor): terminale, I/O, cuante scurte, cuante lungi. Cand un proces care astepta date de la terminal era activat, era trecut in clasa 1; când un proces blocat in aşteptarea discului devenea ready, era trecut in clasa 2; când un proces era in execuţie când i-a expirat cuanta era trecut in clasa 3; când un proces isi folosea cuanta integral de mai multe ori la rând fără sa se blocheze (in aşteptarea terminalului sau a altor operaţii de I/O), era trecut in clasa 4. Astfel erau favorizate procesele interactive in pofida celor de fundal.

2.1.1.5 Inheritance scheduling

Acest este un algoritm descris intr-o hartie de la CMU. Procesele pot da timpul procesorului proceselor „copil” si sa se comporte cum ar fi programate de ei insisi. In acest fel , mai multe tipuri de planificari pot fi implementate : o planificare pentru procese in timp real , o planificare pentru procese interactive , o planificare pentru un lot de prelucrare, etc. Planificatorul de baza implementat de S.O. planifica procesele. |Cat timp procesele individuale ar putea oferi un altfel de planificare , planificarea de baza foloseste formulare MPQ.

2.1.1.6 Lottery scheduling (Planificarea in sistem de loterie)

Acest algoritm atribuie proceselor bilete de loterie pentru diverse resurse (de exemplu pentru timpul alocat pe procesor); atunci când trebuie luata o decizie de planificare se alege un bilet la întâmplare iar procesul care deţine biletul primeşte resursa (de exemplu in planificarea proceselor la procesor , sistemul poate desfăşura o loterie de 50 de ori pe secunda iar fiecare câştigător sa primească 20 milisecunde timp alocat pe procesor).

Procesele importante pot primi mai multe bilete; numărul de bilete primite de un proces la creare influenţează timpul sau de răspuns; de ex. daca exista 100 bilete pentru procesor si un proces deţine 20 bilete, va avea 20 % şansa de a câştiga la fiecare loterie, deci pe termen lung va obţine circa 20 % din timpul procesorului. Procesele cooperante pot schimba bilete intre ele; de ex. când un proces client trimite un mesaj unui proces server si apoi se blochează, poate trimite toate biletele sale serverului pentru a mari şansele acestuia de a se executa in continuare; in absenta clienţilor serverele nu au nevoie de bilete.

Cotoc Ginel Dragos ( 433 A )

2.1.2 Algoritmi folositi in sistemele de operare moderne

2.1.2.1 Multilevel Feedback Queue (Windows NT)

Planificatorul Multilevel Feedback Queue a fost pentru prima data dezvoltat de Corbato in 1962 intr-un sistem cunoscut sub numele de Compatible Time-Sharing System (CTSS), acest lucru ia adus lui Corbato la acordarea premiului Turing.

MLFQ urmareste rezolvarea a doua probleme. Prima se refera la optimizarea timpuli de intoarcere (turnaround time), care e facuta prin rularea srcinilor simple la inceput. A doua problema se refera la faptul ca MLFQ ar dori sa faca un sistem sa se simta sensibil la utilizatori interactivi, minimizand astfel timpul de raspuns (response time); din nefericire algoritmi precum Round Robin reduc timpul de raspuns dar sunt ineficienti cand vine vorba de timpul de intoarcere.

Problema se rezuma la cum sa proiectezi un planificator care sa minimizeze timpul de raspuns.

MLFQ : Regulile de baza

In incercarea de a construi un astfel de planificator, MLFQ are un numar distinct de cozi, fiecare coada avand un nivel de prioritate diferita. La un moment de timp, o sarcina care e gata de rulat poate fi intr-o singura coada. MLFQ foloseste prioritatea pentru a stabili care sarcina ar trebui sa ruleze la un moment dat: o sarcina cu prioritatea cea mai mare va fi cea care va rula.

Desigur, mai mult de o sarcina poate sa fie intr-o coada data, si astfel ele au aceeasi prioritate. In acest caz, vom folosi planificarea round-robin printre aceste sarcini.

Astfel, cheia planificari MLFQ sta in modul cum planificatorul seteaza prioritatile. In loc sa dea fiecarei sarcini o prioritate fixa, MLFQ variaza prioritatea sarcini pe baza observari comportamentului acesteia.

Regula 1: Daca Prioritatea(A) > Prioritatea(B), A va rula (si B nu va rula). Regula 2: Daca Prioritatea(A) = Prioritatea(B), atat A cat si B vor rula in modul round-

robin.

Cum sa schimbi prioritatea?

Trebuie sa decidem cum MLFQ va schimba nivelul de prioritate pentru o sarcina (si astfel in ce coada se afla) de-a lungul timpului de viata al unei sarcini.

Pentru a face asta trebuie sa tinem minte incarcarea sarcinilor: un amestec de sarcini interactive care in mod frecvent elibereaza CPU si cateva sarcini care ruleaza mai mult “CPU bound”, sunt sarcini care au nevoie de mult timp al CPU-ului dar unde timpul de raspuns nu este important.

Regula 3: Cand o sarcina intra in sistem , ea este plasata in coada cu prioritatea cea mai mare.

Regula 4a: Daca o sarcina foloseste un intreg ciclu de timp in timp ce ruleaza, prioritatea sa este redusa ( este mutata mai jos in coada).

Regula 4b: Daca o sarcina elibereaza CPU inainte ca ciclul de timp sa se incheie, ea isi pastreaza acelasi nivel de prioritate.

In urma introduceri ultimelor trei reguli apar doua probleme. Daca sunt prea multe sarcini interactive in sistem, ele vor consuma tot timpul CPU-ului, si astfel sarcinile care ruleaza mai mult nu vor beneficia de timpul CPU-ului. A doua se refera la faptul ca un utilizator mai inteligent poate rescrie programul de planificare. Se refera la faptul ca utilizatorul incerca sa pacaleasca palnificatorul pentru a primi mai mult din partea de resurse care i se cuvine.

Idea care ne ajuta sa iesim din acest impas se refera la stimularea periodica a prioritati tuturor sarcinilor din sistem. Pentru aceasta le vom muta pe toate in coada cu prioritatea cea mai mare. Se impune astfel o noua regula.

Regula 5: Dupa o perioada de timp S, toate sarcinile din sistem vor fi mutate in coada cu prioritatea cea mai mare.

Regula noua rezolva doua probleme deodata. Prima se referea la faptul ca sarcinile stau in coada cu priotiatea cea mai mare, o sarcina va imparti astfel CPU-ul cu alte sarcini de prioritate ridicata conform metodei round-robin. A doua priveste “CPU bound”, si anume daca o sarcina devine interactiva, planificatorul o trateaza corespunzator de indata ce va primi stimularea prioritati.

Mai avem o problema de rezolvat si anume cum sa prevenim rescrierea programului de planificare.

Solutia care se impune aici este o contabilizare mai buna a timpului CPU-ului la fiecare nivel al MLFQ. Pentru aceasta vom rescrie regulile 4a si 4b intr-o singura regula.

Regula 4: O data ce o sarcina foloseste timpul alocat la un nivel dat(indiferent de cate ori a eliberat CPU), prioritatea sa este redusa.

Ciclul de timp al cozilor variaza. Astfel cozile cu prioritatea cea mai mare vor avea un ciclu de timp mai mic, iar cozile cu prioritatea cea mai scazuta vor avea ciclul de timp cel mai mare.

2.1.2.2 O (1) (Linux)

In timpul perioadei de dezvoltare Linux 2.5.x, un nou algoritm de planificare a fost unul dintre cele mai semnificative schimbari ale nucleului (kernel).

Planificatorul Linux 2.4.x, in timp ce era folosit la scara larga, sigur, si in general destul de bun, avea cateva caracateristici nedorite. Caracteristicile nedorite au fost complet incorporate in proiectarea lui, si astfel cand Ingo Molnar s-a ridicat la nivelul provocari de a-l perfectiona, el a proiectat un nou planificator in loc sa faca modificari la cel vechi. Faptul ca algoritumul de planificare Linux 2.4.x continea algoritmi O( n) a fost probabil cel mai mare defect, si ulterior noul planificator a utilizat numai algoritmi O( 1), aceasta a fost cea mai buna imbunatatire a planificatorului.

Ce este un algoritm O( 1)?

Un algoritm opereaza la intrare, si dimensiunea acelei intrari de obicei determina timpul de executie. Notatia O-mare este utilizata pentru a descrie rata de crestere a unei executi a unui algoritm bazat pe timp in functie de cantitatea de la intrare. De exemplu timpul de executie al unui algoritm O( n) creste liniar pe masura ce dimensiunea intrari n creste. Timpul de executie al unui algoritm O( n^2) creste patrat. Daca este posibil sa stabilim granita superioara constanta a unui algoritm cu executie in timp, acesta este considerat a fi algoritumul O( 1) (unul poate spune ca ruleaza in “in timp constant”). Astel un algortitm O( 1) este garantat sa termine intr-un anumit moment de timp indiferent de marimea intrari.

Planificatorul care foloseste algoritmul O( 1) se bazeaza pe tablouri de procese active si expirate pentru a atinge planificarea constanta a timpului. Fiecarui proces ii este dat un timp fix, dupa care este executat si mutat intr-un tablou expirat. O data ce toate sarcinile dintr-un tablu activ au epuizat timpul fix acordat si au fost mutate in tabloul expirat, un comutator de tablouri intervine. Acest comutator transforma tablou activ in nou tablou expirat, care este gol, in timp ce tabloul expirat devine tabloul activ.

Problema principala a acestui algoritm este utilizarea complexa pentru a marca o sarcina ca fiind interactiva sau non-interactiva. Algoritumul incearca sa identifice procese interactive

prin analizarea timpului mediu de inactivitate ( starea de timp pe care o petrec procesele in astepatarea unei intrari). Procesele care sunt inactive pentru perioade mai lungi de timp probabil asteapta intrarea utilizatorului, astfel planificatorul ia decizia ca sunt interactive. Planificatorul da un bonus de prioritate sarcinilor interactive (pentru o mai buna tranzitie) in timp ce penalizeaza sarcinile non-interactive prin scadera prioritati acestora. Toate calculele pentru determinarea interactivitatea unei sarcini sunt complexe si supuse potentialelor erori de calcul, cauzand comportament non-interactiv din partea proceselor interactive.

Ce face ca planificatorul Linux 2.6.8.1 sa functioneze in timpul O( 1)?

Planificatorul Linux 2.6.8.1 nu contine nici un algoitm care sa ruleze mai prost decat O( 1). Astfel fiecare parte a planificatorului este garantata sa execute intr-un anumit moment constant de timp indiferent de cate multe sarcini sunt in sistem. Aceasta permite nucleului Linux sa manevreze in mod eficient numere masive de sarcini fara a creste costuri suplimentare pe masura ce numarul de sarcini creste. Sunt doua structuri de date cheie aici in planificatorul Linux 2.6.8.1 care permit acestuia sa execute sarcinile sale in O( 1), si proiectarea sa se invarte in jurul lor – cozi de executie si tablouri de prioritate.

2.1.2.3 Completely Fair Scheduler ( Linux)

Ingo Molnar, autorul CFS-ului afirma: “CFS in mod uzual modeleaza un CPU ideal, precis, multitasking pe hardware real.”

Sa incercam sa intelegem ce inseamana “CPU ideal, precis, multitasking”, pe masura ce CFS incearca sa imite acest CPU. Un “CPU ideal, precis, multitasking” este un hardware CPU care poate sa ruleze mai multe procese in acelasi timp (in paralel), dand astfel fiecarui proces o parte egala din puterea procesorului (nu timp, ci putere). Daca un singur proces ruleaza, el va receptiona 100% din puterea procesorului. Cu doua procese in executie, fiecare va avea exact 50% din puterea fizica (in paralel). Similar, cu patru procese ruland, fiecare va primi precis 25% din puterea fizica a CPU-ului in paralel.

Astfel CPU va fi “corect” cu toate sarcinile care ruleaza in sistem (Figura 1).

Figura 1

In mod clar, acest CPU ideal nu exista, dar CFS incearca sa imite un astfel de procesor in modul software. Pe un CPU actual din lumea reala, doar o sarcina poate fi alocata la un moment particular de timp. Din acest motiv, toate celelalte sarcini asteapta in decursul acestei perioade. Deci, pe masura ce sarcina curenta primeste 100% din puterea CPU-ului, toate celelalte sarcini primesc 0% din puterea CPU-ului. Acest lucru in mod evident nu este corect( Figura 2).

Figura 2

CFS incearca sa elimine aceasta lipsa de dreptate din sistem. CFS incearca sa tina evidenta parti corecte a CPU care a fost disponibila fiecarui proces din sistem. Deci, CFS ruleaza un ceas de corectitudine la o fractiune din viteza ceasului real al CPU-ului. Rata de crestere a ceasului de corectitudine este calculata prin divizarea timpului de obstacol ( in nanaosecunde) prin numarul total de procese care asteapta. Valoarea rezultata este momentul de timp al CPU cu care fiecare proces este indreptatit.

In timp ce un proces asteapta dupa CPU, planificatorul urmareste cantitatea de timp care ar fi fost folosita pe un procesor ideal. Acest timp de asteptare, reprezentat de timpul variabil de asteptare pe sarcina, este folosit pentru a clasa procesele pentru planificator si pentru a determina cantitatea de timp pentru care proceselor le este permis sa execute inainte de a fi modificate.

Procesul cu timpul de asteptare cel mai lung este luat de planificator si asignat CPU-ului. Cand acest proces ruleaza, timpul lui de asteptare este decrementat, pe cand timpul altor sarcini care asteapta creste. Aceasta inseamana ca dupa o perioada de timp, va fi o noua sarcina cu cel mai mare timp de asteptare, si sarcina curenta care ruleaza va fi modificata.

Folosind acest principiu, CFS incearca sa fie corect cu toate sarcinile si intotdeauna incearca sa aibe un sistem cu timp de asteptare zero pentru fiecare proces- fiecare proces are o parte egala din CPU ( acest lucru ar fi incercat sa faca un “CPU ideal, precis, multitasking”).

Pentru ca un CFS sa imite un “CPU ideal, precis, multitasking”, dand fiecarui proces o parte egala din timpul de executie el trebuie sa contina urmatoarele:

1. Un mecanism care sa caluleze care este partea corecta din CPU care se cuvine fiecarui proces. Aceasta este indeplinita prin utilizarea unuei variabile “system-wide runqueue fair_clock” (cfs_rq->fair_clock). Acest ceas de corectitudine ruleaza la o farctiune din timpul real, pentru ca astfel sa ruleze la pasul ideal pentru o singura sarcina cand sunt N sarcini care ruleaza in sistem.

2. Un mecanism care sa tina evidenta timpului pentru fiecare proces care asteapta in timp ce CPU a fost asignat cu rularea sarcini curente. Acest timp de asteptare este acumulat in “wait_runtime” variabilele pre-proces (process->wait_runtime).

Petre Marian Alin (434 Aa)

2.2 Algoritmi de alocare a resurselor in sistemele multiprocesor

Cresterea volumului de calcule efectuate de aplicatiile software moderne, de la servere de baze de date si servere web la programe de simulare complexe si aplicatii grafice 3D a adus necesitatea creearii de calculatoare din ce in ce mai rapide. Insa, datorita limitarilor tehnicilor VLSI actuale, viteza unui procesor nu este suficient de mare pentru a putea rula anumite tipuri de aplicatii.

Solutia la aceasta problema a fost impartirea aplicatiilor in taskuri care sa poata fi executate in paralel pe un numar mare de procesoare interconectate. Astfel, programe foarte complexe pot fi rulate intr-un timp rezonabil folosind supercalculatoare cu mii de procesoare interconectate, sau pot fi rulate distribuit pe un numar mare de statii in solutii de tipul Cloud Computing.

Principala problema a acestei abordari este alocarea eficienta a timpului fiecarui procesor, pentru a optimiza timpul de rulare al aplicatiei. Aceasta este o problema din punct de vedere computational, solutiile reprezentand compromisuri intre calitatea solutiilor si complexitatea si scalabilitatea algoritmilor folositi.

De asemenea, apare si problema dependentei intre taskuri, astfel ca se intalnesc des situatii in care executia unui task trebuie sa fie in mod necesar precedata de executia altor taskuri.

Problema poate fi modelata matematic folosind grafuri aciclice orientate. Astfel, fiecare nod al grafului reprezinta un task ce trebuie executat. O muchie orientata dinspre taskul Ti spre taskul Tjreprezinta faptul ca executia lui Tj este conditionata de executia prealabila a lui Ti. Valoarea fiecarui nod reprezinta timpul necesar executiei taskului respectiv pe unul dintre procesoarele sistemului ( acestea sunt considerate omogene ). Ponderea asociata fiecarei muchii reprezinta intarzierea de comunicare intre cele 2 taskuri. Problema este reprezentata de maparea taskurilor pe un set de procesoare, respectand dependentele dintre ele, si obtinerea unui timp de executie minim.

Datorita complexitatii problemei, obtinerea unei solutii optime nu este fezabila. In continuarea lucrarii sunt prezentati o serie de algoritmi care incearca sa gaseasca solutii cat mai apropiate de optim. Acesti algortmi sunt impartiti in doua categorii principale: algoritmi one-shot, care printr-o singura parcurgere a grafului incearca sa ghiceasca solutia optima si algoritmi iterativi, care, prin parcurgeri repetate, optimizeaza solutia initiala.

Sindrilaru Florin (433 A)

2.2.1 Algoritmi one-shot

2.2.1.1 Min-min

Programarea euristica min-min, prezentata de Ibbara si Kim, poate fi folosita pentru a programa

un grup de sarcini fara dependente pe un sistem multiprocesor eterogen. Min-min este un

algoritm simplu care selecteaza o sarcina Ti, cu minimum timp de completare pe orice procesor

de la U, grupul de sarcini nemapate/nemarcate, si le programeaza pe procesor, care are minimum

de timp de completare.

Acelasi alogoritm, cu mici modificari, poate fi aplicat pentru problema sarcinilor cu dependente.

In prezenta dependentelor, toate sarcinile de la U, nu se pot compara, pentru ca timpii de

completare nu se pot calcula pentru o sarcina daca toti predecesorii nu sunt deja mapati la un

procesor. Asadar, numai acele sarcini pentru care toti predecesorii au fost deja mapati (acele

sarcini pentru care toti predecesorii sunt in U) pot fi selectati pentru compararea timpului de

completare. In al doilea rand, calculul timpilor de completare contine atat timpul de executie al

sarcinii cat si timpul la care sarcina e gata de executie. Algoritmul min-min este foarte simplu,

usor de implementat si a fost unul dintre cele mai rapide algoritme de comparatie.

2.2.1.2 Chaining

Chaining, propus de Djordjevic si Tosic, este un algoritm deterministic intr-un singur pas bazat

pe tehnici de listare. In programarea eurisitca, numai sarcinile pregatite sunt considerate pentru

mapare. Inlantuirea invinge aceasta constrangere prin permiterea si sarcinilor nepregatite pentru

mapare. Asadar, sarcinile pot fi aranjate pentru mapare in orice ordine, indiferent de dependenta

sarcinii.

Chainingul incearca sa imparta graficul sarcinii intre procesoare si nu permite duplicarea

sarcinilor. Algoritmul incepe cu un grafic al sarcinii partial programat care este graficul sarcinii

originale la care doua sarcini false cu timpul de executie zero, s si q sunt adaugate. Fiecare

procesor incepe cu executarea sarcinii false s si termina cu executarea sarcinii false q. Toate

celelalte sarcinii sunt executate doar o singura data. Atatea p-margini ca si procesoare sunt

adaugate intre s si q. Fiecare p-margine de la s la q reprezinta ordinea executiei a unui singur

procesor. In fiecare iteratie a algoritmului sunt doua etape majore : selectia sarcinii si selectia

unei p-margini. In selectia sarcinii, in primul rand se alege o sarcina si apoi o p-margine. O

sarcina care are cea mai mica mobilitate, ex. o sarcina cu timpi mari de executie si timpi mari de

intarziere, este selectata in etapa alegerii sarcinii. Sarcina este mutata la o p-margine prin plasare

in care marimea celei mai lungi rute care trece prin sarcina este minima. Graficul partial

organizat al sarcinii este updatat prin inlaturarea a tuturor non p-marginilor dintre sarcina actuala

si sarcinile care sunt deja selectate pe p-margine. Acest proces este continuat pana ce toate

sarcinile au fost alocate unui procesor (mutate la o p-margine).

2.2.1.3 (HLFET) Highest Level First with Estimated Time

Algoritmul HLFET (primul cel mai ridicat nivel cu timp estimat), propus de Adam, este un

algoritm de organizare in lista care atribuie prioritatea organizarii pe fiecare nod plasat pe nivelul

static b-level, care este marimea celei mai lungi rute de la un nod la un nod de iesire, fara a lua in

considereare lungimea marginii (sau timpul necesar comunicarii). De exemplu, in figura de mai

sus, sa presupunem ca numarul din stanga fiecarui cerc reprezinta timpul executarii sarcinii. Cea

mai lunga ruta de la nodul T1 la nodul de iesire T5 este T1, T3, T5. Asadar, nivelul static b al lui

T1 = 1 + 3 + 2 = 6; nivelul static b al lui T4 este 3, deoarece T4 este insusi un nod de iesire.

Similar, nivelele statice b ale lui T2 si T3 sunt 4 respectiv 5.

Dupa ce toti predecesorii acestei sarcini au fost organizati, sarcina este pusa pe o lista de sarcini

gata pregatite. Aceasta lista este aranjata intr-o ordinde descrescatoare a nivelurilor statice b.

Nodurile care au aceleasi valori ale nivelului static b sunt selectate la intamplare. Pentru a obtine

o mai buna organizare , prima sarcina din lista celor pregatite este intotdeauna alocata unui

procesor care permite cea mai rapida executie utilizand metoda noninseritiei. Lista sarcinilor

pregatite se updateaza constant si procesul de organizare este repetat pana cand toate sarcinile au

fost organizate. Folosind nivelurile statice b simplifica organizarea deoarece nicelurile statice b

sunt constante pe parcursul intregului proces de organizare; cu toate aceastea, nu este optim

deoarece nu a luat in considerare timpul de comunicare ca factor al prioritatii organizarii

sarcinilor. In plus, algoritmul HLFET utilizeaza metoda noninsertiei si un slot de timpi inactivi

nu sunt utilizati, care afecteaza imbunatatirea performantei.

2.2.1.4 Insertion scheduling heurisitic (ISH)

Algoritmul ISH (Introducerea de programare eurisitca), propus de Kruatrachue si Lewis,

imbunatateste algoritmul HLFET prin utilizarea sloturilor cu timpi inactivi in programare. Initial

foloseste aceeasi abordare ca si algoritmul HLFET pentru a face o lista cu sarcini pregatite pe

baza nivelurilor statice b si organizeaza primul nod in lista utilizand metoda noninsertiei.

Diferenta este ca atunci cand un nod este programat creeaza un slot cu timp inactiv, ISH verifica

daca o sarcina din lista poate fi inserata in acel slot dar nu poate fi programata mai devreme pe

un alt procesor. Programeaza astfel cat mai multe sarcini posibile in acel slot cu timpi inactivi.

2.2.1.5 Duplication scheduling heuristic (DSH)

Duplicarea programarii euristice (DSH), propusa de Kruatrachue si Lewis, este diferita fara de

algoritmul HLFET si algoritmul ISH, care nu permit clonarea sau duplicarea sarcinilor.

Algoritmul DSH multiplica niste predecesori in diferite procesoare astfel incat fiecare copil poate

incepe cat mai devreme posibil prin eliminarea intarzierilor de comunicatie. Atunci cand un nod

creeaza un slot cu timpi inactivi, algoritmul incearca sa multiplice cat mai multi predecesori

posibili in slot daca predecesorii duplicati pot imbunatatii timpul de start al acelui nod. Initial,

nivelul static b al fiecare nod bazat pe diagrama DAG este calculat si toate nodurile sunt puse in

ordine descendenta in functie de nivelul static b. Nodul pregatit Ni cu cel mai mare nivel static b

este selctat ca un candidat si programat primul si testat pe fiecare din procesoare. Daca nodul Ni

creeaza un slot cu timp inactiv in unul din procesoare, atunci parintele Np al acestui nod care nu

este programat in acest procesor si are cel mai indelungat timp de asteptare este considerat pentru

duplicare. Daca aceasta are loc cu succes, timpul de start al nodului Ni este ajustat si Np este

considerat candidat. Parintii lui Np sunt cautati din urma si acest proces se repeta pana nu se mai

permite multiplicarea sau numai exista noduri de intrare. Sarcina selectata Ni ar trebui

programata in procesorul care ofera timpul de start cel mai scazut.

Ahmad si Kwok au modificat algoritmul DSH in algoritmul numit Bottom-Up Top-Down

Duplication Heuristic (BTDH). Marea imbunatatire a acestui algoritm BTDH fata de algoritmul

DSH este ca BTHD continua multiplicarea predecesorilor unui nod chiar daca slotul timpului de

duplicare este complet folosit in speranta ca timpul de start va fi minimalizat. In orice caz, autorii

spus ca performanta celor doi algoritmi este apropriata.

Petre Marian Alin (434 Aa)

2.2.2 Algoritmi de cautare iterativa

2.2.2.1 Algoritmi genetici

Aceasta clasa de algoritmi emuleaza mecanismele naturale de variatie genetica si selectie. Se porneste cu alegerea unei codari a spatiului solutiilor sub forma unor “cromozomi” binari. “Genele” acestor cromozomi sunt reprezentate de elemente ireductibile ale solutiei, in acest caz asocieri intre un anumit task, un procesor al sistemului si perioada de timp in care acel task va rula. Functionarea algorimului este urmatoarea:

Se porneste de la un anumit set cromozomi generati aleator, care reprezinta prima generatie de solutii.

Acest set este evaluat de o functie de fitness, care determina care sunt cele mai bune solutii din generatia curenta si le foloseste pe acestea pentru a genera urmatoarea generatie de solutii. Este ideal ca si o parte a solutiilor slabe sa fie selectata, pentru a garanta diversitatea urmatoarei generatii. Aceasta actiune impiedica convergenta prea rapida a algoritmului intr-un set de solutii sub-optime.

Urmatoarea generatie de solutii este creata prin variatii ale solutiilor selectate din generatia curenta. Se folosesc in general doua metode de variatie, ambele inspirate de variatii naturale ale AND-ului. Prima metoda este mutatia, care implica variatia aleatoare a uneia sau mai multor gene. A doua metoda este cross-over, care implica schimbarea unei secvente de gene intre doi cromozomi.

Functia de fitness este aplicata acestei generatii, iar procesul continua pana cand o solutie suficient de buna este gasita.

Algoritmii genetici sunt algoritmi nedeterministi, deci pot avea mari variatii de performanta. In cazul alocarii taskurilor in sisteme multiprocesor, acestia dau rezultate bune.

2.2.2.2 A*

Algoritmul A* este un algoritm heuristic de cautare de tip best –first. Este un algoritm de cautare in arbori care incepe cu o solutie nula, apoi ajunge la solutie printr-o serie de solutii partiale. Solutia nula inseamna, in cazul nostru, ca nici un task nu va fi alocat pe nici un procesor. Solutiile partiale sunt obtinute alocand un task pe toate procesoarele posibile.

Fiecare alocare este o solutie partiala diferita, deci fiecare nod are p copii, unde p este numarul de procesoare. In fiecare nod, solutia partiala are un task in plus mapat fata de nodul parinte. Numarul total de noduri este limitat astfel incat sa se evite o crestere exponentiala a timpului de executie.

Pentru fiecare nod se aplica functia de cost f(n) = g(n) + h(n), unde g(n) este timpul de procesor total care mai este disponibil si h(n) reprezinta estimarea minim a timpului necesar pentru executia taskurilor ramase. Pentru a limita dimensiunea arborelui, nodurile cu cea mai mare valoare a f(n) sunt eliminate atunci cand numarul total de noduri depaseste limita admisa. Implementare acestui algoritm in pseudocod este:

function A*(start,goal) closedset := the empty set // Setul de noduri care au fost deja evaluate openset := set containing the initial node //Setul de noduri posibile ce var fi evaluate

g_score[start] := 0 //Distanta de la start pe traseul optim h_score[start] := heuristic_estimate_of_distance(start, goal) f_score[start] := h_score[start] // Estimated total distance from start to goal through y. while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from[goal]) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset add y to openset tentative_is_better := true elseif tentative_g_score < g_score[y] tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score h_score[y] := heuristic_estimate_of_distance(y, goal) f_score[y] := g_score[y] + h_score[y] return failure

function reconstruct_path(current_node) if came_from[current_node] is set p = reconstruct_path(came_from[current_node]) return (p + current_node) else return current_node

2.2.2.3 Simulated annealing

Aceasta clasa de algoritmi este inspirata de un proces metalurgic ce consta in incalzirea unui metal urmata de racirea lui treptata, pentru a obtine o structura cristalina cat mai rezistenta. Atunci cand metalul este incalzit, atomii instabili sunt scosi din starea lor de energie si trecuti in stari superioare. Odata cu racirea metalului, atomii acestuia tind spre stari de energie minime, imbunatatind astfel proprietatile structurii cristaline. Prin repetarea procesului, metalul se apropie tot mai mult de o structura cristalina perfecta, de energie minima.

In cazul problemei noastre, se foloseste o varianta simplificata a algoritmului : mai intai toate taskurile sunt etichetate in functie de pozitia topologica in graf. Toate taskurile care

sunt asignate aceluiasi procesor sunt executate secvential in functie de eticheta. Temperatura sistemului este scazuta la fiecare noua generatie. In fiecare noua generatie, o solutie este generata prin modificarea aleatoare a solutiei curente. Aceasta modificare se face prin eliminarea unui task sau schimbarea intre doua taskuri. Noul rezultat este evaluat de functia de fitness. Daca acesta este mai bun sau mai slab in anumite limite decat rezultatul precedent, rezultatul precedent este inlocuit. Algoritmul se opreste atunci cand temeperatura ajunge la o valoare predefinita. Algoritmul este urmatorul:

initializeaza solutia estimeaza temperatura initiala evalueaza solutia daca solutia este acceptabila, inlocuieste solutia precedenta ajusteaza temperatura daca temperatura a atins o valoare predefinita, opreste algorimul;

altfel, genereaza o noua solutie.

2.2.2.4 Tabu search

Tabu search este o tehnica de cautare in vecinatati care incearca se evite minimele locale si incearca sa ghideze cautarea spre un minim global.

Algoritmul este initializat cu o solutie initiala, care poate fi obtinuta cu un algoritm heuristic de tip one-pass, si cauta in vecinatatile soultiei curente, adica toate solutiile care difera de aceasta printr-o singura permutare. Pentru problema de alocare a taskurilor in sisteme multiprocesor, o permutare reprezinta mutarea unui task de pe un procesor pe altul sau schimbarea ordinii executiei taskurilor pe acelasi procesor. Aceasta tehnica considera toate mutarile posibile in vecinatatea imediata si o alege pe aceea cu cel mai mic timp total de executie posibil.

2.2.3 Concluzii

In aceasta sectiune vor fi folosite rezultatele studiului “A performance study of multiprocessor task scheduling algorithm” de S. Jin, G. Schiavone si D. Turgut.

Acest studiu testeaza eficienta algoritmilor mentionati anterior la rezolvare alocarii timpului de procesor pt doi algorimi: eliminarea Gauss-Jordan si factorizare LU a matricilor.

Grafurile de taskuri rezultate pentru cele doua probleme sunt prezentate in figurile 1 si 2.

Figura 1: Graful de taskuri pentru algoritmul de factorizare LU cu 35 de taskuri

Figura 2: Graful de taskuri pentru eliminare Gauss-Jordan cu 36 de taskuri.

Timpul toatal de procesare ( makespan )obtinut de fiecare algoritm in functie de numarul de taskuri este prezentat in figurile 3 si 4.

Figura 3: Makespan obtinut pentru factorizarea LU

Figura 4: Makespan obtinut pentru eliminarea Gauss-Jordan

Din comparatia celor noua algoritmi se obtin urmatoarele concluzii : DSH a avut cel mai scurt timp de executie si a obtinut cele mai bune alocari ale timpului de procesor. Algoritmii one-pass fara duplicarea taskurilor au obtinut rezultate bune si au avut timpi de executie scurti. Algoritmii de cautare iterativa au avut timpi de executie foarte ridicati, insa au obtinut makespan-uri foarte scurte. Folosirea acestora este justificata pentru a face o alocare a taskurilor pentru un algoritm ce va fi rulat de foarte multe ori, alocare ce va fi calculata antrerior executiilor si va fi folosita repetat.

cuprins: - ingineria sistemelor de calculstst.elia.pub.ro/news/teme_soiii_2010/prfirex/fire...

Documents