Vorlesung Echtzeitsysteme IIThema 5: Echtzeitfähige Kommunikation

Robert Baumgartl

11. Januar 2016

1 / 49

Literatur

I Jane W. S. Liu.Real-Time Systems. Kapitel 11Prentice Hall, 2000.

2 / 49

Überblick

I MedienzugriffsverfahrenI Time Triggered Architecture (TTA)I CAN und FlexRayI echtzeitfähige Protokolle fürs Internet

3 / 49

Einführung

Def. Echtzeitfähige Kommunikation sind Verfahren,Mechanismen, Schnittstellen und Protokolle zumDatenaustausch zwischen Aktivitäten, bei denen Garantienbezüglich bestimmter Parameter gegeben werden können.

Wiederum kann harte und weiche Echtzeitfähigkeitunterschieden werden.

Beispiele:I TelefonieI im Auto: CAN, FlexRay, LIN

Achtung! Fälschlich wird meist die umgangssprachlicheDefinition des Begriffes „Echtzeit“ verwendet. („Twitter ist einEchtzeit-Kommunikationsdienst“)

4 / 49

Typische Anforderungen an Echtzeitkommunikation

Latenz einer Nachricht: Zeit zwischen Start einerDatenübertragung in einem Knoten und Empfang der Daten aneinem anderen Knotenprimär (funktional):I maximale Latenz beschränkt und kleinI minimales Jitter (Schwankung) der LatenzI Durchsatz garantiertI Deadlines von Nachrichten eingehalten

sekundär (nicht-funktional):I Flexibilität und AdaptierbarkeitI Zuverlässigkeit: Fehlererkennung und -toleranz

5 / 49

Topologie

= Struktur des (physischen) Verbindungsnetzwerkes

I typisch: Bus, Ring, Stern, BaumI nicht so typisch: vollvermascht (byzantinische Generäle!)

Beispiel einer Topologie: Doppelring

Host A

Host CH

ost B

Ho

st

D

Abbildung: Doppelring mit zweiseparaten Strängen

Host A

Host B

Host C

Host

D

Unterbrechung

Abbildung: Umkonfigurationzum Einfachring (nachUnterbrechung eines Ringes)

6 / 49

GrundbegriffeFlusssteuerung

= Regulation der Senderate in Abhängigkeit vonGeschwindigkeit des Empfängers

I explizit: Empfänger sendet EmpfangsbestätigungenI implizit: Empfänger und Sender einigen sich a priori auf

Übertragungszeitpunkte

7 / 49

FlusssteuerungExplizite Flusssteuerung

Beispiel: Positive Acknowledgement and Retransmission(PAR)1

I Sender erhält für jedes Paket QuittungI keine Quittung nach Ablauf einer vordefinierten Zeitspanne

(Timeout)⇒ Schlussfolgerung: Quittung oder Paketverloren⇒ erneuter Versuch

I Abbruch, wenn maximale Anzahl Versuche fehlgeschlagen

Diskussion:I Sender initiiert KommunikationI Empfänger kann Sender verzögern (wie?)I Kommunikationsfehler auf dem Rückweg nur durch Sender

identifizierbar; Empfänger wird nicht informiertI ineffizient; Sender muss warten, bis Quittung eingetroffen

(→Window)1z. B. genutzt im TCP, HDLC

8 / 49

FlusssteuerungImplizite Flusssteuerung

I Empfänger und Sender stimmen überÜbertragungszeitpunkte überein

I keine QuittungenI Empfänger erkennt Fehler in Datenübertragung (fehlendes

Datum zum Übertragungszeitpunkt oder Prüfsumme ergibtFehler)

I Fehlertoleranz durch aktive Redundanz (n statt 1Nachricht)

I effizientI Verhalten gut determinierbarI ⇒ gut für Echtzeitsysteme geeignet

9 / 49

GrundbegriffeThrashing

Phänomen: Ein bestimmter Güteparameter (Durchsatz, Latenz,Reaktionszeit . . . ) eines Systems verringert sich abrupt, wenndie Last einen bestimmten Schwellwert überschreitet.

Durchsatz

Last100%

Maximum

Thrashing Point

ideal

real, gesteuert

real, ungesteuert

Abbildung: Beispiel für gesteuertes und ungesteuertes Thrashing

10 / 49

GrundbegriffeThrashing

darf in Echtzeit-Systemen nicht auftreten; muss alsogemanagt bzw. verhindert werden!

Thrashing-gefährdete Mechanismen:I Retry-Mechanismus bei Positive Acknowledgement and

Retransmission (PAR)I Medienzugriffsverfahren CSMA/CDI dynamisches Scheduling im BetriebssystemI Management virtuellen SpeichersI gegenseitiges Verschmutzen von Cachelines und TLBI Locking

Literatur: Peter J. Denning: Thrashing. Januar 2008http://denninginstitute.com/pjd/PUBS/ENC/thrash08.pdf

11 / 49

Problem des „Babbling Idiot“

I in Broadcastmedien kann ein einzelner Knoten dengesamten Datenverkehr stören, in dem er z. B.ununterbrochen sendet (→ “Babbling Idiot”)

I Hinzunahme eines zweiten Mediums ungünstig (teuer, wasist, wenn der fehlerhafte Knoten beide Medien stört?)

I Situation muss in echtzeitfähigen Systemen gesteuertwerden; Möglichkeiten:

I Erkennung des fehlerhaften Knotens und Ausschluss vomDatenverkehr

I Zuteilung des Mediums durch eine zentrale Instanz

12 / 49

MedienzugriffsverfahrenKollisionen

Problem: auf das Übertragungsmedium kann i. d. R. zu einemZeitpunkt nur ein Knoten schreibend zugreifen→ Kollisionenmöglich.Mögliche Strategien:I Vermeidung von Kollisionen durch Steuerung des Zugriffs

(collision avoidance), oderI Erkennung und (nachträgliche) Behebung von Kollisionen

(collision detection and resolution)I Medium limitiert Länge oder Abstand von Nachrichten

13 / 49

CSMA/CD

= Carrier Sense Multiple Access (with) Collision Detection

Prinzip:I jede Station lauscht auf DatenverkehrI solange Medium belegt, wird eigener Sendewunsch

verzögertI wenn frei und Sendewunsch→ schreibender Zugriff auf

MediumI während des Sendens wird Medium zur

Kollisionserkennung weiter abgehörtI Kollision: Senden des sog. Jam-Signals, Abbruch des

Sendevorgangs, zufällige Verzögerung, erneuterSendeversuch

I durch endliche Signallaufzeit sind auch Kollisionenmöglich, wenn Stationen nicht gleichzeitig senden

14 / 49

CSMA/CDPrinzip

Medium frei?

Senden

Kollision?

Erfolg

j

n

n

j

j

n

Fehler

Sendewunsch

Verzögerung

Maximum?

Abbildung: Prinzip von CSMA/CD15 / 49

CSMA/CDDiskussion

I Verzögerung: Binary Exponential Backoff: n-te Kollisionwird mit einer zufällig aus den Intervall [0 . . . 2n − 1]gewählten Wartezeit verzögert

I Abbruch nach Maximalzahl erfolgloser Versuche (z.B. 16)I Kollisionsanzahl abhängig von Last (ungünstig)I Gefahr von ThrashingI Übertragungszeit einer Nachricht schlecht vorhersagbarI keine Priorisierung möglich, keine Garantie der

ÜbertragungI schlecht für Echtzeitkommunikation geeignetI viele Varianten, die Kollisionswahrscheinlichkeit reduzieren

16 / 49

CSMA/CA

I . . . Collision AvoidanceI nach der Erkennung eines freien Kanals wird eine zufällige

Zeitspanne gewartet, bis mit der Übertragung begonnenwird

17 / 49

CSMA/CR

I ... Collision ResolutionI in einer so genannten Arbitrierungsphase werden

Kollisionen erkannt und aufgelöst, indem genau 1 Sendergewinnt und den Sendevorgang fortsetzt

I verlierende Sender werden zufällig verzögert undversuchen erneut

I Beispiel: CAN (Controller Area Network)

18 / 49

CSMA/CRBeispiel: Busarbitrierung bei CAN

I Jede Station besitzt eine ID (11 Bit)I notwendig: dominanter und rezessiver logischer Zustand

des Kommunikationskanals (hier: 0 – dominant, 1 –rezessiv)

I beim Senden wird der Nachricht die ID der Stationvorangestellt

I Nachricht (d. h. , zunächst Knoten-ID) wird bitweisebeginnend mit dem MSB auf den Bus geschrieben

I rezessive Bits ‘unterliegen’; Knoten stellt Senden ein,werden zufällig verzögert

I es „gewinnt“ der (sendewillige) Knoten mit der kleinsten IDI Voraussetzung: Sendeverzögerung der Nachricht ist

kleiner als 1 Bitzeit

19 / 49

CSMA/CRBeispiel: Busarbitrierung bei CAN

Bit

Knoten 1

Id 59C

Knoten 2

Id 537

Knoten 3

Id 539

Bus

10 9 8 7 6 5 4 3 2 1 0

16

16

16

verliert

verliert

20 / 49

Virtual Time CSMA (VTCSMA)Voraussetzungen

Idee: Nutzung einer individuellen Deadline zur Priorisierungvon NachrichtenVoraussetzungen:I Uhren aller Knoten sind synchronisiertI Abhören des Mediums möglich (Carrier Sensing)I Nachrichten M sind durch eine individuelle Deadline DM

charakterisiert (Zeitpunkt, bis zu dem die Nachrichtempfangen sein muss).

I Weitere Parameter:I τ – maximale Signallaufzeit des NetzesI TM – Zeit für das Senden einer Nachricht MI AM – Zeitpunkt des Eintreffens einer Nachricht M

21 / 49

Virtual Time CSMA (VTCSMA)Prinzip

I zwei Uhren auf jedem Knoten: RC, die (globale) Zeit desSystems (Real Clock) und VC, die so genannte Virtual Clock

I jeder Knoten hört das Medium ab und implementiert seine VCnach folgenden Regeln:

I wenn Kanal belegt→ VC gestopptI wenn Kanal frei→ VC wird mit Wert der RC initialisiert und

läuft mit einer Rate η (eta), die höher ist als die der RC (VC„geht vor“)

I VCs der Knoten sind somit ebenfalls synchronisiert.

22 / 49

Virtual Time CSMA (VTCSMA)Prinzip, contd.

I jede Nachricht M besitzt als Prioritätskriterium denspätestmöglichen Sendezeitpunkt LM , ohne ihre Deadline zuverletzen (analog zur Slack Time von zu planenden Jobs)

LM = DM − TM − τ

I Ein Knoten sendet eine Nachricht M, wenn das Medium frei istund LM ≤ VC gilt. Sind mehrere Nachrichten sendebereit, sowird die höchstpriorisierte (kleinstes LM ) gesendet.

I Da VC um η schneller läuft als die RC (die Realzeit), kann dieNachricht noch rechtzeitig eintreffen (keine Garantie!).

I Nachrichten, für die DM < RC gilt, werden verworfen, da sie ihreDeadline nicht mehr einhalten.

23 / 49

Virtual Time CSMA (VTCSMA)Kollisionsbehandlung

Da ggf. mehrere Knoten Nachrichten mit gleicher Prioritätversenden wollen, können Kollisionen auftreten.

Reaktion bei Detektion einer Kollision:I mit Wahrscheinlichkeit p: sofortiger erneuter SendeversuchI mit Wahrscheinlichkeit 1− p: Ersetzung der Priorität LM

durch einen Zufallswert aus [RC;LM ] (Priorität wird erhöht)

24 / 49

Virtual Time CSMA (VTCSMA)

Medium frei?

Stop der VC

mit verpasster Deadline

Löschen von Nachrichten

von VC

Initialisierung und Start

Gibt es Nachricht(en) M

Medium frei?

Sendewunsch

mit höchster Priorität

Senden der Nachricht M

Kollision?

Erneute Übertragung oder

j

n

j

n

j

n

j

n

mit L_M<=VC?

Modifikation der Priorität

25 / 49

Virtual Time CSMA (VTCSMA)Beispiel

In einem Netz mit τ = 1 sollen die folgende 4 Nachrichtenübertragen werden.

M AM DM LM

1 0 32 162 10 36 203 20 56 404 20 72 56

Tabelle: Beispiel zu VTCSMA

Die Übertragungszeit aller Nachrichten beträgt TM = 15. Esgelte η = 2.

Es gilt z. B. für Nachricht 1:

L1 = D1 − T1 − τ = 32− 15− 1 = 16.26 / 49

Virtual Time CSMA (VTCSMA)Resultierende RC-VC-Trajektorie für das Beispiel mit η = 2

8 16 3224 40 48 56 7264

24

32

40

48

56

64

72

16

8

M1

RC

VC

M3

M4

M2 verworfen!

27 / 49

Virtual Time CSMA (VTCSMA)Resultierende RC-VC-Trajektorie für das Beispiel mit η = 4

8 16 3224 40 48 56 7264

24

32

40

48

56

64

72

16

8

RC

VC

M2

M1

M3

M4

28 / 49

Virtual Time CSMA (VTCSMA)Beispiel

Auswertung:I für η = 2 musste M2 verworfen werden (Ursache: im

Intervall [0;8] wurde gefaulenzt)I für η = 4 konnten alle 4 Nachrichten übertragen werden

Je größer Steuerungsparameter ηI desto schneller läuft die VC im Vergleich zur RCI umso eher wird eine wartende Nachricht verschicktI umso größer die Chance, trotz Kollision die Nachricht noch

rechtzeitig zu versendenI umso weniger Reserve für potentiell eintreffende

Nachrichten mit kurzfristiger Deadline(und umgekehrt)

29 / 49

Virtual Time CSMA (VTCSMA)Fazit

I Nachrichten werden entsprechend ihrer Deadlinepriorisiert→ besser als CSMA/CD

I keine Garantie der rechtzeitigen ÜbertragungI kein Schutz gegen Überlast

Weiterführende Literatur:I Mart L. Molle, Leonard Kleinrock: Virtual Time CSMA:

Why Two Clocks Are Better than One. IEEE Transactionson Communications, Vol. 33, No. 9, September 1985,919–933

I Wei Zhao, Krithi Ramamritham: Virtual Time CSMAProtocols for Hard Real-Time Communication. IEEETransactions on Software Engineering, Vol. 13, No. 8,August 1987, S.938–952

30 / 49

Token Passing

Ein Token ist ein exklusives Datum, dessen Besitz zum Sendeneiner Nachricht autorisiert.

I nur ein Token existiert→ keine Kollisionen möglichI Token zirkuliert zwischen allen KnotenI deterministisches ZugriffsprotokollI Besitzer des Tokens darf für eine gewisse Dauer (konstant

oder variabel) Daten übertragen und muss dann das Tokenweitergeben

I Topologie: gewöhnlich Ring oder BusI tokenbasierte Protokolle sind stabil bei hoher Last

(unempfindlich gegen Thrashing)I wesentlicher Parameter: Target Token Rotation Time

(TTRT) = angestrebter Wert für einen kompletten Umlaufsdes Tokens (mit Nutzdatenübertragung an jedem Knoten)

Anwendung: Timed Token Protocol (TTP), Profibus31 / 49

Time Division Multiple Access (TDMA)

Idee: Jeder Knoten erhält reihum 1n der Kommunikationszeit.

I Voraussetzung: globale ZeitbasisI Für jeden Knoten ist statisch eine bestimmte Anzahl Slots

reserviert

���

���

������

������

������

������

������

������

���

���

������

������

���

���

���

���

t

...

Slot

TDMA Round

I Problem: Bandbreitenverschwendung wenn Knotentemporär sendeunwillig

32 / 49

Minislottingaka Flexible Time Division Multiple Access (FTDMA)

Idee:I alle sendewilligen Prozesse warten zunächst eine so

genannte Synchronisation Gap (SG) Stille abI danach wartet jeder Prozess eine weitere (kurze)

Zeitspanne, die von Prozess zu Prozess differiert (TerminalGap (TG))

I je höher priorisiert der Prozess, desto kleiner TGI jeder sendewillige Prozess hört gleichzeitig das Medium

ab; wenn nach Ablauf der TG kein (höherpriorisierter)Prozess sendet, so sendet der betreffende Prozess

I Während des Sendevorgangs wird ein Watchdog genutzt,der das Timeout Interval (TI), das längstmöglicheSendeintervall, eines Prozesses kontrolliert, damit diesernicht den Kanal okkupiert.

I → keine Kollisionen33 / 49

MinislottingTimer

3 Timer pro Prozess nötig:I SG – startet, sobald Stille auf dem Bus detektiert wirdI TGi – startet nach Ablauf der SG, sofern weiterhin Stille

auf dem Bus vorliegtI TI – startet, sobald Prozess begonnen hat, zu senden

(d. h., nachdem TGi verstrichen ist)Es gilt

SG > max(TGi) und TI > SG

AnwendungenI ARINC 629 (Feldbussystem für Avionik; eingesetzt in der

Boeing 777)I dynamisches Segment im FlexRay

34 / 49

MinislottingBeispiel

TG1P1

P2 TG2 TG2M2

M1 TI

TI

t

SG

(nach Hermann Kopetz: Real-Time Systems. Kluwer, 1997,S. 162)

35 / 49

Feldbusse

I zur Kommunikation zwischenI Zentrale(n)I Sensoren und Aktoren

in industrieller Umgebung (mechanische Beanspruchung,großer Temperaturbereich, Verschmutzung usw.)

I Standard IEC 61158I Motivation: teure DirektverkabelungI statt dessen: BusI VT: billiger, skalierbarI NT: Reaktionszeit ↑ (Thrashing!), Fehlertoleranz

problematischI ca. 50 verschiedene: Profibus, CAN, LON, FlexRay,

ARINC-629, TTP (Time-Triggered Protocol), EtherCAT,KNZ

I Tendenz: zunehmende Basis Ethernet36 / 49

Controller Area Network (CAN)

I durch die Robert Bosch GmbH ab 1983 entwickelt, ab1987 standardisiert (ISO 11898)

I Motivation: Verringerung VerkabelungsaufwandI weit verbreiteter fehlertoleranter Kommunikationsstandard

für Echtzeitsysteme, insbesondere im Automotive-BereichI Multicast-Protokoll, alle Knoten gleichberechtigtI Kollisionsvermeidung durch priorisierte bitweise

BusarbitrierungI 11 Bit großer Identifikator pro Nachricht, der die Station

identifiziert (später: auch 29 Bit)I max. Datenübertragungsrate: 1 MBit/s

37 / 49

Controller Area Network (CAN)Bit Stuffing

I Synchronisation der Teilnehmer aus DatensignalI lange Folgen gleicher Bitwerte stören Synchronisation

Regel: nach 5 Bits gleichen Werts erhält das 6. Bit(zwangsweise) den dazu inversen Wert.I Empfänger muss dieses Stuffing Bit wieder aus dem

Datenstrom entfernenI → 6 gleichwertige Bits hintereinander bedeuten einen

Fehlerzustand (Bit Stuffing Error)

38 / 49

Controller Area Network (CAN)Aufbau eines Frames

I 2 Längen: 11 und 29 Bit langer IdentifierI 2 Typen

I Data Frame: „normaler“ DatenverkehrI Remote Data Frame: Anforderung an einen speziellen

Knoten, Daten zu senden (Bit RTR gesetzt)

39 / 49

Controller Area Network (CAN)Aufbau eines (kurzen) Standard-Frames gemäß CAN 2.0A

SOF

0

IDE r0 DLC (4 Bit)Identifier (11 Bit) DATA (0...8 Byte) CRC (15 Bit) ACK EOF+IFS (10 Bit)R

TR

Feld Länge BedeutungSOF 1 Start of FrameID 11 Kennzeichnung Station und Nachrichteninhalt

RTR 1 Remote Transmission RequestIDE 1 Identifier Extension (hier: 0)r0 1 reserved

DLC 4 Länge des Datenfeldes in ByteDATA 0-64 NutzdatenCRC 15 Cyclic Redundancy CheckACK 2 Bestätigung der Empfänger

EOF+IFS 7+3 End of Frame/Inter Frame Space

40 / 49

Controller Area Network (CAN)Mechanismen zur Fehlererkennung

I CRC im FrameI Positive AcknowledgementI Fehler in der logischen Framestruktur („Formatfehler“)I Bitstuffing-Fehler (mehr als 5 gleichwertige Bits)I Sender lauscht gleichzeitig (Monitoring); dadurch

Erkennung von Verfälschungen

41 / 49

FlexRayEinführung

I Motivation: größere Datenraten als CAN; mehrFehlertoleranz

I Start: ca. 2000I Konsortium: Freescale, Bosch, NXP, BMW, VW, Daimler,

General MotorsI direkter Konkurrent: TTP (Time-Triggered Protocol)I zunächst in Modellen der „Premium“kategorie (BMW X5,

Audi A8, . . . )

42 / 49

FlexRayTechnische Merkmale

I Kommunikation über 2 physisch getrennte Kanäle á 10MBit/s (Redundanz, Verdopplung derKommunikationsbandbreite)

I Topologien: Bus, Stern, mehrere Sterne, KombinationenI Austausch von NachrichtenI Medienzugriff: Kombination aus TDMA (statisches

Segment) und Minislotting (dynamisches Segment)I Stationen sind so genannte Steuergeräte (Electronic

Control Unit (ECU))I Bus Guardian verhindert den “Babbling Idiot”

43 / 49

FlexRayStruktur einer ECU

Power Supply

BusGuardian

BusDriver

BusDriver

Bus

ECU

CommunicationController

µC (Host)

Guardian

Abbildung: Struktur einer ECU

44 / 49

FlexRayKommunikationszyklus

A B C D E

Kanal 1

Kanal 2

Abbildung: Beispiel einer FlexRay-Topologie

Kanal 1 A0 B0 A2 D0C0 A3 C2

statisches Segment

0 1 2 3 4 5 6 7A1 E0D1C1 A4 C3Kanal 2

t

t

dynamischesSegment

Kommunikationszyklus

A5

C4

Abbildung: Kommunikationszyklus45 / 49

FlexRayFormat eines Frames

Data 1 Data 2 Data n CRC CRC CRCData 0CycleCountHeader CRCFrame ID

durch Header CRC gesichert

Nul

lfra

me

indi

cato

r

Syn

cfra

me

indi

cato

r

Pay

load

prea

mbl

ein

dica

tor

Sta

rtup

fram

ein

dica

tor

rese

rved

11 Bits 7 Bits 11 Bits 6 Bits 0...254 Bytes 24 Bit

Payload Segment Trailer SegmentHeader Segment

PayloadLength

FlexRay-Frame: 5+(0...254)+3 Byte

(nach: FlexRay Consortium: FlexRay Communications SystemProtocol Specification. Version 2.1, Revision A, 2005, S. 90)

46 / 49

FlexRayAnmerkungen zum Frameformat

I Frame ID bestimmt den SlotI Payload Length enthält Anzahl Bytes des Payload

Segmentes, dividiert durch 2I im statischen Segment konstant und gleich für alle KnotenI im dynamischen Segment variabel (für verschiedene

Knoten und Zyklen)I Header (20 Bit) durch extra CRC (11 Bit) geschützt;

Hamming-Distanz von 6

47 / 49

FlexRaySynchronisation der Uhren

I ähnlich dezentrale Mittelwertbildung (↑ EZS1)I “Fault-Tolerant Midpoint Averaging”I Broadcast der lokalen Uhren in regelmäßigen Abständen

(mittels Sync Frame)I Elimination der f größten und f kleinsten UhrenwerteI von den verbleibenden Werten wird das arithmetische

Mittel aus Minimum und Maximum gebildet (= fault-tolerantmidpoint)

I Jennifer Lundelius Welch, Nancy Lynch: A NewFault-Tolerant Algorithm for Clock Synchronization.Information and Computation, Nr. 77, 1988, S. 1–36

48 / 49

ZusammenfassungWas haben wir gelernt?

Vor- und Nachteile von Medienzugriffsverfahren:I CSMA/CDI VTCSMAI Token-basierte VerfahrenI TDMAI Minislotting

2 typische Beispiele für FeldbusseI CANI FlexRay

Was fehlt?I Echtzeitaspekte des InternetI Time-Triggered Architecture (TTA)

49 / 49