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

• US 8,434,082 B2
• Filed: 06/22/2006
• Issued: 04/30/2013
• Est. Priority Date: 06/22/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Bliss, Brian E.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Huaracha, Willy W
• Application Number:
  US11/473,580
• Publication Number:
  US 20070300226A1
• Time in Patent Office: 2,504 Days
• Field of Search: 718/100, 718/101, 718/14, 718/107, 718/1, 718/102, 718/108, 718/104
• 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 for a first thread among a plurality of threads from a monotonically increasing ticket counter;

selecting a first memory location based on the ticket value and the number of memory locations in a distributed polling data structure;

computing a difference between the ticket value and a value from the first memory location, wherein the difference represents a number of other threads among the plurality of threads waiting for access to a shared single-access resource in contention among the plurality of threads which is controlled by a processor;

yielding a remaining portion of a time slice on the processor which is allocated to the first thread, to one of the other threads, when the difference exceeds a threshold value;

polling the first memory location without yielding the remaining portion of the time slice on the processor, until the first memory location contains a value equal to the ticket value when the difference does not exceed the threshold value, wherein the ticket value is stored in a second memory location, and wherein the first memory location and the second memory location are n bytes apart, where n is equal to or exceeds a size of a cache line of the processor;

acquiring the shared single-access resource for the first thread when the value of the first memory location is equal the thread'"'"'s ticket value;

releasing the shared single-access resource when the first thread has completed access;

updating a memory location being polled by a next thread that will be woken up to switch from yield-waiting to busy-waiting; and

updating a memory location being polled by a next thread that is currently busy-waiting.

2. The method of claim 1, further comprising:

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

3. The method of claim 2 wherein decreasing the threshold 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 further comprising:

updating another counter variable that is used to indicate which ticket value should be released, to release a next waiting thread.

5. The method of claim 1, wherein obtaining the ticket value for the first thread comprises calling a WaitInLine operation which obtains the ticket value from a counter by using a fetch-and-increment operation which cannot be interrupted by some other thread.

6. The method of claim 1 wherein an address (index) of a NowServing array element is computed based on the ticket value.

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

obtaining a ticket value for a first thread among a plurality of threads from a monotonically increasing ticket counter;

selecting a first memory location based on the ticket value and the number of memory locations in a distributed polling data structure;

computing a difference between the ticket value and a value from the first memory location, wherein the difference represents a number of other threads among the plurality of threads waiting for access to a shared single-access resource in contention among the plurality of threads which is controlled by the programmable processor;

yielding a remaining portion of a time slice on the programmable processor which is allocated to the first thread, to one of the other threads, when the difference exceeds a threshold value;

polling the first memory location without yielding the remaining portion of the time slice on the programmable processor, until the first memory location contains a value equal to the ticket value when the difference does not exceed the threshold value, wherein the ticket value is stored in a second memory location, and wherein the first memory location and the second memory location are n bytes apart, where n is equal to or exceeds a size of a cache line of the programmable processor;

acquiring the shared single-access resource for the first thread when the value of the first memory location is equal the thread'"'"'s ticket value;

releasing the shared single-access resource when the first thread has completed access;

updating a memory location being polled by a next thread that will be woken up to switch from yield-waiting to busy-waiting; and

updating a memory location being polled by a next thread that is currently busy-waiting.

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

decreasing the ticket value when a thread in a critical section is sharing the programmable processor.

9. The non-transitory computer-readable medium of claim 7 wherein obtaining the ticket value for the first thread comprises calling a WaitInLine operation which obtains the ticket value from a counter by using a fetch-and-increment operation which cannot be interrupted by some other thread.

10. The non-transitory computer-readable medium of claim 7 wherein the memory location is one of a plurality of polling locations in an array, and 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 among the plurality of threads;

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.

11. The non-transitory computer-readable medium of claim 7, containing additional instructions to cause the programmable processor to perform operations comprising:

signaling the first thread after the value from the memory location equals the ticket value.