Soft real-time load balancer
The present disclosure is based on a multi-core or multi-processor virtualized environment that comprises both time-sensitive and non-time-sensitive tasks. The present disclosure describes techniques that use a plurality of criteria to choose a processing resource that is to execute tasks. The present disclosure further describes techniques to re-schedule queued tasks from one processing resource to another processing resource, based on a number of criteria. Through load balancing techniques, the present invention both (i) favors the processing of soft real-time tasks arising from media servers and applications, and (ii) prevents “starvation” of the non-real-time general computing applications that co-exist with the media applications in a virtualized environment. These techniques, in the aggregate, favor the processing of soft real-time tasks while also reserving resources for non-real-time tasks. These techniques manage multiple processing resources to balance the competing demands of soft real-time tasks and of non-real-time tasks.
1. A method comprising:
receiving during a first time interval by a data-processing system a plurality of tasks that are time-sensitive;
bin-packing by the data-processing system the plurality of tasks into (a) a first bin-pack to be executed on a first processor and (b) a second bin-pack to be executed on a second processor, wherein:
(i) μ 1 is a percentage of time to be used by the first processor for executing tasks in the first bin-pack during a second time interval,
(ii) μ 2 is a percentage of time to be used by the second processor for executing tasks in the second bin-pack during the second time interval, and
(iii) the bin-packing is based on minimizing a difference between μ 1 and μ 2 ;
executing by the first processor the tasks in the first bin-pack;
executing by the second processor the tasks in the second bin-pack;
scheduling by the data-processing system a first task that is a non-time-sensitive task to be executed on the first processor, wherein the first task is at a head of a first queue that is associated with the first processor; and
executing a second task that is a non-time-sensitive task on the first processor before the first task when:
the second task is at a head of a second queue that is associated with the second processor;
the first task and the second task are of equal priority; and
the second task entered the second queue before the first task entered the first queue,
wherein:
each time-sensitive task has a runtime parameter;
μ 1 is based on a sum of the runtime parameters of the tasks in the first bin-pack; and
μ 2 is based on a sum of the runtime parameters of the tasks in the second bin-pack.
2. The method of claim 1 wherein each runtime parameter is based on an execution time of an associated task during a third time interval that precedes the first time interval.
3. The method of claim 1 wherein each runtime parameter is based on an average of execution times of respective associated tasks during a plurality of time intervals that precede the first time interval.
4. The method of claim 1 wherein the bin-packing is further based on scheduling tasks to the same processor that executed them during a third time interval that precedes the first time interval.
5. The method of claim 1 further comprising:
scheduling by the data-processing system a first third task that is a non-time-sensitive task to be executed on the first processor; and
executing a second fourth task that is a non-time-sensitive task on the first processor before the first third task when the second fourth task is of higher priority than the first third task.
6. The method of claim 1 wherein the data-processing system comprises a virtualized computing environment that comprises the first processor and the second processor.
7. The method of claim 1 wherein the data-processing system comprises a credit-scheduler that determines an order of execution of the first task and of the second task.
8. The method of claim 1 , further comprising:
scheduling by the data-processing system a third task to be executed on the first processor, wherein the third task is at the head of the first queue that comprises a plurality of tasks to be executed on the first processor;
scheduling by the data-processing system a fourth task to be executed on the second processor, wherein the fourth task is at the head of the second queue that comprises a plurality of tasks to be executed on the second processor; and
executing the fourth task on the first processor before the third task when:
(i) the third task and the fourth task are of equal priority, and
(ii) the third task is a non-time-sensitive task, and
(iii) the fourth task is a time-sensitive task.
9. The method of claim 1 , further comprising:
scheduling the second task to be executed on the second processor, wherein the second queue comprises a plurality of tasks to be executed on the second processor.
10. The method of claim 1 , further comprising:
scheduling by the data-processing system a third task to be executed on the first processor, wherein the third task is at the head of the first queue that comprises a plurality of tasks to be executed on the first processor;
scheduling by the data-processing system a fourth task to be executed on the second processor, wherein the fourth task is at the head of the second queue that comprises a plurality of tasks to be executed on the second processor; and
executing the fourth task on the first processor before the third task when:
(i) the fourth task is of higher priority than the third task, and
(ii) the third task is a non-time-sensitive task.
11. The method of claim 10 , wherein the fourth task is a time-sensitive task.
12. The method of claim 10 , wherein the fourth task is a non-time-sensitive task.
13. The method of claim 10 , wherein the data-processing system comprises a credit-scheduler that determines the order of execution of the third task and of the fourth task.