Hybrid queue and backoff computer resource lock featuring different spin speeds corresponding to multiple-states
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. 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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. 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.
-
Specification