Mutual Exclusion Flashcards
What is the Critical Section?
When more than one processes can access the same code segment, contain shared variable or resources, required to maintain the consistency of variables, the values depend on the sequence of execution of instruction.
What are the 4 Mutual Exclusion Requirements?
No Deadlock, No Starvation, Fairness, Fault Tolerance
Describe Safety and Liveness Properties.
Safety ensures one process can remain in its critical section at any time and is free from deadlock. Liveness ensures every process trying to enter its critical section must eventually succeed.
Describe Fairness and Performance Properties.
Fairness ensures access to critical section should happen in fair order. Performance ensures: minimizing the number of messages in sent to each entry/exit operation, client delay when entering/exiting critical section, synchronization delay which is the time between exiting critical section and the next entering.
What are the 3 types of Mutual Exclusion Solutions?
1) Token-Based Algorithms: Centralised, Ring and Raymond’s Algorithm
2) Non-Token Based Algorithms: Lamport’s and Ricart-Agrawala
3) Quorum based approach: Maekawa’s Algorithm.
Describe Token-Based Algorithms.
-A unique token is shared among all sites
-If a site possesses the unique token it is allowed to enter the critical section
-Uses sequence number to order requests
Sequence numbers used to identify old and current requests
-Each token is unique
What are the Safety and Liveness Properties of the Centralised Algorithm?
Safety Properties: Server ensures grant is only sent after a release is received, Queue ensures only one process is eligible to enter critical section.
Liveness Properties: Server maintains a queue so all processes will eventually enter critical section in order.
What are the Performance and Fairness Properties of the Centralised Algorithm?
Performance Properties:
-enter overhead
-entry delay: message round trip
-synchronization delay: message round trip
-single point of failure
-server can be bottleneck
-server must be known (or elected)
Fairness Properties:
-Server maintains a queue so all processes will eventually enter critical section in order
-Can not ensure happened-before ordering if in an asynchronous system
What are the Safety Properties and Liveness Properties of the Ring Algorithm?
Safety Properties:
-There is only one token and the critical section can only be entered when the process holds the token, therefore only one process can enter the critical section at any time.
-Deadlock free because only one token.
Liveness Properties:
-Every process gets access to the critical section because the token is passed onto the next process after each critical section.
What are the Fairness Properties and Performance Properties of the Ring Algorithm?
Fairness Properties:
-Access to critical section is not fair.
-Order is based on ring and the location of the token.
Performance Properties:
-Enter : 0 to N messages, exit : 0 message
-Delay entering: 0 to N messages, delay exiting : 0
-Synchronization delay: 1 to N-1 messages.
-Token circulating consumes bandwidth.
Describe Raymond’s Tree Based Algorithm.
-Each node has only one parent
-A child node can only send requests to its parents
-Each node maintains a FIFO queue of requests
-If any node is forwarding privilege to other node and has non-empty queue. then it forwards a request message.
What are the Safety and Liveness Properties of Raymond’s Tree Algorithm?
Safety Properties:
-Only one process can hold the privileged token.
-Deadlock is impossible.
Liveness Properties:
-Algorithm can cause starvation if it used greedily, where a site can execute the critical section on receiving the token even when its request is not on the top of the request queue.
What are the Fairness and Performance Properties of Raymond’s Tree Algorithm?
Fairness Properties:
-Everyone is allowed to hold the token.
Performance Properties:
-Enter : 0 to N messages, exit: 1 message.
-Delay Entering: 0 to N messages, delay exiting: 0
-Synchronization delay: (log N / 2)
-The message complexity of this algorithm is O (log N ) as the average distance between any two nodes in a tree with N nodes is log N.
Describe Non-Token Based Algorithms:
-A site communicates with other sites to determine which sites should execute in the critical section.
-Uses timestamps instead of sequence number to order requests.
-Whenever a request is received it gets a timestamp.
-Timestamps used to resolve any conflicts between requests.
-Maintain a logical clock.
What are the Safety and Liveness Algorithms of the Ricart-Agrawala Algorithm?
Safety Properties:
-If a process in the critical section, it doesn’t reply until it exits.
-If more than one process is requesting, process with lowest timestamp will get all N-1 replies first.
Liveness Properties :
-total ordering of timestamps ensures each request will eventually get all replies.
