Note: Descriptions are shown in the official language in which they were submitted.
132~28~
This invention relates to a bus organized structure having a
bus arbitration scheme in which access to the bus is based on
a variable priority system.
BACRGROUND C~F l~E INVhrNTION
In many applications, it is desirable to link a large number
of peripheral devices to a central processor or data
receiving apparatus. It is common to connect a plurality of
peripheral devices to the central processor by a single bus.
In order to allow a plurality of peripheral devices to share
a single bus, some method must be adopted to ensure that no
more than one peripheral device transmits data on the bus at
any particular time.
One known method of selecting a single peripheral device for
transmission on the bus is known as polling. Polling i5 a
technique whereby each peripheral device ~haring a bus i8
periodically interrogated by the central processor to
determine whether or not the device has data to transmit.
~here are two basic polling scheme~. In ring polling, the
peripheral devices are polled Requentially. In priority
polling, the peripheral devices are assigned a priority or
weight. Higher priority devices are polled more frequently
than are low priority devices. While polling is suitable in
3~
132~281
certain applications, where there are many peripheral devices
connected to a single processor, polling can consume an
excessive portion of central processor processing time.
A second known method of selecting a single peripheral device
for transmitting on the bus is known as bus contention-
arbitration. Under this scheme, individual peripheral devices
contend for access to the bus. Priority of access i8 granted
to one peripheral device through an appropriate arbitration
scheme.
Access to the bu~ can be controlled by providing a separate
bus wire ~BA wire) for indicating bus availability. Each
peripheral device asserts a predetermined logic level on the
BA wire when it i5 transmitting to indicate that the data
wlre of the bus is in an active condition. Each peripheral
dovice also monitors the BA wire and will not initiate
transmission when a bus active condition is detected.
Accordingly, the use of a BA wire will prevent a peripheral
device from transmitting when it detects a bu~ active
¢ondition.
Notwithstanding the use of a BA wire, it ie possible for two
or more peripheral devices to take control of the bus
simultaneously. This is because it takes a flnite time for
-- 3 --
132~2~1
the BA wire of the bus to change from the bus inactive state
to the bus active state, and for such change of state to
propagate down the BA wire from one peripheral device to
another. During this transition time, two or more peripheral
devices may simultaneously monitor a bus inactive condition
and assert a bus active condition on the BA wire of the bus.
This allows each of such peripheral devices to commence
transmitting data on the data wire of the bus simultaneously.
Accordingly, some form of arbitration scheme i5 needed to
grant priority to one of the peripheral devices.
The simplest form of arbitration is a bit collision detection
system. In such a system, each peripheral device monitors the
data wire and compares the data signals on the data wire to
the data signal~ that it is transmitting. If two peripheral
devices are transmitting at the same time, a bit colli~ion
will occur. Depending upon the configuration of the bus, a
bit ¢ollision between a logical "1" and a logical "0" results
in either a logical "1" or a logical "0". Accordingly, the
peripheral device that tran~mitted the logical level that was
not assumed by the bus will sense the bit collision and can
be configured to stop transmitting. The peripheral device
that transmitted the logical level conveyed by the bus will
not sense a bit collision and will continue transmitting.
Such a system is a data dependent priority system ln that it
accords priority based on the logic level of the data
transmitted.
-- 4 --
l32a2sl
A data dependent priority system may be suitable where there
are relatively few peripheral devices simultaneously vying
for contention of the bus and there are substantial time
periods in which the bus is inactive. Even if a peripheral
device has a relatively low priority data to transmit,
significant periods in which the bus is inactive will allow
the peripheral device to gain control of the bus within a
reasonable number of attempts. However, where there are many
peripheral devices vying for contention and the bus is in
virtually constant use, a peripheral device having a low
priority data to transmit will be repetitively refused access
to the bus. As a result, such a peripheral device may be
forced to wait an unacceptably long period of time before
uninterrupted data transmission is possible.
An improved form of arbitration in a bit collision detection
system assigns a priority to each peripheral device to
control access to the data bus. Such an arbitration scheme is
di~closed in Canadian Patent No. 832,183. In that scheme,
each peripheral device is assigned a priority and begins
transmi~sion by generating a priority code signal
representing its assigned priority. Each peripheral device
also monitors the priority code signals on the bus and
compares the bus ~ignals to its internally generated priority
code. If the peripheral device detects a signal on the bus of
higher
1320281
priority, it inhibits further transmission untll the higher
priority requester has completed its transmission. However,
an assigned priority system may not be appropriate where all
peripheral devices have identical functions to perform and
none should be preferred over others.
S~MMARY OF TEE INVENTION
The present invention provides a variable priority
arbitration scheme to ensure that a peripheral device will be
guaranteed access to the data bus within a predetermined
number of attempts. Each peripheral device is provided with
an incrementable priority byte register in which a priority
byte is stored. The priority byte is initially set to lowest
priority and is transmitted prior to transmitting data. If a
bit collision occurs and is detected by a first peripheral
device, that device recognizes that a second peripheral
device has priority and stops transmitting. The device that
i~ denied access increments the priority level of the
priority byte and retransmits. If another collision is
detected the transmission is again ceased and the priority
level is again incremented. These steps are repeated until
acce~s to the bus is gained and data transmission is
completed. Following succes~ful transmission, the priority
byte is returned to its initial priority level.
-- 6 --
132~28~
In accordance with one aspect of the present invention there
is provided, in a bus organized structure wherein a
plurality of peripheral devices are adapted to transmit data
in serial bit fashion via a common data bus, the
characteristics of said common data bus being such that when
more than one of said peripheral devices are transmitting
simultaneously, said data bus will assume a first logic level
only if all said peripheral devices are transmitting at said
first logic level and will assume a second logic level if any
one of said peripheral devices is transmitting at said second
logic level, a variable arbitration means associated with
each of said peripheral devices comprising register means for
storing a variable priority byte indicating the priority
level of the data to be transmitted by said peripheral
device, output means for transmitting onto said data bus in
euccession said priority byte and said data, bit collision
detection means for monitoring on a bit-by-bit basis the
logic level of said data bus and the logic level of said
output meane and responsive to a difference in said logic
levels to disable said output means, incrementing means
responsive to said bit collision detection means for
generating an incremented priority level of said variable
priority byte in said register means each time said output
means is disabled and for enabling said output means whereby
a subseguent transmission of said variable priority byte is
at an incremented priority level
~3~281
and means responsive to the completion of transmission of
said data by said output means for resetting the variable
priority byte in said register means to its initial priority
level.
In accordance with another aspect of the present invention
there is provided an improved method of arbitrating access to
a common data bus in a bus organized structure having a
plurality of peripheral devices adapted to transmit data in
serial bit fashion via said data bus, the characteristics of
said data bus being such that when more than one of said
peripheral devices are transmitting simultaneously, said data
bus will assume a first logic level only if all said
peripheral devices are transmitting at said first logic level
lS and will as~ume a second logic if any one of said peripheral
devlces is tran~mitting at said second logic level, the
improved method comprising the steps of storing in each of
~aid peripheral devices a variable priority byte indicating
the priority level of the data to be transmitted by said
peripheral device, transmitting by each of said peripheral
devices that desires access to said data bus said variable
priority byte followed by said data on said data bus,
monitoring by each of said transmitting peripheral devices on
a blt-by-bit basis the logic level of said data bus and the
loglc level transmitted by ~aid peripheral device for a
132028~
difference in said logic levels, disabling transmission by
each of said peripheral devices that monitors a difference in
said logic levels, incrementing the priority level of said
variable priority byte of each of said peripheral devices for
which transmission was disabled and repeating in order said
transmittingl monitoring and disabling steps until no
difference in said logic levels is monitored in said
monitoring step, setting said variable priority byte to its
initial priority level in each of said peripheral device that
has succe~sfully completed said transmitting step.
BRIEF D~SCRIPTION OF T~B DRAWINGS
Fig. 1 is a schematic diagram of one form of circuitry
~uitable for implementing the present invention~
Fig. 2 is a flow chart pertaining to the software programming
~uitable or implementing the present invention.
DBTAILBD DBSCRIPTION OP AN ILLUSTRATIVE EMBODIMæNT
Figure 1 represents a bus organized structure in which
peripheral devices 1 and 2 are connected to central processor
3 through bu~ 4. Peripheral devices 1 and 2 may for example,
be end-user operated termlnals each consi~tlng of a key pad
and a data ~torage reglster for entry and storage of data to
be transmitted to central processor 3. Central proce~sor 3
may
1320281
for example, be a microcomputer. For purposes of clarity,
only two peripheral devices are shown as being connected to
bus 4 in Figure 1. In practice, a large number of such
peripheral devices may be so connected.
Bus 4 comprises a plurality of wires. Wire assignments are in
accordance with Electronic Industries Association Standard RS
232 as follows:
1. Bus Available (BA);
2. Signal Ground ~gnd);
3. Transmit Data (TX DATA);
4. Signal Ground (gnd);
5. -15 Volts;
6. +15 Volts.
Bue 4 i~ connected at one end to the RS 232 serial
communication port on central processor 3. In accordance with
~tandard RS 232 protocol, data is represented by -15 volts
equalling a logical "1" and +15 volts e~ualling a logical
"0". The BA wire and the TXDATA wire of bus 4 are each tied
to -15 volts through pull-up resistors 5 and 6 and
accordingly are each maintained at a normal logical "1"
level.
-- 10 --
132028~
Peripheral device l is connected to bus 4 by means of
communications controller 7. Communications controller 7 may
for example be a progra~mable 8749 communications controller
integrated circuit manufactured by Intel Corporation.
Communications controller 7 is programmed to receive and
store input data and to output such data onto bus 4 in the
manner described below.
Data stored in communications controller 7 is made available
for transmission in serial format at DATA OUT terminal 8.
DATA OUT terminal 8 is connected to the TXDATA wire of bus 4
through bus driver 9 and diode 10. Similarly, a bus available
control signal is available at BA OUT terminal 11. BA OUT
terminal 11 is connected to the BA wire of bus 4 through bus
driver 12 and diode 13.
Two lnput~ allow communicat~ons controller 7 to monitor the
status of the TXDATA and BA wires of bus 4. The TXDATA line
of bus 4 is connected to DATA IN input 14 of communications
controller 7 through buffer amplifier 15 and bu~ receiver 16.
8imilarly, the BA line of bus 4 is connected to BA IN input
17 of communications controller 7 through buffer amplifier 18
and bus receiver 19.
132~281
Data for transmission on bus 4 to central processor 3 is
presented in seria~ form in fixed length data bytes at DATA
OUT terminal 8 of communications controller 7. Data is
shifted from TTL voltage levels to RS 232 voltage levels
through bus driver 9 and is driven through diode 10 onto the
TXDATA wire of bus 4. Diode 10 in effect allows
communications controller 7 to assert only a logic level "0"
on the TXDATA wire. Logic level "1" is blocked by back
biasing diode 10. A logic level "0" forward biases diode 10
into conduction and raise~ the voltage of the TXDATA wire of
bua 4 to +lS volts. Diode 10 also allows more than one
peripheral device to be connected to the same bus. Without
diode 10, DATA OUT terminal 8 of peripheral device 1 would be
tied to the corresponding DATA OUT terminals of other
peripheral devices connected to the TXDATA wire of bus 4 and
accordingly data transmission would not be possible.
Peripheral device 2 has all the same components as device 1
and operates in a similar manner.
When a peripheral device i5 transmitting, it as~erts a
logical "0" state on the BA line of bus 14 to indicate that
the bus is active. This is achieved by applying the signal at
BA OUT terminal 11 of communications controller 7 to bus
driver 12, the output of which is +15 volts representing a
logical "0".
This voltage forward biase~ diode 13 into conduction and
raises the voltage level of the BA wire of bus 4 to +15
volts.
132028~
sefore any peripheral device can transmit data on the TXDATA
wire of bus 4, it must first determine that no other
peripheral device is transmitting. This determination is made
by monitoring the BA wire of bus 4 for a logical "1" state
S (bus inactive) indicating that no other peripheral device is
transmitting.
Each peripheral device monitors the state of the BA wire of
bus 4 through BA IN terminal 17. The signal on the BA wire of
bus 4 i9 buffered by buffer amplifier 18 and is shifted from
RS 232 voltage levels to TTL voltage levels through bus
receiver 19 before being applied to BA IN terminal 17 of
communications controller 7. If the BA wire is in the
inactive state, the peripheral device can take control of bus
4 by asserting a logical "0" state (bus active) on the B~
wire as described above.
Communications controller 7 is programmed to monitor the BA
wire of bus 4 for a logical 1 state ~bus inactive) for a
perlod of 1 bit cell time before it asserts a logical "O"
state (bu~ active) on the BA wire and attempts to transmit
data on the TXDATA wire of bus 4. This ensures that noise on
the BA wire of bus 4 will not falsely indicate an inactive
bus when in fact it is active. In addition, the 1 bit cell
time delay allows the central processor to detect the break
between transmlssions from different peripheral devices.
1 32~2~
Communications controller 7 can also be programmed to
maintain a logical "0" state on the BA wire of bus 4 for a
period of time after it has completed data transmission. Thi~
ensures that no other peripheral device will gain control of
the bus 4 before a subsequent transaction between central
processor 3 and the peripheral device has been completed.
Accordingly, processor 3 does not have to contend for access
to bus 4 to complete the tran~action and is able to identify
the peripheral device that transmitted the data without
requiring additional information indicating the address
assigned to the peripheral device. The length of time that a
logical "0" state is maintained on the BA wire of bus 4 after
data transmission is completed depends upon the response time
of central proce~sor 3.
Where two peripheral devices commence tran~mitting
simultaneou~ly, a bit collision will occur~ Eaah transmitting
perlpheral device monitor~ the TXDATA wire of bu~ 4 to detect
the presence of errors due to bit collisions. Peripheral
device 1 monitors the signal on the TXDATA wire of bus 4
through DATA IN terminal 14 of communications controller 7.
The signal on the TXDA~A wire is buffered by buffer amplifier
15, shifted from RS 232 voltage levels to TTL voltage levels
by bu~ receiver 16 and is applied to DATA IN terminal 14.
Peripheral device 1 compares the bu~ signal at DATA IN
132~281
terminal 14 with the transmitted signal at DATA O~T terminal
8. If the signals are identical, no error has been detected
and peripheral device 1 continues transmitting. If on the
other hand the bus signal at DATA IN terminal 14 is different
than the transmitted signal, communications controller 7
detects an error and immediately ceases transmitting.
When two peripheral devices are transmitting simultaneously
on the TXDATA wire, only one peripheral device will detect a
bit collision. If both peripheral devices transmit a logical
"1" on the TXDATA wire, the resulting bit collision produces
a logical "1". Accordingly, neither peripheral device will
sense an error and both will continue to transmit. Similarly,
if both peripheral devices transmit a logical "0", the
resulting bit collision produces a logical "0" and both
peripheral devices continue to transmit. However, when one
peripheral device transmits a logical "0" and the other
transmlt~ a logical "1", the TXDATA wire will be pulled to
the logical "0" condition. The peripheral device that
tran~mitted the "0" bit will detect no error and will
continue to trancmit. The peripheral device that transmitted
the "1" bit will detect an error and will be forced to cease
transmitting and relinquish control of bus 4 to the other
peripheral device.
- 15 -
13~0281
This bit collision detection technique will function
correctly only if the end-to-end propagation time of a signal
on the bus is less than one-half of one bit cell time. Tnis
ensures that all peripheral devices will have received the
transmitted bit prior to transmission of a subsequent bit and
that the possible collision of a bit may be detected by the
transmitting terminal prior to transmitting the next bit.
In order to alleviate the long waiting times associated with
data dependent priority, communications controller 7 is
programmed to insert a variable priority byte at the
beginning of each data transmission. The purpose of the
variable priority byte is to assign priority to the data to
be transmitted. The variable priority byte is initially set
to the lowest possible priority. Each time the peripheral
device is denied control of the busl the variable priority
~yte i9 incremented and the peripheral device makes a further
attempt to gain control. At some point within an acceptable
number of attempts, the variable priority byte will have been
incremented to a sufficiently high priority to succes~fully
contend for access to the bus.
Based on the fact that in bus organized structure in which
logical "0" bits have priority over logical "1" bits, such as
that shown in Figure 1, and based on the fact that in
standard
- 16 -
~32028~
serial bit data transmission, data bytes are transmitted
starting with the least significant bit (LSB), communications
controller 7 is programmed to generate an incremented
priority level which when compared to the preceding priority
on a bit-by-bit basis, starting with the least significant
bit, has a logic "0" in the first bit position in which no
parity occurs. For example, as between a first variable
priority byte having as a priority level 10110001 and a
second having a priority level 10101001, the first lack of
parity occurs in the fourth least bit position. Accordingly,
the first variable priority byte takes priority as it has a
logical "0" in that bit position.
In order to achieve the maximum number of possible priority
levels the priority level of the variable priority byte is
incremented in accordance with the following table:
MSB LSB PRIORITY
llll llll Lowest po~sible
0111 1111 Lowest +1
1011 1111 Lowest +2
0011 1111 Lowest +3
1101 1111 Lowest +4
0010 0000 Highest -4
1100 Q000 Highest -3
0100 0000 Highest -2
1000 0000 Highe~t -1
0000 0000 Highest possible
- 17 -
1320281
The above table is based on an 8 bit byte system in which
logical "0" bits have priority over logical "1" bits. A
larger or smaller number of bits can be used to suit the
application. It is useful to note that each incremented
priority level is the mirror image of the binary subtraction
of 1 from the mirror image of the previous priority level.
Where the bus structure is configured such that logical "1"
bits take priority over logical "0" bits, the priority
designation of the bytes listed in the above table would be
reversed with the byte 1111 1111 representing the highest
possible priority and the byte 0000 0000 representing the
lowest possible priority. In ~uch a case, the incremented
priority level is the mirror image of the binary addition of
1 to the mirror image of the previous priority level.
lS
The incrementing of the variable priority byte is performed
by communication~ controller 7 under ~oftware control. Any
appropriate programming technique can be used to increment
the priority byte level in accordance with the above
~equence. The above sequence can be generated by placing the
priority byte of lowest po~sible priority in a working
regi~ter, decrementing the register by 1 and creating in a
second regi~ter a mirror image of the number in the working
regi~ter. The mirror image can be created by shifting the
deoremented number 8 bit position~ to the left or right in
wrap around
- 18 -
1320281
fashion. The subsequent priority level in the sequence is
generated by again decrementing the number in the working
register by 1 and creating its mirror image. It will be
evident to those skilled in the art that the above sequence
S can be generated using other techniques. For example, the
above sequence can be generated by performing repetitive
subtractions of n from the priority byte of lowest possible
priority and creating a mirror image of each remainder, where
n i8 equal to the number of times that transmission has been
interrupted.
In the case where a logical "1" takes priority,
communications controller 7 can be programmed to generate the
priority level ~equence in a manner similar to that described
lS abovo except that the mirror image of the previous priority
level ls incremented by 1 before creating the mirror image.
In operation, bus contention with the variable priority byte
i~ a# follows. The lowest pos~ible priority byte is initially
stored in the priority byte register in communication~
controller 7 in peripheral device 1. When a bus inactive
condition is sensed, communications controller 7 asserts a
bus active signal on the BA wire and proceeds to transmit on
the TXDATA wlre of bus 4 as described above. The first byte
transmitted is the priority byte. If a bit colli~ion is
-- 19 --
~32028~
detected, peripheral device 1 will stop transmitting and will
increment the priority level in the priority byte register by
1 to the next priority level. Peripheral device 1 will again
monitor the BA wire for a bus inactive condition and will
attempt to transmit the newly incremented priority byte. If
another bit collision is detected, the priority level is
again incremented and a further attempt to transmit is made.
These steps are repeated until the priority level of the
priority byte of peripheral device 1 is sufficiently high to
10 take priority over the priority byte of all other peripheral
devices contending for access to bus 4. Following successful
transmission, communications controller 7 reset~ the priority
byte to the lowest possible priority. It will be evident that
only one attempt to transmit a priority data byte can occur
15 per terminal for each successful transmission of data by any
peripheral device connected to bus 4. This is because no
attempt to retran~mit a higher priority data byte can be made
until a glven peripheral device has monitored a bus inactive
state on the BA wire of bus 4 for a period of 1 bit time.
The functions of the communications controller described
above are under appropriate software control. Figure 2 is a
flow-chart diagram that represents the basic functions to be
performed by communication3 controller 7. Figure 2 ~hould be
25 con~idered in con~unction with Figure 1. Initiation of an
- 20 -
1320281
attempt to send data on bus 4 places communications
controller 7 in the start condition 20. Communications
controller 7 sets the priority byte to its initial priority
level at step 21 and sets a software timer at step 22 to an
S initial value. The software timer is set to time-out at one
bit cell time. Communications controller 7 monitors BA IN
terminal 17 for the bus inactive logic state at step 23. If
the bus inactive state is not detected, communications
controller 7 resets the software timer to its initial value
and repeats the process of monitoring BA terminal 17. Once
the bus inactive logic state is detected at BA IN terminal
17, communications controller 7 examines the count value of
the software timer at step 24 to determine whether 1 bit cell
time has passed since the bus inactive logic state was first
detected. If 1 bet cell time has not passed, the software
timer iB incremented at step 25 and the logic state at BA IN
termlnal 17 is again eampled. If no bus active logic state is
detected at BA IN terminal 17 before the software timer times
out, communication~ controller 7 places a bus active logic
state on BA OUT terminal 11 at step 26. If on the other hand
a bu~ active logic state is detected before the software
timer times out, the timer is reset to its initial value and
monitoring of BA IN terminal 17 is recommenced. The 1 bit
cell waiting time provided by the software timer ensures that
noise on the BA wlre of bus 4 wlll not falsely indicate an
inactive bus when in fact lt is active and allows central
processor 3 to detect the break between transmissions from
different peripheral devices.
132028~
After the bus active logic state has been set at step 26,
communications controller 7 transmits the priority byte at
its initial priority level at step 27. Transmission is
achieved by clocking the priority byte out through DATA OUT
terminal 8 in serial fashion starting with the least
significant bit. While the priority byte is being clocked out
through DATA OUT terminal 8, communications controller 7
monitors the logic level of the TXDATA wire of bus 4 at DATA
IN terminal 14 at step 28. Communications controller 7
compares the logic level at DATA IN terminal 14 with the
logic level at DATA OUT terminal 8 on a bit by bit basis. A
difference in logic levels indicates that a bit collision has
been detected. Upon detecting a bit collision, communications
controller 7 increments the priority level of the priority
byte at step 29 in the manner described above and at step 30
plaCes a bus inactive logic level at BA OUT terminal 11, in
effect relinquishing control of bus 4 and returning to
monltor for a bus inactive condition. Parity in logic levels
indicates that no bit collision has been detected. This may
be because no other peripheral device i~ transmitting, or
because another peripheral device i~ transmitting the same
bit, or because another peripheral device is transmitting a
different bit of lower priority. If the transmission of each
bit of the priority byte does not produce a detectable bit
colllsion, communications controller 7 proceeds to transmit
data at step 31. Data is tran~mitted in the same manner as
the priority byte.
-- 22 --
132~281
Communications controller 7 continues to check for bit
coliisions at step 32 while transmitting data. This is
because it is possible that the priority level of two
peripheral devices contending for access to bus 4 may be
identical . In such a case, priority is resolved on a data
dependent basis. A bit collision in the data portion of
transmission causes communications controller 7 to increment
priority and relinquish control of bus 4 in the same manner
as if the bit collision has occurred in the priority byte
portion of transmission. After the end of data transmission
i~ detected at step 33, communications controller 7 places a
bus inactive logic state at BA OU~ terminal ll at step 34
freeing bus 4 for further transactions.
U~e of the variable priority byte ensures that a given
peripheral device will be able to gain control of bus 4 and
successfully transmit its data within n attempts, where n is
the number of peripheral devices connected to bus 4. The
maximum number of peripheral devices that may be connected to
bu~ 4 is limited by the number of priority levels afforded by
the priorlty byte. For example, where an eight bit priority
byte is used, there are 256 possible priority levels and
accordingly, a maximum of 256 peripheral devices may be
connected to bus 4.
132~28~
While the invention has been shown and described with
reference to a preferred embodiment thereof, it will be
understood by those skilled in the art that other embodiments
may be devised without departing from the scope of the
invention.
