Lista Figurilor . 3 Lista Acronimelor . 5 Introducere . 7 Capitolul 1. Planificarea proceselor . 8 1.1. Algoritmul de planificare EDF(in limba engleza Earliest Deadline First) . 10 1.2. Algoritmul de planificare LLREF(in limba engleza Largest Local Remaining Execution Time First). 11 Capitolul 2. Migrarea Proceselor . 15 2.1 Decizia de migrare a proceselor pe baza determinarii incarcarii CPU si a memoriei . 16 Capitolul 3 Implementarea simulatorului pentru planificarea si migrarea proceselor . 20 3.1. Implementarea simulatorului pentru planificarea si migrarea proceselor in limbajul C++ . 20 3.2. Interfata grafica a simulatorului implementata in limbajul de programare Java . 29 3.2.1. Interfata grafica V1 . 29 3.2.2. Interfata grafica V2 . 36 Capitolul 4. Comparatia metodelor de planificare pentru diverse configuratii ale sistemului . 37 4.1 Configuratii de sisteme in care se realizeaza doar planificarea proceselor . 37 4.2 Configuratii de sisteme in care se realizeaza atat planificarea, cat si migrarea . 46 Capitolul 5. Concluzii . 64 Bibliografie . 65 Anexa 1 - Codul sursa . 66
Introducere In cazul sistemelor care au un numar mare de resurse si aplicatii care urmeaza sa fie executate, problema principala este planificarea acestora. Pentru ca aplicatiile din sistem sa fie cat mai bine planificate pentru resursele sistemului este nevoie de adoptarea unor algoritmi de planificare. Principala caracteristica a unui sistem distribuit este dinamicitatea acestuia, caracteristica ce influenteaza in mod continuu algoritmii de planificare adoptati. Pentru ca aplicatiile sa fie puse in executie in mod eficient, planificarea trebuie sa fie facuta periodic. Prin urmare, un algoritm de planificare trebuie sa fie pregatit atat pentru situatiile in care au loc schimbari in configuratia sistemului cat si pentru esecurile propiului sistem de planificare. In unele cazuri, se poate adopta in sistem si un mecanism de migrare al proceselor. Acesta are rolul de a ajuta la planificarea eficienta a proceselor, acestea fiind executate cu succes. In aceasta lucrare, am ales descrierea si implementarea a doua metode de planificare: Earliest Deadline First (EDF) si Largest Local Remaining Execution Time First(LLREF). Numele celor doi algoritmi sugereaza modul in care acestia stabilesc prioritatea proceselor in sistem. Pe langa cei doi algoritmi am ales sa adoptam si un mecanism de migrare care, in functie de incarcarea procesoarelor si a memoriei pe care o determina executia unui proces sau in functie de rata de depasire a deadline-ului pentru fiecare proces, va migra un proces de pe un nod incarcat pe unul mai putin incarcat. Am ales diverse configurari ale sistemului si am facut o analiza comparativa intre cei doi algoritmi si intre performanta sistemului doar cu mecanism de planificare si performanta sistemului cu mecanism de planificare si migrare. Partea aplicativa a lucrarii a presupus realizarea unui simulator pentru planificarea si migrarea proceselor si a unei interfete grafice pentru afisarea rezultatelor. In primul capitol al lucrarii va fi prezentat conceptul de planificare al proceselor si vor fi prezentati cei doi algoritmi de planificare(EDF, LLREF). In capitolul urmator va fi prezentata notiunea de migrare, decizia si mecanismul de migrare. Aceste prime doua capitole vor fi urmate de capitolul in care este prezentata atat implementarea simulatorului pentru planificarea si migrarea proceselor, cat si implementarea interfetei grafice care va afisa rezultatele planificarii si/sau migrarii. Lucrarea se incheie cu capitolul in care se adopta diverse configuratii ale sistemului si se compara performantele celor doua metode de planificare. De asemenea, se analizeaza si situatia in care in sistem se alege si realizarea migrarii. Capitolul 1. Planificarea proceselor Intr-un sistem de calcul care controleaza mai multe procese, vor exista mai multe sarcini, atat periodice cat si aperiodice care trebuie sa fie realizate intr-o perioada de timp limitata. Abilitatea sistemului de a indeplini termenele limita ale sarcinilor depinde de capacitatea acestuia de a realiza calculele necesare. In cazul in care mai multe procese trebuie executate foarte aproape in timp unul de altul, sistemul de calcul trebuie sa planifice calculele necesare astfel incat fiecare raspuns necesar sa fie dat in limitele de timp impuse de fiecare proces in parte. Atunci cand se realizeaza planificarea proceselor in timp real se tine cont de anumite proprietati temporare ale acestora. Aceste proprietati sunt: - Timpul de lansare (in limba engleza ,,ready time") - momentul de timpul la care procesul este gata pentru a fi rulat - Termenul limita (in limba engleza ,,deadline") - timpul pana la care executia procesului trebuie sa fie incheiata - Intarzierea minima - intervalul de timp minim care trebuie sa treaca inainte ca executia procesului sa fie inceputa. - Intarzierea maxima - intervalul de timp maxim care trebuia sa treaca inainte ca executia procesului sa fie inceputa - Timpul de executie cel mai defavorabil - timpul maxim necesar pentru a realiza procesul - Timpul de rulare - timpul necesar pentru a executa procesul fara a fi intrerupt - Prioritatea Un sistem in timp real trebuie sa indeplineasca multe cereri intr-o perioada de timp limitata. Importanta cererii poate varia cu natura acesteia sau cu timpul disponibil pentru a primi un raspuns. Prin urmare, alocarea resurselor trebuie sa fie planificata astfel incat sa le fie respectate termenele limita ale tuturor cererilor. Acest lucru se realizeaza prin intermediul unui planificator care implementeaza o politica de planificare, astfel determinandu-se cum se vor aloca programului resursele sistemului. Corectitudinea sistemelor in timp real este determinata atat de logica rezultatului calculului cat si de perioada de timp in care calculul este realizat, fiind esential ca sistemul sa garanteze respectarea constrangerilor de timp. Pentru un set dat de procese, problema generala a planificarii impune o ordine in care procesele vor fi executate astfel incat diferitele constrangeri ale acestora sa fie satisfacute. De obicei, procesele sunt caracterizate de timpul de executie (timpul de calcul), timpul de lansare, termenul limita si cantitatea de resurse de care are nevoie. Executia unui proces poate sau nu sa fie intrerupta (planificare peemtiva sau non-preemtiva), iar in setul de procese, poate sa existe o relatie de precedenta care constrange ordinea de executie in timp. Sistemul in care procesele urmeaza sa fie executate este caracterizat de cantitatea resurselor disponibile. Planificarea in timp real trebuie sa atinga urmatoarele obiective: - Constrangerilor de timp ale sistemului trebuie respectate. - Accesul simultan la resursele si dispozitivele comune trebuie prevenite. - Utilizare sistemului trebuie sa fie eficienta in timp ce constrangerile de timp sunt respectate - Comutarea de context prezenta in cazul planificarii preemtive trebuie sa aiba costuri minime
[1] Veeravalli Bharadwaj, Debasish Ghose, Thomas G. Robertazzi, ,,Divisible Load Theory: A New Paradigm for Load Scheduling inDistributed Systems", Cluster Computing 6, 7-17, 2003, Kluwer Academic Publishers. Manufactured in The Netherlands [2] Hyeonjoong Cho, Binoy Ravindran, E. Douglas Jensen, ,,An Optimal Real-Time Scheduling Algorithm for Multiprocessors", ECE Dept., Virginia Tech Blacksburg, VA 24061, The MITRE Corporation Bedford, MA 01730, USA [3] Dongning Liang, Pei-Jung Ho, Bao Liu, ,,Scheduling in Distributed Systems", Department of Computer Science and Engineering University of California, San Diego [4] Arezou Mohammadi, Selim G. Akl, ,,Scheduling Algorithms for Real-Time Systems", Technical Report No. 2005-499, School of Computing Queen's University Kingston, Ontario Canada K7L 3N6, [5] N. Audsley, A. Burns, ,,Real-Time System Scheduling", report from the ESPRIT BRA Project (3092),Predicatably Dependable Computer Systems, Volume 2, Chapter 2, Part II, Department of Computer Science, University of York, UK [6] Markus Peloquin, ,,A Comparison of Scheduling Algorithms for Multiprocessors", December 13, University of Wisconsin-Madison, 2010 [7] Sorin Zoican, Roxana Zoican, Dan Galatchi,"Improved Load Balancing and Scheduling Performance in Embedded Systems with Task Migration", TELSIKS 2015, oct. 2015 (trimisa pentru revizuire) [8] http://www.vogella.com/tutorials/java.htmlaccesat la 14.03.2015 [9] http://docs.oracle.com/javase/tutorial/uiswing/accesat la 28.03.2015 [10] https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling accesat la 24.01.2015 [11] http://www.ibm.com/developerworks/java/tutorials/j-jni/j-jni.html accesat la 18.04.2015 [12] http://www.cplusplus.com/forum/general/117497/accesat la 18.04.2015 [13] http://mingw.org/wiki/sampleDLLaccesat la 19.04.2015
Plătește în siguranță cu cardul și beneficiezi de garanția 200% din partea Diploma.ro.
Simplu și rapid în doar 2 pași: completezi datele tale și plătești.
