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 .
Claims 1-9, 12-13, 15-23 are pending, claims 10-11 and 14 are cancelled.
Response to Arguments
Regarding 35 U.S.C. 112:
Applicant’s amendment to claim 1 raises a new issue under 35 U.S.C. 112(b).
Regarding: Prior Art Rejections:
Applicant’s arguments and amendments regarding the rejections of claims 1-9, 12-13, and 15-22 have been fully considered and are found to be not persuasive. After further consideration, the rejections of claims 1-9, 12-13, and 15-23 under 35 U.S.C. 103 are maintained.
Applicant’s Remarks recite:
“Kipp discloses that there are multiple queues, each with their own one lock. That is different than subject matter of one queue having multiple locks. So, Kipp fails to disclose the amended subject matter of, "wherein the associating of the first worker thread with the second device identifier comprises locking the second bucket while refraining from locking the first bucket, wherein the first bucket differs from the second bucket, wherein a queue 12
comprises the group of buckets, and wherein the queue is separate from the respective first-in- first-out queues."
Jain discloses an overarching task queue containing groups/buckets of smaller task queues (i.e., queues within a queue). Kipp discloses multiple methods of synchronizing access to shared resources. One method involves locking each task queue individually ([0067] Since a lock around each task queue increases serial time for executing programs, the hierarchy allows distribution of locks, which results in less contentious hierarchy of locks. This decreases the amount of time for the lock, and allows synchronization between task groups therefor preventing stalling, which may effectively serialize the program). The combination results in each queue within the queues of Jain to be assigned a lock. The motivation for such combination is to prevent stalling that may occur from highly demanded unsynchronized queues.
Examiner suggests Applicant to direct claims away from the Job Request Group concept ([0021], [0034], [0039]) of Jain in order to overcome the Jain reference.
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.
Claims 1-7 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, the introduced limitation: “wherein a queue comprises the group of buckets, and wherein the queue is separate from the respective first-in-first-out queues”. It is unclear how the queue can be separate from the respective first-in-first-out queues when it is previously stated that the “queue comprises the group of buckets” and the “respective buckets comprise respective first-in-first-out queues”. Examiner interprets the limitation such that the queue is a distinct entity from the first-in-first-out queues. The first-in-first-out queues cannot be the queue itself while the queue may contain the first-in-first-out queues within.
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.
Claims 1-4, 6-7, and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Jain et Al. US 20200042349 A1 in view of Klein et Al. US 20040064430 A1 in view of Thabet et Al. US 20140380327 A1, Kipp 20150135183 A1, and Miniskar et al. US 20220129275 A1.
Jain, Klein, Thabet, Kipp, and Miniskar are cited a prior office action.
Regarding claim 1, Jain teaches the invention substantially as claimed including:
A system, comprising:
at least one processor ([0088] The system 700 comprises at least one processor); and
at least one memory that stores executable instructions that, when executed by the at least one processor, facilitate performance of operations ([0088] at least one memory, the memory serving to store program instructions corresponding to the operations of the system), comprising:
storing identifiers of devices of a computing cluster (Fig 1A The computing cluster; [0029] The logical depiction of FIG.1A illustrates a computing cluster (e.g., cluster 102} that comprises a plurality of computing nodes (e.g., node 104.sub.1, ... , node 104.sub.N) that are configured to operate in accordance with a virtualization regime.; [0042] As earlier indicated, specialized job request data structures are used to improve the way a computer stores and retrieves data in memory (e.g., for ongoing queue management). Specifically, a queue might be implemented by a collection of first-in, first out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)), wherein the hash table comprises an index that identifies respective buckets of a group of buckets, wherein the respective buckets comprise respective first-in-first-out queues (Fig 1B index of job request groups each with a subqueue of jobs), and wherein worker threads of the computing cluster ([0107] clusters can communicate between one module to another...; [0108] A module as used herein can be implemented using ... hard-wired circuitry embodied as a data processor. A data processor can be organized to execute a processing entity that is configured to execute as a single process or configured to execute using multiple concurrent processes to perform work. A processing entity can carry out computations and/or processing steps using ... one or more threads ...) access the hash table to identify respective devices from which to fetch work (Fig 1A Controller and Distributed Computing Resources; [0029] As can be observed, the virtualized entities 112 access a set of distributed computing resources 116 (e.g., distributed storage resources 122, distributed network resources 124, distributed CPU resources 126, etc.) at cluster 102 through a control layer 114; [0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "nodelD" field); [0049] Queue management logic ... is codified to aid in managing the contents of the multi-level queues (step 204). The content of the multi-level queues can comprise job request and/or job request groups and/or other information pertaining to jobs and/or job requests processed in the virtualization environment. The queue management logic ... might be implemented using ... software data structures (e.g., hash tables) ... the queue management logic ... might include logic ... to facilitate identification a particular job type that corresponds to any entry in any queue); Examiner notes: Queue management logic is implementable with hash tables. Pulling a job from the job queue invokes the queue management logic for managing the contents of multi-level queues, thereby accessing the hash table)
maintaining an insertion index that identifies a first bucket of the group of buckets into which a first device identifier is to be inserted ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has ... a "tail" position ... The tail of a queue
(e.g., tail 174.sub.1 and tail 174.sub.2) is the position that follows the last job request
and/or last populated job request group (if any) in the queue; [0056] if no job request group is found for VM2, job request group G.sub.VM2 is created and placed at the tail of the high priority job queue);
maintaining a fetch index that identifies a second bucket of the group of buckets from which a second device identifier is to be removed ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue; [0022] When computing resources are available to process a job, the job request at the head of the high priority job queue is selected for processing), and wherein incrementing the fetch index changes a bucket of the hash table identified by the fetch index (Fig 6Q; Examiner notes: after processing JVM2 the queue head pointer identifying the next job group increments from GVM2 to GVM3); and
in response to determining to identify one of the identifiers of devices (Fig 2: Determining Step 210; [0050] If there is no then-current processing capacity to start another job (see "No" path of decision 210) ...; [0051] If there is processing capacity available (see "Yes" path of decision 210) after entering an incoming job request into one of the multi-level queues or as indicated by a job processing completion event (see "Job Processing Completed" path of decision 208), then a job request is selected for processing from the multi-level queues (step 240); [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)) to a first worker thread of the worker threads, wherein the first worker thread executes on a second device of the devices ( [0029] the virtualized entities 112 access a set of distributed computing resources 116 (e.g., distributed storage resources 122, distributed network resources 124, distributed CPU resources 126, etc.) at cluster 102 through a control layer 114; [0107] clusters can communicate between one module to another...; [0108] A module as used herein can be implemented using ... hard-wired circuitry embodied as a data processor. A data processor can be organized to execute a processing entity that is configured to execute as a single process or configured to execute using multiple concurrent processes to perform work. A processing entity can carry out computations and/or processing steps using ... one or more threads ...), accessing the second device identifier at the fetch index ([0049] Queue management logic ... is codified to aid in managing the contents of the multi-level queues (step 204) ... The queue management logic ... might be implemented using ... software data structures (e.g., ... hash tables ... ); [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue; [0022] When computing resources are available to process a job, the job request at the head of the high priority job queue is selected for processing; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)), and associating the first worker thread with the second device identifier (Fig 1B: Request Attributes 186; [0065] As shown, the multi-level queue management technique 4B00 accesses the then-current job status log 138 to identify a virtual machine associated with the most-recently started job (step 454). In this embodiment, the most-recently started job is the job that was started as a result of operation of step 408 or as a result of operation of step 416. In some alternative embodiments, accesses to the job status log 138 might be performed at some scheduled cadence to identify the most-recently started job (e.g., the shown most-recently started job 434); [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field); [0107] clusters can communicate between one module to another...; [0108] A module as used herein can be implemented using ... hard-wired circuitry embodied as a data processor. A data processor can be organized to execute a processing entity that is configured to execute as a single process or configured to execute using multiple concurrent processes to perform work. A processing entity can carry out computations and/or processing steps using ... one or more threads ...)), wherein the first bucket differs from the second bucket (Fig 1B GVM2 GVM 3);
wherein a queue comprises the group of buckets, and wherein the queue is separate from the respective first-in-first-out queues (Fig 1B High Priority Job Queue 152 is distinct from Job Request Group GVM2 although 152 contains GVM2);
wherein the first worker thread performs work originated from a first device of the devices that corresponds to the second device identifier, and wherein the work comprises a task to be performed based on the associating ([0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102. Various sets of in-process jobs can be managed by job executor 136. In some cases, each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs; [0065] identify a virtual machine associated with the most-recently started job (step 454). In this embodiment, the most-recently started job is the job that was started as a result of operation of step 408 or as a result of operation of step 416).
Jain does not explicitly teach:
storing identifiers of devices of a computing cluster in a hash table;
atomically accessing data and incrementing a value,
wherein the associating of the first worker thread with the second device identifier comprises locking the second bucket while refraining from locking the first bucket,
However, analogous art by Klein teaches storing identifiers of devices of a computing cluster in a hash table (Fig 6 Element 601; [0031] FIG. 6 is an exemplary block diagram of a container 601 that contains queue metadata objects 602 for multiple queues (i.e., QUEUE 1, QUEUE 2, ... , QUEUE N) according to an embodiment of the invention. In one embodiment, container 601 is a hash table and queue metadata objects 602 are hash buckets. A hash bucket 602 contains the pointers for a queue, and uniquely defines a link to a queue via a data element known as a queue identifier (QUEUE ID). For instance, QUEUE_ID.sub.lis a link to the head node H.sub.1 of QUEUE 1. Similarly, QUEUE_ID.sub.2 is a link to the head node H.sub.2 of QUEUE 2, and so forth. In effect, the queue identifier acts as the hash key for hash table 601).
Jain differs from the claimed invention by the specific data structure used to host the job/task queues. Jain generically mentions queue management logic as being implementable by "any combination of hardware and software, and/or any combination of hardware data structures (e.g., hardware FIFOs) and/or software data structures (e.g., linked lists, pointers, hash tables, etc.)" while the claimed invention uses a hash table to host job/task queues. The multiple queue data structure in Jain does not explicitly use a hash table to reference to the queues. Klein teaches a hash table of queues. Because Klein teaches a hash table containing queues, hash tables and queues are known data structures in the art.
Combining the hash table of queues data structure of Klein with the multiple job queue system of Jain results in a job scheduling system that uses a hash table to reference job queues that store devices that request processing from a distributed resource. The results of the combination would have been predictable because utilization of hashing in object storage is common practice in the art of storing data. It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have simply substituted the multiple queue structure of Jain with the hash table of queues data structure of Klein resulting in a job queuing system that primarily utilizes a hash table to reference job queues.
Jain and Klein do not explicitly teach atomically accessing data and incrementing a value.
However, Thabet teaches: atomically accessing data and incrementing a value ([0034] a "post-increment" field 202; read-access to this field returns the value of the register and increments it automatically and in an atomic manner, that is to say no other operation can take place on this counter between the reading of the "value" field and its incrementation by access to the "post-increment" field)
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the synchronization method of atomic operations from Thabet with the job queue system of Jain and Klein resulting in a multiple queue job queuing system as in Jain that maintains synchronization with all computing systems by using atomic fetch&increment operations on head/tail and start/end pointers as in Thabet to avoid undesirable contention and race conditions on job request fetching. A person having ordinary skill in the art prior to the effective filing date of the claimed invention would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of improving the managing of shared access to a resource by multiple tasks as in Thabet (Thabet [0003] Nonetheless, memory sharing and the necessary coordination of the execution of the tasks require means for mutual synchronization of the tasks. In order to ensure effective parallelism in the execution of several tasks on one and the same platform, it is necessary to have efficient synchronization means, synchronization generally constituting the main bottleneck of shared-memory systems).
Jain, Klein, and Thabet do not explicitly teach locking the second bucket while refraining from locking the first bucket.
However, Kipp teaches wherein the associating of the first worker thread with the second device identifier comprises locking the second bucket while refraining from locking the first bucket ([0023] The task groups are a collection of tasks from the program and are grouped into task groups. The task group queues allow for ordered access to task groups that have been submitted for execution. The task scheduler 108 manages worker threads in the worker thread pool 104 that are scheduled to execute tasks. The task scheduler 108 is responsible for the state of the worker threads and the logic associated with assignment of the worker threads to task queues, task groups, and tasks; [0062] Because adding and removing from a task group queue happen on multiple worker threads, serializing access to the task group queue is necessary to maintain order; [0066] a low level queue that only allows one worker thread at a time may maintain a very simple locking mechanism; [0067] Only one hardware thread can operate on a specific piece of memory at a time. Processors generally do not have a sharing mechanism that orders access fairly. By having each queue maintain a separate lock, the likelihood that two worker threads will try to operate on the same lock is reduced. In this way they are less likely to stall each other and the program will operate faster; Examiner notes: each queue (bucket) having its own lock allows for modularity in the task allocation system. When a thread requires access to a queue it will only lock the queue it is retrieving a task from, refraining from locking all other queues).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the queue locking method of Kipp with the job queue system of Jain, Klein, and Thabet resulting in a hash table of queues job queuing system that maintains synchronization and only locks the required task queue for exclusive thread access. The benefit of maintaining locks on task queues is that the resource holding the lock is able to confidently perform operations on the task queue without external interference changing the queue's contents (Kipp [0006] mutual exclusion (Mutexes), critical sections, and locks. These mechanisms are typically used to guard a region of a program from multiple simultaneous access from multiple threads).
While Jain teaches head and tail pointers changing between the front and rear job groups within a queue, Jain, Klein, Thabet, and Kipp do not explicitly teach wherein incrementing the insertion index past a largest index value of the index comprises setting the insertion index to a smallest index value of the index, wherein incrementing the fetch index past the largest index value of the index comprises setting the fetch index to the smallest index value of the index.
However, Miniskar teaches wherein incrementing the insertion index past a largest index value of the index comprises setting the insertion index to a smallest index value of the index, wherein incrementing the fetch index past the largest index value of the index comprises setting the fetch index to the smallest index value of the index ([0046] A front pointer can be used to designate a next queue element to be dequeued, and a rear pointer can be used to indicate a next queue element to receive an entry; [0077] Both pointers 121, 129 can wrap around from index 8 to index 0 at the appropriate time, as indicated by arrow 113).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Miniskar’s task queue pointer index wraparound with the pointer hashtable-based task distribution system of Jain, Klein, Thabet, and Kipp. A person of ordinary skill in the art would have been motivated to make this combination to provide Jain, Klein, Thabet, and Kipp’s system with the advantage of implementing a circular data structure using linear memory space using wrapping pointers (see Miniskar [00057] a “circular queue” is a queue having a finite linear sequence of successive storage locations, such that a first of the storage locations logically succeeds a last of the storage location. Thus, the finite linear sequence of storage locations has a logical appearance of an endless circular sequence of storage locations. For queues having power-of-two length (e.g. 2, 4, 8, 16, . . . ), circularity can follow naturally from a binary bit representation of an index—e.g. for a queue of length 4 with a two-bit index representation, incremented index values naturally wrap around (0, 1, 2, 3, 0, 1, 2, . . . )).
Regarding claim 2, Jain, Klein, Thabet, and Kipp teach the system of claim 1.
Jain further teaches wherein the operations further comprise: in response to determining to make a third device identifier, of the identifiers of devices, available to the worker threads ([0077] FIG. 6C, a job requestJ.sub.VM2 is received from VM2), inserting the third device identifier into the hash table at the insertion index, and incrementing a value of the insertion index ([0077] A job request group G.sub.VM2 is created for VM2 and positioned at the tail of high priority job queue 152. As shown, the tail of high priority job queue 152 is ahead of any empty job request groups. The job request J.sub.VM2 is positioned at the end of the job request group G.sub.VM2, and later selected for processing at job executor 136 as shown in. ([0077] A job request group G.sub.VM2 is created for VM2 and positioned at the tail of high priority job queue 152. As shown, the tail of high priority job queue 152 is ahead of any empty job request groups. The job request J.sub.VM2 is positioned at the end of the job request group G.sub.VM2, and later selected for processing at job executor 136 as shown in FIG. 6D; [0040] The tail of a queue (e.g., tail 174.sub.1 and tail 174.sub.2) is the position that follows the last job request and/or last populated job request group (if any) in the queue), Examiner notes: if the tail of a queue follows the last job request/job request group and a new job request/ job request group is added, then tail is incremented to follow the most recently added element)
Regarding claim 3, Jain, Klein, Thabet, and Kipp teach the system of claim 1.
Thabet further teaches wherein atomically accessing the second device identifier at the fetch index of the hash table and wherein incrementing the value of the fetch index comprises: performing a fetch-and-add processor instruction at the fetch index of the hash table ([0034] a "post-increment" field 202; read-access to this field returns the value of the register and increments it automatically and in an atomic manner, that is to say no other operation can take place on this counter between the reading of the "value" field and its incrementation by access to the "post-increment" field).
Regarding claim 4, Jain, Klein, Thabet, and Kipp teach the system of claim 1.
Jain further teaches wherein incrementing the value of the fetch index comprises: updating the value of the fetch index from identifying the second bucket to identifying a third bucket of the hash table (Fig 6Q-> Fig 6R: Head of queue becomes job request group Gvm3 from Gvm2; [0061] the job request at the head of the high priority job queue is selected for processing (step 408). As illustrated in job request selection scenario 430.sub.1, a job request at the head of high priority job queue 152 is selected for processing by job executor 136. Following selection of the job request, the contents of the job queues are adjusted (step 418)).
Regarding claim 6, Jain, Klein, Thabet, and Kipp teach the system of claim 1.
Jain further teaches wherein the operations further comprise: in response to determining that the first worker thread has completed the work for the first device ([0051] a job processing completion event), associating the first worker thread with another device identifier of the identifiers of devices in the hash table other than the first device identifier ([0051] If there is processing capacity available (see "Yes" path of decision 210) ... as indicated by a job processing completion event (see "Job Processing Completed" path of decision 208), then a job request is selected for processing from the multi-level queues (step 240). For example, a job request at the head of the high priority job queue or the low priority job queue might be selected for processing; Fig 6k -> Fig 6L: Job from VM2 completes. Job from VM1 fetched and processed in computing cluster).
Regarding claim 7, Jain, Klein, Thabet, and Kipp teach the system of claim 1.
Jain further teaches wherein the operations further comprise: after associating the first worker thread with the second device identifier that is stored at the fetch index of the hash table, removing the second device identifier from the hash table (Fig 6A -> Fig 6B: Jvm1 selected by Job Executor for processing and removed from High Priority Queue; [0051] a job request at the head of the high priority job queue or the low priority job queue might be selected for processing. The multi- level queues are reorganized based at least in part on the then-current job status and/or the queue management logic (step 250)).
Regarding claim 21, Jain, Klein, Thabet, Kipp, and Miniskar teach the system of claim 1.
Jain further teaches wherein the second bucket stores the second device identifier and a third device identifier, and wherein the associating of the first worker thread with the second device identifier comprises determining that the second device identifier was added to the second bucket prior to the third device identifier being added to the second bucket ([0042] As earlier indicated, specialized job request data structures are used to improve the way a computer stores and retrieves data in memory(e.g., for ongoing queue management). Specifically, a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues).
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable over Jain, Klein, Thabet, Kipp, and Miniskar as applied to claim 1 above, and in further view of Maniyar et Al. REVIEW ON ROUND ROBIN ALGORITHM FOR TASK SCHEDULING IN CLOUD COMPUTING.
Maniyar is cited in a previous office action.
Regarding claim 5, Jain, Klein, Thabet, Kipp, and Miniskar teach the system of claim 1.
Jain, Klein, Thabet, Kipp, and Miniskar do not explicitly teach wherein the fetch index is monotonically updated.
However, Maniyar teaches wherein the fetch index is monotonically updated ([4. Round Robin Algorithm] Round- Robin is a simple scheduling algorithm, based on time membership between jobs in equivalent slice/quantum and in circular queue without precedence so it is simple and easy to implement, ... So it focuses on equality between jobs; [4.2] 3. The scheduler always selects the process control block at head of the ready queue. 4.When a running process finishes its portion, it is motivated to end of ready queue). Examiner notes: [0081] of the instant spec reads "Monotonically updating the fetch index can comprise performing modulo arithmetic or otherwise rolling the fetch index back to the start of a hash table index when it is incremented past the end of the hash table index", as such round robin incorporates monotonically updating.)
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the Round Robin scheduling method of Maniyar with the job queue system of Jain, Klein, Thabet, and Kipp resulting in a multiple queue job queuing system that utilizes a hash table of queue pointers, maintains system synchronization, and fairly pulls tasks from each queue in a circular manner. (Maniyar 3.2 Round Robin (RR) algorithm focuses on the equality. Each job in a queue has the same implementation time and it will be executed in turn).
Claims 8-9, 12-13, 15-20, 22-23 are rejected under 35 U.S.C. 103 as being unpatentable over Jain et Al. US 20200042349 A1 in view of Klein et Al. US 20040064430 A1, Kipp US 20150135183 A1, and Miniskar et al. US 20220129275 A1.
Jain, Klein, and Kipp were previously cited to in the prior office action.
Regarding claim 8, Jain teaches the invention substantially as claimed including:
A method, comprising:
storing, by a system comprising at least one processor, identifiers of objects (Fig 1A The computing cluster; [0029] The logical depiction of FIG. 1A illustrates a computing cluster (e.g., cluster that comprises a plurality of computing nodes (e.g., node 104.sub.1, ... , node 104.sub.N) that are configured to operate in accordance with a virtualization regime.; [0042] As earlier indicated, specialized job request data structures are used to improve the way a computer stores and retrieves data in memory(e.g., for ongoing queue management). Specifically, a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)), wherein the hash table comprises an index that identifies respective buckets of a group of buckets (Fig 1B index of job request groups);
maintaining, by the system, an insertion index that identifies a first bucket of the group of buckets into which a first object identifier of the identifiers of objects is to be inserted (([0042] a queue might be implemented by a collection of first-in, first-out (FlFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has ... a "tail" position ... The tail of a queue (e.g., tail 174.sub.1 and tail 174.sub.2) is the position that follows the last job request and/or last populated job request group (if any) in the queue; [0056] if no job request group is found for VM2, job request group G.sub.VM2 is created and placed at the tail of the high priority job queue);
maintaining, by the system, a fetch index that identifies a second bucket of the group of buckets from which a second object identifier of the identifiers of objects is to be removed ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue; [0022] When computing resources are available to process a job, the job request at the head of the high priority job queue is selected for processing), and wherein incrementing the fetch index changes a bucket of the hash table identified by the fetch index (Fig 6Q; Examiner notes: after processing JVM2 the queue head pointer identifying the next job group increments from GVM2 to GVM3); and
in response to determining to communicate (Fig 2: Determining Step 210; [0050] If there is no then- current processing capacity to start another job (see "No" path of decision 210) ...; [0051] If there is processing capacity available (see "Yes" path of decision 210) after entering an incoming job request into one of the multi-level queues or as indicated by a job processing completion event (see "Job Processing Completed" path of decision 208), then a job request is selected for processing from the multi-level queues (step 240); [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" fieId)), to a requestor ( [0029] As can be observed, the virtualized entities 112 access a set of distributed computing resources 116 (e.g., distributed storage resources 122, distributed network resources 124, distributed CPU resources 126, etc.) at cluster 102 through a control layer 114; [0033] A job executor136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102. Various sets of in-process jobs can be managed by job executor 136. In some cases, each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs), one of the identifiers of objects ([0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)), Examiner notes: A job executor identifies job requests, which contain device identifiers, to distributed computing resources 116 for processing, wherein the requestor executes on a second device of the group of devices ([0029] distributed CPU resources 126), communicating, by the system to the requestor, the second object identifier that is stored at the fetch index (Fig 1B: Request Attributes 186 and In-Process Jobs 188; [0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests, (e.g., selected job request 164} for processing at cluster 102 ... each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vm/D" field}, a node identifier (e.g., stored in a "node/D" field)); Examiner notes: Job executor facilitates communication between job requesters and cluster processors.) and incrementing a value of the fetch index (Fig 6L Arrows; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue. [0051] a job request at the head of the high priority job queue or the low priority job queue might be selected for processing). Examiner notes: pulling a job request from the head of the queue means the queue head pointer increments to the next job),
wherein the group of buckets is part of a queue (Fig 1B Job Request Groups GVM2 GVM3 and GVM4 part of High Priority Job Queue 152);
wherein the requestor performs work originated from a first device of a group of devices that corresponds to the second object identifier, based on the communicating ([0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102. Various sets of in-process jobs can be managed by job executor 136. In some cases, each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs; [0065] identify a virtual machine associated with the most-recently started job (step 454). In this embodiment, the most-recently started job is the job that was started as a result of operation of step 408 or as a result of operation of step 416), and wherein the first bucket differs from the second bucket ((Fig 1B different job request groups GVM2 GVM 3 …).
Jain does not explicitly teach storing object identifiers in a hash table.
However, Klein teaches in detail: storing, by a system comprising a processor, identifiers of objects in a hash table (Fig 6 Element 601; [0031] FIG. 6 is an exemplary block diagram of a container 601 that contains queue metadata objects 602 for multiple queues (i.e., QUEUE 1, QUEUE 2, ... , QUEUE N) according to an embodiment of the invention. In one embodiment, container 601 is a hash table and queue metadata objects 602 are hash buckets. A hash bucket 602 contains the pointers for a queue, and uniquely defines a link to a queue via a data element known as a queue identifier (QUEUE ID). For instance, QUEUE_ID.sub.l is a link to the head node H.sub.1 of QUEUE 1. Similarly, QUEUE_ID.sub.2 is a link to the head node H.sub.2 of QUEUE 2, and so forth. In effect, the queue identifier acts as the hash key for hash table 601).
Jain differs from the claimed invention by the specific data structure used to host the job/task queues. Jain generically mentions queue management logic as being implementable by "any combination of hardware and software, and/or any combination of hardware data structures (e.g., hardware FIFOs) and/or software data structures (e.g., linked lists, pointers, hash tables, etc.)" while the claimed invention uses a hash table to host job/task queues. The multiple queue data structure in Jain does not explicitly use a hash table to reference to the queues. The prior art, Klein, teaches a hash table of queues. Because Klein teaches a hash table containing queues, hash tables and queues are known data structures in the art.
Combining the hash table of queues data structure of Klein with the multiple job queue
system of Jain results in a job scheduling system that uses a hash table to reference job queues that store devices that request processing from a distributed resource. The results of the
combination would have been predictable because utilization of hashing in object storage is common practice in computing. It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have simply substituted the multiple queue structure of Jain with the hash table of queues data structure of Klein resulting in a job queuing system that primarily utilizes a hash table to reference job queues.
Jain and Klein do not explicitly teach refraining from locking the first bucket concurrently with communicating, to the requestor, the second object identifier that is stored at the second bucket, while locking the second bucket concurrently with communicating, to the requestor, the second object identifier that is stored at the second bucket.
However, Kipp teaches refraining from locking the first bucket concurrently with communicating, to the requestor, the second object identifier that is stored at the second bucket, while locking the second bucket concurrently with communicating, to the requestor, the second object identifier that is stored at the second bucket, ([0023] The task groups are a collection of tasks from the program and are grouped into task groups. The task group queues allow for ordered access to task groups that have been submitted for execution. The task scheduler 108 manages worker threads in the worker thread pool 104 that are scheduled to execute tasks. The task scheduler 108 is responsible for the state of the worker threads and the logic associated with assignment of the worker threads to task queues, task groups, and tasks; [0062] Because adding and removing from a task group queue happen on multiple worker threads, serializing access to the task group queue is necessary to maintain order; [0066] a low level queue that only allows one worker thread at a time may maintain a very simple locking mechanism; [0067] Only one hardware thread can operate on a specific piece of memory at a time. Processors generally do not have a sharing mechanism that orders access fairly. By having each queue maintain a separate lock, the likelihood that two worker threads will try to operate on the same lock is reduced. In this way they are less likely to stall each other and the program will operate faster; Examiner notes: each queue (bucket) having its own lock allows for modularity in the task allocation system. When a thread requires access to a queue it will only lock the queue it is retrieving a task from, refraining from locking all other queues).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the queue locking method of Kipp with the job queue system of Jain and Klein resulting in a hash table of queues job queuing system that maintains synchronization and only locks the required task queue for exclusive thread access. The benefit of maintaining locks on task queues is that the resource holding the lock is able to confidently perform operations on the task queue without external interference changing the queue's contents (Kipp [0006] mutual exclusion (Mutexes), critical sections, and locks. These mechanisms are typically used to guard a region of a program from multiple simultaneous access from multiple threads).
Jain, Klein, and Kipp do not explicitly teach wherein incrementing the insertion index to be larger than a largest index value of the index comprises setting the insertion index to a smallest index value of the index, wherein incrementing the fetch index to be larger than the largest index value of the index comprises setting the fetch index to the smallest index value of the index.
However, Miniskar teaches wherein incrementing the insertion index to be larger than a largest index value of the index comprises setting the insertion index to a smallest index value of the index, wherein incrementing the fetch index to be larger than the largest index value of the index comprises setting the fetch index to the smallest index value of the index ([0046] A front pointer can be used to designate a next queue element to be dequeued, and a rear pointer can be used to indicate a next queue element to receive an entry; [0077] Both pointers 121, 129 can wrap around from index 8 to index 0 at the appropriate time, as indicated by arrow 113).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Miniskar’s task queue pointer index wraparound with the pointer hashtable-based task distribution system of Jain, Klein, and Kipp. A person of ordinary skill in the art would have been motivated to make this combination to provide Jain, Klein, and Kipp’s system with the advantage of implementing a circular data structure using linear memory space using wrapping pointers (see Miniskar [00057] a “circular queue” is a queue having a finite linear sequence of successive storage locations, such that a first of the storage locations logically succeeds a last of the storage location. Thus, the finite linear sequence of storage locations has a logical appearance of an endless circular sequence of storage locations. For queues having power-of-two length (e.g. 2, 4, 8, 16, . . . ), circularity can follow naturally from a binary bit representation of an index—e.g. for a queue of length 4 with a two-bit index representation, incremented index values naturally wrap around (0, 1, 2, 3, 0, 1, 2, . . . )).
Regarding claim 9, Jain, Klein, Kipp, and Miniskar teach the method of claim 8.
Jain further teaches wherein the fetch index identifies the second bucket, which identifies the second object identifier in response to the second object identifier having been determined to have been inserted into the hash table at an earliest time represented among the identifiers of objects (Fig 1B identifier pointers for job request groups and the job requests within them; [0042] a queue might be implemented by a collection offirst-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue).
Regarding claim 12, Jain, Klein, Kipp, and Miniskar teach the method of claim 8.
Jain further teaches wherein the second bucket stores the second object identifier and a third object identifier of the identifiers of objects (Fig 6S: Gvml storing two next identifiers Jvml and another Jvml), and wherein communicating, to the requestor, the second object identifier that is stored at the second bucket that is stored at the fetch index comprises determining that the second object identifier was added to the second bucket prior to the third object identifier being added to the second bucket (Fig 6J First Jvml added; Fig 6L first Jvml moves to start position of Gvml; Fig 60 second Jvml added to end position of Gvml; Fig 6S Jvml and another Jvml; [0040] Within a job request group are a "start" position and an "end" position. The start of a job request group (e.g., start 176.sub.1 and start 176.sub.2) is the first job request position of the job request group, and the end of the job request group (e.g., end 178.sub.1 and end 178.sub.2) is the last job request position of the job request group).
Regarding claim 13, Jain, Klein, Kipp, and Miniskar teach the method of claim 8.
Jain further teaches wherein the first bucket stores multiple object identifiers of the identifiers of objects (Fig 6T Gvml stores Jvml and another Jvml; [0039] Specifically, the foregoing queues comprise instances of job request groups (e.g.,job request group 182) that may or may not contain one or more job requests), wherein the multiple object identifiers comprise the first object identifier (Fig 6T Jvm1; each job request group corresponds to a particular one of the virtualized entities 112 (e.g., VM1, VM2, VM3, etc.). In many cases, the job request groups comprise one or more instances of job requests (e.g., one or more instances of J.sub.VM1, J.sub.VM2, J.sub.VM3.sup.1, J.sub.VM3.sup.2, etc.) issued by respective instances of the virtualized entities 112), and further comprising:
maintaining, by the system, an ordering of respective times when respective object identifiers of the multiple object identifiers were inserted into the first bucket ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0043] As indicated in the shown set of request attributes 186.sub.1 associated with an incoming job request 160.sub.1, the aforementioned job identifier might be included in a job request message issued by a virtualized entity (e.g., VM1). Specifically, request attributes 186.sub.1 indicates a particular job request might describe ... a timestamp (e.g., stored in a "time" field); [0040] Within a job request group are a "start" position and an "end" position. The start of a job request group (e.g., start 176.sub.1 and start 176.sub.2) is the first job request position of the job request group, and the end of the job request group (e.g., end 178.sub.1 and end 178.sub.2) is the last job request position of the job request group).
Regarding claim 15, Jain teaches the invention substantially as claimed including:
A non-transitory computer-readable medium comprising instructions that, in response to execution, cause a system comprising at least one processor to perform operations ([0101] The term "computer readable medium" or "computer usable medium" as used herein refers to any medium that participates in providing instructions to a data processor for execution; [0102] Common forms of computer readable media include any non-transitory computer readable medium), comprising:
storing identifiers of objects ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, other data structures such as linked lists represent the ordering of job requests groups in the queues; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" fieId), a node identifier (e.g., stored in a "node ID" fieId)), wherein the hash table comprises an index that identifies respective slots of a group of slots (Fig 1B index of job request groups each with a subqueue of jobs);
maintaining a first index that identifies a first slot of the group of slots into which a first object identifier is inserted ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has ... a "tail" position ... The tail of a queue (e.g., tail 174.sub.1 and tail 174.sub.2) is the position that follows the last job request and/or last populated job request group (if any) in the queue; [0056] if no job request group is found for VM2, job request group G.sub.VM2 is created and placed at the tail of the high priority job queue);
maintaining a second index that identifies a second slot of the group of slots from which a second object identifier is removed ([0042] a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues. When FIFOs are used to maintain an order for processing the jobs in a job request group, moving a job request group from one position in a queue to another position in a queue can be done with pointers; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue; [0022] When computing resources are available to process a job, the job request at the head of the high priority job queue is selected for processing), and wherein incrementing the second index changes a bucket of the hash table identified by the second index (Fig 6Q; Examiner notes: after processing JVM2 the queue head pointer identifying the next job group increments from GVM2 to GVM3); and
in response to determining to provide (Fig 2: Determining Step 210; [0050] If there is no then- current processing capacity to start another job (see "No" path of decision 210) ...; [0051] If there is processing capacity available (see "Yes" path of decision 210) after entering an incoming job request into one of the multi-level queues or as indicated by a job processing completion event (see "Job Processing Completed" path of decision 208), then a job request is selected for processing from the multi-level queues (step 240); [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)) a requestor ([0029] As can be observed, the virtualized entities 112 access a set of distributed computing resources 116 (e.g., distributed storage resources 122, distributed network resources 124, distributed CPU resources 126, etc.) at cluster 102 through a control layer 114; [0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134
to select job requests (e.g., selected job request 164) for processing at cluster 102. Various sets of in-process jobs can be managed by job executor 136. In some cases, each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs) with one of the identifiers of objects ([0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" fieId), a node identifier (e.g., stored in a "node ID" fieId)), Examiner notes: A job executor identifies job requests, which contain device identifiers, to distributed computing resources 116 for processing), wherein the requestor executes on a second device ([0029] distributed CPU resources 126), providing the requestor with the second object identifier that is stored at the second index of the hash table (Fig 1B: RequestAttributes 186 and ln-ProcessJobs 188; [0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102 ... each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs; [0043] a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field), a node identifier (e.g., stored in a "node ID" field)); Examiner notes: Job executor facilitates communication between job requesters and cluster processors), and incrementing a value of the second index (Fig 6L Arrows; [0040] Each of the high priority job queue 152 and the low priority job queue 154 has a "head" position ... The head of a queue (e.g., head 172.sub.1 and head 172.sub.2) is the position of the first job request and/or first job request group (if any) in the queue. [0051] a job request at the head of the high priority job queue or the low priority job queue might be selected for processing; Examiner notes: pulling a job request from the head of the queue means the queue head pointer increments to the next job), wherein the first slot differs from the second slot (Fig 1B GVM2 GVM 3),
wherein a queue comprises the group of slots (Fig 1B High Priority Queue 152 contains slots Job Request Groups GVM2 GVM3 GVM4),
and wherein the requestor performs a task to be performed that is originated from a first device of that corresponds to the second object identifier, based on the providing ([0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102. Various sets of in-process jobs can be managed by job executor 136. In some cases, each set of in-process jobs might correspond to a particular type of computing resource (e.g., storage, network, CPU, etc.) associated with the in-process jobs; [0065] identify a virtual machine associated with the most-recently started job (step 454). In this embodiment, the most-recently started job is the job that was started as a result of operation of step 408 or as a result of operation of step 416).
Jain does not explicitly teach storing identifiers of objects in a hash table.
However, Klein teaches storing identifiers of objects in a hash table, (Fig 6 Element 601; [0031] FIG. 6 is an exemplary block diagram of a container 601 that contains queue metadata objects 602 for multiple queues (i.e., QUEUE 1, QUEUE 2, ... , QUEUE N) according to an embodiment of the invention. In one embodiment, container 601 is a hash table and queue metadata objects 602 are hash buckets. A hash bucket 602 contains the pointers for a queue, and uniquely defines a link to a queue via a data element known as a queue identifier (QUEUE ID). For instance, QUEUE_ID.sub.1is a link to the head node H.sub.1 of QUEUE 1. Similarly, QUEUE_ID.sub.2 is a link to the head node H.sub.2 of QUEUE 2, and so forth. In effect, the queue identifier acts as the hash key for hash table 601).
Jain differs from the claimed invention by the specific data structure used to host the job/task queues. Jain generically mentions queue management logic as being implementable by "any combination of hardware and software, and/or any combination of hardware data structures (e.g., hardware FIFOs) and/or software data structures (e.g., linked lists, pointers, hash tables, etc.)" while the claimed invention uses a hash table to host job/task queues. The multiple queue data structure in Jain does not explicitly use a hash table to reference to the queues. The prior art, Klein, teaches a hash table of queues. Because Klein teaches a hash table containing queues, hash tables and queues are known data structures in the art.
Combining the hash table of queues data structure of Klein with the multiple job queue system of Jain results in a job scheduling system that uses a hash table to reference job queues that store devices that request processing from a distributed resource. The results of the combination would have been predictable because utilization of hashing in object storage is common practice in computing. It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have simply substituted the multiple queue structure of Jain with the hash table of queues data structure of Klein resulting in a job queuing system that primarily utilizes a hash table to reference job queues.
Jain and Klein do not explicitly teach refraining from locking the first slot concurrently with communicating, to the requestor, the second object identifier that is stored at the second slot, while locking the second slot concurrently with providing, to the requestor, the second object identifier that is stored at the second slot.
However, Kipp teaches refraining from locking the first slot concurrently with communicating, to the requestor, the second object identifier that is stored at the second slot, while locking the second slot concurrently with providing, to the requestor, the second object identifier that is stored at the second slot ([0023] The task groups are a collection of tasks from the program and are grouped into task groups. The task group queues allow for ordered access to task groups that have been submitted for execution. The task scheduler 108 manages worker threads in the worker thread pool 104 that are scheduled to execute tasks. The task scheduler 108 is responsible for the state of the worker threads and the logic associated with assignment of the worker threads to task queues, task groups, and tasks; [0062] Because adding and removing from a task group queue happen on multiple worker threads, serializing access to the task group queue is necessary to maintain order; [0066] a low level queue that only allows one worker thread at a time may maintain a very simple locking mechanism; [0067] Only one hardware thread can operate on a specific piece of memory at a time. Processors generally do not have a sharing mechanism that orders access fairly. By having each queue maintain a separate lock, the likelihood that two worker threads will try to operate on the same lock is reduced. In this way they are less likely to stall each other and the program will operate faster; Examiner notes: each queue (bucket) having its own lock allows for modularity in the task allocation system. When a thread requires access to a queue it will only lock the queue it is retrieving a task from, refraining from locking all other queues).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the queue locking method of Kipp with the job queue system of Jain and Klein resulting in a hash table of queues job queuing system that maintains synchronization and only locks the required task queue for exclusive thread access. The benefit of maintaining locks on task queues is that the resource holding the lock is able to confidently perform operations on the task queue without external interference changing the queue's contents (Kipp [0006] mutual exclusion (Mutexes), critical sections, and locks. These mechanisms are typically used to guard a region of a program from multiple simultaneous access from multiple threads).
Jain, Klein and Kipp do not explicitly teach wherein incrementing the first index past a largest index value of the index comprises setting the first index to a smallest index value of the index, wherein incrementing the second index past the largest index value of the index comprises setting the second index to the smallest index value of the index.
However, Miniskar teaches wherein incrementing the first index past a largest index value of the index comprises setting the first index to a smallest index value of the index, wherein incrementing the second index past the largest index value of the index comprises setting the second index to the smallest index value of the index ([0046] A front pointer can be used to designate a next queue element to be dequeued, and a rear pointer can be used to indicate a next queue element to receive an entry; [0077] Both pointers 121, 129 can wrap around from index 8 to index 0 at the appropriate time, as indicated by arrow 113).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined Miniskar’s task queue pointer index wraparound with the pointer hashtable-based task distribution system of Jain, Klein, and Kipp. A person of ordinary skill in the art would have been motivated to make this combination to provide Jain, Klein, and Kipp’s system with the advantage of implementing a circular data structure using linear memory space using wrapping pointers (see Miniskar [00057] a “circular queue” is a queue having a finite linear sequence of successive storage locations, such that a first of the storage locations logically succeeds a last of the storage location. Thus, the finite linear sequence of storage locations has a logical appearance of an endless circular sequence of storage locations. For queues having power-of-two length (e.g. 2, 4, 8, 16, . . . ), circularity can follow naturally from a binary bit representation of an index—e.g. for a queue of length 4 with a two-bit index representation, incremented index values naturally wrap around (0, 1, 2, 3, 0, 1, 2, . . . )).
Regarding claim 16, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Jain further teaches wherein the requestor is a first requestor (Fig 1A Distributed Computing Resources 116; [0031] Such interactions between the virtualized entities 112 and controllers comprising the control layer 114 often pertain to requests to access the underlying computing resources (e.g., distributed computing resources 116) of cluster 102 so as to perform certain "jobs" (e.g., tasks, operations, processes, etc.) associated with the virtualized entities 112), and wherein the operations further comprise: determining to provide a third requestor that comprises the first requestor or a second requestor with a third object identifier of the identifiers of objects (Fig 6C -> Fig 6D Jvm2 identified and processed by second resource in Job Executor; [0033] A job executor 136 at job scheduler 130 accesses the multi-level queues 134 to select job requests (e.g., selected job request 164) for processing at cluster 102);
and, in response to determining that the third object identifier is not found in the hash table (Fig 3 Element 308 “Group Exists?”; [0058] If no job request group for the associated virtual machine exists in one of the queues (see "No" path of decision 308), then a new, empty job request group corresponding to the virtual machine is created at the tail of the high priority job queue (step 310). Regardless of whether a job request group has just been newly created, or if it has been determined that a job request group is already in existence for the virtual machine in one of the queues (see "Yes" path of decision 308), then the incoming job request is placed at the end of the located job request group (step 312)), performing iterations of, re-determining to provide the third requestor with the third object identifier (Fig 2 Element 210 Can start a job now?), and
determining whether the third object identifier is found in the hash table (Fig 2 Element 240 Select a job request for processing from the multi-level queues; [0056] If no job request group for the associated virtual machine exists in one of the queues...).
Regarding claim 17, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Jain further teaches in response to inserting at least one object identifier of the identifiers of objects in the hash table (Fig 2 Step 210 in response to step 230 (Enter job request into multi-level queues)).
Kipp further teaches waking at least one requestor of a group of requestors that comprises the requestor ([0022] an active worker thread pool 104, an inactive worker thread pool 106, and a task scheduler 108; [0058] The task scheduler 108 thus will signal the worker thread assigned that work has been assigned and activate the worker thread to begin to perform the added task).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined the activation method of Kipp with the job queue system of Jain, Klein, Kipp, and MacNeil resulting in a hash table of queues job queuing system that wakes/activates workers on demand for job execution in a multi-threaded environment to achieve parallel processing for faster program execution on multithreaded systems. (Kipp [0004] In multi-core systems, it is desirable to perform multi-threading in order to accomplish parallel processing of programs. Multi-threading is a widespread programming and execution model that allows multiple software threads to exist within the context of a single process. These software threads share the resources of the multi-core system, but are able to execute independently. Multi-threading can also be applied to a single process to enable parallel execution on a multi-core system. This advantage of a multi-threaded program allows it to operate faster on computer systems that have multiple CPUs, CPUs with multiple cores, or across a cluster of machines because the threads of the program naturally lend themselves to concurrent execution).
Regarding claim 18, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 17.
Kipp further teaches wherein the operations further comprise: locking the hash table when waking the at least one requestor ([0058] The task scheduler 108 thus will signal the worker thread assigned that work has been assigned and activate the worker thread to begin to perform the added task; [0062] the logic each worker thread runs when it is active and looking for a task group to work on. The code looks at the workload done and will decide which task queue the worker thread will go to next; [0066] a low level queue that only allows one worker thread at a time may maintain a very simple locking mechanism; [0067] Since a lock around each task queue increases serial time for executing programs, the hierarchy allows distribution of locks, which results in less contentious hierarchy of locks. This decreases the amount of time for the lock ... By having each queue maintain a separate lock, the likelihood that two worker threads will try to operate on the same lock is reduced. In this way they are less likely to stall each other and the program will operate faster).
Regarding claim 19, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Jain further teaches wherein the identifiers of objects identify respective devices of a computing cluster ([0029] As such, various instances of virtualized entities 112 (e.g., virtual machines VM1, VM2, VM3, VM7, VM8, VM9, etc.) are implemented at the nodes of cluster 102; [0043] As indicated in the shown set of request attributes 186.sub.1 associated with an incoming job request 160.sub.1, the aforementioned job identifier might be included in a job request message issued by a virtualized entity (e.g., VM1). Specifically, request attributes 186.sub.1 indicates a particular job request might describe a VM identifier (e.g., stored in a "vmlD" field)), and wherein the requestor comprises a thread that performs tasks for the devices (As can be observed, the virtualized entities 112 access a set of distributed computing resources 116 (e.g., distributed storage resources 122, distributed network resources 124, distributed CPU resources 126, etc.) at cluster 102; [0107] Multiple clusters can communicate between one module to another...; [0108] A module as used herein can be implemented using any mix of any portions of memory and any extent of hard-wired circuitry including hard-wired circuitry embodied as a data processor ... A data processor can be organized to execute a processing entity ... A processing entity ... can carry out computations and/or processing steps using ... one or more threads ...).
Regarding claim 20, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Kipp further teaches wherein the first slot is configured to be accessed with a first lock that is local to the first slot ([0067] By having each queue maintain a separate lock...), wherein the second slot is configured to be accessed with a second lock that is local to the second slot ([0067] By having each queue maintain a separate lock...), and wherein the first slot is configured to be accessed concurrently with accessing the second slot ([0067] Since a lock around each task queue increases serial time for executing programs, the hierarchy allows distribution of locks, which results in less contentious hierarchy of locks. This decreases the amount of time for the lock, and allows synchronization between task groups therefor preventing stalling, which may effectively serialize the program. Distribution also distributes the memory needed to decrease contention, and therefore have only one memory associated with the core. Contention happens when multiple hardware threads or processor cores want to operate on the same piece of program memory. Only one hardware thread can operate on a specific piece of memory at a time. Processors generally do not have a sharing mechanism that orders access fairly. By having each queue maintain a separate lock, the likelihood that two worker threads will try to operate on the same lock is reduced. In this way they are less likely to stall each other and the program will operate faster).
Regarding claim 22, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Jain further teaches wherein the second slot stores the second object identifier and a third object identifier, and wherein the providing of the second object identifier comprises determining that the second object identifier was added to the second slot prior to the third object identifier being added to the second slot ([0042] As earlier indicated, specialized job request data structures are used to improve the way a computer stores and retrieves data in memory(e.g., for ongoing queue management). Specifically, a queue might be implemented by a collection of first-in, first-out (FIFO) data structures that are implemented in hardware or software or both. In such cases a job request group is assigned to a corresponding FIFO, and other data structures such as linked lists represent the ordering of job requests groups in the queues.
Regarding claim 23, Jain, Klein, Kipp, and Miniskar teach the non-transitory computer-readable medium of claim 15.
Jain further teaches wherein the operations further comprise: in response to determining to make a third object identifier, of the identifiers of objects, available to the requestor, inserting the third object identifier into the hash table at the first index, and incrementing the first index (Fig 1B Empty Job Request Group GVM4; Examiner notes: once GVM4 is introduced with jobs available the tail pointer increment to point to the space after GVM4).
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
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 https:/www.uspto.gov/interviewpractice. Any inquiry concerning this communication or earlier communications from the examiner should be directed to HARRISON LI whose telephone number is (703) 756-1469. The examiner can normally be reached Monday-Friday 9:00am-5:30pm ET. 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, Aimee Li can be reached on 571-272-4169. 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.
/H.L./
Examiner, Art Unit 2195
/BRADLEY A TEETS/Supervisory Patent Examiner, Art Unit 2197
Prosecution Insights