Raymondův algoritmus - Raymonds algorithm - Wikipedia
Raymondův algoritmus je zámek založený na algoritmu pro vzájemné vyloučení na distribuovaný systém. Ukládá logickou strukturu (a K-ary strom ) na distribuovaných zdrojích. Jak je definováno, každý uzel má pouze jednoho nadřazeného, ke kterému jsou učiněny všechny požadavky na dosažení tokenu.
Algoritmus
Uzlové vlastnosti
- Každý uzel má pouze jednoho rodiče, kterému jsou předávány přijaté požadavky
- Každý uzel udržuje a FIFO fronta požadavků pokaždé, když vidí token;
- Pokud některý uzel předává oprávnění jinému uzlu a má neprázdnou frontu, přepošle spolu zprávu požadavku
Algoritmus
- Pokud uzel i (nedržící token) si přeje obdržet token, aby mohl vstoupit do svého kritická sekce, odešle požadavek svému nadřazenému uzlu j.
- Pokud uzel j FIFO je prázdný, uzel j směny i do fronty FIFO; j poté vydá žádost svému rodiči, kže si přeje žeton
- Pokud uzel j FIFO fronta je ne prázdné, jednoduše se posune i do fronty
- Když uzel k má token a přijímá požadavek od j pošle token do j a sady j jako jeho rodič
- Když uzel j obdrží token od k, přeposílá token na i a i je odebrán z fronty uživatele j
- Pokud fronta j po předání tokenu do není prázdný i, j musí vydat žádost i za účelem získání tokenu zpět
Poznámka: Pokud j přeje si vyžádat token a jeho fronta je ne prázdné, pak se umístí do své vlastní fronty. Uzel j použije token pro vstup do své kritické sekce -li při přijetí tokenu je v čele fronty.
Složitost
Raymondův algoritmus zaručeně bude O (log n) na vstup kritické sekce, pokud jsou procesory organizovány do a K-ary strom. Každý procesor musí navíc uložit maximálně O (log n) bity, protože to musí sledovat O (1) sousedé.[1]
Reference
- ^ R. Chow, T. Johnson; Distribuované operační systémy a algoritmy; Addison-Wesley, 1997.