Adaptive program task scheduling algorithm

Patent metadata

Field	Value
Publication number	US-2020409754-A1
Application number	US-201916457631-A
Country	US
Kind code	A1
Filing date	Jun 28, 2019
Priority date	Jun 28, 2019
Publication date	Dec 31, 2020
Grant date	—

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, comprising:
maintaining, by a server computer system, first and second sets of task queues that have different performance characteristics; collecting, by the server computer system, performance metrics relating to processing of program tasks from the first and second sets of task queues; updating, by the server computer system based on the collected performance metrics, a scheduling algorithm for assigning program tasks to queues in the first and second sets of task queues; receiving, by the server computer system, a particular program task associated with a user transaction; selecting, by the server computer system using the updated scheduling algorithm, the first set of task queues for the particular program task; and assigning, by the server computer system based on the selecting, the particular program task in a particular task queue in the first set of task queues.

2 . The method of claim 1 , wherein the first and second sets of task queues having different performance characteristics constitutes the first set of task queues including blocking queues and the second set of task queues including non-blocking queues.

3 . The method of claim 1 , wherein the performance metrics include execution times associated with executing, by a processor core, of each processed program task, and wherein the selecting is performed by:
estimating, using the updated scheduling algorithm, an execution time for the particular program task; and selecting the first set of task queues in response to determining that the estimated execution time reaches a particular threshold value.

4 . The method of claim 1 , further comprising selecting, by the server computer system, the particular task queue in the first set of task queues in response to determining that the particular task queue supports a particular quality of service parameter associated with the particular 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 particular program task to a different task queue in the first set of task queues.

6 . The method of claim 1 , further comprising reassigning the assigned particular program task to a different task queue in the first set of task queues in response to determining that execution of a different program task in the particular task queue is exceeding an estimated execution time.

7 . The method of claim 1 , further comprising:
receiving a different program task associated with the user transaction; selecting, using the updated scheduling algorithm, the second set of task queues for the different program task; and assigning, based on the selecting of the second set of task queues, the different program task in a different task queue in the second set of task queues.

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 comprising:
maintaining first and second sets of task queues that have different blocking characteristics; collecting performance metrics, including execution times of processed program tasks, relating to processing of program tasks from the first and second sets of task queues; updating, based on the collected performance metrics, a scheduling algorithm for assigning a plurality of program tasks to task queues in the first and second sets of task queues; estimating an execution time for a particular program task of the plurality of program tasks; selecting, using the estimated execution time, the first set of task queues for the particular program task; and assigning, based on the updated scheduling algorithm, the particular program task in a particular task queue in the first set of task queues.

9 . The computer-readable medium of claim 8 , wherein the first and second sets of task queues having different blocking characteristics constitutes the first set of task queues including blocking queues and the second set of task queues including non-blocking queues, and wherein the selecting includes selecting the first set in response to determining that the estimated execution time does not satisfy a threshold value.

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

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

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

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

14 . The 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 execute the instructions to cause the system to:
assign, using a scheduling algorithm, a plurality of program tasks into a set of blocking queues and a set of non-blocking queues maintained in the memory;
based on execution of program tasks from the sets of blocking and non-blocking queues, collect performance metrics of processed ones of the plurality of program tasks;
update, using the collected performance metrics, the scheduling algorithm;
estimate, using the collected performance metrics, an execution time for a particular program task of the plurality of program tasks;
select, in response to a determination that the estimated execution time satisfies a threshold amount of time, the set of non-blocking queues for the particular program task; and
assign, based on the updated scheduling algorithm, the particular program task to a particular non-blocking queue in the set of non-blocking queues.

16 . The system of claim 15 , wherein executing the instructions further causes the system to:
estimate, using the collected performance metrics, a different execution time for a different program task of the plurality of program tasks; select, in response to a determination that the different execution time fails to satisfy the threshold amount of time, the set of blocking queues for the different program task; and assign, based on the updated scheduling algorithm, the different program task to a given blocking queue in the set of blocking queues.

17 . The system of claim 15 , wherein executing the instructions further causes the system to adjust the threshold amount of time based on a first number of program tasks assigned to the set of blocking queues and a second number of program tasks assigned to the set of non-blocking queues.

18 . The s

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

• G06Q20/4014

  Identity check for transactions · CPC title

• G06F2209/501

  Performance criteria · CPC title

• G06F2209/486

  Scheduler internals · CPC title

• G06F2209/483

  Multiproc · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title