1. Introduction

1.1 Terminology

• Task: A process in the Real Time environment
• Active Task: A task that can be executed by the CPU
• Ready Task: a task waiting in the queue, waiting for the CPU
• Running Task: A task that is currently executed by the CPU
• Scheduling Algorithm: Algorithm that defines the task execution order

1.2 Scheduling

Given a set of tasks J = {J₁, &dots;, J_n}, a schedule is an assignment of tasks to the processor so that each task is executed until completion.

Formally a schedule is:

s : ℝ⁺ → ℕ   such that   ∀ t ∈ ℝ⁺, ∃ t₁, t₂ ∈ ℝ⁺ | ∀ t' ∈ [t₁, t₂), s(t) = s(t')

1.3 Properties

• schedulability: A set of task is schedulable if there exists at least one algorithm that can produce a feasible schedule
• feasibility: A schedule is feasible if all task can be completed according to a set of specified constraints

1.4 Task Characterization

The tasks have different properties, that are used to schedule them, accordingly to the scheduling algorithm. Given the task J_i:

• Parameters
  • Arrival time a_i: the time at which the task is ready to be executed
  • Period time T_i: the recurring time at which the task is ready to be executed
  • Computation time C_i: the time needed to execute the task (with no interruption)
  • Deadline d_i: the time before which the task needs to conclude its execution
  • Start time s_i: the time at which the task is starts running
  • Finish time f_i: the time at which the task finished its execution
• Metrics
  • Response Time R_i = f_i - a_i: the interval of time from where the task is arrived to when the task finished its execution
  • Lateness L_i = f_i - d_i: the residual time between the execution conclusion and the deadline
  • Slack time X_i = d_i - a_i - C_i: maximum time a task can be delayed to complete within its deadline

1.5 Constraints

The feasibility constraints for the schedulability are:

• Timing: the task ends their execution before their deadline, the missed deadline is divided into three classes: Hard (cause catastrophic consequence) , Soft (cause performance degradation) or Firm (causes no harm, but the result is useless)
• Precedence: the tasks are executed following precedence rule
• Resource: the task can only access the available resource (those not locked by other tasks)

1.5.1 Task Activation

The task are infinite sequence of identical activities (instances)

• Time activation
  • Periodic Task: activated each period T_i
• Event activation
  • Aperiodic Task: activation is not known and can vary over time
  • Sporadic Task: is an aperiodic task than might activate again after a fixed inter-arrival time

1.5.2 Precedence Constraints

The execution order of the tasks has to respect a precedence relation, usually expressed with a Direct Access Graph (DAG) and are denoted as:

• Predecessor J_a < J_c: the task J_a is a predecessor of the task J_c
• Immediate predecessor J_a → J_b: the task J_a is a immediate predecessor of the task J_b

1.5.3 Resource Constraints

Resource access is particularly critical for Real Time OS, classical structure like semaphores can't be used

---

2. Scheduling Problem

The scheduling is a nondeterministic polynomial (NP) complete problem

2.1 Problem Definition

Given

• a set of tasks J = {J₁,...,J_n} with their constraints
• a set of processors P = {P₁,...,P_n}
• a set of resources R = {R₁,...,R_n}
• a set of precedence specified with a DAG

Scheduling is the process of assigning a processor P_j and resource R_k to a task J_i under their constraints

2.2 Scheduler Classification

Real-time scheduling disciplines are typically characterized by four primary design dimensions:

• Preemption strategy
  • Preemptive: the current task can be interrupted
  • Non-preemptive: once a task starts, it runs to completion without interruption
• Priority assignment
  • Static: priorities are assigned before activation
  • Dynamic: priorities can change during runtime
• Decision timing
  • Off-line: the schedule is pre-computed before the system start
  • On-line: the schedule is made at run time as the tasks arrive
• Optimality
  • Optimal: Guaranteed to find a feasible schedule if one exists
  • Heuristic: Uses rules of thumb for good enough results

2.3 Guaranteed Scheduling

Since Hard Real Time system require feasibility of the schedule, it must be guaranteed in advance. Given this we can define two type of scheduler:

• Static offline scheduling: Decisions are made at compile-time and requires almost no CPU overhead at runtime but offers zero flexibility
• Dynamic online scheduling: Decisions are made at run-time, feasibility is still guaranteed in advance by proving that in the worst case assumption, the mathematical properties of the algorithm ensure it

2.4 Scheduling Metrics

Scheduling metrics are essential tools used to evaluate, verify, and optimize the performance of a real-time system. While the primary goal of hard real-time systems is to ensure all deadlines are met, metrics provide the quantitative data needed to prove this will happen before the system even runs. Generally, a mix of those is used.

• Average response time: no information about deadline satisfaction
  t̅_r = (1/n) ∑_i=1ⁿ (f_i - a_i)
• Total completion time: no information about deadline satisfaction
  t_c = max_i(f_i) - min_i(a_i)
• Weighted sum of completion times:
  t_w = ∑_i=1ⁿ w_i f_i
• Maximum lateness: minimizing maximum lateness does not minimize the number of tasks that miss deadlines
  L_max = max_i(f_i - d_i)
• Maximum number of late tasks:
  N_late = ∑_i=1ⁿ miss(f_i)
  where miss(f_i) = 0 if f_i ≤ d_i, and 1 otherwise.

2.5 Scheduling Anomalies

Given a set of task with feasible scheduling, following the problem definition, the optimization of some of it's parameters (like increasing the number of processors, decreasing the computation time or weakening the precedence constraints) can produce an unfeasible scheduling, as Ronald L. Graham demonstrated in 1966

2.6 Problem Classification

To make the problem more tractable a classification is needed, where different algorithms solve different problems.

Ronald Graham, Eugene Lawler, Jan Karel Lenstra, and Alexander Rinnooy Kan proposed in 1979 a theoretical categorization of the scheduling algorithm, using the following three field annotation (α, β, γ)

• Machine environment (α): environment on which the task set has to be scheduled (usually the number of processors)
• Job description (β): task and resource characteristics (like preemption, precedence, synchronization, activation, ...)
• Objective criterion (γ): cost function to be optimized

---

3. Aperiodic Task Scheduling

Based on tasks Job description β: (synchronous or asynchronous activation, independent or precedence dependent, preemptive or non-preemptive), they can be solved with the following algorithms:

	sync. activation	preemptive async. activation	non-preemptive async. activation
independent	EDD (Jackson '55) O(n log n) Optimal	EDF (Horn '74) O(n2) Optimal	Tree search (Bratley '71) O(n · n!) Optimal
precedence constraints	LDF (Lawler '73) O(n2) Optimal	EDF* (Chetto et al. '90) O(n2) Optimal	Spring (Stankovic & Ramamritham '87) O(n2) Heuristic

3.1 EDD Algorithm

The EDD algorithm, invented by Jackson in 1955, solves 1|sync|L_max:

• Task set: J = {J_i (C_i,d_i) | i=1,...,n}
• Principle: Earliest Due Date (complexity O(n log n))
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: ∑_k=1ⁱ C_k < d_i, ∀ i = 1,...,n with task listed with increasing deadlines

where, in the three field notation

• α = 1: 1 processor
• β = sync: all tasks arrive at the same time (non-preemptive) and are implicitly independent (no precedence constraints nor shared resources)
• γ = L_max: minimize the number of late tasks

3.2 EDF Algorithm

The EDF algorithm, invented by Horn in 1974, solves 1|preem|L_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n}
• Principle: Earliest Deadline first (complexity O(n²))
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: ∑_k=1ⁱ c_k(t) < d_i, ∀ i = 1,...,n with task listed with increasing deadlines and c_i the remaining worst case execution time (WCET) of the task J_i

where, in the three field notation

• α = 1: 1 processor
• β = preem: tasks arrive at different time (preemptive),
• γ = L_max: minimize the number of late tasks and are implicitly independent (no precedence constraints nor shared resources)

3.3 LDF Algorithm

The LDF algorithm, invented by Lawler in 1973, solves 1|(prec,sync)|L_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n} with DAG constraints
• Principle: Latest Deadline first (complexity O(n²))
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: -

where, in the three field notation

• α = 1: 1 processor
• β = (prec,sync): all tasks arrive at the same time (non-preemptive) and are dependent, following the DAG
• γ = L_max: minimize the number of late tasks and are implicitly independent (no precedence constraints nor shared resources)

3.4 LDF* Algorithm

The EDF* algorithm, invented by Chetto in 1990, solves 1|(prec,sync)|L_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n} with DAG constraints
• Principle: Modified Latest Deadline first, change the tasks parameters and makes them independent by exploiting the DAG, given J_j → J_k:
  • task cannot start before its predecessors: a_j = max(a_j, a_k - C_k)
  • cannot preempt their successor: d_j = max(d_j, d_k - C_k)
  and then executes EDF
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: -

where, in the three field notation

• α = 1: 1 processor
• β = (prec,sync): all tasks arrive at the same time (non-preemptive) and are dependent, following the DAG
• γ = L_max: minimize the number of late tasks and are implicitly independent (no precedence constraints nor shared resources)

---

4. Periodic Task Scheduling

The periodic tasks are the majority of the task type usually executed in RTOS. Based on tasks Job description β, they can be solved with the following algorithms:

	di = Ti	di ≤ Ti
Static Priority	RMA Processor utilization approach ∑i=1n (Ci / Ti) ≤ n(21/n - 1)	DMA Response time approach ∀ i, Ri = Ci + ∑j ∈ hp(i) ⌈ Ri / Tj ⌉ Cj ≤ Di
Dynamic Priority	EDF Processor utilization approach ∑i=1n (Ci / Ti) ≤ 1	EDF Processor demand approach ∀ L > 0, L ≥ ∑i=1n (⌊ (L - Di) / Ti ⌋ + 1) Ci

4.1 Cyclic Executive Scheduling

Cyclic Executive Scheduling is a deterministic, time-triggered scheduling approach where tasks are executed in a fixed, repeating sequence called a major cycle. While being logically simple, might be difficult to construct (bin packing problem)

The tasks are mapped in a set of minor cycles, that than constitute the major cycle

4.2 Schedulability guarantee

The schedulability guarantee of the following algorithm is based on two different factors:

• processor utilization factor
• worst case response time factor

4.2.1 Processor utilization factor

Given a set of periodic task Γ, the utilization factor U is the fraction of processor time spent in the execution of the task set

U_Γ = ∑_i=1,...,n (C_i / T_i)

The schedulability test is sufficient, but not necessary:

• Schedulable: U_Γ ≤ U_lub(A)
• Maybe schedulable: U_Γ > U_lub(A)
• Not schedulable: U_Γ > 1

where U_lub(A) is the least upper bound of the utilization factor of a given algorithm A

U_lub(A) = min(U_lub(A, Γ)) ∀ Γ

4.2.2 Response time factor

The worst case response time analysis is sufficient and necessary condition to determine the schedulability of a task set.

R_i = C_i + I_i

where I_i = ∑_{j ∈ hp(i)} ⌈ R_i / T_j ⌉ C_j is the maximum interference that a task can experience.

Then the scheduling is granted if and only if R_i > d_i ∀ i.

4.3 RM Algorithm

The RM algorithm, invented by Liu and Layland in 1973, solves 1|fixed priority|∑ U_i:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n}
• Principle: Rate Monotonic, priorities are assigned according to request rates
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee:
  1. WCRT factor: R_i = C_i + I_i
  2. U factor: U_lub = ∑_i=1ⁿ (C_i / T_i) ≤ n(2^1/n - 1)

where, in the three field notation

• α = 1: 1 processor
• β = (priority): tasks have fixed priority (preemptive)
• γ = ∑ U_i: ensure that the process utilization is within the schedulable bound

4.4 Priority EDF Algorithm

The EDF priority based algorithm, invented by Liu and Layland in 1973, solves 1|dyn priority|C_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n}
• Principle: Earliest Deadline first where task with earlier deadline are assigned to higher priorities
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: U_lub = ∑_i=1ⁿ (C_i / T_i) ≤ 1 (necessary and sufficient)

where, in the three field notation

• α = 1: 1 processor
• β = (dyn priority): tasks have dynamic priority (preemptive)
• γ = C_max: minimizes the total computation time

4.5 DM Algorithm

The DM algorithm, invented by Leung and Whitehead in 1982, solves 1|(fixed priority, D_i ≤ T_i)|L_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n}
• Principle: Deadline Monotonic, priorities are assigned according to request rates
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: D_i ≥ C_i + I_i, with I_i maximum interference that a task can experience.

where, in the three field notation

• α = 1: 1 processor
• β = (priority): tasks have fixed priority (preemptive)
• γ = L_max: ensure that all the tasks meet their deadline

4.6 PDA EDF Algorithm

The Processor Demand Analysis EDF algorithm, invented by Baruah, Rosier and Howell in 1990, solves 1|dyn priority|C_max:

• Task set: J = {J_i (C_i,a_i,d_i) | i=1,...,n}
• Principle: Earliest Deadline first where task with earlier deadline are assigned to higher priorities
• Optimality: Optimal, no feasible schedule guarantee
• Schedulability guarantee: L ≥ ∑_i=1ⁿ (⌊ (L - D_i) / T_i ⌋ + 1) C_i ∀ L > 0, where L is the interval length

where, in the three field notation

• α = 1: 1 processor
• β = (dyn priority): tasks have dynamic priority (preemptive)
• γ = C_max: minimizes the total computation time

4.7 Comparison: RM vs EDF

---

5. Mixed Task Scheduling

Mixed-task scheduling deals with systems where different types of tasks (periodic, sporadic, and aperiodic) must coexist on the same processor without compromising the deadlines of the critical tasks.

There are three main different approach to handle mixed tasks:

• Immediate service: aperiodic requests are served as soon as arrived, postponing periodic tasks
• Background scheduling:
  • Periodic task: assigned to high priority queue and scheduled with RM
  • Aperiodic task: assigned to high priority queue and scheduled with FCFS (first come, first served)
• Aperiodic server (static or dynamic): uses a priority server that handles the aperiodic tasks as aperiodic ones

  

5.1 Static Priority Server

Static priority server insert aperiodic tasks in the ready queue, mixing with periodic tasks, then apply RM as for periodic tasks.

There are different type of static priority server:

• Polling Server
• Deferrable Server
• Priority Exchange
• Sporadic Server
• Slack Stealing

5.1.1 Polling Server

The aperiodic tasks accumulate in the queue and at the start of the priority server period, it sets its capacity C_s to maximum, then

• Aperiodic task pending: the server loads the aperiodic tasks to maximum its capacity C_s (the capacity might be not fully used)
• Aperiodic task queue empty: the server loads no aperiodic tasks and discharge its capacity to 0

The schedulability analysis is computed using the Utilization Factor (PS+RM):
U_ps ≤ n [ (2 / (U_s + 1))^1/n - 1 ]

5.1.2 Deferrable Server

The deferrable server is similar to the polling server, but handles the capacity discharge differently: as soon as an aperiodic tasks arrived, it is immediately moved to the priority server, until it hits the maximum capacity.

The schedulability analysis is computed using the Utilization Factor (DS+RM):
U_ds ≤ n [ ((U_s + 2) / (2U_s + 1))^1/n - 1 ]

5.1.3 PS and DS comparison

By analyzing their utilization factor, we can find out that:

• Invasive behavior of the DS causes lower schedulability bound for periodic tasks
• DS is more responsive than PS but decreases the utilization bound

5.2 Dynamic Priority Server

Dynamic priority server adapts the static priority server approach using EDF:

• the deadline of the aperiodic tasks is assigned in order to not exceed the given bandwidth U_s: d_k = max(r_k, d_k-1) + C_k / U_s
• the periodic and aperiodic tasks are mixed and scheduled with EDF

There are different type of static priority server:

• Dynamic polling server
• Dynamic deferrable server
• Dynamic sporadic server
• Total bandwidth server
• Constant bandwidth server

5.2.1 Total Bandwidth Server

The schedulability analysis is computed using the Utilization Factor (TBS+EDF):
U_p + U_s < 1