Apparatus and method for ensuring that lock requests are serviced in a multiprocessor system
First Claim
1. A lockout avoidance circuit for a plurality of nodes generating lock requests for a shared resource, comprisinga queue including:
- a plurality of registers pipelined together, a first of said registers being the head of the queue and the last of said registers being the tail of the queue;
means for counting lock requests that have been refused from at least one of said nodes;
means for enabling said queue to store a lock request from said node at the tail of the queue after a predetermined number of lock requests from said node have been refused and storing all subsequent lock requests from any other of said nodes at the tail of the queue in the order in which they are registered; and
said means for enabling operating said queue to advance the stored lock requests toward the head of said queue each time the lock request at the head of the queue is serviced.
3 Assignments
0 Petitions
Accused Products
Abstract
A lockout avoidance circuit is provided for a plurality of nodes which generate lock requests for a shared resource such as a memory location. The circuit insures that lock requests are eventually satisfied. A lock queue includes a plurality of registers pipelined together. Lock requests only enter the lock queue if they are refused access to a shared resource a predetermined number of times. A first register is the head of the queue and the last register is the bottom of the queue. An enabling circuit allows the queue to store in the registers lock requests received from the different nodes in the order in which they are initially refused service. The enabling circuit operates the queue by pushing the stored lock requests toward the head of the queue each time the head entry in the queue is serviced. The lockout avoidance circuit is implemented at each level of the system wherein a lockout condition can occur.
71 Citations
22 Claims
-
1. A lockout avoidance circuit for a plurality of nodes generating lock requests for a shared resource, comprising
a queue including: -
a plurality of registers pipelined together, a first of said registers being the head of the queue and the last of said registers being the tail of the queue; means for counting lock requests that have been refused from at least one of said nodes; means for enabling said queue to store a lock request from said node at the tail of the queue after a predetermined number of lock requests from said node have been refused and storing all subsequent lock requests from any other of said nodes at the tail of the queue in the order in which they are registered; and said means for enabling operating said queue to advance the stored lock requests toward the head of said queue each time the lock request at the head of the queue is serviced. - View Dependent Claims (2, 3, 4)
-
-
5. A method for avoiding lockout of lock requests for a particular resource in a system, said lock requests generated from a plurality of nodes coupled to a central location, the method comprising the steps of:
-
counting at a central location the number of times a particular node is refused a lock request to a particular resource; storing all lock requests for any system resource subsequent to a predetermined number of lock requests from the particular node that have been refused; and servicing, serially in the order stored, all lock requests until all lock requests are satisfied.
-
-
6. A method for avoiding lockout of lock requests generated from a plurality of nodes coupled to a central location, the method comprising the steps of:
-
incrementing a counter associated with a particular one of the nodes when a lock request from said particular node is refused in the central location; generating an end of count signal from said counter when the lock request is refused a predetermined number of times; storing the lock request as a head entry in a queue once the end of count signal is generated; subsequently storing any further lock requests from different nodes as further entries in said queue once the queue contains a head entry; and operating said queue to the entries in the order in which they are placed in the queue. - View Dependent Claims (7, 8, 9, 10)
-
-
11. An apparatus for avoiding lockouts of lock requests in a multi-level hierarchical system, comprising:
-
a first lockout avoidance circuit in the highest hierarchical level of said system, said first lockout avoidance circuit guaranteeing that no lockout occurs for lock requests received at said highest hierarchical level, said first lockout avoidance circuit including; a) first means for providing a first level lock request refusal signal if a predetermined number of lock request refusals occur, and b) a first level lock queue for storing highest hierarchical level requester information in response to said first level lock request refusal signal; and a second lockout avoidance circuit in the next highest hierarchical level of the system, said second lockout avoidance circuit guaranteeing that no lockouts occur at the next highest level, said second lockout avoidance circuit including; a) second means for providing a second level lock request refusal signal if second level lock request refusals occur, and b) a second level lock queue for storing next highest hierarchical level requester information in response to said second level lock request refusal signal.
-
-
12. A method for avoiding lockouts of lock requests in a multi-level hierarchical system, comprising the steps of:
-
operating a first lockout avoidance circuit in the highest hierarchical level of said system, said first lockout avoidance circuit guaranteeing that no lockout occurs for lock requests received at said highest hierarchical level and including the steps of; a) providing a first level lock request refusal signal if a predetermined number of first level lock request refusals occurs, and b) storing highest hierarchical level requester information in a first level lock queue in response to said first level lock request refusal signal; and operating a second lockout avoidance circuit located in the next highest hierarchical level of the system, said second lockout avoidance circuit guaranteeing that no lockouts occur at the next highest hierarchical level and including the steps of; a) providing a second level lock request refusal signal if second level lock request refusals occur, and b) storing next highest hierarchical level requester information in a second level lock queue in response to said second level lock request refusal signal.
-
-
13. A circuit for servicing lock requests for memory locations generated from a plurality of nodes, comprising:
-
a plurality of lock registers, each of the lock registers including a storage device and a comparator having first and second inputs, said lock requests being provided to the first input of the comparator and to an input of the storage device, an output of the storage device being coupled to the second input of the comparator; a lock queue coupled to said lock registers, the lock queue receiving lock requests at its inputs, the lock queue including a plurality of queue registers; a control circuit coupled to the lock registers and lock queue for controlling the circuit operation; a plurality of counters each providing a count signal to the control circuit, the number of counters and queue registers equalling the number of nodes from which lock requests are generated; said control circuit including a first signal for operating the lock registers; a second signal for operating the lock queue; and a third signal for operating the counters. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A lockout avoidance circuit for a plurality of nodes generating lock requests for a shared resource, comprising:
-
a queue having a head and a tail; means for counting lock requests that have been refused from at least one of the nodes; means for enabling the queue to store a lock request from the node at the tail of the queue after a predetermined number of lock requests from the node have been refused, and storing all subsequent lock requests from any other of the nodes at the tail of the queue in the order in which they are requested; the means for enabling operating the queue to advance the stored lock requests toward the head of the queue each time the lock request at the head of the queue is serviced.
-
Specification