Fire de executie si procese
Yüklə 312,77 Kb.
|
- Bu səhifədəki naviqasiya:
- 1.2 Metode de comunicare intre procese
|
Fire de executie si procese Cuprins:Adrian Pop(434Aa)
1.1 Concepte generale 1.1.1 Procese 1.1.2 Fire de executie 1.2 Mecanisme de comunicare interproces 1.2.1 Pipe-uri 1.2.2 Semnale Vutan Gheorghe Adrian (433 A)
Jitaru Claudiu(433 A)
Andrei Stefanescu(433 A)
2.1 Algoritmi de alocare a timpului de procesor 2.1.1 Algoritmi “standard” 2.1.1.1 Round-Robin 2.1.1.2 Shortest job first 2.1.1.3 Priority scheduling 2.1.1.4 Multiple priority queues 2.1.1.5 Inheritance scheduling 2.1.1.6 Lottery scheduling Cotoc Ginel Dragos(433 A ) 2.1.2 Algoritmi folositi in sistemele de operare moderne 2.1.2.1 Multilevel feedback queue (Windows NT) 2.1.2.2 O(1) (Linux) 2.1.2.3 Completely Fair Scheduler(Linux) Petre Marian-Alin(434Aa) 2.2 Algoritmi de alocare a resurselor in sistem multiprocesor Sindrilaru Florian(433 A) 2.2.1 Algoritmi “one-shot” 2.2.1.1 Min-min 2.2.1.2 Chaining 2.2.1.3 Highest level first with estimated times (HLFET) 2.2.1.4Insertion scheduling heuristic (ISH) 2.2.1.5 Duplication scheduling heuristic (DSH) Petre Marian-Alin(434Aa) 2.2.2 Algoritmi de cautare iterativa 2.2.2.1 Algoritmi genetici 2.2.2.2 A* 2.2.2.3 Simulated anealing 2.2.2.4 Tabu search 2.2.3 Concluzii Pop Adrian Cristian (434 Aa) 1.1.1.Procese: Toate calculatoarele moderne , deseori fac mai multe lucruri in acelasi timp , insa oamenii care lucrau cu calculatoare personale nu erau constienti de acest lucru, asa ca vom considera cate exemple pentru a clarifica acest lucru. De exemplu , pentru un Server de Web ,cererile pot veni din diverse directii , solicitand o anumita pagina Web. Atunci cand o cerere soseste , serverul verifica daca are pagina ceruta in memoria tampon( cache).Daca aceasta exista , este returnata solicitantului , daca nu , se incepe procedura de aducere a paginii de pe disc. Insa , din perspectiva procesorului , aceste cereri de aducere de pe disc dureaza o eternitate. In timp ce asteapta ca aceasta cerere sa se finalizeze , pot aparea alte cereri de acest gen. Daca avem mai multe discuri la dispozitie , unul sau toate pot fi pornite inainte ca prima cerere sa fie solutionata. Evident este nevoie de un mod de control ale acestor cereri simultane. Aici intervin procesele (si in special firele de executie). Sa luam de exemplu un PC. Atunci cand sistemul se porneste , multe dintre procese sunt pornite silentios de multe ori fara stirea utilizatorului. De exemplu , un proces poate fi pornit in asteptarea e-mailurilor ce trebuie sa soseasca. Alt proces poate functiona pentru antivirus , pentru a verifica daca nu au aparut definitii noi despre virusi. In plus , pot rula si diferite procese pornite de utilizator, printari de fisiere , scrieri pe un CD-ROM , toate concomitent cu navigarea pe internet a utilizatorului. Toate aceste activitati trebuie sa fie gestionate si un sistem multiprogram ce suporta mai multe procese in paralel ar fi foarte indicat. In orice sistem multiprogramare , UCP trece de la un proces la altul foarte rapid , rulandu-le pe fiecare timp de zeci sau sute de milisecunde. Desi , in realitate UCP ruleaza doar un singur proces la fiecare moment de timp, in durata a unei secunde acesta poate lucra la multe din ele , dand iluzia de paralelism.Unele persoane definesc acest lucru ca fiind pseudoparalelism , in contrast cu paralelismul real bazat pe posibilitati hardware ale unor sisteme multiprocesor (care au doua sau mai multe CPU-uri ce impart aceeasi memorie fizica). Urmarirea acestor activitati multiple si paralele este apropape imposibila pentru oameni de facut. De aceea , creatorii de sisteme de operare au folosit un model conceptual , pe care l-au dezvoltat pentru a face fata paralelismului. Acest model va fi tratat in continuare. Modelul de proces: In acest model , orice aplicatie executabila de pe calculator precum si sistemul de operare este organizat intr-un numar de procese secventiale, sau pe scurt procese. Un proces este o instanta a unui program aflat in executie , continand valorile curente ale contorului de program , registrii si variabile. Conceptual , fiecare proces are CPU-ul lui propriu. In realitate insa , CPU-ul real trece de la un proces la altul, insa pentru a intelege mai bine acest sistem , e mai usor sa ne gandim la aceste procese ca ruleaza intr-un pseudo-paralelism, in loc de a incerca sa urmarim saltul procesorului de la program la program. Acest salt rapid de la un proces la altul este numit multiprogramare . In continuare , vom considera existenta unui singur CPU, insa mai nou aceasta presupunere nu este realista pentru ca apar cipuri cu mai multe core-uri ,continand doua , patru sau mai multe CPU.Deci atunci cand zicem ca un procesor poate rula un proces in acelasi moment de timp , daca exista doua core-uri(sau procesoare) fiecare dintre ele va rula un singur proces in acelasi timp. Cu trecerea rapida a procesorului de la un proces la altul , rata la care aceste procese vor face calculele nu va fi uniforma si probabil nereproductibila daca aceleasi procese ar rula din nou. Deci , procesele nu pot fi programate cu anumite presupuneri legate de timpii de executie. Diferenta dintre un proces si un program este subtila dar cruciala.Un proces reprezinta o activitate anume. El are un program , intrare , iesire , si o stare. Un singur procesor poate fi impartit intre mai multe procese , cu ajutorul unui algoritm care va fi folosit pentru a stabili cand sa se opreasca din executia unui proces si sa treaca la altul. Este inutil ca un program sa ruleze de doua ori , ar exista doua procese. De exemplu , de multe ori se intampla sa porniti un program de doua ori , sau sa printati doua fisiere in acelasi timp, daca dispuneti de doua imprimante.Faptul ca doua procese in derulare se intampla sa ruleze acelasi program nu conteaza pentru ca ele sunt doua procese distincte. Sistemul de operare poate fi capabil sa imparta codul intre cele doua astfel incat in memorie sa existe doar o singura copie , insa acest lucru este un detaliu tehnic ce nu schimba situatia conceptuala a doua procese in derulare.
Exista patru evenimente principale care necesita crearea unui proces:
Atunci cand sistemul porneste , sunt create diferite procese. Unele dintre aceste procese sunt procese de fundal , care au ca scop interactionarea cu utilizatorul si de a lucra pentru el. Alte procese sunt ascunse , nefiind asociate unui utilizator anume , insa au fiecare cate o functie specifica. De exemplu , un proces ascuns poate fi creat pentru acceptarea e-mailurilor ce vor sosi, care sta intr-o stare latenta in mare parte a zile , insa se trezeste la viata in momentul sosirii unui nou e-mail. Pe langa procesele create la incarcarea sistemului , noi procese pot fi create de asemenea si dupa aceea.De multe ori un proces in derulare va cere sistemului sa creeze unul sau mai multe procese pentru a-si usura munca.Un exemplu unde acest lucru ar fi eficient , este intr-un sistem in care o cantitate mare de informatii este transferat printr-o retea , atunci ar fi mai bine sa existe un proces care primeste fiecare pachet , si il pune in memorie , iar alt proces ia informatia din memorie si o proceseaza secvential. Intr-un multiprocesor , permiterea rularii unui proces pe un CPU diferit poate face ca sarcina sa se finalizeze mai rapid. In toate aceste cazuri , un nou proces este creat prin intermediul unui alt proces care face un apel de creare la sistem. Acel proces poate fi unul rulat de un utilizator , un proces de sistem invocat de tastatura sau mouse sau un manager de sarcini multiple.Acel apel la sistem ii spune sistemului sa creeze un nou proces si ii indica , direct sau indirect , in care program sa il ruleze. In UNIX , exista un singur apel de sistem pentru crearea unui nou proces : fork. Acest apel creaza o clona a procesului apelant. Dupa fork , cele doua procese , parintele si copilul (denumiri pentru cele doua procese, ce rezulta din ierarhie) au aceeasi imagine de memorie, aceleasi variabile de mediu , si aceleasi fisiere deschise. De obicei , noul proces creat , copilul , executa comanda execve sau un alt apel de sistem similar pentru a-si schimba imaginea de memorie si sa ruleze un alt program. In Windows , avem un singur apel de functie Win32 , CreateProcess , care creaza procesul si de asemenea incarca programul corect in acesta. Acest apel are 10 parametrii , incluzand programul care urmeaza a fi executat , parametrii liniei de comanda pentru acel program , diferite atribute de securitate , biti de control pentru fisierele mostenite, informatie despre prioritate , informatii despre fereastra ce urmeaza a fi creata pentru acest proces (daca este cazul) , si un pointer catre o structura in care informatia despre noul proces este returnata apelantului. In plus , pe langa acest apel CreateProcess , WIN32 mai are 100 alte functii pentru gestionarea si sincronizarea proceselor si a altor subiecti asemanatori. Atat in UNIX cat si in Windows , dupa ce un proces este creat , parintele si copilul au spatiile lor de memorie distincte.Daca oricare dintre ele modifica un cuvand din spatiul de adrese , aceasta modificare nu este vizibila pentru celalalt proces. In UNIX , spatiul initial al copilului este practic o copie a parintelui , insa exista doua spatii de adresare distincte, nefiind partajata nici un fel de memorie inscriptionabila. E posibil insa ca un proces nou creat sa isi imparta cateva din resursele creatorului, cum ar fi fisiere deschise. In Windows , adresa parintelui si a copilului sunt diferite de la bun inceput.
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:
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.
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.
In derulare 1 3 2 Blocat Pregatit 4 In derulare 1 3 2 Blocat Pregatit 4 Desi fiecare proces este o entitate independenta , cu stare interna , contor de program , si stare interna , procesele trebuie sa interactioneze cu alte procese.Un proces poate genera date de intrare pentru un alt proces. Atunci cand un proces se blocheaza, acest lucru se intampla evident din cauza ca nu mai poate continua , si asteapta de obicei niste date de intrare. De asemenea se poate intampla ca un proces sa fie pregatit pentru a fi rulat si oprint deoarece sistemul de operare a considerat sa aloce timpul CPU pentru alt proces. Un proces poate avea trei stari distincte:
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.
Fig. 1 Un proces poate fi in stare de rulare , blocat , sau pregatit. Tranzitiile intre aceste stari se desfasoara conform graficului. Asa cum rezulta si din grafic , sunt posibile 4 tranzitii intre aceste stari. Prima tranzitie apare atunci cand sistemul de operare descopera ca un proces nu poate continua in acest moment , iar in unele sisteme acesta poate executa un apel prin care cere intra in pauza sau starea blocata. In UNIX , daca de exemplu un proces citeste dintr-un terminal , si nu exista date de intrare , acesta este blocat automat. Tranzitiile 2 si 3 sunt cauzate de catre gestionarul de procese , ca parte a sistemului de operare , fara ca 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.
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:
Yüklə 312,77 Kb. Dostları ilə paylaş:
|