Unix™ Systems Programming [Electronic resources] : Communication, Concurrency, and Threads نسخه متنی

7.6 Mutual Exclusion by Voting

One problem with the token method is that it generates continuous traffic (a form of busy waiting) even when no process enters its critical section. If all the processes need to enter their critical sections, access is granted by relative position as the token travels around the ring. An alternative approach uses an algorithm of Chang and Roberts for extrema finding [22]. Processes that need to enter their critical sections vote to see which process obtains access. This method generates traffic only when a process requires exclusive access. The approach can be modified to accommodate a variety of priority schemes in the determination of which process goes next.

Each process that is contending for mutual exclusion generates a voting message with a unique two-part ID. The first part of the ID, the sequence number, is based on a priority. The second part of the ID, the process ID, breaks ties if two processes have the same priority. Examples of priority include sequence numbers based on the current clock time or on the number of times that the process has acquired mutual exclusion in the past. In each of these strategies, the lower value corresponds to a higher priority. Use the latter strategy.

To vote, the process writes its ID message on the ring. Each process that is not participating in the vote merely passes the incoming ID messages to the next process on the ring. When a process that is voting receives an ID message, it bases its actions on the following paradigm.

1. If the incoming message has a higher ID (lower priority) than its own vote, the process throws away the incoming message.

2. If the incoming message has a lower ID (higher priority) than its own vote, the process forwards the message.

3. If the incoming message is its own message, the process has acquired mutual exclusion and can begin the critical section.

Convince yourself that the winner of the vote is the process whose ID message is the lowest for that ballot.

A process relinquishes mutual exclusion by sending a release message around the ring. Once a process detects that the vote has started either because it initiated the request or because it received a message, the process cannot initiate another vote until it detects a release message. Thus, of the processes that decided earliest to participate, the process that received access the fewest times in the past wins the election.

Implement the voting algorithm for exclusive access to standard error. Incorporate random values of the delay value, which is the last parameter of the prtastr function defined in Section 7.3. Devise a strategy for graceful exit after all of the processes have completed their output.