Two-dimensional execution queue for host adapters

• US 6,609,161 B1
• Filed: 06/01/2000
• Issued: 08/19/2003
• Est. Priority Date: 06/01/2000
• Status: Expired due to Term

• Current Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Young, B. Arlen
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mai, Rijue
• Application Number:
  US09/587,538
• Time in Patent Office: 1,174 Days
• Field of Search: 710/5, 710/24, 710/39, 710/53, 710/100, 710/112, 710/36, 710/38, 710/22, 710/31, 712/225, 712/245, 711/147, 711/128, 711/170
• US Class Current: 710/5
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

Abstract

A two-dimensional hardware control block execution queue facilitates multiple command delivery to a single target device over an I/O bus, such as a SCSI bus. The two-dimensional hardware control block execution queue includes a plurality of target queues where each target queue includes at least one hardware control block. Each of target queues is a queue of hardware command blocks, e.g., SCSI control blocks (SCBs) for a specific target device on the I/O bus. There is only one target queue for each target device. One head hardware control block, and only one head hardware control block of each target queue, is included in a common queue. When a selection is made by a host adapter for a target device based upon a hardware control block addressed by a head pointer to the common queue, all hardware control blocks in the target queue within the two-dimensional hardware control block queue, which are accepted by the target device, are transferred to the target device. If there are more hardware control blocks in the target queue than are accepted by the target device, the target queue is moved to the end of two-dimensional queue, and a common queue tail pointer is changed to address the first hardware control block in the moved target queue, and the common queue head pointer is moved to address the first hardware control block in the next target queue with the head hardware control block in the common queue.

Claims

1. In a memory, a command block execution queue comprising:

a plurality of command blocks in a first linked list;

another plurality of command blocks in a second linked list, where only one of said another plurality of command blocks is included in said plurality of command blocks in said first linked list; and

a tail pointer to a tail command block in said second linked list wherein said tail pointer is an only delimiter for said second linked list.

2. The command block execution queue as in claim 1 further comprising:

a head pointer to a head command block in said first linked list.

3. The command block execution queue as in claim 2 further comprising:

a tail pointer to a tail command block in said first linked list.

4. A command block execution queue comprising:

a common linked list of command blocks having a common head command block and a common tail command block;

a head pointer to said common head command block;

a tail pointer to said common tail command block;

a target linked list of command blocks having a target head command block and a target tail command block wherein only said target head command block is included in said common linked list of command blocks; and

a tail pointer to said target tail command block wherein said tail pointer to said target tail command block is an only delimiter of said target linked list of command blocks.

5. The command block execution queue of claim 4 wherein each command block includes a command for a target device, and further wherein said common linked list contains a maximum of one command block for a target.

6. The command block execution queue of claim 5 wherein said target linked list contains only command blocks for a single target device.

7. The command block execution queue of claim 4 further comprising:

another target linked list of command blocks having another target head command block and another target tail command block wherein only said another target head command block is included in said common linked list of command blocks.

8. The command block execution queue of claim 7 further comprising:

another tail pointer to said another target tail command block.

9. The command block execution queue of claim 8 wherein said tail pointer and said another tail pointer are included in a list of tail pointers.

10. A command block execution queue comprising:

a common linked list of command blocks having a common head command block and a common tail command block;

a head pointer to said common head command block;

a tail pointer to said common tail command block;

a target linked list of command blocks having a target head command block and a target tail command block wherein only said target head command block is included in said common linked list of command blocks;

a tail pointer to said target tail command block;

another target linked list of command blocks having another target head command block and another target tail command block wherein only said another target head command block is included in said common linked list of command blocks; and

another tail pointer to said another target tail command block,

wherein said tail pointer and said another tail pointer are included in a list of tail pointers; and

each command block includes a command for a target device having an identification number and further wherein said target linked list contains only command blocks for a single target device having a first identification number, and said another target linked list contains only command blocks for another single target device having a second identification number.

11. The command block execution queue of claim 10 wherein said tail pointer is stored in said list of tail pointers at a location determined by said first identification number.

12. The command block execution queue of claim 10 wherein said another tail pointer is stored in said list of tail pointers at a location determined by said second identification number.

13. A method of managing command block execution queue where each command block is associated with one of a plurality of target devices, the method comprising:

testing a predefined location in a list of target tail pointers to determine whether a target queue exists for a target device specified in a hardware command block;

appending said hardware command block to a tail of the target queue for said target device upon said testing indicating that the target queue exists; and

appending said hardware command block to a tail of a common queue upon said testing indicating that the target queue does not exist.

14. A method of managing command block execution queue where each command block is associated with one of a plurality of target devices, the method comprising:

appending a new command block to a common tail command block of a common linked list of command blocks when said new command block is associated with a target device different from the target devices associated with the command blocks included in said common linked list of command blocks; and

appending said new command block to a target tail command block of a target linked list of command blocks when said new command block is associated with a target device which is a same target device as that associated with one of the command blocks included in said common linked list of command blocks wherein only one target command block of said target linked list is included in said common linked list of command blocks.