Planificarea unitatii centrale ( UC )

Planificarea unitatii centrale ( UC )

Definitii

Multiprogramarea reprezinta cel mai important concept folosit in cadrul sistemelor

de operare moderne. Existenta simultana in memorie a mai multor procese face ca, prin intermediul unui mecanism de planificare a UC, sa se imbunatateasca eficienta globala a

sistemului de calcul, realizandu se o cantitate mai mare de lucru in timp mai putin ( in general, un proces foloseste UC pana in momentul in care trebuie sa astepte, de exemplu, realizarea unei operatii de I/O. Fara multiprogramare, pe durata realizarii acestei operatii UC ramane inactiva. Altfel insa, sistemul de operare permite imediat unui alt proces sa foloseasca UC, eliminand timpul de asteptare din primul caz ).

Deoarece in cadrul sistemului de calcul unitatii centrale ii revine sarcina complexa de

a executa un mare numar de procese ( sau job uri ) atat de tip utilizator cat si de tip sistem,

planificarea UC reprezinta o functie fundamentala a sistemului de operare. Acest mecanism

se bazeaza in principal pe proprietatea proceselor de a se executa in forma unei succesiuni

de cicluri 'rafala' alternative de folosire a UC ( ciclu 'rafala' UC) si de asteptare a realizarii unor I/O ( ciclu 'rafala' I/O). Prin masurarea duratei ciclurilor 'rafala' UC s-a constatat ca, desi variaza destul de mult in functie de proces si de sistemul de calcul folosit, reprezentarea grafica a frecventei lor de aparitie este de tip exponential sau hiper-

exponential ( Figura 6 ).

Figura 6

Atunci cand un program contine in mod predominant cicluri 'rafala' UC de scurta durata, se spune ca el este limitat I/O; in mod analog, daca programul include mai ales cicluri 'rafala' UC foarte lungi, se spune ca este limitat UC. Clasificarea programelor in functie de proprietatea mentionata influenteaza deseori in mod hotarator alegerea algoritmului de planificare a UC.

Procesele incarcate in memorie si gata de a fi lansate in executie sunt grupate intr-un

sir de asteptare ( sir ready ) in vederea alocarii UC. Implementarea acestui sir ( numit de multe ori 'coada' de asteptare) se realizeaza de obicei sub forma unei liste inlantuite ale carei elemente sunt blocurile de control asociate proceselor ( BCP ), fiecare BCP incluzand

un indicator ( un pointer ) catre procesul care ii urmeaza in sirul ready. Antetul listei contine indicatorii primului, respectiv, ultimului BCP.

Deoarece, pe langa UC, procesele folosesc si alte resurse ale sistemului de calcul, pentru fiecare din aceste resurse pot exista siruri de asteptare ( 'cozi' ), numite de exemplu

siruri dispozitiv sau siruri I/O daca este vorba de procesele ce asteapta eliberarea unui dispozitiv de I/O. In mod schematic, comportarea proceselor in raport cu resursele ce le sunt necesare poate fi reprezentate ca in Figura 7, in care se folosesc dreptunghiuri pentru siruri

de asteptare si cercuri pentru resursele ce deservesc sirurile, iar sagetile arata evolutia

proceselor in cadrul sistemului.

Figura 7

Ori de cate ori UC devine inactiva, sistemul de operare, prin intermediul unei componente numite planificator, selecteaza pentru executie unul dintre procesele aflate in sirul ready. Planificatorul UC poate fi planificator pe termen lung ( de perspectiva ) sau planificator pe termen scurt ( imediat ) ( Figura 8 ).

Figura 8

Planificatorul pe termen scurt ( numit si planificator UC ) selecteaza unul dintre procesele gata de executie aflate deja in memoria interna si ii aloca UC. Deoarece multe procese contin cicluri 'rafala' UC foarte scurte ( cateva milisecunde ), planificatorul pe termen scurt are o frecventa de executie foarte mare si, prin urmare, trebuie sa fie foarte rapid pentru a nu irosi timpul de lucru al UC.

Planificatorul pe termen lung numit si planificator de job-uri ) stabileste care sunt procesele ce vor fi incarcate in memoria interna a sistemului pentru a fi executate atunci cand exista mai multe cereri decat posibilitati imediate de executie. De obicei, in astfel de situatii, procesele se afla memorate pe disc magnetic, de unde planificatorul pe termen lung controleaza gradul multiprogramarii ( numarul proceselor din memorie ). In mod evident, frecventa de executie a acestui tip de planificator este mult mai mica si el poate fi folosit mai mult timp decat planificatorul pe termen scurt pentru a selecta procesele. Deoarece in sistem pot exista atat procese limitate I/O, cat si procese limitate UC, este important ca planificatorul pe termen lung sa aleaga o proportie optima de procese apartinand ambelor categorii, altfel sirul ready va fi aproape intotdeauna gol si UC va fi folosita ineficient ( numai procese limitate I/O ) sau sirurile I/O si respectiv dispozitivele asociate vor fi in aceeasi situatie ( numai procese limitate UC ).

Exista si sisteme care folosesc un nivel suplimentar de planificare prin intermediul unui planificator pe termen mediu ( Figura 9). Rolul acestuia este de a modifica gradul de multiprogramare atunci cand este necesar, evacuand din memorie anumite procese ( care altfel ar concura pentru dobandirea UC ) si reintroducandu-le in momentul in care incarcarea sistemului permite reluarea executiei din punctul in care fusese intrerupta. Pentru aceasta metoda se foloseste in limbajul de specialitate denumirea de swapping, ceea ce intr-

o traducere aproximativa ar insemna interschimbare sau, mai sugestiv, evacuare si introducere din/in memorie a procesului. Planificatoarele pe termen mediu sunt incluse mai

ales in cadrul sistemelor de tip time-sharing si a celor cu memorie virtuala.

Figura 9

O alta componenta deosebit de importanta a sistemului de operare este dispecerul care realizeaza efectiv transferarea controlului UC asupra procesului selectat de catre planificatorul pe termen scurt, si la fel ca si acesta, trebuie sa fie foarte rapid pentru a putea executa in mod eficient operatiile necesare: incarcarea registrilor procesului, comutarea in

mod utilizator, efectuarea saltului la locatia corespunzatoare din programul utilizator pentru inceperea/reluarea executiei acestuia.

2. Criterii de performanta

Atunci cand se doreste alegerea unui algoritm de planificare se pot lua in considerare mai multe criterii:

gradul de utilizare al UC: teoretic, poate lua valori intre 0% si 100%, in practica insa, valorile variaza intre 40% ( pentru un sistem cu incarcare redusa ) si 90% ( pentru un sistem cu incarcare mare );

numarul de procese executate intr-un interval de timp precizat ( throughput ): daca

procesele au durata mare de executie, se poate vorbi despre un proces pe ora, in timp

ce daca se lucreaza cu procese scurte, valorile pot fi, de exemplu, de 15 procese pe secunda;

durata totala de executie unui proces ( turnaround time ): reprezinta timpul scurs intre momentul introducerii procesului in memorie si momentul incheierii executiei sale; se exprima ca suma perioadelor de timp de asteptare pentru a intra in memorie,

de asteptare in sirul ready, de executie ( avand alocata UC ) si de realizare a operatiilor de I/O;

durata de asteptare: algoritmul de planificare a UC influenteaza numai marimea duratei de timp pe care procesul o petrece in asteptare in cadrul sirului ready; el nu afecteaza in nici un fel durata de executie a procesului sau volumul de timp destinat operatiilor de I/O. Acesta este motivul pentru care criteriul enuntat este folosit deseori in locul celui anterior;

durata de raspuns: reprezinta timpul scurs intre formularea unei cereri si initierea comunicarii raspunsului corespunzator, fara a include durata comunicarii propriu-zise

se obtine astfel o apreciere a performantelor independenta de performantele dispozitivelor de I/O ). Criteriul este sugestiv, de exemplu, in sistemele interactive in care, la un moment dat, un proces poate produce date de iesire, continuand sa calculeze noi rezultate in timp ce rezultatele anterioare sunt prezentate utilizatorului.

Prin   alegerea unui anumit algoritm de planificare a UC se doreste in general optimizarea criteriului luat in considerare ( maximizarea in cazul primelor doua si, respectiv, minimizarea in cazul ultimelor trei ). Deseori se recurge insa la optimizarea valorii medii sau se urmareste minimizarea variatiei duratei de raspuns asa cum se intampla

in cazul sistemelor de tip time-sharing ( se considera ca un sistem cu durata de raspuns moderata si aproximativ constanta este mai performant decat unul a carui durata de raspuns

este mult mai scurta, dar variaza foarte mult ).

3. Algoritmi de planificare a UC

Prezentarea cat mai fidela a functionarii algoritmilor de planificare a UC ar presupune utilizarea unor exemple care sa includa un numar mare de procese, fiecare dintre

ele fiind o secventa de sute de cicluri 'rafala' UC si I/O. Pentru ca toate acestea sa nu afecteze intelegerea elementelor esentiale, s-a preferat folosirea unei variante simplificate in

care fiecare proces contine un singur ciclu 'rafala' UC, iar performantele sunt apreciate cu ajutorul Duratei Medii de Asteptare ( notata DMA ).

Algoritmul FCFS

Algoritmul FCFS ( Firs Come First Served, cu intelesul aproximativ 'primul sosit- primul servit' ) este cel mai simplu algoritm de planificare a UC: primul proces care cere alocarea UC este cel care o obtine. Sirul ready este de tip FIFO ( First In First Out, adica

'primul intrat-primul iesit'): atunci cand un nou proces devine gata de executie, blocul sau

de control se adauga la sfarsitul sirului ready; ori de cate ori devine disponibila, UC este alocata procesului aflat pe prima pozitie a sirului.

Algoritmul SJF

Algoritmul SJF ( Shortest Job First, cu intelesul aproximativ de 'se executa mai intai cel mai scurt job' ) ia in considerare pentru fiecare proces urmatorul ciclu 'rafala' UC

pe care il contine si aloca UC ( atunci cand ea devine disponibila ) procesului cu cel mai scurt ciclu 'rafala' UC urmator existent in sirul ready. In cazul in care exista doua procese

cu aceeasi durata a ciclului 'rafala' UC urmator, intre ele se aplica regula FCFS.

Se poate demonstra ca planificand un proces scurt inaintea unui lung, durata de asteptare a procesului lung ( Figura 11 ) si, prin urmare, durata medie de asteptare se reduce

in mod substantial. Din acest motiv, algoritmul SJF este optimal, asigurand o durata medie

de asteptare minima, oricare ar fi setul de procese luat in considerare. Singura problema care apare este legata de cunoasterea duratei ciclului 'rafala' UC urmator asociat fiecarui proces analizat.

Figura 11

Daca se doreste planificarea pe termen lung intr-un sistem de tip batch, se foloseste

ca valoare durata limita a job-ului precizata de catre fiecare utilizator in parte ( in cazul in care utilizatorul estimeaza si precizeaza o valoare prea mica, poate sa apara eroare de depasire a limitei de timp, fiind necesara replanificarea job ului ). Daca insa se doreste folosirea algoritmului pentru planificarea pe termen scurt, deorece nu se cunoaste cu

exactitate durata ciclurilor 'rafala' urmatoare ale proceselor implicate, se poate realiza doar

o aproximare a functionarii reale ( de exemplu, se poate predicta valoare unui ciclu 'rafala' UC urmator pe baza valorilor ciclurilor anterioare ).

Algoritmi bazati pe prioritati

In cadrul acestui tip de algoritm, fiecarui proces i se asociaza o prioritate

reprezentata, in general, ca un numar cuprins intr-o gama fixata de valori ), UC fiind alocata

( in momentul in care devine disponibila ) procesului cu cea mai mare prioritate din sirul ready. SJF este un caz particular de algoritm bazat pe prioritati in care prioritatea fiecarui proces este un numar invers proportional cu marimea ciclului 'rafala' UC urmator.

Prioritatea se poate defini intern sau extern. Atunci cand definirea este de tip intern, prioritatea procesului se calculeaza pe baza unei entitati masurabile cum ar fi, de exemplu, limita de timp, necesarul de memorie, numarul fisierelor deschise sau raportul dintre numarul mediu de cicluri 'rafala' I/O si numarul mediu de cicluri 'rafala' UC. Daca definirea este de tip extern, criteriile folosite sunt din afara sistemului de operare: tipul si marimea fondurilor rambursate pentru utilizarea calculatorului, departamentul care sponsorizeaza lucrarea, factorii politici etc.

Principala   problema a algoritmilor bazati pe prioritati este posibilitatea aparitiei blocarii la infinit ( infometarii' ) a proceselor care sunt gata de executie, dar, deoarece au prioritate redusa nu reusesc sa obtina accesul la UC. O astfel de situatie poate sa apara intr-

un sistem cu incaracare mare in care se executa un numar considerabil de procese cu prioritate ridicata; acestea vor obtine mereu accesul la UC in detrimentul proceselor cu prioritate redusa care este posibil sa nu se mai execute niciodata. O metoda de rezolvare a acestei probleme este imbatranirea' proceselor, o tehnica prin care se mareste treptat

prioritatea proceselor care se constata ca raman in sistem un timp mai indelungat. De exemplu, daca prioritatile sunt cuprinse in domeniul 0 pana la 64, se poate stabili ca la fiecare 10 minute sa fie incrementata cu cate o unitate prioritatea proceselor ramase in asteptare. In acest fel, chiar si un proces cu prioritate initiala 0 va reusi ca intr-un timp destul

de scurt sa ajunga cel mai prioritar si, prin urmare, sa obtina accesul la UC ( sa se execute ).

Algoritmi preemptivi

Toti algoritmii de planificare a UC descrisi anterior ( FCFS, SJF si algoritmii bazati

pe prioritati ) sunt algoritmi ne-preemptivi: odata alocata, UC este folosita de catre proces pana in momentul in care acesta doreste sa o elibereze ( isi incheie executia sau urmeaza sa efectueze o operatie de I/O ). Un algoritm preemptiv permite insa intreruperea executiei unui proces in momentul in care in sirul ready apare un alt proces cu drept prioritar de executie, sistemul de operare alocandu-i imediat acestuia UC.

Algoritmul FCFS este prin definitie ne-preemtiv; ceilalti doi algoritmi prezentati pot

fi modificati, astfel incat sa devina preemptivi. SJF preemptiv se formuleaza astfel: daca in

sirul ready soseste un proces al carui ciclu 'rafala' UC urmator este mai scurt decat ceea ce

a mai ramas de executat din ciclul 'rafala' UC al procesului curent, se intrerupe executia celui din urma si se aloca UC noului proces. Un algoritm preemptiv bazat pe prioritati

functioneaza intr-un mod similar: ori de cate ori soseste in sirul ready un nou proces,

prioritatea sa este comparata cu a procesului curent; daca se constata ca este mai mare, se intrerupe executia procesului curent si se aloca UC procesului nou ( daca algoritmul bazat

pe prioritati este de tip ne-preemptiv, executia nu se intrerupe, noul proces fiind pus la inceputul sirului ready, comform prioritatiipe care o are si asteptand eliberarea UC ).

Algoritmul Round-Robin

Round-Robin este un algoritm de planificare a UC proiectat special pentru sistemele

de tip time-sharing. Principalele sale caracteristici sunt definirea si folosirea unei cuante temporale ( cu valori cuprinse intre 10 ms pana la 100 ms) si tratarea sirului ready ca sir FIFO circular. Planificatorul aloca pe rand UC fiecarui proces din sir pe o durata egala cu

cel putin o cuanta ( se foloseste un timer setat in mod corespunzator). Durata ciclului

'rafala' UC al procesului curent este mai mica decat durata cuantei, insusi procesul elibereaza UC prin emiterea unei cereri de I/O sau prin comunicarea incheierii executiei.

Daca insa durata ciclului 'rafala' UC depaseste durata cuantei, timer-ul va genera o

intrerupere si procesul va fi inclus la sfarsitul sirului ready, dupa ce in prealabil contextul sau a fost salvat in blocul de control asociat.

Se poate spune deci ca algoritmul Round Robin este un algoritm preemptiv, care asigura un timp aproape egal de asteptare pentru toate procesele din sistem. Intr-adevar, daca in sirul ready exista N procese si se lucreaza cu o cuanta de valoare C, fiecare proces

va folosi in total 1/N din timpul UC, fiecare alocare durand cel mult C unitati de timp. Intre doua alocari succesive catre acelasi proces durata de asteptare va fi de cel mult (N-1 C

unitati de timp.

Siruri de procese multnivel

Atunci cand procesele existente in sistem pot fi clasate in grupe diferite, in functie de anumite caracteristici ( de exemplu, valori ale timpului de raspuns, prioritate definita extern, necesar de memorie etc. ), se utilizeaza un algoritm de planificare pentru siruri multinivel.

Sirul ready este format din mai multe subsiruri, fiecare dintre acestea continand cate

o categorie de procese si avand propriul algoritm de planificare. De exemplu, se pot crea doua subsiruri: unul pentru procese interactive ( foreground ) si altul pentru procese de tip batch ( background ; pentru primul se poate folosi un algoritm de tip Round-Robin, iar pentru cel de-al doilea un algoritm FCFS. Este important de retinut faptul ca si intre subsiruri trebuie sa existe un algoritm de planificare ( de cele mai multe ori un algoritm preemptiv bazat pe prioritati nemodificabile ). De exemplu, se poate stabili ca subsirul proceselor interactive sa aiba prioritate mai mare decat cel al proceselor de tip batch, ceea ce

va face ca procesele din al doilea subsir sa se poata executa numai atunci cand primul sir este vid; daca intre timp apare un proces in primul sir, se intrerupe executia procesului curent si UC este alocata noului sosit. O alta varianta de planificare intre subsiruri este stabilirea cate unei perioade de timp in care fiecare dintre acestea sa detina UC in mod

exclus De exemplu, pentru subsirul proceselor interactive se poate acorda 80% din timpul total al UC, iar pentru subsirul proceselor de tip batch restul de 20%.

Siruri de procese multinivel cu feedback

Spre deosebire de algoritmul prezentat anterior, in care procesele, odata introduse intr-un subsir, ramaneau in cadrul acestuia pana la incheierea executiei, in cazul unui algoritm de planificare pentru siruri multinivel cu feedback, se permite mutarea unui proces dintr-un subsir in altul, in functie de anumite caracteristici dinamice. Metoda favorizeaza procesele interactive si procesele limitate I/O care sunt plasate in subsiruri cu prioritate ridicata, 'retrogradand' procesele care folosesc UC un timp prea indelungat in subsiruri cu prioritate redusa. De asemenea, previne aparitia fenomenului de 'infometare' ( blocare la infinit ) printr-o forma de 'imbatranire': permite proceselor care asteapta de prea mult timp

in sirurile de prioritate redusa sa 'promoveze' in cadrul sirurilor de prioritate ridicata.

Pentru a putea defini complet un algoritm de planificare pentru siruri multinivel cu feedback este necesara precizarea mai multor parametri:

numarul de subsiruri;

algoritmul de planificare asociat fiecarui subsir;

metoda de stabilire a subsirului in care intra procesul atunci cand doreste sa se execute;

criteriul si metoda de 'promovare' a unui proces intr-un subsir cu prioritate ridicata;

criteriul si metoda de 'retrogradare' a unui proces intr-un subsir cu prioritate redusa. Avand un inalt grad de generalitate, algoritmul de planificare pentru siruri multinivel

cu feedback este si cel mai complex, oferind avantajul unor performante ridicate, dar necesitand in acelasi timp un numar mare de informatii pentru stabilirea valorilor optime in cazul parametrilor de configurare mentionati anterior.