 |
|
|
|
|
|
 Title: |
US5729718:
System for determining lead time latency as function of head switch, seek, and rotational latencies and utilizing embedded disk drive controller for command queue reordering
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Au, Wing Yee; Sunnyvale, CA
|
| Assignee: |
Quantum Corporation, Milpitas, CA
other patents from QUANTUM CORP. (CA) (460700) (approx. 382)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-03-17
/ 1996-05-01
|
| Application Number: |
US1996000641662
|
| IPC Code: |
Advanced:
G11B 5/012;
Core:
more...
IPC-7:
G06F 13/28;
G11B 5/012;
|
| ECLA Code: |
G11B5/012;
|
| U.S. Class: |
Current:
711/167;
360/048;
710/005;
710/039;
711/111;
G9B/005.024;
Original:
395/494;
395/438;
395/825;
395/859;
360/098;
360/048;
369/047;
369/178;
|
| Field of Search: |
395/602,438,440,494,825,844,859
360/098,48
369/047,178
|
| Priority Number: |
| 1996-05-01 |
US1996000641662 |
| 1993-11-10 |
US1993000149982 |
|
| Abstract: |
A method for reordering a queue of disk storage input/output (I/O) transfer commands for a hard disk drive. "Lead time" latencies are calculated for the commands in the queue with respect to the active command. The command with the least lead time latency is selected and promoted to first in the queue. Lead time is seek time plus rotational latency. Lead time may be calculated as the time required for n revolutions of the disk, where the seek time is greater than that time, but less than that required for n+1 revolutions of the disk, plus the rotational time that is required to move from the ending angular position of the active command to the beginning angular position of the subsequent command. In a preferred embodiment, the calculations of lead time are performed in two stages. The first stage determines the beginning and ending physical locations of the I/O transfers for the commands in the queue. These locations do not change for a command and thus these calculations need be performed only once per command. The second stage determines the lead time for each command in the queue with respect to the active command. These values change for each active command and thus must be determined for each command in the queue every time a new command becomes active.
|
| Attorney, Agent or Firm: |
Harrison, David B. ;
|
| Primary / Asst. Examiners: |
Shin, Christopher B.; Perveen, Rehana
|
| INPADOC Legal Status: |
Show legal status actions
|
|
|
|
|
|
|
| Parent Case: |
REFERENCE TO RELATED APPLICATION
This is a continuation of application Ser. No. 08/149,982 filed on Nov. 10, 1993, now abandoned.
|
| Family: |
None
|
First Claim:
Show all 9 claims |
What is claimed is:
1. A method for reordering a queue of disk storage input/output transfer commands with respect to an active command within a disk drive data storage device having an on-board embedded programmed digital controller and an interface for receiving the commands, the method comprising the steps of:
- (a) receiving a first plurality of arbitrary length input/output transfer commands into the interface, and decoding and queuing each of the commands within the device by the embedded controller initially in order of receipt from a host computer as a real time process;
- (b) determining a lead time latency for the first plurality of the commands in the queue relative to completion of the active command as a non-real time, background process by the embedded controller wherein the lead time latency is determined as a function of head switch, seek, and rotational latencies of the disk drive data storage device;
- (c) determining which of the first plurality of the commands has a least lead time latency as a non-real time, background process by the embedded controller;
- (d) promoting within the queue as a non-real time, background process by the embedded controller a command determined in step (c) to have the least lead time latency to a position within the queue to be executed immediately following completion of execution of the active command as a real time process by the embedded controller,
- (e) executing the command promoted in step (d) as a real time process by the embedded controller immmediately following execution of the active command,
- (f) receiving an additional command from the host at the interface, and decoding and queuing the additional command within the queue to form a second plurality of the commands awaiting execution as a real time process by the embedded controller,
- (g) redetermining a command within the second plurality having the least lead time latency as a non-real time, background process by the embedded controller,
- (h) promoting a command determined in step (g) to have the least lead time latency to a position within the queue of the second plurality to be executed immediately following execution the command promoted in step (d) as a non-real time, background process by the embedded controller.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 74 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
|
| Other References: |
Abbot et al, "Scheduling I/O Requests with Deadlines: A Performance Evalua", Dec. 5-7, 1990 pp. 116-117, IEEE: Real-Time Systems, 1990 Symposium.
Ng, "Improving Disk Performance via Latency Reduction", Jan. 1991, pp. 22-24, IEEE Transactions on Computers.
(9 pages)
Cited by 5 patents
[ISI abstract]
Salem, "Performance Evaluation of Movable Head Disk Schedules", Sep. 16-18, 1991 pp. 250-253 Software Engineering for Real Time Systems (IEE Conf. Pub. 344).
IBM Technical Disclosure Bulletin, "Enhanced Disk Task Sequencing", Oct. 1986, pp. 1946-1948, vol. 29, No. 5.
McGraw et al (IBM TDB), "Priority Circuit Servicing Requests Queued by Sector", Nov. 1969, pp. 815-819, vol. 12, No. 6.
Seltzer et al, "Disk Scheduling Revisited", Jan. 1990, pp. 313-323, USENIX Winter 1990 Washington, DC.
Gibson, Redundant Disk Arrays--Reliable, Parallel Secondary Storage, MIT Press, Cambridge MA, ©1992, pp. 17-20: "Lowering I/O Response Time".
Geist & Daniel, "A Continuum of Disk Scheduling Algorithms", ACM Trans. Computer Systems, vol. 5, No. 1, Feb. 1987, pp. 77-92.
(16 pages)
Cited by 3 patents
Teory & Pinkerton, "A Comparative Analysis of Disk Scheduling Policies", Comm. of the ACM, vol. 15, No. 3, Mar. 1972, pp. 177-184.
Denning, "Effects of Scheduling on File Memory", AFIPS Joint Computer Conference Proc. vol. 30, 1967, pp. 9-21.
|
|
 Nominate this for the Gallery...
|
|
