Mutual exclusion: Difference between revisions
pc>Yuron No edit summary |
Yuron [PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) m (1 revision imported) |
(No difference)
|
Revision as of 12:46, 26 July 2019
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 shared memory]; [Atomicity 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.