Analiza metodelor de planificare a proceselor în sisteme distribuite

Cuprins disertație Cum descarc?

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


Extras din disertație Cum descarc?

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


Fisiere în arhivă (122):

  • 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

Imagini din acest disertație Cum descarc?

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


Banii înapoi garantat!

Plătește în siguranță cu cardul și beneficiezi de garanția 200% din partea Diploma.ro.


Descarcă această disertație cu doar 10€

Simplu și rapid în doar 2 pași: completezi datele tale și plătești.

1. Numele și adresa de email:

ex. Andrei, Oana
ex. Popescu, Ionescu

* Pe adresa de email specificată vei primi link-ul de descărcare. Asigură-te că adresa este corectă și că poate primi email-uri.

2. Alege modalitatea de plată preferată:



* La pretul afișat se adaugă 19% TVA.


Hopa sus!