System, method and program for implementing priority inheritance in an operating system

• US 7,752,621 B2
• Filed: 09/15/2004
• Issued: 07/06/2010
• Est. Priority Date: 04/05/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kush, Christopher Starbuck
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Arcos; Caroline
• Application Number:
  US10/942,652
• Publication Number:
  US 20050060710A1
• Time in Patent Office: 2,120 Days
• Field of Search: 718/103, 718/102, 718/104, 718/100
• US Class Current: 718/103
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

Disclosed is a method, system, and program for implementing priority inheritance in an operating system. A first list includes a boost request to boost a priority of an indicated thread holding a shared resource to an indicated priority. Further included is a second list. The system processes the boost request in the first list to boost the priority of the indicated thread to the indicated priority. After boosting priority, the system removes the processed boost request from the first list and places the processed boost request in the second list.

Claims

1. A method for implementing priority inheritance in an operating system, comprising:

receiving a request for a shared resource, comprising a mutex, from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether a list includes a boost request to boost the priority of the second thread, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list includes at least one boost request for the second thread for at least one mutex the second thread holds;

generating a boost request to boost the priority of the second thread to the first priority in response to determining that the list does not include one boost request;

modifying one boost request in the list to boost the priority of the second thread to the first priority in response to determining that the list includes one boost request;

submitting the generated boost request in response to generating the boost request; and

submitting the modified boost request in response to modifying the boost request.

2. The method of claim 1, wherein the first thread is executing in a first process and the second thread is executing in a second process.

3. The method of claim 1, wherein the submitting of the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

placing the submitted boost request on the list in response to determining that the priority of the submitted boost request exceeds the current priority of the second thread.

4. A method for implementing priority inheritance in an operating system, comprising:

receiving a request for a shared resource from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether a restore list includes a boost request to boost the priority of the second thread;

determining whether a pending list includes a boost request to boost the priority of the second thread in response to determining that the restore list does not include a boost request;

generating a boost request to boost the priority of the second thread to the first priority occurs in response to determining that the pending and restore lists do not include one boost request to boost the priority of the second thread;

submitting the generated boost request in response to generating the boost request;

modifying one boost request in the restore list to boost the priority of the second thread to the first priority in response to determining that the restore list includes one boost request;

submitting the modified boost request in the restore list and removing the modified boost request from the restore list in response to modifying the boost request; and

modifying the boost request in the pending list to boost the priority of the second thread to the first priority in response to determining that the pending list includes the boost request.

5. The method of claim 4, wherein the submitting of the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

placing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

6. The method of claim 5, further comprising:

determining whether there is a pending boost request for the second thread in the pending list in response to determining that the priority of the submitted boost request exceeds the current priority of a holding thread;

queuing the submitted boost request in the pending list in response to determining that there is no pending boost request for the second thread in the pending list;

determining whether the priority of the submitted boost request exceeds a priority for the pending boost request in the pending list;

placing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the priority of the pending boost request; and

moving the pending boost request to the restore list and queuing the submitted boost request in response to determining that the priority of the submitted boost request exceeds the priority of the pending boost request.

7. A system for implementing priority inheritance, comprising:

a computer system including an operating system, wherein multiple processes including multiple threads are capable of executing within the operating system;

a memory device accessible to the computer system, including a list;

program logic executed by the computer system to cause the computer system to perform;

receiving a request for a shared resource comprising a mutex from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether the list includes a boost request to boost the priority of the second thread, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list includes at least one boost request for the second thread for at least one mutex the second thread holds;

generating a boost request to boost the priority of the second thread to the first priority in response to determining that the list does not include one boost request;

modifying one boost request in the list to boost the priority of the second thread to the first priority in response to determining that the list includes the boost request;

submitting the generated boost request in response to generating the boost request; and

submitting the modified boost request in response to modifying the boost request.

8. The system of claim 7, wherein the first thread is executing in a first process and the second thread is executing in a second process.

9. The system of claim 7, wherein submitting the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

queuing the submitted boost request on the list in response to determining that the priority of the submitted boost request exceeds the current priority of the second thread.

10. A system for implementing priority inheritance, comprising:

a computer system including an operating system, wherein multiple processes including multiple threads are capable of executing within the operating system;

a memory device accessible to the computer system, including a restore list and a pending list;

program logic executed by the computer system to cause the computer system to perform;

receiving a request for a shared resource from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether the restore list includes a boost request to boost the priority of the second thread;

determining whether the pending list includes a boost request to boost the priority of the second thread in response to determining that the restore list does not include the boost request;

generating a boost request to boost the priority of the second thread to the first priority occurs in response to determining that the restore and pending lists do not include the boost request to boost the priority of the second thread;

submitting the generated boost request in response to generating the boost request;

modifying one boost request in the restore list to boost the priority of the second thread to the first priority in response to determining that the restore list includes one boost request;

submitting the modified boost request in the restore list and removing the modified boost request from the restore list in response to modifying the boost request; and

modifying the boost request in the pending list to boost the priority of the second thread to the first priority in response to determining that the pending list includes the boost request.

11. The system of claim 10, wherein submitting the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

queuing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

12. The system of claim 11, wherein the program logic is further enabled to cause the computer system to perform:

determining whether there is a pending boost request for the second thread in the pending list in response to determining that the priority of the submitted boost request exceeds the current priority of a holding thread;

queuing the submitted boost request in the pending list occurs in response to determining that there is no pending boost request for the second thread in the pending list;

determining whether the priority of the submitted boost request exceeds a priority for the pending boost request in the pending list;

queuing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the priority of the pending boost request; and

moving the pending boost request to the first list and queuing the submitted boost request in response to determining that the priority of the submitted boost request exceeds the priority of the pending boost request.

13. An article of manufacture comprising a computer readable storage having code executed by a computer to implement priority inheritance by performing operations the operations comprising:

receiving a request for a shared resource, comprising a mutex, from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether a list includes a boost request to boost the priority of the second thread, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list includes at least one boost request for the second thread for at least one mutex the second thread holds;

generating a boost request to boost the priority of the second thread to the first priority in response to determining that the list does not include one boost request;

modifying one boost request in the list to boost the priority of the second thread to the first priority in response to determining that the list includes the boost request;

submitting the generated boost request in response to generating the boost request; and

submitting the modified boost request in response to modifying the boost request.

14. The article of manufacture of claim 13, wherein the first thread is executing in a first process and the second thread is executing in a second process.

15. The article of manufacture of claim 13, wherein causing the computer to submit the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

queuing the submitted boost request on the list in response to determining that the priority of the submitted boost request exceeds the current priority of the second thread.

16. An article of manufacture comprising a computer storage having code executed by a computer to implement priority inheritance by performing operation, the operations comprising:

receiving a request for a shared resource from a first thread executing at a first priority, wherein the shared resource is held by a second thread that is executing at a second priority, wherein the second priority is less than the first priority;

determining whether a restore list includes a boost request to boost the priority of the second thread;

determining whether a pending list includes a boost request to boost the priority of the second thread in response to determining that the restore list does not include the boost request;

generating a boost request to boost the priority of the second thread to the first priority occurs in response to determining that the restore and pending lists do not include the boost request to boost the priority of the second thread;

submitting the generated boost request in response to generating the boost request;

modifying one boost request in the restore list to boost the priority of the second thread to the first priority in response to determining that the restore list includes one boost request;

submitting the modified boost request in the restore list and removing the modified boost request from the restore list in response to modifying the boost request; and

modifying the boost request in the pending list to boost the priority of the second thread to the first priority in response to determining that the pending list includes the boost request.

17. The article of manufacture of claim 16, wherein causing the computer to submit the boost request comprises:

determining whether the priority of the submitted boost request exceeds a current priority of the second thread; and

queuing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

18. The article of manufacture of claim 17, wherein the computer program further causes the computer to perform:

determining whether there is a pending boost request for the second thread in the pending list in response to determining that the priority of the submitted boost request exceeds the current priority of a holding thread;

queuing the submitted boost request in the pending list occurs in response to determining that there is no pending boost request for the second thread in the pending list;

determining whether the priority of the submitted boost request exceeds a priority for the pending boost request in the pending list;

queuing the submitted boost request in the restore list in response to determining that the priority of the submitted boost request does not exceed the priority of the pending boost request; and

moving the pending boost request to the restore list and queuing the submitted boost request in response to determining that the priority of the submitted boost request exceeds the priority of the pending boost request.