# US 11,010,099 B1 · Data storage device executing access commands based on leapfrog sort

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,010,099 B1
- Document ID: US11010099B1
- Status: Granted
- Kind: B1
- Application number: 16/688,853
- Filed: 2019-11-19
- Published: 2021-05-20
- Granted: 2021-05-18
- Earliest claimed: 2019-11-19
- Assignees: Western Digital Technologies, Inc.
- Applicants: Western Digital Technologies, Inc.
- Inventors: David R. Hall
- Web page: https://patentgrep.com/patent/US11010099B1

## CPC

- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0676: {Magnetic disk device}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0674: {Disk device}
- G11B 2020/10638: {First-in-first-out memories [FIFO] buffers}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)

## Abstract

A data storage device is disclosed comprising a head actuated over a non-volatile storage medium. A plurality of access commands are received from a host and sored in a host queue and a pending queue. A first access command is selected from the host queue, wherein the first access command having a first execution time needed to execute the first access command. When a second access command in the pending queue can be executed within the first execution time, the second access command is executed, and after executing the second access command, the first access command in the host queue is executed. After selecting the first access command from the host queue, a third access command is transferred from the pending queue to the host queue based on a first-in-first-out (FIFO) order of the pending queue.

## Claims

### Claim 1

A data storage device comprising:
a non-volatile storage medium;
a head actuated over the non-volatile storage medium; and
control circuitry configured to:
receive a plurality of access commands from a host;
store at least one of the access commands in a host queue and store at least one of the access commands in a pending queue;
select a first access command from the host queue, wherein the first access command having a first execution time needed to execute the first access command;
when a second access command in the pending queue can be executed within the first execution time, execute the second access command;
after executing the second access command, execute the first access command in the host queue; and
after selecting the first access command from the host queue, transfer a third access command from the pending queue to the host queue based on a first-in-first-out (FIFO) order of the pending queue.

### Claim 2 (depends on 1)

The data storage device as recited in claim 1, wherein:
executing the second access command creates a free hole command in the pending queue; and
when the free hole command reaches the host queue, the control circuitry is further configured to execute a fourth access command in the pending queue in place of the free hole command.

### Claim 3 (depends on 2)

The data storage device as recited in claim 2, wherein the fourth access command is the next access command in the FIFO order of the pending queue.

### Claim 4 (depends on 2)

The data storage device as recited in claim 2, wherein fourth access command is out of the FIFO order of the pending queue, thereby creating an early hole command in the pending queue.

### Claim 5 (depends on 1)

The data storage device as recited in claim 1, wherein:
executing the second access command creates a free hole command in the pending queue; and
when the free hole command reaches the host queue, the control circuitry is further configured to execute a fourth access command and a fifth access command in place of the free hole command and within a second execution time associated with executing the second access command in the FIFO order.

### Claim 6 (depends on 5)

The data storage device as recited in claim 5, wherein the second execution time associated with executing the second access command in the FIFO order is an actual execution time of the second access command.

### Claim 7 (depends on 5)

The data storage device as recited in claim 5, wherein the second execution time associated with executing the second access command in the FIFO order is an average execution time of the access commands.

### Claim 8 (depends on 1)

The data storage device as recited in claim 1, wherein the control circuitry is further configured to:
store at least two access commands in the host queue;
sort the at least two access commands in the host queue into an execution order based on a rotation-position-optimization algorithm; and
select the first access command based on the execution order.

### Claim 9 (depends on 1)

The data storage device as recited in claim 1, wherein the control circuitry is further configured to:
receive a configuration command from the host to emulate a depth of a host-only queue in the absence of the pending queue; and
process the plurality of access commands received from the host using the host queue and the pending queue in order to emulate the depth of the host-only queue.

### Claim 10

A data storage device comprising:
a non-volatile storage medium;
a head actuated over the non-volatile storage medium; and
control circuitry configured to:
receive a plurality of access commands from a host;
store at least one of the access commands in a host queue and store at least one of the access commands in a pending queue;
execute a first access command in the host queue within a first execution time needed to execute the first access command; and
during the first execution time, execute a second access command in the pending queue.

### Claim 11 (depends on 10)

The data storage device as recited in claim 10, wherein after executing the first access command and the second access command, the control circuitry is further configured to:
transfer a third access command from the pending queue to the host queue based on a first-in-first-out (FIFO) order of the pending queue; and
execute the third access command in the host queue.

### Claim 12 (depends on 11)

The data storage device as recited in claim 11, wherein:
executing the second access command creates a free hole command in the pending queue; and
when the free hole command reaches the host queue, the control circuitry is further configured to execute a fourth access command in the pending queue in place of the free hole command.

### Claim 13 (depends on 12)

The data storage device as recited in claim 12, wherein the fourth access command is the next access command in the FIFO order of the pending queue.

### Claim 14 (depends on 12)

The data storage device as recited in claim 12, wherein fourth access command is out of the FIFO order of the pending queue, thereby creating an early hole command in the pending queue.

### Claim 15 (depends on 11)

The data storage device as recited in claim 11, wherein:
executing the second access command creates a free hole command in the pending queue; and
when the free hole command reaches the host queue, the control circuitry is further configured to execute a fourth access command and a fifth access command in place of the free hole command and within a second execution time associated with executing the second access command in the FIFO order.

### Claim 16 (depends on 10)

The data storage device as recited in claim 10, wherein the control circuitry is further configured to:
store at least two access commands in the host queue;
sort the at least two access commands in the host queue into an execution order based on a rotation-position-optimization algorithm; and
execute the first access command based on the execution order.

### Claim 17 (depends on 10)

The data storage device as recited in claim 10, wherein the control circuitry is further configured to:
receive a command from the host to emulate a depth of a host-only queue in the absence of the pending queue; and
process the plurality of access commands received from the host using the host queue and the pending queue in order to emulate the depth of the host-only queue.

### Claim 18

A data storage device comprising:
a non-volatile storage medium;
a head actuated over the non-volatile storage medium;
a means for receiving a plurality of access commands from a host;
a means for storing at least one of the access commands in a host queue and storing at least one of the access commands in a pending queue;
a means for executing a first access command in the host queue within a first execution time needed to execute the first access command; and
during the first execution time, a means for executing a second access command in the pending queue.

### Claim 19 (depends on 18)

The data storage device as recited in claim 18, wherein after executing the first access command and the second access command, further comprising:
a means for transferring a third access command from the pending queue to the host queue based on a first-in-first-out (FIFO) order of the pending queue; and
a means for executing the third access command in the host queue.

### Claim 20 (depends on 19)

The data storage device as recited in claim 19, wherein:
executing the second access command creates a free hole command in the pending queue; and
when the free hole command reaches the host queue, further comprising a means for executing a fourth access command in the pending queue in place of the free hole command.