PLANIFICAREA PROCESELOR SI TIMPUL

planificarea proceselor si timpul

Intr-un sistem cu partajarea timpului, nucleul aloca UCP unui proces pentru o perioada de timp denumita cuanta de timp, întrerupe procesul si planifica altul atunci când a expira cuanta de timp, si replanifica procesul sa-si continue executia într-un moment ulterior. Functia de planificare în sistemul UNIX utilizeaza timpul relativ de executie ca parametru pentru determinarea procesului care urmeaza sa fie planificat în continuare. Fiecare proces activ are o prioritate de planificare; nucleul comuta contextul planificând procesul care are cea mai mare prioritate. Nucleul recalculeaza prioritatea procesului curent în momentul când revine din modul nucleu în modul utilizator, si reajusteaza periodic prioritatea fiecarui proces "gata de executie" în modul utilizator.

Anumite procese utilizator au nevoie sa cunoasca informatii referitoare la timp. De exemplu, comanda time afiseaza timpul necesar unei alte comenzi pentru executie, iar comanda date afiseaza data si timpul curent. Diverse apeluri sistem legate de timp permit proceselor sa seteze valorile de timp sau sa stabileasca cantitatea de folosire a UCP de catre proces. Sistemul pastreaza timpul cu ajutorul unui ceas hardware care întrerupe UCP la intervale fixate, dependente de hardware, în general de 50 pâna la 100 de ori pe secunda. Fiecare aparitie a unei întreruperi de ceas este denumita ritmul ceasului (clock tick) Acest capitol studiaza activitatile legate de timp pe un sistem UNIX, considerând planificarea proceselor, apelurile sistem de timp si functiile de tratare a întreruperilor de ceas.

Planificarea proceselor

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 înseamna ca nucleul aloca UCP unui proces pentru o cuanta de timp, întrerupe procesul care îsi depaseste cuanta de timp si îl depune într-una din cozile de prioritati. Un proces poate avea nevoie de mai multe iteratii prin "bucla de reactie" înainte ca el sa-si termine executia.

Atunci când nucleul executa o comutare de context si restaureaza contextul unui proces, acesta îsi continua executia din punctul în care a fost suspendat.

Figura 9.1. Algoritm pentru planificarea proceselor

9.1.1 Algoritmul

La concluzia ca trebuie sa se execute o comutare de context, nucleul executa algoritmul de planificare a unui proces (figura 9.1), selectând procesul cu cea mai mare prioritate din cele care se afla în starile "gata de executie si încarcat în memorie" si "întrerupt". Nu are nici un sens selectarea unui proces daca nu este încarcat în 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 în 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 pâna la urmatoarea întrerupere de ceas; dupa tratarea întreruperii, nucleul încearca din nou sa planifice un proces.

9.1.2. Parametri de planificare

Fiecare intrare în tabela de procese contine un câmp de prioritate pentru planificare a procesului. Prioritatea unui proces în 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 în doua clase (vezi figura 9.2): prioritati utilizator si prioritati nucleu. Fiecare clasa contine câteva valori de prioritate, si fiecare prioritate are o coade de procese asociata logic cu ea. Procesele cu prioritate de nivel utilizator au fost întrerupte în momentul revenirii din modul nucleu în modul utilizator, iar prioritatile de nivel nucleu sunt obtinute în 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 rândul lor: procesele cu prioritate nucleu scazuta se trezesc la receptionarea unui semnal, iar procesele cu prioritate nucleu ridicata continua sa ramâna în starea de asteptare.

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

Figura 9.2 Prioritatile proceselor

Prioritatile denumite "încarcator" , "asteptare pentru I/O cu discul", "asteptare pentru eliberarea unui buffer", si "asteptare pentru eliberarea unui inode" sunt prioritati sistem de valoare înalta, neîntreruptibile, cu 1, 3, 2, si 1 procese în 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, întreruptibile, cu 4, 0 si 2 procese în asteptare. În figura se pot distinge prioritatile utilizator denumite "nivel utilizator 0", "nivel utilizator 1" pâna la "nivel utilizator n" având 0, 4 si 1 procese în asteptare.

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

El atribuie prioritatea unui proces care trebuie sa treaca în starea de asteptare prin corelarea unei valori de prioritate fixa cu motivul trecerii în starea de asteptare. Prioritatea nu depinde de caracteristicile run time ale procesului, ci este o valoare constanta stabilita hardware pentru fiecare apel de trecere în starea de asteptare, dependenta de motivul pentru care procesul trece în aceasta stare. Procesele care asteapta în algoritmi de nivel scazut tind sa provoace o saturare mai mare a sistemului când sunt inactive; din aceasta cauza ele primesc o prioritate mai mare decât 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 decât un proces care asteapta eliberarea unui buffer din mai multe motive. Mai întâi, procesul care asteapta terminarea unei operatii I/O cu discul are deja un buffer; când se trezeste exista o sansa mai mare sa se execute si sa elibereze buffer-ul si, posibil, alte resurse. Cu cât elibereaza mai multe resurse, cu atât mai mari sunt sansele ca alte procese sa nu se blocheze când au nevoie de resurse. Sistemul va avea de executat mai putine comutari de context si, în consecinta, timpul de raspuns al procesului si caracteristicile sistemului sunt mai bune. În al doilea rând, un proces care asteapta un buffer liber ar putea astepta buffer-ul retinut de catre procesul care executa operatii I/O. Când 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 în starea de asteptare pâna când celalalt proces elibereaza buffer-ul; de aceea prioritatea sa este scazuta.

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

Rutina de tratare a întreruperilor de ceas ajusteaza prioritatile tuturor proceselor în 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 întrerupe un proces de mai multe ori pe durata cuantei sale de timp; la fiecare întrerupere de ceas, rutina de tratare a întreruperii de ceas incrementeaza un câmp din tabela de procese care înregistreaza valoarea de folosire recenta a UCP de catre proces. De asemenea, o data pe secunda, rutina de tratare a întreruperii de ceas ajusteaza valoarea de folosire a UCP de catre fiecare proces în concordanta cu o functie de reducere

decay(UCP)=UCP/2.

Când recalculeaza folosirea recenta a UCP, rutina de tratare a întreruperii de ceas recalculeaza si prioritatea fiecarui proces aflat în starea "întrerupt dar gata de executie" în 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. Examinând functiile de recalculare a valorii de folosire recenta a UCP si a prioritatii proceselor, cu cât este mai mica rata decay pentru folosirea recenta a CPU, cu atât mai mult timp va fi necesar prioritatii unui proces sa atinga nivelul sau de baza; în consecinta, procesele în 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 între cozile de prioritati, asa cum se arata în figura 9.3. Comparând aceasta figura cu figura 9.2, un proces a fost mutat din coada de prioritati a nivelului utilizator 1 în coada de prioritati a nivelului utilizator 0. Într-un sistem real, toate procesele cu prioritati de nivel utilizator îsi vor schimba coada de prioritati, dar în figura a fost exemplificat doar unul. Nucleul nu schimba prioritatile proceselor în modul nucleu, si nici nu permite proceselor cu prioritati de nivel utilizator sa depaseasca pragul si sa obtina prioritati de nivel nucleu, exceptând cazul când ele fac un apel sistem si se pun în starea de asteptare.

Nucleul încearca sa recalculeze prioritatea tuturor proceselor active o data pe secunda, dar intervalul poate varia usor. Daca întreruperea de ceas soseste în timp ce nucleul executa o regiune critica de cod, acesta nu va recalcula prioritatile, pentru ca ar pastra nucleul în regiunea critica pentru o perioada prea mare de timp. În schimb, nucleul retine faptul ca trebuie sa recalculeze prioritatile proceselor si executa acest lucru la urmatoarea întrerupere de ceas când 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 în modul utilizator. Nucleul raspunde natural la cererile interactive cum sunt cele ale editoarelor de text: astfel de procese au o rata înalta de folosire a timpului inactiv al UCP si în consecinta valorile prioritatilor lor cresc în mod natural când sunt gata de executie. Alte implementari ale mecanismului de planificare modifica dinamic cuanta de timp între zero si o secunda, functie de încarcarea sistemului.

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

Figura 9.3 Mutarea procesului dintr-o coada în alta de prioritati

9.1.3. Exemple de planificare a proceselor

Figura 9.4 arata prioritatile de planificare în 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 întrerupe 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 utilizând 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: în acest timp ceasul întrerupe sistemul de 60 de ori si rutina de tratare a întreruperii incrementeaza câmpul folosire UCP al procesului A de 60 de ori ( pâna 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 întreruperii de ceas incrementeaza câmpul folosire UCP al procesului B de 60 de ori în 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 în sistem. Nucleul poate întrerupe procesul A, punând-ul în 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 în starea "gata de executie", si prioritatea sa de nivel utilizator poate fi mai mare decât a procesului A în 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 înaintea procesului B deoarece acesta a fost în 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 când se pune în asteptare sau când se termina, si are posibilitatea sa faca o comutare de context când revine în modul utilizator din modul nucleu. Nucleul întrerupe un proces care revine în 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 decât a procesului care ruleaza în acel moment sau daca rutina de tratare a întreruperii de ceas a schimbat prioritatea tuturor proceselor aflate în starea "gata de executie". În primul caz, procesul curent nu ar trebui sa ruleze în modul utilizator atât timp cât este disponibil un alt proces aflat în modul nucleu cu o prioritate mai mare. În al doilea caz rutina de tratare a întreruperii 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.

9.1.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 în calculul prioritatii procesului:

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

a nivelului de baza)+(valoarea nice)

Apelul sistem nice incrementeaza sau decrementeaza câmpul nice din tabela de procese cu valoarea parametrului, desi doar administratorul de sistem poate furniza valori nice astfel încât 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 când 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 în executie; un proces nu poate schimba valoarea mice a altui proces. Practic aceasta însemna 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.

9.1.5 Planificator cu partajare corecta

Algoritmul de planificare descris mai înainte nu face nici o diferentiere între clasele de utilizatori. Astfel, este imposibila alocarea a jumatate din timpul UCP unui set particular de procese. Totusi, astfel de situatii sunt importante într-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 împarta comunitatea utilizatorilor într-un set de grupuri de partajare corecta, astfel încât membri fiecarui grup sunt subiectul constrângerilor unui planificator de procese obisnuit relativ la alte procese din grup. Totusi, sistemul aloca timpul UCP proportional fiecarui grup, fara a tine seama cât de multe procese sunt în fiecare grup. De exemplu, sa presupunem ca exista patru grupuri de partajare corecta în 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. Presupunând ca nu exista alte procese în 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 decât fiecare proces din grupul 2, de trei ori mai mult timp UCP decât fiecare proces din grupul 3 si de patru ori mai mult timp UCP decât fiecare proces din grupul 4. În acest exemplu, timpul de folosire al UCP al tuturor proceselor dintr-un grup trebuie sa fie aceleasi, deoarece toate sunt într-o bucla infinita.

Implementarea acestei scheme este simpla, caracteristica ce o face atractiva. Un nou termen este adaugat în formula de calcul a prioritatii procesului, si anume o "prioritate de grup de partajare corecta". Fiecare proces are un câmp nou în zona u rea proprie care ponteaza spre un câmp de utilizare cu partajare corecta a UCP, folosit în comun de catre toate procesele din grupul de partajare corecta. Rutina de tratare a întreruperii de ceas incrementeaza câmpul utilizare UCP al grupului de partajare corecta pentru procesul în executie, la fel cum el incrementeaza câmpul utilizare UCP al procesului în executie si calculeaza valorile tuturor câmpurilor utilizare UCP pentru grupul de partajare corecta, o data pe secunda. Când se calculeaza prioritatile proceselor, o noua componenta de calcul este folosirea de catre grup a UCP, normalizata în raport cu cantitatea de timp UCP alocata grupului de partajare corecta. Cu cât procesele dintr-un grup au primit recent mai mult timp UCP, cu atât mai mare este valoarea numerica a câmpului utilizare UCP de catre grup si, în consecinta, cu atât 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 într-un grup iar procesele B si C sunt în altul. Presupunând ca nucleul planifica mai întâi procesul A, el va incrementa câmpurile 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 câmpul utilizare UCP pentru procesul B creste la 60, la fel si câmpul utilizare grup pentru procesele B si C. Deci, la recalcularea prioritatilor proceselor la sfârsitul celei de-a doua secunde, procesul C va avea prioritatea 75 si nucleul va planifica procesul A, care are prioritatea 74. În figura se arata cum se repeta modelul: nucleul planifica procesele în ordinea A, B, A, C, A, B, s.a.m.d.

Figura 9.6 Exemplu de planificator cu partajare corecta

-trei procese, doua grupuri

9.1.6 Procesarea în timp real

Procesarea în timp real implica posibilitatea de a raspunde imediat la un eveniment extern specific si de a planifica un proces anume sa ruleze într-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 când are loc o schimbare în 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 câteva secunde în plus. Algoritmii de planificare descrisi mai sus au fost proiectati pentru folosirea într-un mediu cu partajare a timpului si sunt inadecvati într-un mediu de timp real, deoarece ei nu pot garanta ca nucleul poate planifica un anume proces într-o limita de timp fixata. Un alt impediment în realizarea procesarii în timp real este acela ca nucleul nu poate planifica un proces de timp real în modul utilizator daca el executa în acel moment un alt proces în modul nucleu, fara a se face schimbari majore. În mod curent, programatorii de sistem trebuie sa insereze procese de timp real în nucleu pentru a obtine raspuns în timp real. O solutie reala a problemei trebuie sa permita proceselor de timp real sa existe dinamic, furnizându-le un mecanism prin care sa informeze nucleul de constrângerile lor de timp real. Nici un sistem UNIX nu are aceasta posibilitate în prezent.

9.2 Apeluri sistem pentru timp

Exista câteva apeluri sistem legate de timp, stime, time, times si alarm. Primele doua se ocupa cu timpul global al sistemului iar ultimele doua cu timpul proceselor individuale.

Apelul sistem stime permite administratorului de sistem sa seteze o variabila nucleu globala la o valoare ce da timpul curent:

stime(pvalue);

unde pvalue indica un întreg pe 32 de biti care contine timpul masurat în secunde de la 1 ianuarie 1970 ora 00:00:00:, GMT. Rutina de tratare a întreruperii de ceas incrementeaza variabila o data pe secunda.

Apelul sistem time furnizeaza timpul setat de catre apelul stime:

time(tloc);

unde tloc indica o locatie în procesul utilizator pentru valoarea obtinuta. De asemenea, apelul time returneaza aceasta valoare din apelul sistem. Comenzile cum sunt date utilizeaza apelul time pentru a determina timpul curent.

Apelul sistem times furnizeaza timpii cumulati pe care procesul apelant i-a consumat în modurile utilizator si nucleu si timpii cumulati consumati de toate procesele fiu în starea zombie în modurile utilizator si nucleu. Sintaxa apelului este

times(tbuffer)

struct tms *tbuffer;

unde structura tms contine timpii obtinuti si este definita prin

struct tms ;

#include<sys/types.h>

#include<sys/times.h>

extern long times();

main()

child(n)

int n;

Figura 9.7. Program care utilizeaza apelul sistem times

Apelul sistem times returneaza timpul scurs "de la un moment arbitrar de timp din trecut",în mod obisnuit de la initializarea sistemului.

În programul din figura 9.7, un proces creeaza 10 procese fiu si fiecare din acestia executa un ciclu de 10000 de ori. Procesul parinte apeleaza times înainte de a crea procesele fiu si dupa terminarea acestora si procesele fiu apeleaza times înainte si dupa ciclu. Ne-am putea astepta ca timpii consumati de procesele fiu în modurile utilizator si sistem (contorizati în câmpurile corespunzatoare ale procesului parinte) sa fie egali cu sumele respective ale timpilor consumati de procesele fiu, si ca timpul real de executie a procesului parinte sa fie egal cu suma timpilor reali de executie ai proceselor fiu. Totusi, timpii consumati de procesele fiu nu includ timpul consumat pentru apelurile sistem fork si exit, si toti timpii pot fi deformati de timpul folosit pentru tratarea întreruperilor sau pentru comutarile de context.

Procesele utilizator pot planifica semnale de alarma folosind apelul sistem alarm De exemplu, programul din figura 9.8 verifica timpul ultimului acces la un fisier în fiecare minut si tipareste un mesaj daca fisierul a fost accesat. Pentru a face aceasta, el intra într-un ciclu infint: în timpul fiecarei iteratii se apeleaza stat pentru a raporta ultimul moment de timp la care fisierul a fost accesat si tipareste un mesaj daca acesta a fost accesat în ultimul minut. Apoi, procesul apeleaza signal pentru a aranja interceptarea semnalelor de alarma, apeleaza alarm pentru a programa un semnal de alarma la 60 de secunde si apeleaza pause pentru a-si suspenda activitatea pâna când receptioneaza un semnal. Dupa 60 de secunde se genereaza semnalul de alarma; nucleul seteaza stiva utilizator a procesului pentru a apela functia de interceptare a semnalului(wake up), functia întoarce adresa instructiunii dupa apelul pause si procesul reia ciclul.

Factorul comun în toate apelurile sistem de timp prezentate este ceasul sistemului: nucleul diferite contoare de timp când trateaza întreruperile de ceas si initiaza actiuni corespunzatoare.

9.3 Ceasul

Functiile rutinei de tratare a întreruperilor de ceas sunt:

reporneste ceasul;

planifica apelurile functiilor interne ale nucleului pe baza timerelor

interne;

furnizeaza posibilitatea schitarii executiei proceselor în modul

nucleu si utilizator;

calculeaza statistici pentru procese si sistem;

urmareste timpul;

trimite semnale de alarma proceselor care solicita acest lucru;

trezeste periodic procesul încarcator;

controleaza planificarea proceselor;

Unele operatii sunt facute la fiecare întrerupere de ceas, pe când altele sunt facute dupa câteva impulsuri de ceas. Rutina de tratare a întreruperii de ceas ruleaza cu nivel de executie al procesorului ridicat, împiedicând aparitia altor evenimente (cum ar fi întreruperile de la dispozitivele periferice) atunci când este activa. Rutina de tratare a întreruperii de ceas este din acest motiv rapida, astfel încât perioadele critice când alte întreruperi sunt blocate sunt cât se poate de mici.

#include <sys/types.h>

#include<sys/stat.h>

#include<sys/signal.h>

main( argc, argv)

int argc;

char *argv[ ];

axtime=(time_t) 0;

for(;;)

if(axtime!=statbuf.st_atime)

signal(SIGALRM, wakeup); /* reset pentru alarma */

alarm(60);

pause(); /* se pune în asteptare pâna când apare un semnal */

}

}

wakeup()

Figura 9.8 Program care utlizeaza apelul sistem alarm

Repornirea ceasului

Când în sistem apare o întrerupere de ceas, cele mai multe calculatoare solicita ca ceasul sa fie rearmat prin instructiuni software astfel încât aceasta sa întrerupa procesorul din nou dupa un interval corespunzator. Astfel de instructiuni sunt dependente de hardware si nu vor fi prezentate.

Sistemul intern de timeout

Câteva operatiuni ale nucleului, unele drivere de dispozitiv si protocoale de retea, solicita apeluri de functii nucleu în timp real. De exemplu, un proces poate pune un terminal în modul caracter astfel încât nucleul sa poata satisface cererile de citire ale utilizatorului la intervale fixate în loc sa astepte ca acesta sa tasteze CR. Nucleul înmagazineaza informatia necesara într-o tabela callout (Figura 9.10), care contine functia ce trebuie apelata atunci când timpul expira, un parametru pentru functie si timpul în impulsuri de ceas pâna când functia trebuie sa fie apelata.

algoritmul clock

intrari: niciuna

iesiri: niciuna

if (este activata facilitatea" profiling" pentru modul nucleu)

retine numaratorul de program la momentul întreruperii;

if (este activata facilitatea" profiling" pentru modul utilizator)

retine numaratorul de program la momentul întreruperii;

calculeaza statisticile pentru sistem;

calculeaza statisticile pentru proces;

ajusteaza marimea valorii de utilizare a UCP

if ( a trecut o secunda sau mai mult de la ultima întrerupere si

procesul nu se afla într-o regiune critica de cod)

trezeste procesul încarcator daca este necesar;

}

}

Figura 9.9 Algoritm pentru tratarea întreruperilor de ceas

Utilizatorul nu are control direct asupra intrarilor în tabela callout. Nucleul sorteaza intrarile în tabela callout în concordanta cu timpii când trebuiesc apelate functiile din intrarile respective, independent de ordinea în care ei au fost pusi în tabela.

Din cauza modului cum sunt aranjati timpii, în câmpul de timp al fiecarei intrari în tabela callout este memorat timpul ramas pâna la apelarea functiei corespunzatoare intrarii dupa ce vor fi apelate functiile din intrarile anterioare. Timpul total pâna la apelarea functiei corespunzatoare unei intrari în tabela este suma timpilor corespunzatori intrarilor anterioare, inclusiv al intrarii specificate.

Figura 9.10 Tabela callout si crearea unei intrari pentru functia f

Figura 9.10 prezinta un exemplu de tabela callout si modul cum aceasta arata înainte si dupa adaugarea unei noi intrari pentru functia f. (Câmpul timp cu valoare negativa pentru functia a va fi explicat). Când se creeaza o noua intrare, nucleul gaseste pozitia corecta pentru aceasta si ajusteaza corespunzator câmpul de timp al intrarii imediat urmatoare. În figura, nucleul aranjeaza apelul functiei f dupa 5 impulsuri de ceas: creeaza o intrare pentru functia f dupa intrarea pentru functia b care are valoarea câmpului de timp egala cu 2 (suma câmpurilor de timp pentru functiile b si f este 5) si schimba câmpul de timp pentru functia c la 8 (c va fi apelata în continuare dupa 13 impulsuri de ceas). Nucleul poate folosi o lista înlantuita pentru fiecare intrare a tabelei callout sau poate reajusta pozitia intrarilor când modifica tabela. A doua varianta nu este asa de consumatoare de timp daca nucleul nu foloseste tabela prea mult timp.

La fiecare întrerupere de ceas, rutina de tratare a întreruperii de ceas verifica daca exista intrari în tabela callout si, daca exista, decrementeaza câmpul de timp al primei intrari. Datorita modului în care nucleul pastreaza timpii în tabela callout, decrementarea câmpului de timp pentru prima intrare duce la decrementarea efectiva a câmpului de timp pentru toate intrarile din tabela. Daca câmpul de timp al primului element din lista este mai mic sau egal cu zero atunci functia specificata trebuie apelata. Rutina de tratare a întreruperii de ceas nu apeleaza functia direct, astfel ca ulterior nu poate bloca din neglijenta întreruperile de ceas viitoare: nivelul prioritatii procesului este setat sa blocheze întreruperile de ceas, dar nucleul nu poate sti cât va dura executia functiei.

Daca functia a durat mai mult decât un impuls de ceas, urmatoarea întrerupere de ceas (si toate celelalte care survin) ar trebui sa fie blocate. În schimb, rutina de tratare a întreruperii de ceas planifica functia respectiva producând o întrerupere software, numita uneori "întrerupere programata" pentru ca ea este cauzata de executia unei instructiuni masina particulara. Deoarece nivelul de prioritate al întreruperilor software este mai mic decât al celorlalte întreruperi ele sunt blocate pâna când nucleul termina tratarea tuturor celorlalte întreruperi.

Multe întreruperi, printre care si cele de ceas, pot apare între momentul când nucleul este gata sa apeleze o functie din tabela callout si momentul aparitiei unei întreruperi software si, din aceasta cauza, câmpul de timp al primei intrari din tabela callout poate avea o valoare negativa. Când în cele din urma apare o întrerupere software, rutina de tratare a întreruperii scoate intrarile din tabela callout al caror timp a expirat si apeleaza functiile corespunzatoare intrarilor respective.

Deoarece este posibil ca, câmpul de timp al primelor intrari din tabela callout sa aiba valori negative, rutina de tratare a întreruperii de ceas trebuie sa gaseasca prima intrare al carei câmp de timp este pozitiv si sa-l decrementeze. În figura 9.10, de exemplu, câmpul de timp corespunzator intrarii functiei a are valoare -2, aceasta însemnând ca sistemul a primit doua întreruperi de ceas dupa ce functia a a devenit eligibila pentru a fi apelata. Nucleul omite intrarea pentru functia a si decrementeaza câmpul de timp pentru functia b.

9.4 Profiling

Facilitatea profiling a nucleului da o masura asupra timpului în care sistemul se executa în modul utilizator fata de modul nucleu, si asupra timpului consumat pentru executarea rutinelor proprii în modul nucleu. Driverul profile al nucleului supravegheaza performantele relative ale modulelor nucleului prin esantionarea activitatii sistemului în momentul unei întreruperi de ceas. Driverul profile contine o lista de adrese nucleu de esantionare, de obicei adresele functiilor nucleu; un proces si-a încarcat anterior aceste adrese prin scrierea driverlui profile. Daca facilitatea profiling a nucleului este activata, rutina de tratare a întreruperii de ceas apeleaza rutina de tratare a întreruperii corespunzatoare driverului profile care determina daca modul de executie al procesorului în momentul aparitiei unei întreruperi este nucleu sau utilizator. Daca a fost modul utilizator, se incrementeaza un contor pentru executia în modul utilizator, iar daca a fost modul nucleu se incrementeaza un contor intern, corespunzator numaratorului de program. Procesele utilizator pot citi driverul profile pentru a obtine contoarele nucleu si pentru a face calcule statistice.

De exemplu, figura 9.11 prezinta adresele ipotetice ale câtorva rutine nucleu. Daca secventa valorilor numaratoarelor de program care au primit peste 10 întreruperi de ceas este 110, 330 si 145 în spatiul utilizator de adrese, 125, 440, 130, 320 si 104 în spatiul nucleu de adrese, figura prezinta numaratoarele salvate de nucleu. Examinând aceasta figura se poate ajunge la concluzia ca sistemul foloseste 20% din timp în modul utilizator si 50% din timp pentru executia algoritmului nucleu bread.

CEAS

Algoritm Adresa Numar

bread 100 5

breada 150 0

bwrite 200 0

brelse 300 2

getblk 400 1

user - 2

Figura 9.11 Adrese de esantionare pentru algoritmii nucleu

Daca facilitatea de profiling a nucleului este activata pentru o perioada mare de timp, tiparul de esantionare al valorilor numaratoarelor de programe converge spre o proportie reala a utilizarii sistemului. Totusi, mecanismul contabilizeaza timpul consumat cu executia rutinei de tratare a întreruperii de ceas si codul care blocheaza întreruperile de ceas deoarece ceasul nu poate întrerupe astfel de regiuni critice de cod si deci nu poate apela rutina de tratare a întreruperii profile acolo. Acest lucru reprezinta un dezavantaj deoarece astfel de regiuni critice ale codului nucleu sunt frecvent cele mai importante pentru profiling. Din acest motiv, rezultatele trebuie considerate putin mai nuantat. Weinberger descrie o schema pentru generarea numaratoarelor de program într-un bloc de instructiuni cum ar fi corpul instructiunilor "if-then" si "else", pentru a furniza exact cât timp s-au executat. Metoda mareste timpul de folosire a unitatii centrale de fiecare data de la 50% la 200% din folosirea sa, un mecanism profiling permanent nefiind practic. Utilizatorii pot exploata facilitatea profiling pentru procesele de nivel utilizator folosind apelul sistem profil:

profil ( buff, bufsize, offset, scale);

unde buff este adresa unui vector în spatiul utilizator, bufsize este lungimea vectorului, offset este adresa virtuala a subrutinei utilizator (uzual, prima) si scale este un factor care mapeaza adresele virtuale ale utilizatorului în vector. Nucleul trateaza parametrul scale ca o fractie binara în virgula fixa: valoarea hexazecimala 0xffff da o mapare unu la unu a numaratoarelor de program la cuvintele din vectorul buff, 0x7fff mapeaza perechi de adrese program într-un singur cuvânt al vectorului buff, 0x3fff mapeaza grupuri de 4 adrese program într-un singur cuvânt al vectorului buff etc. Nucleul înmagazineaza parametrii apelurilor sistem în zona u area a procesului. Când ceasul întrerupe procesul în modul utilzator, rutina de tratare a întreruperii de ceas examineaza numaratorul de program în momentul întreruperii, îl compara cu valoarea parametrului offset si incrementeaza o locatie în vectorul buff a carei adresa este o functie de parametrii buffsize si scale.

#include<signal.h>

int buffer[4096];

main()

}

f()

g()

theend()

Figura 9.12 Exemplu de folosire a apelului sistem profil

De exemplu, în programul din figura 9.12 este prezentat profilul executiei unui program care apeleaza succesiv doua functii f si g într-un ciclu infinit. Procesul invoca apelul signal pentru a aranja apelul functiei theend la aparitia unui semnal de întrerupere si apoi calculeaza gama adreselor de cod pe care doreste sa le urmareasca si, în final, apeleaza profil pentru a informa nucleul ca doreste sa faca un profil al executiei programului. Executarea programului pentru aproape 10 secunde pe un calculator AT&T 3B20 da iesirea din figura 9.13. Adresa functiei f este cu 204 mai mare decât adresa 0; deoarece dimensiunea textului functiei f este de 12 octeti si lungimea unui întreg este de 4 octeti pe un AT&T 3B20, adresele functiei f sunt mapate în intrarile 51, 52 si 53 din vectorul buf. Similar, adresele functiei g sunt mapate în intrarile 54, 55 si 56 din vectorul buf. Intrarile din vectorul buf 46, 48, 49 sunt pentru adresele ciclului din functia main.

CEAS

offset 212 endof 440 text 57

f 416 428 fdiff 204 gdiff 216

buf[46]=50

buf[48]=8585216

buf[49]=151

buf[51]=12189799

buf[53]=65

buf[54]=10682455

buf[56]=67

Figura 9.13 Rezultatele obtinute în urma rularii programului

din figura 9.12

În utilizarile tipice, gama adreselor de esantionare este determinata prin examinarea adreselor de text din tabela de simboluri a programului care este urmarit. Utilizatorii sunt descurajati de folosirea apelului profil direct pentru ca este complicat; în schimb, o optiune a compilatorului C indica compilatorului sa genereze cod pentru a face profilul proceselor.