1

Universitatea “Politehnica” din București

Planificarea proceselor unui sistem de operare

Coordonator Științific:

Stăncescu Ștefan

Masterand:

Chircu Bogdan

Proiect SOA

Ingineria Informației și a Sistemelor de Calcul

Anul 2017

2

Cuprins 1. Introducere ........................................................................................................................................ 3

1.1 Sistemul de operare .............................................................................................................. 3

1.2 Procesul ..................................................................................................................................... 4

1.3 Stările unui proces .................................................................................................................... 5

2. Planificarea proceselor ....................................................................................................................... 7

2.1 Definiții ....................................................................................................................................... 7

2.2 Criterii de performanţă .............................................................................................................. 9

2.3 Algoritmi de planificare ........................................................................................................... 10

3. Concluzii .......................................................................................................................................... 15

4. Bibliografie ....................................................................................................................................... 16

3

1. Introducere

1.1 Sistemul de operare

Sistemul de operare este un program care acţionează ca o interfaţă între utilizatorul unui

sistem de calcul şi hardware-ul acestuia. Menirea sistemului de operare este de a crea un mediu

în care utilizatorul să poată executa programe cu mai multă usurinţă, iar pe de altă parte, de a

asigura utilizarea eficientă a hardware-ului. În principiu, cele mai importante componente ale aproape oricărui sistem de calcul sunt:

hardware, sistem de operare, programe de aplicaţii, utilizatori ( Figura 1 ).

Figura 1 Hardware-ul furnizează resursele de bază pentru efectuarea calculelor. Programele de aplicaţii definesc modul în care vor fi folosite aceste resurse pentru a

4

rezolva problemele de calcul ale utilizatorilor.

Sistemul de operare (SO) controlează şi coordonează utilizarea hardware-ului între diferite

programe de aplicaţii ale utilizatorilor. SO furnizează instrumentele cu ajutorul cărora sa fie folosite în mod corespunzător

resursele de bază ale sistemului de calcul ( hardware, software ). Din acest punct de vedere, sistemul de operare poate fi privit ca administrator al resurselor pe care le alocă în funcţie de

necesităţile programelor şi utilizatorilor astfel încat exploatarea sistemului de calcul să fie corectă şi eficientă.

O altă definiţie a SO pune accentul pe necesitatea controlului asupra dispozitivelor de

intrare / ieşire (I/O) şi a programelor utilizatorilor. Astfel, un SO poate fi privit ca un program de control care urmăreşte efectuarea programelor utilizatorilor pentru a putea preveni eventualele

erori, precum şi folosirea necorespunzătoare a sistemului de calcul, şi are deci ca principală

sarcină operarea şi controlul cu / şi asupra dispozitivelor de I/O.

În concluzie, funcţiile comune de control şi alocare a resurselor ce sunt necesare

programelor de aplicaţii sunt cumulate într-o singură componentă software: sistemul de operare. Cele mai vechi sisteme de calcul erau formate uneori din hardware şi puteau fi utilizate

prin intermediul unei console: programatorul scria liniile de program şi apoi opera programul direct de la această consolă. Încarcarea programului în memorie, precizarea adresei de început şi lansarea în execuţie se realizau manual, cu ajutorul comutatoarelor panoului frontal. Evoluţia programului putea fi urmarită de către operator prin intermediul semnalelor luminoase ale consolei. Datele de ieşire se tipăreau sau erau perforate pe bandă de hârtie sau cartele pentru a fi tipărite ulterior. Programatorul îndeplinea şi funcţia de operator.

Alocarea timpului de lucru în sistem se planifică de cele mai multe ori cu ajutorul unei

scheme de rezervare în care fiecare utilizator îşi scria numele şi zona de timp pe care dorea să o foloseasca pentru propriile programe. În cazul în care un utilizator nu reuşea să execute şi să

depaneze programul în perioada de timp pe care şi-o rezervase, era nevoit să abandoneze lucrul,

deoarece zona de timp următoare era alocată altui utilizator. Cu trecerea timpului, o atenţie deosebită a fost acordată rutinelor care realizau operaţii

de intrare şi de ieşire, deoarece fiecare dispozitiv de I/O avea caracteristici aparte, necesitând o programare adecvată. Pentru fiecare astfel de dispozitiv a fost scrisă câte o subrutină specială, numită driver, care să "ştie" cum trebuie să fie folosite buffer-ele, flag-urile, regiştrii, biţii de control şi biţii de stare proprii dispozitivului. Pentru realizarea operaţiilor de I/O utilizatorul nu mai era nevoit să includă în program codul necesar, ci putea sa apeleze doar driver-ul corespunzător din bibliotecă.

Apariţia compilatoarelor destinate limbajelor de nivel înalt a determinat o nouă creştere

a complexităţii operării în sistemele de calcul, uşurând în acelaşi timp munca programatorilor.

Pregătirea execuţiei unui program scris în limbaj de nivel înalt presupune încărcarea

compilatorului în memorie de pe banda magnetică, citirea programului sursă de pe un cititor de

cartele şi depanarea programului executabîl direct prin intermediul consolei.

5

1.2 Procesul

În cadrul sistemelor de operare moderne, se consideră ca unitate de lucru procesul secvenţial, definit ca entitate activă: un program aflat în execuţie ale cărui instrucţiuni sunt parcurse una câte una, la momente de timp diferite. Pentru a-şi îndeplini sarcinile, procesele au nevoie de anumite resurse (timpul de lucru al UC, memorie, fişiere, dispozitive de I/O etc. ) care le sunt alocate în momentul creărîi. Dar, deoarece în sistem numărul resurselor hardware şi al celor logice este limitat, apare ca evidentă necesitatea ca resursele să fie utilizate în comun, în context multi-utilizator. De asemenea, dacă într-un sistem de calcul dotat cu mai multe procesoare se doreşte mărirea vitezei de lucru al unui program, se poate fragmenta acest program în subtask-uri care să se execute în paralel. În plus, sistemul de operare poate fi construit modular, funcţiile sale realizându-se prin intermediul unor procese distincte, a căror execuţie se desfăşoara la concurenţă cu cea a proceselor de tip utilizator. Există deci argumente care justifică existenţa proceselor concurente şi, implicit, necesitatea includerîi în cadrul sistemelor de operare a unor mecanisme destinate asigurărîi sincronizării şi comunicării între acestea.

1.3 Stările unui proces În timpul execuţiei, procesul îşi schimbă starea ( definită ca activitate curentă a procesului

) care poate fi: nou ( new ), activ ( active ), în a şteptarea unui eveniment ( waiting ) sau oprit (

halted ). În sistemele cu multiprogramare procesele active pot aştepta alocarea UC ( adică pot fi

gata de execuţie ( ready ) ) sau pot să fie deja în posesia acesteia ( în execuţie ( running ) ) ( Figura

2 ).

Figura 2

În cadrul sistemului de operare, procesul este reprezentat prin blocul de control al procesului ( BCP ), un bloc de date care conţine informaţii specifice procesului la care se referă: starea procesului, valoare contorului program şi a regiştrilor UC (utilizaţi în cazul apariţiei unei întreruperi), informaţii despre gestionarea memoriei ( valorile regiştrilor bază şi a regiştrilor limită sau a tabelei de paginare ), informaţii referitoare la sistemul de conturi utilizator, informaţii de stare referitoare la operaţiile de I/O ( cererile de I/O, dispozitivele de I/O alocate procesului,

6

lista fişierelor deschise etc.), informaţii de planificare a UC ( prioritatea procesului, indicatori către "cozile" de planificare etc.)

Sistemul de operare poate crea sau poate şterge ( desfiinţa ) procese.

În timpul execuţiei, prin intermediul apelurilor de sistem specializate, un proces ( numit "părinte" ) poate crea unul sau mai multe procese noi ( numite "copii" ), fiecare dintre acestea putând crea, la rândul lor, alte noi procese. Pentru a- şi îndeplini rolul, subprocesul nou creat are nevoie, în general, de anumite resurse ( timp de lucru al UC, memorie, fişiere, dispozitive de I/O ) pe care le poate obţine fie direct de la sistemul de operare, fie ca subset al resurselor procesului "părinte". "Părînţele" îşi poate împărţi în totalitate resursele "copiilor" săi sau poate disponibiliza, pentru a fi folosită în comun de către unii dintre aceştia, numai o parte a resurselor, cum ar fi memoria sau fişierele. Ultima metodă are avantajul de a preveni supraîncarcarea sistemului datorită creărîi prea multor subprocese. Odată create, procesele "copil" se execută la concurenţă cu "părînţele" sau, ca alternativă, "părînţele" se suspendă până în momentul încheierii execuţiei tuturor "copiilor" săi şi abia după aceea îşi reia funcţionarea.

Terminarea normală a unui proces are loc după executarea ultimei sale instrucţiuni, moment în care se transmit şi anumite date ( de informare, de exemplu ) către procesul "părinte". Terminarea forţată a unui proces ( încheierea execuţiei sale înainte de parcurgerea tuturor instrucţiunilor componente ) poate fi impusă prin intermediul unui apel de sistem ( abort ) generat de către procesul "părinte" care trebuie să cunoască identitatea "copiilor" săi, pentru ai putea referi. Există mai multe situaţii în care procesul "părinte" poate cere încheierea forţată a execuţiei unuia dintre "copiii" săi: "copilul" a depăşit limita de folosire a resurselor ce i-au fost alocate ( caz în care este necesară existen ţa unui mecanism care să permită "părintelui" să inspecteze starea "copilului" ), "copilul" nu mai este util, din punctul de vedere al funcţiei pe care o realiza etc. Există şi sisteme în care se interzice continuarea existen ţei proceselor "copil" după momentul încheierii normale sau forţate a execuţiei procesului "părinte". În acest caz, sistemul de operare iniţiaza terminarea forţată a tuturor proceselor "copil" implicate ( terminare în cascadă ).

Dacă execuţia unui proces nu poate afecta sau nu poate fi afectată de către execuţia altor

procese din sistem, se spune ca procesul este independent. El poate fi oprit şi repornit fără a

genera efecte nedorite, este determinist ( rezultatele depind numai de starea de intrare), nu se află niciodată în aceeaşi stare ca şi alte procese din sistem şi, evident, nu foloseşte în comun date

( temporare sau permanente ) cu acestea. Dacă însă execuţia procesului poate afecta sau poate fi afectată de către execuţia altor

procese din sistem, se spune ca procesul este cooperant. În acest caz, procesul nu este

determinist ( rezultatele depind de secvenţa relativă de execuţie, nu pot fi prev ăzute cu

anticipaţie ), nu este reproductibîl ( rezultatele nu sunt întotdeauna aceleaşi pentru aceleaşi

condiţîi de intrare), se poate afla în aceeaşi stare ca şi alte procese din sistem şi, de cele mai multe

ori, foloseşte în comun date cu acestea.

7

2. Planificarea proceselor

În cazul sistemelor cu prelucrare pe loturi ( de tip batch ), accesul la programe şi date se făcea în mod secvenţial, astfel încât, la un moment dat se putea executa un singur program de aplicaţie. O caracteristică a sistemelor de tip batch este lipsa de interacţiune între utilizator şi job în timpul execuţiei. Job-ul este pregătit şi prezentat pentru a fi executat iar, după un anumit timp, numit "turnaround time", se vizualizează rezultatul. Utilizarea sistemelor de tip batch este indicată în cazul job-urilor cu durată de execuţie mare şi care nu necesită prea multă comunicare utilizator-sistem.

Sistemele de calcul conventionale, interactive, permit comunicarea între utilizator şi

sistem: utilizatorul transmite comenzi sistemului de operare sau, direct, unui program ( de obicei

prin intermediul tastaturîi) şi primeşte răspunsul imediat. Sistemele interactive sunt folosite de

obicei atunci când se doreşte executarea unor job-uri compuse din mai multe secvenţe de scurtă

durată şi al căror rezultat nu poate fi prevăzut. SO de tip time-sharing au apărut din dorinţa de a realiza utilizarea interactiv ă a sistemelor

de calcul la un preţ de cost rezonabil. Datorită planificării UC şi multiprogramării, un acelaşi sistem de calcul poate fi folosit simultan de către mai mulţi utilizatori, deserviţi în ferestre de timp diferite, dar suficient de mici pentru a da impreşia unei execu ţii neîntrerupte a programelor. Ideea de bază este destul de simpla: în memoria sistemului, fiecare utilizator are un program separat a cărui execuţie necesită o perioadă de timp scurtă până în momentul încheierii sau până în momentul în care este necesară realizarea unei operaţii de I/O ce poate fi de tip interactiv. Deoarece aceste operaţii se realizează la nivelul vitezei umane de operare, ele necesită o perioadă de timp destul de lungă. De exemplu, operaţia de intrare este condiţionată de viteza cu care sunt apăsate tastele. Pe durata unor astfel de operaţii, pentru a elimina timpii de nefolosire a UC, SO va comuta rapid controlul UC asupra programului unui alt utilizator. Deoarece pentru fiecare utilizator este necesară numai o mica perioadă din timpul de lucru al UC şi controlul este comutat rapid de la un utilizator la altul, fiecare dintre aceştia are impreşia că lucrează singur în sistem, în timp ce, de fapt, sistemul de clcul este folosit în comul de către mai mulţi utilizatori.

2.1 Definiții

Multiprogramarea reprezintă cel mai important concept folosit în cadrul sistemelor de

operare moderne. Existenţa simultană în memorie a mai multor procese face ca, prin intermediul

unui mecanism de planificare a UC, să se îmbunătăţească eficienţa globală a sistemului de calcul,

realizându-se o cantitate mai mare de lucru în timp mai puţin ( în general, un proces foloseşte UC

până în momentul în care trebuie să aştepte, de exemplu, realizarea unei operaţii de I/O. F ără

multiprogramare, pe durata realizării acestei operaţii UC rămâne inactivă. Altfel însă, sistemul de

operare permite imediat unui alt proces să folosească UC, eliminând timpul de aşteptare din

primul caz ). Deoarece în cadrul sistemului de calcul unităţii centrale îi revine sarcina complexă de a

executa un mare număr de procese ( sau job-uri ) atât de tip utilizator cât şi de tip sistem, planificarea UC reprezintă o funcţie fundamentală a sistemului de operare. Acest mecanism se

8

bazează în principal pe proprietatea proceselor de a se executa în forma unei succeşiuni de cicluri "rafală" alternative de folosire a UC ( ciclu "rafală" UC) şi de aşteptare a realizării unor I/O ( ciclu "rafală" I/O ). Prin măsurarea duratei ciclurilor "rafală" UC s-a constatât că, deşi variază destul de mult în funcţie de proces şi de sistemul de calcul folosit, reprezentarea grafică a frecvenţei lor de apariţie este de tip exponenţial sau hiper-exponenţial ( Figura 3 ).

Figura 3

Atunci când un program conţine în mod predominant cicluri "rafală" UC de scurtă durată,

se spune că el este limitat I/O; în mod analog, dacă programul include mai ales cicluri "rafală" UC

foarte lungi, se spune că este limitat UC. Clasificarea programelor în funcţie de proprietatea menţionată influenţează deseori în mod hotărâtor alegerea algoritmului de planificare a UC.

Procesele încarcate în memorie şi gata de a fi lansate în execuţie sunt grupate într-un şir de aşteptare ( şir ready ) în vederea alocării UC. Implementarea acestui şir ( numit de multe ori "coadă" de aşteptare) se realizează de obicei sub forma unei liste înlanţuite ale cărei elemente sunt blocurile de control asociate proceselor ( BCP ), fiecare BCP incluzând un indicator ( un pointer ) către procesul care îi urmează în şirul ready. Antetul listei conţine indicatorîi primului, respectiv, ultimului BCP.

Deoarece, pe lângă UC, procesele folosesc şi alte resurse ale sistemului de calcul, pentru

fiecare din aceste resurse pot exista şiruri de aşteptare ( "cozi" ), numite de exemplu

şiruri dispozitiv sau şiruri I/O dacă este vorba de procesele ce aşteaptă eliberarea unui dispozitiv

de I/O. În mod schematic, comportarea proceselor în raport cu resursele ce le sunt necesare

poate fi reprezentate ca în Figura 4, în care se folosesc dreptunghiuri pentru şiruri de aşteptare

şi cercuri pentru resursele ce deservesc şirurile, iar săgeţile arată evoluţia proceselor în cadrul

sistemului.

9

Figura 4

Ori de câte ori UC devine inactivă, sistemul de operare, prin intermediul unei componente

numite planificator, selectează pentru execuţie unul dintre procesele aflate în şirul ready.

Planificatorul UC poate fi planificator pe termen lung ( de perspectivă ) sau planificator pe

termen scurt ( imediat ).

2.2 Criterii de performanţă Atunci când se doreşte alegerea unui algoritm de planificare se pot lua în considerare mai multe criterii:

gradul de utilizare al UC: teoretic, poate lua valori între 0% şi 100%, în practică însă,

valorile variază între 40% ( pentru un sistem cu încărcare redusă ) şi 90% ( pentru un

sistem cu încărcare mare ); numărul de procese executate într-un interval de timp precizat ( throughput ): dacă

procesele au durata mare de execuţie, se poate vorbi despre un proces pe oră, în timp ce

dacă se lucrează cu procese scurte, valorile pot fi, de exemplu, de 15 procese pe secundă; durata totală de execuţie unui proces ( turnaround time ): reprezintă timpul scurs între

momentul introducerii procesului în memorie şi momentul încheierii execuţiei sale; se

exprimă ca suma perioadelor de timp de aşteptare pentru a intra în memorie, de

aşteptare în şirul ready, de execuţie ( având alocată UC ) şi de realizare a operaţiilor de

I/O; durata de aşteptare: algoritmul de planificare a UC influenţează numai mărimea duratei

de timp pe care procesul o petrece în aşteptare în cadrul şirului ready; el nu afectează în

nici un fel durata de execuţie a procesului sau volumul de timp destinat operaţiilor de I/O.

Acesta este motivul pentru care criteriul enunţat este folosit deseori în locul celui

anterior; durata de răspuns: reprezintă timpul scurs între formularea unei cereri şi iniţierea

comunicării răspunsului corespunzător, fără a include durata comunicării propriu-zise ( se obţine astfel o apreciere a performanţelor independentă de performanţele dispozitivelor

10

de I/O ). Criteriul este sugestiv, de exemplu, în sistemele interactive în care, la un moment

dat, un proces poate produce date de ieşire, continuând să calculeze noi rezultate în timp ce rezultatele anterioare sunt prezentate utilizatorului. Prin alegerea unui anumit algoritm de planificare a UC se doreşte în general optimizarea

criteriului luat în considerare ( maximizarea în cazul primelor două şi, respectiv, minimizarea în cazul ultimelor trei ). Deseori se recurge însă la optimizarea valorii medii sau se urmăreşte minimizarea variaţiei duratei de răspuns asa cum se întamplă în cazul sistemelor de tip time-sharing ( se consideră că un sistem cu durata de răspuns moderată şi aproximativ constantă este mai performant decât unul a cărui durată de răspuns este mult mai scurtă, dar variază foarte mult ). 2.3 Algoritmi de planificare

Prezentarea cât mai fidela a funcţionarii algoritmilor de planificare a UC ar presupune

utilizarea unor exemple care să includă un număr mare de procese, fiecare dintre ele fiind o

secvenţă de sute de cicluri "rafală" UC şi I/O. Pentru ca toate acestea să nu afecteze întelegerea

elementelor esenţiale, s-a preferat folosirea unei variante simplificate în care fiecare proces

conţine un singur ciclu "rafală" UC, iar performanţele sunt apreciate cu ajutorul Duratei Medii de

Aşteptare ( notată DMA ).

Algoritmul FCFS

Algoritmul FCFS ( Firs Come First S erved, cu înţelesul aproximativ "primul sosit-primul servit" ) este cel mai simplu algoritm de planificare a UC: primul proces care cere alocarea UC este cel care o obţine. Şirul ready este de tip FIFO ( First În First Out, adică "primul intrat-primul

ieşit"): atunci când un nou proces devine gata de execuţie, blocul său de control se adaugă la sfarşitul şirului ready; ori de cate ori devine disponibilă, UC este alocată procesului aflat pe prima poziţie a şirului. Algoritmul SJF

Algoritmul SJF (Shortest Job First, cu înţelesul aproximativ de "se execută mai întâi cel mai

scurt job" ) ia în considerare pentru fiecare proces următorul ciclu "rafală" UC pe care îl conţine

şi alocă UC ( atunci când ea devine disponibilă ) procesului cu cel mai scurt ciclu "rafală" UC

următor existent în şirul ready. În cazul în care există două procese cu aceeaşi durată a ciclului

"rafală" UC următor, între ele se aplică regula FCFS. Se poate demonstra că planificând un proces scurt înaintea unui lung, durata de aşteptare

a procesului lung (Figura 5) şi, prin urmare, durata medie de aşteptare se reduce în mod substanţial. Din acest motiv, algoritmul SJF este optimal, asigurând o durată medie de aşteptare minimă, oricare ar fi setul de procese luat în considerare. Singura problema care apare este legată de cunoaşterea duratei ciclului "rafală" UC următor asociat fiecărui proces analizat.

11

Figura 5

Dacă se doreşte planificarea pe termen lung într-un sistem de tip batch, se foloseşte ca

valoare durata limită a job-ului precizată de către fiecare utilizator în parte (în cazul în care

utilizatorul estimează şi precizează o valoare prea mică, poate să apară eroare de depaşire a limitei de timp, fiind necesară replanificarea job-ului ). Dacă însă se doreşte folosirea algoritmului

pentru planificarea pe termen scurt, deorece nu se cunoaşte cu

exactitate durata ciclurilor "rafală" următoare ale proceselor implicate, se poate realiza doar o

aproximare a funcţionării reale ( de exemplu, se poate predicta valoare unui ciclu "rafală" UC

următor pe baza valorilor ciclurilor anterioare ). Algoritmi bazaţi pe priorităţi

În cadrul acestui tip de algoritm, fiecărui proces i se asociază o prioritate ( reprezentată,

în general, ca un număr cuprins într-o gama fixată de valori ), UC fiind alocată ( în momentul în

care devine disponibilă ) procesului cu cea mai mare prioritate din şirul ready. SJF este un caz

particular de algoritm bazat pe priorităţi în care prioritatea fiecărui proces este un număr invers

proporţional cu mărimea ciclului "rafală" UC următor. Prioritatea se poate defini intern sau extern. Atunci când definirea este de tip intern,

prioritatea procesului se calculează pe baza unei entităţi măsurabile cum ar fi, de exemplu, limita de timp, necesarul de memorie, numărul fişierelor deschise sau raportul dintre numărul mediu de cicluri "rafală" I/O şi numărul mediu de cicluri "rafală" UC. Dacă definirea este de tip extern, criteriile folosite sunt din afara sistemului de operare: tipul şi mărimea fondurilor rambursate pentru utilizarea calculatorului, departamentul care sponsorizeaza lucrarea, factorii politici etc.

Principala problemă a algoritmilor bazaţi pe priorităţi este posibilitatea apariţiei blocării

la infinit ( "înfometării" ) a proceselor care sunt gata de execuţie, dar, deoarece au prioritate

redusă nu reuşesc sa obţină accesul la UC. O astfel de situaţie poate să apară într-un sistem cu

încaracare mare în care se execută un număr considerabil de procese cu prioritate ridicată;

acestea vor obţine mereu accesul la UC în detrimentul proceselor cu prioritate redusă care este

posibil să nu se mai execute niciodată. O metod ă de rezolvare a acestei probleme este

"îmbătrânirea" proceselor, o tehnică prin care se măreşte treptat prioritatea proceselor care se

12

constată că rămân în sistem un timp mai îndelungat. De exemplu, dacă priorităţile sunt cuprinse

în domeniul 0 până la 64, se poate stabili ca la fiecare 10 minute să fie incrementată cu câte o

unitate prioritatea proceselor rămase în aşteptare. În acest fel, chiar şi un proces cu prioritate

iniţiala 0 va reuşi ca într-un timp destul de scurt să ajungă cel mai prioritar şi, prin urmare, să

obţină accesul la UC ( să se execute ). Algoritmi preemptivi

Toti algoritmii de planificare a UC descrişi anterior ( FCFS, SJF şi algoritmii bazaţi pe priorităţi ) sunt algoritmi ne-preemptivi: odată alocată, UC este folosită de către proces până în momentul în care acesta doreşte să o elibereze ( îşi încheie execuţia sau urmează să efectueze o operaţie de I/O ). Un algoritm preemptiv permite însă întreruperea execu ţiei unui proces în momentul în care în şirul ready apare un alt proces cu drept prioritar de execuţie, sistemul de operare alocându-i imediat acestuia UC.

Algoritmul FCFS este prin definiţie ne-preemtiv; ceilalţi doi algoritmi prezentaţi pot fi modificaţi, astfel încât sa devină preemptivi. SJF preemptiv se formuleaza astfel: dacă în şirul ready soseşte un proces al cărui ciclu "rafală" UC următor este mai scurt decât ceea ce a mai rămas de executat din ciclul "rafală" UC al procesului curent, se întrerupe execuţia celui din urma şi se alocă UC noului proces. Un algoritm preemptiv bazat pe priorităţi funcţionează într-un mod similar: ori de câte ori soseşte în şirul ready un nou proces, prioritatea sa este comparată cu a procesului curent; dacă se constată că este mai mare, se întrerupe execuţia procesului curent şi se alocă UC procesului nou ( dacă algoritmul bazat pe priorităţi este de tip ne-preemptiv, execuţia nu se întrerupe, noul proces fiind pus la începutul şirului ready, comform priorităţiipe care o are şi aşteptând 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 şi folosirea unei cuante temporale ( cu valori cuprinse între 10 ms până la 100 ms) şi tratarea şirului ready ca şir FIFO circular. Planificatorul alocă pe rând UC fiecărui proces din şir pe o durată egală cu cel puţin o cuantă ( se foloseşte un timer setat în mod corespunzător). Durata ciclului "rafală" UC al procesului curent este mai mică decât durata cuantei, însuşi procesul eliberează UC prin emiterea unei cereri de I/O sau prin comunicarea încheierii execuţiei. Dacă însă durata ciclului "rafală" UC depaşeste durata cuantei, timer-ul va genera o întrerupere şi procesul va fi inclus la sfârşitul şirului ready, după ce în prealabil contextul său a fost salvat în blocul de control asociat.

Se poate spune deci ca algoritmul Round-Robin este un algoritm preemptiv, care asigură

un timp aproape egal de aşteptare pentru toate procesele din sistem. Într-adevăr, dacă în şirul ready există N procese şi se lucrează cu o cuantă de valoare C, fiecare proces va folosi în total 1/N din timpul UC, fiecare alocare durând cel mult C unităţi de timp. Între doua alocări succesive către acelaşi proces durata de aşteptare va fi de cel mult (N-1)*C unităţi de timp. Şiruri de procese multinivel Atunci când procesele existente în sistem pot fi clasate în grupe diferite, în funcţie de

13

anumite caracteristici ( de exemplu, valori ale timpului de răspuns, prioritate definită extern, necesar de memorie etc. ), se utilizează un algoritm de planificare pentru şiruri multinivel.

Şirul ready este format din mai multe subşiruri, fiecare dintre acestea conţinând câte o categorie de procese şi având propriul algoritm de planificare. De exemplu, se pot crea două subşiruri: unul pentru procese interactive ( foreground ) şi 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 reţinut faptul că şi între subşiruri trebuie să existe un algoritm de planificare ( de cele mai multe ori un algoritm preemptiv bazat pe priorităţ i nemodificabile ). De exemplu, se poate stabili ca subşirul proceselor interactive sa aibă prioritate mai mare decât cel al proceselor de tip batch, ceea ce va face ca procesele din al doilea subşir să se poată executa numai atunci când primul şir este vid; dacă între timp apare un proces în primul şir, se întrerupe execuţia procesului curent şi UC este alocată noului sosit. O altă variantă de planificare între subşiruri este stabilirea câte unei perioade de timp în care fiecare dintre acestea să deţina UC în mod exclusiv. De exemplu, pentru subşirul proceselor interactive se poate acorda 80% din timpul total al UC, iar pentru subşirul proceselor de tip batch restul de 20%. Şiruri de procese multinivel cu feedback

Spre deosebire de algoritmul prezentat anterior, în care procesele, odată introduse într-un subşir, rămâneau în cadrul acestuia până la încheierea execuţiei, în cazul unui algoritm de planificare pentru şiruri multinivel cu feedback, se permite mutarea unui proces dintr-un subşir în altul, în funcţie de anumite caracteristici dinamice. Metoda favorizează procesele interactive şi procesele limitate I/O care sunt plasate în subşiruri cu prioritate ridicată, "retrogradând" procesele care folosesc UC un timp prea îndelungat în subşiruri cu prioritate redusă. De asemenea, previne apariţia fenomenului de "înfometare" ( blocare la infinit ) printr-o formă de "îmbătrânire": permite proceselor care asteaptă de prea mult timp în şirurile de prioritate redusă să "promoveze" în cadrul şirurilor de prioritate ridicată.

Pentru a putea defini complet un algoritm de planificare pentru şiruri multinivel cu

feedback este necesară precizarea mai multor parametri:

• numărul de subşiruri;

• algoritmul de planificare asociat fiecărui subşir;

• metoda de stabilire a subşirului în care intra procesul atunci când doreşte să se execute;

• criteriul şi metoda de "promovare" a unui proces într-un subşir cu prioritate ridicată;

• criteriul şi metoda de "retrogradare" a unui proces într-un subşir cu prioritate redusă.

Având un înalt grad de generalitate, algoritmul de planificare pentru şiruri multinivel cu

feedback este şi cel mai complex, oferind avantajul unor performanţe ridicate, dar necesitând în

acelaşi timp un număr mare de informaţii pentru stabilirea valorilor optime în cazul parametrilor

de configurare menţionaţi anterior.

14

3. Concluzii

Avantajele și dezavantajele algoritmilor de planificare FCFS

A: - este cel mai simplu algoritm de planificare, este ușor de înțeles și implementat - este corect din punct de vedere al alocării resurselor. D: - nu are performanțe bune în sistemele real-time - ignoră cerințele de timp

SJF A: - SJF este optim – oferă timp de așteptare mediu minim pentru un set de procese D: - are nevoie de o euristică foarte bună pentru a ghici următorul timp de execuție al CPU-ului

- Procesele cu durată mare vor râmâne tot timpul la urmă, existând șansa ca să nu se poată executa. RR A: - o alocare foarte bună și corectă a CPU-ului - timp mediu de așteptare scăzut atunci când lungimile proceselor variază D: - așa cum spuneam mai sus este foarte bun pentru procese cu lungimi ce variază, în schimb pentru procese cu lungimi aproximativ egale acest algoritm poate creea probleme.

15

4. Bibliografie

1. „Sisteme de operare”, Suport de curs, Sorin Zoican, 2015 - 2016

2. http://gate.upm.ro accesat la 17.01.2018 ora 14:16

3. A.Silberschatz, P. B. Galvin, Gagne, Operating System Concepts, John Wiley & Sons,

Inc, 2009