Consider the following algorithm, called algorithm X, which might or might not b
ID: 3674867 • Letter: C
Question
Consider the following algorithm, called algorithm X, which might or might not be a solution to the mutual exclusion problem. In evaluating it (unless otherwise stated) make the same assumptions discussed for Petersen's algorithm: all instructions are atomic, but there can be a context switch between processes subsequent to any instruction execution.
1. This part is easy. Assume Process 1 successfully executes the code following "negotiate to enter critical section" and is in its critical section. Now Process 2 comes along and executes its code "negotiate to enter critical section." Show that Process 2 will not get into its critical section. Show that when Process 1 completes the code following "leave critical section" Process 2 will get into its critical section.
2.This part is more difficult. Determine the correctness of algorithm X as a "solution" to the critical section problem. If it is incorrect, show an example of instruction interleaving (what I have been calling a timing chart or a race condition) where mutual exclusion is not achieved. If it is a correct solution, argue for its correctness. Is deadlock possible for this algorithm? Explain.
Explanation / Answer
Lamport's algorithm is the solution for the above mutual exclusion algorithm.
Description:1.Requests for CS are executed in the increasing order of timestamps and time is determined by logical clocks.
2.Every site Si keeps a queue, request queuei , which contains mutual exclusion requests ordered by their timestamps.
3.This algorithm requires communication channels to deliver messages the FIFO order.
The Algorithm Requesting the critical section:
When a site Si wants to enter the CS, it broadcasts a REQUEST(tsi , i) message to all other sites and places the request on request queuei . ((tsi , i) denotes the timestamp of the request.)
When a site Sj receives the REQUEST(tsi , i) message from site Si ,places site Si ’s request on request queuej and it returns a timestamped REPLY message to Si .
Executing the critical section: Site Si enters the CS when the following two conditions hold:
L1: Si has received a message with timestamp larger than (tsi , i) from all other sites.
L2: Si ’s request is at the top of request queuei .
Releasing the critical section:
Site Si , upon exiting the CS, removes its request from the top of its request queue and broadcasts a timestamped RELEASE message to all other sites.
When a site Sj receives a RELEASE message from site Si , it removes Si ’s request from its request queue.
When a site removes a request from its request queue, its own request may come at the top of the queue, enabling it to enter the CS.
correctness Theorem: Lamport’s algorithm achieves mutual exclusion.
Proof: Proof is by contradiction. Suppose two sites Si and Sj are executing the CS concurrently. For this to happen conditions L1 and L2 must hold at both the sites concurrently.
This implies that at some instant in time, say t, both Si and Sj have their own requests at the top of their request queues and condition L1 holds at them.
Without loss of generality, assume that Si ’s request has smaller timestamp than the request of Sj .
From condition L1 and FIFO property of the communication channels, it is clear that at instant t the request of Si must be present in request queuej when Sj was executing its CS.
This implies that Sj ’s own request is at the top of its own request queue when a smaller timestamp request, Si ’s request, is present in the request queuej – a contradiction!
Performance For each CS execution:- Lamport’s algorithm requires (N 1) REQUEST messages, (N 1) REPLY messages, and (N 1) RELEASE messages.
Thus, Lamport’s algorithm requires 3(N 1) messages per CS invocation.
Synchronization delay in the algorithm is T.
Algorithm:-
This algorithm works by giving each thread a number as it enters the competition for the critical section. Threads gain access to the critical resource in order of this number. The number assigned to the thread is higher than the number assigned to any thread thus far.
The assignment of this number is not protected, so two threads can get the same number. In the event of this tie, the thread with the lowest ID (position in the array of threads, the number[] array) will enter the critical section first.
While this may not be fair, it doesn't have to be. The bounded wait condition doesn't require fairness, just determinism. This approach guarantees that each thread will eventually get into the critical section. Although part of the decision about when a thread will enter the critical section is based on an arbitrary factor (thread id), the threads position in the line is determined when it enters. This means that another thread cannot "cut" in line and violating the bounded wait requirement.
If bounded wait occurs then deadlock will be raised if not deadlock will not occur.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.