# Task allocation
How to partition tasks?
* By information sharing.
* By functionality.
* Minimizing resources: number of cores, frequency, energy, etc.
* and many others (e.g fault-tolerance).
{% hint style="danger" %}
These approaches do not aim at schedulability / real-time performance.
{% endhint %}
## Problem
{% hint style="info" %}
### Partitioning problem (bin packing problem)
Given a set of tasks τ = {τ1 , τ2 , ..., τn }, and a multiprocessor platform with m processors,find an assignment from tasks to processors such that each task is assigned to one and only one processor.
{% endhint %}
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).
## Bin packing heuristics - definitions
{% hint style="info" %}
### The Bin Packing problem
Pack n objects of different size a1, a2, ..., an into the minimum number of bins (containers) of fixed capacity c.
{% endhint %}
### Definitions
| | |
| -------------------------------- | ----------------------------------------------------------------- |
|  | 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. |
{% hint style="info" %}
### Simple and immediate bounds
Given a set of n items of volume 
* No algorithm can use less than 
* No algorithm can use more than 
{% endhint %}
“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. |
### First fit
Place each item in the first bin that can contain it.
### Best fit
Place each item in the bin with the smallest empty space.
### Worst fit
Places each item in the used bin with the largest empty space, otherwise start a new bin.
### Next fit
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. |
## First Fit Decreasing
In this case, sorting tasks by decreasing execution times would allow for minimizing the number of bins.
## Some theoretical results
Theoretical results.
* Any online algorithm uses at least 4/3 times the optimal number of bins: 
* 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.
## Some utilization bounds
* 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)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://davidjosearaujo.gitbook.io/notes-miect/sistemas-operativos-e-de-tempo-real/multiprocessor-scheduling-v1.2/task-allocation.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.