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

• US 6,874,144 B1
• Filed: 04/05/1999
• Issued: 03/29/2005
• 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): Sheikh, Ayaz
• Assistant Examiner(s): LAFORGIA, CHRISTIAN A
• Application Number:
  US09/286,173
• Time in Patent Office: 2,185 Days
• Field of Search: 709/108, 709/102, 709/103, 709/104, 709/106, 709/107, 709/100, 713/400
• 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:

providing a first list including a boost request to boost a priority of an indicated thread holding a shared resource to an indicated priority;

providing a second list;

processing the boost request in the first list to boost the priority of the indicated thread to the indicated priority;

removing the processed boost request from the first list and placing the processed boost request in the second list after boosting the priority of the indicated thread to the indicated priority; and

processing one boost request in the second list to adjust the priority of the indicated thread to the indicated priority.

2. The method of claim 1, wherein the first and second lists are capable of including multiple boost requests for a same indicated thread for each shared resource held by the indicated thread, further comprising:

submitting a boost request to boost an indicated thread to an indicated priority;

placing the submitted boost request in the first list after determining that the indicated priority of the submitted boost request is higher than both (a) a current priority of the indicated thread and (b) an indicated priority of a pending boost request in the first list for the indicated thread; and

placing the submitted boost request in the second list if the indicated priority of the submitted boost request is lower than one of (a) the current priority of the indicated thread and (b) the indicated priority of the pending boost request in the first list for the indicated thread.

3. The method of claim 2, further comprising moving the pending boost request in the first list to the second list if the submitted boost request is in the first list.

4. The method of claim 3, further comprising:

releasing, with a thread, the shared resource;

setting the priority of the releasing thread to the indicated priority of a boost request in the first list for a shared resource different from the released shared resource if the first list includes boost requests toward the releasing thread for different shared resources; and

setting the priority of the holding thread to the indicated priority of a boost request in the second list for a shared resource different from the released shared resource if the first list includes no boost requests for the releasing thread and the second list includes boost requests toward the releasing thread for different shared resources moved from the first list to the second list.

5. The method of claim 1, wherein the first list queues boost requests for all threads executing within a process and the second list queues all boost requests for a specific thread executing within the process, wherein there is a second list for each tread holding access to a mutex.

6. The method of claim 1, wherein the boost request in the second list is processed to adjust the priority in response to the indicated thread releasing the shared resource.

7. The method of claim 6, wherein the priority of the indicated thread is adjusted downward when processing the boost request in the second list.

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;

(i) a first list including a boost request to boost a priority of an indicated thread holding a shared resource to an indicated priority; and

(ii) a second list; and

(c) program logic executed by the computer, comprising;

(i) means for processing the boost request in the first list to boost the priority of the indicated thread to the indicated priority;

(ii) means for removing the processed boost request from the first list and placing the processed boost request in the second list after boosting the priority of the indicated thread to the indicated priority; and

(iii) means for processing one boost request in the second list to adjust the priority of the indicated thread to the indicated priority.

9. The system of claim 8, wherein the first and second lists are capable of including multiple boost requests for a same indicated thread for each shared resource held by the indicated thread, wherein the program logic further comprises:

means for submitting a boost request to boost an indicated thread to an indicated priority;

means for queuing the submitted boost request in the first list after determining that the indicated priority of the submitted boost request is higher than both (a) a current priority of the indicated thread and (b) an indicated priority of a pending boost request in the first list for the indicated thread; and

means for queuing the submitted boost request in the second list if the indicated priority of the submitted boost request is lower than one of (a) the current priority of the indicated thread and (b) the indicated priority of the pending boost request in the first list for the indicated thread.

10. The system of claim 9, wherein the program logic further comprises means for moving the pending boost request in the first list to the second list if the submitted boost request is queued in the first list.

11. The system of claim 10, wherein the program logic further comprises:

means for releasing the shared resource;

means for setting the priority of the releasing thread to the indicated priority of a boost request in the first list for a shared resource different from the released shared resource if the first list includes boost requests toward the releasing thread for different shared resources; and

means for setting the priority of the holding thread to the indicated priority of a boost request in the second list for a shared resource different from the released shared resource if the first list includes no boost requests for the releasing thread and the second list includes boost requests toward the releasing thread for different shared resources moved from the first list to the second list.

12. The system of claim 8, wherein the first list queues boost requests for all threads executing within a process and the second list queues all boost requests for a specific thread executing within the process, wherein the memory device further includes a second list for each thread holding access to a mutex.

13. The system of claim 8, wherein the boost request in the second list is processed to adjust the priority in response to the indicated thread releasing the shared resource.

14. The system of claim 13, wherein the priority of the indicated thread is adjusted downward when processing the boost request in the second list.

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:

providing a first list including a boost request to boost a priority of an indicated thread holding a shared resource to an indicated priority;

providing a second list;

processing the boost request in the first list to boost the priority of the indicated thread to the indicated priority;

removing the processed boost request from the first list and placing the processed boost request in the second list after boosting the priority of the indicated thread to the indicated priority; and

processing one boost request in the second list to adjust the priority of the indicated thread to the indicated priority.

16. The article of manufacture of claim 15, wherein the first and second lists are capable of including multiple boost requests for a same indicated thread for each shared resource held by the indicated thread, further causing the computer to perform:

submitting a boost request to boost an indicated thread to an indicated priority;

queuing the submitted boost request in the first list after determining that the indicated priority of the submitted boost request is higher than both (a) a current priority of the indicated thread and (b) an indicated priority of a pending boost request in the first list for the indicated thread; and

queuing the submitted boost request in the second list if the indicated priority of the submitted boost request is lower than one of (a) the current priority of the indicated thread and (b) the indicated priority of the pending boost request in the first list for the indicated thread.

17. The article of manufacture of claim 16, further causing the computer to perform moving the pending boost request in the first list to the second list if the submitted boost request is queued in the first list.

18. The article of manufacture of claim 17, further causing the computer to perform:

releasing, with a thread, the shared resource;

setting the priority of the releasing thread to the indicated priority of a boost request in the first list for a shared resource different from the released shared resource if the first list includes boost requests toward the releasing thread for different shared resources; and

setting the priority of the holding thread to the indicated priority of a boost request in the second list for a shared resource different from the released shared resource if the first list includes no boost requests for the releasing thread and the second list includes boost requests toward the releasing thread for different shared resources moved from the first list to the second list.

19. The article of manufacture of claim 15, wherein the first list queues boost requests for all threads executing within a process and the second list queues all boost requests for a specific thread executing within the process, and wherein there is a second list for each thread holding access to a mutex.

20. The article of manufacture of claim 15, wherein the boost request in the second list is processed to adjust the priority in response to the indicated thread releasing the shared resource.

21. The article of manufacture of claim 20, wherein the priority of the indicated thread is adjusted downward when processing the boost request in the second list.