This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Perhaps the most obvious way of achieving mutual exclusion is to allow a process
to disable interrupts before it enters its critical section and then enable
interrupts after it leaves its critical section.
By disabling interrupts the CPU will be unable to switch processes. This guarantees
that the process can use the shared variable without another process accessing
it.
But, disabling interrupts, is a major undertaking. At best, the computer will
not be able to service interrupts for, maybe, a long time (who knows what a
process is doing in its critical section?). At worst, the process may never
enable interrupts, thus (effectively) crashing the computer.
Although disabling interrupts might seem a good solution its disadvantages far outweigh the advantages.
Another method, which is obviously flawed, is to assign a lock variable. This
is set to (say) 1 when a process is in its critical section and reset to zero
when a processes exits its critical section.
It does not take a great leap of intuition to realise that this simply moves the problem from the shared variable to the lock variable.
| Process 0 | Process 1 |
|
While (TRUE) { } |
While (TRUE) { } |
These code fragments offer a solution to the mutual exclusion problem.
Assume the variable turn is initially set to zero.
Process 0 is allowed to run. It finds that turn is zero and is allowed
to enter its critical region. If process 1 tries to run, it will also find that
turn is zero and will have to wait (the while statement) until turn
becomes equal to 1.
When process 0 exits its critical region it sets turn to 1, which allows
process 1 to enter its critical region.
If process 0 tries to enter its critical region again it will be blocked as
turn is no longer zero.
However, there is one major flaw in this approach. Consider this sequence of
events.
· Process 0 runs, enters its critical section and exits; setting turn to 1. Process 0 is now in its non-critical section. Assume this non-critical procedure takes a long time.
· Process 1, which is a much faster process, now runs and once it has left its critical section turn is set to zero.
· Process 1 executes its non-critical section very quickly and returns to the top of the procedure.
· The situation is now that process 0 is in its non-critical section and process 1 is waiting for turn to be set to zero. In fact, there is no reason why process 1 cannot enter its critical region as process 0 is not in its critical region.
What we can see here is violation of one of the conditions that we listed above
(number 3). That is, a process, not in its critical section, is blocking another
process.
If you work through a few iterations of this solution you will see that the
processes must enter their critical sections in turn; thus this solution is
called strict alternation.
| Last Page | Back to Main Index | Next Page |
Last Updated : 13/01/2002