Patent US6144983A successfully refreshed from Google Patents.
US6144983A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dynamic lock granularity escalation and de-escalation in a computer system
Assignee: Oracle International Corp
•
Filing: 1998-06-09
•
Granted: 2000-11-07
•
Expires: 2018-06-09
Abstract
Abstract A method and apparatus for dynamic lock granularity escalation and de-escalation in a computer system is provided. Upon receiving a request for a resource, a scope of a previously granted lock is modified. According to one embodiment, hash lock de-escalation is employed. In hash lock de-escalation, the scope of the previously granted lock held on a set of resources is reduced by de-escalating the previously granted lock from a coarser-grain lock to one or more finer-grain locks on members of the set. According to another embodiment, hash lock escalation is employed. In hash lock escalation, the scope of previously granted locks held on one or more members of the set of resources are released and promoted into a coarser-grain lock that covers the set of resources as well as the requested resource.
Inventors
- 👤 Boris Klots
- 👤 Roger J. Bamford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:49
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
128 words
A method for managing access to a computer data resource, the method comprising: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 2
Independent Claim
128 words
A method for managing access to a computer data resource, the method comprising: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 3
Dependent Claim
25 words
The method of claim 1, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.
Claim 4
Dependent Claim
80 words
The method of claim 1, wherein said step of detecting comprises: testing to determine whether said granted lock covers said hash bucket; and de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.
Claim 5
Dependent Claim
25 words
The method of claim 1, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 6
Dependent Claim
106 words
The method of claim 1, wherein said request was issued by a requestor, the method further comprising: testing to determine whether: said requester already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and a lock on said hash bucket is not owned by any other entity; and escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.
Claim 7
Dependent Claim
32 words
The method of claim 1, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
Claim 8
Dependent Claim
56 words
The method of claim 1, further comprising the steps of: creating a log of disk access paths over a period of time; generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.
Claim 9
Independent Claim
95 words
A method for de-escalation of disjoint sets of computer data resources, comprising the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource of said group; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 10
Independent Claim
95 words
A method for de-escalation of disjoint sets of computer data resources, comprising the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource of said group; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 11
Dependent Claim
55 words
The method of claim 8, further comprising the steps of: creating a log of disk access paths over a period of time; and generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.
Claim 12
Dependent Claim
25 words
The method of claim 9, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 13
Dependent Claim
32 words
The method of claim 9, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
Claim 14
Dependent Claim
124 words
A computer system configured to perform the steps of: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 15
Dependent Claim
124 words
A computer system configured to perform the steps of: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 16
Dependent Claim
26 words
The computer system of claim 12, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.
Claim 17
Dependent Claim
82 words
The computer system of claim 12, wherein said step of detecting comprises: testing to determine whether said previously granted lock covers said hash bucket; and de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.
Claim 18
Dependent Claim
26 words
The computer system of claim 12, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 19
Dependent Claim
107 words
The computer system of claim 12, wherein said request was issued by a requestor, the method further comprising: testing to determine whether: said requestor already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and a lock on said hash bucket is not owned by any other entity; and escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.
Claim 20
Dependent Claim
33 words
The computer system of claim 12, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
Claim 21
Dependent Claim
59 words
The computer system of claim 12, further configured to perform the steps of: creating a log of disk access paths over a period of time; generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.
Claim 22
Dependent Claim
93 words
A computer system configured to perform the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource said group; modifying a lock scope associated with said granted lock when a lock is detected; and granting a new lock that covers said requested resource.
Claim 23
Dependent Claim
93 words
A computer system configured to perform the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource said group; modifying a lock scope associated with said granted lock when a lock is detected; and granting a new lock that covers said requested resource.
Claim 24
Dependent Claim
58 words
The computer system of claim 19, further configured to perform the steps of: creating a log of disk access paths over a period of time; and generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.
Claim 25
Dependent Claim
26 words
The computer system of claim 20, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 26
Dependent Claim
33 words
The computer system of claim 20, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
Claim 27
Dependent Claim
160 words
A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 28
Dependent Claim
160 words
A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning a plurality of resources to a plurality of hash buckets based on key values associated with said plurality of resources, wherein said step of assigning is performed without respect to any relative order associated with said key values; receiving a request for a resource in said plurality of resources; in response to receiving said request, performing the steps of: generating a hash value based on a key value of said resource; identifying a hash bucket associated with said hash value; detecting a granted lock covering any of said plurality of resources in said hash bucket; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 29
Dependent Claim
26 words
The computer-readable medium of claim 23, wherein said plurality of resources that are assigned to a particular hash bucket are disjoint relative to said key values.
Claim 30
Dependent Claim
82 words
The computer-readable medium of claim 23, wherein said step of detecting comprises: testing to determine whether said previously granted lock covers said hash bucket; and de-escalating said granted lock to cover a first subset of resources in said hash bucket, said first subset not including said requested resource, when said granted lock covers said hash bucket; and wherein said new lock covering said requested resource includes a second subset of resources in said hash bucket, said second subset including said requested resource.
Claim 31
Dependent Claim
26 words
The computer-readable medium of claim 23, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 32
Dependent Claim
107 words
The computer-readable medium of claim 23, wherein said request was issued by a requestor, the method further comprising: testing to determine whether: said requestor already owns one or more locks on a subset of said resources in said hash bucket, said subset including at least one resource other than said requested resource, and a lock on said hash bucket is not owned by any other entity; and escalating said lock on said subset into a lock on said hash bucket, when said requestor already owns said one or more locks on said subset and said lock on said hash bucket is not owned by any other entity.
Claim 33
Dependent Claim
33 words
The computer-readable medium of claim 23, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
Claim 34
Dependent Claim
57 words
The computer-readable medium of claim 23, further comprising the steps of: creating a log of disk access paths over a period of time; generating a hash function, based upon said log, that maps requests on adjacent resources into coarser-grain hash lock requests on disjoint sets of resources thereby breaking up a hot spot identified by said log.
Claim 35
Dependent Claim
125 words
A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource in said group; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 36
Dependent Claim
125 words
A computer-readable medium having stored therein one or more sequences of instructions for managing access to a data resource, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning a plurality of disjoint resources to a plurality of groups; receiving a request for a lock on a resource in said plurality of disjoint resources; and in response to receiving said request, performing the steps of: identifying a group in said plurality of groups that includes said requested resource; detecting a granted lock covering any constituent resource in said group; modifying a lock scope associated with said granted lock; and granting a new lock that covers said requested resource.
Claim 37
Dependent Claim
55 words
The computer-readable medium of claim 30, further comprising the steps of: creating a log of disk access paths over a period of time; generating a hash function, based upon said log, said hash function assigning said plurality of disjoint resources into said plurality of groups thereby breaking up a hot spot identified by said log.
Claim 38
Dependent Claim
26 words
The computer-readable medium of claim 31, wherein said step of modifying said lock scope comprises de-escalating said granted lock into one or more a fine-grain locks.
Claim 39
Dependent Claim
33 words
The computer-readable medium of claim 31, wherein said steps of modifying said lock scope and granting said new lock includes escalating said granted lock and said requested resource into a single coarse-grain lock.
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) | 2003-11-07 | 2004-05-08 | 2004-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-07 | 2008-05-08 | 2008-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-07 | 2012-05-08 | 2012-11-07 | $7700.00 | Window Closed / Lapsed |