Algoritmi de planificare: Algoritmul FCFS, algoritmi bazati pe prioritate, algoritmi preemptivi, round-Robin

1. Algoritmul FCFS (First Come First Served)

Sirul READY este de tip FIFO (First Inpout First Output= Primul Intrat Primul Iesit).

Dezavantaje : Durata medie de asteptare-DMA nu este minimala si poate varia in limite foarte largi in functie de caracteristicile procesului. In plus DMA depinde de ordinea proceselor.

Algoritmul  SJF (Shortest Job First)

Se executa mai intai cel mai scurt job. La egalitate, se aplica regula FCFS (First Come First Served).

Daca se cunosc cu precizie ciclurile UC (ca timp), SJF este optimal. Problema principala este cunoasterea duratei ciclului UC.

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.

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.

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.

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.

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 :

3. Controlul executiei proceselor concurente

Atunci cand exista in sistem mai multe procese care, pentru un interval de timp, se afla simultan in executie, se spune ca aceste procese sunt executate in paralel. Pentru aceste procese, timpul total de executie al fiecaruia cuprinde perioade comune tuturor. In cazul existentei mai multor procesoare, paralelismul executiilor poate fi efectiv, in sensul ca fiecare proces poate fi executat de un alt procesor; in cazul unui singur procesor, procesele executate in paralel se executa, de fapt, pe rand prin alternarea starii RUN cu starile READY sau WAIT.

Procesele paralele sunt acele procese care pot fi executate in paralel; aceste procese nu se interconditioneaza reciproc, in timpul executiei, si nu colaboreaza intre ele (sunt procesele care utilizeaza seturi de resurse disjuncte ale sistemului si nu este necesar sa comunice intre ele).

In cazul programarii executiei proceselor paralele, sistemul de operare trebuie sa asigure functiile obisnuite de gestionare a proceselor: evidenta proceselor din sistem, planificarea, alocarea si dezalocarea resurselor.

Procesele concurente sunt acele procese care se pot interconditiona reciproc in timpul executiei in paralel, de exemplu prin folosirea in comun a unor resurse. Pentru procesele concurente executate in paralel pot exista momente cand executia unui proces este dependenta de executia altui proces sau de rezultatele executiei in curs de desfasurare a altui proces.

De exemplu, consideram doua procese care au acces in actualizare la acelasi fisier, de exemplu fisierul cu locurile la un tren, care se actualizeaza printr-un program de rezervare automata a locurilor; daca acest program este lansat concomitent pentru doua executii, se poate intampla ca, la un moment dat, sa se faca rezervarea simultana a unui loc de catre ambele programe; evident, in acest caz, una dintre rezervari este eronata, deci aparitia unor astfel de situatii trebuie prevenita. Secventa de program care realizeaza rezervarea unui loc, in exemplul nostru, se numeste sectiune critica iar inregistrarea din fisier care se refera la locul rezervat se numeste resursa critica.

Se defineste sectiunea critica drept o secventa de program care nu trebuie sa fie executata simultan de procese concurente; resursa critica este resursa care nu poate fi accesata simultan de procese concurente.

In cazul programarii executiei proceselor concurente trebuie avute in vedere urmatoarele principii pentru tratarea sectiunii critice:

1. La un moment dat, un singur proces trebuie sa poata executa o sectiune critica; orice alt proces care solicita executarea sectiunii critice va primi permisiunea de a o executa numai dupa incheierea executiei ei de catre procesul in curs; in exemplul nostru, daca programul de rezervare a locurilor se lanseaza de la doua statii care fac parte dintr-o retea de calculatoare, atunci sistemul de gestionare a retelei poate bloca accesul in scriere a tuturor proceselor la fisier sau la o inregistrare a fisierului, atata vreme cat inregistrarea a fost accesata in regim de actualizare de un proces activ; accesul la inregistrare este deblocat atunci cand se incheie actualizarea ei de catre procesul care a provocat blocarea.
2. Durata executiei sectiunii critice a proceselor concurente este necunoscuta aprioric (nu se stie cat va dura executia in curs); pe de alta parte, nici un proces nu trebuie sa astepte nedefinit de mult pentru a intra in sectiunea critica. Rezulta a doua regula pentru executia proceselor concurente: oprirea unui proces, prin dezactivare sau blocare, poate avea loc numai in afara sectiunii critice, adica sectiunea critica este neinteruptibila.