Algoritmus Suzuki – Kasami - Suzuki–Kasami algorithm - Wikipedia

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 Suzuki – Kasami“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Září 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Algoritmus Suzuki – Kasami^[1] je žeton -na základě algoritmus za dosažení vzájemné vyloučení v distribuované systémy. Proces, který drží token, je jediný proces schopný vstoupit do jeho kritická sekce.

Toto je úprava Algoritmus Ricart – Agrawala^[2] ve kterém se pro dosažení kritické sekce používá zpráva ŽÁDOST a ODPOVĚĎ. ale v tomto algoritmu zavedli metodu, ve které seniority svěrák a také předáním kritické sekce do jiného uzlu zasláním jedné PRIVILEGE zprávy do jiného uzlu. Takže uzel, který má oprávnění, může použít kritickou sekci, a pokud ji nemá, nemůže. Pokud chce proces vstoupit do své kritické sekce a nemá token, vysílá zprávu požadavku všem ostatním procesům v systému. Proces, který má token, není-li aktuálně v kritické sekci, odešle token do požadujícího procesu. Algoritmus využívá zvyšování čísel požadavků, aby zprávy mohly dorazit mimo pořadí.

Popis algoritmu

Nechat ${ displaystyle n}$ být počet procesů. Každý proces je identifikován celým číslem v ${ displaystyle 1, ..., n}$.

Datové struktury

Každý proces udržuje jednu datovou strukturu:

• pole ${ displaystyle RN [n]}$ (pro číslo požadavku), kde ${ displaystyle RN_ {i} [j]}$ ukládá poslední číslo požadavku přijaté od ${ displaystyle j}$

Token obsahuje dvě datové struktury:

• pole ${ displaystyle LN [n]}$ (pro číslo poslední žádosti), kde ${ displaystyle LN [j]}$ ukládá nejnovější číslo požadavku procesu ${ displaystyle j}$ pro který byl token úspěšně udělen
• fronta Q, která ukládá ID procesů čekajících na token

Algoritmus

Vyžádání kritické sekce (CS)

Když proces ${ displaystyle i}$ chce vstoupit do CS, pokud nemá token, pak:

• zvýší jeho pořadové číslo ${ displaystyle RN_ {i} [i]}$
• odešle zprávu s požadavkem obsahující nové pořadové číslo všem procesům v systému

Uvolnění CS

Když proces ${ displaystyle i}$ opouští CS, to:

• sady ${ displaystyle LN [i]}$ tokenu rovna ${ displaystyle RN_ {i} [i]}$. To naznačuje, že jeho žádost ${ displaystyle RN_ {i} [i]}$ byl proveden
• pro každý proces ${ displaystyle k}$ není ve frontě tokenů ${ displaystyle Q}$, připojuje se ${ displaystyle k}$ na ${ displaystyle Q}$ -li ${ displaystyle RN_ {i} [k] = LN [k] +1}$. To naznačuje tento proces ${ displaystyle k}$ má vynikající požadavek
• pokud je fronta tokenů ${ displaystyle Q}$ není po této aktualizaci prázdný, objeví se ID procesu ${ displaystyle j}$ z ${ displaystyle Q}$ a odešle token na ${ displaystyle j}$
• jinak si token ponechá

Příjem požadavku

Když proces ${ displaystyle j}$ obdrží požadavek od ${ displaystyle i}$ se pořadovým číslem ${ displaystyle s}$, to:

• sady ${ displaystyle RN_ {j} [i]}$ na ${ displaystyle max (RN_ {j} [i], s)}$ (li ${ displaystyle s$, zpráva je zastaralá)
• pokud proces ${ displaystyle j}$ má token a není v CS, a pokud ${ displaystyle RN_ {j} [i] == LN [i] +1}$ (označující nevyřízený požadavek), odešle token ke zpracování ${ displaystyle i}$

Provádění CS

Proces vstoupí do CS, když získá token.

Výkon

• Buď ${ displaystyle 0}$ nebo ${ displaystyle N}$ zprávy pro vyvolání CS (žádné zprávy, pokud proces drží token; jinak ${ displaystyle N-1}$ žádosti a ${ displaystyle 1}$ odpověď)
• Zpoždění synchronizace je ${ displaystyle 0}$ nebo ${ displaystyle N}$ (${ displaystyle N-1}$ žádosti a ${ displaystyle 1}$ odpověď)

Poznámky k algoritmu

• Přístup do CS má pouze web, který aktuálně drží token

• Všechny procesy spojené s přidělením CS

• Vyžádejte si zprávy odeslané všem uzly

• Není založeno na Lamportovy logické hodiny
• Algoritmus místo toho používá pořadová čísla

• Používá se ke sledování zastaralých požadavků
• Postupují nezávisle na každém místě

Hlavní konstrukční problémy algoritmu:

• Vyprávění zastaralých požadavků od aktuálních
• Určení, který web bude mít token další

Reference