Planificarea proceselor PDF

Preview

Summary

Sisteme de operare, Curs 5, pag. 1/8 3 Planificarea proceselor Apariţia unui eveniment într-un sistem calculator, impune ca sistemul de operare să analizeze procesele şi să decidă ca unul dintre ele sa fie executat, aceasta însemnând că i se alocă resursa fizică „procesor”. Partea sistemului de oper...

Description

Sisteme de operare, Curs 5, pag. 1/8

3.10 Planificarea proceselor Apariţia unui eveniment într-un sistem calculator, impune ca sistemul de operare să analizeze procesele şi să decidă ca unul dintre ele sa fie executat, aceasta însemnând că i se alocă resursa fizică „procesor”. Partea sistemului de operare care se ocupă de alocarea resursei procesor se numeşte planificator (scheduler) iar algoritmii utilizaţi se numesc algoritmi de planificare. Cei mai simpli algoritmi de planificare sunt folosiţi în sistemele cu prelucrare pe loturi (batch processing). In sistemele de tip multi-utilizator (interactive) sau în cele de timp-real algoritmii se complică. Scopurile generale urmărite de toate sistemele de operare sunt: 1. Corectitudinea (Onestitatea) - fiecare proces să primeasca resursa procesor în mod echitabil. Procese comparabile trebuie să beneficieze de servicii comparabile 2. Eficienţa - realizarea unei ocupări maxime a tuturor resurselor fizice a sistemului calculator şi în principal a procesorului. 3. Respectarea politicii sistemului de operare - îndeplinirea strategiei propuse de către sistemul de operare. In plus există scopuri specifice tipului de sistem de operare după cum urmează: - Pentru sistemele de prelucrare pe loturi: 1. Productivitate – maximizarea numărului de sarcini pe oră. 2. Timpul de răspuns – minimizarea timpului între introducerea sarcinii şi terminarea acesteia. Practic, acest parametru măsoară cât de mult aşteaptă în medie, un utilizator, datele de ieşire 3. Gradul de utilizare al procesorului – menţinerea procesorului ocupat tot timpul. Această metrică nu este una foarte bună. Cu adevărat important este numărul de sarcini completate de sistem în unitatea de timp (productivitatea) şi intervalul de timp în care se obţin rezultatele pentru o sarcină (timpul de răspuns). -

Pentru sistemele de operare interactive: 1. Timpul de răspuns – răspuns rapid la cereri. Se urmăreşte minimizarea acestui timp care reprezintă timpul scurs între apariţia unei comenzi şi obţinerea rezultatului. Procesarea cererilor interactive mai întâi (în dauna proceselor de fundal, de exemplu) va fi percepută ca performanţă bună a sistemului. 2. Proporţionalitate – îndeplinirea aşteptărilor utilizatorului. Această metrică se referă la faptul că utilizatorii percep într-un mod propriu felul în care trebuie să se execute o sarcină şi mai ales timpul în care aceasta ar fi „normal” să se încheie. Utilizatorii acceptă ca o sarcină complexă să dureze mult timp dar nu vor concepe să se întâmple acelaşi lucru cand este vorba de o cerere simplă.

-

Pentru sistemele de timp-real: 1. Respectarea termenelor – evitarea pierderii datelor. Sistemele de timp-real sunt caracterizate prin existenţa acestor termene care ar trebui respectate. De exemplu, dacă un calculator controlează un dispozitiv care produce date cu o rată constantă, eşecul în a rula procesul de colectare a datelor la timp poate cauza pierderea acestora. 2. Predictibilitatea – evitarea degradării calităţii sistemelor multimedia. In anumite sisteme de timp real, şi mai ales în cele care presupun multimedia,

Sisteme de operare, Curs 5, pag. 2/8 predictibilitatea este importantă. Ratarea ocazională a unui termen nu este crucială, dar dacă un proces audio rulează instabil, calitatea sunetului se va deteriora rapid. Probleme similare pot fi identificate şi în cazul proceselor care operează pe secvenţe video. Pentru a evita aceste neajunsuri, planificarea proceselor trebuie să fie foarte predictivă şi regulată. Unele din aceste criterii pot fi „divergente”. De exemplu, timpul de răspuns şi eficienţa sistemului. 3.10.1 Planificarea round robin Este unul din cei mai vechi, corecţi şi des folosiţi algoritmi de planificare. Conform acestuia fiecărui proces i se atribuie o cuantă de timp în care i se permite să ruleze. Daca procesul este încă în execuţie la expirarea cuantei se ia procesorul respectivului proces şi se atribuie altuia. Daca procesul trece în starea „blocat” înainte de expirarea cuantei, comutarea procesorului se va face în momentul blocării procesului . Algoritmul round robin este uşor de implementat. Tot ceea ce trebuie să facă planificatorul este să administreze o lista de procese aflate in starea „gata de execuţie”. Proces curent

B

Următorul proces F

D

Proces curent C

F

D

Următorul proces C

B

Atunci când cuanta alocată procesului B expiră, procesul este suspendat şi este trecut în coada listei, procesorul fiind atribuit urmatorului proces din listă (procesul F). Problema care se pune în cazul acestui algoritm este stabilirea lungimii cuantei de timp. Acest lucru este foarte important pentru ca are efecte majore asupra eficienţei utilizării sistemului de calcul. Comutarea de la un proces la altul consuma un timp legat de administrare, salvarea, restaurarea contextului procesului si actualizarea tabelelor sistemului de operare. Vom numi acest interval, timp de comutare proces (process switch) sau timp de comutare context (context switch). Presupunând că valoarea acestuia este de circa 5 msec şi că valoarea cuantei este de 20 msec, timpul de comutare context ar reprezintă 20%, ceea ce înseamnă o utilizare ineficienta a calculatorului. Pe de altă parte, dacă alegem o cuanta de 500 msec, timpul de comutare context reprezintă 1% ceea ce pare foarte bine. Dar acest lucru conduce la un timp de răspuns foarte lung. O cuantă rezonabilă este de 10-50 msec. In funcţie de viteza procesorului, care determină în principal timpul de comutare, trebuie realizat un compromis între eficienţă şi timp de răspuns. Pentru sistemele mai rapide se alege o cuantă mai mică pentru că la acestea şi timpul de comutare context este mai mic.

Sisteme de operare, Curs 5, pag. 3/8

3.10.2 Planificarea bazată pe priorităţi Planificarea round robin tratează procesele ca fiind de egală importanţă. O alta posibilitate este de a atribui fiecărui proces o anumita prioritate, conform importanţei sale. Planificatorul va permite rularea procesului „gata de execuţie” cu cea mai mare prioritate. Pentru prevenirea situatiei în care procesele cu prioritate mare ruleaza la infinit, planificatorul poate descreşte prioritatea procesului curent la fiecare întrerupere de ceas. Astfel la un moment dat, prioritatea procesului curent poate să scadă sub a următorului din ierarhie apărând astfel posibilitateea ca acesta să fie şi el lansat cândva în executie. Priorităţile pot fi atribuite proceselor în mod static sau dinamic. Asignarea statică a prioritatilor se face la lansarea în executie, iar aceste prioritati nu se modifică ulterior. Asignarea dinamică se face în timpul executiei procesului dupa anumite reguli. De exemplu, există procese care sunt puternic dependente de operaţii de intrare/ieşire şi îşi petrec majoritatea timpului aşteptând ca aceste operaţii să se încheie. Când un astfel de proces doreşte procesorul, acesta ar trebui să-i fie alocat imediat, pentru a permite procesului să facă următoarea cerere de intrare/ieşire care apoi se poate desfăşura în paralel cu alte procese care efectuează calcule. Un algoritm simplu de atribuire dinamica a prioritatii constă în asignarea fiecarui proces, o prioritate egala cu 1/f unde f reprezintă fractiunea din cuanta de timp pe care procesul a folosit-o ultima dată. De exemplu, daca procesul a rulat 2 msec din durata cuantei (100 msec) va avea prioritatea 50, pentru că f = 2/100 = 0,2. Dacă un proces a beneficiat de întreaga cuanta de 100 msec atunci el va avea prioritatea 1 pentru ca f = 100/100= 1. De multe ori este util să grupăm procesele în clase urmând ca algoritmul de planificare bazat pe prioritati să se aplice la nivelul claselor de procese, iar în interiorul acestora să se aplice algoritmul round robin. Procese in starea GATA Prioritatea 4

PX

PY

Prioritatea 3

Pn

Pm

Prioritatea 2

Pk

Prioritatea 1

PI

PZ

PJ

- prioritatea cea mai mare

- proritatea cea mai mica

Planificare cu 4 clase de prioritati Atat timp cat exista procese în starea „gata de execuţie”, în clasa de prioritati 4 (Px,Py,Pz), se vor trata aceste procese conform algoritmului round robin pentru procesele din aceeaşi clasă. Dacă nu există procese în clasa de prioritate 4 se vor rula procesele din clasa 3 (Pn, Pm) conform algoritmul round robin, s.a.m.d.

Sisteme de operare, Curs 5, pag. 4/8

3.10.3 Planificarea cu cozi multiple Acest tip de planificare se aplică la sistemele de calcul pentru care comutarea între procese este foarte lungă. Acest lucru se întimplă la calculatoarele la care nu se poate pastra in memorie, la un moment dat decat un singur proces. Fiecare comutare presupune transferarea (evacuarea) procesului curent pe harddisc urmat de citirea procesului ce urmează la rând, de pe harddisc şi transferarea lui în memorie. La acest tip de algoritm se urmareste minimizarea numarului de evacuari. Este evident ca un număr mic de evacuări necesită o cuanta de valoare mare, dar a da tuturor proceselor o cuantă mare de timp ar însemna un timp mare de răspuns. Soluţia la această problemă constă în crearea de clase de prioritate. Procesele din cea mai mare clasă de prioritate erau rulate pentru o cuantă de timp. Procesele din următoarea clasă se executau pentru două cuante de timp, cele din următoarea clasă pentru patru cuante de timp s.a.m.d. După ce un proces foloseşte în întregime cuanta alocată este mutat mai jos cu o clasă. Considerăm ca exemplu, un proces care are nevoie pentru executie de 100 cuante. Initial procesul este introdus in clasa in care este executat o cuanta apoi este evacuat. Data următoare i se alocă 2 cuante succesive si apoi iarasi este evacuat. La rulările următoare primeşte 4, 8, 16, 32 si 64 de cuante, chiar daca în ultima clasă ar folosi numai 100-(1+2+4+8+16+32)=37 de cuante. Prin acest algoritm sunt deci necesare numai 7 evacuări faţă de 100 câte ar fi necesare într-o planificare de tip round robin pură. Pe măsură ce avanseaza în clasele de prioritate procesele vor fi rulate din ce in ce mai rar. Impărţirea proceselor în clase de prioritate se poate face în funcţie de tipul de activitate care se desfasoara în cadrul procesului la un moment dat. O posibilitate o reprezintă gruparea în 4 clase: terminale, intrare/ieşire, cuante scurte respectiv cuante lungi. Dacă un proces care aştepta date de la terminal (tastatură) era activat atunci el era mutat în prima clasă de prioritate (terminale). Dacă un proces blocat în aşteptarea discului devenea gata de execuţie atunci era mutat în a doua clasă de priorităţi (intrare/ieşire). Dacă un proces era încă în execuţie atunci când îi expira cuanta de timp,era plasat iniţial în cea de-a treia clasă (cuante scurte). Dar dacă un proces îşi folosea cuanta de timp de prea multe ori la rând fără să se blocheze în aşteptarea unor evenimente, atunci era mutat în ultima clasă (cuante lungi). Metoda este potrivită şi pentru a favoriza procesele interactive în dauna celor de fundal.

3.11 Interblocări (Deadlocks) In sistemele cu multiprogramare pot aparea probleme serioase atunci cind doua procese solicita (initiaza) simultan (sau aproape simultan) utilizarea unei aceiasi resurse. Acest lucru s-a vazut pe larg atunci când s-a discutat problematica referitoare la conditiile de competitie. Astfel putem considera următorul exemplu: Două procese doresc sa tipareasca fiecare în parte câte un fişier, de dimensiuni mari, fiţiere situate pe o bandă magnetică. Procesul A solicită permisiunea sa utilizeze imprimanta şi i se acordă. Procesul B solicita, cvasisimultan, permisiunea să utilizeze banda magnetică şi capătă acest drept. Trebuie mentionat că ambele periferice, imprimanta şi banda magnetică, sunt periferice nepartajabile adică nu pot fi utilizate simultan de mai multe procese. In continuare procesul A solicita utilizarea benzii magnetice, pentru a citi fişierul care trebuie tipărit, dar cererea este nesatisfacuta pâna când banda va fi eliberată de catre procesul B. Procesul B va solicita accesul la imprimanta, iar acesta nu-i va fi permis pentru ca aceasta este atribuita procesului A. In acest moment ambele procese sunt blocate si nu mai ies niciodata din aceasta

Sisteme de operare, Curs 5, pag. 5/8 stare. Aceasta situatie este denumita interblocare (deadlock). Interblocările se pot produce atunci când unui proces i se atribuie utilizarea, „exclusivă” la resursele fizice sau logice ale sistemului calculator. Dacă resursele fizice se referă la dispozitivele fizice ale calculatorului, resursele logice se referă la, înregistrări din bazele de date, fisiere, etc. Dintr-un alt punct de vedere resursele sunt de doua tipuri: preemptibile (sau cu prelevare forţată) şi nepreemptibile. O resursa preemptibilă este o resursă care poate fi luată de la procesul care o deţine fără efecte nedorite. Memoria este un exemplu de resursă preemptibilă. Să considerăm de exemplu, un sistem cu 32MB memorie utilizator, o imprimantă şi două procese de 32MB, fiecare, dorind să tipărească ceva. Procesul A cere şi primeşte acces la imprimantă, apoi începe să prelucreze valorile pentru tipărire. Inainte de a termina prelucrarea i se termină cuanta de timp şi este scos din memorie şi pus pe disc. In continuare, procesul B este încărcat în memorie şi lansat în execuţie. Pentru a tipări propriile date, procesul B cere atribuirea imprimantei care este însă deţinută de procesului A astfel că ajungem la o situaţie de interblocare potenţială deoarece procesul A are imprimanta iar B are memoria şi niciunul nu poate continua fără resursa deţinută de celălalt. Din fericire este posibil ca memoria să fie prelevată forţat de la procesul B prin punerea acestuia pe disc şi aducerea procesului A în locul lui. Acum A poate rula, tipări apoi elibera imprimanta evitându-se astfel interblocarea. O resursa nepreemptibilă este din contră, o resursa care nu poate fi luată de la procesul care o deţine fără ca execuţia acestuia să nu eşueze. De exemplu daca un proces a inceput tiparirea datelor sale, retragerea imprimantei inainte de terminarea tiparirii lor pentru a o atribui altui proces va avea un rezultat negativ. In general interblocările apar la utilizarea resurselor nepreemptibile. Aceste interblocări potentiale se pot rezolva obicei prin realocarea resurselor de la un proces la altul. Secvenţa de evenimente ce trebuie sa se execute la utilizarea unei resurse este: 1. Solicitarea resursei si atribuirea ei; 2. Utilizarea resursei; 3. Eliberarea resursei. Daca resursa nu este disponibila când este solicitata, procesul care solicita resursa este pus in asteptare. In unele sisteme de operare procesul este automat blocat atunci când solicitarea nu poate fi satisfacută şi repornit atunci când resursa devine disponibila. In alte sisteme de operare cererile nesatisfăcute determină aparitia unui cod de eroare. Procesul va testa periodic disparitia erorii, adica eliberarea resursei solicitate. Interblocarea poate fi definită formal astfel: o mulţime de procese se află în interblocare dacă fiecare proces din mulţime aşteaptă un eveniment care poate fi furnizat numai de către alt proces din mulţime. Pentru a fi posibilă interblocarea trebuie îndeplinite următoarele patru condiţii: 1. Condiţia de excludere mutuală. Fiecare resursă este fie alocată unui singur proces, fie disponibilă 2. Condiţia de deţinere şi aşteptare. Procesele care deţin resurse, pe care le-au obţinut mai înainte, pot cere noi resurse. 3. Condiţia de lipsă a prelevării forţate. Resursele la care s-a obţinut deja accesul nu pot fi luate cu forţa de la un proces. Ele trebuie să fie eliberate în mod explicit de procesul care le deţine.

Sisteme de operare, Curs 5, pag. 6/8 4. Condiţia de aşteptare circulară. Trebuie să existe un lanţ circular de două sau mai multe procese, fiecare din ele aşteptând accesul la o resursă deţinută de următorul membru al lanţului. Toate aceste patru condiţii trebuie să fie îndeplinite pentru a fi posibilă interblocarea. Dacă una dintre ele nu este îndeplinită atunci nu este posibilă nicio interblocare. 3.11.1 Modelarea interblocărilor Interblocările se modelează cu ajutorul grafurilor orientate. Grafurile au doua tipuri de noduri: - Noduri procese (simbolizat cu un cerc) - Noduri resurse (simbolizat cu un patrat) Un arc dinspre un nod resursă către un nod proces semnifică faptul că resursa a fost solicitată şi alocată, cu alte cuvinte că este deţinută de către procesul respectiv: R

A

Un arc dinspre un nod proces catre un nod resursa semnifică faptul că procesul este blocat asteptând eliberarea resursei respective, în vederea solicitării şi obţinerii ei: B

R

Folosind aceste reprezentări se poate reprezenta grafic, o situatie de interblocare: D

T

U

C

Se remarcă un ciclu în care sunt implicate resursele T, U si procesele D,C interblocate. 3.11.2 Detectarea interblocării Aceasta tehnică porneşte de la premiza că este posibil să apara în timpul prelucrărilor situaţii de interblocare, caz în care se încearcă detectarea lor şi apoi întreprinderea de acţiuni de ieşire din această situaţie. Considerăm ca exemplu, situaţia în care sunt implicate şapte procese A...G şi resursele R...W. Starea sistemului este urmatoarea: 1. Procesul A are alocat R si solicita S; 2. Procesul B nu are alocat nimic si solicita T; 3. Procesul C nu are alocat nimic dar solicita S;

Sisteme de operare, Curs 5, pag. 7/8 4. 5. 6. 7.

Procesul D are alocat U si solicita S si T; Procesul E are alocat T si solicita V; Procesul F are alocat W si solicita S; Procesul G are alocat V si solicita U.

De asemenea starea sistemului este ilustrată grafic şi în figura următoare: R

A

S

B

T

C

S S

U

D T

T

E

V

W

F

S

V

G

U

Pentru situaţia descrisă se pune intrebarea dacă sistemul se află în interblocare, iar dacă da, care sunt procesele implicate in interblocare. Pentru a rezolva aceasta problema vom construi graful resurselor:

R

A

C

S

D

F

U

W

G

B

T

Se poate observa cu uşurinţă că graful resurselor conţine un ciclu:

E

V

Sisteme de operare, Curs 5, pag. 8/8 D

U

T

E

V

G

De asemenea, remarcăm că procesele implicate în starea de interblocare sunt D,E şi G. Este relativ simplu de a remarca „vizual” procesele interblocate, dar pentru a face acelaşi lucru automat, este necesar un algoritm formal pentru detectarea interblocarilor. Acest algoritm se bazeaza pe unul din algoritmii de detectare a ciclurilor în grafurile orientate. 3.11.3 Ieşirea din starea de interblocare prin preempţiune In anumite situatii este posibil de a „retrage” temporar o resursă, procesului caruia i-a fost alocata şi atribuită altui proces. Acest lucru însă este destul de dificil de realizat şi presupune că este posibila prelevarea forţată a resursei de la un proces şi de a o da altui proces să o folosească, după care să urmez returnarea ei procesului iniţial fără ca acesta să „observe” acest lucru (fără ca acesta să fie perturbat). De multe ori restaurarea în acest mod este chiar imposibilă. Alegerea procesului care să fie suspendat depinde în mare măsură de resursele lui, dacă pot fi returnate cu uşurinţă sau nu. 3.11.4 Ieşirea din starea de interblocare prin revenire (rollback) Aceasta metodă se bazează pe salvarea periodică a „contextelor proceselor” de către sistemul de operare. Acesta copiază într-un fişier informaţiile legate de proces (imaginea memoriei, starea resurselor, etc) astfel încât reconstituind această stare, procesul să poata fi reluat exact din punctul în care s-a salvat contextul acestuia. Pentru a putea fi lansat din oricare moment anterior salvat, noile salvări ale c...