Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
2000-01-28
2002-12-17
Portka, Gary J (Department: 2187)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C711S112000
Reexamination Certificate
active
06496877
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the data processing field, and more particularly, relates to a method and apparatus for scheduling data accesses for random access storage devices with a shortest access chain scheduling algorithm.
DESCRIPTION OF THE RELATED ART
In random access storage devices, such as hard disk and CD-ROM drives, the data to be accessed next is chosen from a list of outstanding commands. The list of outstanding commands is referred to as a queue. The act of choosing the next command is known as scheduling. In general, the goal of the scheduling algorithm is to minimize the average access time for its commands. Many scheduling methods have been used including Shortest-Seek First (SSF), Shortest-Latency First (SLF), and Shortest-Access Time First (SATF). These algorithms share one thing in common, they only look at what the next command will be when choosing the best candidate. This is similar to a chess player only looking at the next move to make without considering his opponent's next move. In the case of a chess player, only looking one move ahead results in poor play. In the case of scheduling commands, this results in poor performance.
A need exists for an improved scheduling algorithm for random access storage devices.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide a method and apparatus for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm. Other important objects of the present invention are to provide such a method and apparatus for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm substantially without negative effect; and that overcome many of the disadvantages of prior art arrangements.
In brief, a method and apparatus are provided for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm. A plurality of possible chains for a queue of commands are processed. The plurality of possible chains are compared to identify one of the plurality of possible chains having a predetermined property. A first command of the identified one chain is selected as a next command to execute.
In accordance with features of the invention, the predetermined property includes, for example, a shortest access time or a lowest energy usage.
REFERENCES:
patent: 5367669 (1994-11-01), Holland et al.
patent: 5570332 (1996-10-01), Heath et al.
patent: 6029163 (2000-02-01), Ziauddin
patent: 6145052 (2000-11-01), Howe et al.
patent: 6154739 (2000-11-01), Wrobel
patent: 6170042 (2001-01-01), Gaertner et al.
patent: 6272473 (2001-08-01), Sandholm
patent: 6272565 (2001-08-01), Lamberts
Teorey, Toby J., et al., “A Comparative Analysis of Disk Scheduling Policies”, Communications of the ACM, 1972, pp. 177-184.*
Andrews, Matthew, et al., “New Algorithms for the Disk Scheduling Problem”, IEEE, 1996, pp. 550-559.
Greenberg Richard
Hall David Robison
Pennington Joan
Portka Gary J
LandOfFree
Method and apparatus for scheduling data accesses for random... 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 apparatus for scheduling data accesses for random..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for scheduling data accesses for random... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984536