US5414839A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hybrid lock escalation and de-escalation protocols
Assignee: Hewlett Packard Development Co LP
•
Filing: 1992-06-19
•
Granted: 1995-05-09
•
Expires: 2012-06-19
Abstract
Abstract Requests for memory locks upon nodes in a multi-level resource hierarchy of a computer system are granted and denied by a hybrid escalation/de-escalation protocol that dynamically modifies the resource hierarchy so that lock escalation may restrict the extent of the hierarchy. Each of the leaf-level nodes, for example, is identified by a flag indicating whether or not it is possible to further refine a lock on the node by de-escalation. During escalation from a lower level of the hierarchy to a higher-level node, the flag for the higher-level node is set to restrict the extent of the hierarchy and to free-up memory previously allocated to descendants of the higher-level node. In a specific embodiment, the lock protocol attempts to place a strong lock at the highest possible node in the portion of the resource hierarchy including an object to be locked, and also records in memory a leaf node instance for the object. Another conflicting request, however, may cause de-escalation of the strong lock toward the leaf-levels of the hierarchy. Escalation of leaf-level locks is attempted just before the lock protocol would otherwise record a leaf node instance for an additional object. Lock escalation is performed by recording a leaf node instance for the ancestor node and de-allocating the memory that was used to store leaf-level node instances of the descendants of the ancestor.
Inventors
- 👤 Ashok M. Joshi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 06:05
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F9/526; G06F9/524; G06F2209/00; G06F2209/52; G06F2209/522; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
370 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock upon a first node at a lower level in said resource hierarchy by placing a memory lock on a higher-level second node in said resource hierarchy that is an ancestor of the first node, and recording in memory a leaf-node instance for said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said resource hierarchy than said second node by detecting a lock conflict between the lock requested by the second request and said lock on said second node, de-escalating the lock on the second node to a lower-level fourth node which is a descendant of said second node and an ancestor of said first node but not an ancestor of said third node to avoid conflict with the lock requested by the second request; c) responding to a third request for a memory lock upon a fifth node at a lower level in said resource hierarchy that is at the same level as said first node by escalating said leaf-node instance from said first node to a sixth node in said resource hierarchy that is an ancestor of both of said first and fifth nodes and is not an ancestor of said fourth node; and d) responding to a fourth request for a lock upon a seventh node at a level in said resource hierarchy that is lower than the level in said resource hierarchy of said sixth node by detecting a lock conflict between the lock requested by said fourth request and the lock on said fourth node, and denying said fourth request upon detecting that said sixth node has a leaf-node instance, thereby prohibiting de-escalation of the lock on the fourth node to below said sixth node.
Claim 2
Independent Claim
370 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock upon a first node at a lower level in said resource hierarchy by placing a memory lock on a higher-level second node in said resource hierarchy that is an ancestor of the first node, and recording in memory a leaf-node instance for said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said resource hierarchy than said second node by detecting a lock conflict between the lock requested by the second request and said lock on said second node, de-escalating the lock on the second node to a lower-level fourth node which is a descendant of said second node and an ancestor of said first node but not an ancestor of said third node to avoid conflict with the lock requested by the second request; c) responding to a third request for a memory lock upon a fifth node at a lower level in said resource hierarchy that is at the same level as said first node by escalating said leaf-node instance from said first node to a sixth node in said resource hierarchy that is an ancestor of both of said first and fifth nodes and is not an ancestor of said fourth node; and d) responding to a fourth request for a lock upon a seventh node at a level in said resource hierarchy that is lower than the level in said resource hierarchy of said sixth node by detecting a lock conflict between the lock requested by said fourth request and the lock on said fourth node, and denying said fourth request upon detecting that said sixth node has a leaf-node instance, thereby prohibiting de-escalation of the lock on the fourth node to below said sixth node.
Claim 3
Independent Claim
273 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock upon a first node at a lower level in said resource hierarchy by placing a memory lock at a higher-level second node in said resource hierarchy that is an ancestor of the first node, and recording in memory a leaf-node instance for said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said resource hierarchy that is at the same level as said first node by escalating said leaf-node instance for said first node to a fourth node in said resource hierarchy that is an ancestor of both of said first and third nodes; and c) responding to a third request for a lock upon a fifth node at a level in said resource hierarchy that is lower than the level in said resource hierarchy of said fourth node by detecting a lock conflict between the lock requested by said third request and said lock on said second node, and denying said third request upon detecting that said fourth node has a leaf-node instance, thereby prohibiting de-escalation of the lock on the second node to a level lower than said leaf node instance.
Claim 4
Independent Claim
273 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock upon a first node at a lower level in said resource hierarchy by placing a memory lock at a higher-level second node in said resource hierarchy that is an ancestor of the first node, and recording in memory a leaf-node instance for said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said resource hierarchy that is at the same level as said first node by escalating said leaf-node instance for said first node to a fourth node in said resource hierarchy that is an ancestor of both of said first and third nodes; and c) responding to a third request for a lock upon a fifth node at a level in said resource hierarchy that is lower than the level in said resource hierarchy of said fourth node by detecting a lock conflict between the lock requested by said third request and said lock on said second node, and denying said third request upon detecting that said fourth node has a leaf-node instance, thereby prohibiting de-escalation of the lock on the second node to a level lower than said leaf node instance.
Claim 5
Dependent Claim
134 words
The method as claimed in claim 2, further comprising the step of responding to a fourth request for a memory lock upon a sixth node at a lower level in said resource hierarchy than said second node by detecting a lock conflict between the lock requested by the fourth request and said lock on said second node, de-escalating said lock on said second node to a lower-level seventh node which is a descendant of said second node and an ancestor of said fourth node but not an ancestor of said sixth node to avoid conflict with the lock requested by the fourth request, and placing a lock on an eighth node which is a descendant of said second node and an ancestor of said sixth node but not an ancestor of said seventh node.
Claim 6
Independent Claim
364 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock on a first node in a previously unlocked portion of the resource hierarchy by recording that said first node is non-de-escalatable, and placing a lock on a second node at a highest possible non-conflicting ancestor node of said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said hierarchy than said second node by detecting a lock conflict between the lock requested by the second request and the lock on said second node, removing the lock on said second node, recording that said third node is non-de-escalatable, and placing a lock on each of a pair of highest lower-level nodes, one of which is a descendant of said second node and an ancestor of the first node but not an ancestor of the third node, and the other of which is an ancestor of the third node but not the first node; c) responding to a third request for a memory lock upon a fourth node at a lower level in said resource hierarchy than said second node by recording as non-de-escalatable a fifth node in said resource hierarchy that is an ancestor of both of said first and fourth nodes and is a descendant of one of said pair of highest level nodes; and d) responding to a fourth request for a lock upon a sixth node at a level in said resource hierarchy that is at a lower level in said resource hierarchy than said fifth node by detecting a lock conflict between the lock requested by the fourth request and said lock on said fifth node, and upon detecting that said fifth node is recorded as non-de-escalatable, denying said fourth request.
Claim 7
Independent Claim
364 words
A method of operating a digital computer for processing requests for memory locks upon nodes of a predefined resource hierarchy of addressable memory of said digital computer, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said method comprising the steps of: a) responding to a first request for a memory lock on a first node in a previously unlocked portion of the resource hierarchy by recording that said first node is non-de-escalatable, and placing a lock on a second node at a highest possible non-conflicting ancestor node of said first node; b) responding to a second request for a memory lock upon a third node at a lower level in said hierarchy than said second node by detecting a lock conflict between the lock requested by the second request and the lock on said second node, removing the lock on said second node, recording that said third node is non-de-escalatable, and placing a lock on each of a pair of highest lower-level nodes, one of which is a descendant of said second node and an ancestor of the first node but not an ancestor of the third node, and the other of which is an ancestor of the third node but not the first node; c) responding to a third request for a memory lock upon a fourth node at a lower level in said resource hierarchy than said second node by recording as non-de-escalatable a fifth node in said resource hierarchy that is an ancestor of both of said first and fourth nodes and is a descendant of one of said pair of highest level nodes; and d) responding to a fourth request for a lock upon a sixth node at a level in said resource hierarchy that is at a lower level in said resource hierarchy than said fifth node by detecting a lock conflict between the lock requested by the fourth request and said lock on said fifth node, and upon detecting that said fifth node is recorded as non-de-escalatable, denying said fourth request.
Claim 8
Dependent Claim
50 words
The method as claimed in claim 4, wherein said step a) includes allocating memory for recording that said first node is non-de-escalatable, and recording in said memory that said first node is non-de-escalatable, and said step c) includes de-allocating said memory in which said first node was recorded as non-de-escalatable.
Claim 9
Dependent Claim
73 words
The method as claimed in claim 4, further comprising the steps of searching an instantiation of said resource hierarchy when responding to each request for a lock on a specified node of said hierarchy, said searching starting from a highest-level root node in said hierarchy and continuing downward to nodes at successively lower levels until either a locked node is reached or the specified node is reached and the specified node is unlocked.
Claim 10
Dependent Claim
45 words
The method as claimed in claim 6, wherein de-escalation of the lock on the locked node found by said searching is attempted when said lock on the locked node found by said searching is found to conflict with the requested lock on said specified node.
Claim 11
Dependent Claim
101 words
The method as claimed in claim 4, wherein said method includes recording as non-de-escalatable at least a predetermined number of children of said fifth node, said recording as non-de-escalatable at least a predetermined number of children of said fifth node being performed before said step (c), and said step (c) includes checking whether said sixth node has at least said predetermined number of children that have been recorded as non-de-escalatable, and wherein said fifth node is recorded as non-de-escalatable when said checking finds that said fifth node has at least said predetermined number of children that have been recorded as non-de-escalatable.
Claim 12
Dependent Claim
38 words
The method as claimed in claim 8, wherein said resource hierarchy defines a total number of children for said fifth node, and said predetermined number of children is approximately said total number of children for said fifth node.
Claim 13
Dependent Claim
40 words
The method as claimed in claim 8, wherein said resource hierarchy defines a total number of children for said fifth node, and said predetermined number of children is a majority of said total number of children for said fifth node.
Claim 14
Dependent Claim
346 words
A digital computer comprising a memory and means for processing requests for memory locks upon nodes of a predefined resource hierarchy, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said means for processing requests for memory locks including: a) first means for responding to a request for a lock on a first specified node that is not locked and does not have a locked ancestor by placing a lock on a node that is in said unlocked portion of said resource hierarchy and is a highest ancestor of said first specified node, and recording that said first specified node is non-de-escalatable; b) second means for responding to a request for a lock on a second node having an ancestor node having a lock that does not conflict with the lock requested on the second node by checking whether the ancestor node of said second node is an ancestor of at least one node that is not said second node and that is recorded as non-de-escalatable, and when said ancestor node is found to be an ancestor of at least one node that is not said second node and that is recorded as non-de-escalatable, recording as non-de-escalatable said ancestor node of said second node; c) third means for responding to a request for a lock on a third node having an ancestor node having a lock that conflicts with the lock requested on the third node by checking whether said ancestor node is recorded as non-de-escalatable and whether said ancestor node has a descendent that is neither said third node nor an ancestor of said third node, and when said ancestor node is not recorded as non-de-escalatable and has a descendant that is neither said third node nor an ancestor of said third node, de-escalating the lock on the ancestor of said third node to the descendant that is neither said third node nor an ancestor of said third node.
Claim 15
Dependent Claim
346 words
A digital computer comprising a memory and means for processing requests for memory locks upon nodes of a predefined resource hierarchy, wherein a pre-existing lock on a node precludes a granting of a subsequent request for a conflicting lock on the node until the pre-existing lock is released, said resource hierarchy having a multiplicity of levels, said means for processing requests for memory locks including: a) first means for responding to a request for a lock on a first specified node that is not locked and does not have a locked ancestor by placing a lock on a node that is in said unlocked portion of said resource hierarchy and is a highest ancestor of said first specified node, and recording that said first specified node is non-de-escalatable; b) second means for responding to a request for a lock on a second node having an ancestor node having a lock that does not conflict with the lock requested on the second node by checking whether the ancestor node of said second node is an ancestor of at least one node that is not said second node and that is recorded as non-de-escalatable, and when said ancestor node is found to be an ancestor of at least one node that is not said second node and that is recorded as non-de-escalatable, recording as non-de-escalatable said ancestor node of said second node; c) third means for responding to a request for a lock on a third node having an ancestor node having a lock that conflicts with the lock requested on the third node by checking whether said ancestor node is recorded as non-de-escalatable and whether said ancestor node has a descendent that is neither said third node nor an ancestor of said third node, and when said ancestor node is not recorded as non-de-escalatable and has a descendant that is neither said third node nor an ancestor of said third node, de-escalating the lock on the ancestor of said third node to the descendant that is neither said third node nor an ancestor of said third node.
Claim 16
Dependent Claim
68 words
The digital computer as claimed in claim 11, wherein said second means includes means for checking whether a parent node of said second node has a predetermined number of child nodes that are each recorded as non-de-escalatable, and when said parent node of said second node is found to have a predetermined number of child nodes that are each recorded as non-de-escalatable, recording said parent node as non-de-escalatable.
Claim 17
Dependent Claim
31 words
The digital computer as claimed in claim 12, wherein said resource hierarchy defines a total number of children of said parent node, and said predetermined number is approximately said total number.
Claim 18
Dependent Claim
33 words
The digital computer as claimed in claim 12, wherein said resource hierarchy defines a total number of children of said parent node, and said predetermined number is a majority of said total number.
Claim 19
Dependent Claim
52 words
The digital computer as claimed in claim 12, further comprising means for allocating memory in which nodes in said hierarchy are recorded as non-de-escalatable, and wherein said second means includes means, operative when said parent node is recorded as non-de-escalatable, for de-allocating memory in which said child nodes are recorded as non-de-escalatable.
Claim 20
Dependent Claim
155 words
The digital computer as claimed in claim 11, further comprising: means for searching an instantiation of said resource hierarchy when responding to a request for a lock on a specified node by starting from a highest-level root node in said resource hierarchy and continuing downward to nodes at successive lower levels until either a locked node is reached or the specified node is reached and the specified node is unlocked; means for activating said first means when said search terminates at said specified node and said specified node is unlocked; means for activating said second means when said search terminates at said locked node and said locked node has a lock that conflicts with the lock requested for the specified node; and means for activating said third means when said search terminates at said locked node and said locked node has a lock that does not conflict with the lock requested for the specified node.
Claim 21
Dependent Claim
64 words
The digital computer as claimed in claim 11, further comprising means for allocating memory in which nodes in said hierarchy are recorded as non-de-escalatable, and wherein said second means includes means, operative when said ancestor node of said second node is recorded as non-de-escalatable, for de-allocating memory in which said at least one node that is not said second node is recorded as non-de-escalatable.
References Cited (Backward Citations)
US4698752A
Cited
US4716528A
Cited
US5119490A
Cited
US4914569A
Cited
US5063504A
Cited
US5063501A
Cited
US5063503A
Cited
US5247672A
Cited
US5301290A
Cited
US5285528A
Cited
US5355477A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-08 | 1998-11-07 | 1999-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-08 | 2002-11-07 | 2003-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-08 | 2006-11-07 | 2007-05-09 | $7700.00 | Window Closed / Lapsed |