Criteriile ce se iau în considerare la definirea performantei unui algoritm de planificare pot fi :
utilizarea UCP-ului;
timpul de prelucrare;
timpul de asteptare;
timpul de raspuns.
Utilizarea UCP-ului reprezinta fractiunea din timp cât UCP este ocupat. Uneori se ia în considerare timpul alocat atât pentru programele uti 616e41g lizator cât si pentru cele sistem, alteori numai pentru programele uti 616e41g lizator ("useful work"). Scopul este de a tine UCP-ul cât mai mult timp ocupat, crescând astfel performanta sistemului.
Timpul de prelucrare poate fi definit ca timpul care se scurge între momentul când programul este lansat în executie si momentul terminarii lui.
Timpul de asteptare este timpul cât un program, pe durata executiei sale, asteapta alocarea resurselor necesare. Poate fi exprimat ca diferenta dintre timpul de prelucrare si timpul efectiv de executie.
Timpul de raspuns este utilizat cel mai frecvent de catre sistemele de operare de timp real sau cu partajarea timpului. Definitiile difera pentru cele doua 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 comanda pâna când primul rezultat apare la terminal (se mai numeste timp de raspuns la un teminal). La sistemele în timp real, poate fi definit ca timpul dintre momentul în care apare un eveniment si momentul când este executata prima instructiune a rutinei de tratare (se mai numeste timp de raspuns la un eveniment) .
A) FCFS (First Come, First Served)
Este unul din cei mai simpli si mai intuitivi algoritmi de planificare, care poate fi caracterizat astfel:
- primul proces lansat este executat fara intrerupere de catre procesor pana la terminarea sa
- in momentul in care procesul aflat in starea running se termina, dintre procesele aflate in starea ready este planificat pentru executie cel care a fost lansat cu cel mai mult timp in urma; acest proces la randul sau ramane in starea running pana la terminarea sa, apoi se reia algoritmul
Sa consideram ca exemplu urmatorul set de procese:
Procesul Momentul
lansarii
Durata totala a
executiei
P
P
P
P
S-a considerat o unitate generica de masura a timpului. Se observa ca nu este tratat cazul in care
doua procese au fost lansate in acelasi timp, deoarece un asemenea caz nu poate apare in practica: intre
doua procese, intotdeauna unul a fost lansat mai devreme decat celalalt. Modul in care procesele sunt
planificate pentru a fi executate de catre procesor poate fi observat in figura urmatoare:
P P P P
Ramane insa o problema: un proces care nu efectueaza nici un apel sistem poate fi executat de
catre procesor un timp oricat de lung. Aceasta situatie nu este exclusiv teoretica, deoarece este oricand
posibil ca un proces sa ramana cantonat intr-o bucla infinita din cauza unei erori de programare.
Trebuie deci sa cautam alti algoritmi, care sa elimine acest neajuns.
B) SJN (Shortest Job Next)
Conform acestui algoritm, procesul aflat in starea running este scos din aceasta stare si
trecut in starea ready dupa o perioada fixata de timp (daca bineinteles nu a efectuat un apel sistem
sau nu s-a terminat mai inainte de expirarea timpului alocat). Dintre procesele aflate in starea ready,
va fi planificat pentru executie procesul care are cel mai mic necesar de timp pentru a se
termina. Rezulta deci ca procesul care tocmai a parasit starea running are sanse de a fi replanificat
imediat la procesor.
Fie urmatorul exemplu:
Procesul Momentul
lansarii
Durata totala a
executiei
P
P
P
P
Pentru un sistem in care procesul aflat in executie este eliberat din starea running dupa 3 unitati
de timp, procesele vor fi executate in felul urmator (pentru simplitate, consideram din nou ca nu se fac
apeluri sistem):
P P P P P
Putem face doua observatii:
- procesul P nu foloseste in intregime perioada de 3 unitati de timp pe care o are la
dispozitie; din acest motiv, planificatorul de procese este apelat la momentul 5 si nu la momentul 6
- la momentul 8 avem de ales intre doua procese, P si P , ambele avand nevoie de inca 4
unitati de timp pentru executie; in acest caz, planificatorul poate alege pe oicare dintre cele doua
procese; de asemenea, la momentul 11 (care nu este reprezentat in diagrama) procesul P este scos din
starea running, dar tot el este replanificat imediat pentru executie, deoarece are necesarul de
timp (1 unitate de timp) mai mic decat procesul P (4 unitati de timp)
Acest algoritm nu este potrivit pentru sistemele uzuale, deoarece presupune cunoasterea
dinainte a duratelor de timp necesare executarii tuturor proceselor, ceea ce este de cele mai multe ori
imposibil. Totusi, in sisteme dedicate unor aplicatii precis definite, este posibila cunoasterea unor
asemenea informatii despre procese, caz in care algoritmul SJN poate fi foarte util.
C) Round-Robin
Si in acest caz, procesul aflat in starea running este eliminat dupa expirarea cuantei de timp
maxime alocate. Planificatorul mentine o lista a proceselor aflate in starea ready si trimite in executie
procesul aflat la inceputul acestei liste. In plus, procesul care tocmai a fost scos din starea running
este plasat la sfarsitul listei (desigur, daca nu a facut un apel de sistem, caz in care este trecut in starea
waiting, sau s-a terminat). Astfel, procesele sunt executate unul dupa altul, iar un proces scos din starea
running va fi din nou planificat pentru executie numai dupa ce toate celelalte procese aflate in starea
ready au fost si ele planificate.
Considerand din nou exemplul anterior, de data aceasta pentru algoritmul Round-Robin, obtinem
urmatoarea diagrama:
P P P P P P P
Un proces care tocmai a fost eliminat din starea running poate fi replanificat imediat pentru
executie numai daca nu exista nici un alt proces in starea ready.
Datorita simplitatii conceptuale si de implementare, precum si faptului ca nu necesita
cunoasterea unor informatii suplimentare despre procese, algoritmul round-robin este cel mai utilizat
in sistemele de operare.
|
