SUPPORTING EFFICIENT SPIN-LOCKS AND OTHER TYPES OF SYNCHRONIZATION IN A CACHE-COHERENT MULTIPROCESSOR SYSTEM

• US 20100332766A1
• Filed: 06/26/2009
• Published: 12/30/2010
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Cypher, Robert E., Zeffer, Haakan E.
• Granted Patent: US 8,296,524 B2
• Time in Patent Office: Days
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Some embodiments of the present invention provide a system that acquires a lock in a shared memory multiprocessor system. During operation, the system loads the lock into a cache associated with the thread and then reads a value of the lock. If the value indicates that the lock is currently held by another thread, the system periodically executes an instruction that tests a status of the lock. If the status indicates the lock is valid, the system continues to test the status of the lock. Otherwise, if the status indicates that the lock was invalidated by a store, the system attempts to acquire the lock by executing an atomic operation. On the other hand, if the status indicates that the lock was invalidated by an atomic operation, or that the lock is not present in the cache, the system repeats the loading and reading operations.

Claims

1. A method for acquiring a lock for a thread in a shared memory multiprocessor system, comprising:

loading the lock into a cache associated with the thread;

reading a value of the lock; and

if the value indicates that the lock is currently held by another thread, periodically executing an instruction that tests a status of the lock, wherein

if the status indicates that the lock is valid, continuing to test the status of the lock;

if the status indicates that the lock was invalidated by a store, attempting the acquire the lock by executing an atomic operation; and

if the status indicates that the lock was invalidated by an atomic operation, or that the lock is not present in the cache, repeating the loading and reading operations.

2. The method of claim 1, wherein attempting to acquire the lock involves performing a test-and-set operation on the lock.

3. The method of claim 1, wherein if the attempt to acquire the lock fails, the method further comprises repeating the loading and reading operations.

4. The method of claim 1, wherein if the attempt to acquire the lock succeeds, the method further comprises:

causing a coherence protocol to invalidate copies of the lock located in other caches, so that status information for the invalidated copies indicates the invalidations were caused by the atomic operation;

executing a critical section associated with the lock; and

after the critical section is executed, releasing the lock.

5. The method of claim 4,

wherein releasing the lock involves storing a value to the lock;

and

wherein storing the value to the lock causes a coherence protocol to invalidate copies of the lock located in other caches, so that status information for the invalidated copies indicates the invalidations were caused by a store.

6. The method of claim 1, wherein prior to loading and reading the lock, the method further comprises initially attempting to acquire the lock, and if the initial attempt fails, performing the loading and reading operations.

7. The method of claim 1,

wherein the lock is located in a cache line;

and

wherein loading the lock involves loading the cache line.

8. The method of claim 7, wherein the instruction that tests the status of the lock additionally updates state information for the cache line to indicate that the cache line was recently used, so that the cache line is less likely to be replaced during subsequent cache accesses.

9. The method of claim 1, wherein the instruction that tests the status of the lock operates by reading status information for the lock from:

a cache line associated with the lock;

or

a per-thread structure associated with the thread.

10. The method of claim 1,

wherein the lock is loaded into a shared cache;

wherein loading the lock involves executing a load-track primitive which initiates tracking of updates to the lock; and

wherein if the tracking indicates that the lock has been updated but not invalidated, the method further comprises attempting to acquire the lock by executing the atomic operation.

11. A system that facilitates acquiring a lock for a thread, comprising:

a multiprocessor comprising a plurality of processors;

a lock-acquiring mechanism in a processor in the plurality of processors, wherein the lock-acquiring mechanism is configured to perform an atomic operation to acquire the lock; and

a lock-testing mechanism in the processor, wherein the lock-testing mechanism is configured to load the lock into a cache associated with the thread, and read a value of the lock; and

wherein if the value indicates that the lock is currently held by another thread, the lock-testing mechanism is configured to periodically execute an instruction that tests a status of the lock;

wherein if the status indicates that the lock is valid, the lock-testing mechanism is configured to continue to test the status of the lock;

wherein if the status indicates that the lock was invalidated by an atomic operation, or that the lock is not present in the cache, the lock-testing mechanism is configured to repeat the loading and reading operations; and

wherein if the status indicates that the lock was invalidated by a store, the lock-acquiring mechanism is configured to attempt to acquire the lock by executing the atomic operation.

12. The system of claim 11, wherein the lock-acquiring mechanism is configured to perform a test-and-set operation on the lock.

13. The system of claim 11, wherein if the attempt to acquire the lock fails, the lock-testing mechanism is configured to repeat the loading and reading operations.

14. The system of claim 11,

wherein if the attempt to acquire the lock succeeds, the processor is configured to,

cause a coherence protocol to invalidate copies of the lock located in other caches, so that status information for the invalidated copies indicates the invalidations were caused by the atomic operation, and

execute a critical section associated with the lock;

and

wherein the processor further comprises a lock-releasing mechanism, wherein after the critical section is executed, the lock-releasing mechanism is configured to release the lock.

15. The system of claim 14,

wherein the lock-releasing mechanism is configured to release the lock by storing a value to the lock;

and

wherein storing the value to the lock causes a coherence protocol to invalidate copies of the lock located in other caches, so that status information for the invalidated copies indicates the invalidations were caused by a store.

16. The system of claim 11,

wherein prior to loading and reading the lock, the lock-acquiring mechanism is configured initially to attempt to acquire the lock;

and

wherein if the initial attempt fails, the lock-testing mechanism is configured to perform the loading and reading operations.

17. The system of claim 11,

wherein the lock is located in a cache line;

and

wherein loading the lock involves loading the cache line.

18. The system of claim 17, wherein the instruction that tests the status of the lock additionally updates state information for the cache line to indicate that the cache line was recently used, so that the cache line is less likely to be replaced during subsequent cache accesses.

19. The system of claim 11,

wherein the lock is loaded into a shared cache;

wherein loading the lock involves executing a load-track primitive which initiates tracking of updates to the lock; and

wherein if the tracking indicates that the lock has been updated but not invalidated, the system further comprises attempting to acquire the lock by executing the atomic operation.

20. A multiprocessor system that facilitates acquiring a lock for a thread, comprising:

a plurality of processors;

wherein a processor in the plurality of processors provides a lock-acquiring instruction which is configured to perform an atomic operation to acquire the lock;

wherein the processor also provides a lock-testing instruction, which is configured to load the lock into a cache associated with the thread, and read a value of the lock;

wherein if the value indicates that the lock is currently held by another thread, the lock-testing instruction is configured to periodically execute an instruction that tests a status of the lock;

wherein if the status indicates that the lock is valid, the lock-testing instruction is configured to continue testing the status of the lock;

wherein if the status indicates that the lock was invalidated by an atomic operation, or that the lock is not present in the cache, the lock-testing instruction is configured to repeat the loading and reading operations; and

wherein if the status indicates that the lock was invalidated by a store, the processor is configured to execute the lock-acquiring instruction to attempt to acquire the lock.