Analiza metodelor de planificare a proceselor in sisteme distribuite

Imagine preview
(10/10 din 1 vot)

Aceasta disertatie trateaza Analiza metodelor de planificare a proceselor in sisteme distribuite.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 122 fisiere pdf, exe, java, class, txt, classpath, project, dll, out, cfg, prefs de 88 de pagini (in total).

Profesor indrumator / Prezentat Profesorului: Prof. Dr. Ing. Sorin Zoican

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, o poti descarca. Ai nevoie de doar 9 puncte.

Domeniu: Electronica

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 document

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

Fisiere in arhiva (122):

  • plan
    • .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
    • 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
    • sim_plan - Copy.cfg
    • sim_plan.cfg
    • sim_plan_after_migration.cfg
  • plan_display
    • .classpath
    • .project
    • .settings
    • .settings
      • org.eclipse.jdt.core.prefs
    • 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
    • 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
    • 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
  • Analiza metodelor de planificare a proceselor in sisteme distribuite.pdf

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