Systems and methods for dynamically determining a priority for a queue of commands

Patent metadata

Field	Value
Publication number	US-9411753-B2
Application number	US-201514861168-A
Country	US
Kind code	B2
Filing date	Sep 22, 2015
Priority date	Jan 27, 2012
Publication date	Aug 9, 2016
Grant date	Aug 9, 2016

Abstract

System and methods are provided for dynamically managing a first-in/first-out (FIFO) command queue of a system controller. One or more commands are received into the command queue, a command being associated with a priority parameter. A current command first in line to be executed in the command queue is determined, the current command being associated with a first priority parameter. A second command associated with a second priority parameter is determined, the second priority parameter being largest among priority parameters associated with the one or more commands. A final priority parameter for the current command is computed based at least in part on the second priority parameter.

First claim

The invention claimed is:

1. A method comprising:
receiving at least three commands into a queue, wherein each command respectively has a corresponding priority, and wherein the at least three commands include
(i) a first command that is first in line in the queue to be executed, and
(ii) a second command that is second in line in the queue to be executed;

determining a first priority for the queue as a function of the priority of the first command;
scheduling execution of the first command from the queue based on the first priority;
executing the first command, resulting in the second command replacing the first command as the first in line in the queue to be executed; and
in response to the second command replacing the first command as the first in line to be executed, determining a second priority for the queue, in place of the first priority, as a function of the priority of the second command.

2. The method of claim 1 , wherein:
the queue includes a highest-priority command that is later in the queue than the second command and whose corresponding priority is the highest priority in the queue;
the first priority is a function of both (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of both (i) the priority of the second command and (ii) the priority of the highest-priority command.

3. The method of claim 2 , wherein:
the first priority is a function of only (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of only (i) the priority of the second command and (ii) the priority of the highest-priority command.

4. The method of claim 3 , wherein:
the first priority is a function of a sum of (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of a sum of (i) the priority of the second command and (ii) the priority of the highest-priority command.

5. The method of claim 1 , wherein the second priority is lower than the first priority.

6. The method of claim 1 , further comprising, after the determining of the second priority and before the second command is executed:
adding, to the queue, a new command; and
in response to the adding, determining a third priority for the queue as a function of the new command, with the third priority exceeding the second priority.

7. The method of claim 1 , further comprising, after the determining of the second priority:
determining a wait time indicating an amount of time a highest priority command in the queue has been in the queue;
if the wait time exceeds the threshold, revising the second priority to equal the priority of the highest priority command in the queue.

8. An integrated circuit comprising:
a memory configured to receive at least three commands into a queue, wherein each command respectively has a corresponding priority, and wherein the at least three commands include
(i) a first command that is first in line in the queue to be executed, and
(ii) a second command that is second in line in the queue to be executed;

an arbitrator configured to determine a first priority for the queue as a function of the priority of the first command;
a scheduler configured to schedule execution of the first command from the queue based on the priority of the queue;
a processor configured to execute the first command, resulting in the second command replacing the first command as the first in line in the queue to be executed; and
the arbitrator being further configured to, in response to the second command replacing the first command as the first in line to be executed, determine a second priority for the queue, in place of the first priority, as a function of the priority of the second command.

9. The integrated circuit of claim 8 , wherein:
the queue includes a highest-priority command that is later in the queue than the second command and whose corresponding priority is the highest priority in the queue;
the first priority is a function of both (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of both (i) the priority of the second command and (ii) the priority of the highest-priority command.

10. The integrated circuit of claim 9 , wherein:
the first priority is a function of only (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of only (i) the priority of the second command and (ii) the priority of the highest-priority command.

11. The integrated circuit of claim 10 , wherein:
the first priority is a function of a sum of (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of a sum of (i) the priority of the second command and (ii) the priority of the highest-priority command.

12. The integrated circuit of claim 8 , wherein the second priority is lower than the first priority.

13. The integrated circuit of claim 8 , wherein the arbiter is configured to, after the determining of the second priority and before the second command is executed, in response to a new command being added to the queue, determine a third priority for the queue, wherein the third priority exceeds the second priority.

14. The integrated circuit of claim 8 , wherein:
the integrated circuit is configured to determine a wait time indicating an amount of time a highest priority command in the queue has been in the queue, and
wherein the arbitrator is configured to, after the determining of the second priority, if the wait time exceeds a threshold, determine the third priority as equal to the priority of the highest priority command in the queue.

15. A non-transitory processor readable medium storing instructions configured to be executed by one or more processors to:
receive at least three commands into a queue, wherein each command respectively has a corresponding priority, and wherein the at least commands include
(i) a first command that is first in line in the queue to be executed, and
(ii) a second command that is second in line in the queue to be executed;

determine a first priority for the queue as a function of the priority of the first command;
schedule execution of the first command from the queue based on the first priority;
execute the first command, resulting in the second command replacing the first command as the first in line in the queue to be executed; and
in response to the second command replacing the first command as the first in line to be executed, determine a second priority for the queue, in place of the first priority, as a function of the priority of the second command.

16. The processor readable medium of claim 15 , wherein:
the queue includes a highest-priority command that is later in the queue than the second command and whose corresponding priority is the highest priority in the queue;
the first priority is a function of both (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of both (i) the priority of the second command and (ii) the priority of the highest-priority command.

17. The processor readable medium of claim 16 , wherein:
the first priority is a function of only (i) the priority of the first command and (ii) the priority of the highest-priority command; and
the second priority is a function of only (i) the pr

Assignees

• Marvell World Trade Ltd

Inventors

• Zhu Jun
• Cao Joseph Jun
• Yang Tsung-Ju
• Lu Ruoyang

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F13/1642 Primary

  with request queuing · CPC title

• G06F3/0659 Primary

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/061

  Improving I/O performance · CPC title