Fair Software Locking Across a Non-Coherent Interconnect

• US 20130014120A1
• Filed: 07/08/2011
• Published: 01/10/2013
• Est. Priority Date: 07/08/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ross, Jonathan
• Granted Patent: US 9,158,597 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Access to a shared resource by a plurality of execution units is organized and controlled by issuing tickets to each execution unit as they request access to the resource. The tickets are issued by a hardware atomic unit so that each execution unit receives a unique ticket number. A current owner field indicates the ticket number of the execution unit that currently has access to the shared resource. When an execution unit has completed its access, it releases the shared resource and increments the owner field. Execution units awaiting access to the shared resource periodically check the current value of the owner field and take control of the shared resource when their respective ticket values match the owner field.

Claims

1. A method, comprising:

receiving a unique number from a hardware atomic unit;

receiving an owner number associated with a shared system resource; and

accessing the shared system resource when the unique number matches the owner number.

2. The method of claim 1, further comprising:

releasing the shared system resource; and

incrementing the owner number.

3. The method of claim 1, further comprising:

comparing the unique number to the owner number;

receiving an updated owner number after a delay period; and

accessing the shared system resource when the unique number matches the updated owner number.

4. The method of claim 3, wherein the delay period is a fixed interval.

5. The method of claim 3, wherein the delay period is an exponential backoff interval.

6. The method of claim 1, wherein the shared system resource is a hardware device.

7. The method of claim 1, wherein the shared system resource is a data storage location.

8. A method, comprising:

receiving a current number associated with a hardware atomic unit;

receiving an owner number associated with a shared system resource;

comparing the current number associated with the hardware atomic unit to a number that is one less than the owner number; and

either requesting a new number when the current number associated with the hardware atomic unit is equal to a number that is one less than the owner number, or not requesting a new number when the current number associated with the hardware atomic unit is not equal to a number that is one less than the owner number.

9. The method of claim 8, further comprising:

accessing the shared system resource when the new current number matches the owner number.

10. The method of claim 9, further comprising:

releasing the shared system resource; and

incrementing the owner number.

11. The method of claim 8, wherein the current number associated with the hardware atomic unit is equal to a last number issued by the hardware atomic unit.

12. The method of claim 8, wherein the current number associated with the hardware atomic unit is equal to a last number issued by the hardware atomic unit minus a concurrency level for the shared system resource.

13. The method of claim 8, wherein the shared system resource is a hardware device.

14. The method of claim 8, wherein the shared system resource is a data storage location.

15. A system, comprising:

a hardware atomic unit adapted to issue ticket numbers upon request from execution units operating on the system;

a shared resource accessible by the execution units; and

a storage device adapted to hold an owner value associated with the shared resource;

wherein the execution units receive a unique ticket number from the hardware atomic unit and are permitted access to the shared resource when the unique ticket number matches the owner value.

16. The system of claim 15, wherein the execution units are selected from one or more of threads, applications, and processes.

17. The system of claim 15, wherein the storage device is selected from a direct-map cache location, a hardware register, or a memory location.

18. The system of claim 15, wherein the shared resource permits concurrent access by a plurality of execution units, and wherein the execution units are permitted access to the shared resource when the unique ticket number is within a concurrency level number of the owner value.