Scheduling for Multicore Platforms
Assumptions
Identical Multicore Systems (all cores are equal).
WCET (upper bound) is known for any scenario.
Periodic or sporadic tasks.
Main approaches:
Partitioned scheduling - Tasks are allocated a priori to a given core - individual queues.
Global scheduling - Tasks are allocated to cores at runtime - single queue.
Partitioned scheduling
Each processor has an independent ready queue.
The processor for each task is determined a priori.
Tasks cannot migrate.
The scheduling problem reduces to:
Bin-packing problem, for allocating tasks to processors.
NP-hard in the strong sense.
Several heuristics:FirstFit, NextFit, BestFit, etc.
Uniprocessor scheduling problem (already studied and well known).
Global scheduling
The system manages a single queue of ready tasks.
The processor is determined at run time.
During execution, a task can migrate to another processor.
Example
Consider a Global Scheduler with RM policy and the task set below.
Is the system schedulable?
Evaluation
Dhall’s effect: Global RM and Global EDF produce unfeasible schedules for task set utilizations arbitrarily close to 1.
m processors and m+1 tasks.
But Partitioned Scheduling allows to schedule such system with just 2 processors!
There are examples of task sets that one of the methods can schedule while the other cannot!
Global vs Partitioned Scheduling
| Global | Partitioned |
|---|---|
+ Automatic load balancing | + Supported by automotive industry (e.g., AUTOSAR) |
+ Lower avg. response time | + No migrations |
+ Easier re-scheduling | + Isolation between cores |
+ More efficient reclaiming and overload management | + Mature scheduling framework |
+ Lower number of preemptions | + Low scheduling overhead (no need to access a global ready queue) |
- Migration costs | - Cannot exploit unused capacity |
- Inter-core synchronization | - Rescheduling not convenient |
- Loss of cache affinity | - NP-hard allocation problem |
- Weak scheduling framework |
Hybrid approaches
Task/job migration can be costly.
contex must be moved, impact on cache, etc.
There are other types of partitioning that consider restrictions on task migration.
Job migration
Tasks are allowed to migrate, but only at jobs boundaries.
Semi-partitioned scheduling
Some tasks are statically allocated to processors, others are split into chunks (subtasks) that are allocated to different processors.
Clustered scheduling
A task can only migrate within a predefined subset of processors (cluster).
Last updated
