Implementarea Proceselor in Unix

2.2. IMPLEMENTAREA PROCESELOR N UNIX

Structurile de date folosite de nucleu pentru gestiunea proceselor sunt :

structura de proces (1 per proces) care con(ine c(mpuri ce trebuie s( fie accesibile nucleului tot timpul :

parametrii pentru planificare : prioritatea, timpul de UCP consumat recent, timpul ct a stat n starea suspendat ultima oar; toate acestea sunt folosite pentru a stabili care proces se selecteaz pentru rulare;

imaginea n memorie : pointeri ctre tabela de pagini asociat procesului, n cazul n care procesul este rezident n memoria principal sau adresa pe dispozitivul de swap (disc);

semnale : un c(mp pentru semnale care arat( semnalele primite de proces dar netratate (nc(;

alte informaii : identificatorul de proces, identificatorii de utilizator i grup efectivi, identificatorul procesului printe, starea curent a procesului, evenimentul pe care l ateapt.

structura utilizator (1 per proces) care con(ine c(mpuri necesare doar (n timpul cnd procesul se afl n starea de execuie:

pointer spre structura de proces;

toi identificatorii de grup sau de utilizator asociai procesului;

un tablou, fiecare element indic(nd modul (n care procesul va reac(iona la semnalul corespunz(tor (ignorare, tratare, terminare proces);

terminalul de control identificat ca "terminalul de login" asociat procesului, dac( exist( vreunul;

parametrii (i rezultatele/erorile apelurilor sistem;

pointer ctre inodul directorului curent (i c(tre inod-ul directorului r(d(cin( (root);

o copie a regitrilor generali, a indicatorului de stiv (SP), a numrtorului de instruciuni (PC) care este scris n momentul comutrii din modul utilizator n modul nucleu;

informaii privind tabela de fiiere deschise;

tabela de regiuni (1 per proces), (n care fiecare element con(ine date despre o regiune:

un pointer c(tre inod-ul fi(ierului care este (nc(rcat (n regiune ((n cazul regiunilor de tip text);

tipul regiunii : text (cod), memorie comun( (date comune), date private sau stiv(;

localizarea regiunii (n memoria fizic(;

dimensiunea regiunii ((n Ko) (i un c(mp care indic( tipul de acces permis procesului (read-only, read-write, read-execute);

starea regiunii, care poate s( fie o combina(ie de :

blocat;

n acces (n cerere);

tocmai se ncarc n memorie;

valid (a fost deja ncrcat n memorie);

adresa tabelei de pagini;

adresa virtual de nceput a regiunii;

Obs. : Regiunile partajate pot avea adrese virtuale diferite (n fiecare proces

Fiecare proces are att o faz utilizator (lucreaz n mod utilizator), ct i o faz sistem (lucreaz n mod sistem, nucleu). Instruciunile obinuite sunt executate n mod utilizator, iar apelurile sistem n mod sistem. Corespunztor, procesului i sunt asociate dou stive.

Comutarea ntre modul utilizator i sistem se realizeaz n cazurile :

- generare excepie;

- apelurile sistem prin care utilizatorul solicit diverse servicii oferite de sistemul de operare; cele care realizeaz operaii de intrare/ieire conduc la suspendarea procesului apelant pe durata transmiterii datelor;

- sosire (ntreruperi de la periferice.

Nucleul p(streaz( intern o tabel( a proceselor active ce con(ine structurile de proces ale proceselor active, indiferent dac( ele sunt (n memorie sau pe disc ((n urma procesului de swapping). De asemenea, p(streaz( intern (i o tabel( de regiuni.

Cu ajutorul apelului sistem fork() se creeaz( un nou proces astfel :

- se aloc( procesului nou (numit proces fiu) o intrare liber( din tabela de procese;

- se asigneaz( un ID unic procesului fiu;

- se completeaz( c(mpurile structurii de proces a procesului fiu (multe sunt copiate de la procesul p(rinte : grupul p(rintelui, UID-urile real (i efectiv, valoare nice a p(rintelui etc.). Nucleul ini(ializeaz( parametrii pentru planificare : valoarea ini(ial( a priorit((ii, folosirea UCP-ului etc.;

- se aloc( memorie pentru regiunile de date (i stiv(, copiindu-se con(inutul celor corespunz(toare p(rintelui. (n mod obi(nuit, nu este necesar( alocarea unei zone pentru cod, deoarece se partajeaz( cel existent;

- dac( sistemul lucreaz( cu memorie paginat(, vor fi construite noi tabele de pagini pentru regiunile de date (i stiv(;

- se aloc( memorie pentru structura utilizator (i se copiaz( informa(iile din structura utilizator a p(rintelui. Astfel, vor fi p(strate valorile descriptorilor fi(ierelor deschise.

Pentru procesele aflate (n starea SUSPENDAT, nucleul folose(te o structur( pentru asocierea (ntre setul de evenimente (i setul de adrese virtuale ale rutinelor ce trateaz( evenimentul.

De(i apare rar, se poate (nt(mpla ca mai multe evenimente s( fie mapate la aceea(i adres(.

C(nd apare un eveniment, TOATE procesele suspendate pe acel eveniment vor fi trezite (i trecute (n starea PREG(TIT. Doar unul dintre ele va beneficia de evenimentul recent produs, celelalte trec(nd din nou (n starea SUSPENDAT, a(tept(nd o nou( apari(ie a evenimentului.

(n tabela de procese, primele intr(ri sunt ocupate de procesele nucleului :

- 0 - swapper- 1 - init- 2 - page daemon2.3. PLANIFICAREA PROCESELOR

Cnd dou sau mai multe procese sunt n starea PREGTIT i deci candideaz pentru execuie, sistemul de operare trebuie s decid cruia i aloc UCP-ul. Acea parte din sistemul de operare care se ocup cu luarea acestei decizii se numete planificator , iar algoritmul folosit, algoritm de planificare.

n cazul sistemelor de prelucrare n loturi (batch systems), algoritmul era foarte simplu : se executa urmtoarea lucrare de pe band. n cazul sistemelor multiutilizator cu partajarea timpului, algoritmul este mult mai complex.

Criteriile ce se iau n considerare la definirea performanei unui algoritm de planificare pot fi :

1. utilizarea UCP-ului;

2. timpul de prelucrare;

3. timpul de ateptare;

4. timpul de rspuns.

Utilizarea UCP-ului reprezint fraciunea din timp ct UCP este ocupat. Uneori se ia n considerare timpul alocat att pentru programele utilizator ct i pentru cele sistem, alteori numai pentru programele utilizator (useful work). Scopul este de a ine UCP-ul ct mai mult timp ocupat, crescnd astfel performana sistemului.

Timpul de prelucrare poate fi definit ca timpul care se scurge ntre momentul cnd programul este lansat n execuie i momentul terminrii lui.

Timpul de ateptare este timpul ct un program, pe durata execuiei sale, ateapt alocarea resurselor necesare. Poate fi exprimat ca diferena dintre timpul de prelucrare i timpul efectiv de execuie.

Timpul de rspuns este utilizat cel mai frecvent de ctre sistemele de operare de timp real sau cu partajarea timpului. Definiiile difer pentru cele dou tipuri de sisteme. Astfel, la sistemele cu partajarea timpului poate fi definit, de ex., ca timpul care se scurge din momentul scrierii ultimului caracter al liniei de comand pn cnd primul rezultat apare la terminal (se mai numete timp de rspuns la un teminal). La sistemele n timp real, poate fi definit ca timpul dintre momentul n care apare un eveniment i momentul cnd este executat prima instruciune a rutinei de tratare (se mai numete timp de rspuns la un eveniment) .

Planificatoarele caut s maximizeze performana medie relativ la un anumit criteriu. Una dintre problemele ntlnite la proiectarea planificatorului este aceea c unele criterii sunt n contradicie cu altele. De exemplu,un timp de rspuns ct mai bun poate duce la scderea utilizrii UCP-ului. Mrind utilizarea UCP-ului i viteza de prelucrare, timpul de rspuns poate avea de suferit. De aceea, proiectanii ncearc s maximizeze performanele relativ la criteriul cel mai important pentru mediul de lucru (planificatoarele sunt dependente de mediu). De exemplu, pentru sistemele cu prelucrare n loturi, intereseaz utilizarea UCP-ului; la sistemele multiutilizator, timpul de rspuns; la sistemele n timp real, s rspund corespunztor multitudinii de evenimente externe.

Algoritmii de planificare pot fi preemptivi sau non-preemptivi.

n cazul non-preemptiv, controlul este cedat sistemului de operare n momentul n care n procesul curent n execuie apare o instruciune de acest gen sau dac procesul ateapt terminarea unei operaii I/O. Deci procesul curent activ nu poate fi nlocuit cu un alt proces aflat n starea pregtit av(nd prioritate mai mare.

n cazul preemptiv, procesul aflat n execuie poate fi nlocuit oricnd cu un alt proces cu prioritate mai mare. Acest lucru este realizat prin activarea planificatorului ori de cte ori este detectat un eveniment ce schimb starea global a sistemului.

Indiferent dac algoritmul este preemptiv sau nu, comutarea de procese presupune salvarea strii procesului fost n execuie, precum i crearea mediului de execuie a noului proces ales a fi executat, ceea ce necesit mult timp. n general, sistemele de tip preemptiv pot furniza un timp de rspuns mai bun, dar consum mult timp cu execuia planificatorului i comutarea proceselor asociate.

Pentru p(strarea consisten(ei structurilor de date interne ale nucleului, un proces utilizator rul(nd (n mod nucleu nu poate fi ntrerupt i (nlocuit (preemted) de un alt proces, ci numai c(nd ruleaz( (n mod utilizator (nucleul ruleaz( non-preemtiv).

(n plus, nucleul cre(te nivelul de execu(ie al procesorului atunci c(nd execut( regiuni critice (ex.: modificare pointeri la liste dublu (nl(n(uite, (n cazul citirii datelor de pe disc) pentru a preveni ca anumite (ntreruperi s(-i cauzeze inconsisten(e ale datelor.

2.3.1. Mecanismul de planificare round-robin

n cazul sistemelor cu partajarea timpului, prima cerin este ca sistemul s furnizeze un timp de rspuns rezonabil i, n general, s partajeze echitabil resursele sistemului ntre toi utilizatorii. Evident, numai disciplinele de planificare preemptive pot fi luate n considerare n astfel de situaii, una dintre cele mai populare fiind round-robin.

Timpul UCP-ului este mprit n cuante, de obicei ntre 10 i 100 msec., care se aloc proceselor. Nici un proces nu poate rula mai mult de o cuant, att timp ct mai sunt procese n sistem ce ateapt s fie executate. Structura de date folosit este o coad a proceselor gata de execuie (aflate n starea pregtit). Cnd cuanta s-a terminat, UCP-ul este alocat unui alt proces (primul din coad). Acelai lucru se ntmpl i n cazul cnd procesul este suspendat sau i-a terminat activitatea naintea expirrii cuantei. Astfel, fiecare proces are alocat 1/N din timpul UCP-ului, unde N este numrul proceselor din sistem.

Round-robin asigur partajarea echitabil a resurselor sistemului ntre procese. Procesele scurte se pot termina ntr-o singur cuant, obinndu-se astfel un timp de rspuns bun. Procesele lungi au nevoie de mai multe cuante de timp, ciclnd n coad pn cnd se termin.

Din punct de vedere hardware, se folosete un timer care genereaz o ntrerupere dup trecerea unui interval de timp egal cu o cuant. Cnd sosete ntreruperea, sistemul de operare lanseaz planificatorul pentru comutarea proceselor. Intervalul de timp este resetat naintea execuiei noului proces ales din coad.

Performana acestui mecanism depinde foarte mult de valoarea cuantei. Astfel, o valoare mic avantajeaz procesele interactive, dar scade eficiena UCP-ului, acesta ocupndu-se mult timp cu tratarea ntreruperii sosite de la timer i cu comutarea proceselor. O valoare mare crete eficiena UCP-ului, dar poate determina un timp de rspuns mare, dezavantajnd procesele interactive (ex.: mai muli utilizatori apas n acelai timp pe o tast). O cuant de 100 msec. realizeaz un compromis bun.

Algoritmul de planificare round-robin se recomand a se folosi n cazul sistemelor multiutilizator, cu partajarea timpului, unde timpul de rspuns conteaz foarte mult.

2.3.2. Mecanismul de planificare bazat pe prioriti

(de tip preemptiv)

Algoritmul round-robin presupune c toate procesele sunt la fel de importante, ceea ce nu este ntotdeauna adevrat. Pentru departajarea proceselor n funcie de importan, se folosesc prioriti acordate fiecrui proces n parte, sistemul rulnd ntotdeauna procesul cu cea mai mare prioritate din sistem.

Pentru a preveni ca procesele cu cea mai mare prioritate s ruleze tot timpul, planificatorul poate scade prioritatea procesului curent n execuie la fiecare ntrerupere de ceas. Cnd prioritatea procesului n execuie a devenit mai mic dect prioritatea unui alt proces, sistemul de operare comut ntre ele.

Prioritile pot fi asignate static sau dinamic. Static, se acord de ctre utilizator sau de ctre sistem, la creare. Dinamic, se asigneaz de ctre sistemul de operare, pentru realizarea unui anumit scop. De exemplu, unele procese lucreaz foarte mult cu sistemul I/O. Ori de cte ori un astfel de proces cere UCP, ar trebui s i se acorde imediat, pentru a lansa urmtoarea cerere I/O, care astfel se va executa n paralel cu execuia unui alt proces de ctre UCP (altfel ocup memoria prea mult timp). Un algoritm simplu pentru a oferi un serviciu bun proceselor orientate spre I/O este de a seta prioritatea la 1/f, unde f reprezint fraciunea de timp ocupat cu UCP din ultima cuant.

Se recomand n sisteme de timp real i alte sisteme care presupun rspuns ntr-un interval de timp (time-critical requirements).

2.3.3. Mecanismul de planificare utiliznd cozi multiple

Algoritmii descrii mai sus caracterizeaz aplicaii particulare, fiind n general ineficieni n alte situaii. Considerm, de ex., un sistem n care avem evenimente care cer tratare ntr-un anumit interval de timp (time-critical events), o multitudine de utilizatori interactivi i unele programe lungi i neinteractive. (n acest caz, se recomand combinarea algoritmilor de planificare. Rezult astfel planificarea cu cozi multiple, n care fiecare coad corespunde unui algoritm de planificare. Pentru exemplul de mai sus vom obine trei cozi, ca n figur : (fig2_8.bmp)

Cozile pot fi gestionate prin round-robin sau bazat pe prioriti.

n cazul gestionrii bazate pe prioriti, sunt servite mai nti procesele din coada cu prioritatea cea mai mare, folosind algoritmul de planificare corespunztor cozii respective. Cnd aceasta devine vid, se trece la urmtoarea coad ca nivel de prioritate. Un proces n execuie poate fi ntrerupt de un alt proces ce sosete ntr-o coad cu prioritate mai mare.

O variant a acestui algoritm este algoritmul cu cozi multiple i reacie negativ (multiple-level queues with feedback). Un proces poate trece dintr-o coad n alta (schimbndu-i-se astfel prioritatea), pe baza comportrii n timpul execuiei din cuanta anterioar. De exemplu, fiecare proces ncepe cu prioritate maxim (este trecut automat n coada cu prioritate maxim). Procesele ce au nevoie de mai mult de o cuant pentru terminare, sunt mutate ntr-o coad de nivel mai mic. Dac procesul nu s-a terminat dup cteva rulri n aceast coad, este mutat ntr-o coad de nivel i mai mic. Pe de alt parte, dac procesul cedeaz voluntar controlul sistemului de operare, este mutat ntr-o coad de nivel mai nalt.

Ideea este de a acorda un tratament preferenial proceselor scurte i de a scufunda procesele consumatoare de resurse n cozi de nivele din ce n ce mai mici, fiind folosite pentru a umple timpul UCP-ului i deci pentru a menine un grad nalt de utilizare a UCP-ului.

(n cazul sistemelor (n timp real, nucleul trebuie s( fie capabil s( furnizeze r(spuns imediat unor evenimente externe, adic( s( fie capabil s( ruleze un anumit proces (ntr-un anumit interval de timp de la apari(ia evenimentului. Ex.: un calculator ce asigur( supravegherea unor sisteme de men(inere a vie(ii (ntr-un spital.

O alt( caracteristic( a sistemelor (n timp real este c( nucleul este non-preemptiv (nu poate fi lansat (n execu(ie un alt proces asociat unui eveniment care tocmaia ap(rut p(n( c(nd procesul curent, asociat unui eveniment asociat anterior, nu se va termina).

De aceea, algoritmii de planificare prezenta(i mai sus nu pot fi utiliza(i (n sisteme (n timp real.

2.3.4. Implementare n UNIX

(ntr-un sistem cu partajarea timpului, nucleul aloc( UCP unui proces pentru o anumit( perioad( de timp, numit( cuant( de timp, cuprins( (ntre 0 (i 1 s; de obicei, (n sistemul Unix este de 100 ms. Func(ia de planificare din sistemul Unix folose(te timpul de execu(ie pentru a determina procesul ce va fi lansat (n execu(ie la o comutare de context. Procesele au asociate priorit((i, valorile mari corespunz(nd priorit((ilor sc(zute.

La expirarea cuantei procesului curent n execuie, se va alege procesul aflat (n starea PREG(TIT cu prioritatea cea mai mare. Nucleul recalculeaz( prioritatea unui proces c(nd acesta revine din modul nucleu (n modul utilizator (i, periodic, ajusteaz( priorit((ile proceselor aflate (n starea PREG(TIT (i (n modul utilizator.

Pentru planificare se folose(te mecanismul cu cozi multiple. Fiecare coad( este asociat( cu un nivel de prioritate. Alegerea (n cadrul cozii se face fie utiliz(nd mecanismul round-robin, fie va fi ales procesul care a stat cel mai mult timp (n starea PREG(TIT (adic( (n func(ie de c(t de mult a a(teptat alocarea UCP-ului).

Dac( (n sistem nu exist( nici un proces (n starea PREG(TIT, procesorul st( (starea idle) p(n( la urm(toarea (ntrerupere (adic( cel mult p(n( la urm(toarea (ntrerupere de ceas). Dup( tratarea (ntreruperii, nucleul verific( dac( sunt procese de rulat.

Parametrii folosi(i la planificare. Fiecare structur( de proces con(ine un c(mp de prioritate folosit la planificare. Prioritatea unui proces (n mod utilizator este (n func(ie de c(t timp a utilizat UCP ultima dat( : cu c(t utilizeaz( mai mult UCP-ul, cu at(t prioritatea scade => asigur( un serviciu bun pentru procesele interactive. Domeniul de valori al priorit((ilor poate fi (mp(r(it (n dou( clase :

priorit((ile proceselor ce ruleaz( (n mod utilizator;

priorit((ile proceselor ce ruleaz( (n mod nucleu.

Priorit((ile nucleu sunt subdivizate. Procesele cu priorit((i nucleu mici pot fi trezite la recep(ionarea unui semnal, (n timp ce procesele cu priorit((i nucleu mari vor fi trezite doar c(nd s-a produs evenimentul pe care s-au blocat (eliberarea resursei).

Nucleul calculeaz( prioritatea unui proces (n anumite st(ri ale procesului :

nucleul atribuie o prioritate unui proces c(nd trece (n starea SUSPENDAT; prioritatea are o valoare fix(, depinz(nd de motivul pentru care procesul este suspendat;

nucleul ajusteaz( prioritatea unui proces ce revine din modul nucleu (n modul utilizator. Anterior, procesul a trecut (n starea SUSPENDAT, av(nd prioritatea (n domeniul priorit((ilor nucleu (deci mai mare). C(nd revine (n modul utilizator, prioritatea (i va fi modificat( (va scade) at(t pentru a trece (n domeniul priorit((ilor utilizator c(t (i pentru a permite (i altor procese utilizator accesul la resursele sistemului;

rutina de tratare a (ntreruperii de ceas va ajusta priorit((ile tuturor proceselor utilizator la interval de 1s (la System V), prevenind astfel ca un proces s( monopolizeze UCP-ul.

Ceasul poate (ntrerupe un proces aflat n execuie de mai multe ori pe parcursul unei cuante. La fiecare (ntrerupere de ceas, pentru procesul aflat (n execu(ie este incrementat un c(mp din structura de proces corespunz(toare, c(mp ce exprim( folosirea UCP-ului. (n plus, la fiecare secund(, pentru toate procesele din sistem rutina de ceas ajusteaz( acest c(mp (s(-l not(m ucp) astfel :

ucp = ucp/2;

(la System V)

(i recalculeaz( prioritatea fiec(rui proces aflat (n starea PREG(TIT :

prio = ucp/2 + prio_prag

unde prio_prag este valoarea priorit((ii care desparte priorit((ile nucleu de priorit((ile utilizator.

(n urma acestei recalcul(ri cozile cu procese utilizator vor fi modificate.

Procesele interactive, deoarece lucreaz( pu(in cu UCP, vor fi mutate (n cozi cu prioritate mare, asigur(ndu-li-se astfel o bun( servire.

Unele implement(ri ale mecanismului de planificare modific( dinamic cuanta de timp, (n func(ie de (nc(rcarea sistemului. Avantajul este c( procesele pot fi rulate mai des. Dezavantaj : cresc cheltuielile de regie (comut(rile de context sunt mai dese).

Controlul priorit((ii unui proces se face prin apelul sistem :

int nice (int valoare);

Argumentul valoare poate fi pozitiv sau negativ.

(n acest caz prioritatea procesului se calculeaz( :

prio = ucp/2 + val_prag + valoare_nice

Doar utilizatorul root (superuser) poate folosi valori negative pentru argumentul valoare (adic( s( creasc( prioritatea procesului).

Procesele fiu mo(tenesc valoarea nice de la p(rinte ((n cadrul apelului sistem fork). Apelul sistem nice are efect doar pentru procesul care (l apeleaz(; un proces nu poate modifica valoare nice a altui proces.

e

proces p(rinteproces fiu

Tabela de regiuni per proces

(adrese virtuale)

coddatestiv(

coddatestiv(

a

b

c

d

Memoria fizic(

structura utilizator a

procesului fiu

structura utilizator a

procesului p(rinte

Tabela de procese a nucleului

proces A

proces B

a(teapt( terminarea unei opera(ii I/O

a(teapt( umplerea buffer-ului

adresa C

proces C

a(teapt( datele de la un terminal

adresa D

SwapperA(teapt( terminarea unei op.I/O cu disculA(teapt( alocarea unui inodA(teapt( citirea datelor de la un terminalA(teapt( scrierea datelor la un terminalA(teapt( terminarea procesului fiuPriorit((i utilizator de nivel 0Priorit((i utilizator de nivel 1.

.Priorit((i utilizator de nivel n

Priorit((i (n mod nucleu

Priorit((i (n mod utilizator

Prioritate de prag

Ne(ntreruptibile

(ntreruptibile

Nivele de prioritate

Procese

PAGE