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 .
Examiner Notes
Examiner cites particular columns and line numbers in the references as applied to the claims below for convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested that, in preparing responses, the applicant fully consider the references cited in their entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner.
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 6/24/2026 has been entered.
Response to Amendment
The Amendment filed 6/24/2026 has been entered. Claim 7 has been canceled. New claims 22-23 has been added. Claims 1-3, 5-6, 8-10, and 12-23 are pending in the present Office Action.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1, 3, 6, 8, 10, 13, 15, 17, 19, and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Wang et al. (NPL Document: “On Harmonic Fixed-Priority Scheduling of Periodic Real-Time Tasks with Constrained Deadlines”), hereinafter Wang, in view of Li et al. (NPL Document: “Analysis of Federated and Global Scheduling for Parallel and Real-Time Tasks”), hereinafter Li, Colena et al. (U.S. Pub. No. 2022/0027861), hereinafter Colena, MOHANA NARAYANAMURTHY et al. (U.S. Pub. No. 2024/0419506), hereinafter MOHANA NARAYANAMURTHY, and Deshpande (U.S. Patent No. 7,451,447).
Regarding claim 1, Wang teaches a set of computing tasks to be scheduled across a set of shared computing resources, the set of computing tasks comprising a plurality of periodic computing tasks (Page 1, 1. INTRODUCTION – “Multi-core platforms have been mainstream for computing systems and more and more real-time computing systems will be built on multi-core platforms.”; Page 2, 2. PRELIMINARY – “We consider a real-time system consisting of N independent periodic tasks, denoted as Γ = {τ1, τ2, . . . , τN}, ordered by their priorities based on deadline monotonic scheduling (DMS) policy. Assume Γ is to be scheduled on a homogeneous multi-core platform, denoted as P = {p1, p2, ...pM}, according to DMS. Each task τi ∈ Γ is characterized by a tuple (Ci,Di, Ti), representing the worst case execution time, the relative deadline and the inter-arrival time (period), respectively. […] Problem 1. Given (i) task set Γ = {τ1, τ2, . . . , τN} and (ii) multi-core platform P = {p1, p2, ...pM}, partition Γ on P such that all tasks can meet their deadlines and the number of cores used is minimized […] we assign tasks τ1 and τ2 together to one processor and task τ3, τ4 and τ5 to another processor. Again, since task τ6 cannot be assigned to either of the two processors, we still have to allocate one more processor to schedule task τ6.”); and obtain a […] solution for scheduling the set of computing tasks across the set of shared computing resources; wherein the […] solution assigns two or more periodic computing tasks in the plurality of periodic computing tasks to a same computing resource in the set of shared computing resources, based at least on the two or more periodic computing tasks having periods that are harmonically compatible (Page 2, 2. PRELIMINARY – “A key to solve problem stated above is to partition real-time tasks in a way that can best utilize the processors. Consider the task set with six tasks shown in Table 1. […] Since harmonic tasks can better utilize a processor, an intuitive approach is therefore to allocate tasks with same periods (or tasks with periods being integer multiples of each other) to the same core. Specifically, for the six tasks above, we assign tasks τ1 and τ2 together to one processor and task τ3, τ4 and τ5 to another processor. Again, since task τ6 cannot be assigned to either of the two processors, we still have to allocate one more processor to schedule task τ6.”).
Wang fails to expressly teach One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations comprising: determining the set of tasks; monitoring performance of a computer system to obtain historical telemetry data associated with the set of computing tasks; based at least in part on the historical telemetry data, determining a plurality of usage statistics associated respectively with the set of computing tasks; filtering out one or more high-utilization computing tasks from the set of computing tasks to be scheduled; generating a constraint programming (CP) model based on the set of computing tasks, the CP model comprising a set of constrained variables, a set of constraints, and a search directive; wherein the set of constrained variables comprises execution-time variables, domains of which are upper-bounded by respective execution periods of periodic tasks, that specify execution times for the periodic tasks within the respective execution periods; wherein the search directive comprises an objective function configured to minimize a total cost element; wherein a domain of the total cost element comprises a maximum value determined based at least in part on the plurality of usage statistics; applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources; without receiving user input that indicates approval of the CP solution, scheduling the set of computing tasks as indicated by the CP solution.
However, Li teaches filtering out one or more high-utilization computing tasks from the set of computing tasks to be scheduled (Page 85, Abstract – “The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores.”; Page 87, III. Federated Scheduling, A. Federated Scheduling Algorithm – “First, tasks are divided into two disjoint sets: ͳhigh contains all high-utilization tasks — tasks with worst-case utilization at least one (ui ≥ 1), and ͳlow contains all the remaining low-utilization tasks. Consider a high-utilization task ͳi […] We assign ni dedicated cores to ͳi […] After a valid core allocation, runtime scheduling proceeds as follows: (1) Any greedy (work-conserving) parallel scheduler can be used to schedule a high-utilization task ͳi on its assigned ni cores. Informally, a greedy scheduler is one that never keeps a core idle if some node is ready to execute. (2) Low-utilization tasks are treated and executed as though they are sequential tasks and any multiprocessor scheduling algorithm (such as partitioned EDF [37], or various rate-monotonic schedulers [3]) with a utilization bound of at most 1/2 can be used to schedule all the low-utilization tasks on the allocated nlow cores.”).
Wang and Li are considered to be analogous art to the claimed invention because they are in the same field as the claimed invention of scheduling a plurality of periodic tasks to a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang to incorporate the teachings of Li such that one or more high utilization tasks are filtered out from the set of tasks to be scheduled as taught by Li. Doing so ensures the low-utilization tasks to be executed on shared resources can be treated as sequential tasks and parallel execution is not required to meet their deadlines (Li: Page 88, III. Federated Scheduling, A. Federated Scheduling Algorithm). Further, allocating the minimum number of dedicated cores to the high-utilization tasks ensures they are schedulable, so that there is no preempting a high-utilization task and the number of migrations is minimized, thereby reducing overhead (Li: Page 95, VII. Practical Considerations).
The combination of Wang in view of Li fails to expressly teach One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations comprising: determining the set of tasks; monitoring performance of a computer system to obtain historical telemetry data associated with the set of computing tasks; based at least in part on the historical telemetry data, determining a plurality of usage statistics associated respectively with the set of computing tasks; generating a constraint programming (CP) model based on the set of computing tasks, the CP model comprising a set of constrained variables, a set of constraints, and a search directive; wherein the set of constrained variables comprises execution-time variables, domains of which are upper-bounded by respective execution periods of periodic tasks, that specify execution times for the periodic tasks within the respective execution periods; wherein the search directive comprises an objective function configured to minimize a total cost element; wherein a domain of the total cost element comprises a maximum value determined based at least in part on the plurality of usage statistics; applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources; without receiving user input that indicates approval of the CP solution, scheduling the set of computing tasks as indicated by the CP solution.
However, Colena teaches One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations ([0338] – “a non-transitory computer readable storage medium comprises instructions which, when executed by one or more hardware processors, causes performance of any of the operations described herein”) comprising: determining the set of tasks ([0170] – “One or more embodiments include identifying a set of maintenance tasks to be performed for the set of machines (Operation 204). […] Additionally or alternatively, the data packet generator 126 may obtain instructions, which when executed by at least one device including a hardware processor, performs one or more maintenance tasks.”; [0300]-[0301] – “one or more embodiments include generating a set of instructions for performing the set of maintenance tasks based on the proposed maintenance schedule (Operation 606). […]. Additional instructions are determined, specified, and/or obtained for scheduling execution of the instructions for performing each maintenance task according to the proposed maintenance schedule. The instructions are executable by at least one device including a hardware processor.”; [0304]-[0305] – “One or more embodiments include performing the set of maintenance tasks according to the proposed maintenance schedule (Operation 608). One or more maintenance resources accept the set of instructions generated at Operation 606. Based on the set of instructions, the maintenance resources perform the set of maintenance tasks according to the proposed maintenance schedule. As an example, a proposed maintenance schedule may indicate that a first maintenance task is scheduled for 9 am and a second maintenance task is scheduled for 10 am. A master server may generate instructions for performing the first maintenance task at 9 am and the second maintenance task at 10 am. The master server may execute the instructions. According to the instructions, the master server may perform the first maintenance task at 9 am and the second maintenance task at 10 am.” The tasks may be scheduled to be executed/performed by the same set of maintenance resource(s), e.g., the master server described in [0305], thus, the maintenance resources are shared by the tasks.); […] generating a constraint programming (CP) model based on the set of computing tasks ([0031] – “Constraint programming (CP) is a form of declarative programming. CP obtains a solution to a real-world problem based on a specification of a CP data model and optionally a CP search directive.”; [0034] – “One or more embodiments include generating a CP data model, to be applied to a CP solver, for determining a proposed maintenance schedule for performing a set of machine maintenance tasks”; [0196] – “FIGS. 3A-B illustrates an example set of operations for generating a constraint programming data model, in accordance with one or more embodiments.”), the CP model comprising a set of constrained variables ([0197]-[0198] – “One or more embodiments include specifying a set of task elements, each task element representing a maintenance task (Operation 302). A data model generator 114 specifies a set of task elements.” […] One or more embodiments include specifying domains of the task elements, each domain representing candidate time windows for performing a maintenance task (Operation 304).”; [0203]-[0204] and [0211]-[0212] – other constrained variables (i.e., variables constrained to a domain) may include time elements and cost elements), a set of constraints ([0248] – “One or more embodiments include generating a data model including the task elements, the time elements, the cost elements, the total cost element, the global cardinality constraint, the element constraint, and the sum constraint (Operation 324). The data model generator 114 generates a data model including the task elements, the time elements, the cost elements, the total cost element, the global cardinality constraint, the element constraint, and the sum constraint.”) and a search directive ([0033] – “A CP search directive guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a CP data model. The CP search directive prioritizes the assignment of certain preferred values over other values for one or more elements. Different CP search directives for a same CP data model may result in a different ordering of CP solutions.”; [0252]-[0253] – “FIG. 4 illustrates an example set of operations for generating a constraint programming search directive, in accordance with one or more embodiments. One or more embodiments include specifying one or more instructions for identifying a target task element (Operation 402). A search directive generator 116 determines, specifies, and/or obtains instructions and/or operations for traversing each of the set of task elements specified at Operation 302.”); wherein the set of constrained variables comprises execution-time variables, domains of which are [bounded to respective execution time windows], that specify execution times for the […] tasks within the respective execution [windows] ([0084] – “A domain of a task element indicates candidate time windows for performing the maintenance task represented by the task element)”; [0198] – “specifying domains of the task elements, each domain representing candidate time windows for performing a maintenance task (Operation 304). The data model generator 114 specifies domains of the task elements.”; [0301] – “instructions for performing each maintenance task is obtained from a data repository. Additional instructions are determined, specified, and/or obtained for scheduling execution of the instructions for performing each maintenance task according to the proposed maintenance schedule. The instructions are executable by at least one device including a hardware processor.”) wherein the search directive comprises an objective function configured to minimize a total cost element ([0034] and [0037] – “One or more embodiments include generating a CP data model, to be applied to a CP solver, for determining a proposed maintenance schedule for performing a set of machine maintenance tasks, while satisfying at least one or more of the following objectives: […] (c) minimizing a total cost value for performing the set of maintenance tasks”; [0098] – “an objective of the CP solver is to minimize a total cost value”; [0153] – “a search directive 125 is a directive that guides a CP solver 132 in the process of determining a CP solution given a particular data model 120. A search directive 125 guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a data model 120. A search directive 125 prioritizes the assignment of certain values over other values for one or more data model elements. Different search directives 124 for a same data model 120 may result in a different ordering of CP solutions”; [0268] – “FIG. 5 illustrates an example set of operations applying a constraint programming data model and search directive to a constraint programming solver, in accordance with one or more embodiments. The CP data model and search directive are iteratively applied to determine a CP solution associated with a total cost element assigned with a lowest total cost value (as compared with other possible CP solutions).”; [0287]-[0292] and [0294] – describes the process of the CP solver iteratively determining CP solutions and ordering them by their assigned total cost element, to find one with a minimum total cost value); wherein a domain of the total cost element comprises a maximum value ([0044] – “A domain of a total cost element indicates possible total cost values for performing the set of maintenance tasks.”; [0050] – “A total cost value associated with a prior solution obtained by the CP solver is used as an upper bound for the domain of the total cost element in a next iteration of the CP solver.”) […] applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources ([0159] – “In one or more embodiments, a proposed maintenance schedule 134 is a schedule for performing one or more maintenance tasks 104a-b based on a CP solution determined by a CP solver 132. The CP solution is determined based on a data model 120 and optionally a search directive 125.”; [0268] – “FIG. 5 illustrates an example set of operations applying a constraint programming data model and search directive to a constraint programming solver, in accordance with one or more embodiments. The CP data model and search directive are iteratively applied to determine a CP solution”; [0283] – “Based on assignment of a time window to a task element, the CP solver 132 returns a proposed maintenance schedule indicating that the maintenance task represented by the task element is scheduled for performance during the assigned time window.”; [0303]-[0304] – the maintenance resources perform the tasks according to the proposed maintenance schedule returned by the CP solver.); without receiving user input that indicates approval of the CP solution, scheduling the set of computing tasks as indicated by the CP solution ([0054] – “Additionally or alternatively, maintenance resources obtain the proposed maintenance schedule. The maintenance resources perform the maintenance tasks according to the proposed maintenance schedule. The maintenance tasks may be performed with or without human intervention.”; [0161] – “In some embodiments, maintenance resources 136 includes only machines, computing devices, and/or tools, without any human intervention. Performance of a maintenance task is hence fully automated.”; [0299] – “user input accepting the proposed maintenance schedule is not necessary. The proposed maintenance schedule output from the CP solver is adopted without human intervention.”).
Colena is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor of generating a schedule for a plurality of constrained tasks to be performed by a set of shared resources. It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have modified the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be implemented as instructions stored on a non-transitory computer-readable storage media to be executed by a hardware processor as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang and Li teaching the periodic tasks being scheduled for execution on processor(s), and would know that computing components and/or logic implemented by computing components, such as a non-transitory computer-readable media storing instructions to be executed by one or more hardware processors, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors as a result of a hardware processor executing instructions stored on a non-transitory computer readable media as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks as a result of a hardware processor executing instructions stored on a non-transitory computer readable media) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors. Further, it would have been obvious to one of ordinary skill in the art to have modified the methods of scheduling of a plurality of periodic tasks as taught by Wang in view of Li to use constraint programming techniques to generate the schedule as taught by Colena. Constraint programming techniques offer an efficient means for obtaining a schedule for performing a set of tasks which satisfies multiple objectives, e.g., satisfies multiple constraints, and allows for parameters of the problem to change, e.g., the tasks can change, without having to change the constraints (see Colena: [0049]).
The combination of Wang in view of Li and Colena fails to expressly teach monitoring performance of a computer system to obtain historical telemetry data associated with the set of computing tasks; based at least in part on the historical telemetry data, determining a plurality of usage statistics associated respectively with the set of computing tasks; domains of the execution-time variables are upper-bounded by respective execution periods of periodic tasks, that specify execution times for the periodic tasks within the respective execution periods, and wherein the search directive comprises an objective function configured to minimize a total cost element; wherein a domain of the total cost element comprises a maximum value determined based at least in part on the plurality of usage statistics.
However, MOHANA NARAYANMURTHY teaches monitoring performance of a computer system to obtain historical telemetry data associated with the set of computing tasks ([0020] – “Each of the workloads 136-138 illustratively represent one or more services that are deployed in containers 142-144. The containers 142-144 include monitors 146-148 and other items 150-152. As is discussed in greater detail below, monitors 146-148 perform runtime monitoring of various characteristics and parameters of the workloads to which they belong. The characteristics and parameters can include quality of service parameters, resource usage parameters, among others.”; [0023] – “historical workload data 132 that represents historical QoS and resource usage of the various containers in which each workload 136-138 is running.”; [0030] – “a monitor that monitors resource usage 206 instantaneously or over time.”); based at least in part on the historical telemetry data, determining a plurality of usage statistics associated respectively with the set of computing tasks ([0033] – “Based upon the runtime feedback signals and the historical workload data 132, analytics and prediction engine 154 generates a predictive future workload state for workload 136, as indicated by block 218. The future workload state can be indicative of a predictive quality of service (or latency) 220, a predicted resource usage level 222, or other predicted future values indicative of the state of the workload 136, as indicated by block 224.”; [0037]-[0038] – “The container size identifier 157 may obtain the request and limit amounts as well as any historical resource usage statistics and quality of service metrics for the workload, as indicated by block 258 in the flow diagram of FIG. 3. The resource usage and quality of service metrics may be at peak operation times 260, and they may identify container level percentages, such as the peak usage, the maximum and minimum usage, the different percentiles of usage, such as 5%, 95%, 99%, etc. Identifying the historical resource usage in terms of container level percentiles is indicated by block 262 in the flow diagram of FIG. 3. The historical resource usage statistics may include the mean, variance, and other information, as indicated by block 264, latency information 266, and any of a wide variety of other resource usage statistics and quality of service metrics, as indicated by block 268. Based upon the historical resource usage statistics and quality of service metrics, the container size identifier 157 in decision engine 156 controls the solver engine 162 in bin packing policy system 158 to obtain container size parameters (R and L) for each of the different types of resources being considered.”); an objective function configured to minimize a total cost element ([0044]-[0050] – “how server cluster identifier 159 and node identifier 161 are used to place the containers for a single workload, once they have been sized by container size identifier 157, on different server clusters and nodes, in an efficient way. […] Once a set of candidate clusters have been identified, then server cluster identifier 159 selects one of the server clusters C, as indicated by block 288 and calculates a space cost function for the space cost of adding workload W to cluster C, as indicated by block 290. […] Server cluster identifier 159 then calculates a time cost function for the cost of adding workload W to the server cluster C. The time cost function may find services with resource utilization peaks that match the resource utilization valleys of other workloads so that the resources in the server cluster can be shared among those workloads without sacrificing performance, as indicated by block 297. […] Server cluster identifier 159 then calculates the combined cost (both the space and time cost) of adding workload W to cluster C, as indicated by block 300. […] Once all of the candidate clusters have been evaluated, then server cluster identifier 159 identifies the particular server cluster C that has the least cost, as indicated by block 304. The workload W is then assigned to the identified cluster C, as indicated by block 306. […] Node identifier 161 can then identify the particular node within the server cluster C using both time and space related costs, in a similar way to which the particular server cluster C was identified”; [0053]-[0056] – “Again, the space cost of merging the two workloads can be based upon the number of nodes needed for each workload, as indicated by block 322, or other space considerations 324.Server cluster identifier 159 then calculates the temporal cost of merging the groups, as indicated by block 326. The temporal cost can be based on the peak CPU usage of each workload, as indicated by block 328, or based upon other cost criteria, as indicated by block 330. Server cluster identifier 159 then calculates the total cost of each of the proposed merged groups and ranks the proposed merged groups based upon the total cost associated with each proposed merged group, as indicated by block 332. [... ] if at block 346, the stopping criteria have been met, then server cluster identifier 159 generates an output to assign the workloads to server clusters based upon the merged groups.") wherein a domain, i.e., possible values, of the total cost element comprises a maximum value determined based at least in part on the plurality of usage statistics ([0028] – “Server cluster identifier 159 then identifies the particular server cluster 121 for deployment of the containers 142-144 in workload 136. Node identifier 161 identifies the particular node for deployment of those containers. Detecting the server cluster and node placement is indicated by block 188 in the flow diagram of FIG. 2. Identifying the server cluster and node placement can be based on a determination as to how to achieve a best balanced resource usage, as indicated by block 190. The placement on a particular server cluster and node can be based on peak resource usage of the workload as indicated by block 192, or based on other criteria 194.”; [0033]-[0034] – a bin packing action output from server cluster identifier 159 (e.g., a placement of workloads on the server clusters) or based on output from node identifier 161 (e.g. a placement of workloads on the nodes within server clusters) may be determined based on data from runtime feedback monitors 146-148 and data from analytics and prediction engine 154, which is based on historical workload data 132; [0055] – “temporal cost can be based on the peak CPU usage of each workload”; [0044]-[0050] and [0053]-[0056] – a total cost is calculated for each candidate cluster/merged group of workloads, where the total cost may be based on resource usage, e.g., resource utilization peaks, and the total costs are ranked as described in [0055]. In a set of ranked total costs (i.e., the “domain of the total cost element”), there is necessarily one total cost which is a maximum (i.e., largest) cost, similar to how there is a total cost which is a minimum as described in paragraph [0049].).
MOHANA NARAYANAMURTHY is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor in assigning a plurality of tasks to a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li and Colena, which include a CP model with an objective function to minimize a total cost element, to include monitoring a computer system to obtain historical telemetry data associated with the set of tasks and determining a plurality of usage statistics associated with the set of computing tasks based on the historical telemetry data, such that a domain of the total cost element to be minimized is based, at least in part, on the usage statistics as taught by MOHANA NARAYANMURTHY. Incorporating the methods of MOHANA NARAYANMURTHY would enable the system to perform workloads, i.e., computing tasks, in a highly efficient manner, with fewer resources, and enables runtime adjustment of the placement and the resources allocated to the workloads being performed based on historical resource usage in addition to currently monitored and predicted resource usage (MOHANA NARAYANMURTHY: [0015]-[0016], [0025], and [0063]).
The combination of Wang in view of Li, Colena, and MOHANA NARAYANMURTHY fails to expressly teach domains of the execution-time variables are upper-bounded by respective execution periods of periodic tasks, where the execution-time variables specify execution times for the periodic tasks within the respective execution periods.
However, Deshpande teaches domains, i.e., possible values, of the execution-time variables are upper-bounded by respective execution periods of periodic tasks, where the execution-time variables specify execution times for the periodic tasks within the respective execution periods (Col. 3, lines 35-40 – “another characteristic of real-time tasks is whether they are periodic or aperiodic. An aperiodic task has a deadline by which it must finish or start, or it may have a constraint on both start and finish time. In the case of a periodic task, the requirement may be stated as "once per period T" or "exactly T units apart."; ”Col. 5, line 64-Col. 6, line 2 – “static table-driven scheduling is applicable to tasks that are periodic. Input to the analysis consists of the periodic arrival time, execution time, period ending deadline, and relative priority of each task. The scheduler attempts to develop a schedule that enables it to meet the requirements of all periodic tasks.”; Col. 7, line 64-Col. 8, line 10 – “in RMS, the task's period T is the amount of time between the arrival of one instance of the task and the arrival of the next instance of the task. […] Typically, the end of a task's period is also the task's hard deadline, although some tasks may have earlier deadlines. The execution (or computation) time C is the amount of processing time required for each occurrence of the task. […] the execution time must be no greater than the period (must have C≤T).” A periodic task’s execution time within its respective period is upper-bounded (less than or equal to) its period.).
Deshpande is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks to a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the execution time variables, domains of which include possible execution times for the tasks, as taught by Colena, such that the domain (possible values for the execution time) is upper-bounded by respective execution periods of periodic tasks as taught by Deshpande. Doing so would ensure the timing requirements and deadlines of the tasks are met by the selected schedule, e.g., to avoid damage or errors in the system (Deshpande: Col. 3, lines 6-40 and Col. 8, lines 22-42).
Regarding claim 3, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY and Deshpande teaches the one or more non-transitory computer-readable media of claim 1. Li teaches the operations further comprising: prohibiting any computing tasks in the set of computing tasks whose duration exceeds an upper period threshold from collocation with any periodic computing task in the plurality of periodic computing tasks (Page 85, Abstract – “The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores.”; Page 87, II. System Model – “the minimum inter-arrival time (or period) Ti represents the time between consecutive arrivals of task instances, […] In this paper, we consider implicit deadline tasks where each task ͳi’s relative deadline Di is equal to its minimum inter-arrival time Ti; that is, Ti = Di. We consider the schedulability of this task set on a uniform multicore system consisting of m identical cores. […] total execution time (or work) Ci of task ͳi: This is the summation of the worst-case execution times of all the subtasks of task ͳi. […] the utilization
C
i
T
i
=
C
i
D
i
of task ͳi is denoted by ui for implicit deadlines.” ; Page 89, V. Canonical Form of a DAG Task – “in this paper, we analyze tasks with implicit deadline, so period equals to deadline (Ti = Di). Recall that we classify each task ͳi as a low-utilization if ui = Ci/Di < 1 (and hence Ci < Dii; or high-utilization task, if ͳi’s utilization ui ≥ 1.” Utilization is the execution time divided by the period, thus utilization is greater than 1 when the execution time (“duration”) exceeds the period. Any task whose execution time exceeds its period (i.e., its “upper period threshold”) is classified as a high-utilization task and assigned its own dedicated set of cores, thereby prohibiting collocation with any other periodic tasks.).
It would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang to incorporate the teachings of Li such that one or more high utilization tasks are assigned their own dedicated resources and thus prohibited from collocating with other tasks as taught by Li. Doing so ensures the low-utilization tasks to be executed on shared resources can be treated a sequential tasks and parallel execution is not required to meet their deadlines (Li: Page 88, III. Federated Scheduling, A. Federated Scheduling Algorithm). Further, allocating the minimum number of dedicated cores to the high-utilization tasks ensures they are schedulable, so that there is no preempting a high-utilization task and the number of migrations is minimized, thereby reducing overhead (Li: Page 95, VII. Practical Considerations).
Regarding claim 6, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the one or more non-transitory computer-readable media of claim 1. Colena further teaches wherein the CP model further comprises the total cost element constrained to [a domain of cost values for performing] the set of computing tasks ([0050] – “One or more embodiments include iteratively applying a CP data model to a CP solver to obtain a proposed maintenance schedule. A total cost value associated with a prior solution obtained by the CP solver is used as an upper bound for the domain of the total cost element in a next iteration of the CP solver.”; [0077]-[0082] – “data model elements 122 in a data model include at least: […] (d) a total cost element. […] A domain of a total cost element indicates possible total cost values for performing the set of maintenance tasks.”; [0268] – “The CP data model and search directive are iteratively applied to determine a CP solution associated with a total cost element assigned with a lowest total cost value (as compared with other possible CP solutions).”.
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
MOHANA NARAYANAMURTHY further teaches the cost element constrained to a peak number of resources consumed by the set of computing tasks ([0005] – “ An efficiency engine identifies container sizes for containers of a workload and allocates the containers across server clusters and nodes based on peak resource usage requirements of the containers.”; [0036]-[0038] – “optimizing or otherwise selecting or identifying the sizes of the various containers 142-144 in which the workload 136 will be deployed. It is first assumed that a request (R) and a limit (L) are parameters that are defined for each type of resource in cloud resource inventory 127. […] The request represents the amount of resources that may be required by a container once the container is scheduled. […] The limit may be the maximum amount of resources that can be used by the container. […] The resources for which a request and limit may be defined may include CPU cores 250, memory 252, network bandwidth 254, and other resources 256. The container size identifier 157 may obtain the request and limit amounts as well as any historical resource usage statistics […] The resource usage and quality of service metrics may be at peak operation times 260, and they may identify container level percentages, such as the peak usage, the maximum and minimum usage, the different percentiles of usage, such as 5%, 95%, 99%, etc. […] Based upon the historical resource usage statistics and quality of service metrics, the container size identifier 157 in decision engine 156 controls the solver engine 162 in bin packing policy system 158 to obtain container size parameters (R and L) for each of the different types of resources being considered.”; [0044] – “how server cluster identifier 159 and node identifier 161 are used to place the containers for a single workload, once they have been sized by container size identifier 157, on different server clusters and nodes, in an efficient way.”; [0047] – “Server cluster identifier 159 then calculates a time cost function for the cost of adding workload W to the server cluster C. The time cost function may find services with resource utilization peaks that match the resource utilization valleys of other workloads so that the resources in the server cluster can be shared among those workloads without sacrificing performance”; [0053]-[0056] – “the space cost of merging the two workloads can be based upon the number of nodes needed for each workload, as indicated by block 322, or other space considerations 324. Server cluster identifier 159 then calculates the temporal cost of merging the groups, as indicated by block 326. The temporal cost can be based on the peak CPU usage of each workload, as indicated by block 328, or based upon other cost criteria, as indicated by block 330. Server cluster identifier 159 then calculates the total cost of each of the proposed merged groups and ranks the proposed merged groups based upon the total cost associated with each proposed merged group, as indicated by block 332. […] if, at block 346, the stopping criteria have been met, then server cluster identifier 159 generates an output to assign the workloads to server clusters based upon the merged groups.”).
It would have been obvious to one of ordinary skill in the art to have modified the CP model for which the CP solver is to generate a CP solution which assigns the plurality of tasks to the set of shared resources as taught by Wang in view of Li and Colena to include a cost element constrained to a peak number of resources consumed by the set of tasks as suggested by MOHANA NARAYANMURTHY. Incorporating the methods of MOHANA NARAYANMURTHY would enable the system to perform workloads, i.e., tasks, in a highly efficient manner, with fewer resources, and enables runtime adjustment of the resources allocated to and placement of the workloads being performed based on predicted resource usage (MOHANA NARAYANMURTHY: [0015]-[0016], [0025], and [0063]).
Regarding claim 8, Colena teaches A system (computer system 800) comprising:
one or more hardware processors (processor 804);
one or more non-transitory computer-readable media (storage device 810); and
program instructions stored on the one or more non-transitory computer readable media which, when executed by the one or more hardware processors, cause the system to perform operations ([0324] – “FIG. 8 is a block diagram that illustrates a computer system 800 upon which an embodiment of the invention may be implemented. Computer system 800 includes […] a hardware processor 804”; [0328]-[0329] – “According to one embodiment, the techniques herein are performed by computer system 800 in response to processor 804 executing one or more sequences of one or more instructions contained in main memory 806. Such instructions may be read into main memory 806 from another storage medium, such as storage device 810. Execution of the sequences of instructions contained in main memory 806 causes processor 804 to perform the process steps described herein. […] The term "storage media" as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 810.”) comprising: the operations of claim 1. Accordingly, claim 8 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 1.
For clarity of the record, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to modify the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be implemented in a system comprising one or more hardware processors and one or more non-transitory computer-readable storage media storing instructions to be executed by the hardware processors as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang and Li teaching the periodic tasks being scheduled on processor(s), and would know that computing components and/or logic implemented by computing components, such as a system comprising one or more hardware processors and one or more non-transitory computer-readable media storing instructions to be executed by the one or more hardware processors, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors as a result of a hardware processor executing instructions stored on a non-transitory computer readable media in a system as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks as a result of a hardware processor executing instructions stored on a non-transitory computer readable media in a system) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors.
Claim 10 recites substantially the same limitations as those recited in claim 3, applied to the system of claim 8. Accordingly, claim 10 is rejected as being unpatentable over Wang in view of Li and Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 3.
Claim 13 recites substantially the same limitations as those recited in claim 6, applied to the system of claim 8. Accordingly, claim 13 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 6.
Regarding claim 15, Colena teaches A method comprising: the operations of claim 1; wherein the method is performed by at least one device including a hardware processor (FIGS. 2-6; [0328] – “Execution of the sequences of instructions contained in main memory 806 causes processor 804 to perform the process steps described herein.”). Accordingly, claim 15 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 1.
For clarity of the record, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to modify the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be performed by at least one device including a hardware processor as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang teaching the periodic tasks being scheduled on processor(s), and would know that computing components and/or logic implemented by computing components, such as a device including a hardware processor, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors by a device comprising a hardware processor as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks using a device comprising a hardware processor) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors.
Claim 17 recites substantially the same limitations as those recited in claim 3, applied to the method of claim 15. Accordingly, claim 17 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 3.
Claim 19 recites substantially the same limitations as those recited in claim 6, applied to the method of claim 15. Accordingly, claim 19 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande for the same reasons presented with respect to claim 6.
Regarding claim 21, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the method of claim 15. Colena teaches the method further comprising: executing the set of computing tasks according to the CP solution ([0159] – “a proposed maintenance schedule 134 is a schedule for performing one or more maintenance tasks 104a-b based on a CP solution determined by a CP solver 132.”; [0304] – “One or more embodiments include performing the set of maintenance tasks according to the proposed maintenance schedule (Operation 608). One or more maintenance resources accept the set of instructions generated at Operation 606. Based on the set of instructions, the maintenance resources perform the set of maintenance tasks according to the proposed maintenance schedule.”; [0054] – “Additionally or alternatively, maintenance resources obtain the proposed maintenance schedule. The maintenance resources perform the maintenance tasks according to the proposed maintenance schedule. The maintenance tasks may be performed with or without human intervention.”; [0161] – “In some embodiments, maintenance resources 136 includes only machines, computing devices, and/or tools, without any human intervention. Performance of a maintenance task is hence fully automated.”).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques for generating a schedule by which tasks are executed as taught by Colena. Doing so provides a more efficient way of generating an optimal schedule for performing a plurality of tasks (Colena: [0049]).
Claims 2, 9, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claims 1, 8, and 15 above, and further in view of Prantner et al. (U.S. Pub. No. 2020/0326980), hereinafter Prantner.
Regarding claim 2, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the one or more non-transitory computer-readable media of claim 1, but fails to expressly teach the operations further comprising: prohibiting collocation of any periodic computing tasks that are harmonically incompatible; wherein a first periodic computing task and a second periodic computing task are harmonically incompatible if (a) a first period of the first periodic computing task is not evenly divisible by a second period of the second periodic computing task and (b) the second period is not evenly divisible by the first period.
However, Prantner teaches prohibiting collocation of any periodic computing tasks that are harmonically incompatible; wherein a first periodic computing task and a second periodic computing task are harmonically incompatible if (a) a first period of the first periodic computing task is not evenly divisible by a second period of the second periodic computing task and (b) the second period is not evenly divisible by the first period ([0134]-[0136] – “The need for high periodic tasks, for example which need to be scheduled every 2 ms, and disharmonic task periods, for example wherein a first task has to be scheduled every 2 ms, and a second task has to be scheduled every 5 ms, create a high number of timer events. According to embodiments, as it will be explained in the following, the virtual machines having respectively at least one real-time attribute. At least one the real time attribute of a first virtual machine is different to the corresponding real-time attribute of a second virtual machine. The real-time attribute are typically defined before the schedule of the virtual machines is determined. […] the real-time attribute is a set of task periods of the respective virtual machine. For each virtual machine, a set of task periods includes task periods of tasks of the virtual machine without task periods of tasks of the same virtual machine, which are multiples of other task periods. According to an embodiment, the high periodic tasks are separated from the low periodic tasks and are assigned to the first VM. For example, a first virtual machine includes one or more periodic tasks to be handled within a first minimum task period and a second virtual machine including only one or more periodic tasks to be handled at least at a second minimum task period, being greater than the first minimum task period, wherein the first period is not a whole number factor of the second period. […] the real-time attribute corresponds to the set of task periods. In particular the tasks are provided such that the lowest task period in the first set of task periods of a first virtual machine is different to the lowest task period in the second set of task period, in particular to the lowest task period of the set of task periods of all other virtual machines, wherein, in particular the lowest task period of the first set of task periods is lower that the lowest task period of the second set of task periods and not a whole number factor of the lowest task period of the second set of task periods.” The set of task periods for tasks assigned to a particular virtual machine are the same task period (e.g. task period A) or a multiple of the task period (e.g., is a multiple of task period A, which would be evenly divisible by the task period A). The set of task periods for the virtual machine exclude/prohibit (“without”) task periods of tasks which are multiples of other task periods/is not a whole number factor of the task period (e.g., tasks with task period B/multiples of task period B, where B > A, are assigned to a different virtual machine, where task period B is not evenly divisible by task period A, i.e., A is not a “whole number factor” of B, and A is not evenly divisible by B since B is greater than A).).
Prantner is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks on a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande to incorporate the teachings of Prantner to prohibit colocations of harmonically incompatible tasks (i.e., prohibiting assignment of a first task to a same resource as a second task, where the period of the first task is not evenly divisible by/a multiple of the period of second task). Incorporating the teachings of Prantner where periodic tasks are split into harmonically compatible groups for scheduling on a same computing resource (e.g., sets of tasks assigned to a particular virtual machine) would allow for reduction in scheduling time and system load, e.g., due to disharmonic task periods (Prantner: [0134]), and would minimize the number of VM switches when the computing resources are virtual machines (Pranter: [0119] and [0137]). Further, Wang teaches it is a well-known fact that harmonic tasks, i.e., tasks with periods being integer multiples of each other, can achieve better utilization on the same resource; thus, avoiding/prohibiting assigning harmonically incompatible tasks to the same resource in favor of scheduling only harmonic tasks to a same resource would allow for higher processor utilization to be achieved (Wang: 1. Introduction – Page 1).
Claim 9 recites substantially the same limitations as those recited in claim 2, applied to the system of claim 8. Accordingly, claim 9 is rejected as being unpatentable over Wang in view of Li, Colena, and MOHANA NARAYANMURTHY, Deshpande and further in view of Prantner, for the same reasons presented with respect to claim 2.
Claim 16 recites substantially the same limitations as those recited in claim 2, applied to the method of claim 15. Accordingly, claim 16 is rejected as being unpatentable over Wang in view of Li, Colena, and MOHANA NARAYANMURTHY, Deshpande, and further in view of Prantner, for the same reasons presented with respect to claim 2.
Claims 5, 12, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claims 1, 8, and 15 above, and further in view of Kadioglu et al. (U.S. Pub. No. 2016/0306671), hereinafter Kadioglu.
Regarding claim 5, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the one or more non-transitory computer-readable media of claim 1. Colena further teaches wherein the set of constrained variables comprises: […] a second set of constrained variables corresponding to task execution time ([0172]-[0173] – “One or more embodiments include identifying a set of candidate time windows for performing the set of maintenance tasks (Operation 206). […] The set of candidate time windows for performing the set of maintenance tasks may be determined based on availability of maintenance resources. The duration of each candidate time window may be the same or different. The data packet generator determines possible time windows for performing each maintenance task. […] As an example, a time window restriction may indicate that a particular maintenance task may be performed during only a subset of a set of candidate time windows.”; [0198] – “One or more embodiments include specifying domains of the task elements, each domain representing candidate time windows for performing a maintenance task (Operation 304). The data model generator 114 specifies domains of the task elements. Each domain may be represented by a vector, an array, and/or any other data structure. A domain for a particular task element represents the set of candidate time windows for performing a maintenance task represented by the particular task element.”; [0170] and [0301] – performing a task may be executing instructions by a processor.).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]). Further, Wang suggests periodic tasks to be scheduled across a set of processors may have constrained deadlines, i.e., deadlines less than or equal to their period, that should be considered in scheduling the tasks (Wang: ABSTRACT and Section 7. CONCLUSIONS).
The combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande does not expressly teach a first set of constrained variables corresponding to task-resource assignment.
However, Kadioglu teaches a first set of constrained variables corresponding to task-resource assignment ([0050] – “requests 112 correspond to requests for performance of one or more tasks by one or more resources 114. Examples of requests 112 include requests for the delivery of services, production of products, execution of operations, and/or performance of other tasks.”; [0070]-[0071] – “data model 120 includes one or more data model elements such as request elements 122-124 and counting elements 142-144. Each request element (such as request element 122 or request element 124) is associated with a request domain (such as request domain 132 or request domain 134). A request domain, corresponding to a particular request, includes a set of possible resources 114 that may be assigned to the particular request. A request domain may include all or a subset of resources 114. In an example, each request domain includes a candidate set of resources, filtered from resources 114, that may be assigned to a particular request based on resource capabilities 116 required and/or preferred for completion of the particular request.”).
Kadioglu is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor of generating a schedule for a plurality of constrained tasks to be performed by a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande such that the constrained variables include a set of constrained variables corresponding to task resource assignment. Doing so would ensure tasks are only assigned to well-suited resources which have the required and/or preferred capabilities for completing the task (Kadioglu: [0028], [0071] and [0096]).
Claim 12 recites substantially the same limitations as those recited in claim 5, applied to the system of claim 8. Accordingly, claim 12 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claim 8, and further in view of Kadioglu for the same reasons presented with respect to claim 5.
Claim 18 recites substantially the same limitations as those recited in claim 5, applied to the method of claim 15. Accordingly, claim 18 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claim 15, and further in view of Kadioglu for the same reasons presented with respect to claim 5.
Claims 14, 20, and 22 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li, Colena, and MOHANA NARAYANMURTHY as applied to claims 1, 8, and 15 above, and further in view of Mayank et al. (NPL Document: “Non-preemptive multiprocessor scheduling for periodic real-time tasks”), hereinafter Mayank.
Regarding claim 14, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the system of claim 8. Colena further teaches wherein the search directive indicates a […] approach to scheduling the set of computing tasks ([0033] – “A CP search directive guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a CP data model. The CP search directive prioritizes the assignment of certain preferred values over other values for one or more elements.”; [0253] – “A search directive generator 116 determines, specifies, and/or obtains instructions and/or operations for traversing each of the set of task elements specified at Operation 302. The instructions include selecting a particular task element, representing a particular maintenance task, as an initial "target task element." In subsequent iterations, traversing the set of task elements, another task element may be selected as the "target task element."; [0272] – “the CP solver may be guided by a CP search directive. The CP search directive may determine a sequence in which time windows are attempted for assignment to one or more task elements.”).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
The combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande fails to expressly teach using a First-Fit Decreasing Utilization (FFDU) approach to scheduling the set of tasks.
However, Mayank teaches a First-Fit Decreasing Utilization (FFDU) approach to scheduling the set of tasks (Page 2, 1. INTRODUCTION – “In this work, we propose a methodology for scheduling of a set of non-preemptive tasks in multiprocessor environment. We try to minimize the number of processor for scheduling the tasks. We use partitioning based approach where the tasks are allocated to processors in the beginning. Once a task is assigned to a processor, it cannot migrate to other processors. For partitioning, we use strategies like best-fit (BF) and first-fit (FF) that are used for solving bin-packing problem. The ordering of tasks is also important for allocation of it. We explore different orderings of tasks based on utilization, periods, etc. in combination with partitioning strategies. […] We observe that FF and BF heuristics with increasing period and decreasing utilization provide good performance with respect to other multiprocessor approaches.”; Page 6, 5. CONCLUSION – “We observed FFDU and BFDU gives better performance on a given number of processor.”).
Mayank is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks on a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the search directive indicating an approach for traversing the task set to be scheduled as taught by Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande to indicate a first-fit decreasing utilization approach as taught by Mayank. Doing so uses a known heuristic for solving bin-packing problems, i.e., the first-fit heuristic, to ensure processor utilization is not exceeded, and uses the task utilization to order the tasks being assigned (Mayank: Page 3). Further, using FFDU provided better performance and a higher success ratio on a given number of processors than other approaches (Mayank: Pages 5-6).
Claim 20 recites substantially the same limitations as those recited in claim 14, applied to the method of claim 15. Accordingly, claim 20 is rejected as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claim 15, and further in view of Mayank for the same reasons presented with respect to claim 14.
Regarding claim 22, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches The method of claim 15. Colena further teaches wherein the CP solver is configured to prioritize [scheduling of tasks] ([0033] – “A CP search directive guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a CP data model. The CP search directive prioritizes the assignment of certain preferred values over other values for one or more elements.”; [0272] – “the CP solver may be guided by a CP search directive.” Claim 14 – “generating a constraint programming search directive, comprising: specifying one or more operations for prioritizing
assignment of the first task element with a time window”).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
The combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande fails to expressly teach the CP solver prioritizing periodic computing tasks in order of highest to lowest utilization.
However, Mayank teaches prioritizing periodic computing tasks in order of highest to lowest utilization (Page 3, Section 3. PROPOSED APPROACHES FOR MULTIPROCESSOR SCHEDULING – “B. Ordering of tasks In partitioning based multiprocessor scheduling, at the beginning each task is assigned to one of the processors. For such assignment, we use FF and BF strategies. The ordering of selection of tasks by BF and FF can be made using the different parameters of the tasks such as execution time, period, utilization, etc […] We assigned the priority to the task according to increasing or decreasing order of period or utilization of tasks”).
Mayank is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks on a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the CP solver prioritizing scheduling of tasks as taught by Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande to prioritize the periodic computing tasks for scheduling in order of decreasing utilization as taught by Mayank. Using a decreasing utilization approach to order periodic tasks to be scheduled, such as First-Fit Decreasing-Utilization, provided better performance and a higher success ratio on a given number of processors than other approaches (Mayank: Abstract Pages 5-6).
Claim 23 is rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande as applied to claim 15 above, and further in view of Digalwar et al. (NPL Document: “Design and Development of a Real Time Scheduling Algorithm for Mixed Task Set on Multi-core”), hereinafter Digalwar.
Regarding claim 23, the combination of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande teaches the method of claim 15, but fails the teach the method further comprising: filtering out one or more non-periodic tasks from the set of computing tasks to be scheduled.
However, Digalwar teaches filtering out one or more non-periodic tasks from the set of computing tasks to be scheduled (Abstract – “Periodic tasks are scheduled using Partitioned Earliest Deadline First (P-EDF) technique. Aperiodic tasks are assigned globally to different processor cores and scheduled using Total Bandwidth Server (TBS) on each core. In the proposed algorithm, the excess processing capacity of the cores left unused by the periodic tasks can be utilized by assigning aperiodic task to each core.”; Page 3 - F. Algorithm Description – “Aperiodic job is inserted in global aperiodic queue on its arrival and then it is assigned to a processor core. Separate queue is maintained on each processor core for holding periodic as well as aperiodic jobs at any time instance.” Fig. 1.2 – the example code shows periodic jobs are added to queue “JQueue” and aperiodic jobs are added to queue “AQ”; Fig. 1.4 – there is separate scheduling logic for tasks based on whether they are periodic (“if (Jobhead [p_id] is periodic)then”) vs. aperiodic (“if (Jobhead [p_id] is aperiodic)then”); FIG 3 – task generator generates tasks into a periodic queue and an aperiodic queue. Separating the aperiodic tasks from periodic tasks is “filtering out” the aperiodic tasks, as the periodic tasks are first scheduled using the P-EDF approach, and then aperiodic tasks are scheduled using a different algorithm in the excess capacity of the cores left unused by the scheduled periodic tasks.)
Digalwar is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of tasks to a shared set of computing resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li, Colena, MOHANA NARAYANMURTHY, and Deshpande such that the aperiodic tasks are filtered out of the set of computing tasks to be scheduled as described by Digalwar. Separating aperiodic tasks from periodic tasks for scheduling, such that the aperiodic tasks are able to be scheduled into the excess processing capacity unused by the periodic tasks after the periodic tasks have been scheduled, would improve the overall utilization of each core and can improve response time of the aperiodic tasks (Digalwar: Abstract).
Response to Arguments
Applicant’s arguments with respect to the rejection of Claim 1 under 35 U.S.C. 103 as being unpatentable over Wang in view of Li, Colena, and MOHANA NARYANMURTHY have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Specifically, the combination of Colena in view of new reference Deshpande (U.S. Patent No. 7,451,447) is relied upon to teach the argued limitations.
Specific details regarding the combination of references to teach the limitations as recited in claim 1 are provided in the rejection of claim 1 in the section titled Claim Rejections - 35 USC § 103 above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Miller et al. (U.S. Pub. No. 2013/0036421) teaches a method for scheduling schedulable entities onto an execution timeline for a processing entity where schedulable entities having the shortest periods (i.e., highest rate) are scheduled first, and harmonic rate monotonic scheduling is implemented (see Abstract, [0016]).
Wang et al. (U.S. Pub. No. 2024/0004707) teaches a method of energy-efficient scheduling of periodic tasks on a group of processing devices includes a constraint that for a periodic task, its execution time must be less than or equal to its period (see [0035], [0073], and [0101]).
Binns (U.S. Pub. No. 2002/0120663) teaches a multitasking system executing periodic and aperiodic tasks, where periodic tasks may be harmonic tasks where the period of each task evenly divides the period of the other tasks in the set of tasks (see Abstract, [0050]). Tasks are characterized as periodic or aperiodic, rate monotonic scheduling may be used for strictly periodic tasks sets, and aperiodic tasks may be scheduled according to a slack stealing algorithm around the periodic tasks (see [0009]-[0011], [0055]-[0057]).
Doan et al. (NPL Document: “Adaptive Local Assignment Algorithm for Scheduling Soft-Aperiodic Tasks on Multiprocessors”) teaches scheduling a mixture of periodic and aperiodic tasks, and suggests using dedicated servers for aperiodic tasks at runtime to improve responsiveness of aperiodic tasks while maintaining relatively low runtime overhead (see Abstract).
Eigenbrand et al. (NPL Document: “Scheduling Periodic Tasks in a Hard Real-Time Environment”) teaches a pair of tasks have harmonic periods if one period is divisible by the other, and tasks with harmonic periods are easier to schedule on the same machine (see pages 300-302).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JENNIFER MARIE GUTMAN whose telephone number is (703)756-1572. The examiner can normally be reached M-F: 8:00 am - 4:00 pm.
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, Kevin Young can be reached at 571-270-3180. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
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.
/JENNIFER MARIE GUTMAN/Examiner, Art Unit 2194 /KEVIN L YOUNG/Supervisory Patent Examiner, Art Unit 2194
Prosecution Insights