Detecting Full-System Idle State In Adaptive-Tick Kernels

• US 20140380084A1
• Filed: 06/20/2014
• Published: 12/25/2014
• Est. Priority Date: 06/20/2013
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Granted Patent: US 9,519,307 B2
• Time in Patent Office: Days
• US Class Current: 713/502
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: G06F 1/3206 Monitoring of events, devices or parameters that trigger a change in power modality
• CPC Class Codes: G06F 1/3237 by disabling clock generation or distribution
• 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

A technique for detecting full-system idle state in an adaptive-tick kernel includes detecting non-timekeeping CPU idle state, initiating a hysteresis period, waiting for the hysteresis period to end, manipulating a data structure whose state indicates whether a scheduling clock tick may be disabled on all CPUs, and disabling the scheduling clock tick if the data structure is in an appropriate state. In a first embodiment, non-timekeeping CPUs manipulate a global counter when entering an idle state, but add hysteresis to avoid thrashing the counter. Timekeeping is turned off based on the count maintained on the global counter. In a second embodiment, a Read-Copy Update (RCU) dynticks-idle subsystem running on a timekeeping CPU manipulates a global state variable whose states indicate whether all non-timekeeping CPUs are in an idle state, and if so, for how long. Timekeeping is turned off based on the state of the global state variable.

Claims

1. In a computer system having plural CPUs, including a timekeeping CPU and one or more non-timekeeping CPUs, operatively coupled to one or more memory devices, said system running an adaptive tick kernel, a method for detecting full-system idle state in said adaptive-tick kernel, comprising detecting a non-timekeeping CPU idle state, initiating a hysteresis period, waiting for said hysteresis period to end, manipulating a data structure whose state indicates whether a scheduling clock tick may be disabled on all of said CPUs, and disabling said scheduling clock tick on all of said CPUs if said data structure is determined to be in an appropriate state.

2. The method of claim 1, wherein:

said detecting a non-timekeeping CPU idle state comprises each non-timekeeping CPU detecting it is ready to enter an idle state;

said initiating a hysteresis period comprises each non-timekeeping CPU setting a timer, then entering said idle state;

said waiting for said hysteresis period to end comprises each non-timekeeping CPU remaining in said idle state until it is awakened by said timer;

said manipulating a data structure comprises each non-timekeeping CPU decrementing a global counter if it remained in said idle state for said hysteresis period, then returning to said idle state indefinitely; and

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global counter having been decremented to a predetermined value indicating that all of said non-timekeeping CPUs have remained in said idle state for at least said hysteresis period.

3. The method of claim 1, wherein:

said detecting a non-timekeeping CPU idle state comprises said timekeeping CPU detecting that all said non-timekeeping CPUs are in said idle state;

said initiating a hysteresis period and said waiting for said hysteresis period to end use a global state variable that indicates whether or not all of said non-timekeeping CPUs are in an idle state, and if so, for how long;

said global state variable being configured to store a first state indicating that at least one non-timekeeping CPU is in a non-idle state, a second state indicating that all of said non-timekeeping CPUs have been in an idle state for a relatively short time period, a third state indicating that all of said non-timekeeping CPUs have been in an idle state long enough that said global state variable may be changed without danger of excessive memory contention, a fourth state indicating that all of said non-timekeeping CPUs have been in an idle state long enough to warrant turning off said scheduling clock tick, and a fifth state indicating that said timekeeping CPU has noted said fourth state and turned off said scheduling clock tick on all of said CPUs;

said initiating a hysteresis period comprises first and second hysteresis initiating operations;

said waiting for said hysteresis period to end comprises first and second hysteresis period waiting operations;

said first hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said first state to said second state, and performing a calculation to determine a first delay period for transition of said global state variable from said second state to said third state;

said first hysteresis period waiting operation comprises said timekeeping CPU waiting until said first delay period has elapsed;

said second hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said second state to said third second state, and performing a calculation to determine a second delay period for transition of said global state variable from said third state to said fourth state;

said second hysteresis period waiting operation comprises said timekeeping CPU waiting until said second delay period has elapsed;

said manipulating a data structure comprises said timekeeping CPU transitioning said global state variable from said third state to said fourth state after said second said delay period has elapsed;

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global state variable being in said fourth state, and includes said timekeeping CPU transitioning said global state variable from said fourth state to said fifth state, then disabling the scheduling clock tick.

4. The method of claim 3, wherein said global state variable is maintained as part of a Read-Copy Update (RCU) dyntick-idle subsystem, and state transitions of said global state variable between said first state, said second state and said third state are performed by an RCU grace period tracking kthread running on said timekeeping CPU.

5. The method of claim 4, wherein said non-timekeeping CPUs record their entry into idle state using a per-CPU idle state variable, and said RCU dyntick-idle subsystem checks said per-CPU idle state variables and transitions said global state variable from said first state to said second state if each non-timekeeping CPU has set its per-CPU idle state variable to indicate said idle state.

6. The method of claim 3, wherein said calculations to determine said first and second delay periods are based on a number of said CPUs, and if said number of CPUs exceeds a threshold, a rate of said scheduling clock tick and an RCU leaf fanout size.

7. The method of claim 3, wherein said scheduling clock tick is restored by one of said non-timekeeping CPUs awakening out of its idle state, checking said global state variable, transitioning said global state variable to said first state if it was in any of said third through fifth states, and sending an inter-processor interrupt to said timekeeping CPU if said global state variable is in said fifth state.

8. A system, comprising:

plural CPUs, including a timekeeping CPU and one or more non-timekeeping CPUs;

one or more memory devices coupled to said CPUs, said memory devices including a computer readable storage medium tangibly embodying at least one program of instructions executable by said CPUs to implement an adaptive tick kernel, and operations for detecting full-system idle state in said adaptive-tick kernel, said operations comprising detecting a non-timekeeping CPU idle state, initiating a hysteresis period, waiting for said hysteresis period to end, manipulating a data structure whose state indicates whether a scheduling clock tick may be disabled on all of said CPUs, and disabling said scheduling clock tick on all of said CPUs if said data structure is determined to be in an appropriate state.

9. The system of claim 8, wherein:

said detecting a non-timekeeping CPU idle state comprises each non-timekeeping CPU detecting it is ready to enter an idle state;

said initiating a hysteresis period comprises each non-timekeeping CPU setting a timer, then entering said idle state;

said waiting for said hysteresis period to end comprises each non-timekeeping CPU remaining in said idle state until it is awakened by said timer;

said manipulating a data structure comprises each non-timekeeping CPU decrementing a global counter if it remained in said idle state for said hysteresis period, then returning to said idle state indefinitely; and

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global counter having been decremented to a predetermined value indicating that all of said non-timekeeping CPUs have remained in said idle state for at least said hysteresis period.

10. The system of claim 8, wherein:

said detecting a non-timekeeping CPU idle state comprises said timekeeping CPU detecting that all said non-timekeeping CPUs are in said idle state;

said initiating a hysteresis period and said waiting for said hysteresis period to end use a global state variable that indicates whether or not all of said non-timekeeping CPUs are in an idle state, and if so, for how long;

said global state variable being configured to store a first state indicating that at least one non-timekeeping CPU is in a non-idle state, a second state indicating that all of said non-timekeeping CPUs have been in an idle state for a relatively short time period, a third state indicating that all of said non-timekeeping CPUs have been in an idle state long enough that said global state variable may be changed without danger of excessive memory contention, a fourth state indicating that all of said non-timekeeping CPUs have been in an idle state long enough to warrant turning off said scheduling clock tick, and a fifth state indicating that said timekeeping CPU has noted said fourth state and turned off said scheduling clock tick on all of said CPUs;

said initiating a hysteresis period comprises first and second hysteresis initiating operations;

said waiting for said hysteresis period to end comprises first and second hysteresis period waiting operations;

said first hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said first state to said second state, and performing a calculation to determine a first delay period for transition of said global state variable from said second state to said third state;

said first hysteresis period waiting operation comprises said timekeeping CPU waiting until said first delay period has elapsed;

said second hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said second state to said third second state, and performing a calculation to determine a second delay period for transition of said global state variable from said third state to said fourth state;

said second hysteresis period waiting operation comprises said timekeeping CPU waiting until said second delay period has elapsed;

said manipulating a data structure comprises said timekeeping CPU transitioning said global state variable from said third state to said fourth state after said second said delay period has elapsed;

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global state variable being in said fourth state, and includes said timekeeping CPU transitioning said global state variable from said fourth state to said fifth state, then disabling the scheduling clock tick.

11. The system of claim 10, wherein said global state variable is maintained as part of a Read-Copy Update (RCU) dyntick-idle subsystem, and state transitions of said global state variable between said first state, said second state and said third state are performed by an RCU grace period tracking kthread running on said timekeeping CPU.

12. The system of claim 11, wherein said non-timekeeping CPUs record their entry into idle state using a per-CPU idle state variable, and said RCU dyntick-idle subsystem checks said per-CPU idle state variables and transitions said global state variable from said first state to said second state if each non-timekeeping CPU has set its per-CPU idle state variable to indicate said idle state.

13. The system of claim 10, wherein said calculations to determine said first and second delay periods are based on a number of said CPUs, and if said number of CPUs exceeds a threshold, a rate of said scheduling clock tick and an RCU leaf fanout size.

14. The method of claim 10, wherein said scheduling clock tick is restored by one of said non-timekeeping CPUs awakening out of its idle state, checking said global state variable, transitioning said global state variable to said first state if it was in any of said third through fifth states, and sending an inter-processor interrupt to said timekeeping CPU if said global state variable is in said fifth state.

15. A computer program product, comprising:

one or more computer readable storage media;

program instructions provided by said one or more computer readable storage media for programming a data processing platform to implement an adaptive tick kernel, and operations for detecting full-system idle state in said adaptive-tick kernel, said operations comprising detecting a non-timekeeping CPU idle state, initiating a hysteresis period, waiting for said hysteresis period to end, manipulating a data structure whose state indicates whether a scheduling clock tick may be disabled on all of said CPUs, and disabling said scheduling clock tick on all of said CPUs if said data structure is determined to be in an appropriate state.

16. The computer program product of claim 15, wherein:

said detecting a non-timekeeping CPU idle state comprises each non-timekeeping CPU detecting it is ready to enter an idle state;

said initiating a hysteresis period comprises each non-timekeeping CPU setting a timer, then entering said idle state;

said waiting for said hysteresis period to end comprises each non-timekeeping CPU remaining in said idle state until it is awakened by said timer;

said manipulating a data structure comprises each non-timekeeping CPU decrementing a global counter if it remained in said idle state for said hysteresis period, then returning to said idle state indefinitely; and

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global counter having been decremented to a predetermined value indicating that all of said non-timekeeping CPUs have remained in said idle state for at least said hysteresis period.

17. The computer program product of claim 15, wherein:

said detecting a non-timekeeping CPU idle state comprises said timekeeping CPU detecting that all said non-timekeeping CPUs are in said idle state;

said initiating a hysteresis period and said waiting for said hysteresis period to end use a global state variable that indicates whether or not all of said non-timekeeping CPUs are in an idle state, and if so, for how long;

said global state variable being configured to store a first state indicating that at least one non-timekeeping CPU is in a non-idle state, a second state indicating that all of said non-timekeeping CPUs have been in an idle state for a relatively short time period, a third state indicating that all of said non-timekeeping CPUs have been in an idle state long enough that said global state variable may be changed without danger of excessive memory contention, a fourth state indicating that all of said non-timekeeping CPUs have been in an idle state long enough to warrant turning off said scheduling clock tick, and a fifth state indicating that said timekeeping CPU has noted said fourth state and turned off said scheduling clock tick on all of said CPUs;

said initiating a hysteresis period comprises first and second hysteresis initiating operations;

said waiting for said hysteresis period to end comprises first and second hysteresis period waiting operations;

said first hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said first state to said second state, and performing a calculation to determine a first delay period for transition of said global state variable from said second state to said third state;

said first hysteresis period waiting operation comprises said timekeeping CPU waiting until said first delay period has elapsed;

said second hysteresis initiating operation comprises said timekeeping CPU transitioning said global state variable from said second state to said third second state, and performing a calculation to determine a second delay period for transition of said global state variable from said third state to said fourth state;

said second hysteresis period waiting operation comprises said timekeeping CPU waiting until said second delay period has elapsed;

said manipulating a data structure comprises said timekeeping CPU transitioning said global state variable from said third state to said fourth state after said second said delay period has elapsed;

said disabling said scheduling clock tick on all of said CPUs is performed by said timekeeping CPU based on said global state variable being in said fourth state, and includes said timekeeping CPU transitioning said global state variable from said fourth state to said fifth state, then disabling the scheduling clock tick.

18. The computer program product of claim 17, wherein said global state variable is maintained as part of a Read-Copy Update (RCU) dyntick-idle subsystem, and state transitions of said global state variable between said first state, said second state and said third state are performed by an RCU grace period tracking kthread running on said timekeeping CPU.

19. The computer program product of claim 18, wherein said non-timekeeping CPUs record their entry into idle state using a per-CPU idle state variable, and said RCU dyntick-idle subsystem checks said per-CPU idle state variables and transitions said global state variable from said first state to said second state if each non-timekeeping CPU has set its per-CPU idle state variable to indicate said idle state.

20. The computer program product of claim 17, wherein said calculations to determine said first and second delay periods are based on a number of said CPUs, and if said number of CPUs exceeds a threshold, a rate of said scheduling clock tick and an RCU leaf fanout size.

21. The computer program product of claim 20, wherein said scheduling clock tick is restored by one of said non-timekeeping CPUs awakening out of its idle state, checking said global state variable, transitioning said global state variable to said first state if it was in any of said third through fifth states, and sending an inter-processor interrupt to said timekeeping CPU if said global state variable is in said fifth state.