Last updated
How to partition tasks?
By information sharing.
By functionality.
Minimizing resources: number of cores, frequency, energy, etc.
and many others (e.g fault-tolerance).
These approaches do not aim at schedulability / real-time performance.
Solutions:
Select a fitness criteria
Example: task utilization or task density
Decide how to sort the tasks (decreasing, increasing, random).
Decide what is the fitness evaluation method (assignment rejection rule).
Use a fitting policy to assign tasks to processors:
FirstFit, BestFit, WorstFit, NextFit (there are others).
number of bins used by an algorithm A.
minimum number of bins used by the optimal algorithm.
Number of bins required for sure by any algorithm.
Number of bins that cannot be exceeded for sure by any algorithm.
“c” is the capacity of each bin.
Optimality implies clairvoyance for online sequences → heuristics.
Partitioning heuristics (some examples)
First fit (FF)
Place each item in the first bin that can contain it.
Best fit (BF)
Place each item in the bin with the smallest empty space.
Worst fit (WF)
Place each item in the used bin with the largest empty space.
Next fit (NF)
Place each item in the same bin as the last item.
Place each item in the first bin that can contain it.
Place each item in the bin with the smallest empty space.
Places each item in the used bin with the largest empty space, otherwise start a new bin.
Place each item in the same bin as the last item. If it does not fit, start a new bin.
The performance of each algorithm strongly depends on the input sequence.
However:
NF
has a poor performance since it does not exploit the empty space in the previous bins.
FF
improves the performance by exploiting the empty space available in all the used bins.
BF
tends to fill the used bins as much as possible.
WF
tends to balance the load among the used bins.
In this case, sorting tasks by decreasing execution times would allow for minimizing the number of bins.
Theoretical results.
NF and WF never use more than 2 · M0 bins.
FF and BF never use more than (1.7 · M0 + 1) bins.
FFD never uses more than ( 4/3 M0 + 1) bins.
FFD never uses more than ( 11/9 M0 + 4) bins.
Given a set of n items of volume
No algorithm can use less than
No algorithm can use more than
Any online algorithm uses at least 4/3 times the optimal number of bins:
Any task set with total utilization is schedulable in a multiprocessor made up of m processors using FF allocation and EDF scheduling on each processor.(Lopez-Diaz-Garcia)
Any task set with total utilization is schedulable in a multiprocessor made up of m processors using FF allocation and RM scheduling on each processor.(Oh and Baker)
When each task has utilization , the task set is feasible by global RM scheduling if . (Andersson, Baruah, Jonsson)
