Method and system for regulating background tasks using performance measurements

• US 6,834,386 B1
• Filed: 07/16/1999
• Issued: 12/21/2004
• Est. Priority Date: 07/16/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Douceur, John R.
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Nguyen, Dustin
• Application Number:
  US09/354,970
• Time in Patent Office: 1,985 Days
• Field of Search: 709/103, 709/224, 709/235, 709/102, 709/104, 709/107, 709/200, 709/204, 710/11, 712/228, 713/320, 713/323, 370/259, 370/447, 714/7, 711/114
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and system for regulating tasks of background processes so as to reduce interference with foreground processes. The progress rate of a background task (e.g., amount of work performed per unit time) is measured and evaluated against a target amount. If the progress rate appears degraded, the background task is suspended for a computed time interval so as to back off from its interference with a foreground process. Each time the progress rate appears degraded, the time interval is exponentially increased from its previous value up to a maximum, however if the performance appears normal, the time interval is reset to a minimum. Evaluation of the work is statistically based so as to eliminate variations in measurements, and automatic calibration of the target amount is provided, as is a mechanism for prioritizing multiple background tasks.

Claims

1. A computer-readable medium having computer-executable instructions, comprising, executing a background task, receiving data from a software component indicative of a measured progress of the background task relative to past performance data of the background task, and determining when to again execute the background task based on the data including comparing the measured progress of the background task against a target progress, the target progress based on data measured from previously running the background task.

2. The computer-readable medium of claim 1 having further computer-executable instructions for suspending the background task for a suspend time, and authorizing the background task to again execute.

3. The computer-readable medium having computer-executable instructions of claim 1, wherein determining when to again execute the background task includes determining a suspend time for suspending the background task.

4. The computer-readable medium having computer-executable instructions of claim 3, wherein if the measured progress with respect to the target progress is acceptable, setting the suspend time to a relatively low duration.

5. The computer-readable medium having computer-executable instructions of claim 4, wherein setting the suspend time to a relatively low duration includes setting the suspend time to a minimum value.

6. The computer-readable medium having computer-executable instructions of claim 3, wherein if the measured progress with respect to the target progress is not acceptable, increasing the suspend time.

7. The computer-readable medium having computer-executable instructions of claim 6, wherein increasing the suspend time includes doubling a previous suspend time.

8. The computer-readable medium having computer-executable instructions of claim 3, wherein if the measured progress with respect to the target progress is not determinable by present data, maintaining the suspend time.

9. The computer-readable medium having computer-executable instructions of claim 1, wherein determining when to again execute the background task includes determining a suspend time for suspending the background task, and wherein the suspend time is further based on a relative importance of the task.

10. The computer-readable medium having computer-executable instructions of claim 1, wherein determining when to again execute the background task includes statistically combining the data received with previous data.

11. The computer-readable medium of claim 1 having further computer-executable instructions for, determining a target value indicative of a target amount of work, and wherein determining when to again execute the background task includes comparing the measured progress of the background task against the target value.

12. The computer-readable medium having computer-executable instructions of claim 11, wherein determining a target value further comprises, using measured progress data to automatically calibrate the target value.

13. The computer-readable medium having computer-executable instructions of claim 1, wherein the measured progress comprises an amount of work performed per unit time.

14. The computer-readable medium having computer-executable instructions of claim 1, wherein the background task is executed for a limited time, and the data include a count of the number of operations performed during the limited time.

15. The computer-readable medium having computer-executable instructions of claim 14, wherein the data include the total real time taken for the operations to complete.

16. The computer-readable medium having computer-executable instructions of claim 15, wherein the data include a parameter representing the relative amount of work performed by each operation.

17. The computer-readable medium having computer-executable instructions of claim 16, wherein the background task is part of a process for recognizing duplicate files on a file system partition, and wherein the amount of work performed by each operation is an amount of data read from the partition.

18. The computer-readable medium having computer-executable instructions of claim 1, wherein the background task performs input/output operations on a resource.

19. The computer-readable medium of claim 1 having further computer-executable instructions for prioritizing an execution of at least one other task.

20. The computer-readable medium of claim 1 wherein receiving data indicative of a measured progress of the background task comprises receiving an indication of acceptable performance.

21. The computer-readable medium of claim 1 wherein receiving data indicative of a measured progress of the background task comprises receiving an indication of unacceptable performance.

22. A system for regulating the execution of a background task, comprising, a task regulator comprising software code for authorizing the background task to execute, a performance evaluator comprising software code for receiving measured performance data of the background task and evaluating the measured performance data with respect to past performance data of the background task and providing progress information corresponding thereto, the performance evaluator evaluating the measured performance data with respect to past performance data by comparing measured progress data against target progress data, and a computation mechanism comprising software code connected to receive the progress information from the performance evaluator, the task regulator connected to the computation mechanism for authorizing the background task to again execute based on information received from the computation mechanism.

23. The system of claim 22 wherein the information received from the computation mechanism includes a suspension time.

24. The system of claim 23 wherein the computation mechanism further determines the suspension time based on a relative importance of the task.

25. The system of claim 22 further comprising a calibration mechanism for providing the target progress data.

26. The system of claim 25 wherein the calibration mechanism receives the measured progress data and statistically combines the measured progress data with previous progress data.

27. The system of claim 22 wherein the measured performance data comprises an amount of work performed per unit time.

28. The system of claim 22 wherein the background process executes for a limited time, and wherein the measured performance data include a count of the number of operations performed during the limited time and a total real time taken for the operations to complete.

29. The system of claim 22 wherein the performance data further include a parameter representing a relative amount of work performed by each operation.

30. The system of claim 22 further comprising a resource accessed by the background process.

31. The system of claim 22 further comprising at least one other task having its execution regulated by the task regulator.

32. The system of claim 22 wherein the progress information provided by the performance evaluator comprises an indication of acceptable performance.

33. The system of claim 22 wherein the progress information provided by the performance evaluator comprises an indication of unacceptable performance.

34. The system of claim 22 wherein the progress information provided by the performance evaluator comprises an indication of more information being needed.

35. A method of executing a background process, comprising the steps of, executing a task of the background process, measuring the progress of the task via software code, comparing the progress of the task against a target progress that is based on at least one previous progress measurement of the task, and if the progress of the task is degraded relative to the target progress, increasing a delay time from a previous value thereof, and suspending for the delay time before re-executing the task.

36. The method of claim 35 wherein the progress of the task corresponds to an amount of work per unit time performed by the task.

37. The method of claim 35 wherein the background process seeks duplicate files of a file system.

38. The method of claim 35 further comprising the step of adjusting the target amount based on the progress of the task.

39. The method of claim 35 wherein the progress of the task corresponds to a number of operations performed.

40. The method of claim 39 wherein the progress of the task corresponds to total time taken for the operations.

41. The method of claim 39 wherein the progress of the task corresponds to a relative amount of work performed by each operation.

42. A computer-readable medium having computer-executable instructions for performing the method of claim 35.

43. A computer-readable medium having computer-executable instructions, comprising, executing a background task, receiving data from a software component indicative of a measured progress of the background task relative to past performance data of the background task, and determining when to again execute the background task based on the data, including statistically combining the data received with previous data.

44. A computer-readable medium having computer-executable instructions, comprising, executing a background task, receiving data from a software component indicative of a measured progress of the background task relative to past performance data of the background task, determining a target value indicative of a target amount of work, and determining when to again execute the background task based on the data, including comparing the measured progress of the background task against the target value.

45. The computer-readable medium having computer-executable instructions of claim 44, wherein determining a target value further comprises, using measured progress data to automatically calibrate the target value.