MANAGING A LOCK TO A RESOURCE SHARED AMONG A PLURALITY OF PROCESSORS

• US 20140108728A1
• Filed: 10/12/2012
• Published: 04/17/2014
• Est. Priority Date: 10/12/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nguyen, Trung N.
• Granted Patent: US 9,354,945 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Provided are a computer program product, system, and method for managing a lock to a resource shared among a plurality of processors. Slots in a memory implement the lock on the shared resource. The slots correspond to counter values that are consecutively numbered and indicate one of busy and free. A requesting processor fetches a counter value comprising a fetched counter value. A determination is made as to whether the slot corresponding to the fetched counter value indicates free. A processor identifier of the requesting processor is inserted into the slot corresponding to the fetched counter value in response to determining that the slot corresponding to the fetched counter value indicates not free. The requesting processor accesses the shared resource in response to determining that the slot corresponding to the fetched counter value indicates free.

Claims

1. A computer program product for managing a lock for a shared resource accessed by a plurality of processors in communication with a memory, wherein the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that executes to cause operations operations, the operations comprising:

maintaining slots in the memory to implement the lock on the shared resource, wherein the slots correspond to counter values that are consecutively numbered and indicate one of busy and free;

fetching, by a requesting processor comprising one of the processors requesting the lock for the shared resource, a counter value comprising a fetched counter value;

determining whether the slot corresponding to the fetched counter value indicates free;

inserting a processor identifier of the requesting processor into the slot corresponding to the fetched counter value in response to determining that the slot corresponding to the fetched counter value indicates not free; and

accessing, by the requesting processor, the shared resource in response to determining that the slot corresponding to the fetched counter value indicates free.

2. The computer program product of claim 1, wherein either all of the slots indicate not free or only one of the slots indicates free.

3. The computer program product of claim 1, wherein the operations further comprise:

performing an atomic operation to perform the fetching of the counter value and incrementing the counter in response to determining the fetch counter value.

4. The computer program product of claim 1, wherein the operations further comprise:

setting a spin location in the memory for the requesting processor to busy;

continually checking, by the requesting processor, the spin location for the requesting processor while the spin location indicates busy; and

accessing, by the requesting processor, the shared resource in response to determining that the spin location for the requesting processor indicates free.

5. The computer program product of claim 4, wherein the operations further comprise:

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the slot indicates free; and

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the spin location for the requesting processor indicates free, wherein the slot indicates that the shared resource is not free if the slot indicates the busy value or one of the processor identifiers.

6. The computer program product of claim 4, wherein there is one separate spin location for each of the processors and wherein there is a same number of slots, spin locations and processors.

7. The computer program product of claim 4, wherein each of the spin locations comprises one cache line and wherein a plurality of slot cache lines are used to implement the slots, such that multiple slots are implemented in each of the slot cache lines.

8. The computer program product of claim 1, wherein the operations further comprise:

determining, by a holding processor, comprising one of the processors, to release the shared resource;

determining, by the holding processor, a next counter value sequentially following the counter value of the slot the holding processor processed when requesting the lock;

determining, by the holding processor, whether a next slot, comprising the slot corresponding to the next counter value, has a busy value;

determining a next processor identifier indicated in the next slot in response to determining that the next slot does not have the busy value; and

notifying a next processor comprising one of the processors identified by the next processor identifier that the lock is free.

9. The computer program product of claim 8, wherein the operations of determining whether the next slot has the busy value and inserting the processor identifier comprise an atomic compare and swap operation.

10. The computer program product of claim 8, wherein the notifying the next processor comprises setting a spin location for the next processor to free, wherein the operations further comprise:

continually determining, by the next processor, whether the spin location for the next processor is free until determining that the spin location is free; and

accessing, by the next processor, the shared resource in response to determining that the spin location is free.

11. The computer program product of claim 8, wherein the operations further comprise:

setting, by the holding processor, the next slot to free in response to determining that the next slot indicates the busy value.

12. The computer program product of claim 1, wherein the operations initialize the slots for the lock by performing:

setting a first slot corresponding to a first counter value to free;

setting the slots other than the first slots to busy;

setting the counter to the first counter value, wherein there is a different counter value corresponding to each of the slots.

13. The computer program product of claim 1 where the shared resource comprises non-parallelized share code in the memory accessible to the processors that cannot be concurrently executed by multiple processors.

14. A system, comprising:

a plurality of processors;

a memory accessed by the plurality of processors; and

a computer readable storage medium having computer program code executed by at least one of the processors to perform operations, the operations comprising;

maintaining slots in the memory to implement a lock on a shared resource, wherein the slots correspond to counter values that are consecutively numbered and indicate one of busy and free;

fetching, by a requesting processor comprising one of the processors requesting the lock for the shared resource, a counter value comprising a fetched counter value;

determining whether the slot corresponding to the fetched counter value indicates free;

inserting a processor identifier of the requesting processor into the slot corresponding to the fetched counter value in response to determining that the slot corresponding to the fetched counter value indicates not free; and

accessing, by the requesting processor, the shared resource in response to determining that the slot corresponding to the fetched counter value indicates free.

15. The system of claim 14, wherein either all of the slots indicate not free or only one of the slots indicates free.

16. The system of claim 14, wherein the operations further comprise:

setting a spin location in the memory for the requesting processor to busy;

continually checking, by the requesting processor, the spin location for the requesting processor while the spin location indicates busy; and

accessing, by the requesting processor, the shared resource in response to determining that the spin location for the requesting processor indicates free.

17. The system of claim 16, wherein the operations further comprise:

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the slot indicates free; and

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the spin location for the requesting processor indicates free, wherein the slot indicates that the shared resource is not free if the slot indicates the busy value or one of the processor identifiers.

18. The system of claim 16, wherein there is one separate spin location for each of the processors and wherein there is a same number of slots, spin locations and processors.

19. The system of claim 16, wherein each of the spin locations comprises one cache line and wherein a plurality of slot cache lines are used to implement the slots, such that multiple slots are implemented in each of the slot cache lines.

20. The system of claim 14, wherein the operations further comprise:

determining, by a holding processor, comprising one of the processors, to release the shared resource;

determining, by the holding processor, a next counter value sequentially following the counter value of the slot the holding processor processed when requesting the lock;

determining, by the holding processor, whether a next slot, comprising the slot corresponding to the next counter value, has a busy value;

determining a next processor identifier indicated in the next slot in response to determining that the next slot does not have the busy value; and

notifying a next processor comprising one of the processors identified by the next processor identifier that the lock is free.

21. A method for managing a lock for a shared resource accessed by a plurality of processors, comprising:

maintaining slots in the memory to implement the lock on the shared resource, wherein the slots correspond to counter values that are consecutively numbered and indicate one of busy and free;

fetching, by a requesting processor comprising one of the processors requesting the lock for the shared resource, a counter value comprising a fetched counter value;

determining whether the slot corresponding to the fetched counter value indicates free;

inserting a processor identifier of the requesting processor into the slot corresponding to the fetched counter value in response to determining that the slot corresponding to the fetched counter value indicates not free; and

accessing, by the requesting processor, the shared resource in response to determining that the slot corresponding to the fetched counter value indicates free.

22. The method of claim 21, wherein either all of the slots indicate not free or only one of the slots indicates free.

23. The method of claim 21, further comprising:

setting a spin location in the memory for the requesting processor to busy;

continually checking, by the requesting processor, the spin location for the requesting processor while the spin location indicates busy; and

accessing, by the requesting processor, the shared resource in response to determining that the spin location for the requesting processor indicates free.

24. The method of claim 23, further comprising:

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the slot indicates free; and

setting the slot corresponding to the fetched counter value to a busy value in response to determining that the spin location for the requesting processor indicates free, wherein the slot indicates that the shared resource is not free if the slot indicates the busy value or one of the processor identifiers.

25. The method of claim 23, wherein there is one separate spin location for each of the processors and wherein there is a same number of slots, spin locations and processors.

26. The method of claim 23, wherein each of the spin locations comprises one cache line and wherein a plurality of slot cache lines are used to implement the slots, such that multiple slots are implemented in each of the slot cache lines.

27. The method of claim 21, further comprising:

determining, by a holding processor ready to release the shared resource, to release the shared resource;

determining, by the holding processor, a next counter value sequentially following the counter value of the slot the holding processor processed when requesting the lock;

determining, by the holding processor, whether a next slot, comprising the slot corresponding to the next counter value, has a busy value;

determining a next processor identifier indicated in the next slot in response to determining that the next slot does not have the busy value; and

notifying a next processor comprising one of the processors identified by the next processor identifier that the lock is free.