Mutual exclusion: Difference between revisions
pc>Yuron No edit summary |
W81054ch [PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) m (1 revision imported) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 2: | Line 2: | ||
-->{{Path|IPC|11}}<!-- | -->{{Path|IPC|11}}<!-- | ||
-->{{#invoke:Dependencies|add|Processes,3|Synchronisation,2|Locks,1}} | -->{{#invoke:Dependencies|add|Processes,3|Synchronisation,2|Locks,1}} | ||
Sometimes it is important to perform some operations | Sometimes it is important to perform some operations ‘[[Atomicity|atomically]]’; however in practice they have to be implemented with a <em>sequence</em> of statements. If processes (or threads) are running asynchronously there needs to be a way of <em>guaranteeing</em> only one thread is in a particular section of code at a time. | ||
‘[[Atomicity|atomically]]’; however in practice they have | |||
to be implemented with a <em>sequence</em> of statements. If processes (or | |||
threads) are running asynchronously there needs to be a way of | |||
<em>guaranteeing</em> only one thread is in a particular section of code at a | |||
time. | |||
The problem can be reduced with a software <strong>mutex</strong> – a Boolean flag | The problem can be reduced with a software <strong>mutex</strong> – a Boolean flag which prevents or allows progress. The flag is tested and if it is (say) <code>FALSE</code> the current thread can set it to <code>TRUE</code> and enter the <strong>critical section</strong> of code. On the other hand, if the flag was <code>TRUE</code> then the thread must wait until it isn’t. | ||
which prevents or allows progress. The flag is tested and if it is | |||
(say) <code>FALSE</code> the current thread can set it to <code>TRUE</code> and enter the | |||
<strong>critical section</strong> of code. On the other hand, if the flag was | |||
<code>TRUE</code> then the thread must wait until it isn’t. | |||
At the end of this section the mutex can be set to <code>FALSE</code> again. | At the end of this section the mutex can be set to <code>FALSE</code> again. This may be a simple write operation, since there can now be no competition for write permission. | ||
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. <em>loop</em>, | A waiting process can “busy-wait”, i.e. <em>loop</em>, continually reading the flag until it is <code>FALSE</code> or it can be caused to [[Signal and Wait|<strong>wait</strong>]]. 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 <em>short</em>, 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]]. | ||
continually reading the flag until it is <code>FALSE</code> or it can be caused | |||
to [[Signal and Wait|<strong>wait</strong>]]. 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 <em>short</em>, 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 <strong>wait</strong> for the mutex then, when the mutex holder | If the choice is to <strong>wait</strong> for the mutex then, when the mutex holder must also check for and [[Signal and Wait|<strong>signal</strong>]] a waiting process so that it can restart. (Note that there could be a <em>queue</em> of waiting | ||
must also check for and [[Signal and Wait|<strong>signal</strong>]] a waiting process so | |||
that it can restart. (Note that there could be a <em>queue</em> of waiting | |||
processes.) | processes.) | ||
[[Image:mutex.png|link=|alt=Mutex]] | [[Image:mutex.png|link=|alt=Mutex]] | ||
The entry sequence – test and lock – must itself be atomic, | 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. | ||
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 [ | The mutex itself will normally be a location in [[Shared Memory|shared memory]]; [[atomicity]] can be provided by using particular machine instructions, provided for this purpose. | ||
memory]; [ | |||
using particular machine instructions, provided for this purpose. | |||
=== [[Semaphores]] === | === [[Semaphores]] === | ||
A <em>mutex</em> provides a simple, Boolean control flag. Semaphores provide | A <em>mutex</em> provides a simple, Boolean control flag. Semaphores provide more control in that they <em>count</em> the number of processes allowed in the critical section, rather than always restricting this to one. | ||
more control in that they <em>count</em> the number of processes allowed in | |||
the critical section, rather than always restricting this to one. | |||
But that, as they say, is [[Semaphores|another story]]. | But that, as they say, is [[Semaphores|another story]]. | ||
---- | ---- | ||
{{BookChapter|6.5|270-272}} | |||
{{PageGraph}} | {{PageGraph}} | ||
{{Category|Deadlock}} | {{Category|Deadlock}} | ||
{{Category|Processes}} | {{Category|Processes}} | ||
{{Category|Security}} | {{Category|Security}} |
Latest revision as of 10:03, 5 August 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; 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 |
---|