Efficient mechanism for preventing starvation in counting semaphores

• US 20060206897A1
• Filed: 03/08/2005
• Published: 09/14/2006
• Est. Priority Date: 03/08/2005
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: McConnell, Marcia E.
• Granted Patent: US 7,984,439 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

An algorithm for preventing starving threads in a counting semaphore for a computer operating system. The algorithm operates in a stealing mode where threads can steal resources from other threads if none of the threads is starving, and operates in a first-in first-out mode if one or more of the threads becomes starving.

Claims

1. A method for allocating resources to threads in a counting semaphore, said method comprising:

maintaining a count of how many of the resources the semaphore currently has available for the threads;

putting threads to sleep on a wait queue if the semaphore does not have enough of the resources available to satisfy a thread;

waking a thread up from the wait queue if resources become available for the thread;

allowing other threads to steal resources from the woken threads before the woken threads can execute; and

allowing a starving thread to be woken and execute if the starving thread has had more than a predetermined maximum number of resources stolen from it.

2. The method according to claim 1 further comprising returning to allowing threads to steal resources when the starving thread uses the resources.

3. The method according to claim 1 further comprising allowing other threads to steal resources from a sleeping thread at a front of the wait queue if the sleeping thread needs a plurality of resources and the semaphore has fewer resources available than the sleeping thread needs.

4. The method according to claim 3 further comprising determining whether a resource is stolen from a thread at the front of the wait queue or a thread that has been woken up from the wait queue and is waiting to execute.

5. The method according to claim 1 further comprising maintaining a count of how many resources are needed by the threads that have been woken from the wait queue and are waiting to execute.

6. The method according to claim 5 further comprising waking up a thread at a front of the wait queue only if the number of resources that the semaphore has is enough to satisfy all of the threads that have been woken, but have not executed, and the thread at the front of the wait queue.

7. The method according to claim 1 further comprising maintaining a count of how many resources the sleeping threads and the woken threads have attempted to get from the semaphore, but have failed.

8. The method according to claim 1 further comprising maintaining a count of the number of resources that are stolen from a thread to determine if the thread is starving.

9. The method according to claim 1 further comprising maintaining a count of the number of threads that are starving.

10. The method according to claim 1 wherein allowing a starving thread to be woken and execute includes putting the starving thread at a front of the wait queue.

11. The method according to claim 1 wherein the method is used in a computer operating system.

12. The method according to claim 11 wherein the operating system is a UNIX operating system.

13. A method for allocating resources to threads in a counting semaphore, said method comprising:

operating in a stealing mode where threads can steal resources from other threads if none of the threads is starving; and

operating in a first-in first-out mode if one or more of the threads are starving.

14. The method according to claim 13 wherein operating in a stealing mode includes allowing other threads to steal resources from a woken thread that was previously sleeping on a wait queue before the woken thread can execute.

15. The method according to claim 13 wherein operating in a stealing mode includes allowing other threads to steal resources from a sleeping thread at a front of a wait queue if the sleeping thread needs a plurality of resources and the semaphore has less resources than the sleeping thread needs.

16. The method according to claim 13 further comprising maintaining a count of how many resources sleeping threads on a wait queue and woken threads have attempted to get from the semaphore, but have failed.

17. The method according to claim 13 further comprising maintaining a count of the number of resources that are stolen from a thread to determine if the thread is starving.

18. The method according to claim 13 further comprising putting a starving thread at the front of a wait queue.

19. A method for allocating resources to threads in a counting semaphore, said method comprising:

maintaining a count of how many of the resources the semaphore currently has available for the threads;

putting threads to sleep on a wait queue if the semaphore does not have enough of the resources available to satisfy a thread;

waking a thread up from the wait queue if resources become available for the thread;

maintaining a count of how many resources are needed by the threads that have been woken from the wait queue and are waiting to execute;

maintaining a count of how many resources the sleeping threads and the woken threads have attempted to get from the semaphore, but have failed;

allowing other threads to steal resources from the woken thread before the woken thread can execute;

allowing other threads to steal resources from a thread sleeping at a front of the wait queue if the sleeping thread needs a plurality of resources and the semaphore has fewer resources available than the sleeping thread needs;

maintaining a count of the number of resources that are stolen from a thread to determine if the thread is starving;

allowing a starving thread to be woken and execute if the starving thread has had more than a predetermined number of resources stolen from it, wherein allowing a starving thread to be woken and execute includes putting the starving thread at the front of the wait queue; and

returning to allowing threads to steal resources when the starved thread uses the resources.

20. The method according to claim 19 further comprising waking up a thread at the front of the wait queue only if the number of resources that the semaphore has available is enough to satisfy all of the threads that have been woken, but have not executed, and the thread at the front of the wait queue.

21. The method according to claim 19 further comprising maintaining a count of the number of threads that are starving.