Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1998-09-03
2002-01-29
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S111000, C710S054000
Reexamination Certificate
active
06343351
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to data processing systems, and in particular to a method and system in a data processing system for dynamically scheduling a plurality of requests which include real-time and non-real-time requests. Still more particularly, the present invention relates to a method and system in a data processing system for scheduling non-real-time requests for processing as long as none of the real-time requests are urgent.
2. Description of the Related Art
Devices in a data processing system, such as disk drive adapters, are usually connected via a bus to transmit data from one device to and from other system resources, such as the central processor and memory. Each of these devices has data that it normally transfers. For example, one device may normally transfer real-time data such as is necessary to display a multimedia presentation. A second device may normally transfer non-real-time data that may be a file transfer. A third device may transfer both real-time and non-real-time data. The data transferred by these devices may be stored in a disk drive.
Real-time data is data that has an associated deadline. The deadline defines the time by which the real-time data must be transferred. Failure to transfer real-time data prior to the associated deadline will result in lost data. Non-real-time data has no associated deadline.
A computer system needs to support the transfer of both real-time and non-real-time data simultaneously. Often, however, when both real-time and non-real-time data are supported simultaneously, real-time data is not transferred in a timely manner without adversely affecting non-real-time data transfer. Since many of the data transfers come from disks, effective, efficient disk scheduling is important to provide timely delivery of data.
Modern disk storage systems use scheduling algorithms to order requests to minimize the amount of seeking, i.e. physical arm movement, a disk must do in order to locate the requested data. One such algorithm is called the elevator or SCAN algorithm. Each data request has an associated track on the physical disk on which the requested data is stored. This algorithm orders requests according to the track location on the disk where the data is stored. The disk first services the request for data stored on the outermost track, and then proceeds to service requests for data stored on tracks that are ordered towards the innermost track. Therefore, the disk is initially traversed from outermost to innermost track. When the innermost track that contains requested data is reached, the direction is reversed so that the disk is traversed from innermost track to outermost track, like an elevator stopping at selected floors. A variant of SCAN is called CSCAN. In CSCAN, instead of reversing direction when the innermost track is reached, the arm will travel back to the outermost track and seek inward again.
Therefore a need exists for a method and system in a data processing system to dynamically schedule a plurality of requests that include real-time and non-real-time requests, where the non-real-time requests are scheduled until a real-time request becomes urgent.
SUMMARY OF THE INVENTION
One object of the present invention is to provide an improved data processing system.
Another object of the present invention is to provide a method and system in a data processing system for dynamically scheduling a plurality of requests that include both real-time and non-real-time requests.
It is yet another object of the present invention to provide a method and system in a data processing system for dynamically scheduling a plurality of requests for processing as long as none of the real-time requests are urgent.
The foregoing objectives are achieved as is now described. A method and system in data processing system are disclosed for the dynamic scheduling of a plurality of requests to access a disk. Each of the requests is associated with a location on the said disk which each of the requests is attempting to access. A scan queue is established for storing the plurality of requests. The plurality of requests are processed in a sequential order. The sequential order is determined utilizing the location on the disk being accessed by each of the requests. Upon one of the stored requests being urgent, the urgent request is processed. The urgent request is associated with a first location on said disk. Processing of the requests then continues in a second sequential order. The second sequential order is determined utilizing the first location. The next request to be processed is one of the requests which is associated with a physically closest location on the disk.
The above as well as additional objectives, features, and advantages of the illustrative embodiment will become apparent in the following detailed written description.
REFERENCES:
patent: 5729718 (1998-03-01), Au
patent: 5835962 (1998-11-01), Chang et al.
patent: 5915260 (1999-06-01), Sokolov
patent: 6023720 (2000-02-01), Aref et al.
patent: 6078998 (2000-06-01), Kamel et al.
A.L. Narasimha Reddy and James C. Wyllie, “I/O Issues in a Multimedia System”, IBM Almaden Research Center, IEEE, pp. 69-74, Mar. 1994.
David P. Anderson, Yoshitomo Osawa and Ramesh Govindan, “A File System for continuous Media”, ACM Transactions on Computer Systems, vol. 10, No. 4, Nov. 1992, pp. 311-337.
Renu Chipalkatti, James F. Kurose and Don Towsley, Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer, Department of Computer and Information Science, IEEE, pp. 774-783.
A.L. Narasimha Reddy and Jim Wyllie, “Disk scheduling in a multimedia I/O system”, ACM Multimedia, pp. 225-233, 1993.
Robert K. Abbott and Hector Garcia-Molina, “Scheduling Real-Time Transactions: A Performance Evaluation”, ACM Transactions on Database Systems, vol. 17, No. 3, Sep. 1992, pp. 513-560.
G.A. Awater and F.C. Schoute, “Performance Improvement of Fast Packet Switching by LDOLL Queueing”, IEEE, pp. 562-568, 1992.
Genduso Thomas B.
Ingerman Donald
Islam Shah Mohammad Rezaul
Lackman Robert Andrew
Anderson M. D.
Bracewell & Patterson LLP
International Business Machines - Corporation
Kim Matthew
LandOfFree
Method and system for the dynamic scheduling of requests to... 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 the dynamic scheduling of requests to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for the dynamic scheduling of requests to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826541