Dynamically variable idle time thread scheduling

• US 20020007387A1
• Filed: 04/25/2001
• Published: 01/17/2002
• Est. Priority Date: 06/02/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ginsberg, Michael
• Granted Patent: US 7,137,117 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 1/3228 Monitoring task completion, e.g. by use of idle timers, stop commands or wait commands
• CPC Class Codes: G06F 1/329 by task scheduling
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 9/44573 Execute-in-place [XIP]
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

The subject matter provides dynamically variable idle time thread scheduling in a device with a high system tick rate. A device based on the subject matter includes an operating system, a set of application program modules, and one or more hardware elements. A thread scheduling mechanism in the operating system schedules threads at a periodic rate. Upon determining that there are no threads to execute, at least a subset of components are deactivated for a dynamic variable amount of time before they are is re-activated. The at least one subset of components are selected from the hardware elements, one or more program modules comprising the operating system, and the like. The dynamic variable amount of time is independent of the periodic rate and based on a sleep state of a set of threads in a sleep queue.

Claims

1. A method for providing thread scheduling in a device, the device comprising one or more hardware elements operatively coupled to an operating system comprising a plurality of program modules, the method comprising:

scheduling one or more threads according to a predetermined periodic rate;

determining whether or not there are any threads to execute; and

responsive to a determination that there are no threads to execute, deactivating at least one subset of components for a dynamic variable amount of time, the one subset being selected from a group of components comprising the hardware elements and the program modules, the dynamic variable amount of time being independent of the predetermined periodic rate and being based on a sleep state of a set of threads in a sleep queue.

2. A method as recited in claim 1, wherein the dynamic variable amount of time is based on a maximum amount of time that a thread can yield before needing to be scheduled for execution.

3. A method as recited in claim 1, wherein the device is a battery powered device.

4. A method as recited in claim 1, wherein the operating system comprises an operating system selected from a group of operating systems comprising Microsoft WINDOWS CE, Linux, WindRiver, QNX, or PALM operating systems.

5. A method as recited in claim 1, wherein the scheduling, the predetermined periodic rate is a millisecond.

6. A method as recited in claim 1:

wherein the providing further comprises setting a system timer to generate a notification at the predetermined periodic rate;

wherein the deactivating further comprises resetting the system timer to generate the notification after the dynamic variable amount of time has elapsed since the deactivating; and

wherein the method further comprises;

receiving the notification after the dynamic variable amount of time has elapsed since the deactivating; and

responsive to the receiving;

resetting the system timer to generate the notification at the predetermined periodic rate; and

activating the at least one subset of components.

7. One or more computer-readable media containing a computer executable program that performs a method as recited in claim 1.

8. A method for providing thread scheduling in a device, the device comprising one or more hardware elements operatively coupled to an operating system comprising a plurality of program modules, the method comprising:

scheduling one or more threads at a predetermined periodic rate;

determining whether or not there are any threads to execute; and

responsive to a determination that there are no threads to execute, deactivating at least one subset of components for a dynamic variable amount of time, the one subset being selected from a group of components comprising the hardware elements and the program modules, the dynamic variable amount of time being based on a sleep state of the a set of threads in a sleep queue and independent of the predetermined periodic rate; and

activating the one subset of components only when the operating system needs to perform an action selected from a group of actions comprising scheduling a thread for execution upon expiration of the dynamic variable amount of time since the deactivating, or upon receipt of an external event, processing the external event, wherein the external event is not a system timer event.

9. A method as recited in claim 8, wherein the device comprises a battery powered device.

10. A method as recited in claim 8, wherein the operating system comprises a Microsoft WINDOWS CE operating system.

11. A method as recited in claim 8, wherein the scheduling, the predetermined periodic rate is a millisecond.

12. A method as recited in claim 8:

wherein the scheduling further comprises setting a system timer to the predetermined periodic rate, the predetermined periodic rate corresponding to a thread scheduling accuracy; and

wherein the deactivating further comprises resetting the system timer to generate a notification after the dynamic variable amount of time has elapsed since the deactivating.

13. A method as recited in claim 8:

wherein the deactivating further comprises resetting a system timer to generate a notification after the dynamic variable amount of time has elapsed, the dynamic variable amount of time being a maximum amount of time that a thread can yield to other threads before needing to be scheduled for execution; and

wherein the activating further comprises resetting the system timer to the predetermined periodic rate to provide substantial thread scheduling accuracy.

14. One or more computer-readable media containing a computer executable program that performs a method as recited in claim 8.

15. A computer-readable storage medium containing computer-executable instructions for scheduling threads in a device, the device including an operating system comprised of a plurality of program modules that are in turn coupled to one or more hardware elements, the computer-executable instructions comprising instructions for:

determining at a periodic rate whether or not there are any threads to execute; and

responsive to a determination that there are no threads to execute, deactivating at least one subset of components for a dynamic variable amount of time, the at least one subset being selected from a group of components comprising the one or more of the program modules and one or more of the hardware elements, the dynamic variable amount of time being independent of the periodic rate, the dynamic variable amount of time being based on a sleep state of a set of threads in a sleep queue.

16. A computer-readable storage medium as recited in claim 15, wherein the dynamic variable amount of time comprises a maximum amount of time that a thread has specified that it will yield to other threads before it needs to be scheduled for execution.

17. A computer-readable storage medium as recited in claim 15, wherein the device comprises a battery powered device.

18. A computer-readable storage medium as recited in claim 15, wherein the operating system comprises a Microsoft WINDOWS CE operating system.

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

in the deactivating, configuring a system timer to send a first timer interrupt after the dynamic variable amount of time has elapsed, the dynamic variable amount of time being a maximum amount of time that a first thread can yield to a second thread before the first thread needs to be executed; and

responsive to receiving the first timer interrupt;

(a) configuring the system timer to send a second timer interrupt at the periodic rate; and

(b) activating the deactivated at least one subset of components to determine if there are any threads to execute.

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

receiving an external interrupt before the dynamic variable amount of time has elapsed since the deactivating, the external interrupt not being a system timer interrupt; and

responsive to receiving the external interrupt, processing the external interrupt such that the at least one subset of components remain deactivated for the dynamic variable amount of time.

21. A computer comprising one or more computer-readable media as recited in claim 15.

22. A device comprising:

a processor configured to fetch and execute a plurality of computer-executable instructions;

a plurality of hardware elements coupled to the processor; and

,

a memory coupled to the processor for storing the computer-executable instructions comprising a scheduler program module, a hardware abstraction layer (HAL) program module, one or more operating system program modules, and a set of application program modules;

wherein the scheduler comprises computer-executable instructions for;

scheduling threads for execution at a periodic time interval; and

determining that there are no threads to execute;

wherein the HAL, responsive to the determining, comprises computer-executable instructions for deactivating, for a dynamic variable amount of time, at least one subset of components selected from a group of components comprising the scheduler, the hardware elements, the one or more operating system program modules, and the application program modules, the dynamic variable amount of time being independent of the periodic time interval and being based on a sleep state of a set of threads in a sleep queue.

23. A device as recited in claim 22, wherein the dynamic variable amount of time is based on a maximum amount of time that a thread can yield before needing to be scheduled.

24. A device as recited in claim 22, wherein the periodic time interval is a millisecond.

25. A device as recited in claim 22, wherein the device comprises a battery powered device.

26. A device as recited in claim 22, wherein the operating system is an operating system selected from a group of operating systems comprising Microsoft WINDOWS CE, Linux, WindRiver, QNX, or Palm®

operating systems.

27. A device as recited in claim 22, wherein the HAL further comprises computer-executable instructions for re-activating the at least one subset of components after the dynamic variable amount of time has elapsed since the at least one subset of components were deactivated.

28. A device as recited in claim 27, wherein the scheduler is re-activated in a manner that allows the scheduler to schedule threads based on the periodic time interval.

29. A device as recited in claim 22, wherein after the scheduler is deactivated, the HAL further comprises computer-executable instructions for receiving a notification in response to an external event, the external event not being a system timer event, responsive to receipt of the notification, the HAL processing the notification in a manner that the scheduler remains deactivated for the dynamic variable amount of time.