Maekawasův algoritmus - Maekawas algorithm - Wikipedia

Maekawův algoritmus je algoritmus pro vzájemné vyloučení na distribuovaný systém. Základem tohoto algoritmu je přístup podobný usnášeníschopnosti, kdy kterýkoli web potřebuje pouze získat oprávnění u podmnožiny jiných webů.

Algoritmus

Terminologie

• A stránky je jakékoli výpočetní zařízení, které spouští Maekawův algoritmus
• Pro každou žádost o vstup do kritické sekce:
  • 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.
• ts odkazuje na místní časovou značku systému podle jeho logické hodiny.

Algoritmus

Žádající stránky:

• Žádající web ${ displaystyle P_ {i}}$ pošle zprávu ${ displaystyle { text {požadavek}} (ts, i)}$ na všechny weby v jeho sadě kvora ${ displaystyle R_ {i}}$.

Přijímající web:

• Po přijetí a ${ displaystyle { text {požadavek}} (ts, i)}$ zprávu, přijímající web ${ displaystyle P_ {j}}$ vůle:
  • Pokud web ${ displaystyle P_ {j}}$ nemá vynikající ${ displaystyle { text {grant}}}$ zpráva (tj ${ displaystyle { text {grant}}}$ zpráva, která nebyla vydána), pak web ${ displaystyle P_ {j}}$ pošle a ${ displaystyle { text {grant}} (j)}$ zpráva na web ${ displaystyle P_ {i}}$.
  • Pokud web ${ displaystyle P_ {j}}$ má vynikající ${ displaystyle { text {grant}}}$ zpráva s procesem s vyšší prioritou než požadavek, pak web ${ displaystyle P_ {j}}$ pošle a ${ displaystyle { text {failed}} (j)}$ zpráva na web ${ displaystyle P_ {i}}$ a web ${ displaystyle P_ {j}}$ zařadí požadavek do fronty z webu ${ displaystyle P_ {i}}$.
  • Pokud web ${ displaystyle P_ {j}}$ má vynikající ${ displaystyle { text {grant}}}$ zpráva s procesem s nižší prioritou než požadavek, pak web ${ displaystyle P_ {j}}$ pošle ${ displaystyle { text {poptat}} (j)}$ zpráva procesu, kterému byl aktuálně udělen přístup do kritické sekce podle webu ${ displaystyle P_ {j}}$. (To znamená, že stránky s vynikající ${ displaystyle { text {grant}}}$ zpráva.)
• Po přijetí a ${ displaystyle { text {poptat}} (j)}$ zpráva, web ${ displaystyle P_ {k}}$ vůle:
  • Poslat ${ displaystyle { text {yield}} (k)}$ zpráva na web ${ displaystyle P_ {j}}$ jen a jen pokud web ${ displaystyle P_ {k}}$ obdržel a ${ displaystyle { text {failed}}}$ zpráva z nějakého jiného webu nebo pokud ${ displaystyle P_ {k}}$ poslal výnos na jiné stránky, ale neobdržel nový ${ displaystyle { text {grant}}}$.
• Po přijetí a ${ displaystyle { text {yield}} (k)}$ zpráva, web ${ displaystyle P_ {j}}$ vůle:
  • Poslat ${ displaystyle { text {grant}} (j)}$ zprávu k požadavku v horní části vlastní fronty požadavků. Všimněte si, že požadavky nahoře mají nejvyšší prioritu.
  • Místo ${ displaystyle P_ {k}}$ do fronty požadavků.
• Po přijetí a ${ displaystyle { text {release}} (i)}$ zpráva, web ${ displaystyle P_ {j}}$ vůle:
  • Vymazat ${ displaystyle P_ {i}}$ ze své fronty požadavků.
  • Poslat ${ displaystyle { text {grant}} (j)}$ zprávu k požadavku v horní části fronty požadavků.

Kritická část:

• Stránky ${ displaystyle P_ {i}}$ vstupuje do kritické sekce po přijetí a ${ displaystyle { text {grant}}}$ zpráva ze všech webů v ${ displaystyle R_ {i}}$.
• Po opuštění kritické sekce ${ displaystyle P_ {i}}$ pošle a ${ displaystyle { text {release}} (i)}$ zpráva všem webům v ${ displaystyle R_ {i}}$.

Sada kvora (${ displaystyle R_ {x}}$):
Sada kvora musí dodržovat následující vlastnosti:

1. ${ displaystyle forall i , forall j , [R_ {i} bigcap R_ {j} neq emptyset]}$
2. ${ displaystyle forall i , [P_ {i} v R_ ​​{i}]}$
3. ${ displaystyle forall i , [| R_ {i} | = K]}$
4. Stránky ${ displaystyle P_ {i}}$ je obsažen přesně ${ displaystyle K}$ sady požadavků

Proto:

• ${ displaystyle | R_ {i} | geq { sqrt {N-1}}}$

Výkon

• Počet síťových zpráv; ${ displaystyle 3 { sqrt {N}}}$ na ${ displaystyle 6 { sqrt {N}}}$
• Zpoždění synchronizace: 2 zpoždění šíření zpráv
• Algoritmus může uváznout bez ochrany na místě.^[1][2]

Viz také

• Lamportův pekárenský algoritmus
• Lamportův distribuovaný algoritmus vzájemného vyloučení
• Algoritmus Ricart – Agrawala
• Raymondův algoritmus

Reference

• M. Maekawa, „Algoritmus √N pro vzájemné vyloučení v decentralizovaných systémech“, ACM

Transaction in Computer Systems, sv. 3., č. 2., str. 145–159, 1985.

• Mamoru Maekawa, Arthur E. Oldehoeft, Rodney R. Oldehoeft (1987). Operační systémy: Pokročilý koncept. Benjamin / Cummings Publishing Company, Inc.
• B. Sanders (1987). Informační struktura distribuovaných algoritmů vzájemného vyloučení. ACM Transaction on Computer Systems, sv. 3, č. 2, s. 145–59.