Language Support for Real Time Programming

„ Concurrency (Ada tasking)

„ Communication & synchronization (Ada Rendezvous)
„ Consistency in data sharing (Ada protected data type)
Real time facilities (Ada real time packages)
What to do if we don’t have Ada?
„

1 2

Why OS?

„ To run one single program is easy

Today’s topic: OS Support „ Two, or three is fine, but more than five would be difficult
without help
for Real Time Programming „ you need to take care
„ memory areas
„ Program counters
„ Scheduling, run one instruction each?
„ ....
„ Communication/synchronization
„ Device drivers
„ OS is nothing but a program offering the functions needed in all
applications e.g. the start of Enea’s OSE

3 4

An example nano-kernel:
a single task cyclic executive Overall Stucture of Computer Systems

Setup-timer In most cases, RTOS=OS Kernel

c=0;
While (1) {suspend until timer expires Application Application Application
c++; Program Program Program
compute tasks due every cycle
if ((c%2)==0) compute tasks due every 2nd cycle OS User Interface Shell
if ((c%3)==0) compute tasks due every 3rd cycle
}
File and Disk Support

OS kernel
Hardware
5 6

1
Basic functions of OS Process, Thread and Task
„ Process mangement „ A process is a program in execution ...
„ Memory management „ Starting a new process is a heavy job for OS: memory has to be
allocated, and lots of data structures and code must be copied.
„ Interrupt handling „ memory pages (in virtual memory and in physical RAM) for code,
„ Exception handling data, stack, heap, and for file and other descriptors; registers in
the CPU; queues for scheduling; signals and IPC; etc.
„ Process Synchronization (IPC) „ A thread is a “lightweight” process, in the sense that different
„ Process schedulling threads share the same address space.
„ They share global and “static” variables, file descriptors, signal
„ Disk management bookkeeping, code area, and heap, but they have own thread
status, program counter, registers, and stack.
„ Shorter creation and context switch times, and faster IPC.
„ to save the state of the currently running task (registers, stack pointer,
PC, etc.), and to restore that of the new task.
„ Tasks are mostly threads

7 8

Basic functions of RTOS kernel Micro-kernel architecture

External System Hardware/software Clock
„ Task mangement interrupts calls exceptions interrupts
„ Interrupt handling
„ Memory management
Case of Exception handling
„ no virtual memory for hard RT tasks Immediate
Interrupt Create task Time services
„ Exception handling (important)
services Suspend task
„ Task synchronization Terminate task
.
„ Avoid priority inversion .
.
„ Task scheduling Create timer
Sleep-timer
„ Time management .
.
Timer-notify
.
Other system calls
Kernel
Scheduling
9 10

Basic functions of RTOS kernel Task: basic notion in RTOS

„ Task mangement „ Task = thread (lightweight process)

„ A sequential program in execution
„ Interrupt handling
„ It may communicate with other tasks
„ Memory management
„ It may use system resources
„ Exception handling
„ ....
„ Task synchronization
„ Task scheduling „ We may have timing constraints for tasks
„ Time management

11 12

2
Task Classification by deadlines (i.e. timing constraints) RT task characterization

„ Hard RT task must be computed within the given deadline value value
(otherwise system failure), e.g ABS control
„ The course will mainly deal with Hard RT tasks Hard deadline soft deadline

„ Soft RT task may be computed after the given deadline e.g.

Multi-media, the web etc

value value
„ On-time RT tasks (e.g alarm, robotics)

On-time deadline no deadline

„ Non RT task (background tasks)

13 14

Task Classification by release rate (1) Task Classification by release rate (2)

„ Periodic tasks: arriving at fixed frequency, can be „ Non-Periodic or aperiodic tasks = all tasks that are
characterized by 3 parameters (C,D,T) where not periodic, also known as Event-driven, their
„ C = computing time activations are generated by interrupts
„ D = deadline
„ T = period (e.g. 20ms, or 50HZ)
„ Sporadic tasks = aperiodic tasks with minimum
Often D=T, but it can be D<T or D>T
interarrival time Tmin (often with hard deadline)
„ worst case = periodic tasks with period Tmin
Also called Time-driven tasks, their activations are
generated by timers

15 16

Task states (1) Task states (2)

„ Ready
„ Running
„ Waiting/blocked/suspended ...
preemption
„ Idling Activate
Ready Runnig
Terminate
Dispatch

„ Terminated
signal wait

Blocked

17 18

3
Task states (Ada, delay) Task states (Ada95)

Idling declared Idling

timeout delay timeout Sleep

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

signal wait signal wait

Blocked Blocked

19 20

TCB (Task Control Block) Basic functions of RT OS

Id
Task mangement
„

„ Task state (e.g. Idling) „

„ Task type (hard, soft, background ...) „ Interrupt handling
Priority
„
„ Memory management
„ Other Task parameters
„ period „ Exception handling
„ comuting time (if available) „ Task synchronization
Relative deadline
Task scheduling
„
„
„ Absolute deadline
„ Context pointer „ Time management
„ Pointer to program code, data area, stack
„ Pointer to resources (semaphors etc)
„ Pointer to other TCBs (preceding, next, waiting queues etc)

21 22

Task managment Task mangement

„ Task creation: create a newTCB „ Challenges for an RTOS

„ Task termination: remove the TCB „ Creating an RT task, it has to get the memory without delay: this is
„ Change Priority: modify the TCB difficult because memory has to be allocated and a lot of data
structures, code seqment must be copied/initialized
„ ...
„ State-inquiry: read the TCB „ The memory blocks for RT tasks must be locked in main memoery
to avoid access latencies due to swapping

„ Changing run-time priorities is dangerous: it may change the run-

time behaviour and predictability of the whole system

23 24

4
Basic functions of RT OS Interrupt Handling
„ Task mangement „ Types of interrupts
„ Asynchronous (or hardware interrupt) by hardware event (timer, network
card …) the interrupt handler as a separated task in a different context.
„ Interrupt handling „ Synchronous (or software interrupt, or a trap) by software instruction (swi
in ARM, int in Intel 80x86), a divide by zero, a memory segmentation fault,
„ Memory management etc. The interrupt handler runs in the context of the interrupting task
„ Exception handling „ Challenges in RTOS
„ Interrupt latency
„ Task synchronization „ The time between the arrival of interrupt and the start of corresponding ISR.
Modern processors with multiple levels of caches and instruction pipelines that
„ Task scheduling „
need to be reset before ISR can start might result in longer latency.
„ Time management „ Interrupt enable/disable
„ The capability to enable or disable (“mask”) interrupt individually.
„ Interrupt priority
„ to block a new interrupt if an ISR of a higher-priority interrupt is still running.
„ the ISR of a lower-priority interrupt is preempted by a higher-priority interrupt.
„ The priority problems in task scheduling also show up in interrupt handling.

25 26

Interrupt Handling Basic functions of RT OS

„ Interrupt nesting „ Task mangement

an ISR servicing one interrupt can itself be pre-empted by another
„
interrupt coming from the same peripheral device.
„ Interrupt handling
„ Interrupt sharing „ Memory management
„ allow different devices to be linked to the same hardware interrupt.
„ check a status register on each of the devices that share the interrupt „ Exception handling
„ calling in turn all ISRs that users have registered with this IRQ. „ Task synchronization
„ Task scheduling
„ Time management

27 28

Memory Management/Protection Basic functions of RT OS

„ Standard methods „ Task mangement

„ Block-based, Paging, hardware mapping for protection „ Interrupt handling
„ 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 „

may access any blocks – Hope that the whole design is proven „ Task synchronization
correct and protection is unneccessary „ Task scheduling
„ to achive predictable timing „ Time management
„ 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

29 30

5
Exception handling Watch-dog

„ Exceptions e.g missing deadline, running out of „ A task, that runs (with high priority) in parallel with all others
memory, timeouts, deadlocks „ If some condition becomes true, it should react ...
„ Error at system level, e.g. deadlock Loop
„ Error at task level, e.g. timeout begin
„ Standard techniques: ....
„ System calls with error code end
„ Watch dog until condition
„ Fault-tolerance (later) „ The condition can be an external event, or some flags
„ However, difficult to know all senarios „ Normally it is a timeout
„ Missing one possible case may result in disaster
„ This is one reason why we need Modelling and Verification

31 32

Example Basic functions of RT OS

„ Watch-dog (to monitor whether the application task is alive) „ Task mangement
Loop „ Interrupt handling
if flag==1 then
„ Memory management
{
„ Exception handling
next :=system_time;
flag :=0 „ Task synchronization
}
„ Time management
else if system_time> next+20s then WARNING;
„ CPU scheduling
sleep(100ms)
end loop
„ Application-task
„ flag:=1 ... ... computing something ... ... flag:=1 ..... flag:=1 ....

33 34

Task Synchronization Task Synchronization

„ Synchronization primitives „ Challenges for RTOS

„ Semaphore: counting semaphore and binary semaphore „ Critical section (data, service, code) protected by lock
„ A semaphore is created with initial_count, which is the number of allowed holders mechanism e.g. Semaphore etc. In a RTOS, the maximum time a
of the semaphore lock. (initial_count=1: binary sem) task can be delayed because of locks held by other tasks should be
„ Sem_wait will decrease the count; while sem_signal will increase it. less than its timing constraints.
A task can get the semaphore when the count > 0; otherwise, block on it.
Race condition – deadlock, livelock, starvation Some
„

Mutex: similar to a binary semaphore, but mutex has an owner. „

deadlock avoidance/prevention algorithms are too complicate and
„
a semaphore can be “waited for” and “signaled” by any task,
indeterministic for real-time execution. Simplicity is preferred, like
„

„ while only the task that has taken a mutex is allowed to release it.
all tasks always take locks in the same order.
„ Spinlock: lock mechanism for multi-processor systems, „

„ allow each task to hold only one resource.

A task wanting to get spinlock has to get a lock shared by all processors.
Priority inversion using priority-based task scheduling and
„

Read/write locks: protect from concurrent write, while allow concurrent „

locking primitives should know the “priority inversion” danger: a
„
read
Many tasks can get a read lock; but only one task can get a write lock. medium-priority job runs while a highpriority task is ready to
proceed.
„

„ 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.”

35 36

6
IPC: Data exchanging Semaphore, Dijkstra 60s

„ Semaphore „ A semaphore is a simple data structure with

„ Shared variables „ a counter
„ the number of ”resources”
„ Bounded buffers
„ binary semaphore
FIFO
„
„ a queue
„ Mailbox „ Tasks waiting
„ Message passing
„ Signal and two operations:
Semaphore is the most primitive and widely used construct for
Synchronization and communicatioin in all operating systems
„ P(S): get or wait for semaphore
„ V(S): release semaphore

37 38

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

„ SCB: Semaphores Control Block „ P(scb):

Disable-interrupt;
If scb.counter>0 then
Counter scb.counter - -1;
Queue of TCBs (tasks waiting) end then
else
Pointer to next SCB save-context();
current-tcb.state := blocked;
insert(current-tcb, scb.queue);
The queue should be sorted by priorities (Why not FIFO?)
dispatch();
load-context();
end else
Enable-interrupt

39 40

Implementation of Semaphores: V-operation Advantages with semaphores

„ V(scb): „ Simple (to implement and use)

Disable-interrupt;
If not-empty(scb.queue) then „ Exists in most (all?) operating systems
tcb := get-first(scb.queue);
tcb.state := ready; „ It can be used to implement other
insert(tcb, ready-queue); synchronization tools
save-context();
schedule(); /* dispatch invoked*/ „ Monitors, protected data type, bounded buffers,
load-context(); mailbox etc
end then
else scb.counter ++1;
end else
Enable-interrupt

41 42

7
Exercise/Questions Disadvantages (problems) with semaphores

„ Implement Mailbox by semaphore „ Deadlocks

„ Send(mbox, receiver, msg) „ Loss of mutual exclusion
Get-msg(mbox,receiver,msg)
„
„ Blocking tasks with higher priorities (e.g. FIFO)
„ How to implement hand-shaking communication? „ Priority inversion !
„ V(S1)P(S2)
„ V(S2)P(S1)
„ Solve the read-write problem
„ (e.g max 10 readers, and at most 1 writer at a time)

43 44

Priority inversion problem Solution?

„ Assume 3 tasks: A, B, C with priorities Ap<Bp<Cp „ Task A with low priority holds S that task C with highest
„ Assume semaphore: S shared by A and C priority is waiting.
„ The following may happen: „ Tast A can not be forced to give up S, but A can be
„ A gets S by P(S) preempted by B because B has higher priority and can run
„ C wants S by P(S) and blocked without S
„ B is released and preempts A
„ Now B can run for a long long period .....
So the problem is that ’A can be preempted by B’
„ A is blocked by B, and C is blocked by A
„ So C is blocked by B
„ The above senario is called ’priority inversion’ „ Solution 1: no preemption (an easy fix) within CS sections
„ It can be much worse if there are more tasks with priorities in „ Solution 2: high A’s priority when it gets a semaphore shared
between Bp and Cp, that may block C as B does! with a task with higher priority! So that A can run until it
release S and then gets back its own priority

45 46

Resource Access Protocols Basic functions of RT OS

„ Highest Priority Inheritance „ Task mangement

„ Non preemption protocol (NPP) „ Interrupt handling
„ Basic Priority Inheritance Protocol (BIP) „ Memory management
„ POSIX (RT OS standard) mutexes „ Exception handling
„ Priority Ceiling Protocols (PCP) „ Task synchronization
Immedate Priority Inheritance
„
„ Highest Locker’s priority Protocol (HLP)
„ Task scheduling
„ Ada95 (protected object) and POSIX mutexes „ Time management

47 48

8
Task states Scheduling algorithms

„ Sort the READY queue acording to

„ Priorities (HPF)
Idling „ Execution times (SCF)
timeout delay „ Deadlines (EDF)
preemption „ Arrival times (FIFO)
Activate Terminate
Ready Runnig „ Classes of scheduling algorithms
Dispatch
„ Preemptive vs non preemptive
„ Off-line vs on-line
signal wait
„ Static vs dynamic
Blocked „ Event-driven vs time-driven

49 50

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 have been explored and implemented.
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 (also small memory usage, low power consumption ...)
„ 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)

51 52

Priority-based scheduling in RTOS Basic functions of RT OS

static priority
„
„ A task is given a priority at the time it is created, and it keeps this
„ Task mangement
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
task’s 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.

53 54

9
 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

55 56

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

57 58

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, real time Mach etc by e.g locking RT tasks in main „ All other interrupts are held and passed to the standard Linux kernel as
memory, assigning 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. MARS (Vienna univ), Spring (univ of „ – user can create realtime tasks and achieve correct timing for
Massachusetts) ... them by deciding on scheduling algorithms, priorities, execution
freq, etc.
„ Run-time systems for RT programmingn languages e.g. Ada, Erlang, „ – Realtime tasks are privileged (that is, they have direct access to
Real-Time Java ... hardware), and they do NOT use virtual memory.

59 60

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

61 62

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
„ Running RT Linux-V3.0 Kernel 2.2.19 on the „
„ But provide good average performance or throughput
– 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) „

63 64

11