Cuprins:



Fire de executie si proceseCuprins:Adrian Pop(434Aa)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 SemnaleVutan Gheorghe Adrian (433 A)Mecanisme de sincronizareSemafoareMutexuriEvenimente Sectiuni criticeVariabile de conditie MonitoareProbleme de sincronizare: deadlock, race conditionJitaru Claudiu(433 A)Functii API de gestiune a proceselor si firelor de executieGestiunea proceselor si a firelor de executie in WindowsGestiunea proceselor si a firelor de executie in LinuxAndrei Stefanescu(433 A)Algoritmi de gestiune de procese si de fire de executie2.1 Algoritmi de alocare a timpului de procesor 2.1.1 Algoritmi “standard”2.1.1.1 Round-Robin2.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 schedulingCotoc 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 multiprocesorSindrilaru 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 genetici2.2.2.2 A* 2.2.2.3 Simulated anealing2.2.2.4 Tabu search2.2.3 ConcluziiPop 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:Initializarea sistemuluiExecutia cererii de creare a unui proces de catre un alt proces in derulareCererea de catre utilizator pentru crearea unui nou procesInitializarea unei sarcini multipleAtunci 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:Iesire normala (voluntara)Iesire pe baza de eroare(voluntara)Eroare fatala (involuntara)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 , proc In derulare 1 3 2 Blocat Pregatit 4 In derulare 1 3 2 Blocat Pregatit 4esele 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:In rulare ( foloseste timpul CPU in acest moment)Pregatit (capabil de a fi rulat , dar oprit temporar pentru a permite altui proces sa fie rulat)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.Procesul se blocheaza in asteptarea datelor de intrareGestionarul alege un alt procesGestionarul alege acest procesDatele de intrare sunt primiteFig. 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 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:Nu pot exista doua procese care sa se afle simultan in regiunile lor criticeNu se pot face nici un fel de presupuneri asupra numarului sau vitezei CPU-urilor.Nici un proces care nu ruleaza in regiunea sa critica nu poate bloca un alt procesNici 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 psau % mkfifo npipeDe 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 npipeCaracterul 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 executienu avem nevoie de un mecanism de sincronizare pentru pipe-uri denumitescrierea 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 calculatorpipe-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?SIGILL 5) SIGTRA? 6) SIGIOT?SIGBUS? 8) SIGFPE ? 9) SIGKILLSIGUSR1 11) SIGSEGV 12) SIGUSR2 SIGPIPE 14) SIGALRM 15) SIGTERMSIGCHLD 18) SIGCONT 19) SIGSTOPSIGTSTP 21) SIGTTIN 22) SIGTTOUSIGURG 24) SIGXCPU 25) SIGXFSZ SIGVTALRM 27) SIGPROF 28) SIGWINCH29) SIGIO 30) SIGPWRProcesele 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 sincronizareIntroducerePentru sincronizarea firelor de execu?ie avem la dispozi?ie: sec?iuni critice (excludere mutual? ?n cadrul aceluia?i proces) – doar Win32mutex: POSIX, Win32semafoare: POSIX, Win32variabile de condi?ie: POSIX, Win32 (?ncep?nd cu Vista)evenimente: doar Win32timere: 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 POSIXSemafoarele 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 buffersemaforul 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( ) 247650151765b) empty = N; full = 0; mutex = 1 ?i se execut? consumer( )2952759525c) empty != 0; full != 0; mutex = 1 ?i cele dou? procese ?ncearc? s? intre simultan ?n SC6667561595full 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 deschidereaFunc?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 incrementareaOpera?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 );DistrugereaOpera?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 succesdaca nu, a?tept s? devin? disponibil, dup? care ?l acaparez, ?i func?ia ?ntoarce succesla 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 EvenimenteEvenimentele 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 criticeAlocarea 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 criticeSec?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 implicitetrebuie 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?iePentru 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 monitorVariabile 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 monitorAcest 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.523875469265Exemple deadlock\171450-114300Exemplul 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-ului4 condi?ii necesare pt. apari?ia deadlock-ului ?ntr-un sistem:Excludere mutual?: fiecare resurs? este de?inut? de cel multun proces“Hold & wait”: procesele care ?nc? de?in resurse primiteanterior 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 resurselorTehnici de tratare a deadlock-ului1) 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?. 695325156210Excludere mutual? ?ntre cele dou? proceseJitaru Claudiu (433 A)Bibliografie – Partea de windows , Documenta?ie : 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_CLASSBELOW_NORMAL_PRIORITY_CLASSNORMAL_PRIORITY_CLASSABOVE_NORMAL_PRIORITY_CLASSHIGH_PRIORITY_CLASSREALTIME_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 prioritateNivelurile de prioritate din cadrul fiec?rei priorit??i de clas? sunt urm?toarele:THREAD_PRIORITY_IDLETHREAD_PRIORITY_LOWESTTHREAD_PRIORITY_BELOW_NORMALTHREAD_PRIORITY_NORMALTHREAD_PRIORITY_ABOVE_NORMALTHREAD_PRIORITY_HIGHESTTHREAD_PRIORITY_TIME_CRITICALToate 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 : 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-spaceAceste 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 SpaceAcestea 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 : de procese1.Procese automateProcesele 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-urileDaemonii 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 interactiveAcestea 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?ieregular_commandRuleaz? aceast? comand? ?n prim plancommand &Ruleaz? aceast? comand? ?n plan secundarJobsArat? procesele/comenzile ce ruleaz? ?n backgroundCtrl+ZSuspend?(stopeaz?,dar nu termin?) un proces care ruleaz? ?n prim plan.Ctrl+CIntrerupe(termin? ?i renun??) un proces ce ruleaz? ?n prim plan%nFiecare 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.bgReactiveaz? un program suspendat din backgroundfgPune jobul ?napoi ?n prim plan.KillTermin? un processCrearea proceselorUn 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”.SemnaleProcesele sf?r?esc deoarece primesc un semnal.Exist? multiple semnale ce pot fi transmise unui anda 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 semnaluluiNum?rul semnaluluiSemnifica?iaSIGTERM15Termin? procesul ?ntr-un mod ordonatSIGINT2?ntrerupe procesul.Un proces poate ignora acest semnalSIGKILL9?nterupe procesul.Un proces nu poate ignora acest semnalSIGHUP1Semnal specific daemon-urilor.Atributele procesuluiCu 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] 26595theo:~> 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 -afBrowser-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 8 root 9 0 0 0 0 SW 0.0 0.0 0:05 kupdated 9 root -1-20 0 0 0 SW< 0.0 0.0 0:00 mdrecoveryd 13 root 9 0 0 0 0 SW 0.0 0.0 0:01 kjournald 89 root 9 0 0 0 0 SW 0.0 0.0 0:00 khubd 219 root 9 0 0 0 0 SW 0.0 0.0 0:00 kjournald 220 root 9 0 0 0 0 SW 0.0 0.0 0:00 kjournaldPrima linie de top con?ine acce?i informa?ie afi?at? de comanda uptime :jeff:~> uptime 3:30pm, up 12 days, 23:29, 6 users, load average: 0.01, 0.02, 0.00Datele acestor programe sunt stocate printre altele , ?n /var/run/utmp (informa?ii despre userii momentan conecta?i) ?i ?n fi?ierul virtual /proc , de exemplu , /proc/loadavg (informa?ii de ocupare medie).Exist? tot felul de aplica?ii grafice pentru a vizualiza aceasta dat? cum ar fi Gnome System Monitor ?i lavaps.Rela?iile ?ntre procese pot fi vizualizate folosing comanda pstree:sophie:~> pstreeinit-+-amd |-apmd |-2*[artsd] |-atd |-crond |-deskguide_apple |-eth0 |-gdm---gdm-+-X | `-gnome-session-+-Gnome | |-ssh-agent | `-true |-geyes_applet |-gkb_applet |-gnome-name-serv |-gnome-smproxy |-gnome-terminal-+-bash---vim | |-bash | |-bash---pstree | |-bash---ssh | |-bash---mozilla-bin---mozilla-bin---3*[mozilla-bin] | `-gnome-pty-helper |-gpm |-gweather |-kapm-idled |-3*[kdeinit] |-keventd |-khubd |-5*[kjournald] |-klogd |-lockd---rpciod |-lpd |-mdrecoveryd |-6*[mingetty] |-8*[nfsd] |-nscd---nscd---5*[nscd] |-ntpd |-3*[oafd] |-panel |-portmap |-rhnsd |-rpc.mountd |-rpc.rquotad |-rpc.statd |-sawfish |-screenshooter_a |-sendmail |-sshd---sshd---bash---su---bash |-syslogd |-tasklist_applet |-vmnet-bridge |-xfs `-xinetd-ipv62. Algoritmi de gestiune de procese si de fire de executie2.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 firstAlgoritmul 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 nepreemptivDuratele 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 roundrobin, 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 schedulingAcest 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 moderne2.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 bazaIn 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 1In 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 2CFS 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: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.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 multiprocesorCresterea 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-shot2.2.1.1 Min-minProgramarea 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 ChainingChaining, 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 TimeAlgoritmul 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 iterativa2.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_node2.2.2.3 Simulated annealingAceasta 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 solutiaestimeaza temperatura initialaevalueaza solutiadaca solutia este acceptabila, inlocuieste solutia precedentaajusteaza temperaturadaca temperatura a atins o valoare predefinita, opreste algorimul;altfel, genereaza o noua solutie.2.2.2.4 Tabu searchTabu 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.0144780Figura 1: Graful de taskuri pentru algoritmul de factorizare LU cu 35 de taskuri-101600151765Figura 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 LUFigura 4: Makespan obtinut pentru eliminarea Gauss-JordanDin 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. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download