Cuprins
- Lista Figurilor . 3
- Lista Acronimelor . 5
- Introducere . 7
- Capitolul 1. Planificarea proceselor . 8
- 1.1. Algoritmul de planificare EDF(în limba engleză Earliest Deadline First) . 10
- 1.2. Algoritmul de planificare LLREF(în limba engleză Largest Local Remaining Execution
- Time First). 11
- Capitolul 2. Migrarea Proceselor . 15
- 2.1 Decizia de migrare a proceselor pe baza determinării încărcării CPU și a memoriei . 16
- Capitolul 3 Implementarea simulatorului pentru planificarea și migrarea proceselor . 20
- 3.1. Implementarea simulatorului pentru planificarea și migrarea proceselor în limbajul C++ . 20
- 3.2. Interfața grafică a simulatorului implementată în limbajul de programare Java . 29
- 3.2.1. Interfața grafică V1 . 29
- 3.2.2. Interfața grafică V2 . 36
- Capitolul 4. Comparația metodelor de planificare pentru diverse configurații ale sistemului . 37
- 4.1 Configurații de sisteme în care se realizează doar planificarea proceselor . 37
- 4.2 Configurații de sisteme în care se realizează atât planificarea, cât și migrarea . 46
- Capitolul 5. Concluzii . 64
- Bibliografie . 65
- Anexa 1 – Codul sursă . 66
Extras din disertație
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
Bibliografie
[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
Preview document
Conținut arhivă zip
- plan
- results
- deadline_1.out
- deadline_1_after.out
- deadline_2.out
- deadline_2_after.out
- deadline_3.out
- deadline_3_after.out
- deadline_4.out
- deadline_4_after.out
- mark_deadline_1.out
- mark_deadline_1_after.out
- mark_deadline_2.out
- mark_deadline_2_after.out
- mark_deadline_3.out
- mark_deadline_3_after.out
- mark_deadline_4.out
- mark_deadline_4_after.out
- mark_period_1.out
- mark_period_1_after.out
- mark_period_2.out
- mark_period_2_after.out
- mark_period_3.out
- mark_period_3_after.out
- mark_period_4.out
- mark_period_4_after.out
- mark_start_1.out
- mark_start_1_after.out
- mark_start_2.out
- mark_start_2_after.out
- mark_start_3.out
- mark_start_3_after.out
- mark_start_4.out
- mark_start_4_after.out
- system_1.out
- system_1_after.out
- system_2.out
- system_2_after.out
- system_3.out
- system_3_after.out
- system_4.out
- system_4_after.out
- .classpath
- .project
- afiseaza_rezultate$1.class
- afiseaza_rezultate$2.class
- afiseaza_rezultate$3.class
- afiseaza_rezultate$4.class
- afiseaza_rezultate$5.class
- afiseaza_rezultate$6.class
- afiseaza_rezultate.class
- Diagram.class
- EDF_LLREF.exe
- help.txt
- libgcc_s_dw2-1.dll
- ReadFile.class
- sim_plan - Copy.cfg
- sim_plan.cfg
- sim_plan_after_migration.cfg
- plan_display
- .settings
- org.eclipse.jdt.core.prefs
- bin
- afiseaza_rezultate$1.class
- afiseaza_rezultate$2.class
- afiseaza_rezultate$3.class
- afiseaza_rezultate$4.class
- afiseaza_rezultate$5.class
- afiseaza_rezultate$6.class
- afiseaza_rezultate.class
- Diagram.class
- ReadFile.class
- results
- deadline_1.out
- deadline_1_after.out
- deadline_2.out
- deadline_2_after.out
- deadline_3.out
- deadline_3_after.out
- deadline_4.out
- deadline_4_after.out
- mark_deadline_1.out
- mark_deadline_1_after.out
- mark_deadline_2.out
- mark_deadline_2_after.out
- mark_deadline_3.out
- mark_deadline_3_after.out
- mark_deadline_4.out
- mark_deadline_4_after.out
- mark_period_1.out
- mark_period_1_after.out
- mark_period_2.out
- mark_period_2_after.out
- mark_period_3.out
- mark_period_3_after.out
- mark_period_4.out
- mark_period_4_after.out
- mark_start_1.out
- mark_start_1_after.out
- mark_start_2.out
- mark_start_2_after.out
- mark_start_3.out
- mark_start_3_after.out
- mark_start_4.out
- mark_start_4_after.out
- system_1.out
- system_1_after.out
- system_2.out
- system_2_after.out
- system_3.out
- system_3_after.out
- system_4.out
- system_4_after.out
- src
- afiseaza_rezultate.java
- Diagram.java
- ReadFile.java
- .classpath
- .project
- afiseaza_rezultate$1.class
- afiseaza_rezultate$2.class
- afiseaza_rezultate$3.class
- afiseaza_rezultate$4.class
- afiseaza_rezultate$5.class
- afiseaza_rezultate$6.class
- afiseaza_rezultate.class
- Diagram.class
- ReadFile.class
- Analiza metodelor de planificare a proceselor in sisteme distribuite.pdf