My notes on bus arbitration. Deciding which bus master gets to use the bus next is called bus arbitration. There are a wide variety of schemes for bus arbitration. These may involve special hardware or extremely sophisticated bus protocols. In a bus arbitration scheme, a device (or the processor) wanting to use the bus signals a bus request and the later granted the bus. After a grant the device an use the bus, later signaling to arbiter that the bus is no longer required. The arbiter can grant the bus to another device. Most multiple bus masters have a set of bus lines for performing request or grants. A bus release line is also needed if each device does not have its own request lines. Sometimes the signals used for the bus arbitration have physically separate lines, while in other systems the data line of the bus are used for this function (though this prevents overlapping of arbitration with transfer).

Arbitration scheme usually try to balance two factors in choosing which device to grant the bus. First, each device has a bus priority, and the highest priority device must be serviced first. Second we should prefer that any device, even one with low priority never be completely locked out from the bus. This property called fairness ensures that every device that wants to use the bus is guaranteed to get it eventually. In addition to these factors more sophisticated schemes aim to reduce the time needed to arbitrate the bus.

Because arbitration time is overhead, which increases the bus time access, it should be reduced and overlapped with the bus transfers whenever possible.

Bus arbitration schemes can be divided into four broad classes.

Daisy chain arbitration

In this scheme the bus grant line is run through the device from highest priority to lowest priority (the priorities are determined by the position on the bus). A high priority device that desires bus access simply intercepts the bus grant signal, not allowing the lower priority device to see the signal.

Advantage: Simplicity.

Disadvantage: It cannot assure fairness. A low priority request may be locked out indefinitely and the use of the daisy chain grant signal also limit the bus speed.

Centralized, parallel arbitration

These schemes use multiple request lines, and the device independently requests the bus. A centralized arbiter chooses from among the devices requesting bus access and notifies the selected device that it is now bus master.

Disadvantage: It requires a central arbiter, which may become the bottleneck for bus usage.

PCI, a standard backplane bus uses a central arbitration scheme.

Distributed arbitration by self selection

These schemes also use multiple request lines, but the devices requesting bus access determine who will be granted access. Each device wanting bus access places a code indicating its identity on the bus. By examining the bus, the devices can determine highest priority device that has made a request. There is no need for a central arbiter, each device determines independently whether it is the high priority requester. This scheme however does require more lines for request signals.

The NuBus, which is the backplane bus in Apple Macintosh II, use this scheme.

Distributed arbitration by collision detection

In this scheme each device independently request the bus. Multiple simultaneous request results in a collision. The collision is detected and the scheme for selecting among the colliding parties is used.

Ethernet use this scheme.