Multiprocessor Scheduling

SMP Schedulability Analysis

• multiprocessors, including multi-core becoming more common
• schedulability theory not well developed, relative to single processor
  • core result for single processor, on "critical instants", does not apply
• traditional method: partitioned scheduling (queue per processor)
  • apply single-processor scheduling on each CPU
  • optimal partitioning is NP-hard
    (See notes on complexity of scheduling for other NP-hard scheduling problems.)
  • first-fit comes within 50% of optimal, usually much better
  • worst case: breakdown at 50% of optimal processor utilization
• global (single queue) scheduling
  • originally deprecated, due to Dhall effect (see below)
  • recently shown to be competitive with partitioning
  • interactions with memory cache are subject to hot debate

``Dhall Effect'' with EDF/DM Scheduling on MP

Observe: This is only a problem when we have some tasks with very high local utilization.

Dhall's example shows worst-case achievable multiprocessor utilization can be arbitrarily close to 1, compared to ideal value of m.

Until recently, it was used as an excuse for using partitioned scheduling on multiprocessors.

However, the example depends on mixing tasks with extremely low and extremely high utilization (or ratio of compute time to deadline).

Intuitively, we know we can achieve higher utilization when we have only smaller tasks.

Global Schedulability Test - Basic Idea

Load-Based Schedulabity Analysis

1. Find a lower bound μ on the load of a window leading up to a deadline that is necessary for the deadline to be missed.

2. Find an upper bound β on the load of such a window that can be generated by a given task set.

3. If β < μ the task set must be schedulable.

There are several variations as to how we define "load" that allow different refinements in analysis.

Generalized EDF Density Test

A system of n independent sporadic tasks can be scheduled to meet all deadlines on m processors using preemptive global EDF scheduling if (but not necessarily only if)

where

• λ_i = e_i / min (p_i, d_i)
• λ_max = max { λ₁, ..., λ_n }
• λ_sum = λ₁ + ... + λ_n

Generalized Fixed-Priority Density Test (Baker & Cirinei)

A system of N independent sporadic tasks can be scheduled to meet all deadlines on M processors using preemptive global fixed task-priority scheduling if (but not necessarily only if), for every task τ_k there exists λ≥λ_k such that one of the following criteria is satisfied

where

This is one of several results, which have gradually provided better techniques for verifying schedulability of task systems on multiprocessors.

Unfortunately, they do not cover all the cases. When it comes to evaluating how well they do, we look at performance in simulations on large numbers of task sets.

Experiment with BC Test for DM Scheduilng on 4 CPUs

The graph shows how many of 1,000,000 randomly generated sporadic task sets could be proven schedulable by deadline-monotonic scheduling using the Baker-Cirinei fixed-priority schedulability test above.

How many of the task sets that could not be proven schedulable are not schedulable?

How many of the task sets that could not be proven schedulable are schedulable, but just not able to be proven schedulable using the BC test?

How many of them are not feasible, i.e., not schedulable by any method at all?

Hierarchy of Possibilities for a Task Set

1. schedulable to meet all deadlines by given method
   • proven schedulable by a given test
   • schedulable, but not proven
2. feasible (there exists a schedule that meets deadlines) but not schedulable by given method
   • proven feasible (how?)
   • feasible, but not proven
3. infeasible (there is an arrival sequence for which no schedule can meet all deadlines)
   • infeasible, but not proven
   • proven infeasible

Throwforward Demand Bound

The following function is a useful measure of competing processor demand for proving that a task set is not feasible.

where