Teil 5: Ez-kommunikation

Transcript

Vorlesung Echtzeitsysteme II Thema 5: Echtzeitfähige Kommunikation Robert Baumgartl 11. Januar 2016 1 / 49 Literatur I Jane W. S. Liu. Real-Time Systems. Kapitel 11 Prentice Hall, 2000. 2 / 49 Überblick I Medienzugriffsverfahren I Time Triggered Architecture (TTA) I CAN und FlexRay I echtzeitfähige Protokolle fürs Internet 3 / 49 Einführung Def. Echtzeitfähige Kommunikation sind Verfahren, Mechanismen, Schnittstellen und Protokolle zum Datenaustausch zwischen Aktivitäten, bei denen Garantien bezüglich bestimmter Parameter gegeben werden können. Wiederum kann harte und weiche Echtzeitfähigkeit unterschieden werden. Beispiele: I Telefonie I im Auto: CAN, FlexRay, LIN Achtung! Fälschlich wird meist die umgangssprachliche Definition des Begriffes „Echtzeit“ verwendet. („Twitter ist ein Echtzeit-Kommunikationsdienst“) 4 / 49 Typische Anforderungen an Echtzeitkommunikation Latenz einer Nachricht: Zeit zwischen Start einer Datenübertragung in einem Knoten und Empfang der Daten an einem anderen Knoten primär (funktional): I maximale Latenz beschränkt und klein I minimales Jitter (Schwankung) der Latenz I Durchsatz garantiert I Deadlines von Nachrichten eingehalten sekundär (nicht-funktional): I Flexibilität und Adaptierbarkeit I Zuverlässigkeit: Fehlererkennung und -toleranz 5 / 49 Topologie = Struktur des (physischen) Verbindungsnetzwerkes I I typisch: Bus, Ring, Stern, Baum nicht so typisch: vollvermascht (byzantinische Generäle!) Beispiel einer Topologie: Doppelring Unterbrechung Host A Host D Host B Host B Host D Host A Host C Host C Abbildung: Doppelring mit zwei separaten Strängen Abbildung: Umkonfiguration zum Einfachring (nach Unterbrechung eines Ringes) 6 / 49 Grundbegriffe Flusssteuerung = Regulation der Senderate in Abhängigkeit von Geschwindigkeit des Empfängers I explizit: Empfänger sendet Empfangsbestätigungen I implizit: Empfänger und Sender einigen sich a priori auf Übertragungszeitpunkte 7 / 49 Flusssteuerung Explizite Flusssteuerung Beispiel: Positive Acknowledgement and Retransmission (PAR)1 I I I Sender erhält für jedes Paket Quittung keine Quittung nach Ablauf einer vordefinierten Zeitspanne (Timeout) ⇒ Schlussfolgerung: Quittung oder Paket verloren ⇒ erneuter Versuch Abbruch, wenn maximale Anzahl Versuche fehlgeschlagen Diskussion: I Sender initiiert Kommunikation I Empfänger kann Sender verzögern (wie?) I Kommunikationsfehler auf dem Rückweg nur durch Sender identifizierbar; Empfänger wird nicht informiert I ineffizient; Sender muss warten, bis Quittung eingetroffen (→ Window) 1 z. B. genutzt im TCP, HDLC 8 / 49 Flusssteuerung Implizite Flusssteuerung I Empfänger und Sender stimmen über Übertragungszeitpunkte überein I keine Quittungen I Empfänger erkennt Fehler in Datenübertragung (fehlendes Datum zum Übertragungszeitpunkt oder Prüfsumme ergibt Fehler) I Fehlertoleranz durch aktive Redundanz (n statt 1 Nachricht) I effizient I Verhalten gut determinierbar I ⇒ gut für Echtzeitsysteme geeignet 9 / 49 Grundbegriffe Thrashing Phänomen: Ein bestimmter Güteparameter (Durchsatz, Latenz, Reaktionszeit . . . ) eines Systems verringert sich abrupt, wenn die Last einen bestimmten Schwellwert überschreitet. Durchsatz Maximum ideal Thrashing Point real, gesteuert real, ungesteuert 100% Last Abbildung: Beispiel für gesteuertes und ungesteuertes Thrashing 10 / 49 Grundbegriffe Thrashing darf in Echtzeit-Systemen nicht auftreten; muss also gemanagt bzw. verhindert werden! Thrashing-gefährdete Mechanismen: I Retry-Mechanismus bei Positive Acknowledgement and Retransmission (PAR) I Medienzugriffsverfahren CSMA/CD I dynamisches Scheduling im Betriebssystem I Management virtuellen Speichers I gegenseitiges Verschmutzen von Cachelines und TLB I Locking Literatur: Peter J. Denning: Thrashing. Januar 2008 http://denninginstitute.com/pjd/PUBS/ENC/thrash08.pdf 11 / 49 Problem des „Babbling Idiot“ I in Broadcastmedien kann ein einzelner Knoten den gesamten Datenverkehr stören, in dem er z. B. ununterbrochen sendet (→ “Babbling Idiot”) I Hinzunahme eines zweiten Mediums ungünstig (teuer, was ist, wenn der fehlerhafte Knoten beide Medien stört?) Situation muss in echtzeitfähigen Systemen gesteuert werden; Möglichkeiten: I I I Erkennung des fehlerhaften Knotens und Ausschluss vom Datenverkehr Zuteilung des Mediums durch eine zentrale Instanz 12 / 49 Medienzugriffsverfahren Kollisionen Problem: auf das Übertragungsmedium kann i. d. R. zu einem Zeitpunkt nur ein Knoten schreibend zugreifen → Kollisionen möglich. Mögliche Strategien: I Vermeidung von Kollisionen durch Steuerung des Zugriffs (collision avoidance), oder I 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 Datenverkehr I solange Medium belegt, wird eigener Sendewunsch verzögert I wenn frei und Sendewunsch → schreibender Zugriff auf Medium I während des Sendens wird Medium zur Kollisionserkennung weiter abgehört I Kollision: Senden des sog. Jam-Signals, Abbruch des Sendevorgangs, zufällige Verzögerung, erneuter Sendeversuch I durch endliche Signallaufzeit sind auch Kollisionen möglich, wenn Stationen nicht gleichzeitig senden 14 / 49 CSMA/CD Prinzip Sendewunsch n Medium frei? j Senden Verzögerung j Kollision? n Maximum? n Erfolg j Fehler Abbildung: Prinzip von CSMA/CD 15 / 49 CSMA/CD Diskussion I Verzögerung: Binary Exponential Backoff: n-te Kollision wird 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 Thrashing I Übertragungszeit einer Nachricht schlecht vorhersagbar I keine Priorisierung möglich, keine Garantie der Übertragung I schlecht für Echtzeitkommunikation geeignet I viele Varianten, die Kollisionswahrscheinlichkeit reduzieren 16 / 49 CSMA/CA I . . . Collision Avoidance I nach der Erkennung eines freien Kanals wird eine zufällige Zeitspanne gewartet, bis mit der Übertragung begonnen wird 17 / 49 CSMA/CR I ... Collision Resolution I in einer so genannten Arbitrierungsphase werden Kollisionen erkannt und aufgelöst, indem genau 1 Sender gewinnt und den Sendevorgang fortsetzt I verlierende Sender werden zufällig verzögert und versuchen erneut I Beispiel: CAN (Controller Area Network) 18 / 49 CSMA/CR Beispiel: 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 Station vorangestellt I Nachricht (d. h. , zunächst Knoten-ID) wird bitweise beginnend 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 ID I Voraussetzung: Sendeverzögerung der Nachricht ist kleiner als 1 Bitzeit 19 / 49 CSMA/CR Beispiel: Busarbitrierung bei CAN Bit Knoten 1 Id 59C16 10 9 8 7 6 5 4 3 2 1 0 verliert Knoten 2 Id 53716 Knoten 3 Id 53916 verliert Bus 20 / 49 Virtual Time CSMA (VTCSMA) Voraussetzungen Idee: Nutzung einer individuellen Deadline zur Priorisierung von Nachrichten Voraussetzungen: I Uhren aller Knoten sind synchronisiert I Abhören des Mediums möglich (Carrier Sensing) I Nachrichten M sind durch eine individuelle Deadline DM charakterisiert (Zeitpunkt, bis zu dem die Nachricht empfangen sein muss). Weitere Parameter: I I I I τ – maximale Signallaufzeit des Netzes TM – Zeit für das Senden einer Nachricht M AM – Zeitpunkt des Eintreffens einer Nachricht M 21 / 49 Virtual Time CSMA (VTCSMA) Prinzip I zwei Uhren auf jedem Knoten: RC, die (globale) Zeit des Systems (Real Clock) und VC, die so genannte Virtual Clock I jeder Knoten hört das Medium ab und implementiert seine VC nach folgenden Regeln: I I I wenn Kanal belegt → VC gestoppt 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“) VCs der Knoten sind somit ebenfalls synchronisiert. 22 / 49 Virtual Time CSMA (VTCSMA) Prinzip, contd. I jede Nachricht M besitzt als Prioritätskriterium den spätestmöglichen Sendezeitpunkt LM , ohne ihre Deadline zu verletzen (analog zur Slack Time von zu planenden Jobs) LM = DM − TM − τ I Ein Knoten sendet eine Nachricht M, wenn das Medium frei ist und LM ≤ VC gilt. Sind mehrere Nachrichten sendebereit, so wird die höchstpriorisierte (kleinstes LM ) gesendet. I Da VC um η schneller läuft als die RC (die Realzeit), kann die Nachricht noch rechtzeitig eintreffen (keine Garantie!). I Nachrichten, für die DM < RC gilt, werden verworfen, da sie ihre Deadline nicht mehr einhalten. 23 / 49 Virtual Time CSMA (VTCSMA) Kollisionsbehandlung Da ggf. mehrere Knoten Nachrichten mit gleicher Priorität versenden wollen, können Kollisionen auftreten. Reaktion bei Detektion einer Kollision: I mit Wahrscheinlichkeit p: sofortiger erneuter Sendeversuch I 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) Sendewunsch n Medium frei? j Initialisierung und Start von VC Löschen von Nachrichten mit verpasster Deadline Gibt es Nachricht(en) M n mit L_M<=VC? j j Senden der Nachricht M mit höchster Priorität Medium frei? n Kollision? n Stop der VC j Erneute Übertragung oder 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 2 3 4 0 10 20 20 32 36 56 72 16 20 40 56 Tabelle: Beispiel zu VTCSMA Die Übertragungszeit aller Nachrichten beträgt TM = 15. Es gelte η = 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 VC 72 64 M4 56 48 M3 40 32 24 M1 16 8 M2 verworfen! 8 16 24 32 40 48 56 64 72 RC 27 / 49 Virtual Time CSMA (VTCSMA) Resultierende RC-VC-Trajektorie für das Beispiel mit η = 4 VC 72 64 M4 56 48 M3 40 32 24 M2 M1 16 8 8 16 24 32 40 48 56 64 72 RC 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 RC I umso eher wird eine wartende Nachricht verschickt I umso größer die Chance, trotz Kollision die Nachricht noch rechtzeitig zu versenden I 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 Deadline priorisiert → besser als CSMA/CD I keine Garantie der rechtzeitigen Übertragung I kein Schutz gegen Überlast Weiterführende Literatur: I Mart L. Molle, Leonard Kleinrock: Virtual Time CSMA: Why Two Clocks Are Better than One. IEEE Transactions on Communications, Vol. 33, No. 9, September 1985, 919–933 I Wei Zhao, Krithi Ramamritham: Virtual Time CSMA Protocols for Hard Real-Time Communication. IEEE Transactions 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 Senden einer Nachricht autorisiert. I I I I I I I nur ein Token existiert → keine Kollisionen möglich Token zirkuliert zwischen allen Knoten deterministisches Zugriffsprotokoll Besitzer des Tokens darf für eine gewisse Dauer (konstant oder variabel) Daten übertragen und muss dann das Token weitergeben Topologie: gewöhnlich Ring oder Bus tokenbasierte Protokolle sind stabil bei hoher Last (unempfindlich gegen Thrashing) wesentlicher Parameter: Target Token Rotation Time (TTRT) = angestrebter Wert für einen kompletten Umlaufs des Tokens (mit Nutzdatenübertragung an jedem Knoten) Anwendung: Timed Token Protocol (TTP), Profibus 31 / 49 Time Division Multiple Access (TDMA) Idee: Jeder Knoten erhält reihum 1 n der Kommunikationszeit. I Voraussetzung: globale Zeitbasis I Für jeden Knoten ist statisch eine bestimmte Anzahl Slots reserviert 11 00 0 1 00 11 00 11 00 11 0 1 0 1 0 1 00 11 0 1 00 11 00 11 00 11 0 1 0 1 0 00 11 0 1 00 11 00 11 001 11 01 01 0 ... 1 Slot t TDMA Round I Problem: Bandbreitenverschwendung wenn Knoten temporär sendeunwillig 32 / 49 Minislotting aka Flexible Time Division Multiple Access (FTDMA) Idee: I alle sendewilligen Prozesse warten zunächst eine so genannte Synchronisation Gap (SG) Stille ab I danach wartet jeder Prozess eine weitere (kurze) Zeitspanne, die von Prozess zu Prozess differiert (Terminal Gap (TG)) I je höher priorisiert der Prozess, desto kleiner TG I 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ögliche Sendeintervall, eines Prozesses kontrolliert, damit dieser nicht den Kanal okkupiert. I → keine Kollisionen 33 / 49 Minislotting Timer 3 Timer pro Prozess nötig: I SG – startet, sobald Stille auf dem Bus detektiert wird I TGi – startet nach Ablauf der SG, sofern weiterhin Stille auf dem Bus vorliegt I TI – startet, sobald Prozess begonnen hat, zu senden (d. h., nachdem TGi verstrichen ist) Es gilt SG > max(TGi ) und TI > SG Anwendungen I ARINC 629 (Feldbussystem für Avionik; eingesetzt in der Boeing 777) I dynamisches Segment im FlexRay 34 / 49 Minislotting Beispiel SG P1 P2 TI TG1 TG2 M1 TI TG2 M2 t (nach Hermann Kopetz: Real-Time Systems. Kluwer, 1997, S. 162) 35 / 49 Feldbusse I zur Kommunikation zwischen I I Zentrale(n) Sensoren und Aktoren in industrieller Umgebung (mechanische Beanspruchung, großer Temperaturbereich, Verschmutzung usw.) I Standard IEC 61158 I Motivation: teure Direktverkabelung I statt dessen: Bus I VT: billiger, skalierbar I NT: Reaktionszeit ↑ (Thrashing!), Fehlertoleranz problematisch I ca. 50 verschiedene: Profibus, CAN, LON, FlexRay, ARINC-629, TTP (Time-Triggered Protocol), EtherCAT, KNZ I Tendenz: zunehmende Basis Ethernet 36 / 49 Controller Area Network (CAN) I durch die Robert Bosch GmbH ab 1983 entwickelt, ab 1987 standardisiert (ISO 11898) I Motivation: Verringerung Verkabelungsaufwand I weit verbreiteter fehlertoleranter Kommunikationsstandard für Echtzeitsysteme, insbesondere im Automotive-Bereich I Multicast-Protokoll, alle Knoten gleichberechtigt I Kollisionsvermeidung durch priorisierte bitweise Busarbitrierung I 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 Datensignal I 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 entfernen I → 6 gleichwertige Bits hintereinander bedeuten einen Fehlerzustand (Bit Stuffing Error) 38 / 49 Controller Area Network (CAN) Aufbau eines Frames I I 2 Längen: 11 und 29 Bit langer Identifier 2 Typen I I Data Frame: „normaler“ Datenverkehr Remote Data Frame: Anforderung an einen speziellen Knoten, Daten zu senden (Bit RTR gesetzt) 39 / 49 Controller Area Network (CAN) 0 Identifier (11 Bit) RTR IDE Aufbau eines (kurzen) Standard-Frames gemäß CAN 2.0A r0 DLC (4 Bit) DATA (0...8 Byte) CRC (15 Bit) ACK EOF+IFS (10 Bit) SOF Feld SOF ID RTR IDE r0 DLC DATA CRC ACK EOF+IFS Länge 1 11 1 1 1 4 0-64 15 2 7+3 Bedeutung Start of Frame Kennzeichnung Station und Nachrichteninhalt Remote Transmission Request Identifier Extension (hier: 0) reserved Länge des Datenfeldes in Byte Nutzdaten Cyclic Redundancy Check Bestätigung der Empfänger End of Frame/Inter Frame Space 40 / 49 Controller Area Network (CAN) Mechanismen zur Fehlererkennung I CRC im Frame I Positive Acknowledgement I 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 FlexRay Einführung I Motivation: größere Datenraten als CAN; mehr Fehlertoleranz I Start: ca. 2000 I Konsortium: Freescale, Bosch, NXP, BMW, VW, Daimler, General Motors I direkter Konkurrent: TTP (Time-Triggered Protocol) I zunächst in Modellen der „Premium“kategorie (BMW X5, Audi A8, . . . ) 42 / 49 FlexRay Technische Merkmale I Kommunikation über 2 physisch getrennte Kanäle á 10 MBit/s (Redundanz, Verdopplung der Kommunikationsbandbreite) I Topologien: Bus, Stern, mehrere Sterne, Kombinationen I Austausch von Nachrichten I 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 FlexRay Struktur einer ECU ECU µC (Host) Power Supply Communication Controller Bus Guardian Bus Driver Bus Guardian Bus Driver Abbildung: Struktur einer ECU 44 / 49 FlexRay Kommunikationszyklus A B C D E Kanal 1 Kanal 2 Abbildung: Beispiel einer FlexRay-Topologie Kanal 1 A0 Kanal 2 A1 0 B0 C0 1 C1 2 A2 D0 3 D1 4 A3 C2 A4 6 C3 7 A5 t E0 5 statisches Segment C4 t dynamisches Segment Kommunikationszyklus 45 / 49 FlexRay Startup frame indicator Sync frame indicator Null frame indicator Payload preamble indicator reserved Format eines Frames durch Header CRC gesichert Frame ID Payload Length Header CRC Cycle Count 11 Bits 7 Bits 11 Bits 6 Bits Header Segment Data 0 Data 1 Data 2 0...254 Bytes Payload Segment Data n CRC CRC CRC 24 Bit Trailer Segment FlexRay-Frame: 5+(0...254)+3 Byte (nach: FlexRay Consortium: FlexRay Communications System Protocol Specification. Version 2.1, Revision A, 2005, S. 90) 46 / 49 FlexRay Anmerkungen zum Frameformat I I Frame ID bestimmt den Slot Payload Length enthält Anzahl Bytes des Payload Segmentes, dividiert durch 2 I I I im statischen Segment konstant und gleich für alle Knoten im dynamischen Segment variabel (für verschiedene Knoten und Zyklen) Header (20 Bit) durch extra CRC (11 Bit) geschützt; Hamming-Distanz von 6 47 / 49 FlexRay Synchronisation 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 Uhrenwerte I von den verbleibenden Werten wird das arithmetische Mittel aus Minimum und Maximum gebildet (= fault-tolerant midpoint) I Jennifer Lundelius Welch, Nancy Lynch: A New Fault-Tolerant Algorithm for Clock Synchronization. Information and Computation, Nr. 77, 1988, S. 1–36 48 / 49 Zusammenfassung Was haben wir gelernt? Vor- und Nachteile von Medienzugriffsverfahren: I CSMA/CD I VTCSMA I Token-basierte Verfahren I TDMA I Minislotting 2 typische Beispiele für Feldbusse I CAN I FlexRay Was fehlt? I Echtzeitaspekte des Internet I Time-Triggered Architecture (TTA) 49 / 49