Achieving both locking fairness and locking performance with spin locks

• US 7,487,279 B2
• Filed: 01/23/2007
• Issued: 02/03/2009
• Est. Priority Date: 01/23/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Su, Gong
• Primary Examiner(s): Dang; Khanh
• Application Number:
  US11/625,842
• Publication Number:
  US 20080177955A1
• Time in Patent Office: 742 Days
• Field of Search: 710/200, 710/240, 710/244, 711/152, 711/163
• US Class Current: 710/200
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for implementing a spin lock in a system including a plurality of processing nodes, each node including at least one processor and a cache memory, the method including steps of: acquiring exclusivity to the cache memory; checking the availability of the spin lock; setting the spin lock to logical one if the spin lock is available; setting the spin lock to logical zero once processing is complete; and explicitly yielding the cache memory exclusivity. Yielding the cache memory exclusivity includes instructing the cache coherent hardware to mark the cache memory as non-exclusive. The cache memory is typically called level two cache.

Claims

1. A method for implementing a spin lock in a system comprising a plurality of processing nodes, each node comprising at least one processor and a cache memory, the method comprising steps of:

obtaining exclusivity to the cache memory;

determining whether the spin lock is available;

acquiring the spin lock upon determining that the spin lock is available;

releasing the spin lock once processing is complete; and

instructing cache coherent hardware in the system to mark the cache memory as non-exclusive in order to explicitly yield the exclusivity to the cache memory;

wherein the instructing step is automatically executed after the releasing step.

2. The method of claim 1 wherein the acquiring step further comprises a step of:

setting the spin lock to a logical state indicating its unavailability to other processors.

3. The method of claim 2 wherein the step of setting the spin lock to the logical state indicating its unavailability further comprises setting the spin lock to an integer other than zero.

4. The method of claim 1 wherein the releasing step further comprises a step of:

setting the spin lock to a logical state indicating its availability to the other processors.

5. The method of claim 4 wherein setting the spin lock to a logical state indicating its availability to the other processors further comprises setting the spin lock to zero.

6. The method of claim 1 wherein the acquiring step further comprises steps of:

accessing the spin lock from a main memory; and

copying the spin lock into the cache memory.

7. The method of claim 1 wherein the releasing step farther comprises a step of:

reacquiring the cache memory exclusivity.

8. The method of claim 1 wherein the determining step further comprises:

interrogating the cache memory to determine if the spin lock is set to the logical state indicating its availability to the other processors.

9. An information processing system comprising:

a distributed shared memory multi-processor architecture comprising;

a main memory comprising a spin lock;

a plurality of nodes operatively coupled with the main memory, each node comprising;

a plurality of processors; and

cache memory;

cache coherent hardware shared by the plurality of nodes;

instructions for explicitly yielding exclusivity to the spin lock, wherein the instructions comprise a directive to whichever one of the plurality of processors is holding the spin lock to instruct the cache coherent hardware to mark the cache memory as non-exclusive once the spin lock is released; and

wherein the plurality of processors execute instructions to;

obtain exclusivity to the cache memory;

determine availability of the spin lock;

acquire the spin lock upon determining that it is available;

release the spin lock once processing completes; and

explicitly yield the exclusivity to the cache memory.

10. The information processing system of claim 9 wherein the cache memory is level two cache memory.

11. The information processing system of claim 9 wherein the plurality of processors execute instructions to:

set the spin lock to a logical state indicating said spin lock'"'"'s unavailability to other processors.

12. The information processing system of claim 9 wherein the spin lock resides in the main memory.

13. The information processing system of claim 9 wherein the plurality of processors further execute instructions to:

set the spin lock to a logical state indicating said spin lock'"'"'s availability to other processors.

14. The information processing system of claim 13 wherein the logical state is zero.

15. The information processing system of claim 11 wherein the logical state is an integer other than zero.

16. The information processing system of claim 9 wherein the plurality of processors share a single cache coherent hardware.