US 5,706,446 AGranted

Arbitration system for bus requestors with deadlock prevention

AssigneeUnisys Corporation

InventorsDavid Mark Kalish, Russell Lee Marrash, Gary Carl Whitlock, Kha Nguyen

Life of this patent

Estimating the term…

Loading patent…

Abstract

An arbitration logic system in a system control module regulates access to a common system bus as provided by a state machine which toggles access priority between two or more resource modules while preventing deadlock contention between two requesting modules while insuring that no module will be starved or denied access even though all the resource modules are contending for bus access. Any continuous deprivation or starvation of a module for bus access is prevented, in addition to any deadlock situations which are also prevented. This occurs by allowing retrying modules to request the bus at a temporarily higher priority and limiting the number of retries that any given requesting module is permitted to have.

In a network wherein a first, second, and third digital resource module share a common system bus whose access is regulated by an arbitration logic means, an arbitration logic bus access system comprising:

(a) said first resource module constituting a Central Processing Module, CPM, connected to a common system bus and including:
(a1) means to request bus access from said arbitration logic means;
(a2) means to receive a bus grant signal from said arbitration logic means;
(b) said second resource module constituting an Input/Output Module, IOM, connected to said common system bus and including:
(b1) means to request bus access from said arbitration logic means;
(b2) means to receive a bus grant signal from said arbitration logic means;
(c) said third resource module constituting a Bus Exchange Module (BEM) connected to said common system bus and having bus access priority over said CPM and IOM except during periods when temporary priority is granted to said IOM and CPM in periods when said BEM is inactive and not requesting bus access;
(d) said arbitration logic means including:
(d1) an arbiter state machine for sequencing bus access priority signals when said BEM is not requesting bus access, to said IOM on a first series of four consecutive incremental states and sequencing bus access priority to said CPM on a second series of four consecutive incremental states including:
(d1a) retry counter state machine means including:
(i) means to enable multiple retries, during said first series of four consecutive incremental states, of bus access requests for said IOM when said common bus is busy including:
(ia) means to transfer bus access to said CPM after said IQM has gained bus access and completed a data transfer cycle;
(ii) means to enable multiple retries, during said second series of four consecutive incremental states, of bus access requests for said CPM when said common bus is busy including:
(iia) means to transfer bus access to said IOM after said CPM has gained bus access and completed a data transfer cycle;
(d1b) bus interface logic means for receiving bus access requests from said first, second and third resource modules including:
(i) means to grant bus access according to said sequencing bus access priority signals;
(ii) means for disabling any selected one of said first, second or third resource module from acquiring bus access said means including:
(iia) selective programming commands which cause said arbiter state machine to deny bus access to a selected BEM, IOM, or CPM.

15 more elements

Abstract

Claims2