# US 2021/0200586 A1 · Method of scheduling jobs in storage device using pre-defined time and method of operating storage system including the same

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

- Number: US 2021/0200586 A1
- Document ID: US20210200586A1
- Status: Published application
- Kind: A1
- Application number: 17/003,455
- Filed: 2020-08-26
- Published: 2021-07-01
- Earliest claimed: 2019-12-26
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: KYUNGBO YANG; DAEHYUN KIM; DONGIK JEON
- Web page: https://patentgrep.com/patent/US20210200586A1

## CPC

- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0673: {Single storage device}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In a method of scheduling jobs in a storage device, a first job is performed. While the first job is being performed, a first timestamp for the first job is pre-updated based on a pre-defined operation time table that represents a relationship between operations of the storage device and operation times. While the first job is being performed, scheduling requests are received that are associated with a second job to be performed after the first job. While the first job is being performed, a scheduling operation for selecting the second job is pre-performed based on the scheduling requests and the timestamps.

## Claims

### Claim 1

A method of scheduling jobs in a storage device, the method comprising:
pre-defining an operation time table that represents a relationship between a plurality of operations of the storage device and expected operation times thereof;
receiving a plurality of scheduling requests associated with a plurality of timestamps for a plurality of jobs each having at least one operation;
performing a first job from the plurality of jobs having a first operation;
while the first job is being performed, pre-updating a first timestamp for the first job based on the first operation and the pre-defined operation time table; and
while the first job is being performed, pre-performing a scheduling operation for selecting a second job from the plurality of jobs to be performed subsequent to the first job based on the plurality of scheduling requests and the plurality of timestamps.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
the plurality of timestamps correspond to a plurality of job performers,
different weights are assigned to the plurality of job performers, and
the operation times of the plurality of operations of the storage device that are included in the pre-defined operation time table are set differently for the plurality of job performers based on the different weights.

### Claim 3 (depends on 2)

The method of claim 2, wherein the plurality of timestamps represent accumulated times in which the plurality of job performers have used the storage device cumulatively.

### Claim 4 (depends on 3)

The method of claim 3, wherein as the first timestamp is pre-updated while the first job is performed, the plurality of timestamps represent virtual accumulated times in which the plurality of job performers are expected to use the storage device cumulatively.

### Claim 5 (depends on 2)

The method of claim 2, wherein pre-updating the first timestamp for the first job includes:
loading a first operation time from the pre-defined operation time table based on a first job performer of the first job among the plurality of job performers and a type of the first job;
obtaining a predicted execution time of the first job based on a size of the first job and the first operation time; and
adding the predicted execution time of the first job to the first timestamp.

### Claim 6 (depends on 2)

The method of claim 2, wherein the plurality of job performers are a plurality of applications that are different from each other and executed by a storage system including the storage device.

### Claim 7 (depends on 2)

The method of claim 2, wherein the plurality of job performers are a plurality of host devices that are different from each other and allow to access the storage device.

### Claim 8 (depends on 1)

The method of claim 1, wherein the plurality of operations of the storage device include a data read operation, a data write operation and a data erase operation on the storage device.

### Claim 9 (depends on 1)

The method of claim 1, wherein pre-performing the scheduling operation for selecting the second job includes:
searching a second timestamp having a minimum value by comparing the plurality of timestamps with each other; and
selecting a job associated with a scheduling request corresponding to the second timestamp among the plurality of scheduling requests as the second job.

### Claim at position 10

10-11. (canceled)

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
after the first job is completed, performing the second job selected by the scheduling operation.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
while the second job is performed, post-compensating the first timestamp for the first job.

### Claim 14 (depends on 13)

The method of claim 13, wherein post-compensating the first timestamp for the first job includes:
checking whether a first event that delays an execution of the first job occurs during the execution of the first job; and
when the first event occurs, adding a first delay time to the first timestamp, the first delay time representing a time interval in which the execution of the first job is delayed by the first event.

### Claim 15 (depends on 14)

The method of claim 14, wherein post-compensating the first timestamp for the first job further includes:
when the first event occurs, determining whether the first event is an event in which post-compensating is required, and
the first delay time is added to the first timestamp when the first event occurs and when the first event is the event in which the post-compensating is required.

### Claim 16 (depends on 13)

The method of claim 13, further comprising:
while the second job is performed, pre-updating a second timestamp for the second job among the plurality of timestamps based on the pre-defined operation time table.

### Claim 17 (depends on 16)

The method of claim 16, wherein, while the second job is performed, an operation of post-compensating the first timestamp is performed first, and then an operation of pre-updating the second timestamp is performed later.

### Claim 18

(canceled)

### Claim 19 (depends on 1)

The method of claim 1, further comprising:
performing a first scheduling operation for selecting the first job from the plurality of jobs based on a plurality of first scheduling requests and a plurality of first timestamps;
while the first job is being performed, receiving a plurality of second scheduling requests and a plurality of second timestamps associated with a second job to be performed subsequent to the first job;
while the first job is being performed, performing a second scheduling operation for selecting the second job based on the plurality of second scheduling requests and the plurality of second timestamps;
immediately after the first job is completed, performing the second job selected by the second scheduling operation;
while the second job is being performed, post-compensating the first timestamp for the first job; and
while the second job is being performed and after the first timestamp is post-compensated, updating a second timestamp for the second job among the plurality of second timestamps based on the pre-defined operation time table,
wherein each plurality of timestamps corresponds to a plurality of job performers to which different weights are assigned, and
wherein the operation times of the plurality of operations of the storage device that are included in the pre-defined operation time table are set differently for the plurality of job performers based on the different weights.

### Claim 20

A method of operating a storage system that includes at least one host device and a storage device, the method comprising:
performing, by the storage device, a first job;
while the first job is being performed, pre-updating, by the storage device, a first completion timestamp for the first job among a plurality of timestamps based on a pre-defined operation time table that is stored in the storage device and represents a relationship between a plurality of operations of the storage device and predicted operation times thereof;
while the first job is being performed by the storage device, transmitting, by the at least one host device, a plurality of scheduling requests to the storage device, the plurality of scheduling requests being associated with a second job to be performed subsequent to the first job by the storage device; and
while the first job is being performed, pre-performing, by the storage device, a scheduling operation for selecting the second job based on the plurality of scheduling requests and the plurality of timestamps.

### Claim 21

A storage device comprising:
a storage controller connected to at least one non-volatile memory; and
a scheduler connected to the storage controller,
wherein the scheduler is configured for receiving a plurality of scheduling requests associated with a plurality of timestamps for a plurality of jobs each having at least one operation with respect to the at least one non-volatile memory,
wherein the storage controller is configured for performing a first job from the plurality of jobs having a first operation with respect to the at least one non-volatile memory,
wherein the scheduler is further configured for pre-updating a first timestamp for the first job based on the first operation and a pre-defined operation time table, while the first job is being performed,
wherein the scheduler is further configured for pre-performing a scheduling operation for selecting a second job from the plurality of jobs to be performed subsequent to the first job based on the plurality of scheduling requests and the plurality of timestamps, while the first job is being performed, wherein the storage controller is configured for performing the second job from the plurality of jobs having a second operation with respect to the at least one non-volatile memory, immediately after the first job is complete.

### Claim 22

(canceled)

### Claim 23 (depends on 21)

The storage device of claim 21, the scheduler comprising:
the pre-defined operation time table, which represents a relationship between a plurality of operations of the storage device with respect to the at least one non-volatile memory and expected operation times thereof;
a timestamp updater connected to the pre-defined operation time table;
a timestamp buffer connected to the timestamp updater; and
a job selector connected to the timestamp buffer;
wherein the job selector is configured to receive a plurality of scheduling requests to the storage device while the first job is being performed by the storage device.

### Claim 24 (depends on 21)

The storage device of claim 21, the scheduler comprising:
a job selector configured for receiving a plurality of first scheduling requests;
a timestamp buffer configured for storing a plurality of first timestamps associated with the plurality of first scheduling requests;
a timestamp updater configured for updating the plurality of first timestamps based on the pre-defined operation time table, which represents a relationship between a plurality of operations of the storage device and expected operation times thereof,
wherein the job selector is configured for performing a first scheduling operation for selecting the first job from the plurality of jobs based on the plurality of first scheduling requests and the plurality of first timestamps,
wherein the job selector is further configured for receiving a plurality of second scheduling requests and a plurality of second timestamps associated with a second job to be performed subsequent to the first job, while the first job is being performed,
wherein the job selector is further configured for performing a second scheduling operation for selecting the second job based on the plurality of second scheduling requests and the plurality of second timestamps, while the first job is being performed,
wherein the storage device is configured for performing the second job selected by the second scheduling operation, immediately after the first job is completed,
wherein the timestamp updater is further configured for post-compensating the first timestamp for the first job, while the second job is being performed,
wherein the timestamp updater is further configured for updating a second timestamp for the second job among the plurality of second timestamps based on the pre-defined operation time table, while the second job is being performed and after the first timestamp is post-compensated,
wherein each plurality of timestamps corresponds to a plurality of job performers to which different weights are assigned, and
wherein the operation times of the plurality of operations of the storage device that are included in the pre-defined operation time table are set differently for the plurality of job performers based on the different weights.
