Adaptive handling of priority inversions using transactions

• US 9,400,677 B2
• Filed: 05/14/2013
• Issued: 07/26/2016
• Est. Priority Date: 01/02/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Trumbull, Benjamin C., Swift, Adam C., Blaine, Russell A., Nham, Benjamin H., Christianson, Kari E.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Huaracha, Willy W
• Application Number:
  US13/893,631
• Publication Number:
  US 20140189693A1
• Time in Patent Office: 1,169 Days
• Field of Search: 718/100, 718/101, 718/102, 718/103
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

An operating system of a data processing system receives a request from a first process to acquire an exclusive lock for accessing a resource of the data processing system. A second priority of a second process is increased to reduce total execution time. The second process is currently in possession of the exclusive lock for performing a transactional operation with the resource. The second priority was lower than a first priority of the first process. The operating system notifies the second process to indicate that another process is waiting for the exclusive lock to allow the second process to complete or roll back the transactional operation and to release the exclusive lock thereafter.

Claims

1. A computer-implemented method, comprising:

receiving, at a resource manager of an operating system of a data processing system, a request from a first process to acquire an exclusive lock for accessing a resource of the data processing system, the first process having a first priority;

increasing by a priority manager of the operating system a second priority of a second process to reduce total lock hold time of the second process, the second process currently in possession of the exclusive lock for performing a transactional operation with the resource, wherein the second priority was lower than the first priority of the first process, wherein the first process and the second process are running within the data processing system;

notifying the second process by the resource manager to indicate that another process is waiting for the exclusive lock, including setting a flag to a predetermined value in a predetermined memory location accessible by the second process, wherein the second process is to periodically poll the predetermined memory location to determine whether another process is waiting for the exclusive lock, wherein in response to the notification, the second process can decide whether to complete or roll back the transactional operation and to release the exclusive lock thereafter;

receiving, by the resource manager, an indication that the second process has released the lock in response to the notification; and

allocating the lock to the first process to allow the first process to access the resource.

2. The method of claim 1, wherein the second priority of the second process is increased to at least match the first priority of the first process.

3. The method of claim 1, further comprising revoking, by the resource manager of the operating system, an ownership of the exclusive lock from the second process after a predetermined period of time if the second process has not released the exclusive lock.

4. The method of claim 1, wherein notifying the second process comprises rejecting further access of the second process to the resource by returning errors in response to current or future input/output (IO) requests to the resource.

5. The method of claim 4, wherein the rejection causes the second process to abort further access of the resource and to release the exclusive lock associated with the resource.

6. The method of claim 4, further comprising:

performing a rollback operation of the transactional operation on behalf of the second process;

revoking an ownership of the exclusive lock from the second process without waiting for the second process to release the exclusive lock; and

assigning the exclusive lock to the first process.

7. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform a method, the method comprising:

receiving, at a resource manager of an operating system of a data processing system, a request from a first process to acquire an exclusive lock for accessing a resource of the data processing system, the first process having a first priority;

increasing by a priority manager of the operating system a second priority of a second process to reduce total lock hold time of the second process, the second process currently in possession of the exclusive lock for performing a transactional operation with the resource, wherein the second priority was lower than the first priority of the first process, wherein the first process and the second process are running within the data processing system;

notifying the second process by the resource manager to indicate that another process is waiting for the exclusive, including setting a flag to a predetermined value in a predetermined memory location accessible by the second process, wherein the second process is to periodically poll the predetermined memory location to determine whether another process is waiting for the exclusive lock, wherein in response to the notification, the second process can decide whether to complete or roll back the transactional operation and to release the exclusive lock thereafter;

receiving, by the resource manager, an indication that the second process has released the lock in response to the notification; and

allocating the lock to the first process to allow the first process to access the resource.

8. The non-transitory machine-readable medium of claim 7, wherein the second priority of the second process is increased to at least match the first priority of the first process.

9. The non-transitory machine-readable medium of claim 7, wherein the method further comprises revoking an ownership of the exclusive lock from the second process after a predetermined period of time if the second process has not released the exclusive lock.

10. The non-transitory machine-readable medium of claim 7, wherein notifying the second process comprises rejecting further access of the second process to the resource by returning errors in response to current or future input/output (IO) requests to the resource.

11. The non-transitory machine-readable medium of claim 10, wherein the rejection causes the second process to abort further access of the resource and to release the exclusive lock associated with the resource.

12. The non-transitory machine-readable medium of claim 10, wherein the method further comprises:

performing a rollback operation of the transactional operation on behalf of the second process;

revoking an ownership of the exclusive lock from the second process without waiting for the second process to release the exclusive lock; and

assigning the exclusive lock to the first process.

13. A data processing system, comprising:

a processor; and

a memory storing instructions, which when executed from the memory, cause the processor to

receive at a resource manager of an operating system a request from a first process to acquire an exclusive lock for accessing a resource of the data processing system, the first process having a first priority,

increase by a priority manager a second priority of a second process to reduce total lock hold time, the second process currently in possession of the exclusive lock for performing a transactional operation with the resource, wherein the second priority was lower than the first priority of the first process, wherein the first process and the second process are running within the data processing system,

notify the second process by the resource manager to indicate that another process is waiting for the exclusive lock, including setting a flag to a predetermined value in a predetermined memory location accessible by the second process, wherein the second process is to periodically poll the predetermined memory location to determine whether another process is waiting for the exclusive lock, wherein in response to the second message, the second process can decide whether to complete or roll back the transactional operation and to release the exclusive lock thereafter,

receive, by the resource manager, an indication that the second process has released the lock in response to the notification, and

allocate the lock to the first process to allow the first process to access the resource.

14. The system of claim 13, wherein the second priority of the second process is increased to at least match the first priority of the first process.

15. The system of claim 13, wherein an ownership of the exclusive lock is revoked by the resource manager of the operating system from the second process after a predetermined period of time if the second process has not released the exclusive lock.

16. The system of claim 13, wherein notifying the second process comprises rejecting further access of the second process to the resource by returning errors in response to current or future input/output (IO) requests to the resource.

17. The system of claim 16, wherein the rejection causes the second process to abort further access of the resource and to release the exclusive lock associated with the resource.

18. The system of claim 16, wherein the instructions further cause the processor to:

perform a rollback operation of the transactional operation on behalf of the second process,

revoke an ownership of the exclusive lock from the second process without waiting for the second process to release the exclusive lock, and

assign the exclusive lock to the first process.