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

• US 20050060710A1
• Filed: 09/15/2004
• Published: 03/17/2005
• Est. Priority Date: 04/05/1999
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kush, Christopher Starbuck
• Granted Patent: US 7,752,621 B2
• Time in Patent Office: Days
• 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 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;

generating a boost request to boost the priority of the second thread to the first priority after 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 shared resource is a mutex, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list is capable of including multiple boost requests for the second thread for each mutex the second thread holds.

4. The method of claim 1, wherein the step of submitting 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 after determining that the priority of the submitted boost request exceeds the current priority of the second thread.

5. The method of claim 1, wherein the list is a restore list, further comprising:

determining whether a pending list includes a boost request to boost the priority of the second thread after determining that the restore list does not include a boost request, wherein the operation of generating the boost request to boost the priority of the second thread to the first priority occurs after determining that the pending and restore lists do not include one boost request to boost the priority of the second thread; and

modifying the boost request in the pending list to boost the priority of the second thread to the first priority after determining that the pending list includes the boost request, wherein the operation of submitting the modified boost request in the restore list comprises submitting the boost request modified in the restore list and removing the modified boost request from the restore list.

6. The method of claim 5, wherein the step of submitting 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 after determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

7. The method of claim 6, further comprising:

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

queuing the submitted boost request in the restore list after 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 after 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 after determining that the priority of the submitted boost request exceeds the priority of the pending boost request.

8. A system for implementing priority inheritance, comprising:

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

(b) a memory device accessible to the computer system, including a queue;

(c) program logic executed by the computer system to cause the computer system to perform;

(i) 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;

(ii) determining whether a list includes a boost request to boost the priority of the second thread;

(iii) generating a boost request to boost the priority of the second thread to the first priority after determining that the list does not include one boost request;

(iv) 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;

(v) submitting the generated boost request in response to generating the boost request; and

(vi) submitting the modified boost request in response to modifying the boost request.

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

10. The system of claim 8, wherein the shared resource is a mutex, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list is capable of including multiple boost requests for the second thread for each mutex the second thread holds.

11. The system of claim 8, 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 after determining that the priority of the submitted boost request exceeds the current priority of the second thread.

12. The system of claim 8, wherein the list is a restore list, wherein the memory further includes a pending list, and wherein the program logic is further enabled to cause the computer system to perform:

determining whether a pending list includes a boost request to boost the priority of the second thread after determining that the restore list does not include a boost request, wherein the operation of generating the boost request to boost the priority of the second thread to the first priority occurs after determining that the restore and pending lists do not include the boost request to boost the priority of the second thread; and

modifying the boost request in the pending list to boost the priority of the second thread to the first priority after determining that the pending list includes the boost request, wherein the operation of submitting the modified boost request in the restore list comprises submitting the boost request modified in the restore list and removing the modified boost request from the restore list.

13. The system of claim 12, 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 after determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

14. The system of claim 13, 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 after determining that the priority of the submitted boost request exceeds the current priority of the holding thread;

queuing the submitted boost request in the restore list occurs after 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 after 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 after determining that the priority of the submitted boost request exceeds the priority of the pending boost request;

15. An article of manufacture for use in programming a computer to implement priority inheritance, the article of manufacture comprising computer usable media including at least one computer program embedded therein that causes the computer 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 a list includes a boost request to boost the priority of the second thread;

generating a boost request to boost the priority of the second thread to the first priority after 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.

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

17. The article of manufacture of claim 15, wherein the shared resource is a mutex, wherein one boost request is maintained for a particular thread holding a particular mutex, wherein the list is capable of including multiple boost requests for the second thread for each mutex the second thread holds.

18. The article of manufacture of claim 15, 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 after determining that the priority of the submitted boost request exceeds the current priority of the second thread.

19. The article of manufacture of claim 15, wherein the list is a restore list, wherein the computer program further causes the computer to perform:

determining whether a pending list includes a boost request to boost the priority of the second thread after determining that the restore list does not include a boost request, wherein the operation of 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 a boost request to boost the priority of the second thread; 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, wherein the operation of submitting the modified boost request in the restore list comprises submitting the boost request modified in the restore list and removing the modified boost request from the restore list.

20. The article of manufacture of claim 19, 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 after determining that the priority of the submitted boost request does not exceed the current priority of the second thread.

21. The article of manufacture of claim 20, 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 after determining that the priority of the submitted boost request exceeds the current priority of the holding thread;

queuing the submitted boost request in the restore list occurs after 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 after 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 after determining that the priority of the submitted boost request exceeds the priority of the pending boost request;