A First-Come-First-Serve Bus-Allocation Scheme Using Ticket Assignments

becomes available again. As soon as that happens, one among the waiting devices is allowed to become the bus-master. In most bus arbitration schemes, this choice is made without regard to the order in which the requests originally arrived; for example, daisy-chaining, device polling, and parallel priority resolution schemes. Some of the commonly used bus arbitration schemes have been reviewed by Chen and Thurber et al. Among them, polling and daisychaining are most commonly used. Polling is suitable only for slow devices, because the waiting times from bus request to bus grant are quite long, as the devices can access the bus only during preassigned time intervals. Daisy-chaining is extensively used in several minicomputers, such as the PDP-lls made by Digital Equipment Corporation (DEC). Arbitration delay in this scheme may be quite long, since it is proportional to the number of devices connected to the bus. Furthermore, by virtue of their location on the bus, the devices are assigned fixed priorities that are used for contention resolution. For faster bus arbitration, the recent computers designed by DEC and Honeywell, Inc. use distributed schemes. These schemes, and those described in Refs. 6, 7, and 8, use the same algorithm with different implementations. They are fast, modular, and flexible, but they, too, allocate fixed priorities to the devices connected to the bus. The major drawback of allocating fixed priorities to the devices is that the low priorities may have to wait indefinitely before being granted access to the bus if a few high-priority devices decide to use the bus frequently.