Browse Prior Art Database

Avoiding Disk Elevator Queue Starvation Disclosure Number: IPCOM000229357D
Publication Date: 2013-Jul-23
Document File: 3 page(s) / 28K

Publishing Venue

The Prior Art Database


Disclosed is a method for avoiding command starvation when using an elevator queue data structure to organize and process queued data elements, such as pending commands to a disk drive. This method retains most of the advantages gained by using an elevator queue while guaranteeing that elements of the queue will not be delayed indefinitely.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 33% of the total text.

Page 01 of 3

Avoiding Disk Elevator Queue Starvation

A data structure known as an elevator queue allows sorting pending elements, to allow processing them in order as much as possible. A common use of this type of data queue is in the software that processes commands for a disk. Pending commands are placed on the elevator queue whenever the disk is busy and cannot process new commands. As the disk completes active commands, new commands are issued to it from the elevator queue. The rest of this article assumes the elevator queue is used by a SCSI disk driver, though this technique could be applied to any use of an elevator queue.

A disk elevator queue typically contains a list of pending disk operations, ordered by the block number of the associated operation. The operations are serviced in ascending order by block number until the end of the queue is reached, at which time processing continues at the beginning of the queue, with the operation that has the lowest block number. This algorithm has two advantages over an algorithm that uses a simple LIFO queue, which services the operations in the order that they arrive in the SCSI disk driver.

1) The elevator queue facilitates coalescing multiple operations into a single SCSI command. For example, if the operations "read block 1", "read block 7" and "read block 2" arrive, by sorting the operations by block number, the driver can easily determine that the first and third operation could be coalesced into one SCSI command to read two blocks starting at block 1. Performing a single SCSI command to read two blocks is more efficient than performing two single-block read operations. Sending one command versus two is also preferred because disk drives typically allow only a limited number of commands to be active concurrently. Coalescing two requests into one command makes better use of the limited queue depth of the disk.

2) Ordering operations reduces disk seek time by grouping operations that are physically near each other on the disk medium.

However, in certain situations, this algorithm could lead to some operations being starved, and staying on the elevator queue for an extended period of time. Also, if the elevator queue grows large, the time to insert an incoming operation may become unreasonable. A previous patent (8135924 b2) resolved that issue. But the algorithm described in this disclosure would also solve the issue resolved by the referenced patent in addition to solving the starvation issue described here, while still allowing some ordering of the pending commands.

Simple Elevator Queue Operation

A simple disk elevator queue algorithm places all new operations into the elevator queue in order based on the block number of the operation. Thus the elevator queue is a linked list of operations ordered by block number. The queue can be defined by three pointers, low, current, and high.

The low and high pointers point to the first and last elements of the queue and the current pointer points...