Reducing latencies in computing systems using probabilistic and/or decision-theoretic reasoning under scarce memory resources

• US 8,112,755 B2
• Filed: 06/30/2006
• Issued: 02/07/2012
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Apacible, Johnson T., Horvitz, Eric J., Iyigun, Mehmet
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US11/428,231
• Publication Number:
  US 20080005736A1
• Time in Patent Office: 2,048 Days
• Field of Search: 718/100, 718/104
• US Class Current: 718/104
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2209/482 Application
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Architecture that employs probabilistic and/or decision-theoretic model(s) of application usage to predict application use and in view of bounded or limited-availability memory. The model(s) is applied with cost-benefit analysis to guide memory management in an operating system, in particular, for both decisions about prefetching and memory retention versus deletion or “paging out” of memory of lower priority items, to free up space for higher value items. Contextual information is employed in addition to computer action monitoring for predicting next applications to be launched. Prefetching is optimized so as to minimize user perceived latencies.

Claims

1. A system, comprising:

a memory component for utilization by system processes;

a learning and reasoning component, implemented by one or more processors configured with executable instructions, to provide a model that predicts a next launch of a system process and to provide a cost-benefit analysis of pre-fetching data into the memory component and for retaining data already in the memory component, with the cost-benefit analysis based in part on a first rate at which cost is calculated before a threshold time, and a second rate at which cost is calculated after the threshold time, the first rate being less than the second rate; and

a management component that manages the memory component to reduce latency according to input from the learning and reasoning component, the input including;

system processes sorted in a priority order, the priority order based on a benefit of a system process divided by a cost of adding that system process to the memory component; and

a single system process, having a benefit greater than all other system processes and sized to fit into the memory component if it were alone in the memory component;

the management component configured to select between a cost-benefit value of the single system process and a portion of the system processes sorted in the priority order, the portion including system processes having highest cost-benefit values and limited to as many system processes as will fit into the memory component.

2. The system of claim 1, wherein the management component manages a decision-theoretic model to reduce the latency associated with the system process according to cost-benefit and uncertainty.

3. The system of claim 1, further comprising an application launch component for monitoring data of the system process to predict launch and/or usage of a next application.

4. The system of claim 3, wherein the data monitored by the application launch component is associated with foreground launch activity of the system process.

5. The system of claim 3, wherein the application launch component distinguishes between a foreground launch and a background launch of the system process, which is an application.

6. The system of claim 1, further comprising an application launch component that monitors launch data associated with an application, stores a record of the launch data, generates a transition model based on the launch record, and updates the model based on new launch data.

7. The system of claim 1, further comprising an application launch component that utilizes a Markov model for computing probability data associated with inferring when a next system process will be launched.

8. The system of claim 1, further comprising a prefetch component that prefetches data into the memory component based on a decision data of a probabilistic and/or decision-theoretic model.

9. The system of claim 1, further comprising a retention component that maintains data in the memory component based on decision data of a probabilistic and/or decision-theoretic model.

10. A computer-implemented method of managing system resources, comprising:

receiving access to a memory component of a device for utilization by device processes;

processing a model, the model predicting execution of the device processes;

performing, by one or more processors configured with executable instructions, a cost-benefit analysis of the device processes, with a cost in the cost-benefit analysis based in part on latency, the cost-benefit analysis using a latency period to calculate a cost, the cost-benefit analysis changing after a threshold period of time such that the cost-benefit analysis assigns a lesser cost to units of time before the threshold period and a greater cost to same duration units of time after the threshold period;

sorting the device processes into a priority order based on the cost-benefit analysis;

identifying a single device process having a benefit greater than all other device processes and sized to fit into the memory component if it were alone in the memory component;

selecting between a cost-benefit value of the single device process and a portion of the device processes sorted in the priority order, the portion including device processes having highest cost-benefit values and limited to as many device processes as will fit into the memory component; and

using the selection between the single device process and the portion of the device processes to make decisions to pre-fetch and retain data in the memory component to reduce latency associated with the device processes.

11. The method of claim 10, further comprising:

separating the device processes related to applications into a group of applications the user cares about and a group of applications the user does not care about using a classification mechanism based on usage monitoring; and

predicting when a next application will launch as part of the device processes based on the groups.

12. The method of claim 11, further comprising inferring probability data associated with determining when the next application will launch, using a Markov model.

13. The method of claim 10, wherein processing the model includes computing an optimization based on user perceptions of the latency.

14. The method of claim 13, wherein the optimization is based on a value-density approximation to a knapsack representation associated with minimizing actual and/or perceived latencies.

15. The method of claim 10, further comprising optimizing a prefetch process to minimize user perception of latency associated with one of the device processes.

16. The method of claim 10, further comprising predicting when an application will launch based on contextual information and at least one of the device processes.

17. The method of claim 10, further comprising performing a prefetch operation based on the cost-benefit analysis.

18. The method of claim 10, further comprising employing a second model in combination with the model to make a decision related to prefetching data into the memory component.

19. A computer-implemented method of managing resources, comprising:

under control of one or more processors configured with executable instructions,

determining available memory in a computer for processing programs and data;

developing and processing models for predicting an application launch, the models including a Markov model that processes a last n steps associated with system processes;

looking back n steps, where n is a variable related to the available device memory and is greater than zero;

accessing and processing context data;

analyzing sequences of n applications and context data using the models, the context data including an amount of time a user has been logged into the computer, an amount of time a returning user has been away from the computer and an amount of time a user has been active within each of the n applications;

predicting a next application launch based in part on analysis and context data, the predicting managing processing of the programs and data based on the available memory to reduce latency associated with the programs and data;

sorting resources into a priority order based on the cost-benefit analysis;

identifying a resource having benefit greater than all other resources and sized to fit into the available memory if it were alone in the available memory;

selecting between a cost-benefit value of the single resource and a portion of the resources sorted in the priority order, the portion including resources having highest cost-benefit values and limited to as many resources as will fit into the memory component;

pre-fetching resources according to the prediction of the next application launch and the selection between the cost-benefit value of the largest resource and the sum of the cost-benefit values of the portion of the resources; and

updating the models for predicting application and data actions.