Analiza metodelor de planificare a proceselor în sisteme distribuite

Introducere

În cazul sistemelor care au un număr mare de resurse şi aplicaţii care urmează să fie

executate, problema principală este planificarea acestora. Pentru ca aplicaţiile din sistem să fie cât

mai bine planificate pentru resursele sistemului este nevoie de adoptarea unor algoritmi de

planificare. Principala caracteristică a unui sistem distribuit este dinamicitatea acestuia,

caracteristică ce influenţează în mod continuu algoritmii de planificare adoptaţi. Pentru ca

aplicaţiile să fie puse în execuţie în mod eficient, planificarea trebuie să fie făcută periodic. Prin

urmare, un algoritm de planificare trebuie să fie pregătit atât pentru situaţiile în care au loc

schimbări în configuraţia sistemului cât şi pentru eşecurile propiului sistem de planificare. În unele

cazuri, se poate adopta în sistem şi un mecanism de migrare al proceselor. Acesta are rolul de a

ajuta la planificarea eficientă a proceselor, acestea fiind executate cu succes.

În această lucrare, am ales descrierea şi implementarea a două metode de planificare:

Earliest Deadline First (EDF) şi Largest Local Remaining Execution Time First(LLREF). Numele

celor doi algoritmi sugerează modul în care aceştia stabilesc prioritatea proceselor în sistem. Pe

lângă cei doi algoritmi am ales să adoptăm şi un mecanism de migrare care, în funcţie de încărcarea

procesoarelor şi a memoriei pe care o determină execuţia unui proces sau în funcţie de rata de

depăşire a deadline-ului pentru fiecare proces, va migra un proces de pe un nod încărcat pe unul mai

puţin încărcat. Am ales diverse configurări ale sistemului şi am făcut o analiză comparativă între cei

doi algoritmi şi între performanţa sistemului doar cu mecanism de planificare şi performanţa

sistemului cu mecanism de planificare şi migrare. Partea aplicativă a lucrării a presupus realizarea

unui simulator pentru planificarea şi migrarea proceselor şi a unei interfeţe grafice pentru afişarea

rezultatelor.

În primul capitol al lucrării va fi prezentat conceptul de planificare al proceselor şi vor fi

prezentaţi cei doi algoritmi de planificare(EDF, LLREF). În capitolul următor va fi prezentată

noţiunea de migrare, decizia şi mecanismul de migrare. Aceste prime două capitole vor fi urmate de

capitolul în care este prezentată atât implementarea simulatorului pentru planificarea şi migrarea

proceselor, cât şi implementarea interfeţei grafice care va afişa rezultatele planificării şi/sau

migrării. Lucrarea se încheie cu capitolul în care se adoptă diverse configuraţii ale sistemului şi se

compară performanţele celor două metode de planificare. De asemenea, se analizează şi situaţia în

care în sistem se alege şi realizarea migrării.

Capitolul 1. Planificarea proceselor

Într-un sistem de calcul care controlează mai multe procese, vor exista mai multe sarcini, atât

periodice cât şi aperiodice care trebuie să fie realizate într-o perioadă de timp limitată. Abilitatea

sistemului de a îndeplini termenele limită ale sarcinilor depinde de capacitatea acestuia de a realiza

calculele necesare. În cazul în care mai multe procese trebuie executate foarte aproape în timp unul

de altul, sistemul de calcul trebuie să planifice calculele necesare astfel încât fiecare răspuns necesar

să fie dat în limitele de timp impuse de fiecare proces în parte. Atunci când se realizează

planificarea proceselor în timp real se ţine cont de anumite proprietăţi temporare ale acestora.

Aceste proprietăţi sunt:

- Timpul de lansare (în limba engleză „ready time”) – momentul de timpul la care procesul

este gata pentru a fi rulat

- Termenul limită (în limba engleză „deadline”) – timpul până la care execuţia procesului

trebuie să fie încheiată

- Întârzierea minimă – intervalul de timp minim care trebuie să treacă înainte ca execuţia

procesului să fie începută.

- Întârzierea maximă – intervalul de timp maxim care trebuia să treacă înainte ca execuţia

procesului să fie începută

- Timpul de execuţie cel mai defavorabil – timpul maxim necesar pentru a realiza procesul

- Timpul de rulare – timpul necesar pentru a executa procesul fără a fi întrerupt

- Prioritatea

Un sistem în timp real trebuie să îndeplinească multe cereri într-o perioadă de timp limitată.

Importanţa cererii poate varia cu natura acesteia sau cu timpul disponibil pentru a primi un răspuns.

Prin urmare, alocarea resurselor trebuie să fie planificată astfel încât să le fie respectate termenele

limită ale tuturor cererilor. Acest lucru se realizează prin intermediul unui planificator care

implementează o politică de planificare, astfel determinându-se cum se vor aloca programului

resursele sistemului. Corectitudinea sistemelor în timp real este determinată atât de logica

rezultatului calculului cât şi de perioada de timp în care calculul este realizat, fiind esenţial ca

sistemul să garanteze respectarea constrângerilor de timp.

Pentru un set dat de procese, problema generală a planificării impune o ordine în care procesele

vor fi executate astfel încât diferitele constrângeri ale acestora să fie satisfăcute. De obicei,

procesele sunt caracterizate de timpul de execuţie (timpul de calcul), timpul de lansare, termenul

limită şi cantitatea de resurse de care are nevoie. Execuţia unui proces poate sau nu să fie întreruptă

(planificare peemtiva sau non-preemtiva), iar în setul de procese, poate să existe o relaţie de

precedenţă care constrânge ordinea de execuţie în timp. Sistemul în care procesele urmează să fie

executate este caracterizat de cantitatea resurselor disponibile.

Planificarea în timp real trebuie să atingă următoarele obiective:

- Constrângerilor de timp ale sistemului trebuie respectate.

- Accesul simultan la resursele și dispozitivele comune trebuie prevenite.

- Utilizare sistemului trebuie să fie eficientă în timp ce constrângerile de timp sunt respectate

- Comutarea de context prezentă în cazul planificării preemtive trebuie să aibă costuri minime