Asynchronous Circuits for Token-Ring Mutual Exclusion.

摘要

We have described three algorithms for distributed mutual exclusion on a ring. All algorithms use a token to select a candidate. We have already implemented the most efficient of these algorithms as an asynchronous VLSI circuit. We are now going to implement the simplest one. An arbitrary number (> 1) of cyclic automata, called 'masters,' make independent requests for exclusive access to a shared resource. The circuit should handle the requests from the masters in such a way that any request is eventually granted, and there is at most one master using the shared resource at any time. The masters are independent of each other: They do not communicate with each other, and the activity of a master not using the resource should not influence the activity of other masters. A master, M, communicates with its private server, m. When M wants to use the shared resource (M is said to be a candidate), it issues a request to m. When the request is accepted, M uses that resource (for a finite period of time), and then informs m that the resource is free again. The servers are connected in a ring. At any time, exactly one (arbitrary) server holds a 'privilege,' or 'token.' The token circulates continuously around the ring of servers, and only the server that holds the token may grant the resource to its master, which guarantees mutual exclusion on the access to the resource.