In order that utilisation of the available bus bandwidth be maximised, the resolution of simultaneous requests for the bus must be performed in a time that is less than the bus cycle time. This means that the algorithm for assigning priority to bus devices must be implemented in hardware.
Many algorithms for assigning priorities have been devised, and their characteristics are well-known. Probably the simplest algorithm is the fixed-priority algorithm. As its name suggests, the fixed-priority algorithm assigns a fixed priority to each contender for the shared resource and allocates cycles accordingly. This algorithm is useful in single-processor bussed architectures for assigning permanent priorities to time-critical devices, such as disks, but its lack of 'fairness' makes it particularly unsuitable for multiprocessor systems. Fairness can be defined in terms of the standard deviation of average wait-times perceived by contending devices, with a low standard deviation indicating a fair arbitration algorithm. For example, an algorithm which always gives rapid attention to some devices and always gives poor attention to others, will have a significant spread of average wait-times. Conversely, an algorithm which does not favour any particular device, or group of devices, when allocating bus cycles, will have approximately equal wait-times on all devices.
A much fairer method of sharing the limited resources of the bus is the fixed time-slice algorithm, in which bus cycle x is allocated to processor |x|n regardless of whether that processor is requesting a cycle. Hence, each device gets one cycle in n, and may have to wait up to n-1 cycles before receiving attention. The relatively poor bandwidth available to individual processors makes this scheme inefficient when devices are operating sporadically or in bursts.
The fixed priority and fixed time-slice algorithms are essentially static algorithms; more sophisticated algorithms resort to using dynamic device priorities in order to combine the throughput of static priority with the fairness of time slicing. Two important algorithms of this type are the least recently used (LRU) and the cyclic priority (CP) algorithms. The LRU algorithm is a well-known algorithm from operating systems, which, as its name suggests, assigns the lowest priority to the processor which used the bus most recently and assigns the highest priority to the processor which used the bus the least recently. The usual way to implement this is with a central arbitrator containing an ordered list of bus devices. Whenever a bus device is allocated a bus cycle, the device given the cycle is placed at the bottom of the list. Then arbitration is performed by selecting the highest requesting device in the list. Conversely, the CP algorithm can be implemented as a distributed arbitration algorithm through the use of a closed daisy chain mechanism. The modification of priority occurs by assigning the highest priority to the device whose position in the chain is immediately after the device which last used the bus.
Finally, the algorithm with the minimum average wait-time (and also the smallest spread of wait-times) is the first-come-first-served algorithm. However, this requires the order of occurrence of requests to be known in order to operate correctly, and this is difficult to discern when multiple requests can occur with very short time intervals between them. In practice this algorithm is not used for bus arbitration, even though it is optimal.