Multi-level job processing queues

Patent metadata

Field	Value
Publication number	US-10990441-B2
Application number	US-201816051254-A
Country	US
Kind code	B2
Filing date	Jul 31, 2018
Priority date	Jul 31, 2018
Publication date	Apr 27, 2021
Grant date	Apr 27, 2021

Abstract

Systems and methods for scheduling job requests in a virtualization system. A method embodiment commences upon initialization of a pair of multi-level queues comprising a high priority job queue and a low priority job queue. A plurality of virtual machines issue job requests. Queue management logic receives incoming job requests from the virtual machines and locates or creates a job request group corresponding to the virtual machine of the incoming job request. The incoming job request is positioned into the job request group and the job request group is positioned into a queue. When a job executor is ready for a next job, then a job for execution can be identified by locating a next job in a next job request group that is at the front of either the high priority queue or at the front of the low priority queue. When a job finishes, the queues are reorganized.

First claim

What is claimed is:

1. A method for scheduling job requests in multi-level job processing queues, the method performed by at least one computer and comprising:
initializing a multi-level queue, the multi-level queue comprising a high priority job queue and a low priority job queue;
receiving a job request from an individual virtual machine;
locating or creating a job request group for the individual virtual machine, wherein the job request group corresponds to the individual virtual machine and different job request groups are created for different respective virtual machines;
positioning the job request into the job request group for the individual virtual machine;
positioning the job request group for the individual virtual machine into at least one of, the high priority job queue, or the low priority job queue;
scheduling execution of a job by locating a next job in a next job request group for the individual virtual machine that is at either a high priority job queue location or at a low priority job queue location; and
reorganizing the multi-level queue.

2. The method of claim 1 , wherein the high priority job queue location comprises a head location in the high priority job queue and the low priority job queue location comprises a head location in the low priority job queue, and scheduling execution of the job comprising locating the job in the head location in the high priority job queue or the head location in the low priority job queue.

3. The method of claim 1 , further comprising:
determining a count of one or more in-process jobs, the count being determined based at least in part on then-current job status, and wherein reorganizing the multi-level queue is based at least in part on the count of the one or more in-process jobs.

4. The method of claim 1 , further comprising:
determining a count of one or more in-process jobs, the count being determined based at least in part on then-current job status, and wherein the count corresponds to a portion of the one or more in-process jobs that is associated with a virtualized entity.

5. The method of claim 1 , wherein reorganizing the multi-level queue comprises demoting the job request group from the high priority job queue to the low priority job queue or reorganizing the multi-level queue comprises promoting the job request group from low priority job queue to the high priority job queue.

6. The method of claim 1 , wherein the multi-level queue holds a plurality of job request groups, and each group of the job request groups corresponds to an single respective virtual machine.

7. The method of claim 1 , wherein a request attribute associated with the job request describes at least one of, a virtual machine identifier, a node identifier, a job identifier, a timestamp, a job status, a request status, or a job attribute.

8. A non-transitory computer readable medium having stored thereon a sequence of instructions which, when stored in memory and executed by a processor causes the processor to perform a process comprising:
initializing a multi-level queue, the multi-level queue comprising a high priority job queue and a low priority job queue;
receiving a job request from an individual virtual machine;
locating or creating a job request group for the individual virtual machine, wherein the job request group corresponds to the individual virtual machine and different job request groups are created for different respective virtual machines;
positioning the job request into the job request group for the individual virtual machine;
positioning the job request group for the individual virtual machine into at least one of, the high priority job queue, or the low priority job queue;
scheduling execution of a job by locating a next job in a next job request group for the individual virtual machine that is at either a high priority job queue location or at a low priority job queue location; and
reorganizing the multi-level queue.

9. The computer readable medium of claim 8 , wherein the high priority job queue location comprises a head location in the high priority job queue and the low priority job queue location comprises a head location in the low priority job queue, and scheduling execution of the job comprising locating the job in the head location in the high priority job queue or the head location in the low priority job queue.

10. The computer readable medium of claim 8 , determining a count of one or more in-process jobs, the count being determined based at least in part on then-current job status, and wherein reorganizing the multi-level queue is based at least in part on the count of the one or more in-process jobs.

11. The computer readable medium of claim 8 , determining a count of one or more in-process jobs, the count being determined based at least in part on then-current job status, and wherein the count corresponds to a portion of the one or more in-process jobs that is associated with a virtualized entity.

12. The computer readable medium of claim 8 , wherein reorganizing the multi-level queue comprises demoting the job request group from the high priority job queue to the low priority job queue or reorganizing the multi-level queue comprises promoting the job request group from low priority job queue to the high priority job queue.

13. The computer readable medium of claim 8 , wherein the multi-level queue holds a plurality of job request groups, and each group of the job request groups corresponds to an single respective virtual machine.

14. The computer readable medium of claim 8 , wherein a request attribute associated with the job request describes at least one of, a virtual machine identifier, a node identifier, a job identifier, a timestamp, a job status, a request status, or a job attribute.

15. A system for scheduling job requests in multi-level job processing queues, the system comprising:
a storage medium having stored thereon a sequence of instructions; and
a processor that execute the sequence of instructions to cause the processor to perform a set of acts, the set of acts comprising,
initializing a multi-level queue, the multi-level queue comprising a high priority job queue and a low priority job queue;
receiving a job request from an individual virtual machine;
locating or creating a job request group for the individual virtual machine, wherein the job request group corresponds to the individual virtual machine and different job request groups are created for different respective virtual machines;
positioning the job request into the job request group for the individual virtual machine;
positioning the job request group for the individual virtual machine into at least one of, the high priority job queue, or the low priority job queue;
scheduling execution of a job by locating a next job in a next job request group for the individual virtual machine that is at either a high priority job queue location or at a low priority job queue location; and
reorganizing the multi-level queue.

16. The system of claim 15 , wherein reorganizing the multi-level queue comprises demoting the job request group from the high priority job queue to the low priority job queue or reorganizing the multi-level queue comprises promoting the job request group from low priority job queue to the high priority job queue.

17. The system of claim 15 , wherein the high priority job queue location comprises a head location in the high priority job queue and the low priority job queue location comprises a head location in the low priority job queue, and scheduling execution of the job comprising locating the jo

Assignees

• Nutanix Inc

Inventors

• Jain Kshitiz
• Kajaria Prateek

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title

• G06F2009/45575

  Starting, stopping, suspending or resuming virtual machine instances · CPC title

• G06F9/45558

  Hypervisor-specific management and integration aspects · CPC title