Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-03-26
2002-08-27
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S158000
Reexamination Certificate
active
06442648
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.
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.
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. In application Ser. No. 09/148,181, filed Sep. 3, 1998, there is disclosed a system in which when a real-time request becomes urgent, the arm moves directly from its current location to the track location on the disk that contains the most urgent real-time request. The arm bypasses all requests, both real-time and non-real-time, that may be between the two locations. Thus, as real-time requests become urgent, the arm may tend to “jump around” servicing real-time requests on a most-urgent basis.
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 the processing of 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 the processing of a plurality of requests that processes urgent real-time requests in a timely manner, while minimizing back-and-forth movement of the disk arm.
The present invention provides a method and system in a data processing system for dynamically scheduling the processing of a plurality of requests to access a disk, in which each of the plurality of requests is associated with a location on the disk. The method of the present invention processes the requests in a first sequential order and determines the amount of time necessary to process a selected number of requests associated with locations between the current location on the disk and the most urgent request. At a time that is earlier than the deadline for processing the most urgent request by the amount of time necessary to process the selected number of requests, the method commences processing of the selected number of requests in a second sequential order.
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: 5737547 (1998-04-01), Zuravleff et al.
patent: 5829046 (1998-10-01), Tzelnic et al.
Genduso Thomas B.
Ingerman Donald
Anderson Matthew D.
Dillon Andrew J.
International Business Machines - Corporation
Kim Matthew
LandOfFree
Method of and system for the dynamic scheduling of requests... 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 of and system for the dynamic scheduling of requests..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and system for the dynamic scheduling of requests... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2914792