PRL 34. Interakce mezi procesy a typické problémy paralelismu

Card Set Information

Author:
hrbi
ID:
223354
Filename:
PRL 34. Interakce mezi procesy a typické problémy paralelismu
Updated:
2013-06-11 06:48:25
Tags:
prl
Folders:

Description:
szz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Interakce mezi procesy
    • kooperace: spolupráce na úkolu, je třeba synchronizace (čtenáři x písaři)
    • soupeření: o omezené zdroje (producent x konzument), mutual exclusion = výlučný přístup
  2. Požadavky/vlastnosti kritické sekce (KS)
    • Maximálně jeden proces je v KS.
    • Pokud v KS není žádný proces, proces který do ní chce se tam musí dostat bez prodlení.
  3. Mutual exclusion (vzájemné vyloučení)
    • hardwarové: atomické instrukce test-and-set a swap
    • OS: semafory, monitory
    • softwarové (bez podpory OS): Dekkrův alg., Petersonův alg., operátor S>, Critical region
  4. Test-and-set
    • shared var lock = 0;
    • repeat
    • while testAndSet(&lock) do skip;
    • critical section
    • lock = 0;
    • remainder section
    • until false;
  5. Atomic Swap
    • shared var lock = 0;
    • repeat
    • key := 1;
    • repeat
    • swap (&lock, &key);
    • until key=0;
    • critical section
    • lock := 0;
    • remainder section
    • until false;
  6. Semafor
    • low-level
    • Slouží k určení výlučného přístupu k datům.
    • Použití semaforu pro synchronizaci: fronta je nastavená na 0.
    • Kritická sekce je mezi instrukcemi P a V.
    • Dvě atomické operace:
  7. Monitor
    • high-level
    • eqvivalent semaforu, ale jednodušší na ovládání
    • zajišťuje exkluzivitu přístupu k datům
    • operace wait(a) a signal(a)
    • narozdíl od semaforu wait(a) VŽDY blokuje proces, zatímco P(S) blokuje jen když je counter < 0
  8. Dekkrův algorimus
    • // flagy žádosti o vstup do kritické sekce
    • // označení aktuálního kola
    • // proces žádá o vstup do kritické sekce (nastaví flag žádosti)
    • // proces ověřuje pokud o vstup žádá i druhý proces
    • // Pokud je právě kolo druhého procesu ...
    • // ... proces se vzdá své žádosti o krit. sekci ...
    • // ... a čeká dokud neskončí kolo druhého procesu
    • // Poté znovu nastaví svoji žádost o kritickou sekci
    • // Proces vstupuje do krit. sekce pokud druhý proces flag nenastavil
    • // Proces nastaví kolo na druhý proces
  9. Petersonův algoritmus
    • // flagy žádosti o vstup do kritické sekce
    • // označení aktuálního kola
    • // Proces žádá o krit. sekci
    • // Proces nastaví kolo na druhý proces
    • // Čeká dokud je kolo druhého procesu a žádá o krit. sekci
    • // Po dokončení krit. sekce proces stáhne žádost o krit sekci
  10. Operátor S>
    • je původně pouze teoretický operátor, implementovaný ve vyšších programovacích jazycích pro paralelní programování
    • problémová implementace
    • <> - atomičnost; B - Bool expr; S - sekvence příkazů
    • S je atomicky vykonaná jen když je B = true
    • příklad: 0 → s = s - 1>
  11. Critical region
    • obalení semaforů ve vyšších jazycích
    • vymezení klíčovým slovem region
    • deklaruje sdílenou proměnnou shared
    • pokud se zanořuje, může dojít ke konfliktu
    • jednoduchá implementace (téměř makro)
    • Conditional Critical Region - rozšíření o podmínku, složitá implementace
  12. Typické problémy paralelismu
    • deadlock, starvation
    • Večeřící filozofové
    • Čtenáři a písaři
    • Producenti a konzumenti

What would you like to do?

Home > Flashcards > Print Preview