US6148300A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hybrid queue and backoff computer resource lock featuring different spin speeds corresponding to multiple-states
Assignee: Oracle America Inc
•
Filing: 1998-06-19
•
Granted: 2000-11-14
•
Expires: 2018-06-19
Abstract
Abstract A probabilistic queue lock divides requesters for a lock into at least three sets. In one embodiment, the requesters are divided into the owner of the lock, the first waiting contender, and the other waiting contenders. The first waiting contender is made probabilistically more likely to obtain the lock by having it spin faster than the other waiting contenders. Because the other waiting contenders spin more slowly, the first waiting contender is more likely to be able to observe the free lock and acquire it before the other waiting contenders notice that it is free. The first of the other waiting contenders that determines that the previous first waiting contender has acquired the lock is promoted to be the new first waiting contender and begins spinning fast. Because only the first waiting contender is spinning fast on the lock, it is probable that only the first waiting contender will attempt to acquire the lock when it becomes available.
Inventors
- 👤 Ashok Singhal
- 👤 Erik Hagersten
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 19:51
CPC Classifications
G; G06; G06F; G06F13/00; G06F9/00; G06F9/06; G06F9/46; G06F9/52; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
114 words
A method of synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least three lock states, said method comprising: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a held state and acquiring said lock; if said lock is in said held state, said first requester setting said lock to a wait state and spinning fast; and if said lock is in said wait state, said first requester spinning slow.
Claim 2
Independent Claim
114 words
A method of synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least three lock states, said method comprising: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a held state and acquiring said lock; if said lock is in said held state, said first requester setting said lock to a wait state and spinning fast; and if said lock is in said wait state, said first requester spinning slow.
Claim 3
Dependent Claim
41 words
The method of claim 1 wherein spinning fast includes querying said lock at a first rate to determine if said lock is in said free state, and if said lock is in said free state then requesting acquisition of said lock.
Claim 4
Dependent Claim
47 words
The method of claim 2 wherein spinning slow includes querying said lock at a second rate to determine if said lock is in said wait state, and if said lock is not in said wait state then attempting to become said first waiting contender for said lock.
Claim 5
Dependent Claim
15 words
The method of claim 3 wherein said first rate is faster than said second rate.
Claim 6
Dependent Claim
14 words
The method of claim 4 wherein an atomic command queries and sets said lock.
Claim 7
Dependent Claim
32 words
The method of claim 3 wherein said resource is a memory location and a requester that acquires said lock accesses said memory location and then sets said lock to said free state.
Claim 8
Dependent Claim
47 words
The method of claim 3 wherein attempting to become said first waiting contender comprises querying said lock to determine a state of said lock and if said lock is in said held state then setting said lock to said wait state and said first requester spinning fast.
Claim 9
Dependent Claim
28 words
The method of claim 7 wherein if said lock is in said wait state when attempting to become said first waiting contender, then said first requester spins slow.
Claim 10
Dependent Claim
31 words
The method of claim 8 wherein if said lock is in said free state when attempting to become said first waiting contender, then said first requester requests acquisition to said lock.
Claim 11
Dependent Claim
125 words
A computer-readable storage medium comprising program instructions for synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least three lock states, said program instructions operable to implement the steps of: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a held state and acquiring said lock; if said lock is in said held state, said first requester setting said lock to a wait state and spinning fast; and if said lock is in said wait state, said first requester spinning slow.
Claim 12
Dependent Claim
125 words
A computer-readable storage medium comprising program instructions for synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least three lock states, said program instructions operable to implement the steps of: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a held state and acquiring said lock; if said lock is in said held state, said first requester setting said lock to a wait state and spinning fast; and if said lock is in said wait state, said first requester spinning slow.
Claim 13
Dependent Claim
41 words
The medium of claim 10 wherein spinning fast includes querying said lock at a first rate to determine if said lock is in said free state, and if said lock is in said free state then requesting acquisition of said lock.
Claim 14
Dependent Claim
47 words
The medium of claim 11 wherein spinning slow includes querying said lock at a second rate to determine if said lock is in said wait state, and if said lock is not in said wait state then attempting to become said first waiting contender for said lock.
Claim 15
Dependent Claim
15 words
The medium of claim 12 wherein said first rate is faster than said second rate.
Claim 16
Dependent Claim
14 words
The medium of claim 13 wherein an atomic command queries and sets said lock.
Claim 17
Dependent Claim
32 words
The medium of claim 12 wherein said resources is a memory location and a requester that acquires said lock accesses said memory location and then sets said lock to said free state.
Claim 18
Dependent Claim
47 words
The medium of claim 12 wherein attempting to become said first waiting contender comprises querying said lock to determine a state of said lock and if said lock is in said held state then setting said lock to said wait state and said first requester spinning fast.
Claim 19
Dependent Claim
28 words
The medium of claim 16 wherein if said lock is in said wait state when attempting to become said first waiting contender, then said first requester spins slow.
Claim 20
Dependent Claim
31 words
The medium of claim 17 wherein if said lock is in said free state when attempting to become said first waiting contender, then said first requester requests acquisition to said lock.
Claim 21
Independent Claim
139 words
A method of synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least four lock states, said method comprising: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a first held state and acquiring said lock; if said lock is in said first held state, said first requester setting said lock to a second held state and spinning fast; if said lock is in said second held state, said first requester setting said lock to a wait state and spinning medium; and if said lock is in said wait state, said first requester spinning slow.
Claim 22
Independent Claim
139 words
A method of synchronizing access to a resource in a computer system that includes a lock corresponding to said resource and a plurality of requesters that may attempt to access said resource, wherein said lock has at least four lock states, said method comprising: a first requester of said plurality of requesters requesting acquisition of said lock; if said lock is in a free state, said first requester setting said lock to a first held state and acquiring said lock; if said lock is in said first held state, said first requester setting said lock to a second held state and spinning fast; if said lock is in said second held state, said first requester setting said lock to a wait state and spinning medium; and if said lock is in said wait state, said first requester spinning slow.
References Cited (Backward Citations)
US4750109A
Cited
US4725834A
Cited
US5351043A
Cited
US4922408A
Cited
US4807118A
Cited
US5055999A
Cited
US5341483A
Cited
US5502840A
Cited
US5506961A
Cited
US5875485A
Cited
US5495481A
Cited
US5548728A
Cited
US5592486A
Cited
US5860159A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-14 | 2004-05-15 | 2004-11-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-14 | 2008-05-15 | 2008-11-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-14 | 2012-05-15 | 2012-11-14 | $7700.00 | Window Closed / Lapsed |