Bus Arbitration

Centralized Bus Arbitration

Centralized bus arbitration requires hardware that will grant the bus to one of the requesting devices. This hardware can be part of the CPU or it can be a separate device on the motherboard.

Centralized One Level Bus Arbiter

This scheme is represented in Fig. 3-36 (a) from the text. The lines needed are

Bus Request Line

This is a wired-OR line: the controller only knows that a request has been made by a device, but doesn't know which device made the request.

Bus Grant Line

This line is propagated through all of the devices.

When the controller sees that a bus request has been made, it asserts the Bus Grant line to the first device.
If a device made a request, it will take control of the bus when it receives the asserted Bus Grant Line and will leave the Bus Grant line negated for the next device in the chain.
If the device didn't request the bus, then it will assert the Bus Grant line for the next device in the chain.

If more than one device makes a request at the same time, then the device that is closer to the arbiter will get the bus. This is known as daisy-chaining. There is a discrete phase in the bus request cycle where requests can be made. Many devices can request the bus during this phase.

Some details that are left to the imagination:

How does the device indicate that it is done? This depends on the type of bus: synchronous or asynchronous. Synchronous means that the device has a fixed time to handle the request, if it can't handle it in that time, then it will issue a signal forcing the CPU to wait. The CPU would send a Halt signal to the Arbiter so that the start of another cycle would be delayed. Otherwise, the Arbiter will release the bus at a predefined time. Asynchronous means that the bus is more complicated and has more lines to indicate that a request has been completed. The bus would indicate to the CPU that the bus request was done. This information would then be sent to the Arbiter via a Release Bus message to indicate that the bus could be released. It is also different if DMA is being used. DMA can be used for transferring blocks of data. The CPU initiates the first read (or write) of a byte, then passes the remainder of the accesses to the DMA controller. After each byte is processed by the device, it releases the bus, so that a device with a higher priority could interrupt the current transfer. When the entire block has been transferred, an interrupt is sent to the CPU.
When is the Bus Grant line negated? When the request is completed. See above for details of how a device indicates it is done. When the Bus Grant line is negated, then a new bus cycle can begin.
How often does a device make a request before it is granted? The device asserts its Request line until it gets the bus. If a device with a high priority is busy, then a lower priority device could wait a long time before having its request granted.
When is the Bus Request Line negated? When the device finishes its request.
How does the device remember that it made a request? There must be hardware (a register) in the device that remembers that it made a request. This hardware is separate from the Bus Request line, since as soon as one device requests the bus, the Bus Request line will be asserted for all devices.
Does each device monitor Bus Request to see if the bus is available? No, this is centralized arbitration, the devices do not decide who goes next.

Centralized Two Level Bus Arbiter

This scheme is represented in Fig 3-36 (b) from the text. The lines needed are:

Bus Request: one for each level.
Bus Grant: one for each level.

This helps to alleviate the problem that the closest device to the controller always gets the device. If requests are made on more than one request line during the same clock cycle, then only the highest priority is granted the bus. The advantage to this is that once the bus has been granted to a lower priority device, a higher priority device can't steal the bus. However, if a higher priority device makes a request during each cycle, then the lower priority device will never get the bus.

Decentralized Bus Arbitration

In decentralized arbitration there isn't an arbiter, so the devices have to decide who goes next. This makes the devices more complicated, but saves the expense of having an arbiter.

VAX SBI Bus

On the VAX by DEC, there are 16 separate request lines. All devices monitor all the request lines, and know their own priority level. If a device wants the bus, it must first check to see if a higher priority device wants the bus: if not, then it gets the bus, otherwise it must wait.

Things left to the imagination:

When does a device negate its request line? After it completes its request.
How does a device know that the bus is in use? By seeing if any device with a higher priority has requested it. When all higher prority buses have finished their requests, then they will negate their request lines.

Multibus

This scheme is represented in Fig. 3-37 of the text. The necessary lines are:

Arbitration line: This acts as a line to indicate that the bus is being granted. If the IN line is asserted, then a device knows that the bus has been granted to it. If the IN line is negated, then the bus has not been granted. When the bus is available and no device wants the bus, all the IN lines for each device will be asserted. The device attempts to grab the bus by negating OUT. However, the device must wait a period of time before asserting BUSY, to make sure that a device with a higher priority hasn't negated its own OUT line.
Busy: Each device must wait until BUSY is negated before negating its OUT line in order to attempt to gain the bus. When a device gets control of the bus, it asserts BUSY and OUT. All other lines then know that their request was not granted. This is how the arbitration is resolved: each device knows that it can't request the bus until Busy is negated. After the bus master asserts the Busy line, it can assert the OUT line, so that all other devices can have the IN asserted. When the master completes its bus operation, it negates Busy. By this time, all the IN lines will have been reasserted, so another bus request cycle can begin.
Bus Request: This line indicates whether another device has made a request. If Busy is negated, then the device negates OUT and waits an undetermined amount of time to see if its IN will be negated.

Timbus

The above indicates that there are discrete phases in the bus grant cycle: 1) request bus and negate OUT, 2) wait to see if IN gets negated, if not then assert BUSY. Here is another solution that I made up that doesn't require a waiting period. See if it makes sense to you.

Arbitration Line: This acts as a line to indicate that the bus is being granted. If the IN line is asserted, then a device knows that the bus has been granted to it. If the IN line is negated, then the bus has not been granted. When the bus is available and no device wants the bus, only the IN line to the first device will be asserted, all others will be negated.
Busy: Each device must wait until Busy is negated before making a request. When a device gets control of the bus, it asserts Busy. All other lines then know that their request was not granted. This is how the arbitration is resolved: each device knows that it can't request the bus until Busy is negated. After the bus master asserts the Busy line, all other devices must negate the OUT line. When the master completes its bus operation, it negates Busy. By this time, all the OUT lines will have been negated, so another bus request cycle can begin.
Bus Request: This line indicates whether another device has made a request. Each device monitors Bus Request, if it sees that Bus Request has been asserted, but that it hasn't made a request, then as soon as it sees IN asserted, it will assert OUT so that the bus can be granted to a device further down the chain. If IN is never asserted before Bus Busy is asserted, then it knows that a device higher up in the chain received the bus. If it requests the bus before IN is asserted, then it can steal the bus if IN becomes asserted.