Browse Prior Art Database

Device Queue Management

IP.com Disclosure Number: IPCOM000034498D
Original Publication Date: 1989-Mar-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 5 page(s) / 64K

Publishing Venue

IBM

Related People

Bakke, BE: AUTHOR

Abstract

This invention provides a single queuing structure which combines the features of: * First-in, first-out (FIFO) queuing * Last-in, first-out (LIFO) queuing * Elevator seek command prioritization queuing This queuing structure allows sequence independent commands that are received after sequence dependent commands to be reprioritized among themselves. This invention also provides storage management functions and system level command, device level command, and error recovery command transparency. Command queuing is a method of increasing throughput in an I/O subsystem. Queuing allows command preprocessing to occur in parallel with seek operations, thus minimizing the device idle time between commands.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 40% of the total text.

Page 1 of 5

Device Queue Management

This invention provides a single queuing structure which combines the features of: * First-in, first-out (FIFO) queuing

* Last-in, first-out (LIFO) queuing

* Elevator seek command prioritization queuing This queuing structure allows sequence independent commands that are received after sequence dependent commands to be reprioritized among themselves. This invention also provides storage management functions and system level command, device level command, and error recovery command transparency. Command queuing is a method of increasing throughput in an I/O subsystem. Queuing allows command preprocessing to occur in parallel with seek operations, thus minimizing the device idle time between commands. Queuing also allows implementation of various command priority schemes (shortest seek distance, elevator sort, etc.) to efficiently utilize the attached devices.

(Image Omitted)

No one single queuing scheme fits the requirements placed on multi-tasking I/O processors: 1. Non-sequence dependent system level commands should

be reprioritized to make efficient use of the subsystem

resources. This requirement can be met with an

elevator sort scheme.

2. Sequence dependent system level commands must not

execute prior to any previous system level commands.

System level commands preceding a sequence dependent

command must not execute prior to the sequence

dependent system level command. This requirement can

be met with a FIFO scheme. 3. Error recovery commands

must be executed immediately following the command that

failed. A single failure can require multiple error

recovery commands to be issued. This requirement can

be met with a LIFO scheme.

(Image Omitted)

This invention describes a queuing scheme that

allows sequential (i.e., FIFO and LIFO) and

reprioritizable operations to reside on the same queue

without having parasitic effects on each other. In

Fig. 1, Frame A represents error recovery operations

that have been queued using a LIFO scheme. Frame B

would be a group of system level commands that have

been prioritized to efficiently utilize the attached

device. Frame C is a sequence dependent system command

that was received after the commands in Frame B. Frame

D contains system commands received after those in

Frame C. Commands in Frame D are reprioritized among

1

Page 2 of 5

themselves. Device Queue Management is implemented using two sub-queues and a control structure (Fig. 2). The Active Queue contains all device level commands that are waiting to be executed. The Free Queue contains storage that is available for future device level commands. The control structure (Queue Status Block) contains pointers to the Head and Tail of the Active Queue, the Logical Block address of the currently executing device level command, a pointer to the Free Queue, and a count of the size of the Free Queue. The Active Queue is implemented as a doubly linked list (Fig. 2). The next device command to be issued is taken off the active...