Real-Time Operating System course

1Contact infoIntroduction

Some history about operating systemsReal-time systems

Miscellaneous

2

Contact informationMarko Bertognamarko@sssup.it

RTOS course web pagehttp://retis.sssup.it/~marko/rtos.html

RTOS course mailing listrtos-arezzo@retis.sssup.it

3

DocumentationPDF notes and slides (available on the web page)

Giorgio Buttazzo, Sistemi in Tempo Reale, Pitagora Editrice, Bologna, 2000.or, Giorgio Buttazzo, "HARD REAL-TIME COMPUTING SYSTEMS: Predictable Scheduling Algorithms and Applications", Kluwer Academic Publishers, Boston, 1997.

Linux man pages (as a reference for POSIX programming).

Notes on concurrent programming in UNIX systems.

Other reference books are available on the web page...

Introduction

5

Aim of the course

Studing basic concepts about concurrent programming

Studing software technologies & methodologies for supporting time critical computing systems.(we will not consider how to control a system, but only how to providea proper operating system support)

Provide a basic knowledge on the features available in real-time operating systems

6

Course outline

Introduction to operating systems Real-time systems (≈ 30 hours)

task scheduling aperiodic service problem of shared resources kernel design issues examples on a real-time system

Concurrent programming (≈ 20 hours) how to write a concurrent program the POSIX standard examples on UNIX-like systems

Computer architectures (≈ 40 hours) Synchronous and asynchronous logical networks Typical composing elements of a computer Assembler x86

Real-tim

e Operating System

s

Com

puter Architectures

7

Exams

Real-time systems part Oral exam

Questions on scheduling and schedulability analysis of real-time systems

Optional written exam during the course (allows avoiding oral exam) Concurrent programming part

Written exam on synchronization problems Set of threads to be properly synchronized using semaphores and/or

mutexes Project using POSIX synchronization primitives and real-time tasks

Might be a game, a control problem, a simulator, etc. Examples of past projects presented will be available on the web page

(Frogger, Space invaders, Boar hunt, etc.)

Computer architectures To be defined

Some history about operating systems

9

Fundamentals

Algorithm it is the logical procedure to solve a certain problem it is informally specified as a sequence of elementary steps that an

“execution machine” must follow to solve the problem it is not necessarily expressed in a formal programming language!Program it is the implementation of an algorithm in a programming language can be executed several times with different inputsProcess an instance of a program that given a sequence of inputs produces a

set of outputs

10

Operating System (OS)

An operating system is a program that provides an “abstraction” of the physical machine provides a simple interface to the machine each part of the interface is a “service”

An OS is also a resource manager with the term “resource” we denote all physical entities of a

computing machine the OS provides access to the physical resources the OS provides abstract resources (for example, a file, a virtual

page in memory, etc.)

11

Levels of abstraction

Kim Lisa Bill

Main Board CPU

Keyboard

Video Card

Network Card

Printer

Printer

Hard disk

OperatingSystem

Interface (System API)

Virtual Memory Scheduler Virtual File Sys.

Device Driver

Device Driver

Device Driver

Device Driver

Device Driver

Device Driver

Web Browser Shell Videogame Printer

Daemon

UserLevel

ProgrammerLevel

SystemLevel

HWLevel

12

Abstraction mechanisms

Why abstraction?Programming the HW directly has several drawbacks

it is difficult and error-prone it is not portable

Suppose you want to write a program that reads a text file from disk and outputs it on the screenWithout a proper interface it is virtually impossible!

13

Abstraction mechanisms

Application Programming Interface (API)provides a convenient and uniform way to access one service so that HW details are hidden to the high level programmer one application does not depend on the HW the programmer can concentrate on higher level tasks

Examplefor reading a file, linux and many other unix OS provide the open(), read() system calls that, given a “file name”, allow loading the data from an external support

14

Historical perspective

In the beginning was the batch processor huge machines, not very powerful used mainly for scientific computation and military applications

Programs were executed one at time They were called jobs

Program were simple sequential computations read the input compute produce output

Non-interactive!

15

Batch processor

batch = non-interactive the program could not be interrupted or suspended (non-

preemptive) scheduling:

priority based (e.g. safely critical applications first...) strictly FIFO shortest job first (SJF)

CPUProgram PunchCards

Result

jobs

16

Batch processor: performance

ttime the program is in execution on the CPUTtime the system is busy with the program

program loading I/O

The idea in batch systems is to reduce T as much as possible to be able to serve more jobs

efficiency= tT

17

Drawbacks

CPU was inactive for long intervals of time while reading the punch cards, the CPU had to wait the punch card reader was very slow

Solution: spooling use a magnetic disk (a faster I/O device) jobs were grouped into “job pools” while executing one job of a pool, read the next one into the disk when a job finishes, load the next one from the disk spool = symultaneous peripheral operation on-line

18

Interactivity

The need for interaction for reading input from the keyboard during the computation for showing intermediate results for saving intermediate result on magnetic support

Input/output it can be done with a technique called polling

wait until the device is ready and get/put the data handshaking

again, the CPU was inactive during I/O operations

19

Multi-programming

The natural evolution was “concurrency”IDEA: while a job is reading/writing from/to a I/O device, schedule another job to execute (preemption)

CPU Result

jobs

Preemption

20

Multi-programming

Multi-programming is very common in real-life

Consider a lawyer that has many clients: FIFO policy: serving one client at a time, from the beginning until the court

sentence in Italy, a sentence can be given after more than 10 years: imagine a poor

lawyer trying to survive with one client only for ten years! in reality, the lawyer adopts a TIME SHARING policy!

All of us adopts a time-sharing policy when doing many jobs at the same time!

21

The role of the Operating System

Who decides when a job is suspended? Who decides who is to be executed next?

in the first computers, these tasks were carried out by the application itself

each job could suspend itself and pass the “turn” to the next job (co-routines)

however, this is not very general or portable! Today, the OS provides the multiprogramming services

the scheduler module chooses which job executes next, depending on the status of the system

22

ProcessSwitch

Time sharing systems

In time sharing systems the time line is divided into “slots”, or “rounds”, each one of maximum

lenght equal to a fixed time quantum if the executing job does not block on a I/O operation before the end of

the quantum, it is suspended to be executed later

CPU

jobs

CPUCPUCPU

23

Time sharing systems

In time sharing systems Each process executes approximately as it were alone on a slower

processor The OS (thanks to the scheduler) “virtualizes” the processor

one single processor is seen as many (slower) parallel processors (one for each process)

We will see that an OS can virtualize many HW resources memory, disk, network, etc

Time sharing systems are not predictable the amount of execution time received by one process depends on

the number of processes in the system if we want a predictable behavior, we must use a RTOS

24

Time sharing systems: performance Mean response time

the time between a user request and the answer from the system i.e., the time between the instant when the user presses a key, and

the instant when it appears on the screen It is impossible to minimize the response time for each

program The idea is that each program runs like it is in a slower

processor how frequent the various tasks are switched? context change time: 1ms? 10ms? 50ms?

CPU intensive → batch Interactive → timesharing Predictable → real-time

25

Multi-user systems

The first computers were very powerful and very expensive a university could afford only one mainframe, but many people

needed to access the same computer therefore, the mainframe would give simultanous access to many

users at the same time this is an obvious extension of the multi-process system one or more processes for each user

26

Multi-user systems

The terminals had no computing power a keyboard + a monitor + a serial line every computation was carried out in the mainframe it is like having one computer with many keyboards and

videos

Mainframe

DumbTerminal

DumbTerminal

DumbTerminal

27

Multi-user systems

Another dimension was necessary the concept of user and account was born the first privacy concerns were raised

access rules passwords

criptography was applied for the first time in a non-military environment this makes the system more complex!

28

Distributed systems

Finally, distribution was introduced thanks to the DARPA, the TCP/IP protocol was developed and

internet was born the major universities in the USA connected their mainframes mail, telnet, ftp, etc the natural evolution was internet and the world wide web all of this was possible thanks to

the freedom of circulation of ideas the “liberal” environment in universities the need for communication and sharing information

29

Distributed systems: more flexibility

Client/server architectures one server provides “services” to remote clients example: web, ftp, databases, etc

It is possible to distribute an application different “parts” execute on different computers and then

communicate to exchange information and synchronise massively parallel programs can be easily implemented

seti@home distribute the contents

peer2peer

Migration processes can “move” from one computer to another to carry out a

certain service examples: agents, videogames, applets, etc

30

Evolution of computer systems

users

time

?

'70 '80 '90 '00

embeddedsystems

PC

minimainframes

'60

a disruptive process

31

Abstractions and Operating Systems

The OS provides an abstraction of a physical machine to allow portability to make programmer’s life easier

The level of abstraction depends on the application context it means that the kind of services an OS provides depend on which

kind of services the application requires general purposes OS should provide a wide range of services to satisfy as

many users as possible specialised OS provide only a group of specialised services

OS can be classified depending on the application context general purpose (windows, linux, etc) servers micro-kernel embedded OS real-time OS

32

Services

Virtual processor An OS provides “concurrency” between processes

many processes are executed at the same time in the same system each process executes for a fraction of the processor bandwidth (as it

were on a dedicated slower processor) Provided by the scheduling sub-system Provided by almost all OS, from nano-kernels to general-purpose

systems

CPU CPU CPU CPU

33

Services

Virtual memory Physical memory is limited; In old systems, the number of concurrent processes was

limited by the amount of physical memory IDEA: extend the physical memory by using a “fast” mass

storage system (disk) some of the processes stay in memory, some are temporarily

saved on the disk when a process must be executed, if it is on the disk it is first

loaded in memory and then executed this technique is called “swapping”

34

Virtual memory and physical memory

virtual memory is very large (virtually infinite!) the program functionality does not depend on the size of the

memory the program performance could be reduced by the swapping

mechanism

Process E

Process D

Process C

Process B

Process A

Process E

Process A

Process C

CPUACEBD

B

D

DiskPhysical memoryVirtual memory

A CEBDA CEBD

Process B A

Process B

Process A

35

Virtual memory

Advantages virtual infinite memory the program is not limited by the size of the physical memory

Disadvantages if we have too many programs, we spend most of the time

swapping back and forth (thrashing) performance degradation! not suitable for real-time systems

it is not possible to guarantee a short response time because it depends on the program location

36

Virtual file system

Basic concepts file: sequence of data bytes

it can be on a mass storage (hard disk, cd-rom, etc.) it can be on special virtual devices (i.e. RAM disks) it can be on a remote system!

directory: list of files usually organized in a tree represents how files are organized on the mass storage system

Virtualisation Device filesystem: in most OS, external serial devices (like the

console or the video terminal) can be seen as files (i.e. stdin, stout , stderr)

37

Virtual file system

A good virtual file system provides additional features: buffering & caching

for optimising I/O from block devices transactions

for example ext3, Reiser FS, and others fault tolerance capabilities

for example, the RAID system

Virtual file system is not provided by all OS categories micro and nano kernels do not even provide a file system!

38

Privacy and access rules

When many users are supported we must avoid that non-authorised users access restricted

information usually, there are two or more “classes” of users

supervisors normal users

each resource in the system can be customised with proper “access rules” that prevent access from non-authorised users

for example, the password file should be visible only to the system supervisor

Real-time systems

40

Real-time systems

A computing system able to respond to events within precise timing constraints is called a Real-Time System

real-timesystem

event

action

41

What’s a real-time system?

It is a system in which the correctness depends not only on the output values, but also on the time at which results are produced.

environmentRT system

y

x

t

(t)

(t+)

42

What’s a real-time system? (2)

REAL TIME means that system time must be synchronized with the time in the environment.

environmentRT system

y

x

t

(t)

(t+)t

43

Embedded control systems

Embedded control system

automatic control

software engineering

fault tolerance

computer electronic

mechanics

userbehavior

44

Typical RT applications Flight control systems Defense military systems Radar tracking Air traffic control Railway switching systems Telecommunication systems Flight simulators Robotics

45

… and many others Control of chemical/nuclear power plants Automotive applications Multimedia systems Small embedded devices

cell phones digital TV videogames intelligent toys

Wearable objects In general, everything that works or has to control some

environment

46

Intelligent objects We are used to think at embedded systems like something

far away from everyday life... ...but embedded systems will be soon part of our life, and

the software that controls them will have to interact with the environment

“When Things start to think”, by Neil GershenfeldIdea of intelligent pillar (example taken from a Nicholas Negroponte interview)

47

Development process

moreover, there can be: changes in the requirements dependencies between phases interaction between different phases

requirements

unit test

system integration

validation/calibrationarchitectural design

design parameters

detailed designfunctional, control algorithms

implementationtechnologiesRTOS, network communication, code generation...

48

Traditional approach In spite of this large application domain, most of RT

applications are designed using empirical techniques: assembly programming timing through dedicated timers low level control programming priority manipulations

49

Disadvantages Tedious programming which heavily depends on the

programmer’s ability Difficult code understanding Difficult software maintainability Difficult verification of timing constraints

50

Implications

Such a way of programming RT applications is

very dangerous

It may work in most situations, but the risk of a failure is high.

When the system fails, it is very difficult to understand why

low reliability

51

Accidents due to SW Patriot '91 (bug in the real-time clock) Ariane 5 '96 (64bit float to 16bit integer conversion) Mars Pathfinder '97 (mutual exclusion problem in VxWorks RTOS caused multiple resets for timeout) First flight of the Space Shuttle '85 (RTOS synch) Airbus 320 (cart and holding task) ... many more ...

see 100 other cases at: http://www.cs.tau.ac.il/~nachumd/horror.html

52

Murphy's laws (in Italian)(from Giorgio Buttazzo's book)

Legge Generale di Murphy Se qualcosa può andar male, lo farà

Legge di Naeser Si può fare qualcosa a prova di bomba, ma non a prova di jella

Seconda legge di Sodd Prima o poi, la peggiore combinazione possibile di circostanze è

destinata a verificarsi Corollario

Un sistema deve essere sempre progettato in modo da resistere alla peggiore combinazione possibile di circostanze

53

Lessons learned Tests, although necessary, allow only a partial verification of

system behavior Predictability must be improved at the kernel level Overload handling and fault-tolerance Critical systems must be designed by making pessimistic

assumptions

54

Real-Time ≠ Fast A real-time system is not a fast system Speed is always relative to a specific environment Running faster is good, but does not guarantee a correct

behavior

55

Speed vs. Predictability The objective of a real-time system is to guarantee the

timing behavior of each individual task. The objective of a fast system is to minimize the average

response time of a task set. But …

Do not trust average when you have to guarantee individual performance

56

Sources of non determinism Architecture

cache, pipelining, interrupts, DMA Operating system

scheduling, synchronization, communication Language

lack of explicit support for time Design methodologies

lack of analysis and verification techniques