EECE 276

Embedded Systems
RTOS Basics
Process scheduling

EECE 276 – Embedded Systems RTOS Basics 1

 RTOS Basics
O Kernel: schedules tasks
O Tasks: concurrent activity with its own state
(PC, registers,stack, etc.)

TASK TASK TASK

ISR1

Code Code Code

TASK3
Data Data Data
TASK2

TASK1
ITs
RTOS
Time
HW

EECE 276 – Embedded Systems RTOS Basics 2

 Tasks
O Tasks = Code + Data + State (context)
O Task State is stored in a Task Control Block
(TCB) when the task is not running on the
processor
O Typical TCB: The RTOS effectively
multiplexes the CPU among
ID the tasks
Priority
Status TCB RTOS
Registers TCB CPU
TCB
Saved PC
Saved SP

EECE 276 – Embedded Systems RTOS Basics 3

 Task states
O Executing: running on the CPU
O Ready: could run but another one is using the
CPU
O Blocked: waits for something (I/O, signal,
resource, etc.)
O Dormant: created but not executing yet

O Terminated: no longer active

The RTOS implements a Finite State Machine

for each task, and manages its transitions.

EECE 276 – Embedded Systems RTOS Basics 4

 Task State Transitions
Task created

Dormant

Task active
Task activated Task scheduled
Task releases Executing
Ready processor/time-
slice exhausted
Task waits for
Task terminates
Event arrives event (I/O,
resource)
Blocked Event arrives

Task terminated
Terminated

EECE 276 – Embedded Systems RTOS Basics 5

 RTOS Scheduler
O Implements task state machine
O Switches between tasks
O Context switch algorithm:
1. Save current context into current TCB
2. Find new TCB
3. Restore context from new TCB
4. Continue
O Switch between EXECUTING -> READY:
1. Task yields processor voluntarily: NON-PREEMPTIVE
2. RTOS switches because of a higher-priority task/event:
PREEMPTIVE

EECE 276 – Embedded Systems RTOS Basics 6

 RTOS Tasks
O Run in the same memory space
O Can share data
» Data sharing problems as before!
» Cannot simply disable IT-s (this would stop the
RTOS!)
O Can share code – Similar problems
void task1() { … vCountErr(9); … }
void task2() { … vCountErr(10); …}
static int cErrors;
void vCountError(int addErr) {
cErrors += addErr; Not an atomic
} operation

EECE 276 – Embedded Systems RTOS Basics 7

 RTOS Tasks: Code sharing
O Reentrancy: A function is called reentrant if it
can be entered simultaneously, by multiple
tasks.
O Rules: A reentrant function
» May not use variables in a non-atomic way (unless
local variables or private variables of the calling
task)
» May not call other, non-reentrant functions
» May not use the HW in a non-atomic way

EECE 276 – Embedded Systems RTOS Basics 8

 Process scheduling
O Goal: to satisfy timing requirements
O Pre-run-time (static) scheduling: determine
precise task schedules at design-time.
» Ex: TTA
O Run-time (dynamic) scheduling: scheduling is
done dynamically, by the RTOS, based on
priorities.

EECE 276 – Embedded Systems RTOS Basics 9

 Task attributes (1)
A task model (periodic tasks):
O Precedence constraints: specify if any task(s) must
precede other tasks.
O Release (arrival) time - r(i,j): The release time of the j-
th instance of the i-th task
O Phase: Φ(i): The release time of the first instance of
the i-th task.
O Response time: Time span between task activation
and its completion
O Absolute deadline - d(i,j): The instant by which the j-
th instance of the i-th task must complete
O Relative deadline – D(i): The maximum allowable
response time for the task

EECE 276 – Embedded Systems RTOS Basics 10

 Task attributes (2)
O Laxity type: Notion of urgency or leeway in a
task’s execution
O Period - p(i): The minimum length of intervals
between the release times of consecutive
tasks.
O Execution time – e(i): The (maximum)
amount of time required to complete the
execution of the i-th task when it executes
alone and has all the resources it requires.

EECE 276 – Embedded Systems RTOS Basics 11

 Task model
Some basic identities:
O Φ(i) = r(i,1) // First release time
O r(i,k) = Φ(i) + (k-1) * p(i) // Periodic tasks

O d(i,j) = Φ(i) + (j-1) * p(i) + D(i) // Abs. Deadline

O If D(i) == p(i) then

d(i,k) = r(i,k) + p(i) = Φ(i) + k * p(i)

EECE 276 – Embedded Systems RTOS Basics 12

 Task model
Simple task model:
O All tasks are strictly periodic.

O The relative deadline of a task is equal to its period.

O All tasks are independent – no precedence

constraints
O No tasks have non-preemptible sections – cost of

preemption is negligible
O Only processing requirements count – memory and

I/O requirements are negligible.

EECE 276 – Embedded Systems RTOS Basics 13

 Scheduling techniques
O Round-robin scheduling:
» Each task is assigned a fixed time quantum (slice).
» Fixed-rate timer generates a periodic IT. Rate is
equal to the slice
» Task runs until completion or slice expiration
» If task does not complete, it is placed at the end of
a queue of executable (“ready”) tasks.
- Fair scheduling
- All tasks have the same priority

EECE 276 – Embedded Systems RTOS Basics 14

 Scheduling techniques
O Cyclic executive:
» Schedule consists of (pre-run-time scheduled)
frames. A sequence of frames in which all tasks
execute, all deadlines and periods are satisfied is
called a hyperperiod (‘major cycle’). It’s length is
lcm(p(i)) over all i-s.

EECE 276 – Embedded Systems RTOS Basics 15

 Scheduling techniques
O Cyclic executive:
» A frame (f) is long enough s.t. every task can start
and complete within the frame – No preemption
within the frame.
» Scheduler makes scheduling decisions only at the
beginning of each frame.
– Cond #1: f >= max(e(i)) : “Frame is long enough”.
– Cond #2: floor(p(i)/f) – p(i)/f = 0: “Hyperperiod has integer
number of frames”
– Cond #3: 2*f – gcd(p(i),f) < D(i) : “There is at least one
frame between the release time and deadline of each
task.”

EECE 276 – Embedded Systems RTOS Basics 16

 Scheduling techniques
O Fixed priority – Rate Monotonic Scheduling
Given a set of periodic tasks and a preemptive priority
scheduling, then assigning priorities s.t. tasks with the shorter
periods have higher priorities (rate-monotonic), yields a feasible
scheduling algorithm. (RM Rule).
Utilization: u(i) = e(i)/p(i)
A set of N periodic,independent tasksl
is RM-schedulable [Liu73] if
N →∞

N
U= ∑i =1
u (i ) ≤ N * (21/ N − 1)

Note: If N -> infinity lim () = ln2 ~ 0.69.

EECE 276 – Embedded Systems RTOS Basics 17

 Scheduling techniques
O Dynamic priority – Earliest Deadline First
Scheduling: The ready task with the earliest
deadline has the highest priority.
O EDF Bound theorem:
A set of N tasks, each of whose relative deadline
equals to its period, can be feasibly scheduled by
EDF if and only if N
∑ (e(i) / p(i)) ≤ 1
i =1

EDF is optimal for a single processor (with

preemption allowed)

EECE 276 – Embedded Systems RTOS Basics 18