 |
|
|
|
|
|
 Title: |
US5548795:
Method for determining command execution dependencies within command queue reordering process
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Au, Wing Y.; 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: |
1996-08-20
/ 1994-03-28
|
| Application Number: |
US1994000218567
|
| IPC Code: |
Advanced:
G06F 3/06;
Core:
more...
IPC-7:
G06F 12/02;
|
| ECLA Code: |
G06F3/06M;
|
| U.S. Class: |
Current:
710/052;
710/003;
711/004;
Original:
395/872;
395/404;
395/823;
364/DIG.1;
364/236.2;
364/239.7;
|
| Field of Search: |
364/200 MS File,900 MS File
369/018
360/055,86,97.01,135,55
395/404,439-441,823,872
|
| Priority Number: |
| 1994-03-28 |
US1994000218567 |
|
| Abstract: |
A disk drive command queue reordering method includes calculation of least-latency and accounts for dependencies of I/O commands in the queue to avoid data hazards with respect to reordering of I/O commands. Command queue representation is augmented by a graph structure representing dependencies of queue commands. Computational overhead associated with constructing, maintaining, and executing graph flow analysis relative to the dependency graph is sufficiently low to allow interleaved operation with higher level disk drive functions such as timely interaction with the host device. The disclosure includes a method of calculating and maintaining the dependency information in a command queue and using this information to constrain command reordering in a time and computationally efficient manner.
|
| Attorney, Agent or Firm: |
Harrison, David B. ;
|
| Primary / Asst. Examiners: |
Kim, Matthew M.;
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 11 claims |
What is claimed is:
1. A method of managing a command queue within a storage device defining a multiplicity of block addresses for storing user data blocks and receiving into the command queue a group of presently unexecuted input/output (I/O) commands for the device from a host system, the method comprising the steps:
- maintaining a sequential ordering of said group of commands within the command queue;
- maintaining command execution dependency relation information for each command of said group, each dependency relation indicating an overlap of block addresses between a given command and other commands within the group;
- identifying a set of independent commands within the group as having no block address overlap relative to other commands within the group; and
- selecting one of said independent commands for promotion to a command execution position within the command queue, said selected independent command determined by the device to be a least-latent one of said independent commands relative to a head-of-queue command presently being executed within the storage device.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 48 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G96-392971
DERG96-392971
|
| Other References: |
Spencer W. Ng, Improving Disk Performance Via Latency Reduction, IEEE Transactions on Computers, vol. 40, No. 1, pp. 22-30, Jan. 1991.
(9 pages)
Cited by 5 patents
[ISI abstract]
Charles J. Sippl, Microcomputer Dictionary and Guide, p. 318, 1975.
E. M. McGraw, Priority Circuit for Servicing Requests Queued by Sector, , IBM Technical Disclosure Bulletin, vol. 12, No. 6, Nov. 1969, pp. 815-819.
Margo Seltzer, Disk Scheduling Revisited, USENIX-Winter 1990, pp. 313-324.
Denning, "Effects of Scheduling on File Memory",AFIPS Joint Compuer Conference Proc. vol. 30, 1967, pp. 9-21.
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.
Cited by 5 patents
|
|
 Nominate this for the Gallery...
|
|
