Konfigurierbare Systemsoftware (KSS) - FAU · Konﬁgurierbare Systemsoftware (KSS) VL 7 – Summary and Discussion Daniel Lohmann Lehrstuhl für Informatik 4 Verteilte Systeme und

Konfigurierbare Systemsoftware

(KSS)

VL 7 – Summary and Discussion

Daniel Lohmann

Lehrstuhl für Informatik 4Verteilte Systeme und Betriebssysteme

Friedrich-Alexander-UniversitätErlangen-Nürnberg

SS 16 – 2016-07-11

http://www4.informatik.uni-erlangen.de/Lehre/SS16/V_KSS

http://www4.informatik.uni-erlangen.de/Lehre/SS16/V_KSS

Agenda

7.1 Summary

7.2 From Instance- to Interaction Tailoring

7.3 Evaluation und Diskussion

7.4 References

c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.1 Summary 7–2

The Operating System – A Swiss Army Knife?



Commodity operating systems provide a rich set of features to be

prepared for all kinds of applications and contingencies:

Malicious or erroneous applications

preemptive scheduling, address space separation, disk quotas

Multi-user operation

authentication, access validation and auditing

Multi-threaded and interacting applications

Threads, semaphores, pipes, sockets

Many/large concurrently running applications

virtual memory, swapping, working sets



One size fits all? →֒ Variability

“Clearly, the operating system design must be strongly influ-

enced by the type of use for which the machine is intended. Un-

fortunately it is often the case with ’general purpose machines’

that the type of use cannot be easily identified; a common criti-

cism of many systems is that in attempting to be all things to all

men they wind up being totally satisfactory to no-one.

”Lister and Eager 1993: Fundamentals of Operating Systems [4]



One size fits all? →֒ Variability

“Clearly, the operating system design must be strongly influ-

enced by the type of use for which the machine is intended. Un-

fortunately it is often the case with ’general purpose machines’

that the type of use cannot be easily identified; a common criti-

cism of many systems is that in attempting to be all things to all

men they wind up being totally satisfactory to no-one.

”Lister and Eager 1993: Fundamentals of Operating Systems [4]

/∈c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.1 Summary 7–4


Big is beautiful? →֒ Granularity

“Some applications may require only a subset of services or

features that other applications need. These ’less demanding’

applications should not be forced to pay for the resources con-

sumed by unneeded features.

”Parnas 1979: “Designing Software for Ease of Extension and Contraction” [5]



Big is beautiful? →֒ Granularity

“Some applications may require only a subset of services or

features that other applications need. These ’less demanding’

applications should not be forced to pay for the resources con-

sumed by unneeded features.

”Parnas 1979: “Designing Software for Ease of Extension and Contraction” [5]

*c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.1 Summary 7–5

Between a Rock and a Hard Place...

7

S y s t e m S o f t w a r e

Hardware

Application

functional and nonfunctional requirements

functional and nonfunctional properties

taskssocketsfile system...event latencysafety...

ISAIRQ handlingMMU / MPU...cache sizecoherenceIRQ latency...


Between a Rock and a Hard Place...

7

S y s t e m S o f t w a r e

Hardware

Application

functional and nonfunctional requirements

functional and nonfunctional properties

taskssocketsfile system...event latencysafety...

ISAIRQ handlingMMU / MPU...cache sizecoherenceIRQ latency...

High variety of functional and

nonfunctional application requirements

High variety of hardware platforms

High per-unit cost pressure

; System software has to be tailored

for each concrete application


Configurable Software – Software Product Line

Problem Space Solution Space

Specif ic Problem Specif ic Solution

Domain Expert ��

��

��

��

Features and Dependencies

Architect / Developer

��

��

��Class

��Aspect...

Architecture and Implementation

System User

��...

�

�Conf igurationA

B

D

C

System User

inst

ance

leve

lm

odel

leve

l

Variant

intendedproperties

actual implementation

intentional side extensional side


Configurable Software – Software Product Line

Problem Space Solution Space

Specif ic Problem Specif ic Solution

Domain Expert ��

��

��

��

Features and Dependencies

Architect / Developer

��

��

��Class

��Aspect...

Architecture and Implementation

System User

��...

�

�Conf igurationA

B

D

C

System User

inst

ance

leve

lm

odel

leve

l

Variant

intendedproperties

actual implementation

intentional side extensional side

KSS


Software Product Line: Building Blocks

System Software Product Lines

Problem Space Approaches

Feature Diagrams DSLs

Solution Space Approaches

Decompositional

Preprocessors

Compositional

OOP AOP

Generative

Generators

Focus: solution space techniques


Implementation Techniques: Classification

Decompositional Approaches

Configuration

Components Variant

Text-based filtering (untyped)

Preprocessors

Compositional Approaches

Configuration

Components Variant

Language-based composition

mechanisms (typed)

OOP, AOP, Templates

Generative Approches

Configuration

Generator VariantTemplates

Metamodel-based generation

of components (typed)

MDD, C++ TMP, generators


Feature vs. Instance-Based Configuration

OSEKeCos

FreeRTOS

LinuxQNX

featu

rein

stantiation

static

dynamic staticsystem object instantiation


Feature vs. Instance-Based Configuration

OSEKeCos

FreeRTOS

LinuxQNX

featu

rein

stantiation

static

dynamic staticsystem object instantiation

Not only features, but also object instances are known at compile-time:

Facilitates optimizations (static arrays instead of linked lists, . . . )

Advantages wrt. footprint, latency, resilience, . . .


Feature vs. Instance-Based: Case Study [2]

Sampling

3 msDigital

Sensor

Analog

Sensor

Signal

Processing

Flight

Control

Actuator

DataActuate

9 msUpdate

Actuators

IP Stack

RC Signal

Remote RXCopter

Control

WD

CounterWatchdog

1 ms

PanicSteering

reset +1 WD Counter > 25

Synchronized via Resource (Shared SPI Bus)

Real-world flight-control application (11 tasks, 3 alarms, 1 ISR)

Results with eCos and ERIKA Enterprise (open source OSEK)

eCos ERIKA factor

kernel code (bytes) 14763 6765 2.2x

kernel time (instructions) 88465 46087 1.9x

robustness (109 SDCs) 148 18 8.2x


Traditional Operating-System Design

Hardware

Application

HAL

least common denominator

Kernel

ISR1 ISR2 Task1 Task2 Task3

Feature Feature Feature Feature Feature

multiplex

syscallsyscall

abstract



Hardware

Application

HAL


Kernel



multiplex

syscallsyscall

abstract



Hardware

Application

HAL


Kernel



multiplex

syscallsyscall

abstract


Hardware-Centric Operating-System Design

Hardware

Application

HAL


Kernel

Kernel with Active HAL



multiplexsyscall

syscall

abstract


Agenda

7.1 Summary



7.4 References

c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.2 From Instance- to Interaction Tailoring 7–13

dOSEK: Dependability-Oriented Static Embedded Kernel

An extremely fault-tolerant OSEK implementation

Dependability by constructive measures

Employ standard hardware memory protectionAgressive avoidance of indirections ; lots of inliningArithmetic encoding of the kernel path (scheduler)


dOSEKRTAS ’15 [3]





Scenario: quadrotor flight-control application

11 tasks, 3 alarms, 1 ISR53 syscall invocations

Results (compared to ERIKA enterprise)

SDC reduction by 5 orders of magnitude: 109−→ 104 SDCs

Code size increases by factor 25: 8 −→ 200 KiBSyscall latency increases by factor 4: 100 −→ 400 cycles


dOSEKRTAS ’15 [3]










Culprit: arithmetically encoded scheduler ; avoid scheduling!


dOSEKRTAS ’15 [3]

Ein vereinfachtes OSEK System

TASK( Task1 ) {int data = read_data ();if (data == ’\0 ’) {

ActivateTask ( Task3 );} else {

bb_put (data );}ChainTask ( Task2 );

}

Task 1; Priorit 4

TASK( Task2 ) {

setup_of_device ();

TerminateTask ();}

Task 2; Priorit 5

TASK( Task3 ) {parse_message ();bb_clear_buffer ();

TerminateTask ();}

Task 3; Priorit 3

[email protected] Globale Optimierung von OSEK Systemen 4 – 23

An OSEK System


Der Kontrollflussgraph (CFG)

Task 1; Priorit 4 Task 2; Priorit 5

Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);

ActivateTask(Task3);

ChainTask(Task2);

setup_of_device()

TerminateTask()

parse_message()

bb_clear_buffer();

TerminateTask();


An OSEK System: Control-Flow Graphs


Der Kontrollflussgraph (CFG)


Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);


ChainTask(Task2);

setup_of_device()

TerminateTask()

parse_message()

bb_clear_buffer();

TerminateTask();


An OSEK System: Control-Flow Graphs


Spezialisierung von Systemaufrufen


Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);


ChainTask(Task2);

Idle

setup_of_device()

TerminateTask()

parse_message()

bb_clear_buffer();

TerminateTask();Idle


An OSEK System: Global Control-Flow Graph




Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);

SetReady(Task3);

ChainTask(Task2);

Idle

setup_of_device()

TerminateTask()

parse_message()

bb_clear_buffer();



(Partial) Specialization of System Calls [1]




Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);

SetReady(Task3);

SetSuspended(Task1)

SetReady(Task2)

DispatchTo(Task2);

Idle

setup_of_device()

TerminateTask()

parse_message()

bb_clear_buffer();







Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);

SetReady(Task3);

SetSuspended(Task1)

SetReady(Task2)

DispatchTo(Task2);

Idle

setup_of_device()

SetSuspended(Task2)

Reschedule()

parse_message()

bb_clear_buffer();







Task 3; Priorit 3

data = read_data();

if (data == ’\0’)

bb_put(data);

SetReady(Task3);

SetSuspended(Task1)

SetReady(Task2)

DispatchTo(Task2);

Idle

setup_of_device()

SetSuspended(Task2)

Reschedule()

parse_message()

bb_clear_buffer();

SetSuspended(Task3);

GotoIdle();Idle














dOSEKRTAS ’15 [3]






11 tasks, 3 alarms, 1 ISR } 243 GCFG edges53 syscall invocations

Results with call-site specialization LCTES ’15 [1]


Code size increases by factor 10.5: 8 −→ 85 KiBSyscall latency increases by factor 1.5: 100 −→ 150 cycles

; Further application-specific tailoring pays off!


dOSEKRTAS ’15 [3]

Instance-Based Tailoring (e.g., based on OIL file)

Hardware

Application

HAL


Kernel

Kernel (tailored to configuration)



multiplexsyscall

syscall

abstract

Kernel constrained to specified features and system objects.


Interaction-Based Tailoring (e.g., based on GCFG analysis)

Hardware

Application

HAL


Kernel

Kernel (tailored to actual usage)



multiplexsyscall

syscall

abstract

Kernel constrained to specified features and system objects.Further constrained to actually possible app → kernel interactions.


Agenda

7.1 Summary



7.4 References

c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.3 Evaluation und Diskussion 7–25

Evaluation

...


Diskussion

Am coolsten finde / fand ich...

Ich habe vermisst...

Bei einer Erweiterung auf 5 ECTS...


Wie gehts weiter? (Bachelor/Master)

SST7,5

Systemsoftwaretechnik

EZS5 – 7,5

BS5 – 7,5

MW5 – 7,5

EZS2P: 10

BST5

KSS2,5

PASSTP: 10

VS5 – 7,5

Examensarbeit / ProjektarbeitBA / SA, MA / DA, PA

SeminarMA

Systemprogrammierung10 ECTS

6

5

4

3

2/4

1/3


Referenzen

[1] Christian Dietrich, Martin Hoffmann, and Daniel Lohmann. “Cross-KernelControl-Flow-Graph Analysis for Event-Driven Real-Time Systems”. In:Proceedings of the 2015 ACM SIGPLAN/SIGBED Conference on Languages,Compilers and Tools for Embedded Systems (LCTES ’15). (Portland, Oregon,USA). New York, NY, USA: ACM Press, June 2015. isbn: 978-1-4503-3257-6.doi: 10.1145/2670529.2754963.

[2] Martin Hoffmann, Christoph Borchert, Christian Dietrich, Horst Schirmeier,Rüdiger Kapitza, Olaf Spinczyk, and Daniel Lohmann. “Effectiveness of FaultDetection Mechanisms in Static and Dynamic Operating System Designs”. In:Proceedings of the 17th IEEE International Symposium on Object-OrientedReal-Time Distributed Computing (ISORC ’14). (Reno, Nevada, USA). IEEEComputer Society Press, 2014, pp. 230–237. doi: 10.1109/ISORC.2014.26.

[3] Martin Hoffmann, Florian Lukas, Christian Dietrich, and Daniel Lohmann.“dOSEK: The Design and Implementation of a Dependability-Oriented StaticEmbedded Kernel”. In: Proceedings of the 21st IEEE International Symposium onReal-Time and Embedded Technology and Applications (RTAS ’15). Washington,DC, USA: IEEE Computer Society Press, 2015, pp. 259 –270. doi:10.1109/RTAS.2015.7108449.

[4] A.M. Lister and R.D. Eager. Fundamentals of Operating Systems. 5th.Macmillian, 1993. isbn: 0-333-46986-0.

c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.4 References 7–29

http://dx.doi.org/10.1145/2670529.2754963

http://dx.doi.org/10.1109/ISORC.2014.26

http://dx.doi.org/10.1109/RTAS.2015.7108449

Referenzen (Cont’d)

[5] David Lorge Parnas. “Designing Software for Ease of Extension and Contraction”.In: IEEE Transactions on Software Engineering SE-5.2 (1979), pp. 128–138.

c© dl KSS (VL 7 | SS 16) 7 Summary and Discussion | 7.4 References 7–30

Documents

Konfigurierbare Systemsoftware (KSS) - FAU · Konﬁgurierbare Systemsoftware (KSS) VL 7 – Summary and Discussion Daniel Lohmann Lehrstuhl für Informatik 4 Verteilte Systeme und