System for estimating access time by deriving from first and second rotational time from rotational time table based on logical address and head movement time

• US 5,854,941 A
• Filed: 05/31/1996
• Issued: 12/29/1998
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: eAcceleration Corporation
• Original Assignee: Acceleration Software International Corporation
• Inventors: Ballard, Clinton L., Smith, Timothy W.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Chen, Anderson I.
• Application Number:
  US08/656,372
• Time in Patent Office: 942 Days
• Field of Search: 364/236.2, 360/48, 360/49, 360/77.08, 711/4, 395/825
• US Class Current: 710/5
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: G11B 21/083 on discs
• CPC Class Codes: G11B 27/105 of operating discs

Abstract

Disk I/O average access time is improved by estimating access time for pending I/O requests and selecting the request with the lowest estimated access time as the next request to be processed. To provide fast run-time estimation, disk characteristics are derived off-line and stored in files/tables for access during run-time estimation. A time (RT) to rotate the disk from a reference sector to each physical sector on the hard drive is derived and stored for each logical block address (LBA). A time (HT) for the heads to move an incremental number of cylinders also is derived. Access time of a destination LBA after completing access to a source LBA is estimated using estimated rotational times for the source and destination looked up in an RT table, and a head movement time estimate looked up in an HT table, based on a run-time calculated cylinder increment between the source and destination LBAs. Methods for developing rotational time estimates, head movement time estimates, disk zone characteristics, disk rotation time and other data are included.

Claims

1. A method for estimating access time of a rotating storage disk between a source logical block address and a destination logical block address, the disk comprising a plurality of tracks, each track comprising a plurality of sectors, a given sector addressed by a host computer using a logical block address, wherein the plurality of sectors for a given track have consecutively numbered logical block addresses starting from a first logical block address for the given track, the method comprising the steps of:

looking up a first rotational time estimate for the source logical block address and a second rotational time estimate for the destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

estimating radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table; and

deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate.

2. The method of claim 1, in which the rotational time estimate table and head movement time estimate table are derived off-line relative to a run-time process comprising the rotational time estimate looking up, radial distance determining, head movement time estimate looking up and estimated access time deriving steps.

3. A method for estimating access time of a rotating storage disk between a source logical block address and a destination logical block address, the disk comprising a plurality of tracks, each track comprising a plurality of sectors, a given sector addressed by a host computer using a logical block address, wherein the plurality of sectors for a given track have consecutively numbered logical block addresses starting from a first logical block address for the given track, the method comprising the steps of:

looking up a first rotational time estimate for the source logical block address and a second rotational time estimate for the destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

estimating radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table;

deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate; and

wherein the rotational time estimate table is generated in a disk data gathering method, comprising the steps;

for each one logical block address on a disk obtaining a completion-time time stamp for processing an I/O request for said one logical block address;

estimating time for the disk to make one revolution from a plurality of completion-time time stamps;

for the first logical block address of each track, obtaining a completion-time time stamp for said first logical block address and for a reference logical block address and storing rotational time estimate for said first logical block address as a difference between the completion-time time stamp for said first logical block address and said reference logical block address; and

for each i-th logical block address of a plurality of logical block addresses of a given track, storing rotational time estimate as the rotational time estimate for the i-1th logical block address plus an incremental time estimate for the i-th logical block address.

4. The method of claim 3, in which the incremental time estimate corresponds to the revolution time estimate less a difference between completion-time time stamp for the i-1th logical block address and the completion-time time stamp for the ith logical block address.

5. The method of claim 3, further comprising the step of identifying a first of the plurality of logical block addresses for each track of the disk by differencing a time stamp for a given logical block address on a given track with a numerically adjacent logical block address to said given logical block address, said given logical block address being the first of the plurality of logical block address along the given track when the difference is not within a prescribed margin of estimated revolution time.

6. Memory storage media encoded with executable instructions and data representing a computer program that cause a computer to perform a set of functions, comprising:

means for determining a first rotational time estimate for a source logical block address and a second rotational time estimate for a destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of a rotational storage disk;

means for estimating radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

means for looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table; and

means for deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate.

7. A computer system, comprising:

a disk drive having a disk comprising a plurality of disk platens for storing information, each platen comprising a plurality of tracks, each track comprising a plurality of sectors, each sector corresponding to a unique logical block address for accessing the information stored at the sector, the disk characterized by a plurality of cylinders, each cylinder comprising a constant number of the tracks;

means for requesting access to the disk drive using logical block addresses; and

means for estimating access time of the disk between a source logical block address and a destination logical block address, the access time estimating means comprising;

means for looking up a first rotational time estimate for the source logical block address and a second rotational time estimate for the destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

means for determining radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

means for looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table; and

means for deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate.

8. A computer system, comprising:

a disk drive having a disk comprising a plurality of disk platens for storing information, each platen comprising a plurality of tracks, each track comprising a plurality of sectors, each sector corresponding to a unique logical block address for accessing the information stored at the sector, the disk characterized by a plurality of cylinders, each cylinder comprising a constant number of the tracks;

means for requesting access to the disk drive using logical block addresses; and

means for estimating access time of the disk between a source logical block address and a destination logical block address, the access time estimating means comprising;

means for looking up a first rotational time estimate for the source logical block address and a second rotational time estimate for the destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

means for determining radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

means for looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table; and

means for deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate;

means for generating the rotational time estimate table;

the generating means comprising;

(i) means for obtaining a completion-time time stamp for each logical block address on the disk;

(ii) means for estimating time for the disk to make one revolution from a plurality of completion-time time stamps;

(iii) for the first logical block address of each track, means for obtaining a completion-time time stamp for said first logical block address and for a reference logical block address and means for storing rotational time estimate for said first logical block address as a difference between the completion-time time stamp for said first logical block address and said reference logical block address; and

(iv) for each i-th logical block address of a plurality of logical block address of a given track, means for storing rotational time estimate as the rotational time estimate for the i-1th logical block address plus an incremental time estimate for the i-th logical block address.

9. The computer system of claim 8, in which the incremental time estimate corresponds to the revolution time estimate less the difference between completion-time time stamp for the i-1th logical block address and the completion-time time stamp for the ith logical block address.

10. The computer system of claim 8, further comprising means for identifying a first logical block address along a track of the disk for each track to be a one logical block address corresponding to a completion-time time stamp difference with a numerically adjacent logical block address to said one logical block address in which the completion-time time stamp difference is not within a prescribed margin of estimated revolution time.

11. A method for scheduling an I/O request to a rotating storage disk which is to follow a first I/O request to the rotating storage disk, the rotating storage disk comprising a plurality of tracks, each track comprising a plurality of sectors, a given sector addressed by a host computer using a logical block address, wherein the plurality of sectors for a given track have consecutively numbered logical block addresses starting from a first logical block address for the given track, wherein the first I/O request specifies a source logical block address, the method comprising the steps of:

looking up a first rotational time estimate for the source logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

for a second I/O request, looking up a second rotational time estimate for the destination logical block address from the table of rotational time estimates;

estimating radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table;

deriving the estimated access time for the first I/O request from the first rotational time estimate, second rotational time estimate and head movement time estimate;

repeating the steps of looking up the second rotational time estimate, estimating the radial distance, looking up the head movement time estimate and deriving the estimated access time for at least one other I/O request, wherein for each repetition the destination logical block address is determined by the I/O request corresponding to the repeated steps; and

scheduling one I/O request of the second I/O request and said at least one other I/O request to follow the first I/O request.

12. The method of claim 11 in which the rotational time estimate table is generated in a disk data gathering method, comprising the steps:

for each one logical block address on a disk obtaining a completion-time time stamp for processing an I/O request for said one logical block address;

estimating time for the disk to make one revolution from a plurality of completion-time time stamps;

for the first logical block address of each track, obtaining a completion-time time stamp for said first logical block address and for a reference logical block address and storing rotational time estimate for said first logical block address as a difference between the completion-time time stamp for said first logical block address and said reference logical block address; and

for each i-th logical block address of a plurality of logical block addresses of a given track, storing rotational time estimate as the rotational time estimate for the i-1th logical block address plus an incremental time estimate for the i-th logical block address.

13. A computer system, comprising:

a disk drive having a disk comprising a plurality of disk platens for storing information, each platen comprising a plurality of tracks, each track comprising a plurality of sectors, each sector corresponding to a unique logical block address for accessing the information stored at the sector, the disk characterized by a plurality of cylinders, each cylinder comprising a constant number of the tracks;

means for requesting access to the disk drive using logical block addresses; and

means for estimating access time of the disk between a source logical block address and a destination logical block address, the access time estimating means comprising;

means for looking up a first rotational time estimate for the source logical block address and a second rotational time estimate for the destination logical block address from a table of rotational time estimates accessed by logical block address number, each entry in the table of rotational time estimates having a value not more than one rotational time of the disk;

means for determining radial distance between a first track having the source logical block address and a second track having the destination logical block address based upon the source logical block address and the destination logical block address;

means for looking up a head movement time estimate corresponding to the calculated radial distance in a head movement time estimate table;

means for deriving the estimated access time from the first rotational time estimate, second rotational time estimate and head movement time estimate; and

means for selecting one of a plurality of I/O requests to follow a first I/O request by comparing derived estimated access time for each one of said plurality of I/O requests.

14. The computer system of claim 13, further comprising means for generating the rotational time estimate table;

the generating means comprising;

means for obtaining a completion-time time stamp for each logical block address on the disk;

means for estimating time for the disk to make one revolution from a plurality of completion-time time stamps;

for the first logical block address of each track, means for obtaining a completion-time time stamp for said first logical block address and for a reference logical block address and means for storing rotational time estimate for said first logical block address as a difference between the completion-time time stamp for said first logical block address and said reference logical block address;

for each i-th logical block address of a plurality of logical block address of a given track, means for storing rotational time estimate as the rotational time estimate for the i-1th logical block address plus an incremental time estimate for the i-th logical block address.