Post on 27-Jun-2020
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