Method for prioritizing tasks queued at a server system

• US 9,378,061 B2
• Filed: 12/16/2014
• Issued: 06/28/2016
• Est. Priority Date: 06/20/2014
• Status: Active Grant

• Current Assignee: ABBYY Production LLC (ABBYY Software)
• Original Assignee: ABBYY Development LLC
• Inventors: Panferov, Vasily Vladimirovich, Mesheryakov, Dmitry Konstantinovich
• Primary Examiner(s): VU, TUAN A
• Application Number:
  US14/571,832
• Publication Number:
  US 20150370606A1
• Time in Patent Office: 560 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests

Abstract

An algorithm for assigning priorities to tasks queued for processing by users based on how heavily each task'"'"'s user used the system resources in the past, including the number of tasks queued by the user in the past, the volume of these tasks, and the amount of processor time used. In the OCR context, the tasks are graphic files placed on servers and chosen for processing in accordance with the assigned priorities.

Claims

1. A method for prioritizing for at least one processor a plurality of tasks of a plurality of users, comprising, for an unprocessed task provided by a user from the plurality of users,

assigning a numerical priority to the user;

calculating a monotonic metric M1 for cumulative processor time used by prior tasks provided by the user on the at least one processor within a prior time period T1;

calculating a monotonic metric M2 for time interval between the unprocessed task and a preceding task provided by the user for the at least one processor within a prior time period T2;

calculating a monotonic metric M3 for cumulative task volume provided by the user for the at least one processor within a prior time period T3;

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, and M3; and

assigning the user'"'"'s numerical priority to the unprocessed task;

wherein unprocessed tasks with higher priorities are selected for processing on the at least one processor before unprocessed tasks with lower priorities; and

wherein the at least one processor sequentially executes only one task at a time.

2. The method of claim 1, further comprising:

calculating a monotonic metric M4 for cumulative task volume provided by the user for the at least one processor within an earlier time period T4; and

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, M3, and M4.

3. The method of claim 1, wherein the at least one processor executes any of the plurality of tasks entirely without interrupting for any other task of the plurality of tasks or simultaneously processing any other task of the plurality of tasks.

4. The method of claim 1, wherein the user'"'"'s numerical priority is an integer within an interval.

5. The method of claim 1, wherein among unprocessed tasks with equal priorities the task provided for processing at an earlier moment is selected for processing on the at least one processor before other unprocessed tasks with equal priorities.

6. A system comprising:

a computer server or a cloud server being equipped with physical memory for storing tasks and software capable of executing instructions for prioritizing for at least one processor a plurality of tasks of a plurality of users, comprising, for an unprocessed task provided by a user.

calculating a monotonic metric M1 for cumulative processor time used by prior tasks provided by the user on the at least one processor within a prior time period T1;

calculating a monotonic metric M2 for time interval between the unprocessed task and a preceding task provided by the user for the at least one processor within a prior time period T2;

calculating a monotonic metric M3 for cumulative task volume provided by the user for the at least one processor within a prior time period T3;

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, and M3; and

assigning the user'"'"'s numerical priority to the unprocessed task;

wherein unprocessed tasks with higher priorities are selected for processing on the at least one processor before unprocessed tasks with lower priorities; and

wherein the at least one processor sequentially executes only one task at a time.

7. The system of claim 6, wherein the instructions further comprise:

calculating a monotonic metric M4 for cumulative task volume provided by the user for the at least one processor within an earlier time period T4; and

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, M3, and M4.

8. The system of claim 6, wherein the at least one processor executes any of the plurality of tasks entirely without interrupting for any other task of the plurality of tasks or simultaneously processing any other task of the plurality of tasks.

9. The system of claim 6, wherein the user'"'"'s numerical priority is an integer within an interval.

10. The system of claim 6, wherein among unprocessed tasks with equal priorities the task provided for processing at an earlier moment is selected for processing on the at least one processor before other unprocessed tasks with equal priorities.

11. A physical, non-transitory computer storage medium having stored thereon a program which when executed by a processor, performs instructions for prioritizing for at least one processor a plurality of tasks of a plurality of users, comprising, for an unprocessed task provided by a user from the plurality of users,

assigning a numerical priority to the user;

calculating a monotonic metric M1 for cumulative processor time used by prior tasks provided by the user on the at least one processor within a prior time period T1;

calculating a monotonic metric M2 for time interval between the unprocessed task and a preceding task provided by the user for the at least one processor within a prior time period T2;

calculating a monotonic metric M3 for cumulative task volume provided by the user for the at least one processor within a prior time period T3;

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, and M3; and

assigning the user'"'"'s numerical priority to the unprocessed task;

wherein unprocessed tasks with higher priorities are selected for processing on the at least one processor before unprocessed tasks with lower priorities; and

wherein the at least one processor sequentially executes only one task at a time.

12. The medium of claim 11, wherein the instructions further comprise:

calculating a monotonic metric M4 for cumulative task volume provided by the user for the at least one processor within an earlier time period T4; and

reducing the user'"'"'s numerical priority monotonically depending on M1, M2, M3, and M4.

13. The medium of claim 11, wherein the at least one processor executes any of the plurality of tasks entirely without interrupting for any other task of the plurality of tasks or simultaneously processing any other task of the plurality of tasks.

14. The medium of claim 11, wherein the user'"'"'s numerical priority is an integer within an interval.

15. The medium of claim 11, wherein among unprocessed tasks with equal priorities the task provided for processing at an earlier moment is selected for processing on the at least one processor before other unprocessed tasks with equal priorities.