Mutual exclusion
| On path: IPC | 1: Processes • 2: Interprocess Communication • 3: Shared Memory • 4: Files • 5: Unix Signals • 6: Pipes • 7: Sockets • 8: Synchronisation • 9: Synchronisation Barrier • 10: Atomicity • 11: Mutual exclusion • 12: Signal and Wait |
|---|
| Depends on | Processes • Synchronisation • Locks |
|---|
Sometimes it is important to perform some operations ‘atomically’; however in practice they have to be implemented with a sequence of statements. If processes (or threads) are running asynchronously there needs to be a way of guaranteeing only one thread is in a particular section of code at a time.
The problem can be reduced with a software mutex – a Boolean flag which prevents or allows progress. The flag is tested and if it is (say) FALSE the current thread can set it to TRUE and enter the critical section of code. On the other hand, if the flag was TRUE then the thread must wait until it isn’t.
At the end of this section the mutex can be set to FALSE again. This may be a simple write operation, since there can now be no competition for write permission.
A waiting process can “busy-wait”, i.e. loop, continually reading the flag until it is FALSE or it can be caused to wait. The decision on which approach to take is partly a balance between how long the expected wait might be and how expensive it is to schedule another process or thread. Normally it is desirable to keep critical sections short, so waiting times are limited. Note, however, that if a busy-waiting thread/process prevents the current ‘owner’ of the mutex proceeding, there will be deadlock.
If the choice is to wait for the mutex then, when the mutex holder must also check for and signal a waiting process so that it can restart. (Note that there could be a queue of waiting processes.)
The entry sequence – test and lock – must itself be atomic, otherwise it is possible for two processes to read and test the mutex near-simultaneously and each decide that it can proceed before the other can claim the mutex. This can happen if there is an inconveniently-timed context switch or (more probably) if there are multiple (hardware) processors (“cores”) present.
The mutex itself will normally be a location in shared memory; atomicity can be provided by using particular machine instructions, provided for this purpose.
Semaphores
A mutex provides a simple, Boolean control flag. Semaphores provide more control in that they count the number of processes allowed in the critical section, rather than always restricting this to one.
But that, as they say, is another story.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 6.5, pages 270-272 |
|---|
