US5596749A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Arbitration request sequencer
Assignee: Texas Instruments Inc
•
Filing: 1992-09-21
•
Granted: 1997-01-21
•
Expires: 2012-09-21
Abstract
Abstract A method of improving efficiency in computer systems through a novel arbitration scheme is disclosed. The arbitration scheme includes a bus arbiter circuit that transparently operates in both central arbitration and distributed arbitration computer systems. The bus arbiter circuit includes an arbitration request sequencer, an arbitration competition protocol sequencer, a multiplexer, a latch, two comparators, and a series of control status registers that together provide increased system efficiency by effectively self-preempting competition priorities on its own board, thus allowing tasks with the highest priorities to compete for mastership of the bus and eliminating priority inversions.
Inventors
- 👤 Jay T. Cantrell
- 👤 Edward R. Schurig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 21:45
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/36
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
120 words
A method of preventing priority inversions in a distributed mode arbitration system through self-preemption of a request competing for mastership of a bus on its own computer card, comprising the steps of: determining whether a new task on a computer card having a priority value is greater in importance than the priority value of the task on the same computer card presently competing for mastership of the bus, wherein the presence of a new task is indicated by the sending of a message having a priority value to a send message register on the computer card; and replacing the task presently competing for mastership of the bus with the new task if the new task possesses a greater priority value.
Claim 2
Independent Claim
120 words
A method of preventing priority inversions in a distributed mode arbitration system through self-preemption of a request competing for mastership of a bus on its own computer card, comprising the steps of: determining whether a new task on a computer card having a priority value is greater in importance than the priority value of the task on the same computer card presently competing for mastership of the bus, wherein the presence of a new task is indicated by the sending of a message having a priority value to a send message register on the computer card; and replacing the task presently competing for mastership of the bus with the new task if the new task possesses a greater priority value.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein the presence of a new task is indicated by the assertion of a bus request on the computer card.
Claim 4
Dependent Claim
30 words
The method of claim 1 wherein the presence of a new task is indicated by the updating of the priority of the task presently competing for mastership of the bus.
Claim 5
Dependent Claim
67 words
The method of claim 1 wherein the step of determining whether a new task has greater priority comprises the steps of: asserting a bus request having a priority value to a request sequencer circuit; and comparing the priority value of the bus request with a previous priority value of a previous bus request wherein the previous priority bus request was competing for mastership of a system bus.
Claim 6
Dependent Claim
53 words
The method of claim 4 wherein asserting a bus request having a priority value to a request sequencer circuit, comprises the steps of: requesting the system bus for a task; assigning a priority value to the task; and checking whether other tasks with assigned priorities are competing for mastership of the system bus.
Claim 7
Independent Claim
133 words
A method of self-preemption on a single computer card operating in a backplane environment in a distributed mode computer system, comprising the steps of: asserting a preemption request signal from a request sequencer circuit to an arbitration competition circuit that is competing for mastership of a system bus with a priority value associated with a task from the computer card that is less than the priority value of a new task on the same computer card; replacing the priority value of the lower priority task presently competing for mastership of the system bus with the higher task priority value wherein the single computer card has preempted itself; asserting a pre-emption acknowledge signal from the arbitration competition circuit to the request sequencer circuit; and releasing the preemption request signal to the arbitration competition circuit.
Claim 8
Independent Claim
133 words
A method of self-preemption on a single computer card operating in a backplane environment in a distributed mode computer system, comprising the steps of: asserting a preemption request signal from a request sequencer circuit to an arbitration competition circuit that is competing for mastership of a system bus with a priority value associated with a task from the computer card that is less than the priority value of a new task on the same computer card; replacing the priority value of the lower priority task presently competing for mastership of the system bus with the higher task priority value wherein the single computer card has preempted itself; asserting a pre-emption acknowledge signal from the arbitration competition circuit to the request sequencer circuit; and releasing the preemption request signal to the arbitration competition circuit.
Claim 9
Dependent Claim
61 words
The method of claim 6 wherein the replacement of the task with a lower priority value with the new task priority value comprises the steps of: removing the lower priority task value from competing for mastership of the system bus; and latching the new, higher task priority value into the arbitration competition circuit which competes for mastership of the system bus.
Claim 10
Dependent Claim
18 words
The method of claim 7 wherein the new task having a new task priority value is a message.
Claim 11
Independent Claim
208 words
A method of updating priority requests on a single computer card operating within a backplane environment in a distributed mode arbitration computer system, comprising the steps of: asserting an update priority request signal having a priority value to a request sequencer circuit; evaluating an arbitration competition circuit status to determine whether a task is presently competing for mastership of a system bus; latching a task priority value into the arbitration competition circuit if no task is presently competing for mastership of the system bus; checking whether a bus acquisition request signal has been asserted from the request sequencer circuit to the arbitration competition circuit if a task is presently competing for mastership of the system bus; determining whether the priority value of the bus acquisition request is greater than the updated priority value if a task is presently competing for mastership of the system bus; and asserting a preemption request signal from the request sequencer circuit to the arbitration competition circuit if the updated priority value is greater than the priority value associated with the bus acquisition request such that a single computer card self-preempts when a task having an updated priority value becomes greater in importance than the task presently competing for mastership of the system bus.
Claim 12
Independent Claim
208 words
A method of updating priority requests on a single computer card operating within a backplane environment in a distributed mode arbitration computer system, comprising the steps of: asserting an update priority request signal having a priority value to a request sequencer circuit; evaluating an arbitration competition circuit status to determine whether a task is presently competing for mastership of a system bus; latching a task priority value into the arbitration competition circuit if no task is presently competing for mastership of the system bus; checking whether a bus acquisition request signal has been asserted from the request sequencer circuit to the arbitration competition circuit if a task is presently competing for mastership of the system bus; determining whether the priority value of the bus acquisition request is greater than the updated priority value if a task is presently competing for mastership of the system bus; and asserting a preemption request signal from the request sequencer circuit to the arbitration competition circuit if the updated priority value is greater than the priority value associated with the bus acquisition request such that a single computer card self-preempts when a task having an updated priority value becomes greater in importance than the task presently competing for mastership of the system bus.
Claim 13
Independent Claim
81 words
A method of self-preempting a task with a priority value competing for mastership of a bus with a message request having a priority value greater than the task on a single computer card, comprising the steps of: asserting a send message request signal to an arbitration request sequencer; sending a send arbitrated message request signal from the arbitration request sequencer to an arbitration competition protocol sequencer; and preempting a task that initially had bus priority through the arbitration competition protocol sequencer.
Claim 14
Independent Claim
81 words
A method of self-preempting a task with a priority value competing for mastership of a bus with a message request having a priority value greater than the task on a single computer card, comprising the steps of: asserting a send message request signal to an arbitration request sequencer; sending a send arbitrated message request signal from the arbitration request sequencer to an arbitration competition protocol sequencer; and preempting a task that initially had bus priority through the arbitration competition protocol sequencer.
Claim 15
Dependent Claim
191 words
An arbitration protocol sequencer that transparently operates in either distributed mode or central mode arbitration schemes in a backplane environment computer system and provides self-preemption on a single computer card, comprising: an arbitration request sequencer circuit; an arbitration competition protocol sequencer circuit connected to the arbitration request sequencer; and a multiplexer connected to the arbitration request sequencer; a latch connected to the multiplexer, the arbitration request sequencer, and the arbitration competition protocol sequencer; and two comparators connected to the multiplexer, the latch, and the arbitration request sequencer; wherein the arbitration request sequencer circuit compares via the two comparators and the multiplexer a priority value of a new bus request to a priority value of a bus request presently competing for mastership of a system bus, and when the new bus request priority value is greater than the priority value of the bus request competing for mastership of the system bus the latch latches the new bus request priority value to the arbitration competition protocol sequencer circuit such that the computer card preempts itself and competes for mastership of the system bus with the new priority value of the new bus request.
Claim 16
Dependent Claim
191 words
An arbitration protocol sequencer that transparently operates in either distributed mode or central mode arbitration schemes in a backplane environment computer system and provides self-preemption on a single computer card, comprising: an arbitration request sequencer circuit; an arbitration competition protocol sequencer circuit connected to the arbitration request sequencer; and a multiplexer connected to the arbitration request sequencer; a latch connected to the multiplexer, the arbitration request sequencer, and the arbitration competition protocol sequencer; and two comparators connected to the multiplexer, the latch, and the arbitration request sequencer; wherein the arbitration request sequencer circuit compares via the two comparators and the multiplexer a priority value of a new bus request to a priority value of a bus request presently competing for mastership of a system bus, and when the new bus request priority value is greater than the priority value of the bus request competing for mastership of the system bus the latch latches the new bus request priority value to the arbitration competition protocol sequencer circuit such that the computer card preempts itself and competes for mastership of the system bus with the new priority value of the new bus request.
Claim 17
Dependent Claim
25 words
The arbitration protocol sequencer of claim 11 wherein the arbitration request sequencer and arbitration competition protocol sequencer comprise state machines implemented with asynchronous sequential circuits.
Claim 18
Dependent Claim
25 words
The arbitration protocol sequencer of claim 11 wherein the arbitration request sequencer and arbitration competition protocol sequencer comprise state machines implemented with synchronous sequential circuits.
Claim 19
Dependent Claim
111 words
The method of claim 1 wherein the step of replacing the task presently competing for mastership of the bus with the new task having greater priority comprises: asserting a preemption request to an arbitration competition circuit when the priority value of the bus request is greater than the priority value of the previous bus request wherein the assertion of the preemption request causes the priority value of the previous bus request to replace the priority value of the previous bus request and compete for mastership of the system bus via the arbitration competition circuit, thus allowing the bus request with the highest priority to compete for mastership of the system bus.
References Cited (Backward Citations)
USRE33705E
Cited
US4851990A
Cited
US5193193A
Cited
US5293493A
Cited
US5119480A
Cited
US5371849A
Cited
US5195185A
Cited
US5182800A
Cited
US5247684A
Cited
US5307487A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-21 | 2000-07-22 | 2001-01-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-21 | 2004-07-22 | 2005-01-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-21 | 2008-07-22 | 2009-01-21 | $7700.00 | Window Closed / Lapsed |