H8: Coordination Flashcards
(26 cards)
Wat zijn de regels voor distributed mutual exclusion? (3)
- Geen shared variables tussen processen
- Geen OS support
- Alleen message passing wordt gebruikt
Welke failure modes zijn er bij het Mutual Exclusion probleem? (3)
- Kanaal fouten
- process fouten
- processen gedragen zich (verlaten kritische zone uiteindelijk)
Wat zijn de metrics van een goede Mutual Exclusion Issue oplossing? (3) Welke zijn verplicht?
- Safe: max 1 in kritische sectie tegelijk
- Liveliness: Elke process entered / leaved uiteindelijk, geen starvations en deadlocks
- Fair (Bonus): logische clock
Welke commands in kritische sectie API? (3)
- enter()
- resourceAccess()
- exit()
Wat zijn de evaluatie metrics kritische sectie probleem? (3)
- Bandwith consumption: Aantal message om kritische sectie te leaven / enteren
- Client Delay: tijd om kritische sectie te enteren / verlaten. Gemeten bij UNLOADED systeem, dit gaat over het netwerk delay
- System throughput: Hoeveel processen kunnen per tijdseenheid kritische sectie in. Hangt af van access time natuurlijk, dus om te meten gebruiken we de synchronisatie-delay.
Wat is synchronisatiedelay?
De gemiddelde tijd tussen vorige process dat leaved en nieuw process dat entered.
Hoe werkt het centrale server algoritme?
Een process request access aan de server, server grant het of zet het in queue. Granting wordt met een token gedaan die gelijk is aan het huidige process id in de kritische sector of gelijk aan -1.
Waarom centrale server algoritme OK?
- Safe: Token variable guard het
- Liveliness: elke process entered en kan altijd leaven
- Fairness: Queue FIFO
Wat zijn de evaluatie metrics van het centrale server algoritme?
- Bandwith: 3 messages
- Client delay: 2s (want leave blokt niet)
- Synchronisatie delay: 2s (leave + grant)
Hoe werkt het ring-based algoritme?
Token wordt doorgegeven totdat een proces hem nodig heeft.
Is het ring-based algoritme OK?
- Safe: er is maar 1 token
- Liveliness: Geen starvation + token wordt altijd doorgegeven
- Fair: Nee, moet geluk hebben
Wat zijn de evaluatie metrics van het ring algoritme?
- bandwith: (N + 1)/2
- client delay: Ns/2
- synchronisatie delay: (N + 1)s/2
Hoe werkt Ricard-Agrawala?
Multicasten tot alle andere processen het eens zijn. Elk proces heeft 3 staten: “Released, Wanted en Held”. Gebruikt Lamport clock (logische clock) en queue voor requests.
Is Ricard-Agrawala OK?
- Safe: Heel bewijs, maar komt neer op dat (Ti, Pi) < (Tj, Pj) bij wanted zit.
- Liveliness: Elk request is eventually granted
- fair: FIFO
Wat zijn de evaluatie metrics van Ricard-Agrawala?
- Bandwidth: N + (N-1) = 2N - 1
- Client delay: 2s
- Synchronisatie delay: 1s
Hoe werkt Maekawa Voting?
Voting sets, moet alle votes hebben.
Hoe groot zijn de voting sets?
liefst sqrt(N), maar IRL meestal 2sqrt(N)
Is Maekawa Voting OK?
- Safety: Ja, elk proces kan maar voor 1 proces voten en votings sets hebben altijd doorsnede
- Liveliness: Prone tegen deadlock als doorsnede van 2 votings sets 2 is, en beide anders gevote zijn
- Fairness: Starvation kan zeker gebeuren
Oplossing: Lamport clocks
Wat zijn voor Maekawa Voting de evaluatie metrics?
- Bandwidth: 2KM + KM
- Client delay: 2s
- Synchronisatie Delay: 2s
Wat zijn de metrics van OK Elections? (2)
- Safety: Elke participant moet Electedi = ? of Electedi = P, met P het proces wat gekozen is.
- Liveliness: Alle processen pi doen mee, uiteindelijk oftewel een participant verkozen, oftewel crash
Wat zijn de Evaluatie Metrics van elections? (2)
- Bandwidth: Messages voor election
- Turnaround time: time needed voor election
Hoe werkt het Ring Algoritme van Chang-Roberts?
In ring gaan en zoeken tot proces met grootste ID, als een election message krijg met je eigen id, elect je jezelf en stuurt iedereen deze election message door.
Is Chang-Roberts OK?
- Safety: Ja, kan maar 1 proces geforward worden omdat ID’s unique zijn
- Liveliness: Cirkel stopt uiteindelijk na max 3 rotaties
Wat zijn de evaluatie metrics van Chang-Roberts?
- Bandwidth: 2NM tot (3N-1)M -> (5N-1)M/2
- Turnaround time: 2Ns tot (3N-1)s -> (5N-1)s/2
