Sleep queue management

• US 7,210,146 B2
• Filed: 06/18/2001
• Issued: 04/24/2007
• Est. Priority Date: 06/18/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hsieh, Bor-Ming
• Primary Examiner(s): Thomson; William
• Assistant Examiner(s): WU, QING YUAN
• Application Number:
  US09/884,374
• Publication Number:
  US 20020194250A1
• Time in Patent Office: 2,136 Days
• Field of Search: 710/5, 718102-103
• US Class Current: 718/103
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G06F 9/4825 Interrupt from clock, e.g. time of day
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Various implementations of the described subject matter provide for the management of a multi-dimensional sleep queue, such that a group of threads with a same wake-up time are removed from the multi-dimensional sleep queue in a deterministic amount of time that is independent of the number of threads in the removed group. This is significant because it allows an operating system to schedule other threads for execution within deterministic/predetermined time parameters. Moreover, the described subject matter also provides for inserting new threads into the multi-dimensional sleep queue in a manner that allows other processes to execute during the thread insertion process.

Claims

1. A computer implemented method for managing a multi-dimensional sleep queue, the method comprising:

identifying a thread of execution to insert into the multi-dimensional sleep queue for a predetermined amount of time;

responsive to the identifying, inserting the thread of execution into a first dimension of the multi-dimensional sleep queue if;

(a) there is not a thread with a wake-up time equivalent to the predetermined amount of time in the first dimension; and

(b) if there are one or more different threads of execution with the wake-up time in a second dimension of the multi-dimensional sleep queue, each of the one or more different threads of execution has a thread priority lower than or equal to a thread priority associated with the thread of execution.

2. A computer implemented method as recited in claim 1, wherein the multi-dimensional sleep queue is a real-time multi-dimensional sleep queue.

3. A computer implemented method as recited in claim 1, wherein the multi-dimensional sleep queue is a two-dimensional sleep queue.

4. A computer implemented method as recited in claim 1, wherein inserting the thread of execution into the multi-dimensional sleep queue is performed in a manner that allows the thread scheduling mechanism to schedule other threads for execution within a deterministic amount of time.

5. A computer implemented method as recited in claim 1, wherein inserting the thread of execution into the multi-dimensional sleep queue further comprises inserting the thread of execution into the multi-dimensional sleep queue such that a group of threads can be removed from the multi-dimensional sleep queue in a deterministic amount of time.

6. A computer implemented method as recited in claim 1, wherein the multi-dimensional sleep queue comprises a group of threads, and wherein the method further comprises:

removing the group of threads from the multi-dimensional sleep queue in a deterministic amount of time, each thread in the group having a same wake-up time.

7. A computer implemented method as recited in claim 1,

wherein the predetermined amount of time is a wake-up time, and wherein the thread of execution has a priority;

and

wherein inserting the thread of execution into the multi-dimensional sleep queue further comprises

sorting the thread of execution into the first dimension based on respective thread wake-up times; and

sorting the thread of execution into the second dimension based on respective thread priorities; and

wherein the thread of execution is sorted first with respect to the first dimension and second with respect to the second dimension.

8. A computer implemented method as recited in claim 1, wherein the second dimension comprises a plurality of threads, each thread of the threads having a same respective thread wake-up time.

9. A computer implemented method as recited in claim 7, wherein sorting the thread of execution further comprises:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

concluding that a first priority corresponding to the thread of execution is higher than a second priority corresponding to the different thread; and

replacing the different thread in the first dimension with the thread of execution, such the thread of execution is a member of both the first and the second dimensions, and such that the replaced thread has a secondary position with respect to the first and second dimensions.

10. A computer implemented method as recited in claim 7, wherein sorting the thread of execution further comprises:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

determining that a first priority corresponding to the thread of execution is lower than a second priority that corresponds to the different thread; and

inserting the new thread of execution into the second dimension, such the thread of execution occupies a secondary position with respect to the first and second dimensions and such that any different thread in the second dimension with lower priority than the first priority is subsequent in position to the secondary position.

11. A computer storage medium for managing a multi-dimensional sleep queue, the computer storage medium comprising computer-executable instructions for:

identifying a thread of execution to insert into the multi-dimensional sleep queue for a predetermined amount of time;

responsive to the identifying, inserting the thread of execution into a first dimension of the multi-dimensional sleep queue if;

(a) there is not a thread with a wake-up time equivalent to the predetermined amount of time in the first dimension; and

(b) if there are one or more different threads of execution with the wake-up time in a second dimension of the multi-dimensional sleep queue, each of the one or more different threads of execution has a thread priority lower than or equal to a thread priority associated with the thread of execution.

12. A computer storage medium as recited in claim 11, wherein the multi-dimensional sleep queue is a real-time multi-dimensional sleep queue.

13. A computer storage medium as recited in claim 11, wherein the computer-executable instructions for inserting the thread of execution into the multi-dimensional sleep queue are performed in a manner that allows the thread scheduling mechanism to schedule other threads for execution in a deterministic amount of time.

14. A computer storage medium as recited in claim 11, wherein the computer-executable instructions for inserting the thread of execution into the multi-dimensional sleep queue further comprise instructions for inserting the thread of execution into the multi-dimensional sleep queue such that a group of threads can be removed from the multi-dimensional sleep queue in a deterministic amount of time.

15. A computer storage medium as recited in claim 11, wherein the multi-dimensional sleep queue comprises a group of threads, and wherein the computer-executable instructions further comprise instructions for:

removing the group of threads from the multi-dimensional sleep queue in a deterministic amount of time, each thread in the group having a same wake-up time.

16. A computer storage medium as recited in claim 11, wherein the predetermined amount of time is a wake-up time, and wherein the thread of execution has a priority;

and

wherein the computer-executable instructions for inserting the thread of execution into the multi-dimensional sleep queue further comprise instructions for;

sorting the thread of execution into the second dimension based on respective thread priorities; and

wherein the thread of execution is sorted first with respect to the first dimension and second with respect to the second dimension.

17. A computer storage medium as recited in claim 11, wherein the second dimension comprises a plurality of threads, each thread of the threads having a same respective thread wake-up time.

18. A computer storage medium as recited in claim 11, wherein the thread of execution is a new thread, and wherein the instructions for inserting the thread of execution further comprises instructions for:

determining that the predetermined amount of time is different as compared to each respective wake-up time of each other thread in the first dimension; and

responsive to the determining, introducing the new thread into the first dimension.

19. A computer storage medium as recited in claim 16, wherein the computer-executable instructions for sorting the thread further comprise instructions for:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

concluding that a first priority corresponding to the thread of execution is higher than a second priority corresponding to the different thread; and

replacing the different thread in the first dimension with the thread of execution, such the thread of execution is a member of both the first and the second dimensions, and such that the replaced thread has a secondary position with respect to the first and second dimensions.

20. A computer storage medium as recited in claim 16, wherein the computer-executable instructions for sorting the thread further comprise instructions for:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

determining that a first priority corresponding to the thread of execution is lower than a second priority that corresponds to the different thread; and

inserting the thread of execution into the second dimension, such the thread of execution occupies a secondary position with respect to the first and second dimensions and such that any different thread in the second dimension with lower priority than the first priority is subsequent in position to the secondary position.

21. A system for managing a sleep queue, the system comprising:

a memory comprising computer-executable instructions and a multi-dimensional sleep queue; and

a processor operatively coupled to the memory for executing the computer-executable instructions, the computer-executable instructions comprising instructions for;

identifying a thread of execution to insert into the multi-dimensional sleep queue for a predetermined amount of time;

responsive to the identifying, inserting the thread of execution into a first dimension of the multi-dimensional sleep queue if;

(a) there is not a thread with a wake-up time equivalent to the predetermined amount of time in the first dimension; and

(b) if there are one or more different threads of execution with the wake-up time in a second dimension of the multi-dimensional sleep queue, each of the one or more different threads of execution has a thread priority lower than or equal to a thread priority associated with the thread of execution.

22. A system as recited in claim 21, wherein the multi-dimensional sleep queue is a real-time multi-dimensional sleep queue.

23. A system as recited in claim 21, wherein the instructions for inserting the thread of execution are performed in a manner that allows a thread scheduling mechanism to schedule other threads for execution in a deterministic amount of time.

24. A system as recited in claim 21, wherein the instructions for inserting the thread of execution further comprise instructions for:

inserting the thread of execution into the multi-dimensional sleep queue such that a group of threads can be removed from the multi-dimensional sleep queue in a deterministic amount of time.

25. A system as recited in claim 21, wherein the multi-dimensional sleep queue further comprises a group of threads, and wherein the computer-executable instructions further comprise instructions for:

inserting the group of threads into the multi-dimensional sleep queue; and

removing the group of threads from the multi-dimensional sleep queue in a deterministic amount of time, each thread in the group having a same wake-up time.

26. A system as recited in claim 21, wherein the thread has a wake-up time and a priority, and wherein the instructions for inserting the thread further comprise instructions for:

sorting the thread of execution into the first dimension based on respective thread wake-up times; and

sorting the thread of execution into the second dimension based on respective thread priorities; and

wherein the thread of execution is sorted first with respect to the first dimension and second with respect to the second dimension.

27. A system as recited in claim 26, wherein the second dimension comprises a plurality of threads, each thread of the threads having a same respective thread wake-up time.

28. A system as recited in claim 26, wherein the instructions for sorting the thread of execution further comprise instructions for:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

concluding that a first priority corresponding to the thread of execution is higher than a second priority corresponding to the different thread; and

replacing the different thread in the first dimension with the thread of execution, such the thread of execution is a member of both the first and the second dimensions, and such that the replaced thread has a secondary position with respect to the first and second dimensions.

29. A system as recited in claim 26, wherein the instructions for sorting the thread of execution further comprise instructions for:

identifying a different thread in the first dimension that has a wake-up time equivalent to the predetermined amount of time; and

responsive to identifying the different thread;

determining that a first priority corresponding to the thread of execution is lower than a second priority that corresponds to the different thread; and

inserting the thread of execution into the second dimension, such the thread of execution occupies a secondary position with respect to the first and second dimensions and such that any different thread in the second dimension with lower priority than the first priority is subsequent in position to the secondary position.