Vzájemné vyloučení v DS

• Vzájemné vyloučení je mechanismus, který zajišťuje, že v daném okamžiku může určitý kritický úsek kódu (nebo sdílený prostředek) používat pouze jeden proces.
• Je důležitý pro zajištění konzistence a zabránění konfliktů.

Centralizované řešení

• Velmi jednoduchá myšlenka i provedení.
• Jeden uzel (rozhodčí) rozhoduje o výhradním přístupu ke sdílenému zdroji.

Postup:

• Rozhodčí drží frontu žádostí.

1. Zájemce $i$ pošle žádost.
2. Rozhodčí potvrdí OK, je-li zdroj volný, jinak dá $i$ do fronty.
3. Proces $i$ po dokončení práce pošle RELEASE.
4. Rozhodčí pošle OK dalšímu ve frontě, nebo čeká na žádost.

• Rozhodčí může selhat $\to$ to ostatní nepoznají.
• Rozhodčí může být přetížený (je to prostě bottleneck).

Ricart-Agrawala algoritmus

• Byl navržen aby umožnil procesům koordinovat svůj přístup ke sdíleným zdrojům.

• Stačí nám méně zpráv (než u využití logických hodin) a není potřeba FIFO komunikace

• Každý proces má logické hodiny.

• Procesy si posílají $2$ typy zpráv:

  • request
  • ack

Postup:

1. Proces $p_i$, který chce vstoupit zašle request $(p_i,t)$ ostatním $p_j$.
2. Proces $p_j$ při přijetí $(p_i,t)$ pošle ack pokud nechce vstoupit nebo $t$ je menší než logické hodiny procesu $p_j$, jinak si přidá $p_i$ do fronty.
3. Při přijetí $(N-1)$ ack zpráv, proces vstoupí do kritické sekce.
4. Při výstupu proces $p_i$ pošle ack všem ve frontě čekajícím procesům.

Problém:

• $N$ bodů selhání
  • Lze vyřešit opakovaným posíláním zprávy, kdy odesílatel po neobdržení odpovědí usoudí, že proces selhal.
• Vyžaduje multicast komunikaci
  • Nevhodné pro rozsáhlé systémy, protože je potřeba evidence.

Token-ring algoritmus

• Algoritmus využívající princip tokenu - speciální zpráva, která obíhá mezi uzly.

• Tento token určuje, který proces má aktuálně právo vstoupit do kritické sekce.

• Inicializace:

  • Každý uzel v systému má určený identifikátor a zná seznam všech uzlů v DS.
  • Tyto uzly jsou uspořádány do logického kruhu (obecně nezávislé na fyzické topologii).

• Token:

  • Token je speciální zpráva, která obíhá mezi uzly v kruhové síti.
  • Kdo má token, může vstoupit do kritické sekce.

• Vstup do kritické sekce:

  • Když token dorazí k uzlu, který si přeje vstoupit do kritické sekce, může vstoupit do této části kódu.
  • Během této doby ostatní uzly nemohou vstoupit do kritické sekce.

• Opuštění kritické sekce:

  • Když proces dokončí svou činnost v kritické sekci, předá token dalšímu uzlu v prstenci.

• Kruhový pohyb tokenu:

  • Token pokračuje v obíhání v kruhu.
  • Uzly, které si nepřejí vstoupit do kritické sekce, pouze předávají token dál.

Problémy:

• Ztráta tokenu
• Udržování topologie

• Je důležité poznamenat, že toto řešení funguje dobře pro malé a střední sítě. Může mít problémy s výkonem a efektivitou ve velkých systémech.

Decentralizované řešení

• Každý zdroj je replikován $N$ krát. Přitom každá replikace má svého koordinátora.
• Pokud chce proces vstoupit do kritické sekce, pošle zprávu každému koordinátorovi (tedy $N$ zpráv).
• Koordinátor může poslat pouze jedno potvrzení, pokud dostane více žádostí, ignoruje je.
• Pokud proces dostane nadpoloviční počet potvrzení, může vstoupit do kritické sekce.
• Po vystoupení z kritické sekce, informuje všechny, že odešel a může se znovu hlasovat.

Předchozí otázka Následující otázka

Všechny otázky

---

*Toto je navíc z předchozího ročníku.

Logické hodiny

• Lamportovy logické hodiny mohou být využity pro implementaci algoritmu vzájemného vyloučení v DS.

• Každý proces má logické hodiny.

• Všechny procesy si posílají 3 druhy zpráv.

  • request
  • release
  • ack

• Request:

  • Proces $p_i$ každému procesu posílá zprávu $(p_i,t)$ s hodnotou logických hodin $t$ (žádá o vstup) a zprávu si uloží do fronty.
  • Při přijetí request je $(p_i,t)$ uloženo do fronty a posláno potvrzení ack.

• Release:

  • Proces každému procesu zasílá zprávu (oznámení o výstupu), při přijetí je $(p_i,t)$ smazáno z fronty.

• Ack:

  • Potvrzení request.

Zvyšování hodin:

• Každé volání request, release, ack $\to$ hodiny $+1$.

Podmínka o vstup:

• Proces vstoupí do kritické sekce pokud má ve frontě request s hodnotou $t$.
• $t$ je menší než všechny ostatní request ve frontě.
• Obdržel potvrzení od každého uzlu s hodnotou větší než $t$ Všechny body musí platit.

Warning

Komunikace musí probíhat FIFO