Transcript 資工系網媒所NEWS實驗室

Introduction of EOS
Embedded Real-Time Operating Systems
Introduction
Real-Time Scheduling
VxWorks
uCLinux
Real-Time Linux
uC/OS-II
04:35
0 /80
資工系網媒所
NEWS實驗室
Embedded OS trends 2001-2002,
sorted by 2001 usage
30%
25%
20%
2001
15%
2002
10%
5%
0%
Chorus
LynxOS
Green Hills
Nucleus
QNX
WinCE
Embedded Linux
DOS
VxWorks
Home grown
1 /80
資工系網媒所
NEWS實驗室
Embedded OS trends 2001-2002,
sorted by 2002 expectation
30%
25%
20%
2001
15%
2002
10%
5%
0%
Home grown
Chorus
DOS
QNX
Green Hills
BSD
LynxOS
WinCE
VxWorks
Embedded Linux
2 /80
資工系網媒所
NEWS實驗室
Real-Time Systems vs. Embedded Systems
RTS
ES
RTES
.Radar
.ABS
.Calculator
3 /80
資工系網媒所
NEWS實驗室
Real-Time Systems
Value
Deadline
Soft RTS
Hard RTS
FirmRTS
Time
-Value
4 /80
資工系網媒所
NEWS實驗室
RTOS at a Glance
- http://www.onesmartclick.com/rtos/rtos.html
AMX, KwikNet, KwikPeg (from KADAK Products Ltd.)
C EXECUTIVE (from JMI Software Systems, Inc.)
CMX-RTX (from CMX Systems, Inc.)
DeltaOS (from CoreTek Systems, Inc.)
eCos (from Red Hat, Inc.)
embOS (from SEGGER Microcontroller Systeme GmbH)
eRTOS (from JK microsystems, Inc.)
ETS (from VenturCom)
EYRX (from Eyring Corporation)
INTEGRITY (from Green Hills Software, Inc.)
INtime® real time extension to Windows® (from
TenAsys Corporation)
IRIX (from SGI)
iRMX (from TenAsys Corporation)
Jbed (from esmertec, inc.)
LynxOS (from LynuxWorks)
MQX (from Precise Software Technologies Inc)
Nucleus PLUS (AcceleratedTechnology, ESD Mentor Graphics)
On Time RTOS-32 (from On Time Informatik GmbH)
OS-9 (from Microware Systems Corporation)
OSE (from OSE Systems )
PDOS (from Eyring Corporation)
PSX (from JMI Software Systems, Inc.)
QNX Neutrino (from QNX Software Systems Ltd.)
QNX4 (from QNX Software Systems Ltd.)
REDICE-Linux (from REDSonic, Inc.)
RTLinux (from Finite State Machine Labs, Inc.)
RTX 5.0 (from VenturCom)
Portos (from Rabih Chrabieh)
smx (Micro Digital, Inc.)
SuperTask! (from US Software)
ThreadX (from Express Logic, Inc.)
Treck MicroC/OS-II (from Elmic Systems USA, Inc.)
TronTask! (from US Software)
TTPos: (from TTTech Computertechnik AG)
VxWorks 5.4 (from Wind River)
SCORE, DACS and TADS (from DDC-I)
Nimble - the SoC RTOS (from Eddy Solutions)
Nucleus (from Accelerated Technology)
Fusion RTOS (from DSP OS, Inc.)
FreeRTOS (from Richard Barry)
5 /80
資工系網媒所
NEWS實驗室
What is a Real-Time System?
A system enforcing timing constraints, e.g.
Avionics, Missile Control, …
The correctness of the system depends not only
on the logical result of the computation, but also
on the time at which the results are produced.
Real-Time vs. High Performance
What is a timing constraint?
A constraint of timing requirements, e.g. period,
distance, deadline, ready time, …
Functional and temporal correct.
6 /80
資工系網媒所
NEWS實驗室
Real-Time Task Model
Periodic Task Model
parameters are known a priori
request time
ready time
deadline start finish preempt resume
period
worst-case execution time
Predictability vs. Schedulability
high predictability and schedulability
easy-to-check schedulability condition
7 /80
資工系網媒所
NEWS實驗室
Real-Time System Examples
Industrial and automation system
Computer networking system
Gaming and multimedia
Medical instrument and devices
Financial transaction applications
Military defense system
Security monitoring and response system
Data acquisition system
Machine vision/translation system
…
資工系網媒所
8 /80
NEWS實驗室
Scheduling Approaches
Time-Driven Scheduling Approach
widely used
inflexible, efficient
large space needed
e.g. cyclic executive
0
6
3
Priority-Driven Scheduling Approach
dynamic-priority
e.g. earliest deadline first
fixed-priority
e.g. rate monotonic
0
6
3
9 /80
資工系網媒所
NEWS實驗室
Rate Monotonic
Job with smaller period gets higher priority.
Priority assignment is fixed (static).
1/2
1/3
1/6
0
1
2
3
4
5
6
10 /80
資工系網媒所
NEWS實驗室
Earliest Deadline First
Job with earlier deadline gets higher priority.
Priority is changing dynamically.
1/2
2/6
0
1
2
3
4
5
6
11 /80
資工系網媒所
NEWS實驗室
Periodic Real-Time Schedulers
Earliest Deadline First : optimal dynamic-priority scheduler
job with earlier deadline gets higher priority
schedulability condition
e
r (T   p  1
i
i
i
Rate Monotonic : optimal fixed-priority scheduler
job with smaller period gets higher priority
schedulability condition
1/n
r (T  n (2 - 1)
12 /80
資工系網媒所
NEWS實驗室
Distance-Constrained Task Model
video server
inter-frame distance must be less than 33ms
robot arm movement
needs steady and smooth operations
satellite/cellular phone tracking
service in constant time interval
more predictable inter-execution time
than the periodic task(PT) model
worst inter-execution time for PT is 2xperiod-ei
13 /80
資工系網媒所
NEWS實驗室
Study of Pinwheel Scheduling
n tasks are schedulable on a node (using Sr)
if the total utilization is less than or equal to
1/n
n(2 - 1).
n tasks are schedulable on all nodes (using
1/n-1
DSr) if the utilization on any node is ≦ 2
.
Algorithm of O(n) to minimize the total task
delays between two nodes.
Algorithm of O(mn) to minimize the total endto-end delays on m nodes.
14 /80
資工系網媒所
NEWS實驗室
Time-driven Scheduling Approach
on-line approach
execute tasks according to off-line
generated schedule or parameters
more flexible
off-line approach
0
6
3
construct complete schedule
exponential time and space
generate effective time parameters
start time, resume time, finish time
optimization
15 /80
資工系網媒所
NEWS實驗室
SSr: Pinwheel Schedule Constructor
Generate start times and finish times in O(n2)
0
5.3
10.6
15.9
21.2
task1
task2
task3
task4
task5
16 /80
資工系網媒所
NEWS實驗室
Pinwheel Transformation
2
E.g. A={3,4,6,13}  {3}
B ={3,3,6,12} ={3,3,3×21, 3×22}
• single-number reduction
A
Pinwheel
(RM)
any numbers 
multiples
jitterless, predictable
Signal
analog  digital
B
noiseless, ease of
control
e.g. CD music
(PW)
0
3
6
9
12
17 /80
資工系網媒所
NEWS實驗室
Pinwheel Scheduling Properties
Good jitter control in schedules
Easy-to-check schedulability
Predictable resource accesses
Easy extension for aperiodic tasks
Predictable end-to-end delay
Network scheduling (INFOCOM’95 by Han & Shin)
Flexible time-driven approach
18 /80
資工系網媒所
NEWS實驗室
Comparison of Schedulers
Scheduler
EDF
RM
Srb
schedulability
condition
jitter
high
low*
none
end-to-end delay
long
short
shortest
easy*
easy
large
small
stable
stable
1
resource reservation difficult
worst case
large
blocking time
system
unstable
overload
n (21/n - 1) n (21/n - 1)
*for higher priority tasks
19 /80
資工系網媒所
NEWS實驗室
RTOS
Introduction
VxWorks
uCLinux
Real-Time Linux
uC/OS-II
20 /80
資工系網媒所
NEWS實驗室
TORNADO II：
VxWorks
國立台灣大學
資訊工程學系
TORNADO II：VxWorks
Embedded Development Tools
VxWorks Real Time Operating System
Wind Microkernel
Snapshoot of Host Development Tools
04:35
22 /80
資工系網媒所
NEWS實驗室
The Next Generation of
Embedded Development Tools
04:35
23 /80
資工系網媒所
NEWS實驗室
Host Development Tools (I)
WindView
A logic analyzer for real-time software.
Provides information about context switches, events,
and instrumented objects.
CrossWind
A remote source-level debugger.
It is an extended version of the GDB.
WindSH
A host-resident command shell.
Provides interactive access from the host to all runtime facilities.
04:35
24 /80
資工系網媒所
NEWS實驗室
Host Development Tools (II)
Browser
A system-object viewer, a graphical companion to the
Tornado shell.
Provides display facilities to monitor the state of the target
system.
CodeTest
It is a visualize tool to design code coverage analysis and
tracking dynamic memory allocation.
Provides source code viewer-coverage and memory
allocation by function.
Look!
For C++ development, look inside source level bugs, to see
object relationship, and all messages among objects.
04:35
25 /80
資工系網媒所
NEWS實驗室
Host Development Tools (III)
WindNavigator
It performs hierarchical browsing on the application
code at working project mode by parsing source tree.
Stethoscope
It is a unique real-time graphic data monitor tool.
Watching any variable, see peak values, and look for
otherwise miss.
Project Manager
Simplifies organizing, configuring, and building
VxWorks applications.
04:35
26 /80
資工系網媒所
NEWS實驗室
Host Development Tools (IV)
Simulator
It is a port of VxWorks to the host system.
Simulates a target operating system.
3rd Party Tools
More than 300 partners provide solutions.
Custom Tools
An open extension architecture makes sample to
custom tools for using Tornado.
Easy to create custom tool using TCL base tool API.
04:35
27 /80
資工系網媒所
NEWS實驗室
VxWorks
04:35
28 /80
資工系網媒所
NEWS實驗室
Wind Microkernel
04:35
29 /80
資工系網媒所
NEWS實驗室
Embedded Internet
04:35
30 /80
資工系網媒所
NEWS實驗室
Virtual Memory
04:35
31 /80
資工系網媒所
NEWS實驗室
Multiprocessing
04:35
32 /80
資工系網媒所
NEWS實驗室
Graphics
04:35
33 /80
資工系網媒所
NEWS實驗室
File Systems
04:35
34 /80
資工系網媒所
NEWS實驗室
Networking
04:35
35 /80
資工系網媒所
NEWS實驗室
WindView
04:35
36 /80
資工系網媒所
NEWS實驗室
Stethoscope
04:35
37 /80
資工系網媒所
NEWS實驗室
RTOS
Introduction
VxWorks
uCLinux
Real-Time Linux
uC/OS-II
04:35
38 /80
資工系網媒所
NEWS實驗室
Introduction to uClinux
國立台灣大學
資訊工程學系
uCLinux
What is uClinux
Linux vs. uClinux
Features
Ported microcontrollers and
microprocessors
Devices running uClinux
Related web sites
04:35
40 /80
資工系網媒所
NEWS實驗室
What is uCLinux?
Embedded Linux/Microcontroller Project
Pronounced "you-see-linux"
"Mu" stands for "micro", and the "C" is for
"controller "
Derivative of Linux 2.0 kernel
Intended for microcontrollers without
Memory Management Units (MMUs)
04:35
41 /80
資工系網媒所
NEWS實驗室
What is uClinux? (Cont.)
First ported to the Motorola MC68328:
DragonBall Integrated Microprocessor.
First target system to successfully boot is
the 3Com PalmPilot using a TRG
SuperPilot Board.
04:35
42 /80
資工系網媒所
NEWS實驗室
Linux vs. uClinux
Multitasking can be tricky with Non-MMU
microprocessors.
Most user applications that run on top of
uClinux, however, will not require
multitasking.
04:35
43 /80
資工系網媒所
NEWS實驗室
Linux vs. uClinux(Cont.)
But uClinux absolutely DOES support
multi-tasking.
Although there are a few things that must
be keep in mind:
There is no memory protection.
uClinux does not implement fork(); instead it
implements vfork().
Stack does not autogrow. There is a compile
time option to set the stack size of a program.
04:35
44 /80
資工系網媒所
NEWS實驗室
Linux vs. uCLinux(Cont.)
Most of the binaries and source code for
the kernel have been rewritten to tightenup and slim-down the code base.
This all means that the uClinux kernel is
much, much smaller than the original
Linux 2.0 kernel.
Common Linux API
uCkernel < 512 KB
uCkernel + tools < 900 KB
04:35
45 /80
資工系網媒所
NEWS實驗室
Feature
uClinux retains the main advantages of the
Linux operating system.
Network
Full TCP/IP stack, as well as support for numerous
other networking protocols.
File systems
NFS
ext2
MS-DOS
FAT16/32
And more…
04:35
46 /80
資工系網媒所
NEWS實驗室
Ported Microcontrollers and
Microprocessors
uClinux is the leader in portability.
Now uClinux is ported to:
Motorola DragonBall, ColdFire, QUICC
Hitachi H8300
ARM7TDMI
ETRAX
Intel i960
PRISMA
Atari 68k
NEC V850E
04:35
47 /80
資工系網媒所
NEWS實驗室
Devices running uClinux
Aplio’s voice-over-IP telephone
MCU: ARM7TDMI
04:35
48 /80
資工系網媒所
NEWS實驗室
Devices running uClinux(Cont.)
AXIS 2100 Network Camera
MCU: AXIS ETRAX
Place it anywhere - no PC required
High-quality images - up to 10 frames/sec
No extra accessories, software or video
cabling needed
Built-in Web server
04:35
49 /80
資工系網媒所
NEWS實驗室
Related Web Site
Wind River Home
http://www.windriver.com/
The official site of uClinux:
http://www.uclinux.org/
04:35
50 /80
資工系網媒所
NEWS實驗室
RTOS
Introduction
VxWorks
uCLinux
Real-Time Linux
uC/OS-II
04:35
51 /80
資工系網媒所
NEWS實驗室
Introduction to
Real-Time Linux
國立台灣大學
資訊工程學系
Real-Time Linux
UTIME and KURT-Linux
RTLinux
RTAI
04:35
53 /80
資工系網媒所
NEWS實驗室
UTIME
UTIME and KURT-Linux are developed by the
Information and Telecommunication Technology
Center (ITTC) at the University of Kansas
UTIME is now a part of the KURT-Linux distribution
http://www.ittc.ku.edu/utime/
Supports Intel 80x86 architecture
In Linux, timing resolution of kernel timer is restricted
to 10 ms (80x86 architecture) due to the 100 Hz
frequency of timer interrupt
Linux maintains the sense of time at every timer
interrupts and handles the kernel timer in the timer
interrupt bottom half
04:35
54 /80
資工系網媒所
NEWS實驗室
Aims of UTIME
Provides microsecond level timing
resolution for Linux kernel timer
Reprogram the timer chip of X86 as one-shot
or periodic timer at any frequency
Use Time Stamp Counter (TSC register) of
Pentium or timer chip itself for non-Pentiums to
determine the time in a tick
Fully compatible with Linux kernel APIs and
system calls (time(), nanosleep(),
gettimeofday())
04:35
55 /80
資工系網媒所
NEWS實驗室
Implementation of UTIME
Add additional field "usec" to the
timer_list structure of Linux which
indicates the microsecond within the
current "jiffy" that the timer is to timeout
Added a "jiffies_u" variable which tracks
the microseconds within a 10ms tick
Call the do_timer() routine (Linux timer
interrupt handler) every jiffy by UTIME
instead of timer interrupt handler
04:35
56 /80
資工系網媒所
NEWS實驗室
Using the UTIME
User can take advantage of UTIME by
The nanosleep system call
Interval timers
The select system call
A custom kernel module
04:35
57 /80
資工系網媒所
NEWS實驗室
UTIME nanosleep example
void nanosleep_test(int delay) {
struct timespec sleepy;
sleepy.tv_sec = 0;
sleepy.tv_nsec = delay * 1000;
nanosleep(&sleepy, 0);
}
04:35
58 /80
資工系網媒所
NEWS實驗室
void timer_handler(int signal) {
// This is a job of one real-time task
}
UTIME Interval Timer Example
void setitimer_test(int delay, int interval, int tries) {
struct itimerval timer; sigset_t mask;
struct sigaction action; int i;
timer.it_interval.tv_sec = 0;
timer.it_interval.tv_usec = interval;
timer.it_value.tv_sec = 0;
timer.it_value.tv_usec = delay;
sigemptyset(&mask);
action.sa_handler = timer_handler;
action.sa_flags = 0;
sigaction(SIGALRM, &action, 0);
setitimer(ITIMER_REAL, &timer, 0);
for (i = 0 ; i < tries ; i++) {
sigsuspend(&mask);
}
timer.it_interval.tv_sec = 0;
timer.it_interval.tv_usec = 0;
timer.it_value.tv_sec = 0;
timer.it_value.tv_usec = 0;
setitimer(ITIMER_REAL, &timer, 0);
}
04:35
59 /80
資工系網媒所
NEWS實驗室
UTIME select and poll Example
void select_test(int delay) {
struct timeval timeout;
timeout.tv_sec = 0;
timeout.tv_usec = delay;
select(0, 0, 0, 0, &timeout);
}
void poll_test(int delay) {
poll(0, 0, delay);
}
04:35
60 /80
資工系網媒所
NEWS實驗室
UTIME Kernel Module Example
1 extern unsigned long volatile jiffies;
2 extern int volatile jiffies_u;
3 void timer_handler(unsigned long data) {
4 struct timeval now;
5 gettimeofday(&now, NULL);
6}
04:35
61 /80
資工系網媒所
NEWS實驗室
UTIME Kernel Module Example (cont’d)
7 int init_module(void) {
8
struct timer_list timer; unsigned long timeout; signed long
timeout_u;
9
struct timeval now;
10 /* Initialize and set the timer to go off in 5ms */
11 init_timer(&timer);
12 timer.expires = jiffies;
13 timer.usec = jiffies_u + 5000;
14 if (timer.usec >= USEC_PER_JIFFIES) {
15
timer.expires++;
16
timer.usec -= USEC_PER_JIFFIES;
17 }
18 timer.data = 100;
19 timer.function = timer_handler;
20 timer.flags |= UTIME_OFFSET;
21 /* Now add the timer. */
22 add_timer(&timer);
23 return 0;
24 }
04:35
62 /80
資工系網媒所
NEWS實驗室
Performance of UTIME (Pentium-200)
04:35
63 /80
資工系網媒所
NEWS實驗室
Performance of UTIME without
Pentium (Simulated by Pentium-200)
04:35
64 /80
資工系網媒所
NEWS實驗室
KURT-Linux
Provide on-demand, microsecond resolution and realtime scheduling capabilities to the standard Linux kernel
Real-time process could be kernel function (provide by
UTIME) or user-space process using KURT API
http://www.ittc.ku.edu/kurt/
Event-driven (time-driven) scheduling mechanism that
switches tasks in an explicit order
Static real-time schedule – generate an off-line schedule
and save it in a file and load this schedule from disk at
run-time
Dynamic real-time schedule – generate an off-line
schedule and submit this schedule at run-time
04:35
65 /80
資工系網媒所
NEWS實驗室
API of KURT-Linux
KURT Pseudo Device
Only three operations, open, close and ioctl
KURT kernel subsystem uses this device to
communicate with user space programs
Used by KURT API library
KURT API
DLL which is linked with real-time process
General and Utility operations
Process Initialization, registration, and control
Schedule submission
04:35
66 /80
資工系網媒所
NEWS實驗室
KURT-Linux Architecture
04:35
67 /80
資工系網媒所
NEWS實驗室
General and Utility Operations
kurt_open() – open an instance of the KURT pseudo device before
doing any KUT API calls
get_num_rtprocs() – return the number of real-time processes in
KURT
get_rtstats() – reports a process’s real-time behavior
get_rt_id_from_name() – retrieve a process’s real-time id via name
lookup
event_stats() – prints real-time timer statistical information
proc_stats() – prints statistical information for all real-time
processes
set_scheduling_offset() – set the delay setting of UTIME, default is
20 microseconds
get_scheduling_offset() – get the delay setting of UTIME
04:35
68 /80
資工系網媒所
NEWS實驗室
Process Initialization, Registration, and Control
rt_suspend() – suspends a real-time process
set_rtparams() – sets, resets, or unsets the
real-time parameters for a process
get_rtparams() – retrieves the real-time
parameters for a process
04:35
69 /80
資工系網媒所
NEWS實驗室
Schedule Submission
rt_schedule_events() - submits a binary schedule file of
contiguous real-time timers to the kernel
set_scheduling_task() / clear_scheduling_task() –
registers/unregisters current process as the KURT
scheduling task, which is the only one task to assign the
schedule to KURT-Linux
switch_to_rt() – switches the kernel to a specific realtime mode
switch_to_normal() – disables real-time scheduling
submit_dynamic_schedule() – submits a binary
schedule of real-time timers type rt_timer_list into the
kernel
disable_dynamic_schedule() – disables the dynamic
scheduling facilities
04:35
70 /80
資工系網媒所
NEWS實驗室
Real-Time Linux
UTIME and KURT-Linux
RTLinux
RTAI
04:35
71 /80
資工系網媒所
NEWS實驗室
RTLinux
Hard real-time operating system
Coexists with Linux or BSD kernel
RTLinux itself is non-preemprive
Runs Linux as a lowest priority thread
Worst case interrupt latency on a x86 is less
than 15 microseconds from the moment the
hardware interrupt is asserted
Uses a standard GDB Debugger
Runs on x86, PowerPC, Alpha, and MIPS
Provides POSIX threads and signals
http://fsmlabs.com
04:35
72 /80
資工系網媒所
NEWS實驗室
Tasks in RTLinux
Real-time tasks in RTLinux are
written as special Linux modules
Runs in the kernel space
Privileged
Do not use virtual memory.
RT-FIFO
A user space process
Do system calls for RTLinux thread
04:35
73 /80
資工系網媒所
NEWS實驗室
Detail of the bare Linux kernel
User Processes
System Libraries
UNIX/Linux kernel
Device Drivers
I/O
Hardware Interrupts
Hardware
04:35
74 /80
資工系網媒所
NEWS實驗室
RTLinux Kernel Architecture
Linux is executed in the background
User Processes
Real-time tasks
System Libraries
UNIX/Linux kernel
Device Drivers
I/O
Direct
Hardware
Access
RT Scheduler
Hardware Interrupts
RTLinux Plugin
I/O
Hardware Interrupts
Hardware
04:35
75 /80
資工系網媒所
NEWS實驗室
Data Flow in an RT Application
04:35
76 /80
資工系網媒所
NEWS實驗室
RTLinux APIs
Basic API
Creating RTLinux POSIX threads
Time facilities
Conversion routines
Scheduling threads (priority-driven scheduler)
Advanced API
Floating point operations support
RTLinux IPC
Real-time FIFOs
Shared memory
Waking and suspending RTLinux threads
Mutual exclusion
Accessing memory
Interrupts
04:35
77 /80
資工系網媒所
NEWS實驗室
Real-Time Linux
UTIME and KURT-Linux
RTLinux
RTAI
04:35
78 /80
資工系網媒所
NEWS實驗室
RTAI
Variant of RTLinux
http://www.aero.polimi.it/~rtai/
RTAI supports X86, PowerPC, ARM
(StrongARM; ARM7: clps711x-family, Cirrus
Logic EP7xxx, CS89712), and MIPS
Using RTHAL to trap Linux
A structure which contains function pointers
and variables of Linux
Trap Linux kernel by replacing the function
pointers in RTHAL
04:35
79 /80
資工系網媒所
NEWS實驗室
Architecture of RTAI
04:35
80 /80
資工系網媒所
NEWS實驗室