Patent US5263161A successfully refreshed from Google Patents.
US5263161A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-busy waiting resource control
Assignee: Massachusetts Institute of Technology
•
Filing: 1992-06-11
•
Granted: 1993-11-16
•
Expires: 2012-06-11
Abstract
Abstract A data structure has a value field for storing values and a lock field for indicating a lock state of the resource associated with the data structure. This data structure is used to implement a locking protocol amongst multiple processes competing for shared resources. If the lock field is a locked state, the process that locked the lock field has exclusive access to the resource. If, however, the lock field is in an unlocked state, any process may gain access to the resource. The lock field also has deferred states corresponding to the locked and unlocked states wherein multiple requests to lock or unlock the resource may be stored until serviced. The locking protocol is useful in a data processing system having multiple processing elements and utilizes a locking means that includes a local memory controller.
Inventors
- 👤 Paul S. Barth
- 👤 Richard M. Soley
- 👤 Kenneth M. Steele
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 19:49
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
152 words
A data processing system, comprising: at least one processor element for generating access requests for a data processing memory of at least two access request types; a memory storing a data structure for implementing locking protocol for synchronization of access requests to memory comprising: a. a value field for holding values which can be accessed by an access request; and b. a lock field addressed with the value field that indicates whether the value field is locked; and a controller for controlling service of access requests to the memory and setting of the lock field in response to an access request of a first access request type, the controller, when the value field is locked, deferring access to the value field by an access request of the first access request type that locked the value field but unlocking the value field and servicing an access request of a second access request type.
Claim 2
Dependent Claim
152 words
A data processing system, comprising: at least one processor element for generating access requests for a data processing memory of at least two access request types; a memory storing a data structure for implementing locking protocol for synchronization of access requests to memory comprising: a. a value field for holding values which can be accessed by an access request; and b. a lock field addressed with the value field that indicates whether the value field is locked; and a controller for controlling service of access requests to the memory and setting of the lock field in response to an access request of a first access request type, the controller, when the value field is locked, deferring access to the value field by an access request of the first access request type that locked the value field but unlocking the value field and servicing an access request of a second access request type.
Claim 3
Dependent Claim
21 words
The data processing system of claim 1 wherein the controller causes the value field to hold data in an unlocked state.
Claim 4
Dependent Claim
41 words
The data processing system of claim 1 wherein the controller causes the value field to hold a pointer that points to a list of access requests for a specific access request type when the value field is in a deferred state.
Claim 5
Dependent Claim
69 words
The data processing system of claim 1 wherein the controller places the lock field in a locked and deferred state that indicates to the controller than an locking type of access request currently has exclusive access to the value field and multiple request for exclusive access to the value field by access requests of the same locking type are pending which are stored on a deferred list of requests.
Claim 6
Dependent Claim
69 words
The data processing system of claim 1 wherein the controller places the lock field in an unlocked and deferred state that indicates to the controller than an unlocking type of access request currently has exclusive access to the value field and multiple request for exclusive access to the value field by access requests of the same locking type are pending which are stored on a deferred list of requests.
Claim 7
Dependent Claim
33 words
The data processing system of claim 4 wherein when the lock field is in the locked and deferred state, a pointer points to a deferred list of access requests of the locking type.
Claim 8
Dependent Claim
33 words
The data processing system of claim 5 wherein when the lock field is in the unlocked and deferred state, a pointer points to a deferred list of access requests of a locking type.
Claim 9
Dependent Claim
181 words
A data processing system, comprising: at least one processor element for generating memory access requests of at least two access request types: a memory storing a data structure for implementing locking protocol for synchronization of access by access requests to the memory comprising at a single memory address: a) a data field for holding values which can be accessed by an access request; b. a lock field that indicates whether the data field is locked; and c) a pointer field to point to lists of access requests for a specific access request type; and a controller for controlling service of access requests to the memory and setting of the lock field in response to an access request of a first access request type, the controller, when the data field is locked, deferring access to the data field by an access request of the first access request type that locked the data field but unlocking the value field and servicing an access request of a second access request type, the controller identifying a list of deferred access requests in the pointer field.
Claim 10
Dependent Claim
181 words
A data processing system, comprising: at least one processor element for generating memory access requests of at least two access request types: a memory storing a data structure for implementing locking protocol for synchronization of access by access requests to the memory comprising at a single memory address: a) a data field for holding values which can be accessed by an access request; b. a lock field that indicates whether the data field is locked; and c) a pointer field to point to lists of access requests for a specific access request type; and a controller for controlling service of access requests to the memory and setting of the lock field in response to an access request of a first access request type, the controller, when the data field is locked, deferring access to the data field by an access request of the first access request type that locked the data field but unlocking the value field and servicing an access request of a second access request type, the controller identifying a list of deferred access requests in the pointer field.
Claim 11
Dependent Claim
69 words
The data processing system of claim 8 wherein the controller places the lock field in a locked and deferred state that indicates to the controller that a locking type of access request currently has exclusive access to the data field and multiple requests for exclusive access to the data field by other access requests of the locking type are pending which are stored on a deferred list of requests.
Claim 12
Dependent Claim
70 words
The data processing system of claim 8 wherein the controller places the lock field in an unlocked and deferred state that indicates to the controller that an unlocking type of access request currently has exclusive access to the data field and that multiple requests for exclusive access to the data field by access requests of the same unlocking type are pending which are stored on a deferred list of requests.
Claim 13
Dependent Claim
36 words
The data processing system of claim 8 wherein the controller places the lock field in a locked and deferred state in which the pointer points to a deferred list of access requests of the locking type.
Claim 14
Dependent Claim
36 words
The data processing system of claim 8 wherein the controller places the lock field in an unlocked and deferred state in which the pointer points to a deferred list of access requests of the locking type.
Claim 15
Independent Claim
212 words
A method of synchronizing access by a plurality of access requests generated in a data processing system to a data processing resource wherein the resource contains a lock field for indicating the current lock state of the resource, the method performed by a controller for controlling service of requested accesses and setting of lock states in the lock field comprising the steps of: a. the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by a first type of access request if the lock field is in an unlocked state; b. the controller causing an access request to be serviced and setting the lock field of the resource is requested by a second type of access request if the lock field is in a locked state; and p1 c. the controller deferring service of an access request and setting the lock field of the resource to a locked and deferred state when the resource is requested by the first type of access request if the lock field is in a locked state, and the controller then also adding the resource access request on to a deferred list of pending resource access requests of the first type.
Claim 16
Independent Claim
212 words
A method of synchronizing access by a plurality of access requests generated in a data processing system to a data processing resource wherein the resource contains a lock field for indicating the current lock state of the resource, the method performed by a controller for controlling service of requested accesses and setting of lock states in the lock field comprising the steps of: a. the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by a first type of access request if the lock field is in an unlocked state; b. the controller causing an access request to be serviced and setting the lock field of the resource is requested by a second type of access request if the lock field is in a locked state; and p1 c. the controller deferring service of an access request and setting the lock field of the resource to a locked and deferred state when the resource is requested by the first type of access request if the lock field is in a locked state, and the controller then also adding the resource access request on to a deferred list of pending resource access requests of the first type.
Claim 17
Dependent Claim
80 words
A method as recited in claim 13 further comprising the step of: the controller deferring service of an access request and setting the lock field of the resource to an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked state, and the controller then also adding the resource access request on to a deferred list of pending resource access requests of the second type.
Claim 18
Dependent Claim
82 words
A method as recited in claim 13 further comprising the step of: the controller deferring service of an access request and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the first type of resource access request if the lock field is in a locked and deferred state, and the controller then also adding the resource access request on to the deferred list of pending resource access requests of the first type.
Claim 19
Dependent Claim
81 words
A method as recited in claim 14 further comprising the step of: the controller deferring service of an access request and keeping the lock field of the resource in an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked and deferred state, and the controller then also adding the resource access request on to the deferred list of pending resource requests of the second type.
Claim 20
Dependent Claim
101 words
A method as recited in claim 13 further comprising the step of: the controller causing an access request to be serviced and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the second type of resource access request if the lock field is in a locked and deferred state and other resource access request of the first type have been received yet are still outstanding and, the controller then also popping and servicing a pending resource access request off the deferred list of pending resource access requests of the first type.
Claim 21
Dependent Claim
103 words
A method as recited in claim 14 further comprising the step of: the controller causing an access request to be serviced and keeping the lock field of the resource to an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked and deferred state and other resource access requests of the first type have been received yet are still outstanding and, the controller than also popping and servicing an pending resource access request off the deferred list of pending resource access requests from processes of the first type.
Claim 22
Dependent Claim
96 words
A method as recited in claim 13 further comprising the step of: the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by the second type of resource access request if the lock field is in a locked and deferred state and only one resource access request of the first type is outstanding and, the controller then also popping and servicing the last pending resource access request off the deferred list of pending resource access requests of the first type.
Claim 23
Dependent Claim
96 words
A method as recited in claim 14 further comprising the step of: the controller causing an access request to be serviced and setting the lock field of the resource to an unlocked state when the resource is requested by the first type of resource access request if the lock field is in an unlocked and deferred state and only one resource access request of the second type is outstanding and, the synchronizer then also popping and servicing the last pending resource access request off the deferred list of pending resource access requests of the second type.
Claim 24
Dependent Claim
14 words
A method as recited in claim 13 wherein the resource is a memory location.
Claim 25
Dependent Claim
15 words
A method as recited in claim 21 wherein the resource is an I-structure memory location.
Claim 26
Independent Claim
788 words
A method of synchronizing access by a plurality of resource access requests generated in a data processing system to a data processing resource wherein the resource contains a lock field for indicating the current lock state of the resource, the method performed by a controller for controlling service of requested accesses and setting of lock states in the lock field comprising the steps of: the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by a first type of resource access request if the lock field is in an unlocked state; b. the controller causing service of an access request and setting the lock field of the resource to an unlocked state when the resource is requested by a second type of resource access request if the lock field is in a locked state; p1 c. the controller deferring service of an access request and setting the lock field of the resource to a locked and deferred state when the resource is requested by the first type of resource access request if the lock field is in a locked state, and the controller than also adding the resource access request on to a deferred list of pending resource access requests of the first type; d. the controller deferring service of an access request and setting the lock field of the resource to an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked state, and the controller then also adding the resource access request to a deferred list of pending resource access requests of the second type; e. the controller deferring service of an access request and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the first type of resource access request if the lock field is in a locked and deferred state, and the controller then also adding the resource access request to the deferred list of pending resource access requests of the first type; f. the controller causing an access request to be serviced and keeping the lock field of the resource in an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked and deferred state, and the controller then also adding the resource access request to the deferred list of pending resource access requests of the second type; g. the controller causing an access request to be serviced and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an locked and deferred state and other requests for the resource from resource access request of the first type have been received yet are still outstanding and, the controller then also popping and servicing a pending resource access request off the deferred list of pending resource access requests of the first type; h. the controller causing an access request to be serviced and keeping the lock field of the resource in an unlocked and deferred state when the resource is requested by the first type of resource access request if the lock field is in an unlocked and deferred state and other requests for the resource from resource access requests of the second type have been received yet are still outstanding and, the controller then also popping and servicing a pending resource access request off the deferred list of pending resource access requests of the second type; i. the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by the second type of resource access request if the lock field is in a locked and deferred state and only one resource access request of the first type is outstanding and, the controller then also popping the last pending resource access request off the deferred list of pending resource access requests of the first type; and j. the controller causing an access request to be serviced and setting the lock field of the resource to a unlocked state when the resource is requested by the first type of resource access request if the lock field is in an unlocked and deferred state and only one resource access request of the second type is outstanding and, the controller then also popping and servicing the last pending resource access request off the deferred list of pending resource access requests of the second type.
Claim 27
Independent Claim
788 words
A method of synchronizing access by a plurality of resource access requests generated in a data processing system to a data processing resource wherein the resource contains a lock field for indicating the current lock state of the resource, the method performed by a controller for controlling service of requested accesses and setting of lock states in the lock field comprising the steps of: the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by a first type of resource access request if the lock field is in an unlocked state; b. the controller causing service of an access request and setting the lock field of the resource to an unlocked state when the resource is requested by a second type of resource access request if the lock field is in a locked state; p1 c. the controller deferring service of an access request and setting the lock field of the resource to a locked and deferred state when the resource is requested by the first type of resource access request if the lock field is in a locked state, and the controller than also adding the resource access request on to a deferred list of pending resource access requests of the first type; d. the controller deferring service of an access request and setting the lock field of the resource to an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked state, and the controller then also adding the resource access request to a deferred list of pending resource access requests of the second type; e. the controller deferring service of an access request and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the first type of resource access request if the lock field is in a locked and deferred state, and the controller then also adding the resource access request to the deferred list of pending resource access requests of the first type; f. the controller causing an access request to be serviced and keeping the lock field of the resource in an unlocked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an unlocked and deferred state, and the controller then also adding the resource access request to the deferred list of pending resource access requests of the second type; g. the controller causing an access request to be serviced and keeping the lock field of the resource in a locked and deferred state when the resource is requested by the second type of resource access request if the lock field is in an locked and deferred state and other requests for the resource from resource access request of the first type have been received yet are still outstanding and, the controller then also popping and servicing a pending resource access request off the deferred list of pending resource access requests of the first type; h. the controller causing an access request to be serviced and keeping the lock field of the resource in an unlocked and deferred state when the resource is requested by the first type of resource access request if the lock field is in an unlocked and deferred state and other requests for the resource from resource access requests of the second type have been received yet are still outstanding and, the controller then also popping and servicing a pending resource access request off the deferred list of pending resource access requests of the second type; i. the controller causing an access request to be serviced and setting the lock field of the resource to a locked state when the resource is requested by the second type of resource access request if the lock field is in a locked and deferred state and only one resource access request of the first type is outstanding and, the controller then also popping the last pending resource access request off the deferred list of pending resource access requests of the first type; and j. the controller causing an access request to be serviced and setting the lock field of the resource to a unlocked state when the resource is requested by the first type of resource access request if the lock field is in an unlocked and deferred state and only one resource access request of the second type is outstanding and, the controller then also popping and servicing the last pending resource access request off the deferred list of pending resource access requests of the second type.
Claim 28
Dependent Claim
20 words
A data processing system as recited in claim 1 wherein the data processing system is a data flow processing system.
Claim 29
Dependent Claim
22 words
A data processing system as recited in claim 1 wherein the data processing system is a tagged token data flow processing system.
Claim 30
Dependent Claim
35 words
A method as recited in claim 13 wherein the resource is a memory location, the first type of access request is a read request and the second type of access request is a write request.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-15 | 1997-05-17 | 1997-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-15 | 2001-05-17 | 2001-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-15 | 2005-05-17 | 2005-11-16 | $7700.00 | Window Closed / Lapsed |