Procese - UNIX

Procese - UNIX

Aceasta sectiune examineaza mai indeaproape subsistemul proceselor. Ea descrie structura unui proces si o serie de structuri de date utilizate pentru gestiunea memoriei. Apoi, se va oferi o imagine preliminara a diagramei de stare a proceselor si se vor analiza diferite aspecte legate de tranzitia starilor.

Un proces reprezinta executia unui program si consta dintr-un sablon de octeti care sunt interpretati de U.C.P. ca instructiuni masina ('text'), date, si zone de stiva. Prin planificarea proceselor pentru executie de catre nucleu, ele par a se executa simultan si mai multe procese pot fi instante ale aceluias program. Un proces se executa urmand strict o secventa de instructiuni proprii si nu poate sari la instructiunile altui proces; acesta citeste si scrie propriile date si sectiuni de stiva, insa nu poate citi si scrie date si stive ale altui proces. Procesele comunica intre ele si cu exteriorul prin intermediul apelurilor sistem.

Practic, un proces in UNIX este o entitate creata prin apelul sistem fork. Fiecare proces, exceptand procesul 0 , este creat in urma executiei de catre un alt proces a apelului sistem fork. Procesul care invoca fork este proces parinte, iar procesul nou creat este proces fiu. Fiecare proces are un singur parinte, insa poate avea mai multi fii. nucleul identifica fiecare proces prin numarul sau de proces, numit identificator de proces (PID). Procesul 0 este un proces special creat manual la incarcarea sistemului; dupa nasterea procesului fiu (procesul 1) procesul 0 devine procesul incarcator. Procesul 1, cunoscut si ca procesul init, este stramosul tuturor celorlalte procese din sistem si beneficiaza de relatii speciale cu acestea (Capitolul 8).

Un utilizator compileaza codul sursa al unui program pentru a crea un fisier executabil, care consta din cateva parti:

un set de antete care descriu atributele fisierului;

textul programului;

o reprezentare in limbaj masina a datelor care sunt initializate la inceputul executiei programului, si o indicatie asupra marimii spatiului ce trebuie alocat de nucleu pentru datele neinitializate, numite bss, si pe care nucleul le initializeaza cu 0 la rulare;

alte sectiuni, cum ar fi informatii despre tabela de simboluri.

Pentru programul din figura 1.3 textul fisierului executabil este codul generat pentru functiile main si copy, data initializata este variabila version (introdusa in program doar pentru a avea date initializate), iar data neinitializata este sirul buffer. Compilatorului de C al versiunii System V creaza implicit o sectiune de text separata, insa accepta o optiune care permite includerea de instructiuni program in cadrul sectiunii de date, folosita in versiunile mai vechi ale sistemului.

Nucleul incarca un fisier executabil in memorie prin apelul sistem exec, iar procesul incarcat consta din cel putin trei parti numite regiuni : text, date si stiva. Regiunile de text si date corespund sectiunilor de text si date bss ale fisierului executabil, iar regiunea de stiva este creata automat, dimensiunea ei fiind ajustata dinamic in timpul rularii. Stiva contine cadre de stiva (stack frame) logice care sunt depuse in stiva la apelarea unei functii si sunt scoase la revenirea din functie. Adancimea curenta a stivei este indicata de un registru special numit indicator de stiva (stack pointer). Un cadru de stiva contine parametrii unei functii, variabilele sale locale, si datele necesare revenirii la cadrul anterior printre care valorile contorului de program (program counter) si indicatorul de stiva din momentul apelului functiei. Codul programului contine secvente de instructiuni care gestioneaza dimensiunea stivei, iar nucleul aloca spatiu pentru stiva conform necesitatilor. In programul din figura 1.3, parametrii argc si argv si variabilele fdold si fdnew din functia main apar in stiva cand aceasta este apelata (o singura data in orice program), iar parametrii old si new si variabila count din functia copy apar in stiva la fiecare apel al functiei copy.

Deoarece un proces in sistemul UNIX se poate executa in doua moduri, nucleu si utilizator, se folosesc stive separate pentru fiecare mod. Stiva utilizator contine argumentele, variabilele locale si alte date necesare pentru executia functiilor in modul utilizator.

Figura 2.4. Stivele utilizator si nucleu pentru programul

Copy

In partea stanga a figurii 2.4. este reprezentata stiva utilizator pentru procesul care executa apelul sistem write din programul copy. Procedura de inceput a procesului (inclusa intr-o biblioteca) a apelat functia main cu doi parametri, depunand cadrul 1 in stiva utilizator; cadrul 1 contine spatiu pentru cele doua variabile locale ale functiei main. Apoi, main apeleaza copy cu doi parametri: old si new si depune cadrul 2 in stiva utilizator; acest cadru contine spatiu pentru variabila locala count. In final, procesul invoca apelul sistem write apeland functia de biblioteca write. Fiecare apel sistem are un punct de intrare intr-o biblioteca de apeluri sistem, care este codificata in limbaj de asamblare, si contine instructiuni speciale trap care, atunci cand sunt executate, determina o intrerupere care conduce la comutarea hardware-ului in modul nucleu. Un proces apeleaza punctul de intrare in biblioteca pentru un anumit apel sistem in acelasi fel cum apeleaza orice functie, creand un cadru pe stiva pentru functia de biblioteca. Cand procesul executa instructiuni speciale, el comuta in modul nucleu, executa codul nucleu si foloseste stiva nucleu.

Stiva nucleu contine cadre pentru functii ce se executa in modul nucleu. Intrarile de date si functiile din stiva nucleu se refera la functiile si datele din nucleu, nu din programul utilizator, insa constructia stivei nucleu este similara cu aceea a stivei utilizator. Stiva nucleu a unui proces este vida cand procesul se executa in modul utilizator. In partea dreapta a figurii 2.4 este prezentata stiva nucleu pentru un proces care executa apelul sistem write din programul copy.

Fiecarui proces i se aloca o zona utilizator U area care contine date proprii manipulate numai de nucleu, si o intrare in tabela de procese din nucleu. Tabela de procese pointeaza catre tabela privata de regiuni ,specifica fiecarui proces, ale carei intrari pointeaza catre intrarile din tabela de regiuni.

O regiune este o zona continua din spatiul de adrese al procesului cum ar fi zona de text, de date, sau de stiva. Intrarile din tabela de regiuni contin atributele regiunii: daca contine text sau date, daca este partajata sau privata, cat si localizarea in memorie a continutului regiunii. nivelul suplimentar de indirectare (de la tabela privata de regiuni la tabela globala de regiuni) permite partajarea regiunilor de catre procese independente. Cand un proces invoca apelul sistem exec, nucleul aloca regiuni pentru textul, datele si stiva acestuia dupa ce elibereaza vechile regiuni pe care procesul le-a utilizat. Cand un proces invoca apelul fork, nucleul duplica spatiul de adrese al vechiului proces, permitand proceselor (tata si fiu) sa partajeze regiuni atunci cand este posibil, si facand o copie fizica cand nu este posibil acest lucru. Cand un proces invoca exit, nucleul elibereaza regiunile pe care le-a utilizat. Figura 2.5 prezinta structurile de date relevante pentru un proces aflat in executie : Tabela de procese pointeaza spre tabela privata de regiuni care contine pointeri catre intrarile din tabela de regiuni pentru regiunile de text, date si stiva ale procesului.

Figura 2.5. Structurile de date ale proceselor

Intrarea in tabela de procese si u area contin informatii de control si stare despre proces. Zona u area este o extensie a intrarii din tabela de procese (in capitolul 6 vor fi examinate diferentele dintre cele doua tabele). Campurile din tabela de procese ce vor fi discutate in capitolele urmatoare sunt:

campul de stare;

identificatori care indica proprietarul procesului (UID);

un descriptor de eveniment setat cand un proces este suspendat (in starea de asteptare);

Zona u area contine informatii referitoare la proces care sunt necesare si accesibile numai pe perioada executiei acestuia. Campurile importante sunt:

un pointer catre slotul din tabela de procese al procesului in curs de executie;

parametrii apelului sistem curent, valorile de retur si codurile de eroare;

descriptorii de fisiere pentru toate fisierele deschise de proces;

parametri interni de I/O;

directorul curent si radacina curenta;

dimensiunile limita ale procesului si fisierului.

Nucleul poate accesa direct campurile din u area ale procesului in executie, insa nu si zona u area a altor procese. Intern, nucleul refera variabila structurala u pentru a accesa zona u area a procesului aflat in executie, iar cand se executa alt proces, nucleul rearanjeaza spatiul sau de adrese virtuale astfel incat variabila u sa refere zona U area a noului proces. Implementarea ofera nucleului o cale simpla de identificare a procesului curent - u area pointeaza catre intrarea corespunzatoare din tabela de procese.

Contextul unui proces

Contextul unui proces este starea sa, definita de textul sau, valorile structurilor de date si a variabilelor sale utilizator globale, valorile registrilor masina folositi de el, valorile memorate in slotul sau din tabela de procese si u area, precum si continutul stivelor sale utilizator si nucleu. Textul (codul) sistemului de operare si structurile sale de date globale sunt partajate de catre toate procesele, dar nu fac parte din contextului vreunui proces.

Cand se ruleaza un proces, sistemul se executa in contextul procesului. Cand nucleul decide ca trebuie executat alt proces, face o schimbare de context , astfel incat sistemul ruleaza in contextul altui proces. nucleul permite o schimbare a contextului numai in anumite conditii. Cand se face o schimbare de context, nucleul salveaza informatiile necesare revenirii ulterioare la procesul respectiv si continuarii executiei sale. In mod similar, la trecerea din modul utilizator in modul nucleu, nucleul salveaza informatiile ce ii vor permite reintoarcerea ulterioara in modul utilizator si continuarea executiei din locul in care a avut loc schimbarea modului. Analizand figura 1.5, nucleul face o schimbare de context, de la procesul A la procesul B; schimbarea modului de executie se executa in contextul unui proces, procesul A.

nucleul serveste intreruperile in contextul procesului intrerupt chiar daca nu acesta a cauzat intreruperea. Procesul intrerupt poate fi executat in modul utilizator sau nucleu. nucleul salveaza informatiile necesare pentru a putea relua executia procesului intrerupt si serveste intreruperea in modul nucleu. Pentru tratarea intreruperilor, nucleul nu da nastere si nu planifica vreun proces special.

Starile procesului

Timpul de viata al unui proces poate fi divizat intr-un set de stari, fiecare avand anumite caracteristici care descriu procesul. Capitolul 7 va descrie toate starile procesului, insa este esential sa se intelega pentru moment urmatoarele stari:

Procesul se executa in modul utilizator (user running).

Procesul se executa in modul nucleu (kernel running).

Procesul nu se executa, dar este gata de executie (ready to run) imediat ce planificatorul il alege. Mai multe procese pot fi in aceasta stare, dar algoritmul de planificare determina care dintre ele se va executa.

Procesul se pune in asteptare (sleep). Un proces se pune in asteptare cand nu mai poate continua executia (de exemplu cand asteapta incheierea unei operatii I/O

Deoarece un procesor poate executa numai un proces la un moment dat, cel mult un proces poate fi in starile 1 sau 2. Cele doua stari corespund celor doua moduri de executie, utilizator si nucleu.

Tranzitia starilor

Starile proceselor descrise mai inainte ofera o imagine statica asupra unui proces, dar procesele isi modifica in mod continuu starile conform unor reguli bine definite.

O diagrama de tranzitie a starilor este un graf orientat ale carui noduri reprezinta starile unui proces iar arcele reprezinta evenimentele care determina trecerea unui proces dintr-o stare in alta. Tranzitia dintr-o stare in alta este posibila numai daca intre ele exista un arc de la prima stare spre a doua. Exista posibilitatea ca dintr-o stare sa se treaca in mai multe stari, insa procesul va trece intr-o singura stare determinata de evenimentul sistem ce are loc. Figura 2.6 prezinta diagrama de tranzitie a starilor pentru starile definite anterior.

Mai multe procese se pot executa simultan prin partajarea in timp a resurselor (intr-o maniera 'time-sharred') si pot rula concomitent in modul nucleu. Daca s-ar permite rularea in modul nucleu fara restrictii, s-ar putea altera structurile de date globale ale nucleului. Prin interzicerea comutarii arbitrare a contextului si controlul aparitiei intreruperilor, nucleul isi protejeaza consistenta.

Nucleul permite schimbarea contextului numai cand procesul trece din starea executie in modul nucleu in starea in starea asteptare in memorie. Desi sistemul poate intrerupe procesele care sunt executate in modul utilizator, procesul care ruleaza in modul nucleu nu poate fi intrerupt de alte procese; prin urmare nucleul este numit adesea non-preemtiv.

Figura 2.6. Starile si tranzitiile procesului

Deoarece este non-preemtiv, nucleul pastreaza consistenta structurilor sale de date, rezolvandu-se prin aceasta problema excluziunii mutuale (sectiunile critice de cod sa fie executate de cel mult un proces la un moment dat).

De exemplu, considerand codul din figura 2.7 care insereaza o structura de date a carei adresa este in pointerul bp1 intr-o lista dublu inlantuita dupa structura a carei adresa este in bp. Daca sistemul permite comutarea contextului in timp ce nucleul executa fragmentul de cod, se poate produce urmatoarea situatie. Presupunem ca nucleul executa codul pana la comentariu si apoi face o schimbare de context. Lista dublu inlantuita este in stare de inconsistenta: structura bp1 este pe jumatate in lista inlantuita. Daca un proces va folosi pointerul de legatura spre dreapta, va gasi bp1 in lista, daca insa va folosi pointerul de legatura spre stanga nu va gasi bp1 (Figura 2.8).

Daca alte procese ar manipula pointerii din lista inaintea reluarii procesului initial de inserare, lista dublu inlantuita ar putea fi distrusa definitiv. Sistemul UNIX previne astfel de situatii prin interzicerea comutarii de context atunci cand un proces se executa in modul nucleu. Daca un proces intra in starea sleep, fapt ce permite comutarea de context, algoritmii nucleului sunt coceputi in asa fel incat sa asigure consistenta structurilor de date din sistem.

O problema similara ce poate determina inconsistenta datelor nucleului o constituie tratarea intreruperilor, care pot modifica informatiile de stare ale nucleului. De exemplu, daca nucleul executa codul din figura 2.7 si primeste o intrerupere cand ajunge la comentariu, rutina de tratare a intreruperii poate deteriora legaturile daca manipuleaza pointerii, dupa cum s-a aratat.

struct queue *bp,*bp1;

bp1 ->forp = bp ->forp;

bp1 ->backp = bp;

bp ->forp = bp1;

/*consideram ca aici are loc o schimbare de context */

bp1 ->forp ->backp = bp1;

Figura 2.7. Cod simplu de creare a unei liste dublu inlantuite

O solutie pentru a rezolva aceasta problema, ar fi ignorarea de catre sistem a tuturor cererilor de intrerupere cand se lucreaza in modul nucleu, insa aceasta poate determina intarzierea servirii unor intreruperi critice, cu consecinte grave asupra sistemului.

Figura 2.8. Lista inlantuita incorect datorita schimbarii

contextului

Alta solutie o constituie, ridicarea nivelului de executie al procesorului de catre nucleu cand se ajunge in regiunea critica de cod. O sectiune de cod este critica daca executia unei rutine de tratare a intreruperii poate genera probleme de inconsistenta a datelor.De exemplu, daca rutina de tratare a intreruperii de disc manipuleaza cozile de buffere din figura, sectiunea de cod unde nucleul manipuleaza aceste cozi este o sectiune critica. Regiunile critice sunt rare si de dimensiuni reduse, astfel incit sistemul este foarte putin afectat de acestea. Unele sisteme de operare rezolva aceasta problema prin evitarea tuturor intreruperilor pe timpul executiei in starile sistem, sau prin utilizarea unor scheme de blocare care asigura consistenta datelor.

Sleep si wake up

Un proces care se executa in modul nucleu are libertatea de a alege modul in care reactioneaza la evenimentele ce apar in sistem. Procesele pot comunica intre ele si isi pot 'sugera' diferite alternative, insa ele iau singure decizia finala. Asa cum se va vedea, exista un set de reguli pe care procesele le respecta cand se confrunta cu diferite situatii, dar in ultima instanta, fiecare proces urmeaza din proprie initiativa aceste reguli. De exemplu, cand un proces trebuie sa-si suspende temporar executia (se pune in asteptare), el o face din proprie initiativa. Astfel, o rutina de tratare a intreruperii nu se poate pune in asteptare, deoarece in acest caz, procesul intrerupt ar intra implicit in starea de asteptare.

Procesele intra in starea de asteptare deoarece asteapta aparitia unui eveniment, de exemplu terminarea unei operatii de I/O de la un dispozitiv periferic, terminarea unui proces, eliberarea unor resurse sistem, si altele.

Se poate intampla ca mai multe procese sa fie in asteptarea aceluiasi eveniment , iar la aparitia acestuia se trezesc. Cand un proces se trezeste, el nu trece din starea de asteptare in starea executie in modul nucleu, ci in starea gata de executie asteptand sa fie planificat pentru a se executa. Procesele aflate in asteptare nu consuma resurse U.C.P. nucleul nu verifica in mod constant daca un proces mai este in starea sleep sau nu, dar asteapta producerea evenimentului ce determina trezirea procesului.

De exemplu, un proces caree se executa in mod nucleu poate uneori bloca o structura de date in cazul in care intra in asteptare. Procesele care incearca sa foloseasca aceasta structura trebuie sa verifice acest lucru si sa intre in asteptare daca gasesc blocata stuctura respectiva. nucleul implementeaza aceste blocari in modul urmator:

while (condittia este adevarata)

sleep (eveniment: conditia devine falsa);

conditia este stabilita la valoarea adevarat;

El deblocheaza structura blocata si trezeste toate procesele care asteapta deblocarea acesteia dupa cum urmeaza:

conditia se stabileste la valoarea fals;

wakeup (eveniment: conditia este falsa);

Figura 2.9 descrie un exemplu in care trei procese A, B si C isi disputa un buffer blocat. Blocarea buffer-ului constituie conditia de punere in asteptare.

Procesele, se executa cate unul la un moment dat, gasesc buffer-ul blocat si se pun in asteptare pana la deblocarea buffer-ului. Cand buffer-ul este deblocat, toate procesele se trezesc si intra in starea gata de executie.

Proces A Proces B Proces C

Buffer blocat

Asteptare

:

: Buffer blocat

: Asteptare

: :

: : Buffer blocat

: : Asteptare

Buffer-ul este deblocat Trezirea tuturor proceselor care

asteapta acest eveniment

Gata de executie Gata de executie Gata de executie

: Ruleaza :

: Buffer deblocat :

: Blocare buffer :

: : :

: Asteapta dintr-un motiv oarecare

: : :

Ruleaza : :

Buffer blocat : :

Asteptare : :

: : :

: : Ruleaza : : Buffer blocat : : Asteptare : : :

: Trezire :

: Deblocare buffer :

Gata de executie Trezirea tuturor Gata de executie

: proceselor care dorm :

: Eventual comutare de context :

Ruleaza : :

Timp

Figura 2.9. Cazul mai multor procese concurente la

aceeasi resursa

Nucleul alege (de exemplu) procesul B sa se execute. Procesul B executa ciclul "while", gaseste buffer deblocat, il blocheaza, dupa care continua. "while", gaseste buffer blocat si intra din nou in starea sleep; procesul C poate face acelasi lucru. Cand procesul B se trezeste si deblocheaza buffer, permite celorlalte procese, A si C, sa acceseze din nou buffer. Astfel, ciclul 'while-sleep' permite cel mult unui proces accesul la o resursa.

Capitolul 6 va prezenta mai detaliat algoritmii sleep si wake-up. Acestia vor fi considerati deocamdata 'atomici'. Un proces intra imediat in starea sleep si sta aici pana cand este trezit. Dupa ce intra in starea de asteptare, nucleul planifica alt proces pentru a rula si comuta contextul.