Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-08-11
2002-04-23
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S112000, C711S151000, C709S241000, C709S241000, C710S006000, C710S039000, C710S054000
Reexamination Certificate
active
06378052
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
The present invention is related to the subject matter of co-pending patent application Ser. No. 09/148,181 entitled METHOD AND SYSTEM FOR THE DYNAMIC SCHEDULING OF REQUESTS TO ACCESS A STORAGE SYSTEM and assigned to the assignee herein filed on Sep. 3, 1998 and incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to data processing systems, and in particular to a data processing system and method for efficiently servicing a plurality of disk requests, some of which have an associated deadline or specific time by which they must be serviced. Still more particularly, the present invention relates to a data processing system and method for scheduling a plurality of pending disk requests so that sufficient time exists to service both a most urgent disk request as well as a second most urgent disk request before the expiration of the requests' deadlines.
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, such as a file transfer. A third device may transfer both real-time and non-realtime 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 toward 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.
When urgent requests are pending, known systems service pending requests in an order consistent with their location on the disk and the SCAN or CSCAN algorithm until the deadline of the most urgent request occurs. When the deadline is reached, the most urgent request is then serviced. A problem often arises, however, because the deadline for the second most urgent request may pass before the disk arm is able to move to the second most urgent request.
Therefore a need exists for efficiently servicing a plurality of pending requests to access a disk so that sufficient time exists to service both a most urgent request as well as a second most urgent disk request before the expiration of the requests' deadlines.
SUMMARY OF THE INVENTION
A method and system in data processing system are disclosed for efficiently servicing requests to access a disk. Each of the requests are associated with a location on the disk. The requests include real-time requests and non-real time requests. A most urgent one of the requests is determined. The most urgent one of the requests is associated with a first deadline and a first location on the disk. A second most urgent one of the requests is also determined. The second most urgent one of the requests is associated with a second deadline and a second location on the disk. The first deadline is earlier in time than the second deadline. A service time is determined. The service time is earlier in time than the first deadline. The service time is determined so that sufficient time will exist to service the most urgent one of the requests before the first deadline and service the second most urgent one of the requests before the second deadline. A closest request is determined by determining whether the first location or the second location is closest to a current location of a disk arm. The closest request is either the most urgent one of the requests or the second most urgent one of the requests. In response to a current time reaching the service time, the closest request is serviced such that the most urgent one of the requests is serviced before the first deadline and the second most urgent one of the requests is serviced before the second deadline.
The above as well as additional objectives, features, and advantages of the preferred embodiment will become apparent in the following detailed written description.
REFERENCES:
patent: 5787482 (1998-07-01), Chen et al.
patent: 6023720 (2000-02-01), Aref et al.
patent: 6078998 (2000-06-01), Kamel et al.
Genduso Thomas B.
Ingerman Donald
Dillon Andrew J.
Song Jasmine
Yoo Do Hyun
LandOfFree
Data processing system and method for efficiently servicing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing system and method for efficiently servicing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system and method for efficiently servicing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2869615