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

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.

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.

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.

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.

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.

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.