System and method for accessing a shared computer resource using a lock featuring different spin speeds corresponding to multiple states

• US 6,578,033 B1
• Filed: 06/20/2000
• Issued: 06/10/2003
• Est. Priority Date: 06/19/1998
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hagersten, Erik, Singhal, Ashok
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US09/597,863
• Time in Patent Office: 1,085 Days
• Field of Search: 707/2, 707/8, 707/201
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

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.

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 first state, said first requester setting said lock to a second state and acquiring said lock;

if said lock is in said second state, said first requester setting said lock to a third state and spinning at a first rate; and

if said lock is in said third state, said first requester spinning at a second rate.

2. The method as recited in claim 1, wherein said first state is indicative of said resource being available for acquisition.

3. The method as recited in claim 1, wherein said second state is indicative of said resource not being available for acquisition and causing a second requester to become a first waiting contender for said lock.

4. The method as recited in claim 3, wherein said first rate is faster than said second rate.

5. The method as recited in claim 1, wherein said third state is indicative of said resource not being available for acquisition and causing a third requester to become another waiting contender for said lock.

6. The method as recited in claim 1, wherein said spinning at a first rate includes executing a first software loop to query said lock to determine if said lock is in said first, second or third state.

7. The method as recited in claim 1, wherein said spinning at a second rate includes executing a second software loop to query said lock to determine if said lock is in said first, second or third state, wherein said second software loop includes a delay.

8. The method as recited in claim 1, wherein said first, second and third states correspond to three values in a register.

9. The method as recited in claim 8, wherein said first state is a free state.

10. The method as recited in claim 8, wherein said second state is a held state.

11. The method as recited in claim 8, wherein said third state is a wait state.

12. A computer system comprising:

a resource;

a plurality of requesters coupled to said resource and configured to request access to said resource;

a lock coupled to said resource and configured to synchronize access to said resource, wherein said lock has at least a first state, a second state and a third state;

wherein, in response to a first requester of said plurality of requesters determining that said lock is in said first state, said first requester of said plurality of requesters is configured to set said lock to said second state and acquire said lock;

wherein, in response to a second requester of said plurality of requesters determining that said lock is in said second state, said second requester of said plurality of requesters is configured to set said lock to said third state and to spin at a first rate; and

wherein, in response to a third requester of said plurality of requesters determining that said lock is in said third state, said third requester of said plurality of requesters is configured to spin at a second rate.

13. The computer system as recited in claim 12, wherein said first rate is faster than said second rate.

14. The computer system as recited in claim 12, wherein spinning at said first rate includes executing a first software loop to query said lock to determine if said lock is in said first, second or third state.

15. The computer system as recited in claim 14, wherein spinning at said second rate includes executing a second software loop to query said lock to determine if said lock is in said first, second or third state, wherein said second software loop includes a delay.

16. The computer system as recited in claim 15, wherein if said lock is in said second state, then said second requester of said plurality of requesters is configured to become a first waiting contender for said lock.

17. The computer system as recited in claim 12, wherein said first, second and third states correspond to three values in a register.

18. The computer system as recited in claim 17, wherein said first state is a free state.

19. The computer system as recited in claim 17, wherein said second state is a held state.

20. The computer system as recited in claim 17, wherein said third state is a wait state.