PRL 35. Distribuovaný broadcast, synchronizace v distribuovaných systémech

Card Set Information

Author:
hrbi
ID:
223356
Filename:
PRL 35. Distribuovaný broadcast, synchronizace v distribuovaných systémech
Updated:
2013-06-11 07:51:09
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. PRAM
    • Parallel Random-Access Machine
    • synchronní model paralelního výpočtu ve kterém procesory komunikují sdílenou pamětí
    • výpočet probíhá po krocích: čtení sdílené paměti; lokální operace; zápis do sdílené paměti
    • přístupy do paměti: EREW(, ERCW), CREW, CRCW
    • řešení zápisových konfliktů
    • broadcast
  2. Řešení zápisových konfliktů PRAM
    • COMMON: všechny zapisované hodnoty musí být shodné
    • ARBITRARY: zapisované hodnoty mohou být různé, zapíše se libovolná
    • PRORITY: procesory mají prioritu
  3. Broadcast v PRAM
    • Hodnota uložená v paměti má být rozšířena mezi N procesory:
    • pro CREW a CRCW řešení v konstantním čase
    • pro EREW je třeba simulovat současné čtení (P1 přečte D a zpřístupní jej P2, P1 a P2 jej zpřístupní P3 a P4...)
  4. Distribuovaný broadcast
    • komunikace: známe horní mez zpoždění zprávy; lokální hodiny pro každý proces
    • m = zpráva z množiny možných zpráv
    • Každá zpráva obsahuje:
    • (a) totožnost odesilatele sender(m)
    • (b) pořadové číslo (kolikátou zprávu odesilatel poslal) seq(m)
  5. Základní vlastnosti distr. broadcastu
    • Validity: Pokud korektní proces odešle broadcast, pak všechny korektní procesy tento broadcast obdrží (dříve či později)
    • Agreement: Pokud korektní proces obdržel broadcast, potom všechny korektní procesy obdrží broadcast také (dříve či později)
    • Integrity: Každý korektní procs obdrží broadcast maximálně jednou (nedojde k zacyklení)
  6. Další vlastnosti broadcastu
    • FIFO Order: pokud nějaký proces broadcastuje zprávu m před zprávou n, potom žádný korektní proces nepřijmne zprávu n, aniž by nejdříve přijal zprávu m (tj. zprávy jsou doručovány ve stejném pořadí jak byly odeslány)
    • Causal Order: FIFO Order, ale v rámci všech procesů v systému (tj. Pokud máme 2 procesy a každý vysílá 2 broadcasty A (m,n), B(o,p) pak žádný proces nepřijme v pořadí (m,n,p,o) nebo (o,p,n,m) nebo (p,n,m,o)... Jediné správné je (m,n,o,p) nebo (o,p,m,n) nebo (m,o,p,n) nebo (m,o,n,p))
    • Total Order: doručování přesně ve stejném pořadí, jak byly broadcasty odeslány
  7. Spolehlivý broadcast
    validita, agreement, integrita
  8. Klasifikace broadcastů
    • Reliable (RBCAST): Validity + Agreement + Integrity
    • FIFO (FBCAST): reliable + FIFO Order
    • Causal (CBCAST): reliable + Causal Order
    • Atomic (ABCAST): reliable + Total Order
  9. Suma prefixů
    • jeden ze základních kamenů stavby paralelních systémů
    • operace, jejímž vstupem je binární asociativní operátor ⊕ a uspořádaná posloupnost n prvků 𝑎0, 𝑎1 , ..., 𝑎𝑛−1, jejímž výstupem je vektor (𝑎0, 𝑎0⊕𝑎1, ..., 𝑎0⊕𝑎1⊕...⊕𝑎𝑛−1)
  10. Synchronizace v distr. systémech
    • absence globálních a synchronizačních hodin
    • řešení vzájemného vyloučení:
    • (a) centralizované řešení
    • (b) distribuované (Lamportův alg., Raymondův alg.)
  11. Lamportův algoritmus
    • předpokládá oboustranné FIFO kanály mezi procesy
    • každý proces udržuje vlastní frontu požadavků
    • používá časových značek k uspořádání požadavků
    • vyžaduje 3(n-1) zpráv
    • fáze: požadavek (request), potvrzení (reply), uvolnění (release)
    • algoritmus:
    • (a) proces P pošle všem ostatním procesům request
    • (b) všechny ostatní procesy musí odpovědět reply
    • (c) po dokončení proces P pošle release
    • (d) požadavky se vyřizují dle FIFO front
  12. Raymondů algoritmus
    • procesy uspořádány do stromu
    • pracuje na bázi předávání pověření
    • udržuje frontu požadavků na pověření od procesů nižších úrovní

What would you like to do?

Home > Flashcards > Print Preview