Adaptive program task scheduling to blocking and non-blocking queues

Patent metadata

Field	Value
Publication number	US-11422856-B2
Application number	US-201916457631-A
Country	US
Kind code	B2
Filing date	Jun 28, 2019
Priority date	Jun 28, 2019
Publication date	Aug 23, 2022
Grant date	Aug 23, 2022

Abstract

Techniques are disclosed relating to scheduling program tasks in a server computer system. An example server computer system is configured to maintain first and second sets of task queues that have different performance characteristics, and to collect performance metrics relating to processing of program tasks from the first and second sets of task queues. Based on the collected performance metrics, the server computer system is further configured to update a scheduling algorithm for assigning program tasks to queues in the first and second sets of task queues. In response to receiving a particular program task associated with a user transaction, the server computer system is also configured to select the first set of task queues for the particular program task, and to assign the particular program task in a particular task queue in the first set of task queues.

First claim

What is claimed is:

1. A method performed by a server computer system to update a scheduling algorithm for program tasks that are executed by a processor having a plurality of processor cores, the method comprising:
distributing the program tasks across first and second sets of task queues that are in a memory accessible by the server computer system, the first set of task queues including blocking queues and the second set of task queues including non-blocking queues;
collecting performance metrics relating to processing of the program tasks from the first and second sets of task queues that include collected execution times for at least some of the processed program tasks;
updating, based on the collected performance metrics, the scheduling algorithm for assigning the program tasks to queues in the first and second sets of task queues by modifying a threshold amount of time that is used to assign the program tasks to the first and second sets of task queues;
receiving first and second program tasks associated with a user transaction;
estimating respective first and second execution times for the first and second program tasks based on the collected execution times for ones of the processed program tasks that are similar to the first and second program tasks;
in response to determining that the first estimated execution time is greater than the modified threshold amount of time, storing the first program task in one queue of the first set of task queues;
in response to determining that the second estimated execution time is less than the modified threshold amount of time, storing the second program task in the second set of task queues;
pulling, from the one queue of the first set of task queues by a particular processing core of the plurality of processing cores, the first program task; and
executing, by the particular processing core, the first program task.

2. The method of claim 1 , wherein ones of the second set of task queues are associated with respective ones of the plurality of processing cores.

3. The method of claim 1 , further comprising adjusting the estimated first and second execution times based on an availability of data associated with the respective first and second program tasks.

4. The method of claim 1 , further comprising selecting, by the server computer system, the one queue in the first set of task queues in response to determining that the one queue supports a particular quality of service parameter associated with the first program task.

5. The method of claim 1 , further comprising:
repeating the updating of the updated scheduling algorithm; and
in response to use of the repeatedly updated scheduling algorithm, reassigning the first program task to a different task queue in the first set of task queues.

6. The method of claim 1 , further comprising moving the first program task from the one queue in the first set of task queues to a different queue in the first set of task queues in response to determining that execution of a different program task in the one queue is exceeding a respective estimated execution time.

7. The method of claim 1 , further comprising:
pulling, from the second set of task queues by a given processing core of the plurality of processing cores, the second program task; and
executing, by the given processing core, the second program task.

8. A non-transitory, computer-readable medium storing instructions that, when executed by a server computer system, cause the server computer system to perform operations to update a scheduling algorithm for a plurality of program tasks that are executed by a processor having a plurality of processor cores, the operations comprising:
distributing the plurality of program tasks across first and second sets of task queues that are in a memory accessible by the server computer system, the first set of task queues including blocking queues and the second set of task queues including non-blocking queues;
collecting performance metrics, including collected execution times of at least some processed program tasks, relating to processing of the plurality of program tasks from the first and second sets of task queues;
updating, based on the collected performance metrics, the scheduling algorithm for assigning the plurality of program tasks to task queues in the first and second sets of task queues by modifying a threshold amount of time that is used to assign the plurality of program tasks to the first and second sets of task queues;
estimating respective first and second execution times for a first program task and a second program task of the plurality of program tasks based on the collected execution times for ones of the processed program tasks that are similar to the first and second program tasks;
in response to determining that the first estimated execution time is greater than the modified threshold amount of time, storing the first program task in one queue of the first set of task queues;
in response to determining that the second estimated execution time is less than the modified threshold amount of time, storing the second program task in the second set of task queues;
receiving, from the one queue of the first set of task queues by a particular processing core of the plurality of processing cores, the first program task; and
executing, by the particular processing core, the first program task.

9. The non-transitory, computer-readable medium of claim 8 , wherein ones of the second set of task queues are associated with respective ones of the plurality of processing cores.

10. The non-transitory, computer-readable medium of claim 8 , wherein the operations further comprise selecting, in response to determining that data to be used to process the first program task is located in a database that is external to the server computer system, selecting the first set of task queues for the first program task.

11. The non-transitory, computer-readable medium of claim 8 , further comprising selecting the first set of task queues for a different program task of the plurality of program tasks in response to determining that an insufficient amount of performance metrics have been collected to estimate execution times for the different program task.

12. The non-transitory, computer-readable medium of claim 8 , wherein the operations further comprise moving the first program task from the one queue to a different queue in the first set of task queues in response to execution of a different program task in the one queue exceeding an estimated execution time.

13. The non-transitory, computer-readable medium of claim 8 , wherein the operations further comprise selecting the one queue in the first set of task queues in response to determining that the one queue supports a particular quality of service parameter associated with the first program task.

14. The non-transitory, computer-readable medium of claim 8 , wherein the collected performance metrics includes respective start and finish times for executed program tasks.

15. A system comprising:
a memory storing instructions; and
a processor configured to update a scheduling algorithm for a plurality of program tasks that are executed by a plurality of processor cores by executing the instructions to cause the system to:
assign, using the scheduling algorithm, the plurality of program tasks into a set of blocking queues and a set of non-blocking queues that are maintained in the memory;
based on execution of the plurality of program tasks from the sets of blocking and non-blocking queues, collect performance metrics of processed ones of the plurality of program tasks that inc

Assignees

• Paypal Inc

Inventors

• Li Xin
• Sun Libin
• Zhang Chao
• Yun Xiaohan
• Zhang Jun
• Tu Frédéric
• Yu Yang
• Wang Lei
• Ling Zhijun

Classifications

• G06F9/466

  Transaction processing · CPC title

• G06F9/4881 Primary

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

• G06F2209/483

  Multiproc · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title

• G06F9/463

  Program control block organisation · CPC title