Efficient ticket lock synchronization implementation using early wakeup in the presence of oversubscription
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
45 Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
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. - View Dependent Claims (22, 23)
-
Specification