7.5 Mutual Exclusion with Tokens

All the processes on the ring share the standard error device, and the call to prtastr described in Section 7.3 is a critical section for these processes. This section describes a simple token-based strategy for granting exclusive access to a shared device. The token can be a single character that is passed around the ring. When a given process acquires the token (reads the character from standard input), it has exclusive access to the shared device. When that process completes its use of the shared device, it writes the character to standard output so that the next process in the ring can acquire the token. The token algorithm for mutual exclusion is similar to the speaking stick (or a conch [42]) used in some cultures to enforce order at meetings. Only the person who holds the stick can speak.

The acquisition of mutual exclusion starts when the first process writes a token (just a single character) to its standard output. From then on, the processes use the following strategy.

1. Read the token from standard input.

2. Access the shared device.

3. Write the token to standard output.

If a process does not wish to access the shared device, it merely passes the token on.

What happens to the preceding algorithm at the end? After a process has completed writing its messages to standard error, it must continue passing the token until all other processes on the ring are done. One strategy for detecting termination is to replace the character token by an integer. The initial token has a zero value. If a process finishes its critical section but will still access the shared device at a later time, it just passes the token unchanged. When a process no longer needs to access the shared device, it performs the following shutdown procedure.

1. Read the token.

2. Increment the token.

3. Write the token.

4. Repeat until the token has a value equal to the number of processes in the ring.

   1. Read the token.

   2. Write the token.

5. Exit.

The repeat section of the shutdown procedure has the effect of forcing the process to wait until everyone is finished. This strategy requires that the number of processes on the ring be known.

Implement and test mutual exclusion with tokens as follows .

1. Start with version ring3 of the ring program from Section 7.3.

2. Implement mutual exclusion for standard error by using the integer token method just described but without the shutdown procedure. The critical section should include the call to prtastr .

3. Test the program with different values of the command-line arguments. In what order do the messages come out and why?

4. Vary the tests by having each process repeat the critical section a random number of times between 0 and r . Pass r as a command-line argument. Before each call to prtastr , read the token. After calling prtastr , write the token. When done with all output, execute a loop that just passes the token. (Hint: Read the man page on drand48 and its related functions. The drand48 function generates a pseudorandom double in the range [0, 1). If drand48 generates a value of x , then y = (int)(x*n) is an integer satisfying = y < n .) Use the process ID for a seed so that the processes use independent pseudorandom numbers .

5. The messages that each process writes to standard error should include the process ID and the time the operation began . Use the time function to obtain a time in seconds. Print the time in a nice format as in Example 5.8. (Page 302 in Chapter 9 has a more detailed description of time .)