CS代写 GPU18) by multiple clients l Centralized Solution

Advanced Cloud
Distributed Mutual Exclusion (Distributed Locking)

Mutual Exclusion revisit

Copyright By PowCoder代写 加微信 powcoder

l ME1: Mutual Exclusion
l This is the safety property
l ME2: No Deadlock
l That is, at least 1 process is in critical section (CS) if both want to go inside l This is also a safety property
l ME3: Bounded Waiting
l If a process A wants to enter the CS but get to wait
n E.g., stuck at function waitForMyTurn()
n Such waitForMyTurn() will eventually return
n There is an upper bound of the number of times other processes can enter the CS after process A starts waiting
l E.g., O(W), where W is # of threads who want to enter CS n This is a safety or liveness property?

Mutual Exclusion revisit
Optional Requirements: – Fairness (e.g., FIFO)
l ME4: Progress
l Say no process currently in C.S.
l One of the waiting processes can eventually get in

Progress vs. Bounded waiting
l 3 people: A, B, C on an aisle AC
l Consider a solution of:
n When I crash into someone, I will move to the other side of the aisle and try to continue
B has progress
B has bounded waiting
(it actually did not need to wait)
AC also have bounded waiting. Why?

Mutual Exclusion under
l Shared-Memory Model (OS)
l Processes A, B, C want to enter Critical Section
n Use of extra shared variables and/or atomic instructions to implement sleep-lock, spin-lock, or lock-free
l Distributed Model
l E.g., Mutually exclusive access to a shared resource
(e.g., GPU18) by multiple clients l Centralized Solution
n A standalone process be a central coordinator
n Can solve ME but may suffer from no FIFO l Decentralized Solutions:
n Message-Passing and Token-Passing
Msg x ≺ yàprocess i should be granted to CS first But, as channels from:
i to Houston (FIFO)
j to Houston (FIFO)
are independent, msg y may arrive first
To Houston: message x: “I want to enter CS”
To j: message m
Received m
To Houston: message y: “I want to enter CS”

Decentralized Solutions for ME
l Message-Passing
l Lamport’s solution
n Using logical clock timestamp l Ricart-Agrawala’s solution
l Maekawa’s solution
l Token-Passing
l Suzuki-Kasami’s solution l Raymond’s solution

Lamport’s solution (Assume I am process i)
l L1: If I want to enter the CS?
l send a req message to all others l i.local-queue.add()
l L2: If I receive a CS message from process y? l i.local-queue.add()
l IfIamnotintheCS
n reply y an l IfIamintheCS
n delay reply to you until I leave my CS l L3: A process can only enter the CS if
l in its local queue, its own request is the oldest (based on timestamp) among the others and
l It has received from all other processes
l L4: To exit from the CS
l i.local-queue.del()
l Senda“release”messagestoall others
l L5: When a process receives a “release” message from y,
l i.local-queue.del()

Proof of ME1 (mutual exclusion) by contradiction
l Assume i and j are entering the CS at the same time
l That implies both i and j received all ’s
l i received j’s; j received i’s;
=> j’s request is in i’s local queue and i’s request is in j’s local queue
l If i enters the CS, it implies timestamp-i is older than j’s l If j enters the CS, it implies timestamp-j is older than i’s
è Contradiction

Proof of ME3 (bounded waiting)
l By induction
l Intuition: # of processes ahead of process i who wants to enter their CS
l Base case:
l When process i makes a request
n there are at most n-1 processes in its local queue
l Induction:
l Assume there are k processes in i’s local queue (where 1 <= k <= n-1) l When process j finishes, # of processes in i’s queue is -- l All subsequent processes after i are behind i’s in its local queue l So, in a finite number of steps, # of processes before i will down to 0, and become i’s turn Analysis of Lamport’s ME solution l When i wants to enter then CS and then leave the CS l it sends n-1 messages to others,
l it receives n-1 from others, and
l Finally sends n-1 to others
l = 3(n-1) messages

Decentralized Solutions for ME
l Message-Passing l Lamport’s solution
l Ricart-Agrawala’s solution l Maekawa’s solution
l Token-Passing
l Just like there is only 1 key
l Whoever gets the key can enter the CS l Suzuki-Kasami’s solution
l Raymond’s solution

Suzuki-Kasami [Trans. On Computer System ’85]
l Only the process holds the token can access the CS
l Every process i keeps an array req[0 . . . n-1] of integers
l where req[j] stores the last received from process j
l Assuming the process i is now holding the token
l j: Requesting CS
l j increment req[j] by 1 //increment the sequence number; req[j]++
l Broadcast a request //since you don’t know which process holds the token
array last[0 … n-1]; //store the most recent seq num of i for the which i is granted the token queue Q; //storing the PID of processes waiting for the token

Suzuki-Kasami solution
l k: on receiving a request from j //everybody receives the request l Set k’s req[j] = max(k’s req[j], j’s req[j]) //k: “ok, I now know that j wants to enter the CS”
l i: on releasing the CS //who is holding the token now
l Set token.last[i] = req[i] //indicating this request has just been served l For process j with a request NOT in token.Q
n If req[j] = token.last[j]+1 //meaning process j has issued a CS request while I was holding the token l Append j to token.Q
l If token.Q is not empty
n Head = token.Q.dequeue() n Forward the token to Head
n It keeps the token
array last[0 … n-1]; //store the most recent seq num of i for the which i is granted the token queue Q; //storing the PID of processes waiting for the token

Message Complexity
l For 1 CS access (enter and leave) l broadcast n-1 requests
l On getting the token
n Receive 1 message about the token l=n

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com