Controlling access to shared resource by issuing tickets to plurality of execution units

• US 9,158,597 B2
• Filed: 07/08/2011
• Issued: 10/13/2015
• Est. Priority Date: 07/08/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ross, Jonathan
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Lee, James J
• Application Number:
  US13/179,344
• Publication Number:
  US 20130014120A1
• Time in Patent Office: 1,558 Days
• US Class Current: 1/1
• 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 memory device having program instructions stored thereon that, upon execution by processor of a computer system, cause the computer system to:

assign a current-owner value to a shared resource, the current-owner value identifying a ticket value that is eligible to be granted current access to the shared resource;

issue a first ticket value to a first process by a ticket provider, the ticket provider configured to issue ticket values that are used to determine access to the shared resource;

allow the first process to access the shared resource when a difference between the first ticket value and the current-owner value is equal to or smaller than a selected number of allowed concurrent processes, wherein the selected number of allowed concurrent processes is greater than one;

increment the current-owner value when the first process has finished accessing the shared resource;

obtain, by a second process, a last-issued-ticket value from the ticket provider without requesting a new ticket from the ticket provider, the last-issued-ticket value representing a value of a last ticket actually issued by the ticket provider to one of the plurality of processes;

compare the current-owner value and the last-issued-ticket value;

based upon the comparison, request a ticket for the second process from the ticket provider when a difference between the last-issued-ticket value and the current-owner value is equal to or smaller than the selected number of allowed concurrent processes; and

based upon the comparison, do not request a ticket for the second process from the ticket provider when the difference between the last-issued-ticket value and the current-owner value is greater than the selected number of allowed concurrent processes.

2. The memory device of claim 1, wherein a process may access the shared resource immediately by taking a ticket when the last-issued-ticket value is equal to one less than current-owner value.

3. The memory device of claim 1, wherein a process will not achieve immediate access to the shared resource when the last-issued-ticket value is other than one less than the current-owner value.

4. The memory device of claim 1, wherein obtaining the last-issued-ticket value does not require reading a current ticket value at the ticket provider.

5. The memory device of claim 1, wherein the ticket provider is a hardware atomic unit.

6. A system, comprising:

a processor having a plurality of execution units; and

a memory coupled to the processor, the memory having program instructions stored thereon that, upon execution by the processor, cause the system to;

assign a current-owner value to a shared resource, the current-owner value identifying a ticket value that is eligible to be granted current access to the shared resource;

issue a first ticket value to a first process by a ticket provider, the ticket provider configured to issue ticket values that are used to determine access to the shared resource;

allow the first process to access the shared resource when a difference between the first ticket value and the current-owner value is equal to or smaller than a selected number of allowed concurrent processes, wherein the selected number of allowed concurrent processes is greater than one;

increment the current-owner value when the first process has finished accessing the shared resource;

obtain, by a second process, a last-issued-ticket value from the ticket provider without requesting a new ticket from the ticket provider, the last-issued-ticket value representing a value of a last ticket actually issued by the ticket provider to one of the plurality of processes;

compare the current-owner value and the last-issued-ticket value;

based upon the comparison, request a ticket for the second process from the ticket provider when a difference between the last-issued-ticket value and the current-owner value is equal to or smaller than the selected number of allowed concurrent processes; and

based upon the comparison, do not request a ticket for the second process from the ticket provider when the difference between the last-issued-ticket value and the current-owner value is greater than the selected number of allowed concurrent processes.

7. The system of claim 6, 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.

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

9. The system of claim 6, wherein the system further comprises a storage device storing the last-issued-ticket value and the current-owner value, wherein the storage device is selected from a direct-map cache location, a hardware register, or a memory location.

10. A method, comprising:

assign a current-owner value to a shared resource, the current-owner value identifying a ticket value that is eligible to be granted current access to the shared resource;

issuing a first ticket value to a first process by a ticket provider, the ticket provider configured to issue ticket values that are used to determine access to the shared resource;

allow the first process to access the shared resource when a difference between the first ticket value and the current-owner value is equal to or smaller than a selected number of allowed concurrent processes, wherein the selected number of allowed concurrent processes is greater than one;

incrementing the current-owner value when the first process has finished accessing the shared resource;

obtaining, by a second process, a last-issued-ticket value from the ticket provider without requesting a ticket from the ticket provider, the last-issued-ticket value representing a value of a last ticket actually issued by the ticket provider to one of the plurality of processes;

comparing the current-owner value and the last-issued-ticket value;

based upon the comparison, requesting a ticket for the second process from the ticket provider when a difference between the last-issued-ticket value and the current-owner value is equal to or smaller than a selected number of allowed concurrent processes; and

based upon the comparison, not requesting a ticket for the second process from the ticket provider when the difference between the last-issued-ticket value and the current-owner value is greater than the selected number of allowed processes.

11. The method of claim 10, wherein obtaining the last-issued-ticket value does not require reading a current ticket value at the ticket provider.

12. The method of claim 10, wherein the ticket provider is a hardware atomic unit.