Übersichtwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-11/11-BS-IPC-2.pdfBetriebssysteme – WS 2015/16 - Teil 11/IPC 3 Grundbegriffe • Interprocess-Kommunikation = Austausch

2Betriebssysteme – WS 2015/16 - Teil 11/IPC

Übersicht

• Grundbegriffe

• Shared Memory

• Pipelines

• Messages

• Ports

• Sockets


Grundbegriffe

• Interprocess-Kommunikation = Austausch von Daten über einen Kanal zwischen Prozessen bzw. Threads innerhalb eines Systems

• Ein Kanal realisiert in der Regel einen Datenstrom in einer Richtung, so dass für eine bidirektionale Verbindung zwei Kanäle erforderlich sind.

• Schema:

T1 T2

Queue

D1

D1

D3

D2

D4

write() read() T1 T2


Einteilung I

Interprozess-Kommunikation

speicherbasiert

SignaleExceptions

strombasiert nachrichtenbasiert

SharedMemory

PipeNamed Pipe

MessagesSockets


Einteilung II

• Anzahl der Teilnehmer– Unicast

– Multicast

• Richtung– Unidirektional

– Bidirektional

• Entfernung der Teilnehmer– Im selben Virtuellen Speicher

– Im selben System

– Zwischen Systemen


Shared Memory I

• Beide Kommunikationspartner befinden sich im selben RAM.

• Unterscheidung zwischen:(a) Zwei Threads innerhalb eines Prozesses

(b) Zwei Prozesse

• VM = Virtueller per MMU realisierter Adressraum

Thread1 Thread2

ProzessVM

Prozess1 Prozess2VM VM


Shared Memory II mit MMU

Code Heap Stack

Prozess1

Code Heap Stack

Prozess2

VirtuellerSpeicher

RealerSpeicher

Abbildungdurch MMU


Bemerkungen

• Die Segmente der Prozesse werden in gleichgroße Seiten (Pages) meist 4 KByte lang aufgeteilt.

• Die Memory Management Unit (MMU) bildet diese Seiten in beliebiger Anordnung in den RAM ab.

• Mehrere virtuelle Seiten werden gemeinsam auf denselben Bereich abgebildet; das ist der gemeinsam benutzte Speicher (Shared RAM).

9AVS – WS 2015/16 - Teil 6/IPC

Producer/Consumer mit Monitoren I

ConsumerProducer

Zirkulärer Puffer

• Producer:– In einen freien Bereich werden Daten geschrieben.

– Dann werden diese vom Producer für den Consumer frei gegeben.

• Consumer:– Die vom Producer geschriebenen Daten werden entnommen.

– Der nun ausgelesene Bereich wird für den Producer frei gegeben.

Die Producer/Consumer-Mechanismen gehören zu den Standard-Verfahrender Kommunikation zwischen Threads bzw. Prozessen.


Idee des Zirkulären Puffers II

• MOD ist der Modulo-Operator, dessen Anwendung dafür sorgt, dass die beiden Indices in und out sich immer innerhalb der erlaubten Array-Grenzen bewegen.

• Es gibt folgende Bedingungen:1)Der Puffer ist dann leer, wenn gilt: in = out

2)Der Puffer ist dann voll, wenn gilt: in+1 MOD size = out

3)Wenn beide Bedingungen nicht gelten ist der Puffer gefüllt.

• Um die Implementierung zu vereinfachen, wird in der Variablen count die Anzahl der belegten Elemente vermerkt.

• Wenn nur mit in und out gearbeitet wird, dann muss in auf das letzte in die Queue gebrachte Element zeigen und unmittelbar vor dem Hineinbringen eines weiteren Elements erhöht und auf die zweite Bedingung geprüft werden.

• Statt eines Array mit den langsamen Indizierungen wird häufig mit Pointern in ein Array gearbeitet.


Producer/Consumer mit Monitoren II – Teil 1

MONITOR Buffer { elem[0..size-1] buffer;

int count:= 0; int in:= 0, out:= 0; condition NotEmpty, NotFull;

PROC write(elem what) { IF count = size THEN waitcond(NotFull); FI buffer[in]:= what; in:= (in+1) MOD size; count++; signalcond(NotEmpty);

}


Producer/Consumer mit Monitoren III – Teil 2

elem FUNC read(){

IF count = 0 THEN waitcond(NotEmpty); FI what:= buffer[out]; out:= (out+1) MOD size; count--; signalcond(NotFull);

return(what);

}}

Dies ist eine typische Ring-Puffer-Lösung zur Interprozesskommunikation.


Bemerkungen I

• Es gibt zwei Bedingungsvariablen:– NotEmpty symbolisiert die Bedingung, dass der Puffer nicht leer ist,

d.h. es ist irgendetwas enthalten

– NotFull symbolisiert die Bedingung, dass der Puffer nicht vollständig gefüllt ist, d.h. es gibt noch Platz

• Wenn nun ein Thread etwas in den Puffer schreiben will, muss vorher Platz da sein. Ist der Puffer voll, legt er sich auf das Ereignis, dass mindestens für ein Element Platz ist, schlafen: waitcond(NotFull)

• Wenn ein Thread etwas aus dem Puffer lesen will, muss mindestens ein geschriebener Eintrag vorhanden sein. Wenn nicht, so legt er sich auf das Ereignis schlafen, dass etwas in den Puffer geschrieben wurde: waitcond(NotEmpty)

• Die entsprechenden Threads, die lesen bzw. schreiben, wecken die wartenden Threads auf: signalcond(NotFull) und signalcond(NotEmpty)


Bemerkungen II

• Monitore werden mit den vorgestellten Mitteln: p(), v() etc. implementiert.

• Regeln– Kein Thread sollte sich lange in einem Monitor aufhalten.

– Ein Ausschluss sollte nicht zu lange erfolgen.

• Schachteln von Monitoren kann zu Deadlocks führen.

• Threads, die sich in geschachtelten Monitore befinden, sollten höher priorisiert werden, damit sie schneller die Monitore frei geben.

• Um die Modulo-Operation schnell ausführen zu können, wird in dr Praxis für die Array-Größe eine 2er-Potenz genommen, z.B. 32. Dann wird die %-Operation durch Ausmaskierung der unteren Bits realisiert.


Dasselbe noch einmal ohne Monitore I

CLASS Buffer { elem[0..size-1] buffer; int in:= 0, out:= 0; Semaphore mutex:= 1; Semaphore empty:= size; Semaphore full:= 0;

PROC write(elem what) { p(empty); p(mutex); buffer[in]:= what; in:= (in+1) MOD size; v(mutex); v(full); }

elem FUNC read(){ p(full); p(mutex); what:= buffer[out]; out:= (out+1) MOD size; v(mutex); v(empty); return(what); }}KA= kritischer Abschnitt

KAKA


Erklärungen

• Hier werden Integer-Semaphoren verwendet.

• Die initiale Zahl gibt die Anzahl der Threads an, die den kritischen Abschnitt gleichzeitig betreten dürfen.

• Bisher hatten wir binäre Semaphoren mit dem initialen Wert von 1 bzw. True.

• Die eine Semaphore (empty) zählt die freien Bereiche, die andere (full) die belegten Bereiche. Zwei der Semaphoren werden hier zum Zählen der freien Ressourcen benutzt.P() erniedrigt de Zähler, v() erhöht ihn. Ein Prozess wird schlafen gelegt, wenn der Zähler vor dem Erniedrigen 0 ist.

• Die dritte Semaphore (mutex = mutual exclusion) ist eine binäre Semaphore und erlaubt nur einem Thread die Manipulation der Queue.


Bewertung – Shared Memory

• Standard-Methode bei der Kommunikation zwischen Threads

• Sehr effizient (kein Kopieren)

• Synchronisation liegt in der Hand der Programmier(innen)Quelle vieler Fehler

• Kein/Kaum Unterstützung durch Compiler/Programmiersprachen

• Ein falscher Pointer: Tod für alle Threads


Zusammenfassung des Bisherigen

T1 T2

Queue

D1

D1

D3

D2

D4

write() read()Abstraktion

• Die Realisierung wird in einem Abstrakten Datentyp, z.B. einer Klasse, versteckt.

• Die Queue liegt aber immer noch innerhalb des Virtuellen Speichers der Beteiligten.


Über das Betriebssystem I

T1 T2

Queue

D1

D1

D3

D2D4

Betriebssystem

Prozesse/Threads

read()write()

Manager

create()

destroy()

pipe()

• Derartige Queues werden Pipes (Pipelines) genannt.

• In Unix werden diese im Shell mit einem senkrechten Strich ausgedrückt, z.B. "ls | more".


Über das Betriebssystem II

• Der pipe-Syscall erzeugt eine Queue, die mit dem Schließen der Enden (close) wieder zerstört wird.

• In die Queue wird mit write() geschrieben, aus ihr mit read() gelesen.

• Beide Operationen sind wartend, in dem Sinne, dass– beim read() gewartet wird bis etwas in der Pipe ist,

– beim write() gewartet wird bis Platz in der Pipe ist.

• Über Pipes wird üblicherweise zwischen Prozessen kommuniziert, es geht aber auch zwischen Threads eines Prozesses.


Pipelines über das Dateisystem I

T1

QueueBetriebssystem

Prozesse/Threads

read()write()

Manager

create()

destroy()

open() Write

QueueQueue

Im Dateisystem werden die Queuesangelegt und im Kernel realisiert: named pipe genannt

open() Read

T2


Pipelines über das Dateisystem II

• Die Enden einer Pipe haben nun einen Namen, der in die Namen des Dateisystems integriert ist.

• Damit ist die Existenz einer Pipe unabhängig von der Ausführung eines Prozesses.

• Pipes liegen im RAM und werden mit Terminieren bzw. Schließen der Verbindung zerstört.

• Named Pipes werden im Dateisystem angelegt und erst dann zerstört, wenn sie gelöscht werden. Damit realisieren sie allgemeine Schnittstellen zu Prozessen.

• Die Semantik von Pipes und Named Pipes ist so in Unix-Systemen realisiert.


Pipelines über das Dateisystem III

Server1

Dateiname

Client2

Client1

ClientN

write()

write()

write()

read()

pipe

• Server werden über den Namen einer Queue angesprochen.

• Aber: die Verbindung zwischen Queue (Pipe) und Server ist lose, d.h. es können ein oder mehrere Server an den Pipe-Ausgang anschließen.

• Der (Datei-)Name der Pipe ist daher kein Service-Name.


Feste Verbindung: Port I

Server1

Portname

Client2

Client1

ClientN

send()

send()

send()

receive()

Queue

Port

• Wenn eine feste Verbindung zwischen Schnittstelle und Server als Schnittstelle zum Server besteht, wird von Ports gesprochen.

• Das Schreiben in ein Port wird send() und das Lesen receive() genannt.

• Die ausgetauschten Daten werden Messages (Nachrichten) genannt.


Feste Verbindung: Port II

• Dies ist die höchste Abstraktion.

• Für die Prozesse/Threads ist nicht erkennbar, ob der Partner im selben System oder in einem anderen System liegt.

• Unter Unix– gibt es das Message-Konzept für Kommunikation innerhalb eines

Systems in den Varianten der synchronen und asynchronen Kommunikation

– gibt es das Socket-Konzept für Kommunikation zwischen Systemen,dies geht auch im Spezialfall innerhalb eines Systems


Sockets

• Socket = Sockel = Begriff aus dem UNIX-Kernel für Schnittstellen zu anderen Prozessen auf demselben oder fremden Systemen (über ein Netz)

Server1

Socket

Client1

receive()

Betriebssystem

Socket

send()

Betriebssystem

TCP/IP-Verbindung


Bewertung – Nachrichtenbasierte Kommunikation

• Standardverfahren bei Kommunikation zwischen Systemen;Alternative Sockets mit offenen Strom

• Hoher Abstraktionsgrad

• Passt ins Konzept von Objekt-Orientierten Sprachen – wird aber von denen nicht/kaum unterstützt

• Ineffizient, da fast immer mit Kopieren gearbeitet wird – wenn innerhalb des Systems kommuniziert wird

• Das Beste ist wohl eine nachrichtenbasierte Kommunikation mit Hilfe von Shared Memory, da bei hoher Abstraktion eine hohe Effizienz realisiert wird.


Synchron und Asynchron I

• send()– Synchron: der Sender wartet solange, bis der Empfänger empfangen hat

– Asynchron: der Sender setzt seine Nachricht ab und arbeitet weiter; diese wird in einer Queue zwischengespeichert

• receive()– Synchron: der Empfänger wartet solange, bis eine Nachricht für ihn

vorhanden ist

– Asynchron: der Empfänger empfängt eine Nachricht, falls sie da ist, ansonsten arbeitet er weiter.

• Prinzipiell sind alle vier Kombinationen möglich. Implementiert werden aber nicht unbedingt alle: Meistens ist send() blockierend oder nicht blockierend (no-wait-send), während receive() immer blockierend ist.

• Bei den asynchronen Varianten ist eine Queue als Zwischenspeicher erforderlich.

Synchron und Asynchron betreffen die (zeitliche) Entkopplung.


Synchron und Asynchron II

• Synchrone Operationen und blockierend– send() und receive() blockieren bis der Partner bereit ist

– Direkte Kommunikation

– Keine Zwischenspeicherung der Nachricht notwendig falls innerhalb desselben Systems sich der Partner befindet

– Implizite Empfangsbestätigung

– Einfach und schnell

– Dieses Verfahren wird auch Rendezvous genannt.

Blockierend betrifft die Möglichkeit eines Wartens.


Synchron und Asynchron II

• Asynchrone Operationen und möglichst nicht blockierend– Queue erforderlich

– Wenn Sender terminiert, entsteht beim Empfänger kein Deadlock

– Empfangsbestätigung kompliziert

Aber! Wenn die Queue voll ist oder kein Speicher für die Nachrichtverfügbar ist, ist das asynchrone Senden blockierend.

• Asynchrone Operationen und nie blockierend

Aber! Wenn die Queue voll ist oder kein Speicher für die Nachrichtverfügbar ist, scheitert das asynchronen Senden; es könnte dann eineException geworfen werden.


Send-receive-reply I

Sender Empfänger

send()

receive()

reply()

Rendezvous mit Antwort durch reply().


Send-receive-reply II

• reply() ist die Operation, mit der der Empfänger eine Rückantwort aufgrund einer Nachricht zurückschickt.

• Da der Speicher für die Nachricht vorhanden ist, kann er auch zur Antwort benutzt werden. Das bedeutet, dass der reply()-Aufrufer bei der Speicher-Allokation meist nicht blockiert.

• Wenn die Rückantwort dagegen durch ein eigenes send() realisiert wird, dann kann der send()-Aufrufer bei der Speicher-Allokation blockieren.


Nach dieser Anstrengung etwas Entspannung....

Schnee, nichts als Schnee – soweit das Auge reicht

Documents

Übersichtwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-11/11-BS-IPC-2.pdfBetriebssysteme – WS 2015/16 - Teil 11/IPC 3 Grundbegriffe • Interprocess-Kommunikation = Austausch