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.