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).