Task Scheduling Basics

Embedded Systems Design

Dr. M Faisal Iqbal

Embedded System Design 1

Last Lecture
• Introduction to task synchronization
• Producer consumer problem
• Too much milk problem
• Peterson’s solution
• Task synchronization using locks
• Test & set instruction
• Efficient use of test and set is important
• Test & set without busy waiting
• Test & Test & set

Embedded System Design 2

Tasks and Resources
• The unit of computation is a task
• A processor executes a task
• When a task is scheduled it is placed on the timeline based on the
decision of the scheduler

Task1 Task2

Embedded System Design 3

General Task Structure
A c-style function
void task1(){
Int a;
While(1){ Basic Block
a = read_sensor();
a = a * 2; Functionality
sleep(1000);
} Period

Embedded System Design 4

Tasks and Jobs
• Any instance of a task is called a Job
• A new job is created every iteration of the loop
• A job is represented by letter J followed by two numbers
• First number tells which task does the job belong to
• Second number tells the iteration of the task

Task 1 J1.1 J1.2 … J1.n

Embedded System Design 5

Periodic Tasks
• One job is created every x-time units
• Release time: Time at which a job is ready for execution
• At this time the task will start to create jobs which will request access to the
CPU
• Period (P): It is the period between releases of jobs in a task
• Execution Time (E) : time to execute a job.
• Simply speaking how long the box is
• Deadline (D): The latest time at which a task must be finished
• Absolute deadline: Relative to time 0
• Relative deadline: relative to the last release of the job
• In case no deadline is given, it is assumed that relative deadline is the task period

Embedded System Design 6

A successful schedule
T1 T1 R1 = 0 P1 = 3 E1 = 1 D1 = 4
T2 R2 = 1 P2 = 10 E2 = 2 D2 = 9
T2
T3 R3 = 5 P3 = 5 E3 = 0.5 D3 =2
T3

R1 R2 D1 R3 D3 D2

T1 T2 T1 T3 T1 T1

Embedded System Design 7

 Further Terminology
• Feasibility Interval: Between release time & deadline [r,d]
• Phase: Shifted release time of the first job in each task, φ
• Jitter: Maximal span of uncertainty in release time [r+, r-]

R1 D1
Phase = 1.0

T1

Embedded System Design 8

Hyper Period
• Schedule on a time line makes a pattern
• Hyperperiod (H) is the period where the pattern starts to reappear
• At H all jobs are schedules the same way as time = 0

Embedded System Design 9

Hyperperiod
• Calculated as Least Common Multiple (LCM) of individual periods
• Example: P1 = 3, P2 = 4, P3 = 10
• 3: 3, 6, 9, 12, …. , 51, 54, 57, 60
• 4: 4, 8, 12, 16, … , 52, 56, 60
• 10: 10, 20, 30, 40, 50, 60

Embedded System Design 10

Types of Real-time System
• Hard Real-time Systems
• Cannot miss any deadline, otherwise system will produce useless results
• Examples:
• ABS Breaks, Airbag systems, emergency breaks in elevators and trains

• Soft Real-time System

• Some deadlines can be missed, however quality of product decreases with
more missed deadlines
• Soft deadlines are often specified in the probabilistic terms
• Examples:
• Cell phone network: call should be put through in no more than 10 seconds for 95
percent of the time and in no more than 20 seconds for 99.95 percent of the time
• Multimedia system: user are often willing to tolerate a few glitches in the video streams

Embedded System Design 11

Task States
Suspend
Suspended called

resume Suspend
called called

Ready Running
Scheduled
Suspend
called Event e.g.,
Delay runs out

Blocking
Blocked API Called
e.g., delay()

This is the state transition diagram in FreeRTOS

Embedded System Design 12
Real-time Task Scheduling
• Feasible schedule: A schedule that never misses a deadline
• Schedulable Tasks: A set of tasks is schedulable if there exists at least
one scheduling algorithm that can generate a feasible schedule
• Optimal Algorithm: A scheduling algorithm is optimal if it always
produces a feasible schedule for a set of schedulable tasks

Embedded System Design 13

Scheduling Example
T1

D1 D2 D3 T3

T
2
Infeasible

feasible
T
T1 T3
2

Embedded System Design 14

Precedence Graph
• Precedence constraints are given as a relation of precedence, <, over
a set of jobs {Ji}: J < J’
• J’ is dependent on J
• J should be scheduled before J’
• Example

T1 T4 T5

T2

T3

Embedded System Design 15

Preemptive Vs Non-Preemptive Schedulers
• Preemptive: The execution of a job can be interrupted & continue at a
later stage
• Non-Premptive: Jobs continue for complete execution time
• Example: Two jobs
• T1:e1=1, p1=2, high priority
• T2: e2=2, p2 = 10, lower priority
T1
T2 not finished yet but
T1 has higher priority
T2
T2 T1 T2 T1

Embedded System Design 16

What actually happens at preemption?

Scheduled

Scheduled
PSR

PC 0x00041

SP 0x0085D

Task 1 GPREG Task 2

R0: 0x00
MOV R1,0x01 R1: 0x00
0x01 LDR R2, [R1]
Execute R2:0x00
ADD R1, R2, R3 MOV R1,0x02
R3:0xff
R4:0xff
…
Embedded System Design 17
Context Switch Procedure
• The complete context switch procedure

Timer

Task 1

Task 2

Embedded System Design 18

Context Switch Overhead
• Switching between thread has some overhead
• Saving and loading context
• Deciding which task to execute next
• Must be taken into account when scheduling for real time systems

Embedded System Design 19

Comparison by Example
• 8 Jobs: J1, J2, …, J8 (lower index has higher priority)
• J5 is released at t4 and all others at t= 0
J1

J2 J3 J4

J5 J6

J7 J8
J1 J4 J7 J6

J2 J3 J7 J5 J8

Embedded System Design 20

Non-preemptive scheduler
• 8 Jobs: J1, J2, …, J8 (lower index has higher priority)
• J5 is released at t4 and all others at t= 0
J1

J2 J3 J4

J5 J6

J7 J8
J1 J4 J5 J6

J2 J3 J7 J8

Embedded System Design 21

Static Scheduling
• Simple, Predictable
• Static schedule is stored in a table as a pair (t,T)
• t = scheduling time
• T = Task or a hole (hole is absence of a task)
• Scheduler accesses this time table to schedule tasks

Embedded System Design 22

 Utilization
• A simple way to check if there is a feasible schedule for the set of task
𝑒𝑖
• System Utilization: 𝑢 = 𝛴
𝑃𝑖
• If u > 1, the system is not feasible
• Utilization Example
P E D
T1 3 1 3 1 1 1
𝑢 = + + = 0.78
T2 4 1 4 3 4 5
T3 10 2 10

Embedded System Design 23

Components of a Scheduler
Heap Memory

Timer
Task Memory Task Memory

• Timer expires at the scheduling point

• Job from task T is scheduled at time t
• OS sets the timer to expire at the next scheduling point
• Next scheduling point is determined by the static scheduler

Embedded System Design 24

Pseudo-code for a static scheduler

Embedded System Design 25

 Static scheduling example
• Schedule is created offline
• Precedence constraints are treated explicitly
• Scheduler only decides when a timer expires

Time (t) Task (T)

0 T1
1 T3
T
3 T2 T1 T3 T2 T5
5
5 T4
7.5 t5

Embedded System Design 26