Efficient ticket lock synchronization implementation using early wakeup in the presence of oversubscription

• US 20070300226A1
• Filed: 06/22/2006
• Published: 12/27/2007
• Est. Priority Date: 06/22/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Bliss, Brian E.
• Granted Patent: US 8,434,082 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A turn-oriented thread and/or process synchronization facility obtains a ticket value from a monotonically increasing ticket counter and waits until a memory location contains a value equal to the ticket value, yielding the processor between polls of the memory location only if a difference between the ticket value and the contents of the memory location exceeds a threshold value. Machine-readable media containing instructions to implement similar methods, and systems that can use the methods, are also described and claimed.

Claims

1. A method comprising:

obtaining a ticket value from a monotonically increasing ticket counter;

computing a difference between the ticket value and a value from a memory location;

yielding a processor if the difference exceeds a threshold value; and

polling the memory location without yielding until it contains a value equal to the ticket value if the difference does not exceed the threshold value.

2. The method of claim 1, further comprising:

decreasing the threshold value if a thread in a critical section is sharing the processor.

3. The method of claim 2 wherein decreasing comprises:

determining a number of positions by which a current thread trails the thread in the critical section; and

decreasing the threshold value by the number of positions.

4. The method of claim 1 wherein the memory location is a first memory location, the method further comprising:

updating a value in a second memory location to release a next waiting thread.

5. The method of claim 4 wherein the first memory location and the second memory location are identical.

6. The method of claim 4 wherein the first memory location and the second memory location are n bytes apart, n to equal or exceed a size of a cache line of the processor.

7. The method of claim 1 wherein an address of the memory location is related to the ticket value.

8. A computer-readable medium containing instructions to cause a programmable processor to perform operations comprising:

initializing a serialized-access counter;

obtaining a ticket value from the counter;

computing a polling location from the ticket value; and

examining the polling location repeatedly until a value in the polling location equals the ticket value.

9. The computer-readable medium of claim 8, containing additional instructions to cause the programmable processor to perform operations comprising:

relinquishing a time slice if a difference between the value in the polling location and the ticket value exceeds a configurable value; and

examining the polling location in a busy-waiting loop if the difference does not exceed the configurable value.

10. The computer-readable medium of claim 9, containing additional instructions to cause the programmable processor to perform operations comprising:

decreasing the configurable value if a thread in a critical section is sharing the programmable processor.

11. The computer-readable medium of claim 8 wherein computing the polling location from the ticket value comprises computing a remainder of the ticket value divided by a number of polling locations in an array of polling locations.

12. The computer-readable medium of claim 11 wherein a first polling location in the array and a following polling location in the array are displaced by a number of bytes that equals or exceeds a cache line size of the programmable processor.

13. The computer-readable medium of claim 8 wherein the polling location is a first polling location, containing additional instructions to cause the programmable processor to perform operations comprising:

calculating a second ticket value, the second ticket value to be a ticket value obtained by a different thread;

computing a second polling location from the second ticket value; and

examining the second polling location in a yield-waiting loop until a value in the second polling location equals the second ticket value.

14. The computer-readable medium of claim 8, containing additional instructions to cause the programmable processor to perform operations comprising:

signaling a thread after the value in the polling location equals the ticket value.

15. A method comprising:

obtaining a ticket value atomically from a ticket counter;

polling a first memory location in a yield-waiting loop;

polling a second memory location in a busy-waiting loop after completing the yield-waiting loop;

using a shared, single-access resource; and

updating a value in a third memory location.

16. The method of claim 15, further comprising:

updating a value in a fourth memory location.

17. The method of claim 15 wherein the first memory location, the second memory location and the third memory location are identical.

18. The method of claim 15 wherein an address of the first memory location and an address of the second memory location differ by at least a number of bytes in a cache line of a processor.

19. The method of claim 15 wherein the polling and updating operations are performed atomically.

20. The method of claim 19 wherein at least one of the obtaining, polling and updating operations is protected by a synchronization primitive.

21. A system comprising:

a plurality of programmable processors, each including a cache memory;

a resource to be shared between a plurality of threads executing on the processors; and

access control logic including a ticket granting counter, a plurality of now-serving indicators, and early wakeup logic to busy-wait if a ticket value from the ticket granting counter is close to one of the plurality of now-serving indicators, wherein

the access control logic is to prevent more than one thread at a time from accessing the resource.

22. The system of claim 21, further comprising:

a main memory to contain the plurality of now-serving indicators;

wherein

an address of a first indicator differs from an address of an immediately successive indicator by a number of bytes that equals or exceeds a size of a cache line of one of the plurality of programmable processors.

23. The system of claim 21, further comprising:

ticket release logic to update one of the plurality of now-serving indicators when a thread has finished using the resource.