Mutual exclusion

We have described the problem of race conditions, when two or more concurrent processes are trying to make non-atomic changes to a data structure at the same time. Effectively, while one process is making its changes, the other process can see the data structure in an inconsistent state. In the example we gave, the inconsistent state was where one process was in the middle of incrementing a variable, but the variable in memory had not yet been updated. A more complex example in the context of operating systems, might be when one process is updating the 'runnable processes' list. Several changes must be made to pointers in the list, and it is essential that no other process (which might be running the dispatcher code, for example), gets access to the list before the update is complete.

For the system to work, the 'critical sections' of code must be mutually exclusive---only one process should be allowed to execute its critical section at any one time.

We shall examine several techniques for ensuring mutual exclusion. Ideally, we would like the following to hold true

While one process is in its critical section, no other process may enter its critical section.
A process may freely enter its critical section if no other process is in its critical section.
There may be any number and speeds of CPUs.
No process ought to wait forever to enter its critical section. (fairness)

Race conditions potentially occur anywhere where two or more processes have access to the same memory (or shared files), but for the moment we concentrate on conditions within the OS kernel, and look at how the OS can maintain mutual exclusion in its critical sections---there are several techniques.

last updated 15 February 1998