Mutual exclusion for a critical section access has two required and one desirabl

Question

Mutual exclusion for a critical section access has two required and one desirable properties:

1. Safety: at most one process executes the critical section at a time.

2. Liveness: requests to enter and exit the critical section eventually succeed.

3. (Optional property) Ordering: if one request to enter the critical section happens before a second one, access is granted in that order.

Processes may be multi-threaded, in which case a process may do other tasks while waiting for access. Part of this other processing may entail messages to another process which triggers it to request critical section access. The ordering property guarantees the rst process gets access rst in this case. When ordering is required, it is assumed that all requests for the critical section have a ”happens before” relationship. With the ring algorithm, suppose that all processes are correct, so a process cannot die and fail to release the lock for the critical section. Does the ring algorithm for mutual exclusion assure the ordering property holds? Either explain why, or give an example of how processes may not be given access in happens-before order.

Explanation / Answer

In Mutual exclusion, a critical section can be used by one process at a time.

Now, In a ring algorithm, each process will know about its successor. So when a process gets completed it will send a message to its successor process. It is assumed that each process completed successfully and used critical section using ring algorithm. So it will notify its successor process to get access to a critical section. In this case, it will satisfy "happens before" order successfully.

Now, what if any process lost or crashed, its neighbor will get notified and neighbor process will send (election ) message to its successor process. So when that failed process is ready, it will get added at last in ring algorithm. So this entire process will change the order of process. So initial order of processes will not be served in this case.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.