Last updated
Identical Multicore Systems (all cores are equal).
WCET (upper bound) is known for any scenario.
Periodic or sporadic tasks.
Partitioned scheduling - Tasks are allocated a priori to a given core - individual queues.
Global scheduling - Tasks are allocated to cores at runtime - single queue.
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).
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.
Consider a Global Scheduler with RM policy and the task set below.
Is the system schedulable?
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!
+ 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
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.
Tasks are allowed to migrate, but only at jobs boundaries.
Some tasks are statically allocated to processors, others are split into chunks (subtasks) that are allocated to different processors.
A task can only migrate within a predefined subset of processors (cluster).
