Lamports distribuovaný algoritmus vzájemného vyloučení - Lamports distributed mutual exclusion algorithm - Wikipedia

Viz také: Lamportův pekárenský algoritmus

Lamportův distribuovaný algoritmus vzájemného vyloučení je algoritmus založený na tvrzení pro vzájemné vyloučení na distribuovaný systém.

Algoritmus

Uzlové vlastnosti

  1. Každý proces udržuje frontu nevyřízených požadavků na zadání kritické sekce v pořadí. Fronty jsou seřazeny podle virtuálních časových razítek odvozených od Lamportova časová razítka.[1]

Algoritmus

Proces vyžádání

  1. Posunutí jeho požadavku do vlastní fronty (seřazené podle časových razítek)
  2. Odeslání požadavku do každého uzlu.
  3. Čekání na odpovědi ze všech ostatních uzlů.
  4. Pokud je vlastní požadavek v čele jeho fronty a byly přijaty všechny odpovědi, přejděte do kritické sekce.
  5. Po opuštění kritické sekce odeberte její požadavek z fronty a odešlete zprávu o vydání každému procesu.

Další procesy

  1. Po obdržení požadavku posuňte požadavek do vlastní fronty požadavků (seřazené podle časových razítek) a odpovězte časovým razítkem.
  2. Po přijetí zprávy o uvolnění odeberte odpovídající požadavek z vlastní fronty požadavků.

Složitost zprávy

Tento algoritmus vytváří 3 (N - 1) zprávy na žádost, nebo (N - 1) zprávy a 2 vysílání. 3 (N - 1) zprávy na žádost zahrnují:

  • (N - 1) celkový počet žádostí
  • (N - 1) celkový počet odpovědí
  • (N - 1) celkový počet vydání

Nevýhody

Tento algoritmus má několik nevýhod. Oni jsou:

  • Je to velmi nespolehlivé, protože selhání některého z procesů zastaví postup.
  • Má vysokou složitost zpráv 3 (N - 1) zprávy na vstup / výstup do kritické sekce.

Viz také

Reference

  1. ^ Kshemkalyani, A., & Singhal, M. Kapitola 9: Distribuované algoritmy vzájemného vyloučení. Distribuované výpočty: Principy, algoritmy a systémy (strana 10 z 93). Cambridge University Press.