Planificarea proceselor - UNIX

Planificarea proceselor - UNIX

Planificatorul din sistemul UNIX apartine clasei generale de planificatoare din sistemele de operare cunoscute sub numele lista circulara de procese cu mai multe nivele de reactie inversa, ceea ce inseamna ca nucleul aloca UCP unui proces pentru o cuanta de timp, intrerupe procesul care isi depaseste cuanta de timp si il depune intr-una din cozile de prioritati. Un proces poate avea nevoie de mai multe iteratii prin "bucla de reactie" inainte ca el sa-si termine executia.

Atunci cand nucleul executa o comutare de context si restaureaza contextul unui proces, acesta isi continua executia din punctul in care a fost suspendat.

Figura Algoritm pentru planificarea proceselor

1 Algoritmul

La concluzia ca trebuie sa se execute o comutare de context, nucleul executa algoritmul de planificare a unui proces (figura 9.1), selectand procesul cu cea mai mare prioritate din cele care se afla in starile "gata de executie si incarcat in memorie" si "intrerupt". Nu are nici un sens selectarea unui proces daca nu este incarcat in memorie, deoarece acesta nu poate fi executat. Daca mai multe procese au cea mai mare prioritate, nucleul alege acel proces care a fost pentru cea mai lunga perioada de timp in starea "gata de executie", conform politicii de planificare a listei circulare. Daca nu exista nici un proces eligibil pentru a fi executat, procesorul nu face nimic pana la urmatoarea intrerupere de ceas; dupa tratarea intreruperii, nucleul incearca din nou sa planifice un proces.

2. Parametri de planificare

Fiecare intrare in tabela de procese contine un camp de prioritate pentru planificare a procesului. Prioritatea unui proces in modul utilizator este functie de folosirea UCP, prin care procesul obtine o prioritate scazuta daca a folosit recent UCP. Domeniul prioritatilor procesului poate fi partitionat in doua clase (vezi figura 9.2): prioritati utilizator si prioritati nucleu. Fiecare clasa contine cateva valori de prioritate, si fiecare prioritate are o coade de procese asociata logic cu ea. Procesele cu prioritate de nivel utilizator au fost intrerupte in momentul revenirii din modul nucleu in modul utilizator, iar prioritatile de nivel nucleu sunt obtinute in cadrul algoritmului sleep. Prioritatile de nivel utilizator sunt dispuse sub o valoare de prag, iar prioritatile de nivel nucleu peste valoarea de prag. Prioritatile de nivel nucleu se subdivid la randul lor: procesele cu prioritate nucleu scazuta se trezesc la receptionarea unui semnal, iar procesele cu prioritate nucleu ridicata continua sa ramana in starea de asteptare.

Figura 9.2 prezinta prioritatea de prag dintre prioritatile utilizator si prioritatile nucleu sub forma unei linii duble intre prioritatile "asteptare pentru terminarea fiului" si "nivelul utilizator 0".

Figura 9.2 Prioritatile proceselor

Prioritatile denumite "incarcator" , "asteptare pentru I/O cu discul", "asteptare pentru eliberarea unui buffer", si "asteptare pentru eliberarea unui inode" sunt prioritati sistem de valoare inalta, neintreruptibile, cu 1, 3, 2, si 1 procese in asteptare pe nivelul de prioritate respectiv, iar prioritatile denumite "asteptare pentru intrare de la tty", "asteptare pentru iesire de la tty" si "asteptare pentru terminarea fiului" sunt prioritati sistem de valoare scazuta, intreruptibile, cu 4, 0 si 2 procese in asteptare. In figura se pot distinge prioritatile utilizator denumite "nivel utilizator 0", "nivel utilizator 1" pana la "nivel utilizator n" avand 0, 4 si 1 procese in asteptare.

Nucleul calculeaza prioritatea unui proces functie de starile specifice ale procesului.

El atribuie prioritatea unui proces care trebuie sa treaca in starea de asteptare prin corelarea unei valori de prioritate fixa cu motivul trecerii in starea de asteptare. Prioritatea nu depinde de caracteristicile run time ale procesului, ci este o valoare constanta stabilita hardware pentru fiecare apel de trecere in starea de asteptare, dependenta de motivul pentru care procesul trece in aceasta stare. Procesele care asteapta in algoritmi de nivel scazut tind sa provoace o saturare mai mare a sistemului cand sunt inactive; din aceasta cauza ele primesc o prioritate mai mare decat procesele ce pot provoca o saturare mai mica a sistemului. De exemplu, un proces care este inactiv si asteapta terminarea unei operatii I/O cu discul are o prioritate mai mare decat un proces care asteapta eliberarea unui buffer din mai multe motive. Mai intai, procesul care asteapta terminarea unei operatii I/O cu discul are deja un buffer; cand se trezeste exista o sansa mai mare sa se execute si sa elibereze buffer-ul si, posibil, alte resurse. Cu cat elibereaza mai multe resurse, cu atat mai mari sunt sansele ca alte procese sa nu se blocheze cand au nevoie de resurse. Sistemul va avea de executat mai putine comutari de context si, in consecinta, timpul de raspuns al procesului si caracteristicile sistemului sunt mai bune. In al doilea rand, un proces care asteapta un buffer liber ar putea astepta buffer-ul retinut de catre procesul care executa operatii I/O. Cand operatia I/O se termina, ambele procese se trezesc deoarece ambele asteptau la aceeasi adresa. Daca procesul care asteapta buffer-ul va rula primul, el va trece oricum din nou in starea de asteptare pana cand celalalt proces elibereaza buffer-ul; de aceea prioritatea sa este scazuta.

Nucleul ajusteaza prioritatea unui proces care revine din modul nucleu in modul utilizator. Este posibil ca procesul sa fi intrat anterior in starea de asteptare, schimbandu-si prioritatea la una de nivel nucleu, iar la intoarcerea in modul utilizator ea trebuie sa fie scazuta la o prioritate de nivel utilizator. De asemenea nucleul penalizeaza procesul care se executa in defavoarea altor procese, deoarece el tocmai a folosit resurse nucleu valoroase.

Rutina de tratare a intreruperilor de ceas ajusteaza prioritatile tuturor proceselor in mod utilizator la intervale de o secunda si determina nucleul sa execute algoritmul de planificare pentru a preveni ca un proces sa acapareze folosirea UCP.

Ceasul poate intrerupe un proces de mai multe ori pe durata cuantei sale de timp; la fiecare intrerupere de ceas, rutina de tratare a intreruperii de ceas incrementeaza un camp din tabela de procese care inregistreaza valoarea de folosire recenta a UCP de catre proces. De asemenea, o data pe secunda, rutina de tratare a intreruperii de ceas ajusteaza valoarea de folosire a UCP de catre fiecare proces in concordanta cu o functie de reducere

decay(UCP)=UCP/2.

Cand recalculeaza folosirea recenta a UCP, rutina de tratare a intreruperii de ceas recalculeaza si prioritatea fiecarui proces aflat in starea "intrerupt dar gata de executie" in concordanta cu formula

prioritatea=("valoarea de folosire recenta a UCP" / 2)+(prioritatea utilizator a nivelului de baza)

unde "prioritatea utilizator a nivelului de baza" este valoarea de prag dintre modul nucleu si modul utilizator descrisa anterior. O valoare numerica scazuta implica o prioritate de planificare mai mare. Examinand functiile de recalculare a valorii de folosire recenta a UCP si a prioritatii proceselor, cu cat este mai mica rata decay pentru folosirea recenta a CPU, cu atat mai mult timp va fi necesar prioritatii unui proces sa atinga nivelul sau de baza; in consecinta, procesele in starea "gata de executie" vor tinde sa ocupe nivele de prioritate mai mare.

Efectul recalcularii prioritatilor o data pe secunda este acela ca procesele cu prioritati de nivel utilizator sunt mutate intre cozile de prioritati, asa cum se arata in figura 9.3. Comparand aceasta figura cu figura 9.2, un proces a fost mutat din coada de prioritati a nivelului utilizator 1 in coada de prioritati a nivelului utilizator 0. Intr-un sistem real, toate procesele cu prioritati de nivel utilizator isi vor schimba coada de prioritati, dar in figura a fost exemplificat doar unul. Nucleul nu schimba prioritatile proceselor in modul nucleu, si nici nu permite proceselor cu prioritati de nivel utilizator sa depaseasca pragul si sa obtina prioritati de nivel nucleu, exceptand cazul cand ele fac un apel sistem si se pun in starea de asteptare.

Nucleul incearca sa recalculeze prioritatea tuturor proceselor active o data pe secunda, dar intervalul poate varia usor. Daca intreruperea de ceas soseste in timp ce nucleul executa o regiune critica de cod, acesta nu va recalcula prioritatile, pentru ca ar pastra nucleul in regiunea critica pentru o perioada prea mare de timp. In schimb, nucleul retine faptul ca trebuie sa recalculeze prioritatile proceselor si executa acest lucru la urmatoarea intrerupere de ceas cand nivelul de executie al procesorului este suficient de scazut. Recalcularea periodica a prioritati procesului asigura politica de planificare prin lista circulara a proceselor care se executa in modul utilizator. Nucleul raspunde natural la cererile interactive cum sunt cele ale editoarelor de text: astfel de procese au o rata inalta de folosire a timpului inactiv al UCP si in consecinta valorile prioritatilor lor cresc in mod natural cand sunt gata de executie. Alte implementari ale mecanismului de planificare modifica dinamic cuanta de timp intre zero si o secunda, functie de incarcarea sistemului.

Astfel de implementari pot raspunde mai repede proceselor, deoarece ele nu trebuie sa astepte pana la o secunda pentru a rula; pe de alta parte nucleul poate fi mult mai incarcat datorita comutarilor de context suplimentare.

Figura 9.3 Mutarea procesului dintr-o coada in alta de prioritati

3. Exemple de planificare a proceselor

Figura 9.4 arata prioritatile de planificare in System V pentru 3 procese A, B, si C, supuse urmatoarelor conditii: ele au fost create simultan cu prioritatea initiala 60, cea mai mare prioritate de nivel utilizator este 60, ceasul intrerupe sistemul de 60 de ori pe secunda, procesele nu fac apeluri sistem, si nici un alt proces nu este gata de executie. Nucleul calculeaza rata de reducere pentru valoarea de folosire a UCP utilizand formula :

UCP = decay (UCP) = UCP / 2

iar prioritatea procesului este :

prioritatea=(CPU/2)+60;

Figura 9.4 Exemplu de planificare a proceselor

Presupunem ca procesul A este primul care se executa si ca el ruleaza o secunda: in acest timp ceasul intrerupe sistemul de 60 de ori si rutina de tratare a intreruperii incrementeaza campul folosire UCP al procesului A de 60 de ori ( pana la 60). Nucleul forteaza schimbarea de context dupa o secunda si, dupa recalcularea prioritatilor tuturor proceselor, planifica procesul B pentru executie. Rutina de tratare a intreruperii de ceas incrementeaza campul folosire UCP al procesului B de 60 de ori in timpul secundei urmatoare si recalculeaza valoarea de folosire a UCP si prioritatea tuturor proceselor si forteaza schimbarea de context. Modelul se repeta, pentru procesele care au dreptul sa se execute.

Acum consideram procesele cu prioritatile din figura 9.5, si presupunem ca avem si alte procese in sistem. Nucleul poate intrerupe procesul A, punand-ul in starea "gata de executie", dupa ce el a primit mai multe cuante de timp si prioritatea sa de nivel utilizator poate fi scazuta (Figura 9.5a).

Pe masura ce timpul trece procesul B poate intra in starea "gata de executie", si prioritatea sa de nivel utilizator poate fi mai mare decat a procesului A in acea clipa (Figura 9.5b). Daca nucleul nu planifica nici unul dintre procesele A sau B o perioada de timp (planifica alte procese), ambele procese ar putea eventual sa fie pe acelasi nivel de prioritate utilizator, desi procesul B ar putea atinge acest nivel primul deoarece nivelul lui de start a fost initial mai aproape de origine(Figurile 9.5c si 9.5d). Cu toate acestea nucleul ar putea alege sa planifice procesul A inaintea procesului B deoarece acesta a fost in starea "gata de executie" pentru o perioada mai mare de timp (Figura 9.5e). Aceasta este regula de exceptie pentru procesele cu prioritate egala.

Figura 9.5 Liste circulare de planificare si prioritatile proceselor

Sa ne reamintim din sectiunea 7.4.3 ca nucleul planifica un proces ca rezultat al unei comutari de context. Un proces trebuie sa execute o comutare de context cand se pune in asteptare sau cand se termina, si are posibilitatea sa faca o comutare de context cand revine in modul utilizator din modul nucleu. Nucleul intrerupe un proces care revine in modul utilizator daca un proces cu prioritate mai mare este gata de executie. Astfel de procese exista daca nucleul trezeste un proces cu o prioritate mai mare decat a procesului care ruleaza in acel moment sau daca rutina de tratare a intreruperii de ceas a schimbat prioritatea tuturor proceselor aflate in starea "gata de executie". In primul caz, procesul curent nu ar trebui sa ruleze in modul utilizator atat timp cat este disponibil un alt proces aflat in modul nucleu cu o prioritate mai mare. In al doilea caz rutina de tratare a intreruperii de ceas decide daca procesul si-a epuizat cuanta de timp, si deoarece multe procese si-au schimbat prioritatile, nucleul executa o comutare de context pentru a replanifica alt proces.

4 Controlul prioritatilor proceselor

Procesele pot exercita un control riguros al prioritatii lor de planificare prin folosirea apelului sistem nice:

nice(valoare);

unde parametrul valoare este adaugat in calculul prioritatii procesului:

prioritatea=(valoarea de folosire a CPU / 2 ) + ( prioritatea utilizator

a nivelului de baza)+(valoarea nice)

Apelul sistem nice incrementeaza sau decrementeaza campul nice din tabela de procese cu valoarea parametrului, desi doar administratorul de sistem poate furniza valori nice astfel incat sa mareasca prioritatea proceselor. Similar, doar administratorul de sistem poate furniza valori nice sub un prag anume. Utilizatorii care invoca apelul sistem mice pentru a scadea prioritatea proceselor lor cand executa sarcini de calcul intensiv sunt amabili (mice) fata de alti utilizatori din sistem. Procesele mostenesc valoarea mice a parintelui pe durata apelului sistem for. Apelul sistem mice functioneaza doar pentru procesul in executie; un proces nu poate schimba valoarea mice a altui proces. Practic aceasta insemna ca daca administratorul de sistem doreste sa scada valorile de prioritate ale diferitelor procese care consuma prea mult timp, nu exista nici o modalitate de a o face la fel de repede ca prin apelul sistem kil.

5 Planificator cu partajare corecta

Algoritmul de planificare descris mai inainte nu face nici o diferentiere intre clasele de utilizatori. Astfel, este imposibila alocarea a jumatate din timpul UCP unui set particular de procese. Totusi, astfel de situatii sunt importante intr-un centru de calcul, unde un set de utilizatori ar putea dori sa aiba jumatate din timpul UCP al unei masini, pentru a-si asigura un nivel sigur de raspuns.

Principiul planificatorului cu partajare corecta este sa imparta comunitatea utilizatorilor intr-un set de grupuri de partajare corecta, astfel incat membri fiecarui grup sunt subiectul constrangerilor unui planificator de procese obisnuit relativ la alte procese din grup. Totusi, sistemul aloca timpul UCP proportional fiecarui grup, fara a tine seama cat de multe procese sunt in fiecare grup. De exemplu, sa presupunem ca exista patru grupuri de partajare corecta in sistem, fiecare cu o cota alocata UCP de 25%, iar grupurile contin 1, 2, 3 si 4 procese care nici o data nu vor renunta sa obtina procesorul. Presupunand ca nu exista alte procese in sistem, fiecare proces din cele patru grupuri ar obtine 10% din timpul UCP (fiind 10 procese) folosind algoritmul de planificare obisnuit, deoarece nu exista nici o cale de a le distinge unele de altele. Dar folosind planificatorul cu partajare corecta, procesul din grupul 1 va primi de doua ori mai mult timp UCP decat fiecare proces din grupul 2, de trei ori mai mult timp UCP decat fiecare proces din grupul 3 si de patru ori mai mult timp UCP decat fiecare proces din grupul 4. In acest exemplu, timpul de folosire al UCP al tuturor proceselor dintr-un grup trebuie sa fie aceleasi, deoarece toate sunt intr-o bucla infinita.

Implementarea acestei scheme este simpla, caracteristica ce o face atractiva. Un nou termen este adaugat in formula de calcul a prioritatii procesului, si anume o "prioritate de grup de partajare corecta". Fiecare proces are un camp nou in zona u rea proprie care ponteaza spre un camp de utilizare cu partajare corecta a UCP, folosit in comun de catre toate procesele din grupul de partajare corecta. Rutina de tratare a intreruperii de ceas incrementeaza campul utilizare UCP al grupului de partajare corecta pentru procesul in executie, la fel cum el incrementeaza campul utilizare UCP al procesului in executie si calculeaza valorile tuturor campurilor utilizare UCP pentru grupul de partajare corecta, o data pe secunda. Cand se calculeaza prioritatile proceselor, o noua componenta de calcul este folosirea de catre grup a UCP, normalizata in raport cu cantitatea de timp UCP alocata grupului de partajare corecta. Cu cat procesele dintr-un grup au primit recent mai mult timp UCP, cu atat mai mare este valoarea numerica a campului utilizare UCP de catre grup si, in consecinta, cu atat mai mica este prioritatea pentru toate procesele din grupul de partajare corecta.

De exemplu, consideram cele trei procese din figura 9.6 si presupunem ca procesul A este intr-un grup iar procesele B si C sunt in altul. Presupunand ca nucleul planifica mai intai procesul A, el va incrementa campurile utilizare UCP si utilizare grup ale procesului A dupa trecerea unei secunde. La recalcularea prioritatilor proceselor dupa o secunda, procesele B si C au cea mai mare prioritate; presupunem ca nucleul planifica procesul B. Pe durata secundei urmatoare campul utilizare UCP pentru procesul B creste la 60, la fel si campul utilizare grup pentru procesele B si C. Deci, la recalcularea prioritatilor proceselor la sfarsitul celei de-a doua secunde, procesul C va avea prioritatea 75 si nucleul va planifica procesul A, care are prioritatea 74. In figura se arata cum se repeta modelul: nucleul planifica procesele in ordinea A, B, A, C, A, B, s.a.m.d.

Figura 9.6 Exemplu de planificator cu partajare corecta

-trei procese, doua grupuri

6 Procesarea in timp real

Procesarea in timp real implica posibilitatea de a raspunde imediat la un eveniment extern specific si de a planifica un proces anume sa ruleze intr-o anumita perioada de timp specificata dupa aparitia evenimentului. De exemplu, un calculator poate monitoriza sistemele vitale ale pacientilor dintr-un spital pentru a se lua masuri urgente cand are loc o schimbare in starea unui pacient. Procese cum ar fi editoarele de text nu sunt considerate procese de timp real. Este de dorit ca raspunsul lor sa fie rapid, dar nu este critic faptul ca un utilizator asteapta cateva secunde in plus. Algoritmii de planificare descrisi mai sus au fost proiectati pentru folosirea intr-un mediu cu partajare a timpului si sunt inadecvati intr-un mediu de timp real, deoarece ei nu pot garanta ca nucleul poate planifica un anume proces intr-o limita de timp fixata. Un alt impediment in realizarea procesarii in timp real este acela ca nucleul nu poate planifica un proces de timp real in modul utilizator daca el executa in acel moment un alt proces in modul nucleu, fara a se face schimbari majore. In mod curent, programatorii de sistem trebuie sa insereze procese de timp real in nucleu pentru a obtine raspuns in timp real. O solutie reala a problemei trebuie sa permita proceselor de timp real sa existe dinamic, furnizandu-le un mecanism prin care sa informeze nucleul de constrangerile lor de timp real. Nici un sistem UNIX nu are aceasta posibilitate in prezent.