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. On the 8088 it is a separate device: the 8288 Bus Controller.

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.

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.

Some details that are left to the imagination:

  1. 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. Asynchronous means that the bus is more complicated and has more lines to indicate that a request has been completed. 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 the first byte is accessed, the CPU must send a Halt command to the Arbiter so that it won't grant the bus to another device until the current block transfer is complete. When DMA is being used, an interrupt is sent to the CPU when the block transfer is done. When the device is done, it negates its Bus Request line.
  2. When is the Bus Grant line negated? This also depends on the type of bus. A synchronous bus will have a specific time interval for the request to be processed. When this cycle is complete, then the arbiter will negate the Bus Grant line, allowing another bus cycle to begin. If the device can't handle the request in the time interval, then it must send a signal to the CPU to delay the start of the next cycle. The CPU then sends a HALT signal to the Arbiter. The Arbiter must then wait before it starts the next bus cycle. In the case of DMA, when the CPU receives the interrupt from the device then the CPU will send a Release Bus command to the Arbiter.
  3. How often does a device make a request before it is granted? It could make many attempts. Here is a possibility: the device knows that it takes a cycle for the bus request to get to the controller, another cycle for the controller to react, then one or more cycles for the signal to propagate. Perhaps a device makes a request every three cycles until it receives the bus.
  4. When is the Bus Request Line negated? The controller after it grants the bus? No, this would be like an extra line for Acknowledge. The solution is that each device asserts Bus Request until it actually is granted the bus.
  5. How does the device remember that it made a request? There must be hardware 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.
  6. 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:

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:

  1. When does a device negate its request line? After it is granted the bus.
  2. How does a device know that the bus is in use? There must be another line called Bus Busy which indicates that the bus is available. A device asserts Bus Busy when it gets the bus. The Bus Request lines are not sufficient to indicate that the bus is in use.

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.
Busy
Each device must wait until Busy is negated before making a request. When a device gets control of the bus, it asserts this line. 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.

This doesn't make sense to me. How long does the device wait until it becomes bus master, and what is the purpose of the Bus Request line? This would make more sense to me (differences from the above are in this color):

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 this line. 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.