Efficient mechanism for preventing starvation in counting semaphores

• US 7,984,439 B2
• Filed: 03/08/2005
• Issued: 07/19/2011
• Est. Priority Date: 03/08/2005
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: McConnell, Marcia E.
• Primary Examiner(s): Puente; Emerson C
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US11/075,118
• Publication Number:
  US 20060206897A1
• Time in Patent Office: 2,324 Days
• Field of Search: 718/100
• US Class Current: 718/100
• 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 computer-implemented method for allocating a plurality of resources to a plurality of threads in a counting semaphore that protects the plurality of resources, said method comprising:

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

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

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

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

allowing a starving one of the threads to be woken and execute if the starving one of the threads has had more than a predetermined maximum number of the protected resources stolen from it;

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

maintaining a count of the number of the protected resources that are stolen from one of the threads to determine if the thread is starving.

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

3. The method according to claim 1 further comprising determining whether one of the protected resources is stolen from one of the threads at the front of the wait queue or from one of the threads that has been woken up from the wait queue and is waiting to execute.

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

5. The method according to claim 4 further comprising waking up one of the threads at a front of the wait queue only if the number of protected 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.

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

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

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

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

10. The method according to claim 9 wherein the operating system is a UNIX operating system.

11. A computer-implemented method for allocating a plurality of resources to a plurality of threads in a counting semaphore that protects the plurality of resources, said method comprising:

operating in a stealing mode where one of the threads can steal the protected resources from the other threads when none of the threads is starving for any of the protected resources, wherein operating in the stealing mode includes allowing threads to steal the protected resources from a sleeping one of the threads on a wait queue if the sleeping thread needs more than one of the protected resources and the semaphore has less of the protected resources than the sleeping thread needs;

operating in a first-in first-out mode when one or more of the threads are starving for any of the protected resources; and

maintaining a count of the number of the protected resources that are stolen from one of the threads to determine if the thread is starving.

12. The method according to claim 11 wherein operating in the stealing mode includes allowing threads to steal the protected resources from a woken one of the threads that was previously sleeping on a wait queue before the woken one of the threads can execute.

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

14. The method according to claim 11 further comprising putting a starving one of the threads at the front of a wait queue.

15. A computer-implemented method for allocating a plurality of resources to a plurality of threads in a counting semaphore that protects the plurality of resources, said method comprising:

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

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

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

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

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

allowing other ones of the threads to steal the protected resources from a particular woken one of the threads before the particular woken one of the threads can execute;

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

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

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

returning to allowing the threads to steal the protected resources when the starved one of the threads uses the protected resources.

16. The method according to claim 15 further comprising waking up one of the threads at the front of the wait queue only if the number of the protected 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.

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