Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-07-16
2004-12-21
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S102000, C718S103000
Reexamination Certificate
active
06834386
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to computer systems, and more particularly to improving the operating performance of computer systems.
BACKGROUND OF THE INVENTION
Many computer systems execute background processes. The tasks of these processes are often directed to performing maintenance (housekeeping) functions, such as file compression, disk defragmentation, file-system content indexing and file archiving. While these tasks are relatively important to complete at some time, there is ordinarily no need to do so at any particular time. Thus, they are often run in the background, operating when no higher-priority foreground process, such as a process of an application program interacting with a user, is operating.
The traditional approach to operating a background process is to assign the process a priority level that is just above the system idle process, whereby CPU (central processing unit) cycles are allotted to the background process only when no normal priority process is ready to use the CPU. For example, in the Unix programming environment, the command “nice” initiates a process with reduced scheduling priority, which may be set as low as the system idle priority level.
Governing the execution of a process by priority scheduling of CPU cycles assumes that the CPU is the limiting resource. However, in many instances, the CPU is not the limiting resource, but instead, process performance may be limited by I/O (input/output) rate and/or contention for another system resource, such as the disk, processor cache, memory capacity and/or memory bandwidth. Since background processes contend for these resources, background processes interfere with higher priority foreground processes, and scheduling priority is insufficient as a mechanism for limiting this interference. The interference increases with background processes related to file-system maintenance activities, since such activities are resource intensive, but often use few CPU cycles.
By way of example, consider a background process that wants to access the same I/O resource (e.g., a disk) as a foreground process, wherein both processes are regularly performing I/O operations to the disk resource that take longer than the amount of time each process needs the CPU. When the foreground process is performing disk I/O operations, the background process is given some CPU cycles, during which time the background process desires access to the disk resource. As can be appreciated, the background process has to wait for completion of the I/O by the foreground process.
When the foreground process completes its I/O operation, the background process is given access to the disk and the foreground process is given CPU cycles, during which time the foreground process again wants access to the disk resource. However, because the foreground process has to wait for access to the disk resource, the foreground process has to idle, and at that moment, the CPU is essentially not being used by either the foreground or background process. Accordingly, the CPU is not the limiting resource, but rather the disk is, i.e., contention for the disk resource by the background process causes the interference with the foreground process. Unless the background process is entirely halted, however, the background process will receive CPU cycles when the foreground process is performing I/O, and thus will continue to interfere with the foreground process because the background process also will request access to the disk resource during its allotted cycles.
A foreground application program's process that is of immediate consequence to a user is thus negatively impacted by (non-CPU) resource contention, unless the background process is canceled. However, simply canceling the background process defeats the many advantages of having a background process run, e.g., to perform useful work during the many times when the foreground process is not contending with the background process for the CPU or other resource.
SUMMARY OF THE INVENTION
Briefly, the present invention provides a method and system for limiting the interference of a background process with a foreground process. A background process is executed for a brief time slice. The actual performance of the background process is measured, and statistically analyzed to determine if the performance is degraded, operating normally, or if more information is needed. If the performance is degraded, the background process is likely interfering with the foreground process, whereby the background process is then suspended (backed off) for longer and longer time intervals between executions until either some acceptable limit is reached or until the performance of the background process no longer appears to be degraded, indicating that it is likely not interfering with another process. If normal performance is detected, the back-off time interval is reset to some predetermined minimum value. If normal performance is detected or more information is needed, the task will again receive authorization to perform work. Because the actual performance is dynamically measured for each execution period, contention for a resource other than the CPU is actively detected, enabling the background process to appropriately and quickly back off from interfering with the foreground process via device contention. A critical task may have the suspension time dynamically adjusted based on its relative importance such that it will operate at a higher duty cycle.
The measured performance data may be used to automatically and statistically calibrate a target performance value for determining whether the measured performance is degraded. A mechanism for regulating multiple background tasks such that the tasks also do not interfere with one another is further provided. An exemplary application using the present invention to operate in the background to find and merge duplicate files is also described.
Other advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:
REFERENCES:
patent: 5408663 (1995-04-01), Miller
patent: 5410667 (1995-04-01), Belsan et al.
patent: 5537566 (1996-07-01), Konno et al.
patent: 5542088 (1996-07-01), Jennings, Jr. et al.
patent: 5706510 (1998-01-01), Burgoon
patent: 5778384 (1998-07-01), Provino et al.
patent: 5778395 (1998-07-01), Whiting et al.
patent: 5822584 (1998-10-01), Thompson et al.
patent: 5907673 (1999-05-01), Hirayama et al.
patent: 5918229 (1999-06-01), Davis et al.
patent: 5938723 (1999-08-01), Hales et al.
patent: 5949762 (1999-09-01), Green et al.
patent: 6047308 (2000-04-01), Grummer et al.
patent: 6058489 (2000-05-01), Schultz et al.
patent: 6076157 (2000-06-01), Borkenhagen et al.
patent: 6098090 (2000-08-01), Burns
patent: 6101194 (2000-08-01), Annapareddy et al.
patent: 6185574 (2001-02-01), Howard et al.
patent: 6223201 (2001-04-01), Reznak
patent: 6243736 (2001-06-01), Diepstraten et al.
patent: 0 774 715 (1997-05-01), None
patent: WO 99/09480 (1999-02-01), None
patent: WO 99/12098 (1999-03-01), None
patent: WO 99/21082 (1999-04-01), None
LaLonde, Ken, “Batch daemon—README”, UNIX Batch Command, University of Toronto, pp. 1-3 (Feb. 27, 1997), ftp://ftp.cs.toronto.edu/pub/batch.tar.z printed Dec. 8, 2000.
Steere et al., “A Feedback-driven Proportion Allocator for Real-Rate Scheduling”,Third Symposium on Operating Systems Design and Implementation(OSDI '99), USENIX Association, pp. 145-158 (Feb. 22, 1999).
Copy of International Search Report from corresponding PCT Application No. PCT/US00/18989 mailed Jan. 5, 2001.
Bolosky William J.
Douceur John R.
Follansbee John
Law Offices of Albert S. Michalik PLLC
Microsoft Corporation
Nguyen Dustin
LandOfFree
Method and system for regulating background tasks using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for regulating background tasks using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for regulating background tasks using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324767