DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Objections
Claims 4 and 15 objected to because of the following informalities: The limitation “if the target number does not exceed a maximum single task extraction number of the current task scheduling queue, and a sum of the number of tasks to be executed extracted from the current task scheduling queue to the task execution queue and the target number does not exceed the maximum number of tasks to be executed that can be extracted from the current task scheduling queue to the task execution queue, select the target number of tasks to be executed from the current task scheduling queue as the selected tasks to be executed;” appears to have an additional word “executed” before the word “extracted” based on the following limitation which uses similar phrasing in the same claim: “…and a sum of the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue…” Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: “a task scheduling queue obtainer,” “a task execution queue obtainer,” “a calculator” and “a selector” in claim 12. The terms “a task scheduling queue obtainer,” “a task execution queue obtainer,” “a calculator” and “a selector” are generic placeholders coupled to the functional language “configured to… obtain/calculate/select” and the generic placeholders are not preceded by a structural modifier.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim 7 recites the limitation "the single maximum number of tasks extracted corresponding to the target task scheduling queue" in “wherein an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue.” There is insufficient antecedent basis for this limitation in the claim as the term "the single maximum number of tasks extracted corresponding to the target task scheduling queue" is not previously mentioned either earlier in claim 7 or in claims 6, 3, or 1.
With regards to Claim 18, the method of Claim 7 performs the same steps as the machine of Claim 18, and Claim 18 is therefore rejected using the same rationale set forth above in the rejection of Claim 7.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-19 and 21 are rejected under 35 U.S.C. 101 because the claimed invention is directed to (an) abstract idea(s) without significantly more.
Claims 1, 12 and 19 recite:
A task scheduling method, comprising:
obtaining several task scheduling queues of a terminal, wherein one task scheduling queue corresponds to storing a task to be executed of a task type in the terminal, and different task scheduling queues store different task types of tasks to be executed;
determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue according to an execution priority of each task type;
obtaining the task execution queue, wherein the task execution queue comprises the tasks to be executed extracted from the task scheduling queues;
if a current queue depth of the task execution queue is less than a maximum queue depth of the task execution queue, calculating a target number of tasks to be executed that can be added to the task execution queue;
selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order and the target number;
taking out the tasks to be executed from the task execution queue for processing.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 1 is a process.
Claim 12 is a machine.
Claim 19 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #2 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a queue scheduling order according to an execution priority of each task type, including comparison or judgement.
The ‘calculating’ limitation in #4 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “calculating” in the context of this claim encompasses a person analyzing, evaluating, or calculating a target number of tasks to be executed that can be added to the task execution queue, including comparison or judgement.
The ‘selecting’ limitation in #5 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting tasks to be executed according to the queue scheduling order and the target number, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘obtaining’ limitation in #1 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “obtaining” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘obtaining’ limitation in #3 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “obtaining” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘taking’ limitation in #6 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “taking” in the context of this claim encompasses merely taking out the tasks to be executed from the task execution queue for processing. See MPEP 2106.05(f).
Additionally, one or more of the claims recite the following additional elements:
A processor (Claims 12 and 19)
A memory (Claim 19)
A computer program (Claim 19)
These additional elements are recited at a high level of generality (i.e., as generic computer components) such that they amount to no more than components comprising mere instructions to apply the exception. Accordingly, these additional elements do not integrate the abstract idea(s) into a practical application because they do not impose any meaningful limits on practicing the abstract ideas(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Claim 10 merely further describes the execution priority of claim 1. The claim does not include additional elements that integrate into practical application or are sufficient to amount to significantly more than the judicial exception.
Therefore, Claims 1, 10, 12, and 19 are directed to (an) abstract idea(s) without significantly more.
Claims 2, 13 and 21 recite:
wherein before obtaining the several task scheduling queues of the terminal, the method further comprises:
creating each of the task scheduling queues;
when the terminal generates the task to be executed, determining the task type of the task to be executed;
according to the task type of the task to be executed, storing a generated task to be executed in a corresponding task scheduling queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 2 is a process.
Claim 13 is a machine.
Claim 21 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #8 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining the task type of the task to be executed, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘creating’ limitation in #7 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “creating” in the context of this claim encompasses merely creating each of the task scheduling queues. See MPEP 2106.05(f).
The ‘storing’ limitation in #9 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “storing” in the context of this claim encompasses merely storing information in memory. See MPEP 2106.05(g).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Additionally, with regards to #9 above, per MPER 2106.05(d)(II), the courts have recognized the following computer functions as well-understood, routine, and conventional functions when they are claimed in a merely generic matter (e.g., at a high level of generality) or as insignificant extra-solution activity:
Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93;
Therefore, Claims 2, 13, and 21 are directed to (an) abstract idea(s) without significantly more.
Claims 3 and 14 recite:
wherein selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order and the target number comprises:
selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number, wherein a number of tasks to be executed selected from each task scheduling queue does not exceed a single maximum task extraction number corresponding to the task scheduling queue, and a number of all selected tasks to be executed does not exceed the target number;
extracting selected tasks to be executed from the task scheduling queue and
adding the selected tasks to be executed to the task execution queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 3 is a process.
Claim 14 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘selecting’ limitation in #10 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting the tasks to be executed according to the queue scheduling order and the target number, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘extracting’ limitation in #11 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “extracting” in the context of this claim encompasses merely extracting selected tasks to be executed from the task execution queue. See MPEP 2106.05(f).
The ‘adding’ limitation in #12 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “adding” in the context of this claim encompasses merely adding the selected tasks to be executed to the task execution queue. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 3 and 14 are directed to (an) abstract idea(s) without significantly more.
Claims 4 and 15 recite:
wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises:
selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue;
if the target number does not exceed a maximum single task extraction number of the current task scheduling queue, and a sum of the number of tasks to be executed extracted from the current task scheduling queue to the task execution queue and the target number does not exceed the maximum number of tasks to be executed that can be extracted from the current task scheduling queue to the task execution queue, selecting the target number of tasks to be executed from the current task scheduling queue as the selected tasks to be executed;
if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time, and a sum of the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue and the target number exceeds the maximum number of tasks in storage corresponding to the current task scheduling queue, using a next task scheduling queue as the current task scheduling queue according to the queue scheduling order;
if the target number does not exceed the maximum number of tasks extracted from the current task scheduling queue at a time, and the sum of the number of tasks in storage and the target number of tasks to be executed extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that can be extracted from the current task scheduling queue to the task execution queue, performing selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 4 is a process.
Claim 15 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘selecting’ limitation in #13 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting the task scheduling queue that ranks first in the queue scheduling order, including comparison or judgement.
The ‘selecting’ limitation in #14 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting the target number of tasks to be executed from the current task scheduling queue, including comparison or judgement.
The ‘selecting’ limitation in #16 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘using’ limitation in #15 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “using” in the context of this claim encompasses merely using a next task scheduling queue as the current task scheduling queue according to the queue scheduling order. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 4 and 15 are directed to (an) abstract idea(s) without significantly more.
Claims 5 and 16 recite:
wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises:
selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue;
if the target number exceeds the single maximum task extraction number of the current task scheduling queue, and the number of tasks in storage of the tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue, calculating a first difference between the number of tasks in storage and the maximum number of tasks in storage of the current task scheduling queue,
determining a smaller number from the first difference and the single maximum task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue, and
taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order;
if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time, and the number of tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue is greater than or equal to the maximum number of tasks that can be extracted from the current task scheduling queue to the task execution queue, according to the queue scheduling order, using the next task scheduling queue as the current task scheduling queue;
obtaining a second difference between the target number and the extraction number, and
updating the target number to the second difference;
returning to execute if the target number exceeds the maximum single task extraction number of the current task scheduling queue, wherein the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue,
calculating the first difference between the number of tasks in storage and the maximum number of tasks in storage in the current task scheduling queue,
determining the smaller number from the first difference and the maximum single task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue,
taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order, until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 5 is a process.
Claim 16 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘selecting’ limitation in #17 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “selecting” in the context of this claim encompasses a person analyzing, evaluating, or selecting the task scheduling queue that ranks first in the queue scheduling order, including comparison or judgement.
The ‘calculating’ limitation in #18 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “calculating” in the context of this claim encompasses a person analyzing, evaluating, or calculating a first difference between the number of tasks in storage and the maximum number of tasks in storage of the current task scheduling queue, including comparison or judgement.
The ‘determining’ limitation in #19 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a smaller number from the first difference and the single maximum task extraction number of the current task scheduling queue, including comparison or judgement.
The ‘calculating’ limitation in #25 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “calculating” in the context of this claim encompasses a person analyzing, evaluating, or calculating the first difference between the number of tasks in storage and the maximum number of tasks in storage in the current task scheduling queue, including comparison or judgement.
The ‘determining’ limitation in #26 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining the smaller number from the first difference and the maximum single task extraction number of the current task scheduling queue, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘taking’ limitation in #20 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “taking” in the context of this claim encompasses merely taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order. See MPEP 2106.05(f).
The ‘using’ limitation in #21 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “using” in the context of this claim encompasses merely using the next task scheduling queue as the current task scheduling queue. See MPEP 2106.05(f).
The ‘obtaining’ limitation in #22 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “obtaining” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘updating’ limitation in #23 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “updating” in the context of this claim encompasses merely updating the target number to the second difference. See MPEP 2106.05(f).
The ‘executing’ limitation in #24 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “executing” in the context of this claim encompasses merely returning to execute if the target number exceeds the maximum single task extraction number of the current task scheduling queue. See MPEP 2106.05(f).
The ‘taking’ limitation in #27 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “taking” in the context of this claim encompasses merely taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 5 and 16 are directed to (an) abstract idea(s) without significantly more.
Claims 6 and 17 recite:
detecting an actual processing delay of each of the tasks to be executed, wherein the actual processing delay being a difference between a time when the task to be executed is added to the task scheduling queue and a time when the task to be executed is completed;
obtaining the expected processing delay corresponding to each task scheduling queue;
updating a maximum number of tasks in storage corresponding to each task scheduling queue according to the actual processing delay and an expected processing delay corresponding to each task scheduling queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 6 is a process.
Claim 17 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘detecting’ limitation in #28 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “detecting” in the context of this claim encompasses a person analyzing, evaluating, or detecting an actual processing delay of each of the tasks to be executed, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘obtaining’ limitation in #29 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “obtaining” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘updating’ limitation in #30 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “updating” in the context of this claim encompasses merely updating a maximum number of tasks in storage corresponding to each task scheduling queue. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 6 and 17 are directed to (an) abstract idea(s) without significantly more.
Claims 7 and 18 recite:
wherein updating the maximum number of tasks in storage corresponding to each task scheduling queue according to the actual processing delay and the expected processing delay corresponding to each task scheduling queue comprises:
setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue;
determining a number of timeout tasks corresponding to each scheduling task queue in a latest monitoring cycle, wherein the timeout task is a task whose actual processing delay exceeds the maximum processing delay of the scheduling task queue;
determining a target task scheduling queue whose execution priority level is greater than a preset level;
if a ratio of the number of tasks in the target scheduling task queue in the latest monitoring cycle to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing exceeds a preset maximum ratio, then increasing the maximum number of tasks in storage corresponding to the target task scheduling queue, wherein an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 7 is a process.
Claim 18 is a machine.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #32 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a number of timeout tasks corresponding to each scheduling task queue in a latest monitoring cycle, including comparison or judgement.
The ‘determining’ limitation in #33 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining whether a target task scheduling queue whose execution priority level is greater than a preset level, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘setting’ limitation in #31 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “setting” in the context of this claim encompasses merely setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue. See MPEP 2106.05(f).
The ‘increasing’ limitation in #34 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “increasing” in the context of this claim encompasses merely increasing the maximum number of tasks in storage corresponding to the target task scheduling queue. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 7 and 18 are directed to (an) abstract idea(s) without significantly more.
Claim 8 recites:
wherein according to the task type of the task to be executed, storing the generated task to be executed in the corresponding task scheduling queue comprises:
determining the target task scheduling queue corresponding to the generated task to be executed according to the task type of the task to be executed;
determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue based on a storage quantity of the tasks to be executed stored in the target task scheduling queue;
storing the generated task to be executed in the corresponding target task scheduling queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 8 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #35 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining the target task scheduling queue according to the task type of the task to be executed, including comparison or judgement.
The ‘determining’ limitation in #36 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘storing’ limitation in #37 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “storing” in the context of this claim encompasses merely storing information in memory. See MPEP 2106.05(g).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Additionally, with regards to #37 above, per MPER 2106.05(d)(II), the courts have recognized the following computer functions as well-understood, routine, and conventional functions when they are claimed in a merely generic matter (e.g., at a high level of generality) or as insignificant extra-solution activity:
Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93;
Therefore, Claim 8 is directed to (an) abstract idea(s) without significantly more.
Claim 9 recites:
obtaining a candidate task scheduling queue with largest total number of pending tasks processed and completed within a monitoring cycle;
if an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level, reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue, wherein a reduced maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 9 is a process.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘obtaining’ limitation in #38 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “obtaining” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘reducing’ limitation in #39 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “reducing” in the context of this claim encompasses merely reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 9 is directed to (an) abstract idea(s) without significantly more.
Claim 11 recites:
when scheduling the tasks to be executed into the task execution queue, setting first to extract the tasks to be executed from the task scheduling queue storing the tasks to be executed with a higher execution priority and
add the tasks to be executed to the task execution queue, and then
extracting the tasks to be executed from the task scheduling queue storing the tasks to be executed with a lower execution priority and
add the tasks to be executed to the task execution queue.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 11 is a process.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘extracting’ limitation in #40 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “extracting” in the context of this claim encompasses merely extracting the tasks to be executed from the task scheduling queue. See MPEP 2106.05(f).
The ‘adding’ limitation in #41 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “adding” in the context of this claim encompasses merely adding the tasks to be executed to the task execution queue. See MPEP 2106.05(f).
The ‘extracting’ limitation in #42 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “extracting” in the context of this claim encompasses extracting the tasks to be executed from the task scheduling queue. See MPEP 2106.05(f).
The ‘adding’ limitation in #43 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “adding” in the context of this claim encompasses merely adding the tasks to be executed to the task execution queue. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 11 is directed to (an) abstract idea(s) without significantly more.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-6, 11-17, 19 and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Lumb et al. (U.S. Publication No. US 20040194095 A1), hereinafter “Lumb” in view of D. Chang et al. (U.S. Publication No. US 20170249191 A1), hereinafter “D. Chang.”
With regards to claim 1, Lumb teaches:
A task scheduling method, comprising:
obtaining several task scheduling queues of a terminal (Fig. 4, paragraph 32, “Requests arriving at the QoS controller 104 (e.g., from hosts 108) are queued in the input queues 110 where the requests from each workload are preferably assigned to a particular one of the queues 110. Based on repeated input from the I/O monitor 114 and the I/O controller 116, the scheduler 112 maintains a target queue depth value for the device queue 118 and per-workload latency targets which the scheduler 112 attempts to maintain.” The input queues which contain requests from assigned workloads correlates to obtaining several task scheduling queues of a terminal),
obtaining the task execution queue, wherein the task execution queue comprises the tasks to be executed extracted from the task scheduling queues (Paragraph 34, “Alternately, the scheduler 112 may compute the current device queue depth based on I/O request arrival and completion information from the monitor 114, for example, where the device 106 does not support reporting of the depth of the device queue 118. Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116.” The requests from the input queues being forwarded to the device queue, which completes I/O requests, correlates to obtaining the task execution queue, wherein the task execution queue comprises the tasks to be executed extracted from the task scheduling queues);
if a current queue depth of the task execution queue is less than a maximum queue depth of the task execution queue, calculating a target number of tasks to be executed that can be added to the task execution queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” The number of requests needed to bring the device queue’s current depth to the target depth correlates to calculating a target number of tasks to be executed that can be added to the task execution queue. The scheduler repeatedly selecting the workload with the next earliest deadline in the input queue to forward to the device queue until the current depth of the device queue reaches the target depth would involve the current depth of the device queue being less than the maximum queue depth and therefore correlates to calculating a target number of tasks to be executed that can be added to the task execution queue if a current queue depth of the task execution queue is less than a maximum queue depth of the task execution queue);
selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the target number (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” The scheduler repeatedly selecting the workload with the next earliest deadline in the input queue to forward to the device queue until the current depth of the device queue reaches the target depth correlates to selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the target number);
taking out the tasks to be executed from the task execution queue for processing (Paragraph 34, “Alternately, the scheduler 112 may compute the current device queue depth based on I/O request arrival and completion information from the monitor 114, for example, where the device 106 does not support reporting of the depth of the device queue 118. Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116.” The requests from the input queues being forwarded to the device queue, where the I/O requests are completed, correlates to taking out the tasks to be executed from the task execution queue for processing).
Lumb does not explicitly teach that selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue [are] according to the queue scheduling order. However, selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order is of a popular method of task scheduling as evidenced by D. Chang (Paragraphs 28 and 48-49, “In contrast to some other scheduling techniques, each task queue is associated with a respective priority ratio, and the priority ratio defines the frequency with which tasks from the respective task queue are scheduled by first processor 16A to be executed by the at least one processor of processors 16… In some examples, the inputs from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530 may be arranged in a selected order. Scheduler 510 may be configured to sequentially evaluate the messages from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530, such that scheduler 510 progresses through the task queues in a predetermined interleaved order… In this way, scheduler 510 may be configured to evaluate the messages associated with the respective task queues 540 in a predetermined order, and to schedule a task from a respective task queue for execution by one of processors 260 (FIG. 2) based on the priority ratio associated with the respective task queue, as indicated by the messages received by scheduler 510 from the respective multi-level programmable priority ratio units 530.” The scheduler sequentially scheduling tasks from the respective task queues based on their priority ratio in a predetermined interleaved order correlates to selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order).
Lumb does not explicitly teach:
wherein one task scheduling queue corresponds to storing a task to be executed of a task type in the terminal, and different task scheduling queues store different task types of tasks to be executed;
determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue according to an execution priority of each task type;
However, D. Chang teaches:
wherein one task scheduling queue corresponds to storing a task to be executed of a task type in the terminal, and different task scheduling queues store different task types of tasks to be executed (Paragraph 26, “The tasks may be of different types, and, in some examples, each respective type of task may be stored in or associated with a respective task queue while waiting for execution by processors 16.” Each respective type of task being stored in a respective task queue to wait for execution by processors correlates to wherein one task scheduling queue corresponds to storing a task to be executed of a task type in the terminal, and different task scheduling queues store different task types of tasks to be executed);
determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue according to an execution priority of each task type (Paragraphs 28, 30, and 48-49 “In contrast to some other scheduling techniques, each task queue is associated with a respective priority ratio, and the priority ratio defines the frequency with which tasks from the respective task queue are scheduled by first processor 16A to be executed by the at least one processor of processors 16… In some examples, first processor 16A additionally may base the priority ratio on a type of task associated with the respective task queue. For example, front-end tasks may have a higher priority than house-keeping tasks or system tasks... In some examples, the inputs from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530 may be arranged in a selected order. Scheduler 510 may be configured to sequentially evaluate the messages from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530, such that scheduler 510 progresses through the task queues in a predetermined interleaved order… In this way, scheduler 510 may be configured to evaluate the messages associated with the respective task queues 540 in a predetermined order, and to schedule a task from a respective task queue for execution by one of processors 260 (FIG. 2) based on the priority ratio associated with the respective task queue, as indicated by the messages received by scheduler 510 from the respective multi-level programmable priority ratio units 530.” The scheduler sequentially scheduling tasks for execution by a processor from the respective task queues based on their priority ratio in a predetermined interleaved order correlates to determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue. The priority ratio being determined based on the type of task associated with the respective task queue, where front-end tasks can have a higher priority than system tasks, correlates to determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue according to an execution priority of each task type);
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with wherein one task scheduling queue corresponds to storing a task to be executed of a task type in the terminal, and different task scheduling queues store different task types of tasks to be executed; determining a queue scheduling order of each task scheduling queue when scheduling tasks to be executed into a task execution queue according to an execution priority of each task type; selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order as taught by D. Chang because schedulers can be configured to evaluate messages from different task queues in a predetermined order based on a priority ratio associated with a respective task queue. Priority ratios may be updated periodically to additionally facilitate auto prioritization based in part on the number of tasks currently or recently added in the task queue (D. Chang: paragraphs 29 and 49).
With regards to Claims 12 and 19, the method of Claim 1 performs the same steps as the machines of Claims 12 and 19 respectively, and Claims 12 and 19 are therefore rejected using the same rationale set forth above in the rejection of Claim 1.
With regards to claim 2, Lumb in view of D. Chang teaches the method of claim 1 above. Lumb further teaches:
wherein before obtaining the several task scheduling queues of the terminal, the method further comprises:
creating each of the task scheduling queues (Fig. 4, paragraph 32, “Requests arriving at the QoS controller 104 (e.g., from hosts 108) are queued in the input queues 110 where the requests from each workload are preferably assigned to a particular one of the queues 110. Based on repeated input from the I/O monitor 114 and the I/O controller 116, the scheduler 112 maintains a target queue depth value for the device queue 118 and per-workload latency targets which the scheduler 112 attempts to maintain.” The input queues which contain requests from assigned workloads would need to be created before requests can be assigned to them and therefore correlates to creating each of the task scheduling queues before obtaining the several task scheduling queues of the terminal);
D. Chang further teaches:
when the terminal generates the task to be executed, determining the task type of the task to be executed (Paragraphs 33-34, “Arbitrator and event distributor 210 may receive a message from one of plurality of processors 260 that includes a task (or event) type and a task (or event) pointer. The task type may indicate a general category of task… Arbitrator and event distributor 210 may receive the task type and the task indicator and assign the task to one of plurality of task queues 230 based at least in part on the task type.” The arbitrator and event distributer receiving a message from the processors including a task type and then assigning the task to a task queue correlates to when the terminal generates the task to be executed, determining the task type of the task to be executed);
according to the task type of the task to be executed, storing a generated task to be executed in a corresponding task scheduling queue (Paragraph 34, “Arbitrator and event distributor 210 may receive the task type and the task indicator and assign the task to one of plurality of task queues 230 based at least in part on the task type. In some examples, each task type has an associated task queue.” The task being assigned to a plurality of task queues based on the task type correlates to according to the task type of the task to be executed, storing a generated task to be executed in a corresponding task scheduling queue).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with when the terminal generates the task to be executed, determining the task type of the task to be executed; according to the task type of the task to be executed, storing a generated task to be executed in a corresponding task scheduling queue as taught by D. Chang because tasks can be assigned to task queues based in part on their task type. Task pointers associated with a processor message can be used to assign a task to a task queue, in addition to additional information associated with the task, such as cache information, to be stored in the queue (D. Chang: paragraphs 33-35).
With regards to Claims 13 and 21, the method of Claim 2 performs the same steps as the machines of Claims 13 and 21 respectively, and Claims 13 and 21 are therefore rejected using the same rationale set forth above in the rejection of Claim 2.
With regards to claim 3, Lumb in view of D. Chang teaches the method of claim 1 above. Lumb further teaches:
wherein selecting the tasks to be executed from the task scheduling queues and adding the tasks to be executed to the task execution queue according to the queue scheduling order and the target number comprises:
selecting the tasks to be executed from at least one task scheduling queue according to the target number, wherein a number of tasks to be executed selected from each task scheduling queue does not exceed a single maximum task extraction number corresponding to the task scheduling queue, and a number of all selected tasks to be executed does not exceed the target number (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” The scheduler repeatedly selecting the workload with the next earliest deadline in the input queue to forward to the device queue until the current depth of the device queue reaches the target depth would involve adding a particular number of tasks to reach but not exceed the target depth of the particular device queue and therefore correlates to selecting the tasks to be executed from at least one task scheduling queue according to the target number, wherein a number of tasks to be executed selected from each task scheduling queue does not exceed a single maximum task extraction number corresponding to the task scheduling queue, and a number of all selected tasks to be executed does not exceed the target number);
extracting selected tasks to be executed from the task scheduling queue and adding the selected tasks to be executed to the task execution queue (Paragraph 34, “Alternately, the scheduler 112 may compute the current device queue depth based on I/O request arrival and completion information from the monitor 114, for example, where the device 106 does not support reporting of the depth of the device queue 118. Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116.” The requests from the input queues being forwarded to the device queue, where the I/O requests are completed, correlates to extracting selected tasks to be executed from the task scheduling queue and adding the selected tasks to be executed to the task execution queue).
Lumb does not explicitly teach that selecting the tasks to be executed from at least one task scheduling queue [are] according to the queue scheduling order. However, selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order is a popular method of task scheduling as evidenced by D. Chang above (Paragraphs 28 and 48-49).
With regards to Claim 14, the method of Claim 3 performs the same steps as the machine of Claim 14, and Claim 14 is therefore rejected using the same rationale set forth above in the rejection of Claim 3.
With regards to claim 4, Lumb in view of D. Chang teaches the method of claim 3 above. D. Chang further teaches:
wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises:
selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue (Paragraphs 28 and 48-49, “In contrast to some other scheduling techniques, each task queue is associated with a respective priority ratio, and the priority ratio defines the frequency with which tasks from the respective task queue are scheduled by first processor 16A to be executed by the at least one processor of processors 16… In some examples, the inputs from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530 may be arranged in a selected order. Scheduler 510 may be configured to sequentially evaluate the messages from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530, such that scheduler 510 progresses through the task queues in a predetermined interleaved order… In this way, scheduler 510 may be configured to evaluate the messages associated with the respective task queues 540 in a predetermined order, and to schedule a task from a respective task queue for execution by one of processors 260 (FIG. 2) based on the priority ratio associated with the respective task queue, as indicated by the messages received by scheduler 510 from the respective multi-level programmable priority ratio units 530.” The scheduler sequentially scheduling tasks from the respective task queues based on their priority ratio in a predetermined interleaved order would involve selecting the highest priority task queue first and therefore correlates to selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue);
Lumb further teaches:
if the target number does not exceed a maximum single task extraction number of the current task scheduling queue, and a sum of the number of tasks to be executed extracted from the current task scheduling queue to the task execution queue and the target number does not exceed the maximum number of tasks to be executed that can be extracted from the current task scheduling queue to the task execution queue, selecting the target number of tasks to be executed from the current task scheduling queue as the selected tasks to be executed (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” The target depth of the particular device queue correlates to the maximum number of tasks to be executed. The scheduler repeatedly selecting the workload with the next earliest deadline in the input queue to forward to the device queue until the current depth of the device queue reaches the target depth would involve adding a particular number of tasks to reach but not exceed the target depth of the particular device queue and therefore correlates to selecting the target number of tasks to be executed from the current task scheduling queue as the selected tasks to be executed, if the target number does not exceed a maximum single task extraction number of the current task scheduling queue, and a sum of the number of tasks to be executed extracted from the current task scheduling queue to the task execution queue and the target number does not exceed the maximum number of tasks to be executed that can be extracted from the current task scheduling queue to the task execution queue); if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time, and a sum of the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue and the target number exceeds the maximum number of tasks in storage corresponding to the current task scheduling queue, using a next task scheduling queue as the current task scheduling queue according to the queue scheduling order (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” The device queue can be in a scenario where the current queue depth is less than the target depth to a point where if all the requests of a particular input queue are forwarded to the device queue, the device queue’s current queue depth would still below the target depth. The number of requests needed to bring the device queue’s current depth to the target depth correlates to the target number, where in the proposed scenario, would correlate to if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time. All of the requests of a particular input queue being forwarded to the device queue but the device queue’s current queue depth still being below the target depth correlates to if a sum of the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue and the target number exceeds the maximum number of tasks in storage corresponding to the current task scheduling queue. The device queue then being forwarded requests from a different input queue in the scenario where the all the particular input queue’s requests have already been forwarded but the device’s current queue depth is less than the target depth would therefore correlate to using a next task scheduling queue as the current task scheduling queue according to the queue scheduling);
if the target number does not exceed the maximum number of tasks extracted from the current task scheduling queue at a time, and the sum of the number of tasks in storage and the target number of tasks to be executed extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that can be extracted from the current task scheduling queue to the task execution queue, performing selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order (Paragraph 34, “Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” One input queue can be in a scenario where there are more next-highest-priority requests in the particular input queue than the number of requests needed to bring the device queue’s current queue depth to the target depth. The number of requests needed to bring the device queue’s current depth to the target depth correlates to the target number, where in the proposed scenario, would correlate to if the target number does not exceed the maximum number of tasks extracted from the current task scheduling queue at a time. Not of the requests of a particular input queue being forwarded to the device queue due to reaching the device queue’s target depth correlates to if the sum of the number of tasks in storage and the target number of tasks to be executed extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that can be extracted from the current task scheduling queue to the task execution queue. The device queue then being forwarded the next-highest-priority requests from the particular input queue for executing the I/O requests correlates to performing selecting the target number of tasks to be executed from the current task scheduling queue).
Lumb does not explicitly teach that the selecting is performed until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order. However, selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order is a popular method of queue prioritization as evidenced by D. Chang (Paragraphs 28 and 48-49, “In contrast to some other scheduling techniques, each task queue is associated with a respective priority ratio, and the priority ratio defines the frequency with which tasks from the respective task queue are scheduled by first processor 16A to be executed by the at least one processor of processors 16… In some examples, the inputs from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530 may be arranged in a selected order. Scheduler 510 may be configured to sequentially evaluate the messages from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530, such that scheduler 510 progresses through the task queues in a predetermined interleaved order… In this way, scheduler 510 may be configured to evaluate the messages associated with the respective task queues 540 in a predetermined order, and to schedule a task from a respective task queue for execution by one of processors 260 (FIG. 2) based on the priority ratio associated with the respective task queue, as indicated by the messages received by scheduler 510 from the respective multi-level programmable priority ratio units 530.” The scheduler sequentially scheduling tasks from the respective task queues based on their priority ratio in a predetermined interleaved order would involve certain queues being moved towards the end of the interleaved order once a certain amount of tasks are scheduled and therefore correlates to selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises: selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue, selecting the target number of tasks to be executed from the current task scheduling queue until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order as taught by D. Chang because assigning a priority to the plurality of tasks in an optimized order to determine which tasks should be executed first improves the efficiency of the memory system. Each time a new task enters a task queue, a priority being applied to the new task to determine its optimized order further improves the efficiency of the memory system (D. Chang: paragraphs 26 and 30).
With regards to Claim 15, the method of Claim 4 performs the same steps as the machine of Claim 15, and Claim 15 is therefore rejected using the same rationale set forth above in the rejection of Claim 4.
With regards to claim 5, Lumb in view of D.Chang teaches the method of claim 3 above. D. Chang further teaches:
wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises:
selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue (Paragraphs 28 and 48-49, “In contrast to some other scheduling techniques, each task queue is associated with a respective priority ratio, and the priority ratio defines the frequency with which tasks from the respective task queue are scheduled by first processor 16A to be executed by the at least one processor of processors 16… In some examples, the inputs from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530 may be arranged in a selected order. Scheduler 510 may be configured to sequentially evaluate the messages from the respective task queues 540 and associated respective multi-level programmable priority ratio units 530, such that scheduler 510 progresses through the task queues in a predetermined interleaved order… In this way, scheduler 510 may be configured to evaluate the messages associated with the respective task queues 540 in a predetermined order, and to schedule a task from a respective task queue for execution by one of processors 260 (FIG. 2) based on the priority ratio associated with the respective task queue, as indicated by the messages received by scheduler 510 from the respective multi-level programmable priority ratio units 530.” The scheduler sequentially scheduling tasks from the respective task queues based on their priority ratio in a predetermined interleaved order would involve selecting the highest priority task queue first and therefore correlates to selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue);
Lumb further teaches:
if the target number exceeds the single maximum task extraction number of the current task scheduling queue, and the number of tasks in storage of the tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” The device queue can be in a scenario where the current queue depth is less than the target depth to a point where if all the requests of a particular input queue are forwarded to the device queue, the device queue’s current queue depth would still below the target depth. The number of requests needed to bring the device queue’s current depth to the target depth correlates to the target number, where in the proposed scenario, would correlate to if the target number exceeds the single maximum task extraction number of the current task scheduling queue. The requests are forwarded one at a time and therefore there is a point in time where not all of the requests in the current input queue have been forwarded to the device queue, which correlates to the number of tasks in storage of the tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue), calculating a first difference between the number of tasks in storage and the maximum number of tasks in storage of the current task scheduling queue, determining a smaller number from the first difference and the single maximum task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” Using the same scenario above, the requests are forwarded one at a time and therefore the number of requests that can be forwarded from the input queue to the device queue cannot exceed the number of remaining requests in the input queue. The current number of requests in the input queue correlates to the number of tasks in storage and the initial number of requests in the input queue before any requests were forwarded to the device queue correlates to the maximum number of tasks in storage of the current task scheduling queue. Forwarding the remaining requests in the input queue to the device queue, where the number of requests forwarded cannot exceed the number of remaining requests, therefore correlates to calculating a first difference between the number of tasks in storage and the maximum number of tasks in storage of the current task scheduling queue and determining a smaller number from the first difference and the single maximum task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue), and taking the next task scheduling queue as the current task scheduling queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” Using the same scenario described above, the requests from input queues being repeatedly forwarded until the device queue reaches the target depth would involve additional requests from at least one other input queue being forwarded to the device queue after the current input queue has exhausted its remaining requests and therefore correlates to taking the next task scheduling queue as the current task scheduling queue);
if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time, and the number of tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue is greater than or equal to the maximum number of tasks that can be extracted from the current task scheduling queue to the task execution queue, using the next task scheduling queue as the current task scheduling queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” The device queue can be in a scenario where the current queue depth is less than the target depth to a point where if all the requests of a particular input queue are forwarded to the device queue, the device queue’s current queue depth would still below the target depth. The number of requests needed to bring the device queue’s current depth to the target depth correlates to the target number, where in the proposed scenario, would correlate to if the target number exceeds the maximum number of tasks extracted from the current task scheduling queue at a time. The current number of requests in the particular input queue correlates to the maximum number of tasks that can be extracted from the current task scheduling queue to the task execution queue. All of the requests of a particular input queue being forwarded to the device queue correlates to the number of tasks to be executed that have been extracted from the current task scheduling queue to the task execution queue is greater than or equal to the maximum number of tasks that can be extracted from the current task scheduling queue to the task execution queue. The device queue then being forwarded requests from a different input queue in the scenario where the all the particular input queue’s requests have already been forwarded but the device’s current queue depth is less than the target depth would therefore correlate to using a next task scheduling queue as the current task scheduling queue);
obtaining a second difference between the target number and the extraction number, and updating the target number to the second difference (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” All of the forwarded requests from the initial input queue correlates to the extraction number, and the target depth of the device queue correlates to the target number. Using the same scenario described above, forwarding all of the initial input queue’s requests to the device queue would increase the device queue’s current depth to the sum of the previous current depth and all of the forwarded requests, which correlates to obtaining a second difference between the target number and the extraction number, and updating the target number to the second difference);
returning to execute if the target number exceeds the maximum single task extraction number of the current task scheduling queue, wherein the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue (Paragraph 34, “The scheduler 112 polls the device queue 118 repeatedly to determine a then-current queue depth (i.e. the number of requests pending in the queue 118) … Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” The device queue can be in a scenario where the current queue depth is less than the target depth to a point where if all the requests of a particular input queue are forwarded to the device queue, the device queue’s current queue depth would still below the target depth. The number of requests needed to bring the device queue’s current depth to the target depth correlates to the target number, where in the proposed scenario, would correlate to if the target number exceeds the maximum single task extraction number of the current task scheduling queue. The requests are forwarded one at a time and therefore there is a point in time where not all of the requests in the current input queue have been forwarded to the device queue, which correlates to the number of tasks in storage that have been extracted from the current task scheduling queue to the task execution queue does not exceed the maximum number of tasks in storage that the current task scheduling queue can extract to the task execution queue. The device queue completing the I/O requests that have been forwarded correlates to returning to execute), calculating the first difference between the number of tasks in storage and the maximum number of tasks in storage in the current task scheduling queue, determining the smaller number from the first difference and the maximum single task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth. A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” Using the same scenario above, the requests are forwarded one at a time and therefore the number of requests that can be forwarded from the input queue to the device queue cannot exceed the number of remaining requests in the input queue. The current number of requests in the input queue correlates to the number of tasks in storage and the initial number of requests in the input queue before any requests were forwarded to the device queue correlates to the maximum number of tasks in storage of the current task scheduling queue. Forwarding the remaining requests in the input queue to the device queue, where the number of requests forwarded cannot exceed the number of remaining requests, therefore correlates to calculating the first difference between the number of tasks in storage and the maximum number of tasks in storage of the current task scheduling queue and determining the smaller number from the first difference and the maximum single task extraction number of the current task scheduling queue as the extraction number of tasks to be executed selected from the current task scheduling queue), taking the next task scheduling queue as the current task scheduling queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” Using the same scenario described above, the requests from input queues being repeatedly forwarded until the device queue reaches the target depth would involve additional requests from at least one other input queue being forwarded to the device queue after the current input queue has exhausted its remaining requests and therefore correlates to taking the next task scheduling queue as the current task scheduling queue).
Lumb does not explicitly teach that taking the next task scheduling queue as the current task scheduling queue [is] according to the queue scheduling order, using the next task scheduling queue as the current task scheduling queue according to the queue scheduling order and that the taking is performed until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order. However, taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order and using the next task scheduling queue as the current task scheduling queue according to the queue scheduling order is a popular method of task scheduling as evidenced by D. Chang above (Paragraphs 28 and 48-49). Additionally, taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order is a popular method of queue prioritization as evidenced by D. Chang above (Paragraphs 28 and 48-49).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with wherein selecting the tasks to be executed from at least one task scheduling queue according to the queue scheduling order and the target number comprises: selecting the task scheduling queue that ranks first in the queue scheduling order as the current task scheduling queue, taking the next task scheduling queue as the current task scheduling queue according to the queue scheduling order, until the current task scheduling queue is the task scheduling queue at an end of the queue scheduling order as taught by D. Chang because assigning a priority to the plurality of tasks in an optimized order to determine which tasks should be executed first improves the efficiency of the memory system. Each time a new task enters a task queue, a priority being applied to the new task to determine its optimized order further improves the efficiency of the memory system (D. Chang: paragraphs 26 and 30).
With regards to Claim 16, the method of Claim 5 performs the same steps as the machine of Claim 16, and Claim 16 is therefore rejected using the same rationale set forth above in the rejection of Claim 5.
With regards to claim 6, Lumb in view of D. Chang teaches the method of claim 3 above. Lumb further teaches:
detecting an actual processing delay of each of the tasks to be executed, wherein the actual processing delay being a difference between a time when the task to be executed is added to the task scheduling queue and a time when the task to be executed is completed (Paragraphs 32 and 37, “Requests arriving at the QoS controller 104 (e.g., from hosts 108) are queued in the input queues 110 where the requests from each workload are preferably assigned to a particular one of the queues 110… In addition to monitoring the request arrival rates, the I/O monitor 114 preferably also monitors the time of arrival of each I/O request as the requests are received into the QoS controller 104. In addition, the monitor 114 monitors the completion time for each request reported by the devices 106. From this, the monitor 114 may compute the latency for each request and average latencies for each workload (over time periods of w).” The monitor computing the latency for each request based on the time of arrival of each I/O request in an input queue and the completion time for each request correlates to detecting an actual processing delay of each of the tasks to be executed, wherein the actual processing delay being a difference between a time when the task to be executed is added to the task scheduling queue and a time when the task to be executed is completed);
obtaining the expected processing delay corresponding to each task (Paragraph 37, “From this, the monitor 114 may compute the latency for each request and average latencies for each workload (over time periods of w). The average latencies are then reported to the controller 116. The latency averages are preferably computed and reported periodically, every P=0.05 seconds, though it will be apparent that another period may be selected.” The monitor computing the average latency for each workload correlates to obtaining the expected processing delay corresponding to each task);
updating a maximum number of tasks in storage corresponding to each task execution queue according to the actual processing delay and an expected processing delay corresponding to each task (Paragraphs 38 and 40, “In response to the average latency information, the controller 116 may adjust the target depth of the device queue 118... In a particular implementation, the controller 116 compares the current target latencies for each workload to its average latency measured during the prior period for adjusting the target depth of the device queue 118.” The controller adjusting the target depth of the device queue based on the current target latency for each workload and the average latency of each workload correlates to updating a maximum number of tasks in storage corresponding to each task execution queue according to the actual processing delay and an expected processing delay corresponding to each task).
Lumb does not explicitly teach that the expected processing delay corresponds to each task scheduling queue and that the maximum number of tasks in storage corresponding to each task scheduling queue are updated. However, task scheduling queues are a popular type of queue storing tasks of the same type as evidenced by D. Chang (Paragraph 26, “The tasks may be of different types, and, in some examples, each respective type of task may be stored in or associated with a respective task queue while waiting for execution by processors 16.” Each respective type of task being stored in a respective task queue to wait for execution by processors would involve the same type of task in a particular queue and therefore correlates to a task scheduling queue for storing a task to be executed of a task type).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with each task scheduling queue as taught by D. Chang because schedulers can be configured to evaluate messages from different task queues in a predetermined order based on a priority ratio associated with a respective task queue. Priority ratios may be updated periodically to additionally facilitate auto prioritization based in part on the number of tasks currently or recently added in the task queue (D. Chang: paragraphs 29 and 49).
With regards to Claim 17, the method of Claim 6 performs the same steps as the machine of Claim 17, and Claim 17 is therefore rejected using the same rationale set forth above in the rejection of Claim 6.
With regards to claim 11, Lumb in view of D. Chang teaches the method of claim 1 above. Lumb further teaches:
when scheduling the tasks to be executed into the task execution queue, setting first to extract the tasks to be executed from the task scheduling queue storing the tasks to be executed with a higher execution priority and add the tasks to be executed to the task execution queue, and then extracting the tasks to be executed from the task scheduling queue storing the tasks to be executed with a lower execution priority and add the tasks to be executed to the task execution queue (Paragraph 34, “Requests from a workload are forwarded to the device queue 118 under specified circumstances: A request may be forwarded to the device queue 118 when the current depth of the device queue 118 is less than the target specified by the I/O controller 116. In this case, the scheduler 112 selects the workload with the earliest deadline and forwards the first request (i.e. the request having the earliest deadline) in its corresponding queue 110 to the device queue 118. The scheduler 112 repeats these steps of selecting a workload with the next earliest deadline and forwarding the first request of that workload to the device queue 118 until the current depth of the device queue 118 reaches the target depth. Thus, the requests are prioritized in the input queues 110 and a highest priority one of the requests is forwarded to the device queue 118 so as to maintain the device queue 118 at its target depth.” The scheduler forwarding the first request with the earliest deadline from its corresponding queue to the device queue correlates to setting first to extract the tasks to be executed from the task scheduling queue storing the tasks to be executed with a higher execution priority and add the tasks to be executed to the task execution queue. The scheduler then selecting a workload with the next earliest deadline to forward to the device queue, where requests are prioritized in input queues and a highest priority request is forwarded, correlates to then extracting the tasks to be executed from the task scheduling queue storing the tasks to be executed with a lower execution priority and add the tasks to be executed to the task execution queue).
Claim(s) 7 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Lumb in view of D. Chang, Ahuja et al. (U.S. Publication No. US 9667722 B2), hereinafter “Ahuja,” Y. Chang et al. (U.S. Publication No. US 7934028 B1), hereinafter “Y. Chang” and Leonard et al. (U.S. Publication No. US 20140137128 A1), hereinafter “Leonard.”
With regards to claim 7, Lumb in view of D. Chang teaches the method of claim 6 above. Lumb further teaches:
wherein updating the maximum number of tasks in storage corresponding to each task scheduling queue according to the actual processing delay and the expected processing delay corresponding to each task scheduling queue comprises:
determining a number of timeout tasks corresponding to each scheduling task queue in a latest monitoring cycle, wherein the timeout task is a task whose actual processing delay exceeds the maximum processing delay of the task (Paragraph 34, “Preferably, the queue depth is polled periodically (e.g., every 1 ms) and also upon completions of I/O requests. Requests from a workload are forwarded to the device queue 118 under specified circumstances… A request may also be forwarded to the device queue 118 when its deadline has already passed. All past-due requests are preferably forwarded to the device queue 118 even if this causes the depth of the device queue 118 to exceed its target depth.” The deadline of a request in an input queue correlates to the maximum processing delay of the task. The requests which have passed their deadline being forwarded to the device queue after polling the current queue depth periodically would involve a determinization of the number of tasks which need to be forwarded and therefore correlates to determining a number of timeout tasks corresponding to each scheduling task queue in a latest monitoring cycle, wherein the timeout task is a task whose actual processing delay exceeds the maximum processing delay of the task);
Lumb does not explicitly teach that the maximum processing delay [is for] the scheduling task queue. However, determining a maximum processing delay for a scheduling task queue is a popular method of queue analysis as evidenced by Ahuja below (Col. 16, lines 2-9, “The queue information processing module stores the calculated latency for P1 in the latency statistics information of the queue data repository along with the queue identifier 27. After each latency calculation for a given queue, the queue information processing module of the latency calculation device calculates latency statistics for the queue that include average latency of the queue and maximum latency of the queue.” The maximum latency of the given queue being calculated using each latency calculation for a given queue correlates to a maximum processing delay for each task scheduling queue).
Lumb in view of D. Chang does not explicitly teach:
setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue;
determining a target task scheduling queue whose execution priority level is greater than a preset level;
if a ratio of the number of tasks in the target scheduling task queue in the latest monitoring cycle to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing exceeds a preset maximum ratio, then increasing the maximum number of tasks in storage corresponding to the target task scheduling queue, wherein an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue.
However, Ahuja teaches:
setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue (Col. 16, lines 2-9, “The queue information processing module stores the calculated latency for P1 in the latency statistics information of the queue data repository along with the queue identifier 27. After each latency calculation for a given queue, the queue information processing module of the latency calculation device calculates latency statistics for the queue that include average latency of the queue and maximum latency of the queue.” The maximum latency of the given queue being calculated using each latency calculation for a given queue correlates to setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue);
Additionally, Y. Chang teaches:
determining a target task scheduling queue whose execution priority level is greater than a preset level (Paragraph 29, “According to the priority in a default order (i.e. metadata management 112B, user data access 112A, garbage collection 112D, and wear leveling control 112C), the task M1 of metadata management 112B is converted into command(s) by the task scheduling unit 242 first and stored in the corresponding execution queue(s) among the execution queues 234A-234D. Then the tasks U1-U3 of user data access 112A and task G1 of garbage collection 112D are converted into commands and stored in the corresponding execution queues among the execution queues 234A-234D in order according to the priority and the requirements for these tasks to be executed in which memory/memories, as shown in FIG. 5B.” The default order of priorities where metadata management tasks and their related queues have a higher priority and are converted into commands for an execution queue over other types of tasks correlates to determining a target task scheduling queue whose execution priority level is greater than a preset level);
Additionally, Leonard teaches:
if a ratio of the number of tasks in the target scheduling task queue in the latest monitoring cycle to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing exceeds a preset maximum ratio (Col. 5, lines 63-67, Col. 6, lines 22-25 and 31-40, “Both the low-depth-alarm setting and the high-depth-alarm setting may be based on percentages of the maximum allowable depth. For example, the high-depth-alarm setting could be 80% of the maximum allowable depth and the low-depth-alarm setting could be 20% of the maximum allowable depth… For example, a high-depth-alarm event will be generated when the current depth of the queue exceeds the high-depth-alarm setting and the high-depth-alarm activation setting is set at "on."… In a second embodiment, the monitoring component 220 polls the queue periodically to ascertain current attribute values associated with the queue. For example, the current depth of the queue could be retrieved periodically. Having retrieved an attribute value, the attribute value is evaluated against threshold values within the monitoring component 220, such as a high-depth threshold value for a particular queue. The monitoring component 220 would then generate an alarm if the current queue depth exceeds the threshold high-depth value.” The high-depth-alarm setting being at 80% of the maximum allowable depth correlates to a preset maximum ratio. The current depth of the queue correlates to the number of tasks in the target scheduling task queue in the latest monitoring cycle. The previous number of requests in the queue, which can be the maximum allowable depth, correlates to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing. Therefore, comparing the current depth against the high-depth threshold value to generate an alarm if the current queue depth exceeds the threshold value correlates to if a ratio of the number of tasks in the target scheduling task queue in the latest monitoring cycle to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing exceeds a preset maximum ratio), then increasing the maximum number of tasks in storage corresponding to the target task scheduling queue (Fig. 3, Col. 7, lines 50-52 and 63-65 “At step 310, information indicating that a depth level of a queue exceeds an original high-depth setting is received… At step 320, a maximum depth of the queue is increased from an original maximum setting to an updated maximum setting that is larger than the original maximum setting.” The maximum depth of the queue being increased in response to the depth level of the queue exceeding an original high-depth setting correlates to increasing the maximum number of tasks in storage corresponding to the target task scheduling queue).
Leonard does not explicitly teach that wherein an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue. However, increasing the maximum number of tasks in storage [to] not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue is a popular form of queue management as evidenced by Y. Chang (Paragraph 39, “On the other hand, as shown in FIG. 2-FIG. 5D, the capacity of tasks in each of the task queues 232A-232D and the capacity of commands in each of the execution queues 234A-234D are both 4 units, but in some embodiments, the task capacity or the command capacity may be different or modified according to system requirements, which is not limited herein.” The capacity of the task and command queues being modified according to system requirements correlates to increasing the maximum number of tasks in storage. The capacity of a task queue can be modified from 3 to 4 units, and the execution queue can be 4 units as shown in the example. In this scenario, the execution queue can only hold up to 4 units from a task queue which correlates to the single maximum number of tasks extracted corresponding to the target task scheduling queue, and therefore an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with setting the maximum processing delay of each task scheduling queue according to the expected processing delay of each task scheduling queue as taught by Ahuja because latency statistics can be transmitted to an output interface so that a user or application may access the latency statistics. These latency statistics may be re-calculated based on additional queue information to accurately represent the current state of each queue (Ahuja: Col. 14, lines 23-33 and Col. 18, lines 7-24).
Additionally, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with determining a target task scheduling queue whose execution priority level is greater than a preset level and wherein an increased maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the target task scheduling queue as taught by Y. Chang because assigning a priority to tasks to determine which task should be executed first improves the efficiency of the memory system. The priority may be adjustable based on the status of a memory system, with a default priority from high to low prioritizing metadata management, user data access, garbage collection, and wear leveling control (Y. Chang: paragraphs 26 and 28).
Additionally, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with if a ratio of the number of tasks in the target scheduling task queue in the latest monitoring cycle to a total number of all tasks to be executed from the target scheduling task queue and completed in the processing exceeds a preset maximum ratio, then increasing the maximum number of tasks in storage corresponding to the target task scheduling queue as taught by Leonard because increasing the depth of the queue allows the queue to continue receiving messages while the cause of the high-depth condition is identified and corrected. This prevents disruption to the transmission of messages to the queue and decreases the possibility that messages could be lost if the queue becomes full (Leonard: Col. 8, lines 8-13).
With regards to Claim 18, the method of Claim 7 performs the same steps as the machine of Claim 18, and Claim 18 is therefore rejected using the same rationale set forth above in the rejection of Claim 7.
Claim(s) 8 is rejected under 35 U.S.C. 103 as being unpatentable over Lumb in view of D. Chang and Leonard.
With regards to claim 8, Lumb in view of D. Chang teaches the method of claim 2 above. D. Chang further teaches:
wherein according to the task type of the task to be executed, storing the generated task to be executed in the corresponding task scheduling queue comprises:
determining the target task scheduling queue corresponding to the generated task to be executed according to the task type of the task to be executed (Paragraph 34, “Arbitrator and event distributor 210 may receive the task type and the task indicator and assign the task to one of plurality of task queues 230 based at least in part on the task type. In some examples, each task type has an associated task queue.” The task being assigned to a plurality of task queues based on the task type would involve determining a particular task queue based on the task type and therefore correlates to determining the target task scheduling queue corresponding to the generated task to be executed according to the task type of the task to be executed);
storing the generated task to be executed in the corresponding target task scheduling queue (Paragraph 34, “Arbitrator and event distributor 210 may receive the task type and the task indicator and assign the task to one of plurality of task queues 230 based at least in part on the task type. In some examples, each task type has an associated task queue.” The task being assigned to a plurality of task queues based on the task type correlates to storing the generated task to be executed in the corresponding target task scheduling queue).
Lumb in view of D. Chang does not explicitly teach:
determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue based on a storage quantity of the tasks to be executed stored in the target task scheduling queue;
However, Leonard teaches:
determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue based on a storage quantity of the tasks to be executed stored in the target task scheduling queue (Col. 5, lines 63-67, Col. 6, lines 22-25 and 31-40, “Both the low-depth-alarm setting and the high-depth-alarm setting may be based on percentages of the maximum allowable depth. For example, the high-depth-alarm setting could be 80% of the maximum allowable depth and the low-depth-alarm setting could be 20% of the maximum allowable depth… For example, a high-depth-alarm event will be generated when the current depth of the queue exceeds the high-depth-alarm setting and the high-depth-alarm activation setting is set at "on."… In a second embodiment, the monitoring component 220 polls the queue periodically to ascertain current attribute values associated with the queue. For example, the current depth of the queue could be retrieved periodically. Having retrieved an attribute value, the attribute value is evaluated against threshold values within the monitoring component 220, such as a high-depth threshold value for a particular queue. The monitoring component 220 would then generate an alarm if the current queue depth exceeds the threshold high-depth value.” The current depth of a queue exceeding a high-depth-alarm setting of 80% of the maximum allowable depth can involve the current queue depth being at any number above 80% but less than 100% and therefore correlates to determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue based on a storage quantity of the tasks to be executed stored in the target task scheduling queue);
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with when the terminal generates the task to be executed, determining the task type of the task to be executed; according to the task type of the task to be executed, storing a generated task to be executed in a corresponding task scheduling queue as taught by D. Chang because tasks can be assigned to task queues based in part on their task type. Task pointers associated with a processor message can be used to assign a task to a task queue, in addition to additional information associated with the task, such as cache information, to be stored in the queue (D. Chang: paragraphs 33-35).
Additionally, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with determining that the current queue depth of the target task scheduling queue is less than the maximum queue depth of the target task scheduling queue based on a storage quantity of the tasks to be executed stored in the target task scheduling queue as taught by Leonard because alarms can be used to alert a designated responder, such as a person or program designed to respond to queue problems, to a potential problem with the queue in time to take corrective action before the queue reaches maximum depth and messages are turned away. (Leonard: Col. 5, lines 51-55).
Claim(s) 9 is rejected under 35 U.S.C. 103 as being unpatentable over Lumb in view of D. Chang, Ahuja, Y. Chang, Leonard and Miao et al. (U.S. Publication No. US 20190258514 A1), hereinafter “Miao.”
With regards to claim 9, Lumb in view of D. Chang, Ahuja, Y. Chang and Leonard teaches the method of claim 7 above. Lumb in view of D. Chang, Ahuja, Y. Chang and Leonard does not explicitly teach:
obtaining a candidate task scheduling queue with largest total number of pending tasks processed and completed within a monitoring cycle; if an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level, reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue, wherein a reduced maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue.
However, Miao teaches:
obtaining a candidate task scheduling queue with largest total number of pending tasks processed and completed within a monitoring cycle (Paragraphs 68-69, “Correspondingly, the I/O request scheduling apparatus 2231 includes at least two queues a critical queue and a non-critical queue. The critical queue and the non-critical queue store an I/O request of a critical application (referred to as a critical I/O request) and an I/O request of a non-critical application (referred to as a non-critical I/O request), respectively. The I/O request scheduling apparatus 2231 schedules, based on importance of applications corresponding to the queues, the I/O requests stored in the queues to control dispatching of the I/O requests… Even if the I/O requests are dispatched based on the specified ratio, in some cases, excessive I/O requests of a non-critical application may be still probably dispatched to the storage, and therefore block the storage. For example, during a period of time, a critical application does not generate an I/O request corresponding to the critical application, but a non-critical application generates a lot of I/O requests, and these I/O requests are stored to the non-critical queue… After this period of time, the storage is full of to-be-processed non-critical I/O requests.” The non-critical queue storing an excessive number of I/O requests where the storage is full of pending non-critical I/O requests would involve have more pending non-critical I/O requests than the critical queue’s pending and completed tasks combined and therefore correlates to obtaining a candidate task scheduling queue with largest total number of pending tasks processed and completed within a monitoring cycle);
if an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level, reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue (Paragraphs 68-70, “Correspondingly, the I/O request scheduling apparatus 2231 includes at least two queues a critical queue and a non-critical queue. The critical queue and the non-critical queue store an I/O request of a critical application (referred to as a critical I/O request) and an I/O request of a non-critical application (referred to as a non-critical I/O request), respectively. The I/O request scheduling apparatus 2231 schedules, based on importance of applications corresponding to the queues, the I/O requests stored in the queues to control dispatching of the I/O requests. For example, because the critical queue is more important than the non-critical queue… After this period of time, the storage is full of to-be-processed non-critical I/O requests. As a result, an I/O request of the critical application is forced to wait for a long time, resulting in an excessively low response speed for the I/O request of the critical application. Considering the foregoing illustrated case or other possible cases, the I/O request scheduling apparatus 2231 may further monitor an I/O request response speed of the critical queue. If it is determined that the I/O request response speed of the critical queue is excessively low, a queue depth of at least one non-critical queue is reduced to decrease a quantity of I/O requests stored in the non-critical queue.” The non-critical queue having a lower importance than a critical queue correlates to an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level. The storage being full of pending non-critical I/O requests and resulting in low response speeds for critical I/O requests further causing a reduction in queue depth of the non-critical queue to decrease a quantity of I/O requests stored in the non-critical queue correlates to if an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level, reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue).
Miao does not explicitly teach that wherein a reduced maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue. However, reducing a maximum number of tasks in storage [to] not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue is a popular form of queue management as evidenced by Y. Chang (Paragraph 39, “On the other hand, as shown in FIG. 2-FIG. 5D, the capacity of tasks in each of the task queues 232A-232D and the capacity of commands in each of the execution queues 234A-234D are both 4 units, but in some embodiments, the task capacity or the command capacity may be different or modified according to system requirements, which is not limited herein.” The capacity of the task and command queues being modified according to system requirements correlates to increasing the maximum number of tasks in storage. The capacity of a task queue can be modified from 4 to 3 units, and the execution queue can be 4 units as shown in the example. In this scenario, the execution queue can only hold up to 4 units from a task queue which correlates to the single maximum number of tasks extracted corresponding to the candidate task scheduling queue, and therefore a reduced maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with obtaining a candidate task scheduling queue with largest total number of pending tasks processed and completed within a monitoring cycle; if an execution priority of pending tasks stored in the candidate task scheduling queue is lower than the preset level, reducing the maximum number of tasks in storage corresponding to the candidate task scheduling queue as taught by Miao because excessive amounts of non-critical I/O requests can be dispatched to storage even if critical I/O requests are prioritized. This can result in the storage being full of pending non-critical I/O requests, where an I/O request of the critical application is forced to wait for a long time, resulting in an excessively low response speed for the I/O request of the critical application. Lowering the queue depth of at least one non-critical queue to decrease a quantity of I/O requests stored in the non-critical queue can improve the I/O request response speed for critical I/O requests (Miao: paragraphs 69-70).
Additionally, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with wherein a reduced maximum number of tasks in storage does not exceed the single maximum number of tasks extracted corresponding to the candidate task scheduling queue as taught by Y. Chang because assigning a priority to tasks to determine which task should be executed first improves the efficiency of the memory system. The priority may be adjustable based on the status of a memory system, with a default priority from high to low prioritizing metadata management, user data access, garbage collection, and wear leveling control (Y. Chang: paragraphs 26 and 28).
Claim(s) 10 is rejected under 35 U.S.C. 103 as being unpatentable over Lumb in view of D. Chang, and Miao.
With regards to claim 10, Lumb in view of D. Chang teaches the method of claim 1 above. Lumb in view of D. Chang does not explicitly teach:
an execution priority of a foreground task is higher than an execution priority of a background task.
However, Miao teaches:
an execution priority of a foreground task is higher than an execution priority of a background task (Paragraphs 75 and 94, “For example, an application originally runs on the background and belongs to a non-critical application group. When a switch-to-foreground event of the application is detected, it indicates that the application is to switch to run on the foreground. In this case, the application is reclassified to a critical application group… Through timely adjustment of the depth of each queue, the I/O request response time of the critical queue is gradually restored such that a response speed of a critical application (which is a foreground application, a system service, or a user-experience-sensitive background application) corresponding to the critical queue is increased, and user experience is improved.” The application running in the background and belonging to a non-critical application group which is associated with a non-critical queue, and the foreground application being associated with a critical queue correlates to an execution priority of a foreground task is higher than an execution priority of a background task).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Lumb with an execution priority of a foreground task is higher than an execution priority of a background task as taught by Miao because grouping of applications can be used to classify applications as critical or non-critical. Applications can additionally change their grouping through events such as a switch-to-foreground event of the application, which indicates that the application is to switch to run on the foreground. Each queue can have their own weight, so that the priorities of each queue is different, with critical queues having corresponding I/O response time thresholds which can be configured by a user or preset in the system (Miao: paragraphs 75, 82 and 85).
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Tang et al. (U.S. Publication No. US 11314547 B1); teaching a method of task scheduling based on shared bandwidth. A priority of each of the tasks is determined upon receiving a request. Task types for each task are determined and each task is added to a plurality of task queues associated with different task type. Scheduling the tasks is performed based on their priority and bandwidth allocation.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SELINA HU whose telephone number is (571)272-5428. The examiner can normally be reached Monday-Friday 8:30-5:30.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Chat Do can be reached at (571) 272-3721. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
The publicPAIR and privatePAIR systems are no longer available. Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
SELINA HU
Examiner
Art Unit 2193
/Chat C Do/ Supervisory Patent Examiner, Art Unit 2193
Prosecution Insights