Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
1999-10-15
2002-08-13
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S005000, C710S036000, C710S039000, C710S040000, C709S241000
Reexamination Certificate
active
06434631
ABSTRACT:
TECHNICAL FIELD
This invention is related to a method of scheduling computer storage input and output requests to provide minimum quality of service guarantees.
BACKGROUND OF THE INVENTION
Increasingly, computer users are relying upon a single computing platform to execute multiple applications. In such situations, the various applications executing on the platform must share access to the available system resources, such as disk I/O. In those situations where available resources far exceed the requirements of the applications, control of access to system resources can be relatively straightforward. However, it is often not practical or economical to over provision resources in this manner. Thus, the operating system must make various resource allocation decisions for the various executing processes.
In many situations, it is desirable for a process to be provided with a guaranteed minimum level of system resources. For example, multimedia applications often require that I/O services (e.g., disk or network accesses) be provided with a certain quality of service (e.g., minimum throughput or maximum delay). If the quality of service declines, the performance of the application can suffer, resulting in jerky video display, choppy audio, and other problems.
Ideally, a system should provide a quality of service (“QoS”) guarantee to an application requesting it. If the minimum performance requirement for the requested service cannot be guaranteed, the system should not accept the request.
Conventional operating systems, such as Windows NT and UNIX both dynamically compute the priorities of unprivileged processes and allocate system resources accordingly. Although high priority applications are serviced in advance of lower priority applications, such systems do not guarantee minimum service levels. While a user may be merely annoyed of the system delays the execution of an interactive application to service another process, such a delay in a multimedia application can render the application's audio or video output wholly unusable.
A variety of specific scheduling algorithms have been proposed to provide levels of QoS guarantees. However, these conventional approaches consider each resource in isolation, neglecting interactions. Unfortunately, this is not realistic due to “closed-loop” nature of most applications: After completion of a request on one resource (e.g., disk), applications often have to compete for another resource (e.g., CPU) before being able to make another request on the first resource. In such situations, scheduling delays on each resource can accumulate and make actual throughput much lower than expected if each resource is considered in isolation.
SUMMARY OF THE INVENTION
A disk scheduling algorithm with high cumulative service guarantees, low delay, and good fairness is provided by assigning I/O requests from various system elements to particular domains. Each domain is guaranteed a minimum quality of service and an admission control algorithm is used to determine whether a new QoS domain can be added without violating the QoS guarantees of existing domains. I/O requests from each QoS domain are maintained in separate FIFO queues and are serviced by a disk scheduler selects in accordance with the fair queuing scheduling algorithm of the invention which preserves the quality of service guarantees. An I/O request is maintained at the head of the corresponding domain queue while it is being serviced and is removed only after service completion.
According to the invention, the scheduling algorithm associates a start tag, Si, and a finish tag, Fi, with each domain queue i which is an element of the set of domains D. Initially, Si and Fi are both zero. As requests are added to a queue and subsequently serviced, the start and finish tags are updated as to reflect the estimated time required to service the request at the head of the queue with regard for the size of the input or output associated with the request and the proportion of disk bandwidth assigned to the particular domain. When the disk scheduler is ready to service a new request, the request is selected from the queue for the domain with the smallest finish tag among all busy domains, i.e., those domains which have I/O requests either waiting in the queue or being serviced. In this implementation, a domain can be safely deleted, freeing up the fraction of disk resource assigned to it, when the start tags for all of the other busy domains greater than or equal to the finish tag for the domain to be deleted.
REFERENCES:
patent: 5761692 (1998-06-01), Ozden et al.
patent: 5828878 (1998-10-01), Bennett
patent: 6112221 (2000-08-01), Bender et al.
S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance”,IEEE/ACM Transactions on Networking, Aug. 1993.
B. Suter, T.V. Lakshman, D. Stiliadis, and A. K. Choudhry, “Design Considerations for Supporting TCP with Per-Flow Queueing”,Proceedings of IEEE INFOCOM San Francisco, Mar. 1998.
R. Guérin, S. Kamat, V. Peris, and R. Rajan, “Scalable QoS Provision Through Buffer Management,”Proceedings of the ACM SIGCOMM Vancouver, Sep. 1998.
Ellen L. Hahne and Robert G. Gallager, Round Robin Scheduling for Fair Flow Control in Data Communication Networks,IEEE International Conference on Communications, Jun. 1986, pp. 103-107.
Dong Lin and Robert Morris, Dynamics of Random Early Detection,IEEE SIGCOMM '97, Sep. 1997.
Bruno John Louis
Brustoloni Jose Carlos
Gabber Eran
Ozden Banu
Silberschatz Abraham
Darby & Darby
Gaffin Jeffrey
Lucent Technologies - Inc.
Park Ilwoo
LandOfFree
Method and system for providing computer storage access with... 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 providing computer storage access with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for providing computer storage access with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961853