Mutual Exclusion

Next: Heavyweight vs Lightweight Up: XINU Processes and Previous: Synchronization and Semaphores

Mutual Exclusion

We now consider mutual exclusion, which ensures that two concurrent processes do not access shared data at the same time.

The following example illustrates the need for mutual exclusion:

int a[2];
int n = 0;

main()
{
    resume( create(AddChar, 200, 20, "AddChar1", 1, `a') );
    resume( create(AddChar, 200, 20, "AddChar2", 1, `b') );
}

AddChar(item)
char item;
{
    a[n++] = item;     
}

The purpose of the program is to spawn two processes, each of which adds an item to the global array a, which represents a set whose maximum size is 2. After all processes are completed, the result should be either:

n =  2;
a[1] = `a';
a[2] = `b';

n = 2;
a[1] = `b';
a[2] = `a';

The order in which the two elements are added is not important because of the set semantics.

Is one of the two results guaranteed by the above program? Certainly, if the assignment statement:

a[n++] = item;

is executed atomically, (that is executed as one unit by the processor) one of the two results is guaranteed. However, if they are not executed atomically, an invalid result may be produced, as shown below.

Assume that the statement:

a[n++] = item;

in process AddChar1 is translated into the following three atomic statements:

temp1 = n;
n++;
a[temp1] = item;

Similarly, assume that

a[n++] = item

in process AddChar2 is translated into:

temp2 = n;
n++;
a[temp2] = item

Now assume that the OS interleaves the execution of the two statements in the following manner:

/* begin executing a[n++] = item in process AddChar1 */
temp1 = n;

/* switch to a[n++] = item in process AddChar2 */
temp2 = n;
n++;
a[temp2] = item;

/* execute rest of a[n++] = item in process AddChar1 */
n++;
a[temp1] = item;

The result is:

n = 2;
a[0] = `a';
a[1] = ?;

since both temp1 and temp2 are assigned the initial value of n.

This error can be corrected by using a semaphore to disallow concurrent access to the shared data. The semaphore has an initial count of 1. Before accessing shared data, each process executes wait on the semaphore, and calls signal after it has completed. Thus the statement `a[n++] = item' is replaced by

wait(mutex);
a[n++] = item;
signal(mutex)

where mutex is the semaphore used for mutual exclusion.

Prasun Dewan
Tue Jan 13 12:23:19 EST 2004