Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Utility Patent
1998-03-19
2001-01-02
Gossage, Glenn (Department: 2759)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S112000, C710S005000, C710S006000, C710S039000, C710S054000, C709S241000
Utility Patent
active
06170042
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to data storage systems. More particularly, the present invention relates to methods of sorting and scheduling commands, and data storage systems utilizing the same, in order to minimize command sorting delay times and to enhance system performance.
Computers and other types of host systems read and write data to data storage devices such as disc (or “disk ”) drives. The process of reading data from or writing data to a specific media location is initiated by the host system or device which issues a command across a bus using a defined protocol. Some interface protocols, such as the small computer system interface (SCSI) protocol, allow multiple commands to be queued at the disc drive. In other words, a read or write command can be issued to the disc drive and placed in queue without having to wait for the execution of any outstanding commands to be completed.
Typically, disc drives are adapted to execute the commands in an order which is deemed most appropriate based upon the types of commands in the queue. Intelligent disc controller firmware sorts the commands, using any of a variety of different sorting algorithms, in order to reduce mechanical delays within the drive. Mechanical delays include the times required to seek, to spin to the beginning of a block of data, and to transfer the data associated with the command. Proper sorting of queued commands can dramatically improve the performance of a disc drive data storage system by reducing these mechanical delays.
A significant problem with sorting queued commands is that the sorting process requires many computations. As the size of the queue to be sorted increases, so does the demand for processing power necessary to implement the sorting algorithm. Disc drives typically contain fairly inexpensive microprocessors to control functions of the system such as sorting and execution of commands from the host system. The typical microprocessors used are often incapable of sorting the queued commands fast enough. In order to minimize delays, the microprocessors must be capable of sorting the queued commands and finding the next optimal command to issue during the time that it takes the current command to execute. When many commands must be sorted, the time it takes to perform the sorting algorithm calculations required to determine the next optimal command can exceed the mechanical delays associated with execution of the current command. When this happens, a delay occurs between the completion of the current command and the start of the next command. The occurrence of this type of delay causes serious performance degradation of the disc drive.
The present invention provides a solution to this and other problems, and offers other advantages over the prior art.
SUMMARY OF THE INVENTION
The present invention relates to data storage systems and apparatus, such as disc drive data storage systems, in which commands to be executed are stored in one or more queues.
In accordance with one embodiment of the invention, a data storage system and method of scheduling in the same are provided in which commands are stored in a command sort queue and a scheduled command queue. Commands in the command sort queue are sorted and assigned a priority. Eventually, commands in the command sort queue are transferred to the scheduled command queue. Commands in the scheduled command queue are executed without further sorting. The desired queue depth of the scheduled command queue is determined as a function of both the queue depth of the command sort queue and of a command execution rate value which is indicative of the rate at which commands in the scheduled command queue are executed.
REFERENCES:
patent: 5220653 (1993-06-01), Miro
patent: 5561456 (1996-10-01), Yu
patent: 5570332 (1996-10-01), Heath et al.
patent: 5687390 (1997-11-01), McMillan, Jr.
patent: 5802394 (1998-09-01), Baird et al.
Gaertner Mark A.
Heath Mark A.
Pruett David C.
Gossage Glenn
Seagate Technology LLC
Westman Champlin & Kelly P.A.
LandOfFree
Disc drive data storage system and method for dynamically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Disc drive data storage system and method for dynamically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disc drive data storage system and method for dynamically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2524095