Overall Stucture of Computer Systems

Application Application Application

Todays topic: RTOS Program Program Program

OS User Interface/Shell, Windows

Filesystem and Disk management

OS kernel
Hardware
1 2

Why OS? Operating System Provides

Environment for executing programs
To run a single program is easy
What to do when several programs run in parallel? Support for multitasking/concurrency
Memory areas Hardware abstraction layer (device drivers)
Program counters
Scheduling (e.g. one instruction each) Mechanisms for Synchronization/Communication
....
Filesystems/Stable storage


Communication/synchronization/semaphors
Device drivers
OS is a program offering the common services needed in all applications
(e.g. Eneas OSE kernel)
We will focus on concurrence and real-time issues
First, a little history

Batch Operating Systems Timesharing Operating Systems

Original computers ran in batch mode: Solution

Submit job & its input Store multiple batch jobs in memory at once
Job runs to completion When one is waiting for the tape, run the other one
Collect output
Submit next job Basic idea of timesharing systems

Processor cycles very expensive at the time Fairness, primary goal of timesharing schedulers
Jobs involved reading, writing data to/from tapes Let no one process consume all the resources
Cycles were being spent waiting for the tape! Make sure every process gets equal running time

1
Real-Time Is Not Fair Do We Need OS for RTS?
Main goal of an RTOS scheduler: Not always
meeting timing constraints e.g. deadlines Simplest approach: cyclic executive
If you have five homework assignments and only one
is due in an hour, you work on that one loop
Fairness does not help you meet deadlines do part of task 1
do part of task 2
do part of task 3
end loop

Cyclic Executive Real-Time Systems and OS

Advantages We need an OS
Simple implementation For convenience
Low overhead Multitasking and threads
Very predictable Cheaper to develop large RT systems
But - dont want to loose ability to meet deadlines
Disadvantages (timing and resource constraints in general)
Cant handle sporadic events (e.g. interrupt) This is why RTOS comes into the picture
Everything must operate in lockstep
Code must be scheduled manually

Requirements on RTOS Basic functions of OS kernel

Determinism Process mangement

Memory management
Responsiveness (quoted by vendors)

Interrupt handling
Fast process/thread switch
Exception handling
Fast interrupt response
Process Synchronization (IPC)
User control over OS policies
Process schedulling
Mainly scheduling, many priority levels
Memory support (especially embedded)
Reliability

12

2
Process, Thread and Task Basic functions of RTOS kernel

A process is a program in execution. Task mangement

Interrupt handling
A thread is a lightweight process, in the sense that different
threads share the same address space, with all code, data, Memory management
process status in the main memory, which gives Shorter creation no virtual memory for hard RT tasks
and context switch times, and faster IPC
Exception handling (important)
Tasks are implemented as threads in RTOS. Task synchronization
Avoid priority inversion
Task scheduling
Time management

13 14

Micro-kernel architecture Basic functions of RTOS kernel

External System Hardware/software Clock

interrupts calls exceptions interrupts Task mangement
Interrupt handling
Case of Exception handling Memory management
Immediate
Interrupt Create task Time services Exception handling
services Suspend task Task synchronization
Terminate task
. Task scheduling
.
.
Create timer Time management
Sleep-timer
.
.
Timer-notify
.
Other system calls
Kernel
Scheduling
15 16

Task: basic notion in RTOS Typical RTOS Task Model

Task = thread (lightweight process) Each task a triplet: (execution time, period, deadline)
Usually, deadline = period
A sequential program in execution


Can be initiated any time during the period
It may communicate with other tasks
It may use system resources such as memory blocks Execution
Initiation Deadline
We may have timing constraints for tasks time

Time

Period

17

3
 Example: Fly-by-wire Avionics:
Task Classification (1) Hard real-time system with multi-rate tasks

Control laws Actuating Actuators

Periodic tasks: arriving at fixed frequency, can be Sensors Signal
Conditioning
characterized by 3 parameters (C,D,T) where
Aileron 1
C = computing time gyros, INU 1 kHz
Aileron
accel. 1kHz Pitch control
D = deadline 500 Hz

T = period (e.g. 20ms, or 50HZ) Aileron 2

GPS Aileron
GPS 1 kHz
Often D=T, but it can be D<T or D>T 20 Hz
Lateral Control
250 Hz
Air Air data Elevator
Elevator
Also called Time-driven tasks, their activations are Sensor 1 kHz 1 kHz

generated by timers Throttle Control

Joystick 250 Hz Rudder
Stick 500 Hz Rudder
1 kHz

19

Task Classification (2) Task states (1)

Non-Periodic or aperiodic tasks = all tasks that are Ready

not periodic, also known as Event-driven, their
activations may be generated by external interrupts Running
Waiting/blocked/suspended ...
Sporadic tasks = aperiodic tasks with minimum
interarrival time Tmin (often with hard deadline) Idling
worst case = periodic tasks with period Tmin Terminated

21 22

Task states (2) Task states (Ada, delay)

Idling
timeout delay

preemption preemption
Activate Terminate Activate Terminate
Ready Dispatch
Runnig Ready Dispatch
Runnig

signal wait signal wait

Blocked Blocked

23 24

4
 Task states (Ada95) TCB (Task Control Block)

Id
Task state (e.g. Idling)
Task type (hard, soft, background ...)

declared Idling Priority

timeout Sleep Other Task parameters
period
preemption comuting time (if available)
Activate

created Terminate
Ready Dispatch
Runnig Relative deadline
Absolute deadline
Context pointer
Pointer to program code, data area, stack
signal wait
Pointer to resources (semaphors etc)
Blocked Pointer to other TCBs (preceding, next, waiting queues etc)

25 26

Basic functions of RT OS Task managment

Task mangement Task creation: create a newTCB

Interrupt handling Task termination: remove the TCB
Memory management Change Priority: modify the TCB
Exception handling ...
Task synchronization
State-inquiry: read the TCB


Task scheduling
Time management

27 28

Task mangement Basic functions of RT OS

Challenges for an RTOS Task mangement

Creating an RT task, it has to get the memory without delay: this is Interrupt handling
difficult because memory has to be allocated and a lot of data Memory management
structures, code seqment must be copied/initialized
Exception handling
The memory blocks for RT tasks must be locked in main memoery Task synchronization
to avoid access latencies due to swapping Task scheduling
Time management
Changing run-time priorities is dangerous: it may change the run-
time behaviour and predictability of the whole system

29 30

5
Interrupts Handling an Interrupt
1. Normal program
Interrupt: environmental event that demands attention execution
Example: byte arrived interrupt on serial channel 3. Processor state
saved 4. Interrupt routine
2. Interrupt runs
Interrupt routine: piece of code executed in response to an
occurs
interrupt

6. Processor state
restored
5. Interrupt routine
terminates
7. Normal
program
execution
resumes

Interrupt Service Routines Interrupt Handling

Types of interrupts
Most interrupt routines:

Asynchronous (or hardware interrupt) by hardware event (timer, network card ) the
interrupt handler as a separated task in a different context.
Synchronous (or software interrupt, or a trap) by software instruction (swi in ARM, int
Copy peripheral data into a buffer in Intel 80x86), a divide by zero, a memory segmentation fault, etc. The interrupt
handler runs in the context of the interrupting task
Indicate to other code that data has arrived Interrupt latency
Acknowledge the interrupt (tell hardware) The time delay between the arrival of interrupt and the start of corresponding ISR.
Modern processors with multiple levels of caches and instruction pipelines that need to
be reset before ISR can start might result in longer latency.
The ISR of a lower-priority interrupt may be blocked by the ISR of a high-priority
Longer reaction to interrupt performed outside interrupt routine

E.g., causes a process to start or resume running

34

Basic functions of RT OS Memory Management/Protection

Task mangement Standard methods

Interrupt handling Block-based, Paging, hardware mapping for protection
No virtual memory for hard RT tasks
Memory management

Lock all pages in main memory
Exception handling Many embedded RTS do not have memory protection tasks
Task synchronization may access any blocks Hope that the whole design is proven
Task scheduling correct and protection is unneccessary
Time management to achive predictable timing
to avoid time overheads
Most commercial RTOS provide memory protection as an option
Run into fail-safe mode if an illegal access trap occurs
Useful for complex reconfigurable systems

35 36

6
Basic functions of RT OS Exception handling

Task mangement Exceptions e.g missing deadline, running out of

Interrupt handling memory, timeouts, deadlocks
Memory management Error at system level, e.g. deadlock
Error at task level, e.g. timeout
Exception handling

Standard techniques:
Task synchronization System calls with error code
Task scheduling Watch dog
Time management Fault-tolerance (later)
However, difficult to know all senarios
Missing one possible case may result in disaster
This is one reason why we need Modelling and Verification

37 38

Watch-dog Example

A task, that runs (with high priority) in parallel with all others Watch-dog (to monitor whether the application task is alive)
If some condition becomes true, it should react ... Loop
Loop if flag==1 then
begin {
.... next :=system_time;
end flag :=0
until condition }
The condition can be an external event, or some flags else if system_time> next+20s then WARNING;
sleep(100ms)
Normally it is a timeout
end loop
Application-task
flag:=1 ... ... computing something ... ... flag:=1 ..... flag:=1 ....

39 40

Basic functions of RT OS Task Synchronization

Task mangement Synchronization primitives

Interrupt handling Semaphore: counting semaphore and binary semaphore
A semaphore is created with initial_count, which is the number of allowed holders
Memory management of the semaphore lock. (initial_count=1: binary sem)
Sem_wait will decrease the count; while sem_signal will increase it.
Exception handling A task can get the semaphore when the count > 0; otherwise, block on it.
Mutex: similar to a binary semaphore, but mutex has an owner.
Task synchronization

a semaphore can be waited for and signaled by any task,
while only the task that has taken a mutex is allowed to release it.
Time management Spinlock: lock mechanism for multi-processor systems,
A task wanting to get spinlock has to get a lock shared by all processors.
CPU scheduling Read/write locks: protect from concurrent write, while allow concurrent
read
Many tasks can get a read lock; but only one task can get a write lock.
Before a task gets the write lock, all read locks have to be released.
Barrier: to synchronize a lot of tasks,
they should wait until all of them have reached a certain barrier.

41 42

7
Task Synchronization IPC: Data exchanging

Challenges for RTOS

Semaphore
Critical section (data, service, code) protected by lock
mechanism e.g. Semaphore etc. In a RTOS, the maximum time a Shared variables
task can be delayed because of locks held by other tasks should be
less than its timing constraints. Bounded buffers
Race condition deadlock, livelock, starvation Some FIFO
deadlock avoidance/prevention algorithms are too complicate and
indeterministic for real-time execution. Simplicity is preferred, like Mailbox
all tasks always take locks in the same order. Message passing
allow each task to hold only one resource.
Priority inversion using priority-based task scheduling and Signal
locking primitives should know the priority inversion danger: a
medium-priority job runs while a highpriority task is ready to Semaphore is the most primitive and widely used construct for
proceed. Synchronization and communicatioin in all operating systems

43 44

Semaphore, Dijkstra 60s Implementation of Semaphores: SCB

A semaphore is a simple data structure with SCB: Semaphores Control Block

a counter
the number of resources
Counter
binary semaphore
a queue Queue of TCBs (tasks waiting)
Tasks waiting Pointer to next SCB

and two operations:

The queue should be sorted by priorities (Why not FIFO?)

P(S): get or wait for semaphore

V(S): release semaphore

45 46

Implementation of semaphores: P-operation Implementation of Semaphores: V-operation

P(scb): V(scb):
Disable-interrupt; Disable-interrupt;
If scb.counter>0 then If not-empty(scb.queue) then
scb.counter - -1; tcb := get-first(scb.queue);
end then tcb.state := ready;
else insert(tcb, ready-queue);
save-context(); save-context();
current-tcb.state := blocked; schedule(); /* dispatch invoked*/
insert(current-tcb, scb.queue); load-context();
dispatch(); end then
load-context(); else scb.counter ++1;
end else end else
Enable-interrupt Enable-interrupt

47 48

8
Advantages with semaphores Exercise/Questions

Simple (to implement and use) Implement Mailbox by semaphore

Send(mbox, receiver, msg)
Exists in most (all?) operating systems

Get-msg(mbox,receiver,msg)
It can be used to implement other How to implement hand-shaking communication?
synchronization tools V(S1)P(S2)
Monitors, protected data type, bounded buffers, V(S2)P(S1)
mailbox etc Solve the read-write problem
(e.g max 10 readers, and at most 1 writer at a time)

49 50

Disadvantages (problems) with semaphores Priority inversion problem

Deadlocks Assume 3 tasks: A, B, C with priorities Ap<Bp<Cp

Assume semaphore: S shared by A and C
Loss of mutual exclusion The following may happen:
Blocking tasks with higher priorities (e.g. FIFO) A gets S by P(S)
Priority inversion ! C wants S by P(S) and blocked
B is released and preempts A
Now B can run for a long long period .....
A is blocked by B, and C is blocked by A
So C is blocked by B
The above senario is called priority inversion
It can be much worse if there are more tasks with priorities in
between Bp and Cp, that may block C as B does!

51 52

Solution? Resource Access Protocols

Task A with low priority holds S that task C with highest Highest Priority Inheritance
priority is waiting. Non preemption protocol (NPP)
Tast A can not be forced to give up S, but A can be Basic Priority Inheritance Protocol (BIP)
preempted by B because B has higher priority and can run POSIX (RT OS standard) mutexes
without S
Priority Ceiling Protocols (PCP)
So the problem is that A can be preempted by B Immedate Priority Inheritance
Highest Lockers priority Protocol (HLP)
Ada95 (protected object) and POSIX mutexes
Solution 1: no preemption (an easy fix) within CS sections
Solution 2: high As priority when it gets a semaphore shared
with a task with higher priority! So that A can run until it
release S and then gets back its own priority

53 54

9
Basic functions of RT OS Task states

Task mangement
Interrupt handling
Memory management
Idling
Exception handling timeout delay
Task synchronization preemption
Activate Terminate
Task scheduling Ready Dispatch
Runnig
Time management
signal wait

Blocked

55 56

Priority-based Scheduling Scheduling algorithms

Sort the READY queue acording to

Typical RTOS based on fixed-priority Priorities (HPF)
preemptive scheduler Execution times (SCF)
Assign each process a priority Deadlines (EDF)
Arrival times (FIFO)
At any time, scheduler runs highest priority
Classes of scheduling algorithms
process ready to run Preemptive vs non preemptive
Process runs to completion unless Off-line vs on-line
preempted Static vs dynamic
Event-driven vs time-driven

58

Task Scheduling Schedulability

Scheduler is responsible for time-sharing of CPU among tasks. A schedule is an ordered list of tasks (to be executed) and a
A variety of scheduling algorithms with predictable behaviors exist.
schedule is feasible if it meets all the deadlines

The general trade-off: the simplicity and the optimality.

Challenges for an RTOS A queue (or set) of tasks is schedulable if there exists a
Different performance criteria
GPOS: maximum average throughput
schedule such that no task may fail to meet its deadline
RTOS: deterministic behavior
A theoretically optimal schedule does not exist
Hard to get complete knowledge task requirements and hard properties
the requirements can be dynamic (i.e., time varying) adaptive scheduling

How to garuantee Timing Constraints?

scheduling

New tasks Dispatching
Running Termination

Preemption

How do we know all possible queues (situations) are schedulable?

we need task models (next lecture)

59 60

10
Priority-based scheduling in RTOS Basic functions of RT OS

static priority Task mangement

A task is given a priority at the time it is created, and it keeps this
priority during the whole lifetime. Interrupt handling
The scheduler is very simple, because it looks at all wait queues at
each priority level, and starts the task with the highest priority to Memory management
run.
dynamic priority Exception handling
The scheduler becomes more complex because it has to calculate Task synchronization
tasks priority on-line, based on dynamically changing parameters.
Earliest-deadline-first (EDF) --- A task with a closer deadline gets a Task scheduling
higher scheduling priority.
Rate-monotonic scheduling
A task gets a higher priority if it has to run more frequently. Time management
This is a common approach in case that all tasks are periodic . So, a
task that has to run every n milliseconds gets a higher priority than a
task that runs every m milliseconds when n<m.

61 62

Time mangement Time interrupt routine

A high resolution hardware timer is programmed to Save the context of the task in execution
interrupt the processor at fixed rate Time interrupt Increment the system time by 1, if current time > system
Each time interrupt is called a system tick (time lifetime, generate a timing error
resolution): Update timers (reduce each counter by 1)
A queue of timers
Activation of periodic tasks in idling state
Normally, the tick can vary in microseconds (depend on hardware)
The tick may (not necessarily) be selected by the user Schedule again - call the scheduler
All time parameters for tasks should be the multiple of the tick Other functions e.g.
Note: the tick may be chosen according to the given task parameters (Remove all tasks terminated -- deallocate data structures e.g TCBs)
System time = 32 bits (Check if any deadline misses for hard tasks, monitoring)
One tick = 1ms: your system can run 50 days

One tick = 20ms: your system can run 1000 days = 2.5 years
load context for the first task in ready queue
One tick = 50ms: your system can run 2500 days= 7 years

63 64

Basic functions of RT OS Features of current RTOS: SUMMARY

Task mangement ! Multi-tasking

Interrupt handling !

Priority-based scheduling
Memory management !
Application tasks should be programmed to suit ...
Exception handling !
Ability to quickly respond to external interrupts
Task synchronization !
Task scheduling ! Basic mechanisms for process communication and
Time management ! synchronization
Small kernal and fast context switch
Support of a real time clock as an internal time
reference

65 66

11
Existing RTOS: 4 categories RT Linux: an example
Priority based kernel for embbeded applications e.g. OSE, VxWorks, RT-Linux is an operating system, in which a small real-time
QNX, VRTX32, pSOS .... Many of them are commercial kernels kernel co-exists with standard Linux kernel:
Applications should be designed and programmed to suite priority-based The real-time kernel sits between standard Linux kernel and the
scheduling e.g deadlines as priority etc h/w. The standard Linux Kernel sees this RT layer as actual h/w.
The real-time kernel intercepts all hardware interrupts.
Real Time Extensions of existing time-sharing OS e.g. Real time Linux, Only for those RTLinux-related interrupts, the appropriate ISR is run.
Real time NT by e.g locking RT tasks in main memory, assigning All other interrupts are held and passed to the standard Linux kernel as
highest priorities etc software interrupts when the standard Linux kernel runs.
The real-time kernel assigns the lowest priority to the standard
Linux kernel. Thus the realtime tasks will be executed in real-time
Research RT Kernels e.g. SHARK, TinyOS user can create realtime tasks and achieve correct timing for
them by deciding on scheduling algorithms, priorities, execution
Run-time systems for RT programmingn languages e.g. Ada, Erlang, freq, etc.
Real-Time Java ... Realtime tasks are privileged (that is, they have direct access to
hardware), and they do NOT use virtual memory.

67 68

RT Linux Scheduling
Linux contains a dynamic scheduler
RT-Linux allows different schedulers
EDF (Earliest Deadline First)
Rate-monotonic scheduler
Fixed-prioritiy scheduler

69 70

Time Resolution Linux v.s. RTLinux

Linux Non-real-time Features
RT tasks may be scheduled in microseconds
Linux scheduling algorithms are not designed for real-time tasks
But provide good average performance or throughput
Running RT Linux-V3.0 Kernel 2.2.19 on the

Unpredictable delay
486 allows stable hard real-time operation: Uninterruptible system calls, the use of interrupt disabling, virtual
memory support (context switch may take hundreds of microsecond).
17 nanoseconds timer resolution. Linux Timer resolution is coarse, 10ms
Linux Kernel is Non-preemptible.
6 microseconds interrupt response time (measured RTLinux Real-time Features
on interrupts on the parallel port). Support real-time scheduling: guarantee hard deadlines
Predictable delay (by its small size and limited operations)
High resolution timing functions give

Finer time resolution

nanosecond resolution (limited by the Pre-emptible kernel
No virtual memory support
hardware only)

71 72

12