CS844 U5 IP
Maekawa’s algorithm as seen by each node (here called “this” node, i)
Initially, State = Released, Voted = False
This node (i) wants the lock. // The calling thread blocks until state=Released.
State = Wanted
Multicast a request to all nodes in voting set Vi (including self)
Wait for K replies // Including from itself
State = Held // after K replies have been received
This node receives a request: // Possibly from itself
If Voted then
Queue the request without replying
else
reply
Voted = True
This node is done with the lock:
State = Released
Multicast release to all nodes in voting set Vi (including self)
This node receives a release message // Possibly from itself
Voted = False
if request queue not empty then
remove head of queue, say pk // Possibly itself
reply to pk
Voted = True
3/12/2019
1
Maekawa scenario
3/11/2019
2
Part 3: Essay
Summarize the course in your own words
4-7 or so pages.
Make it read nicely from top to bottom
Style according to APA
Reuse your own DB posts, etc., if you like
Please correct known errors.
Include (at least):
How threads and safe objects interact
Entity-life modeling
Deadlock prevention
Logical clocks
6/10/2019
3
State of Node P1 Event Action New state Queue
Released, not voted Request from P4 Reply to P4 Released, voted P4 gets lock
Relased, voted Release from P4 Released, not voted P4 is done
Released, not voted Request from P2 Reply to P2 Released, voted P2 gets lock
Released, voted Request from P3 Released, voted P3 P3's request is queued
Released, voted Release from P2 Reply to P3 Released, voted P2 done; P3 gets lock
Released, voted Release from P3 Released, not voted P3 done
Released, not voted P1 calls Acquire Multicast request Wanted, not voted Local call to Acquire
Wanted, not voted Request from P1 Reply to P1 Wanted, voted P1 receives and replies to own request
Wanted, voted Replies from P1, P2, P3, P4 Held, voted P1 gets lock
Held, voted P1 calls Release Multicast release Released, voted Local call to Release
Released, voted Release from P1 Released, not voted P1 receives own release message
Released, not voted Request from P2 Reply to P2 Released, voted P2 gets lock
Released, voted Request from P4 Released, voted P4 P4's request is queued
Released, voted P1 calls Acquire Multicast request Wanted, voted P4 Local call to Acquire
Wanted, voted Request from P1 Wanted, voted P4 ,P1 P1 queues own request
Wanted, voted Release from P2 Reply to P4 Wanted, voted P1 P2 done. P4 gets lock
Wanted, voted Release from P4 Reply to P1 Wanted, voted P4 done. P1 replies to own request
Wanted, voted Replies from P1, P2, P3, P4 Held, voted P1 gets lock
Held, voted P1 calls Release Multicast release Released, voted Local call to Release
Released, voted Release from P1 Released, not voted P1 receives own release message
State of Node P1Event ActionNew stateQueue
Released, not votedRequest from P4Reply to P4Released, votedP4 gets lock
Relased, votedRelease from P4 Released, not votedP4 is done
Released, not votedRequest from P2Reply to P2Released, votedP2 gets lock
Released, votedRequest from P3 Released, votedP3P3's request is queued
Released, votedRelease from P2Reply to P3Released, votedP2 done; P3 gets lock
Released, votedRelease from P3 Released, not votedP3 done
Released, not votedP1 calls AcquireMulticast requestWanted, not votedLocal call to Acquire
Wanted, not votedRequest from P1Reply to P1Wanted, votedP1 receives and replies to own request
Wanted, votedReplies from P1, P2, P3, P4 Held, voted P1 gets lock
Held, votedP1 calls ReleaseMulticast releaseReleased, votedLocal call to Release
Released, votedRelease from P1 Released, not votedP1 receives own release message
Released, not votedRequest from P2Reply to P2Released, votedP2 gets lock
Released, votedRequest from P4 Released, votedP4P4's request is queued
Released, votedP1 calls AcquireMulticast requestWanted, votedP4Local call to Acquire
Wanted, votedRequest from P1 Wanted, votedP4 ,P1P1 queues own request
Wanted, votedRelease from P2Reply to P4Wanted, votedP1P2 done. P4 gets lock
Wanted, votedRelease from P4Reply to P1Wanted, votedP4 done. P1 replies to own request
Wanted, votedReplies from P1, P2, P3, P4 Held, voted P1 gets lock
Held, votedP1 calls ReleaseMulticast releaseReleased, votedLocal call to Release
Released, votedRelease from P1 Released, not votedP1 receives own release message
Sheet1
| State of Node P1 | Event | Action | New state | Queue | |
| Released, not voted | Request from P4 | Reply to P4 | Released, voted | P4 gets lock | |
| Relased, voted | Release from P4 | Released, not voted | P4 is done | ||
| Released, not voted | Request from P2 | Reply to P2 | Released, voted | P2 gets lock | |
| Released, voted | Request from P3 | Released, voted | P3 | P3's request is queued | |
| Released, voted | Release from P2 | Reply to P3 | Released, voted | P2 done; P3 gets lock | |
| Released, voted | Release from P3 | Released, not voted | P3 done | ||
| Released, not voted | P1 calls Acquire | Multicast request | Wanted, not voted | Local call to Acquire | |
| Wanted, not voted | Request from P1 | Reply to P1 | Wanted, voted | P1 receives and replies to own request | |
| Wanted, voted | Replies from P1, P2, P3, P4 | Held, voted | P1 gets lock | ||
| Held, voted | P1 calls Release | Multicast release | Released, voted | Local call to Release | |
| Released, voted | Release from P1 | Released, not voted | P1 receives own release message | ||
| Released, not voted | Request from P2 | Reply to P2 | Released, voted | P2 gets lock | |
| Released, voted | Request from P4 | Released, voted | P4 | P4's request is queued | |
| Released, voted | P1 calls Acquire | Multicast request | Wanted, voted | P4 | Local call to Acquire |
| Wanted, voted | Request from P1 | Wanted, voted | P4 ,P1 | P1 queues own request | |
| Wanted, voted | Release from P2 | Reply to P4 | Wanted, voted | P1 | P2 done. P4 gets lock |
| Wanted, voted | Release from P4 | Reply to P1 | Wanted, voted | P4 done. P1 replies to own request | |
| Wanted, voted | Replies from P1, P2, P3, P4 | Held, voted | P1 gets lock | ||
| Held, voted | P1 calls Release | Multicast release | Released, voted | Local call to Release | |
| Released, voted | Release from P1 | Released, not voted | P1 receives own release message |