|
|
|
PLANIFICAREA PROCESOARELOR (UC)
Multiprogramarea reprezinta cel mai important concept folosit in cadrul sistemelor de operare moderne. Existenta in memorie a mai multor procese face posibil ca, printr-un mecanism de planificare a unitatii centrale (UC), sa se imbunatateasca eficienta globala a sistemului de calcul, realizandu-se o cantitate mai mare de lucru intr-un timp mai scurt.
Exista procese:
-limitate UC, cand procesul are componente cu timp majoritar de desfasurare in I/O;
-limitate I/O, cand procesul are componente cu timp majoritar de desfasurare in UC.
1. SCHEMA GENERALA DE PLANIFICARE
A PROCESOARELOR
Procesele stau in memorie grupate intr-un sir de asteptare in vederea alocarii in UC. Implementarea acestui sir, numit coada
de asteptare, se realizeaza de obicei sub forma unei liste inlantuite.
Planificatorul pe termen lung (planificator de joburi) stabileste care sunt procesele ce vor fi incarcate in memorie. El controleaza gradul de multiprogramare. Frecventa sa este mica.
PLANIFICARE
DEPLANIFICARE DISPECER
PERSPECTIVASIR READY IMEDIATA INCHEIEREA EXECUTIEI
SIR DE ASTEPTARE I/O
Fig. 1. Schema generala de planificare a proceselor.
Dispecerul realizeaza efectiv transferarea controlului UC asupra procesului selectat de planificatorul UC. Trebuie sa fie rapid pentru a putea realiza eficient operatiile necesare: incarcarea registrelor, comutarea in mod utilizator etc.
Planificatorul pe termen scurt (planificator UC) selecteaza unul din procesele gata de executie, aflate deja in memoria interna, si il aloca UC. Are o frecventa de executie foarte mare si trebuie proiectat foarte rapid.
CRITERII DE PERFORMANTA A
PLANIFICARII UC
Cand se doreste un algoritm de planificare, se pot lua in considerare mai multe criterii :
-gradul de utilizare UC (aproximativ 40% pentru un sistem cu grad de incarcare redusa, 90% pentru un sistem cu grad mare de incarcare ) ;
-throughput (numarul de procese executate intr-un interval de timp precizat);
-turnaround time (durata totala a executiei unui proces) 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 (in UC) si de realizare a operatiilor I/O ;
-durata de asteptare ( algoritmul de asteptare influenteaza numai durata de asteptare in sirul READY si nu afecteaza durata de executie a procesului sau timpul destinat operatiilor I/O) ;
-durata de raspuns (timpul scurs intre formularea unei cereri si initierea raspunsului corespunzator).
Prin alegerea unui algoritm de planificare se urmareste optimizarea criteriului luat in consideratie si anume maximizare pentru primele doua si minimizare pentru ultimele trei.
3. ALGORITMI DE PLANIFICARE UC
In prezentarea algoritmilor de planificare UC performantele sunt apreciate cu ajutorul marimii DMA (durata medie de asteptare).
3.1. Algoritmul FCFS (First Come
First Served)
Sirul READY este de tip FIFO (First Inpout First Output= Primul Intrat Primul Iesit).
Exemplu:
Proces
Durata UC
Durata de asteptare
1
10
0
2
29
10
3
3
39
4
7
42
5
12
49
Durata medie de asteptare va fi :
DMA=(0+10+39+42+47)/5=140/5 =28
Dezavantaje : DMA nu este minimala si poate varia in limite foarte largi in functie de caracteristicile procesului. In plus DMA depinde de ordinea proceselor.
3. Algoritmul SJF (Shortest Job First)
Asa cum arata denumirea, se executa mai intai cel mai scurt job. La egalitate, se aplica regula FCFS (First Come First Served).
Exemplu:
Proces
Durata UC
Proces
Durata UC
Durata de asteptare
1
10
3
3
0
2
29
4
7
3
3
3
1
10
10
4
7
5
12
20
5
12
2
29
32
Durata medie de asteptare va fi :
DMA =(3+10+20+32)/5=65/5=13
Daca se cunosc cu precizie ciclurile UC (ca timp), SJF este optimal. Problema principala este cunoasterea duratei ciclului UC.
3.3. Algoritmi bazati pe prioritate
In cadrul unui astfel de algoritm, fiecarui proces i se asociaza o prioritate, UC fiind alocata procesului cu cea mai mare prioritate din sirul READY. Se poate defini o prioritate interna si o prioritate externa.
Prioritatea interna se calculeaza pe baza unei entitati masurabile :
-limita de timp ;
-necesarul de memorie ;
-numarul fisierelor deschise ;
-raportul dintre numarul de cicluri rafala I/O si numarul de
cicluri rafala UC.
Pentru prioritatea externa, criteriile folosite sunt din afara sistemului de operare :
-departamentul care sponsorizeaza lucrarile ;
-factori politici ;
-factori financiari.
Principala problema a algoritmilor bazati pe prioritati este posibilitatea blocarii la infinit ( a infometarii) 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 incarcare mare, in care se executa un numar considerabil de procese cu prioritate ridicata ; acestea vor obtine accesul la UC in detrimentul proceselor cu prioritate redusa care pot sa nu fie executate niciodata. O solutie a acestei probleme este imbatranirea proceselor, o tehnica prin care se mareste treptat prioritatea proceselor remanente timp indelungat in sistem.
3.4. Algoritmi preemptivi
Un algoritm preemptiv permite intreruperea executiei unui proces in momentul cand in sirul READY apare un alt proces cu drept prioritar de executie.
Dintre algoritmii prezentati anterior :
-FCFS este prin definitie nepreemptiv ;
-SJF poate fi realizat preemptiv; daca in sirul READY soseste un proces al carui ciclu rafala UC urmator este mai scurt decat ce a mai ramas de executat din ciclul curent, se intrerupe executia ciclului curent si se aloca UC noului proces;
-algoritmii bazati pe prioritate, de asemenea, pot fi realizati preemptiv ; la fel ca la SJF, timpul ramas poate fi inlocuit cu marimea prioritatii.
Exemplu:
Proces
Momentul sosirii in sirul READY
Durata ciclului rafala
1
0
12
2
3
3
3
4
6
In SJF fara preemptie :
Ordine
Asteptare
P1(12)
0
P2(3)
9
P3(6)
8+3
DMA = (9+8+3 )/3=6,67
In SJF cu preemptie :
Ordine
Asteptare
P13
P1 asteapta 3+6=9
P23
P2 asteapta 0
P36
P3 asteapta 3-1
P19
DMA = (9+0+2)/3 =3,67
3.5. Algoritmul Round-Robin
Este un algoritm de tip time-sharing. Fiecarui proces i se aloca numai o cuanta de timp (10ms - 100ms) iar sirul READY se trateaza ca FIFO circular.
Exemplu:
Proces
Durata ciclului rafala
1
10
P1 asteapta
2
29
3
3
4
7
5
12
Daca cuanta de timp este de 10 ms, atunci ordinea in UC este urmatoarea:
P1(0) P2(19) P3(0) P4(0) P5(2) P2(9) P5(0) P2(0)
In paranteza este dat timpul care a mai ramas.
Observatii :
-planificatorul aloca UC fiecarui proces pe durata a cel mult o cuanta ; daca durata procesului este mai mica decat aceasta cuanta, procesul elibereaza UC prin comunicarea incheierii executiei ;
-marime cuantei afecteaza performantele algoritmului Round-Robin ; daca cuanta este foarte mare, comportarea este asemanatoare FCFS ; daca cuanta este foarte mica, frecventa comutarii se mareste foarte mult si performantele scad deoarece se consuma mult timp pentru salvare/restaurare registre ;
-se poate spune ca algoritmul Round-Robin este un algoritm preemptiv care asigura un timp aproape egal de asteptare pentru toate procesele din sistem.
3.6. Alti algoritmi de planificare
Exista unii algoritmi cu siruri de procese multinivel. Sirul READY este format din mai multe subsiruri. Fiecare susbsir are propriul algoritm de planificare. In schema de planificare apar siruri READY multiple :
