Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1997-06-30
2001-10-30
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S151000, C711S152000
Reexamination Certificate
active
06311256
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to mass storage devices, and in particular, to methods and apparatus for improving performance by modifying the controller for a mass storage system.
Disk drive systems have grown enormously in both size and sophistication in recent years. These systems can typically include many large disk drive units controlled by a complex, multi-tasking, disk drive controller such as the EMC Symmetrix disk drive controller. A large scale disk drive system can typically receive commands from a number of host computers and can control a number of disk drive mass storage devices, each mass storage device capable of storing in excess of several gigabits of data.
There is every reason to expect that both the sophistication and the size of the disk drive systems will continue to increase. As the systems increase in complexity, so does the user's reliance upon the system, for fast and reliable recovery and storage of data. Accordingly, the user typically uses data throughput and speed of response as a primary criteria for evaluating performance of the disk drive systems. As a result, mass storage devices and the controllers which drive them have become quite sophisticated in trying to improve command response time. Systems such as the EMC Symmetrix disk drive controller system thus incorporate a large cache memory, and other techniques to improve the system throughput.
SUMMARY OF THE INVENTION
The invention relates to a method and apparatus for reordering, at the disk drive controller, a received sequence of read and write commands. In this manner, the data throughput will advantageously be improved.
The method features the steps of determining any time delays in completing an initiated command at the disk drive controller; initiating, if the time delay exceeds allowed criteria, a next selective command in the received sequence; and completing that next selective command while waiting for at least a portion of the originally initiated command to complete. In this manner, the controller is not idly waiting for a command to complete, but in fact will complete commands in a sequence other than that in which they are received. As a result, throughput through the disk drive controller is increased.
Among the criteria, which would result in taking commands out of order, are the expected time to complete for a command, whether there is a cache miss during a read command, and whether write cache is full.
In another aspect, the method of reordering a received sequence of read and write commands at a disk drive controller features the steps of storing the received read and write commands in a command list or queue in the order that they are received at the controller; adding each newly received command to the end of the command list, the command at the beginning of the list being the next command to be executed; moving a selected command from a position more distant from the beginning of the list to a position less distant from the beginning of the list when that selected command can be executed and completed without substantial delay; and executing a command near the top of the list.
In this particular embodiment of the invention, the method can further feature flagging any command which moves to a position at the beginning of the list (as a result of another command or commands being moved closer to the end of the list), and preventing any flagged command from moving further from the beginning of the list (for any reason). In another aspect, the method further features repeating the moving step a plurality of times and wherein the executing step features the step of executing the write instruction closest to the beginning of the list.
The disk controller of the invention relates to reordering a received sequence of read and write commands to increase their throughput. The disk controller features circuitry for determining any time delays in completing an initiated read or write command, circuitry for initiating, if the time delay meets specified criteria, a next selected command in the received sequence, and circuitry for completing that next selected command while at least a portion of the initiated read or write command is completing. In particular embodiments, the specified criteria can be either an expected time to complete threshold, a cache miss during a read operation, or the inability to write data to destaging memory.
In yet another aspect of the invention, the disk drive controller receives a sequence of read and write commands and features storing the read and write commands in a command list in the order in which they are received, circuitry for adding the newly received commands to the end of the list, the command at the beginning of the list being the next command to be executed, circuitry for moving a selected command from a position more distant from the beginning of the list to a position less distant from the beginning of the list when that selected command can be executed and completed without substantial delay, and circuitry for executing a command near the top of the list.
In particular embodiments, the disk drive controller flags any read or write command which is moved to a position at the beginning of the list from a position more distant from the head of the list and prevents any flagged command from being moved away from the head of the list.
Accordingly, the invention provides improved and increased throughput, through the disk drive controller by reordering the read and write commands from the order in which they are received by the disk drive controller. As a result, “down time” at the controller is minimized, and disk drive instructions are using those system resources which are available.
REFERENCES:
patent: 4855904 (1989-08-01), Daberkow et al.
patent: 5341491 (1994-08-01), Ramanujan
patent: 5455924 (1995-10-01), Shenoy et al.
patent: 5548795 (1996-08-01), Au
patent: 5590379 (1996-12-01), Hassler et al.
patent: 5649157 (1997-07-01), Williams
patent: 5652859 (1997-07-01), Mulla et al.
patent: 5729718 (1998-03-01), Au
patent: 5905998 (1999-05-01), Ebrahim et al.
patent: 5961621 (1999-10-01), Wu et al.
patent: 6047334 (2000-04-01), Langendorf et al.
patent: 6078998 (2000-06-01), Kamel et al.
patent: 6088772 (2000-07-01), Harriman et al.
patent: 6112265 (2000-08-01), Harriman et al.
patent: 6145052 (2000-11-01), Howe et al.
Fitzgerald John T.
Halligan Kenneth A.
Ofer Erez
Bataille Pierre-Michel
EMC Corporation
Fitzgerald, Esq. Leanne J.
Gagne, Esq. Christopher K.
Gunther, Esq. John M.
LandOfFree
Command insertion and reordering at the same storage controller does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Command insertion and reordering at the same storage controller, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Command insertion and reordering at the same storage controller will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2568857