Algoritmus Ricart – Agrawala - Ricart–Agrawala algorithm

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Algoritmus Ricart – Agrawala“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Algoritmus Ricart-Agrawala je algoritmus pro vzájemné vyloučení na distribuovaný systém. Tento algoritmus je rozšířením a optimalizací Lamportův distribuovaný algoritmus vzájemného vyloučení odstraněním potřeby ${displaystyle ack}$ zprávy^[1]. Byl vyvinut společností Glenn Ricart a Ashok Agrawala.

Algoritmus

Terminologie

• A stránky je jakékoli výpočetní zařízení, které spouští Ricart-Agrawala Algorithm
• The požadující web je web, který požaduje vstup do kritické sekce.
• The přijímající stránky je každý další web, který přijímá požadavek z požadujícího webu.

Algoritmus

Žádající stránky

• Odešle zprávu na všechny weby. Tato zpráva obsahuje název webu a jeho aktuální časovou značku logické hodiny (o kterém se předpokládá, že bude synchronizován s ostatními weby)

Příjem stránek

• Po přijetí zprávy požadavku, okamžité odeslání časové značky odpověď zpráva právě tehdy, když:

• přijímací proces nemá v současné době zájem o kritickou sekci NEBO
• přijímací proces má nižší prioritu (obvykle to znamená mít pozdější časové razítko)

• Jinak proces přijímání odloží odpověď. To znamená, že odpověď bude odeslána až po dokončení procesu přijímání pomocí samotné kritické sekce.

Kritická část:

• Žádající stránka vstoupí do své kritické sekce až po přijetí všech odpovědí.
• Po opuštění kritické sekce web odešle všechny zprávy s odloženou odpovědí.

Výkon

• Maximální počet síťových zpráv: ${displaystyle 2 * (N-1)}$
• Zpoždění synchronizace: Zpoždění šíření jedné zprávy

Běžné optimalizace

Jednou web ${displaystyle P_ {i}}$ obdržel a ${displaystyle reply}$ zpráva z webu ${displaystyle P_ {j}}$, web ${displaystyle P_ {i}}$ může do kritické sekce vstoupit několikrát bez povolení od uživatele ${displaystyle P_ {j}}$ při dalších pokusech až do okamžiku, kdy ${displaystyle P_ {i}}$ poslal (a) ${displaystyle reply}$ zpráva pro ${displaystyle P_ {j}}$. Tomu se říká Roucairol-Carvalho optimalizace nebo Roucairol-Carvalho algoritmus.

Problémy

Jedním z problémů v tomto algoritmu je selhání uzlu. V takové situaci může proces hladovět navždy. Tento problém lze vyřešit detekcí selhání uzlů po určité době.

Viz také

• Lamportův pekárenský algoritmus
• Lamportův distribuovaný algoritmus vzájemného vyloučení
• Maekawův algoritmus
• Algoritmus Suzuki – Kasami
• Raymondův algoritmus
• Algoritmus Naimi – Trehel

Reference

• Maekawa, M., Oldehoeft, A., Oldehoeft, R. (1987). Operační systémy: Advanced Concept. Benjamin / Cummings Publishing Company, Inc.