Mutual Exclusion
A mutex is a programming flag used to grab and release an object. When data are acquired that cannot be shared, the mutex is set to lock (typically zero), which blocks other attempts to use it.
Requirements for Mutual Exclusion:
- Mutual exclusion must be enforced :Only one process at a time is allowed into its critical section, among all processes that have critical sections for the same resource or shared object.
- A process that halts in its noncritical section must do so without interfering with other processes.
- It must not be possible for a process requiring access to a critical section to be delayed indefinitely: no deadlock or starvation.
- When no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delay.
- No assumptions are made about relative process speeds or number of processors.
- A process remains inside its critical section for a finite time only.
One approach is to leave the responsibility with the processes that wish to execute concurrently.
Hardware Support
Interrupt Disabling: In uniprocessor system, to guarantee mutual exclusion, it is sufficient to prevent a process from being interrupted. This capability can be provided in the form of primitives defined by the OS kernel for disabling and enabling interrupts.
Won’t work in a multiprocessor architecture. Because with more than one processor, it is possible (and typical) for more than one process to be executing at a time.
Special Machine Instructions: #todo
Advantages of using special machine instruction to enforce mutual exclusion:
- Applicable to any number of processes on either a single processor or multiple processors sharing main memory
- It is simple and therefore easy to verify
- It can be used to support multiple critical sections
Disadvantages:
- Busy-waiting consumes processor time
- Starvation is possible when a process leaves a critical section and more than one process is waiting
- Deadlock with two resources and two processes, each process holding one resource
- Priority inversion
- If a low priority process has the critical region and a higher priority process needs, the higher priority process will obtain the processor to wait for the critical region
- Pipeline stalls
Mutual Exclusion
We can solve mutual exclusion problem using a semaphore. See Semaphore.
In each process, a semWait (s) is executed just before its critical section. If the value of s becomes negative, the process is blocked. If the value is 1, then it is decremented to 0 and the process immediately enters its critical section; because s is no longer positive, no other process will be able to enter its critical section.
The semaphore is initialized to 1. Thus, the first process that executes a sem- Wait will be able to enter the critical section immediately, setting the value of s to 0. Any other process attempting to enter the critical section will find it busy and will be blocked, setting the value of s to −1. Any number of processes may attempt entry; each such unsuccessful attempt results in a further decrement of the value of s. When the process that initially entered its critical section departs, s is incre- mented and one of the blocked processes (if any) is removed from the queue of blocked processes associated with the semaphore and put in a Ready state. When it is next scheduled by the OS, it may enter the critical section.
Example:
Figure 5.7, based on one in [BACO03], shows a possible sequence for three processes using the mutual exclusion discipline of Figure 5.6. In this example three processes (A, B, C) access a shared resource protected by the semaphore lock. Process A executes semWait (lock); because the semaphore has a value of 1 at the time of the semWait operation, A can immediately enter its critical section and the semaphore takes on the value 0. While A is in its critical section, both B and C perform a semWait operation and are blocked pending the availability of the semaphore. When A exits its critical section and performs semSignal (lock), B, which was the first process in the queue, can now enter its critical section.
The program of Figure 5.6 can equally well handle a requirement that more than one process be allowed in its critical section at a time. This requirement is met simply by initializing the semaphore to the specified value. Thus, at any time, the value of s.count can be interpreted as follows:
- s.count ≥ 0: s.count is the number of processes that can execute semWait (s) without suspension (if no semSignal (s) is executed in the meantime). Such situations will allow semaphores to support synchronization as well as mutual exclusion.
- s.count < 0: The magnitude of s.count is the number of processes suspended in s.queue.
From CS343
Goal of simple mutual exclusion
Ensure only one thread is executing a block of code with respect to a particular object, i..e., a critical section. This capability is accomplished by mutual-exclusion code placed before (entry protocol) and possibly after (exit protocol) the critical section. The entry protocol is divided into two parts:
- doorway is a prefix in which no waiting (or unbounded looping) occurs.
- Busy waiting is one or more loops causing a delay until it is appropriate to make forward progress.
Use analogy of bathroom to explain the problems!