Patent US5349690A successfully refreshed from Google Patents.
US5349690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fair arbitration scheme for arbitrating between multiple nodes in a computer system seeking control of a common bus
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-02-11
•
Granted: 1994-09-20
•
Expires: 2013-02-11
Abstract
Abstract A method and apparatus for selecting a particular node from a plurality of nodes connected to a common bus to allow the node to use the bus. The nodes have a pre-determined priority. After initially enabling the nodes, the bus is monitored for a bus idle condition. It is then determined which of the nodes are enabled message nodes, which are enabled nodes that have a message to send on the bus. There is then arbitration between the enabled message nodes after the bus is in the bus idle condition for a first period of time, such that the enabled message node having the highest pre-determined priority among the enabled message nodes is disabled for arbitration purposes, and also at the same time selects a target and performs a transfer. This procedure is repeated until all the enabled message nodes have been disabled. Thereafter, all of the nodes on the bus are enabled when the bus is in the bus idle condition for a second period of time, which is longer than the first period of time.
Inventors
- 👤 Robert C. Frame
- 👤 Fernando A. Zayas
- 👤 Edward A. Gardner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:29
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/36; G06F13/368
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
240 words
A method for selecting a particular node from a plurality of nodes coupled to a bus, each node having a predetermined priority, to allow said particular node to use the bus, and for enabling the plurality of nodes after each of the nodes has had an opportunity to use the bus to allow a subsequent selection of a particular node, said method comprising the steps of: a. enabling for for arbitration each of said nodes having a message to send on the bus; wherein such enabling is performed by each node itself; b. monitoring the bus for a bus idle condition; c. determining which of said nodes are enabled message nodes, d. arbitrating between said enabled message nodes after the bus has been in a bus idle condition for a first period of time, to select the enabled message node having a highest pre-determined priority among said enabled message nodes to use the bus; e. disabling said selected enabled message node from arbitration; wherein such disabling is performed by each selected enabled message node itself; f. repeating steps b, c, d and e until all said enabled message nodes have been disabled from arbitration; and g. thereafter enabling all said nodes for arbitration when the bus has been in a bus idle condition for a second period of time which is longer than the first period of time, while the plurality of nodes and said bus are running and stable.
Claim 2
Independent Claim
240 words
A method for selecting a particular node from a plurality of nodes coupled to a bus, each node having a predetermined priority, to allow said particular node to use the bus, and for enabling the plurality of nodes after each of the nodes has had an opportunity to use the bus to allow a subsequent selection of a particular node, said method comprising the steps of: a. enabling for for arbitration each of said nodes having a message to send on the bus; wherein such enabling is performed by each node itself; b. monitoring the bus for a bus idle condition; c. determining which of said nodes are enabled message nodes, d. arbitrating between said enabled message nodes after the bus has been in a bus idle condition for a first period of time, to select the enabled message node having a highest pre-determined priority among said enabled message nodes to use the bus; e. disabling said selected enabled message node from arbitration; wherein such disabling is performed by each selected enabled message node itself; f. repeating steps b, c, d and e until all said enabled message nodes have been disabled from arbitration; and g. thereafter enabling all said nodes for arbitration when the bus has been in a bus idle condition for a second period of time which is longer than the first period of time, while the plurality of nodes and said bus are running and stable.
Claim 3
Dependent Claim
22 words
The method of claim 1, further comprising the step of monitoring time elapsed after the bus enters into the bus idle condition.
Claim 4
Dependent Claim
21 words
The method of claim 2, wherein step (a) includes the step of setting an internal enable flag in each said node.
Claim 5
Dependent Claim
23 words
The method of claim 3, wherein step (e) includes the step of clearing said internal enable flag of said selected enabled message node.
Claim 6
Dependent Claim
30 words
The method of claim 4, wherein step (c) includes determining which of said enabled nodes have asserted a busy signal which indicates said enabled node has a message to send.
Claim 7
Dependent Claim
31 words
The method of claim 1, wherein step (d) includes comparing a priority asserted by each said enabled message node, and selecting said enabled message node which has asserted a highest priority.
Claim 8
Dependent Claim
21 words
The method of claim 1, wherein step (a) includes the step of setting an internal enable flag in each said node.
Claim 9
Dependent Claim
23 words
The method of claim 7, wherein step (e) includes the step of clearing said internal enable flag of said selected enabled message node.
Claim 10
Dependent Claim
30 words
The method of claim 1, wherein step (c) includes determining which of said enabled nodes have asserted a busy signal which indicates said enabled node has a message to send.
Claim 11
Dependent Claim
46 words
The method of claim 1, wherein step (d) includes comparing a priority identification bit asserted by each said enabled message node, and selecting an enabled message node which has asserted a corresponding priority identification bit that has a highest priority among the asserted priority identification bits.
Claim 12
Dependent Claim
25 words
The method of claim 1, wherein said first period of time is approximately 800 nsec, and said second period of time is approximately 1600 nsec.
Claim 13
Dependent Claim
254 words
In a bus system, having a bus and a plurality of nodes coupled to the bus, each node having a predetermined priority, an apparatus for implementing decentralized arbitration comprising a plurality of arbitration devices, one provided for each node and coupled to the bus, each device comprising: means for self-enabling the node corresponding to the arbitration device for arbitration; means for monitoring the bus to detect a bus idle condition and for measuring an amount of time elapsed after the bus enters into the bus idle condition; means for determining whether the node corresponding to the arbitration device is an enabled message node an enabled message node being an enabled node that has a message to send on the bus; means for interacting with other arbitration devices when the node corresponding to the arbitration device is an enabled message node to arbitrate and select an enabled message node after the bus is in the bus idle condition for a first period of time, such that the enabled message node having a highest pre-determined priority among the enabled message nodes is selected to use the bus; and means for self-disabling the node corresponding to the arbitration device from arbitration once the node is selected; said means for enabling responsive to the bus being in an idle condition for a second period of time which is longer than the first period of time to enable the node corresponding to the arbitration device for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 14
Dependent Claim
254 words
In a bus system, having a bus and a plurality of nodes coupled to the bus, each node having a predetermined priority, an apparatus for implementing decentralized arbitration comprising a plurality of arbitration devices, one provided for each node and coupled to the bus, each device comprising: means for self-enabling the node corresponding to the arbitration device for arbitration; means for monitoring the bus to detect a bus idle condition and for measuring an amount of time elapsed after the bus enters into the bus idle condition; means for determining whether the node corresponding to the arbitration device is an enabled message node an enabled message node being an enabled node that has a message to send on the bus; means for interacting with other arbitration devices when the node corresponding to the arbitration device is an enabled message node to arbitrate and select an enabled message node after the bus is in the bus idle condition for a first period of time, such that the enabled message node having a highest pre-determined priority among the enabled message nodes is selected to use the bus; and means for self-disabling the node corresponding to the arbitration device from arbitration once the node is selected; said means for enabling responsive to the bus being in an idle condition for a second period of time which is longer than the first period of time to enable the node corresponding to the arbitration device for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 15
Dependent Claim
201 words
A node adapted to be coupled no a bus with at least one other node, each node having a pre-determined priority, the node comprising: means for self-enabling said node for arbitration when said node has a message to send on the bus; means for monitoring the bus to detect bus idle condition and for measuring an amount of time elapsed after the bus enters into the bus idle condition; means for interacting with at least one arbitration device when said node is an enabled message node to arbitrate and select between enabled message nodes coupled to the bus after the bus is in the bus idle condition for a first period of time, such that said enabled message node having a highest pre-determined priority among said enabled message nodes is selected to use the bus; and means for disabling said node from arbitration once selected, wherein such disabling is performed by the node itself; said means for enabling responsive to the bus being in the bus idle condition for a second period of time which is longer than the first period of time to enable said node for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 16
Dependent Claim
201 words
A node adapted to be coupled no a bus with at least one other node, each node having a pre-determined priority, the node comprising: means for self-enabling said node for arbitration when said node has a message to send on the bus; means for monitoring the bus to detect bus idle condition and for measuring an amount of time elapsed after the bus enters into the bus idle condition; means for interacting with at least one arbitration device when said node is an enabled message node to arbitrate and select between enabled message nodes coupled to the bus after the bus is in the bus idle condition for a first period of time, such that said enabled message node having a highest pre-determined priority among said enabled message nodes is selected to use the bus; and means for disabling said node from arbitration once selected, wherein such disabling is performed by the node itself; said means for enabling responsive to the bus being in the bus idle condition for a second period of time which is longer than the first period of time to enable said node for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 17
Independent Claim
283 words
A method for arbitrating among a plurality of nodes coupled to a common bus to select one of the plurality of nodes to use the bus for communication, the method comprising the steps of: (a) assigning a predetermined priority to each node of the plurality of nodes; (b) operating each node of the plurality of nodes to enable itself for arbitration; (c) operating each node of the plurality of nodes to monitor the bus for a bus idle condition; (d) after a bus idle condition has subsisted for a first predetermined period of time, operating each node of the plurality of nodes to assert a signal when the node is enabled and the node has a message to send on the bus, the signal containing an indication of the predetermined priority of the node; (e) thereafter operating each one of the enabled nodes that has a message to send to compare its predetermined priority with the predetermined priority contained in the signal asserted by each other enabled node that has a message to send to determine if its priority is the highest priority; (f) thereafter operating an enabled node with the highest priority that has a message to send to take control of the bus for communication and to disable itself from arbitration; (g) repeating steps (c)-(f) until all enabled nodes that have a message to send have been disabled from arbitration; and (h) operating each one of the disabled nodes to monitor the bus for a bus idle condition and to enable itself when a bus idle condition subsists on the bus for a second predetermined period of time, which second period of time is longer than the first period of time.
Claim 18
Independent Claim
283 words
A method for arbitrating among a plurality of nodes coupled to a common bus to select one of the plurality of nodes to use the bus for communication, the method comprising the steps of: (a) assigning a predetermined priority to each node of the plurality of nodes; (b) operating each node of the plurality of nodes to enable itself for arbitration; (c) operating each node of the plurality of nodes to monitor the bus for a bus idle condition; (d) after a bus idle condition has subsisted for a first predetermined period of time, operating each node of the plurality of nodes to assert a signal when the node is enabled and the node has a message to send on the bus, the signal containing an indication of the predetermined priority of the node; (e) thereafter operating each one of the enabled nodes that has a message to send to compare its predetermined priority with the predetermined priority contained in the signal asserted by each other enabled node that has a message to send to determine if its priority is the highest priority; (f) thereafter operating an enabled node with the highest priority that has a message to send to take control of the bus for communication and to disable itself from arbitration; (g) repeating steps (c)-(f) until all enabled nodes that have a message to send have been disabled from arbitration; and (h) operating each one of the disabled nodes to monitor the bus for a bus idle condition and to enable itself when a bus idle condition subsists on the bus for a second predetermined period of time, which second period of time is longer than the first period of time.
Claim 19
Independent Claim
186 words
A method for selecting a particular node from a plurality of nodes coupled to a common bus to allow said particular node to use said bus for communication, said method comprising the steps of: (a) assigning a predetermined priority to each node of the plurality nodes; (b) enabling each node of the plurality of nodes that has a message to send on the common bus; (c) monitoring the bus for a bus idle condition; (d) arbitrating between the enabled message nodes after the bus is in the bus idle condition for a first period of time, such that an enabled message node having a highest predetermined priority among the enabled message nodes is selected to use the bus; (e) disabling the selected enabled message node from arbitration; (f) operating the selected enabled message node to communicate over the bus; (g) repeating steps c, d, e and f until all the enabled message nodes have been disabled; and (h) enabling the disabled nodes when the bus is in the bus idle condition for a second period of time which is longer than the first period of time.
Claim 20
Independent Claim
186 words
A method for selecting a particular node from a plurality of nodes coupled to a common bus to allow said particular node to use said bus for communication, said method comprising the steps of: (a) assigning a predetermined priority to each node of the plurality nodes; (b) enabling each node of the plurality of nodes that has a message to send on the common bus; (c) monitoring the bus for a bus idle condition; (d) arbitrating between the enabled message nodes after the bus is in the bus idle condition for a first period of time, such that an enabled message node having a highest predetermined priority among the enabled message nodes is selected to use the bus; (e) disabling the selected enabled message node from arbitration; (f) operating the selected enabled message node to communicate over the bus; (g) repeating steps c, d, e and f until all the enabled message nodes have been disabled; and (h) enabling the disabled nodes when the bus is in the bus idle condition for a second period of time which is longer than the first period of time.
Claim 21
Dependent Claim
31 words
The method of claim 15 wherein steps (b), (c), (e) (f) and (h) are each performed by each respective node individually and wherein step (d) is performed collectively by the nodes.
Claim 22
Dependent Claim
30 words
The method of claim 15, wherein step (b) includes the step of setting an internal enable flag in each one of the plurality of nodes that a message to send.
Claim 23
Dependent Claim
23 words
The method of claim 17, wherein step (e) includes the step of clearing the internal enable flag of the selected enabled message node.
Claim 24
Dependent Claim
30 words
The method of claim 15, wherein step (b) includes determining which of the enabled nodes have asserted a busy signal which indicates the enabled node has a message to send.
Claim 25
Dependent Claim
48 words
The method of claim 15, wherein step (d) includes comparing a priority identification bit asserted by each one of the enabled message nodes, and selecting the enabled message node which has asserted a corresponding priority identification bit that is a highest priority among the asserted priority identification bits.
Claim 26
Dependent Claim
25 words
The method of claim 15, wherein the first period of time is approximately 800 nsec, and the second period of time is approximately 1600 nsec.
Claim 27
Dependent Claim
218 words
A node adapted to be coupled bus with at least one other node, each node having a predetermined priority, the node comprising: (a) an enabler to controllably enable and disable the node for arbitration; (b) a monitor to monitor the bus for a bus idle condition; and (c) an arbitrator, responsive to said monitor indicating a bus idle condition subsisting for a first period of time, to determine if i) the node is enabled for arbitration, and ii) the node has a highest predetermined priority among all nodes coupled to the bus and seeking to send a message on the bus; (d) the arbitration adapted to take control of the bus when the node has the highest predetermined priority, is enabled for arbitration and has a message to send on the bus; (e) the enabler operating to disable the node from arbitration in the event that the arbitrator take control of the bus; (f) the monitor indicating when a bus idle condition subsists on the bus for a second period of time, the second period of time being longer than the first period of time; and (g) the enabler being responsive to an indication of the second period of time to enable the node for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 28
Dependent Claim
218 words
A node adapted to be coupled bus with at least one other node, each node having a predetermined priority, the node comprising: (a) an enabler to controllably enable and disable the node for arbitration; (b) a monitor to monitor the bus for a bus idle condition; and (c) an arbitrator, responsive to said monitor indicating a bus idle condition subsisting for a first period of time, to determine if i) the node is enabled for arbitration, and ii) the node has a highest predetermined priority among all nodes coupled to the bus and seeking to send a message on the bus; (d) the arbitration adapted to take control of the bus when the node has the highest predetermined priority, is enabled for arbitration and has a message to send on the bus; (e) the enabler operating to disable the node from arbitration in the event that the arbitrator take control of the bus; (f) the monitor indicating when a bus idle condition subsists on the bus for a second period of time, the second period of time being longer than the first period of time; and (g) the enabler being responsive to an indication of the second period of time to enable the node for arbitration, while the plurality of nodes and said bus are running and stable.
Claim 29
Independent Claim
194 words
A method for communicating among a plurality of nodes coupled to a common bus, the method comprising the steps of: (a) determining each node of the plurality of nodes that has a message to send on the bus; (b) monitoring the bus for a bus idle condition; (c) upon a bus idle condition subsisting on the bus for a first period of time, selecting through arbitration based upon priority one determined node, each node of the plurality of nodes having a predetermined priority; (d) disabling from arbitration the node selected in step (c); (e) operating the selected node to communicate over the bus; (f) repeating steps (a)-(e) until each node of the plurality of nodes that has a message to send on the bus has been disabled from arbitration; (g) monitoring the bus for a bus idle-condition that has subsisted on the bus for a second period of time; and (h) enabling for arbitration each of the disabled nodes subsequent to the end of the second period of time, the second period of time being longer than the first period of time, while the plurality of nodes and said bus are running and stable.
Claim 30
Independent Claim
194 words
A method for communicating among a plurality of nodes coupled to a common bus, the method comprising the steps of: (a) determining each node of the plurality of nodes that has a message to send on the bus; (b) monitoring the bus for a bus idle condition; (c) upon a bus idle condition subsisting on the bus for a first period of time, selecting through arbitration based upon priority one determined node, each node of the plurality of nodes having a predetermined priority; (d) disabling from arbitration the node selected in step (c); (e) operating the selected node to communicate over the bus; (f) repeating steps (a)-(e) until each node of the plurality of nodes that has a message to send on the bus has been disabled from arbitration; (g) monitoring the bus for a bus idle-condition that has subsisted on the bus for a second period of time; and (h) enabling for arbitration each of the disabled nodes subsequent to the end of the second period of time, the second period of time being longer than the first period of time, while the plurality of nodes and said bus are running and stable.
Claim 31
Dependent Claim
229 words
A computer system comprising: (a) a bus; (b) a plurality of nodes coupled to the bus; (c) each one of said plurality of nodes comprising: (i) an enabler to controllably enable and disable the node for arbitration; said enabling said node if said node has a message to send on the bus; (ii) a monitor to monitor the bus for a bus idle condition; and (iii) an arbitrator, responsive to said monitor indicating a bus idle condition subsisting on the bus for a first period of time, to determine if 1) the node is enabled for arbitration, and 2) the node has a highest predetermined priority among all enabled nodes coupled to the bus and seeking to send a message on the bus; (iv) the arbitrator adapted to take control of the bus when the node has the highest predetermined priority, is enabled for arbitration and has a message to send on the bus; (v) the enabler operating to disable the node from arbitration in the event that the node takes control of the bus; (vi) the monitor indicating when a bus idle condition has subsisted on the bus for a second period of time, the second period of time being longer than the first period of time; and (vii) the enabler being responsive to an indication of the second period of time to enable the node for arbitration.
Claim 32
Dependent Claim
229 words
A computer system comprising: (a) a bus; (b) a plurality of nodes coupled to the bus; (c) each one of said plurality of nodes comprising: (i) an enabler to controllably enable and disable the node for arbitration; said enabling said node if said node has a message to send on the bus; (ii) a monitor to monitor the bus for a bus idle condition; and (iii) an arbitrator, responsive to said monitor indicating a bus idle condition subsisting on the bus for a first period of time, to determine if 1) the node is enabled for arbitration, and 2) the node has a highest predetermined priority among all enabled nodes coupled to the bus and seeking to send a message on the bus; (iv) the arbitrator adapted to take control of the bus when the node has the highest predetermined priority, is enabled for arbitration and has a message to send on the bus; (v) the enabler operating to disable the node from arbitration in the event that the node takes control of the bus; (vi) the monitor indicating when a bus idle condition has subsisted on the bus for a second period of time, the second period of time being longer than the first period of time; and (vii) the enabler being responsive to an indication of the second period of time to enable the node for arbitration.
Claim 33
Independent Claim
218 words
A method of operating a node adapted to be coupled to a bus, at least one other node being coupled to the bus, the method comprising the steps of: (a) assigning a priority to the node, the priority being relative to priorities assigned to all other nodes adapted to be coupled to the bus; (b) operating the node to monitor a bus idle condition on the bus; and (c) operating the node to take control of the bus after a bus idle condition has subsisted on the bus for a first time period when: (i) the node has a message to send the node is enabled for arbitration; and (ii) the priority of the node is the highest priority among all other nodes that have a message to send; (d) repeating steps (b) and (c) until the node takes control of the bus; (e) operating the node to be disabled from arbitration in the event that the node takes control of the bus; (f) operating the disabled node to monitor the bus for a bus idle condition; and (g) enabling the node for arbitration when the disabled node monitors a bus idle condition that has subsisted on the bus for a second period of time, which second period of time is longer than the first period of time.
Claim 34
Independent Claim
218 words
A method of operating a node adapted to be coupled to a bus, at least one other node being coupled to the bus, the method comprising the steps of: (a) assigning a priority to the node, the priority being relative to priorities assigned to all other nodes adapted to be coupled to the bus; (b) operating the node to monitor a bus idle condition on the bus; and (c) operating the node to take control of the bus after a bus idle condition has subsisted on the bus for a first time period when: (i) the node has a message to send the node is enabled for arbitration; and (ii) the priority of the node is the highest priority among all other nodes that have a message to send; (d) repeating steps (b) and (c) until the node takes control of the bus; (e) operating the node to be disabled from arbitration in the event that the node takes control of the bus; (f) operating the disabled node to monitor the bus for a bus idle condition; and (g) enabling the node for arbitration when the disabled node monitors a bus idle condition that has subsisted on the bus for a second period of time, which second period of time is longer than the first period of time.
References Cited (Backward Citations)
US4271465A
Cited
US4257095A
Cited
US4229791A
Cited
US4334288A
Cited
US4384323A
Cited
US4320467A
Cited
FR2482745A1
Cited
JPS5714953A
Cited
US4408300A
Cited
US4456956A
Cited
US4463445A
Cited
US4454581A
Cited
US4621342A
Cited
US4785394A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-09-19 | 1998-03-21 | 1998-09-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-19 | 2002-03-21 | 2002-09-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-19 | 2006-03-21 | 2006-09-20 | $7700.00 | Window Closed / Lapsed |