SO 6 Kurs

An universitar: 2014 2015Facultatea: Automatic i CalculatoareDomeniul: Calculatoare i Tehnologia Informaiei

Sisteme de Operare Planificarea proceselor

Funcionarea unui planificator Implementarea unui planificator Algoritmi de planificare

[SO - 2014-2015] Curs 6 - Planificarea proceselor 2/42

Planificarea proceselor Planificarea este funcia principal a sistemelor de operare.

Aproape toate resursele unui sistem de calcul sunt planificate naintea utilizrii

Datorit naturii unor constrngeri relative la consumul de resurse, problema planificrii se reduce la gsirea unui algoritm eficient pentru gestionarea accesului i utilizarea resurselor pe baza unei metrici de performan.

Tipurile de resurse luate n calcul sunt timpul CPU i capacitatea memoriei.

Clasificare: planificare uniprocesor (task-uri cu resurse independente sau

partajate) planificare multiprocesor:

planificare static planificare dinamic


Planificarea proceselor problema planificrii uniprocesor poate fi

privit ca o problem de cutare: avem n procese < p1, p2, pn > i vrem s gsim

o secven de execuie astfel nct toate procesele s se poat executa.

Alocarea proceselor este diferit de planificare: alocarea se refer la task-uri cu resurse

independente, deci nu se realizeaz preceden ntre ele

planificarea se refer la procese care au resurse partajate deci i relaii de preceden.


Planificarea proceselor Planificarea static:

exist un set de procese < p1, p2, pn >. Se obine o planificare a proceselor pe sistemul

multiprocesor dat n aa numita faz de testare a fezabilitii planificrii, procesele se vor executa exact n ordinea stabilit de aceast planificare fr ca n timpul rulrii proceselor s apar elemente necunoscute despre procese.

Planificarea dinamic: se pot varia caracteristicile (constrngerile) proceselor

odat cu apariia unor noi procese.


Deciziile de planificare1.Cnd un proces trece din

starea running n starea waiting (cerere I/O, crearea unui proces fiu sau ateptarea terminrii acestuia);

2.Cnd un proces trece din starea running n starea ready (cnd apare o ntrerupere);

3.Cnd un proces trece din starea waiting n starea ready (terminarea unei operaii I/O);

4.Cnd un proces este terminat.

Doar n cazurile 1 i 4, atunci planificarea este nepreemptiv;

altfel, planificarea este preemptiv.


Planificarea nepreemptiv odat ce procesorul a fost alocat unui

proces, procesul pstreaz CPU pn cnd se termin sau pn cnd trece ntr-o stare de wait

este folosit n cazul MSDOS, Windows 3.11

nu necesit existena unui timer


Planificarea preemptiv necesit costuri suplimentare:

fie cazul a dou procese A i B care partajeaz o dat; procesul A poate fi n mijlocul operaiei de modificare

a datei cnd este preemptat i procesul B ruleaz; procesul B poate ncerca s citeasc data care n

momentul respectiv nu este consistent. n acest caz este necesar introducerea de

mecanisme suplimentare pentru coordonarea accesului la resursa comun.


Planificarea preemptiv i kernelul are influen i asupra proiectrii

kernelului sistemului de operare. n timpul procesrii unui apel sistem, kernelul

poate fi ocupat cu o activitate asupra comportamentului unui proces, ceea ce poate duce la modificarea unor date ale kernelului (cozile I/O).

Ce se poate ntmpla dac procesul este preemptat n mijlocul acestor modificri i kernelul are nevoie s citeasc sau s modifice datele?


Planificarea preemptiv i kernelul ntreruperile pot interveni oricnd nu pot fi tot timpul ignorate de kernel seciunile de cod afectate de ntreruperi

trebuie protejate mpotriva utilizrii simultane (concurente) de mai multe procese. se inhib (disable) tratarea ntreruperilor la

intrarea n seciunea critic (utilizarea datelor) i se reactiveaz (enable) la ieire .


Niveluri de planificare Planificarea pe termen lung Planificarea pe termen mediu Planificarea pe termen scurt


Planificarea pe termen lung are drept sarcin alegerea job-ului ce va fi

executat, alocarea resurselor necesare i crearea proceselor.

ruleaz cu frecvena cea mai mic i trebuie s separe tipurile de job-uri n funcie de solicitri.

La unele sisteme poate avea un rol minim sau poate lipsi (la sistemele time-sharing)


Planificarea pe termen mediu Planificatorul pe tremen mediu este cel care decide

momentele n care se fac evaluri, procesele care se evacueaz i care se readuc n memorie pentru continuarea execuiei.

Stabilitatea sistemelor de tip time-sharing depinde de resursele sistemului de calcul i de aceea la aceste sisteme se aplic tehnica de swapping prin care procesele sunt trecute din starea run n swap i din swap n ready.

Prin aceste evacuri temporare, gradul de multiprogramare scade i se prelungete durata execuiei, dar se permite accesul simultan al mai multor utilizatori n sistem.


Planificarea pe termen scurt are n vedere trecerea alternativ a

proceselor din starea ready n starea run i invers.

Tot la acest nivel se desfoar i activitatea dispecerului de procesoare.


Cozile de ateptare ale planificatorului


Strile proceselor i tipul planificrii


Planificare proceselor - Metrici timpul de ateptare al unui proces: este

timpul ct un proces ateapt n coada de execuie

T wait=i=1

n

twait ( pi )

n


Planificare proceselor - Metrici timpul de ciclare reprezint timpul din momentul

crerii procesului (intrare n coada gata de execuie) pn n momentul terminrii execuiei

t ciclare ( pi )=twait ( pi )+ ( pi ) ( pi )

T ciclare=i=1

n

t ciclare ( pi )

n

- timpul de execuie

- timpul de ciclare mediu


ncrcarea CPU

=1

- rata medie de sosire a noilor procese n coada de execuie

- rata medie de deservire a proceselor ( 1/ este timpul mediu de execuie)

Dac ), atunci unitatea central va fi saturat indiferent de algoritmul de planificare.

Dac =1 (=), lista de execuie nu este suficient de lung.

Algoritmii ce vor fi prezentai se vor referi la cazul


Funcionarea unui planificator descrierea funcionrii unui planificator trebuie

avute n vedere dou aspecte: regulile de aciune implementarea n contextul sistemului de operare.

Fixarea sarcinilor unui planificator, indiferent de nivelul la care acioneaz, se face preciznd: modalitatea de intervenie funcia de prioritate regula de arbitraj


Funcionarea unui planificatorModalitatea de intervenie stabilete momentele n care planificatorul

intr n aciune momentele impuse de proces

atunci cnd un proces i termin activitatea sau cnd ateapt terminarea unor operaii de I/O - planificatorul este partajat;

planificatorul este apelat de procese ca un subprogram

momentele impuse de SO SO intervine indiferent de starea proceselor pe care

le planific planificatorul este master.


Funcionarea unui planificatorFuncia de prioritate are ca argumente procesele i parametrii

sistemului. Determinarea prioritii se face avnd n

vedere criterii cum ar fi: cererea de memorie, atingerea unui timp de servire de ctre CPU, timpul real din sistem, timpul total de servire, valorile prioritilor externe, necesarul de timp rmas pn la terminarea

procesului etc.


Funcionarea unui planificatorFuncia de prioritate Algoritmii de planificare trebuie s ndeplineasc

urmtoarele criterii: s realizeze scopurile de performan pentru care au fost elaborai; s aib o durat foarte mic de execuie, pentru a nu crete n

mod nejustificat timpul de execuie alocat SO. Exist multe metode matematice de planificare care dau

soluia optim n nite restricii date Proiectanii de sisteme de operare prefer algoritmi

euristici, mai simpli i cu rezultate mai mult sau mai puin apropiate de cea optim, deoarece un model sofisticat consum mai mult timp fcnd s creasc timpul alocat SO, deci randamentul global s scad.


Funcionarea unui planificatorRegula de arbitraj stabilete o ordine n caz de prioriti

egale: servirea n ordine cronologic servirea circular sau aleatoare.

Observaie: Informaiile legate de starea proceselor care trebuiesc planificate sunt obinute din PCB-ul fiecrui proces.


Implementarea unui planificator Toate tipurile de planificatoare sunt implementate prin

intermediul semafoarelor i folosesc facilitile oferite de gestiunea memoriei.

n funcie de tipul sistemului de operare, planificatoarele dein module specializate de alocare i eliberare a resurselor, prevenire, detectare i ieire din blocaje.

Conceptele de multiprogramare i programare n timp real sunt implementate cu ajutorul planificrii pe termen scurt.

Tot la acest nivel are loc selectarea proceselor candidate la resursele disponibile.

La nivel mediu este potrivit s se modifice prioritile proceselor, dac SO permite aceast facilitate.


Algoritmi de planificareCriterii de evaluare Utilizarea CPU Rspunsul (troughput) Numrul de procese terminate n unitatea de timp Timpul de ciclare (turnaround) timpul mediu de la sosirea

unui proces pn la terminarea lui Timp de ateptare (waiting time) n lista gata de execuie Timpul de rspuns (response time) timpul mediu de la

sosirea proceselor pn la prima execuie Eficiena planificatorului = overhead-ul introdus de planificator. Reprezentarea proceselor se va face cu ajutorul diagramelor

Gantt.


Algoritmi de planificareFCFS (First-Come, First-served) Procesele sunt planificate pe msura sosirii lor n

coada gata de execuie. Procesorul este alocat procesului care l cere primul. Algoritmul mai este denumit i FIFO. Unitatea de msur a performanei este timpul mediu

de ateptare. n acest caz pri(i) = ti , unde ti este momentul cnd

sosete n coada gata de execuie. Dac pentru dou procese i i j, avem pri(i) < pri(j) atunci ti < tj .

n general vom spune ca un proces este de prioritate cu att mai mare cu ct valoarea pri(i) este mai mic.


Algoritmi de planificareFCFS (First-Come, First-served) Pentru FCFS planificarea se va face n

funcie de prioritatea maxim. Lista gata de execuie va fi o list FIFO.

planificare CPU

blocate

sheduler

FIFO

gata de executie


Algoritmi de planificareFCFS (First-Come, First-served)


Algoritmi de planificareShortest-Job-First (SJF) nepreemptiv Procesul planificat pentru execuie este

procesul cu timpul de execuie cel mai mic. Acest algoritm se mai numete i Shortest-Job-Next (SJN).


Algoritmi de planificareShortest-Job-First (SJF) preemptiv Procesul planificat pentru execuie este procesul cu

timpul de execuie rmas cel mai mic. Acest algoritm mai este numit i Shortest Remaining Time First.


Algoritmi de planificarePS (Priority Scheduling) Fiecare proces are asociat prioritate, fiind

lansate n execuie de la prioritatea cea mai mic la prioritatea cea mai mare.

Este cel mai folosit algoritm.


Algoritmi de planificarePS (Priority Scheduling) Se poate introduce un mecanism de prioriti dinamice, n care

pe msur ce timpul de ateptare crete, va crete i prioritatea. Aceast situaie este ntlnit la Unix - se oprete periodic (la

fiecare secund) activitatea sistemului i se recalculeaz prioritatea fiecrui proces.

Astfel se garanteaz un timp mediu de rspuns rezonabil pentru fiecare proces din sistem, dar nu se asigur rspuns prompt la o execuie secvenial.

Prioritile se stabilesc astfel: job-ul primete prioritatea la intrarea n sistem i o pstreaz pn la

sfrit ( este posibil s apar fenomenul de nfometare, dac apar multe procese cu prioritate mare);

SO calculeaz prioritile dup reguli proprii i le ataeaz dinamic proceselor n execuie. Aceast variant este folosit la planificarea pe termen mediu.


Algoritmi de planificareRound-Robin (RR) este un algoritm preemptiv destinat sistemelor de tip time-

sharing i se bazeaz pe distribuirea n mod egal a timpului de procesare ntre procese.

Este folosit o cuant de timp q (cu valori ntre 10 i 100 milisecunde) pe durata creia sunt executate pe rnd pri din fiecare proces.

Dac se introduce i timpul consumat c prin schimbarea contextului, fiecare proces va primi de fapt c+q uniti de timp.

Unele procese se pot termina nainte de expirarea cuantei de timp, moment n care se invoca planificatorul care reface prioritile, reseteaz cuanta de timp i replanific procesele.

Replanificarea are loc i la apariia unui proces nou. Algoritmul RR se implementeaz folosind ntreruperea de ceas a

sistemului respectiv.


Algoritmi de planificareRound-Robin (RR) Dac cuanta de timp q este mai mare algoritmul tinde

ctre FCFS. Algoritmul RR funcioneaz cel mai bine cnd 80% din

procese au timpii de execuie mai mari dect cuanta q.


Algoritmi de planificareRound-Robin (RR)


Algoritmi de planificare Highest Response Ratio Next (HRRN)

Este ales procesul cu cea mai mare rat de deservire (response ratio rr):

n general sunt favorizate procesele cu durata de execuie cea mai mic. Dac ateptarea procesului crete, atunci crete i valoarea ratei de deservire.


Algoritmi de planificare Algoritmul

Feedback

este folosit atunci cnd nu se cunoate timpul de care mai are nevoie un proces ca s-i termine execuia.

Sunt penalizate procesele care ruleaz prea mult i poate duce la apariia fenomenului de nfometare (process/ resource starvation) dac nu variem algoritmii de planificare i prioritile n funcie de cozile de ateptare.


Algoritmi de planificare Planificarea cu listele multinivel

Este o combinaie ntre: algoritmii bazai pe prioriti, Round-Robin i algoritmi folosii pentru tratarea proceselor de aceeai prioritate (HRRN).

Presupunem c lista gata de execuie este format din n subliste n care procesele au prioritile ntre 1 i m.

n acest caz procesul Pi din sublista k va avea prioritatea k.

Pentru a nltura dezavantajul unui timp de ateptare mare pentru subliste apropiate de n se poate folosi o schem de planificare care s favorizeze subliste de mare prioritate (algoritmi nepreemptivi n liste i ntre liste algoritmi preemptivi).


Planificarea cu listele multinivelterminatedq = 10

q = 20

q = 40

FCFS

new

Procese care intr n coad

Procese care se termin sau sunt mutate n alt coad

q = 8

q = 16

FCFS

Priority 0

Priority 1

Priority 2

If 8

If > 8

If 16

If > 16


Inversarea prioritii apare atunci cnd un proces de prioritate

sczut acceseaz o seciune critic apoi un proces de prioritate mare acceseaz i el SC respectiv i se blocheaz.

procese de prioritate intermediar vor mpiedica de asemenea primul proces (de prioritatea cea mai sczut) s deblocheze seciunea critic.


Prevenirea inversrii prioritii Se folosete motenirea prioritii:

de fiecare dat cnd un proces deine o SC pentru care ateapt i alte procese i se acord respectivului proces maximul prioritii proceselor aflate n ateptare.

Problema este c motenirea prioritii micoreaz eficiena algoritmului de planificare i crete overhead-ul ( i se da prioritate maxima ca s nu fie preemptat i s termine lucrul cu SC ).


Prevenirea inversrii prioritii Preempia poate interaciona cu sincronizarea ntr-un

context multiprocesor genernd un alt efect nedorit numit efectul de convoi: un proces acceseaz o seciune critic dup care se suspend. Alte procese care au nevoie de seciunea critic vor trebui

suspendate pn cnd primul se va trezi (va fi reactivat) i va termina seciunea critic.

n acel moment toate procesele suspendate din cauza sincronizrii vor fi trezite ncercnd pe baza prioritii s acceseze seciunea critic.

Astfel, se creeaz efectul de convoi. n general, efectul de convoi apare cnd o mulime de

procese au nevoie de o resurs pentru un timp scurt, iar un altul deine resursa pentru un timp mult mai lung blocndu-le pe primele.

SO 6 Kurs

Documents

Transcript of SO 6 Kurs