Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen ::

Kommunikation und Synchronisaztion von Prozessen

Lernziele

• Sie beurteilen die Eignung nachrichten- und speicherbasierter Verfahren zur Kommunikation zwischen parallelen Abläufen.
• Sie analysieren Anwendungsprobleme von Unix-Pipes.
• Sie unterscheiden zwei Implementierungsarten von Monitoren.
• Sie erläutern das Grundprinzip eines Rendezvous paralleler Prozesse.
• Sie entwickeln eigene Programme, die Berkeley-Sockets bzw. RPC zur rechnerübergreifenden Datenverarbeitung nutzen.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Taxonomie

Taxonomie

• IPC: Interprocess Communication
• Ein Prozess wartet auf die Terminierung eines anderen (Eltern-Kind Gruppe);
• Ein Prozess wartet auf Daten von einem anderen; Beispiel: Anforderung von Daten eines Web Servers über HTTP (remote) oder ein Prozess waretet auf Daten einer Datenbank; → Kooperation
• Prozesse wollen quasi gleichzeitig (oder zeitlich sehr nahe beiandner) einen gemeinsamen Punkt im Programmfluss erreichen; Barriere
• Prozesse greifen auf geteilte Ressourcen qusi parallel zu und der Zugriff muss sequenzialisiert werden; Wettbewerb
• Prozesse warten auf zeitliche Ereignisse (ist es der gleiche Timer und mehrere Prozesse warten darauf dann ist das IPC)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Taxonomie

Taxonomie

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Taxonomie

Taxonomie

bsdp Überblick über Synchronisation und Kommunikation

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Taxonomie

Taxonomie

• Es wird unterschieden zwischen den zwei Gruppen »Synchronisation« und »Kommunikation«.
• Bei der Kommunikation wird weiter unterteilt in »speicherbasierte Verfahren« und »nachrichtenbasierte Verfahren«.
• Die Kommunikation unterscheidet sich von der Synchronisation, indem explizit Daten zwischen den Prozessen ausgetauscht werden und nicht nur eine Koordination im zeitlichen Ablauf oder Ressourcenzugriff realisiert wird.

IPC-Verfahren aus Sicht der Programmierung

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Taxonomie

Taxonomie

• Jedes der Programmierkonzepte weist bezüglich einer bestimmten Problemklasse seine Vorzüge auf.
• Wesentlich ist jedoch, dass alle Konzepte funktional äquivalent sind, d.h., jedes Konzept kann in seiner Wirkungsweise durch jedes andere nachgebildet werden.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Nachrichtenbasierte Verfahren

Unter nachrichtenbasierten Verfahren fassen wir alle Mechanismen zusammen, die einen Datenaustausch zwischen Prozessen und Threads mithilfe von Systemfunktionen bewerkstelligen.

Allgemeine Aspekte

Datenabgrenzung bei der Kommunikation

Die Datenabgrenzung bei der Kommunikation hängt von der Form der ausgetauschten Daten ab. Diese ist bestimmend für mögliche Lösungen der Datenabgrenzung.

1. Datenaustausch mittels Nachrichten (message passing)
2. Datenaustausch mittels Datenströmen (streaming)
3. Datenaustausch mittels Paketen (packeting)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

• Beim Datenaustausch mittels Nachrichten haben wir eine abgegrenzte Datenmenge bei der Kommunikation in Form der Meldung (message).
  • Die Meldungsgröße kann systemabhängig fest oder variabel sein.

Nachrichtenbasierte Verfahren

• Kommen hingegen für den Datenaustausch Datenströme zur Anwendung, so ist die Nachrichtengrenze für den Sender und den Empfänger unsichtbar.
  • Die übertragbare Datenmenge ist theoretisch unbeschränkt.
  • Typischerweise werden die Dateisystemfunktionen read() und write() für eine stromartige Datenübertragung genutzt.

Beim Datenaustausch mittels Paketen kommen feste, oft standardisierte Datenformate zum Einsatz.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Nachrichtenbasierte Verfahren

• Sie sind im Rahmen von Kommunikationsprotokollen definiert (z.B. IP-Paketformat).
  • Für die Applikationsprogrammierung sind die Pakete nicht sichtbar (transparent).
  • Beim Übertragen der Pakete kann eine Fragmentierung (= Aufteilung in Teilpakete) und eine Defragmentierung (= Zusammensetzen aus Teilpaketen) stattfinden.
  • Dies wird versteckt (hidden) durch die Netzwerksoftware realisiert.

• Der Datenaustausch mittels Paketen ist ein Thema der Computernetze und wird daher hier nicht weiter berücksichtigt. Die zwei verbleibenden Arten des Datenaustauschs wollen wir jedoch anhand von Realisierungsformen kennenlernen.

Synchronität bei der Kommunikation

Unter einer synchronen Kommunikation versteht man den Fall, dass der Sender warten muss, bis der Empfänger zur Entgegennahme der Daten bereit ist (Rendezvous). Bei der asynchronen Kommunikation läuft der Sender hingegen weiter, auch wenn der Empfänger gerade nicht für den Datenempfang bereit ist.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Synchronität bei der Kommunikation

• Bei der synchronen Kommunikation muss entweder der Sender (A1) oder der Empfänger (A2) warten, wenn nicht gerade das Senden und Empfangen zeitlich zusammenfallen.
• Bei der asynchronen Kommunikation (B) kann hingegen das Senden sofort erfolgen, auch wenn der Empfänger nicht gerade für den Empfang bereit ist. Es ist also ein Puffer für die Zwischenlagerung von Daten, ein sogenannter Nachrichtenpuffer, notwendig.

Synchrone und asynchrone Kommunikation

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Synchronität bei der Kommunikation

• Die asynchrone Kommunikation entkoppelt den Ablauf des Senders und des Empfängers und hilft, Geschwindigkeitsunterschiede in der Datenverarbeitung auszugleichen.
  • Genau genommen läuft bei der asynchronen Kommunikation der Sender erst dann weiter, wenn die Nachricht vollständig in einen Zwischenspeicher kopiert wurde.
  • Dies ist in der Abbildung durch die schräg verlaufenden Pfeile angedeutet und gilt auch für den Nachrichtenempfang.

send    (destination, &message);
receive (source,      &message);

Programmierschnittstelle für die synchrone und asynchrone Nachrichtenkommunkation. Bei einer synchronen Art können beide Funktionen den Prozess blockieren. Ein Nachrichtenpuffer message trägt eine Identifikation (Textname, Deskriptor, Handle o.Ä.).

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Synchrone versa Asynchone Kommunikation

bsdp Vergleich von synchroner und asynchroner Kommunikation

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Synchrone versa Asynchone Ein- und Ausgabe

• Auch bei der Grerätekommunikation kann A. vs S. unterschieden werden.

  • Bei der S. Kommunikation muss beim Lesen und Schreiben der Prozess warten bis die Operation ausgeführt wurde (und beim Lesen die Daten verfügbar sind).
  • Bei der A. Kommunikation kann der Prozess eine E/A Operation starten aber mit der Programmausführung fortsetzen. Der Prozess kann auch mehrere E/A Operationen starten.
  • Nur dann ist die Frage wie er mitbekommt wann E/A Operationen ausgeführt wurden (also auch Daten verfügbar sind).

• Viele Programmiersprachen sind vom Paradigma her strikt sequenziell. Es ist nicht möglich mehrer Operationen parallel auszuführen.

• A. E/A ist daher in Virtuellen Maschinen eine gängige Möglichkeit auf der Programmierebene das strikt sequenzielle Paradigma aufrecht zu erhalten und unter der Motorhaube E/A Operationen mit Threads parallel auszuführen.
• Mittels Callback Funktionen können dann erfüllte Operationen ihr Ergebnis wieder an das Programm übermitteln.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Nachrichtenbasierte Verfahren

Synchrone versa Asynchone Ein- und Ausgabe

function callback(status,data) { 
  if (!status)   print("Error:",status) 
  else if (data) processData(data) 
}
send('edu-9.de','mymessage1',callback) // Time 1
send('ag-0.de','mymessage2',callback)  // Time 2
receive('edu-9.de',callback)           // Time 3
receive('ag-0.de',callback)            // Time 4
print('I am finished with my computation. Waiting for I/O completion')
// Time 10: callback(...)
// Time 12: callback(...)

Asynchone E/A mit Callback Funktionen am Beispiel von JavaScript

• Das Problem: Die Callbackhölle, Verschachtelung, und schwierige Fehlerbehandlung.
• Z.B. wenn die zweite Send Operation auf Daten von der ersten Receive Operation warten muss ist eine Verlegung der Send Operation in den Callback Handler notwendig!

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Vergleich von Kommunikationsverfahren

bsdp Vergleich von Kommunikationsverfahren: Speicherbasiert versa nachrichtenbasiert.

Ein Datenaustausch mittels Speicher kann mithilfe von Systemfunktionen erfolgen oder in Selbstverwaltung, nachdem ein gemeinsamer Speicherbereich eingerichtet wurde.

• Bei der Selbstverwaltung muss in der Regel mittels Semaphoren die Koordinierung der beteiligten Threads bzw. Prozesse sichergestellt werden.
• Somit stellt der Einsatz gemeinsamen Speichers meist eine Mischform dar, die sich für den schnellen Transfer großer Datenmengen besonders anbietet.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Geteilter Speicher

• Prozesse können sich über das Betriebssystem einen Speicherbereich teilen.
  • Dieser ist aber nur ein Bytepuffer ohne Datentyp.
  • Ein sinnvoller Datentyp kann mit C durch Typecasting erstellt werden.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Geteilter Speicher

void* create_shared_memory(size_t size) {
  // Our memory buffer will be readable and writable:
  int protection = PROT_READ | PROT_WRITE;
  // The buffer will be shared (meaning other processes can access it), but
  // anonymous (meaning third-party processes cannot obtain an address for it),
  // so only this process and its children will be able to use it:
  int visibility = MAP_SHARED | MAP_ANONYMOUS;
  // The remaining parameters to `mmap()` are not important for this use case,
  // but the manpage for `mmap` explains their purpose.
  return mmap(NULL, size, protection, visibility, -1, 0);
}
...
void* shmem = create_shared_memory(16);
int * counter = (int*)&shmem[0];
*counter=0;
int pid = fork();
if (pid == 0) { // child process
  *counter++;
} else {        // parent process
  *counter--;
}

SHM für zwei Prozesse, hier als "Vererbung" durch das Forking vpn Kindprozessen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Geteilter Speicher

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Geteilter Speicher

• Und das ist das Problem bei SHM Kommunikation: Es gibt keine Programmflusssteuerung! Diese muss dann zusätzlich z.B. mit Semaphoren erfolgen.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Vergleich von Kommunikationsverfahren

Vergleich von Kommunikationsverfahren

Andrew Forney Vergleich von Kommunikationsverfahren: Nachrichtenbasiert versa speicherbasiert.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Verbindungsorientierung

Verbindungsorientierung

• Die Verbindungsorientierung spielt eine Rolle beim asynchronen Datenaustausch, wenn wiederholt Datenübertragungen mit gleichen Kommunikationspartnern anstehen.
• Unabhängig davon, ob man streng abgegrenzte Nachrichten oder einfach Datenströme austauschen will, können zwei Verbindungsformen unterschieden werden.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Verbindungsorientierung

• Der logische Verbindungskanal kann zu jedem Zeitpunkt nur einen Datentransfer in eine Richtung (unidirektional) oder gleichzeitig in beide Richtungen erlauben (bidirektional).
• Der unidirektionale Datenaustausch (mit alternierender Richtung) wird als Halbduplex-, der bidirektionale Datenaustausch als (Voll-) Duplexbetrieb bezeichnet.
• Ist generell nur eine Kommunikationsrichtung möglich, so handelt es sich um einen Simplex-Betrieb.

Halb- und Vollduplex-Betrieb

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Verbindungsorientierung

• Ein verbindungsloser (connectionless, datagram-oriented) Datenaustausch benutzt für jeden einzelnen Datentransfer die Identität des Empfängers als Adresse.
• Es können sofort Daten übertragen werden, ohne dass zuerst ein Verbindungskanal angelegt werden muss.

bsdp Vergleich von verbindungsorientierter und verbindungsloser Kommunikation.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Empfängeradressierung

Empfängeradressierung

• Neben der Frage wie zwei Prozesse miteinander kommunizieren können und sich "finden" kann man adressierte Kommunikation in verschiedene Klassen einteilen.
• Diese Klassen bestimmen die Empfänger von Nachrichten (lösen aber nicht das Problem der eindeutige Adressierung der Prozesse an sich)

Empfängeradressierung bei der Kommunikation

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Empfängeradressierung

Empfängeradressierung

Bei einem unicast (1:1) wird genau ein bestimmter Empfänger angesprochen. Bei einem multicast (1:m) wird eine definierte Gruppe an Empfängern (m) adressiert. Der anycast übermittelt Daten an irgendeinen Empfänger, mindestens einen einzigen (1:1..n). Der broadcast schließlich geht an alle Empfänger (n), die sich finden lassen (1:n). Welche Empfängeradressierung eine Lösung unterstützt, ist implementationsabhängig. Meistens ist es aber nur der unicast.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Empfängeradressierung

Prioritäten

Erfolgen bei einem Datenaustausch alle Übertragungen mit der gleichen Priorität, so werden sie bei einer Zwischenpufferung in der FIFO-Reihenfolge abgelegt.

• Können unterschiedliche Prioritäten benutzt werden, so ist es möglich, neue Daten vor alten Daten in den Nachrichtenpuffer einzutragen. Bei Datenströmen sind Prioritäten meistens nicht sinnvoll, daher ist diese Möglichkeit in der Regel dem Meldungsaustausch vorbehalten.
• Im einfachsten Fall sind zwei Prioritäten definiert, nämlich »normal« und »dringend«. Anspruchsvollere Lösungen können feinere Prioritätsabstufungen anbieten.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Empfängeradressierung

Anwendungsszenario Client/Server

Der gepufferte Nachrichtenaustausch eignet sich zur Realisierung eines Client/Server-Betriebs.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Empfängeradressierung

Anwendungsszenario Client/Server

Client/Server-Prinzip mittels Meldungen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Pipe als Verbindungskanal zweier Prozesse

Pipe als Verbindungskanal zweier Prozesse

• Eine namenlose Pipe für die Kommunikation zweier Prozesse anzulegen erfordert insgesamt drei Prozesse und die folgenden Schritte:

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Pipe als Verbindungskanal zweier Prozesse

Pipe als Verbindungskanal zweier Prozesse

int main()
{
  int fds[2];                             // Für Pipe-Dateideskriptoren
  char *text = "Hallo da!\n";             // Zu transferierender Text
  char buffer [5];                        // Lesepuffer
  int count, status;                      // Leseanzahl bzw. Endstatus
  pipe(fds);                              // Unnamed pipe erzeugen
  if (fork() == 0) {                      // Kindprozess 1:
     dup2(fds[1], 1);                     // stdout auf Pipe-Eingang legen
     close(fds[0]);                       // Pipe-Ausgang schließen
     write(1,text,strlen(text)+1);        // Text in Pipe schreiben
  } else if (fork() == 0) {               // Kindprozess 2:
     dup2(fds[0], 0);                     // Pipe-Ausgang auf stdin legen
     close(fds[1]);                       // Pipe-Eingang schließen
     while ((count = read(0, buffer, 4)) != 0) { // Wiederholt auslesen
        buffer[count]= 0;                 // »string terminating zero«
        printf("%s", buffer);             // Laufend ausgeben
     }
  } else {                                // Elternprozess:
     close(fds[0]);                       // Pipe-Ausgang schließen
     close(fds[1]);                       // Pipe-Eingang schließe
     wait(&status);                       // Warte auf erstes Kind
     wait(&status);                       // Warte auf zweites Kind
  }
  exit(0);
}

Ein einfaches Zwei-Prozess-Kommunikationssystem über Pipers

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Pipe als Verbindungskanal zweier Prozesse

Benannte Pipes

Hier werden die Pipes als "virtuelle" Dateien über ds Dateisystem von Prozessen mit üblichen Read und Write Operationen geteilt.

Client/Server-Konstellation mit benannten Unix-Pipes

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Message Queues

Message Queues

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Message Queues

Message Queues

bsdp Aufbau einer Message Queue

Eine Meldung besteht immer aus den zwei Teilen msg_typ und msg_txt, die den Meldungstyp und den Meldungsinhalt repräsentieren. Wie in einer eigenen Applikation ein Meldungstyp deklariert werden kann, zeigt nachfolgendes Beispiel:

struct meine_nachricht {
  long msg_typ;
  char msg_txt[100];
}

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Mutualer Ausschluss und Semaphor

Bisher wurde nachrichtenbasierte Kommunikation eingeführt. Nebem dem Nachrichtenaustausch (Kooperation) ist aber auch die Konfliktlösung bei Wettbewerb wichtig, also eine sequenzielle Synchronisation.

Wir unterscheiden wieder zwei Arten der Prozessinteraktion:

1. Kooperation, d.h. Produzenten-Konsumenten Anwendungen
2. Wettbewerb, d.h. Konflikte bei der Nutzung von geteilten Ressource.

Der Semaphor kann zur Synchronisation für beide Arten verwenden werden.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Mutualer Ausschluss und Semaphor

bsdp Semaphor mit einer Identität (Instanzenbezeichnung), den Operationen P/V und den Attributen Zähler (für Marken) und Warteschlange (für Prozesse)

Der Semaphor implementiert einen geschützten Zähler (Marken, Tokens) mit einer Prozesswarteschlange:

1. Invariante: Der Zähler darf nie negativ werden
2. Prozesse werden blockiert die diese Invariante verletzen würden
3. Es gibt zwei Operationen: V(+) oder Up und P(-) oder Down. Beide Operationen verändern den Zähler um den Wert 1.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Mutualer Ausschluss und Semaphor

(Oben) Definition der P-Operation: Der aufrufende Prozess erhält entweder sofort eine Marke oder muss warten, bis eine verfügbar wird (dazu wird er an die Warteschlange des Semaphors angefügt). (Unten) Definition der V-Operationen: Der aufrufende Prozess übergibt eine Marke entweder dem Semaphor oder einem am Semaphor wartenden Prozess, der damit wieder weiterlaufen kann.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Semaphortypen

Es existieren zwei Grundtypen von Semaphoren:

1. Binärer Semaphor (binary semaphore, mutex): Es sind genau 0 oder 1 Marke erlaubt ⇒ Lösung des mutualen Ausschlussproblems (entweder oder), Mutex Lock
2. Zählsemaphor (counting semaphore, general semaphore): Es sind beliebig viele Marken erlaubt, dies stellt die universellere Form dar.

Unteilbarkeit von P/V

Die Unteilbarkeit der P- und V-Operationen muss durch ihre Implementierung sichergestellt werden. Mögliche Lösungen dafür sind:

• Ausschalten der Prozessorneuzuteilung für die Operationsdauer
• Vorübergehend höhere Priorität als alle anderen Prozesse
• Ausschalten aller Interrupts (= Gewaltlösung) während der P- und V-Operationen; ist aber nur für Einprozessorsysteme ausreichend
• Verwendung atomarer Prozessorinstruktionen (v.a. der TAS-Befehl, siehe S. 201)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Aktives oder passives Warten

Eine zweite Implementierungsfrage betrifft die Art des Wartens an der Semaphor-Warteschlange.

• In der Regel heißt dies, dass der Prozess für die Dauer des Wartens blockiert wird, d.h. die CPU freigibt und in den Zustand »Wartend« wechselt (passives Warten). Dies erlaubt anderen Prozessen die Wartezeit zu nutzen.

• Unter speziellen Bedingungen kann jedoch ein aktives Warten die bessere Lösung sein:

  • Sehr kurze Wartezeit: Der Zeitbedarf für ein Blockieren kann größer sein als für ein aktives Warten. Das Blockieren und spätere Aufwecken des Prozesses beinhaltet zwei Prozessumschaltungen, für die eine zwar kleine, aber doch gegebene Zeitdauer nötig ist.
  • Multiprozessorsysteme: Da eine echte Parallelität möglich ist, wird in verschiedenen Situationen die Wartezeit sehr klein sein. Dies macht ebenfalls ein Blockieren unattraktiv.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Aktives oder passives Warten

Für diese speziellen Situationen bieten manche Betriebssysteme einen speziellen Semaphortyp an, der als Spinlock bezeichnet wird (ein passender deutscher Begriff fehlt).

• In einer ersten Variante wartet ein Spinlock beliebig lange in einer aktiven Warteschlange.
  • Dies ist unattraktiv, wenn nicht bekannt ist, wie lange das Warten dauert.
• Eine zweite Variante wartet in einer aktiven Warteschleife, kennt dafür aber ein Zeitlimit.
  • Wird dieses überschritten, so wird ein passives Warten, d.h. ein Blockieren des Prozesses, durchgeführt.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Wartereihenfolge

• Eine dritte Implementierungsfrage betrifft die Einreihung in der Semaphor-Warteschlange.
  • Erfolgt dies nach dem FIFO-Prinzip, so ist sichergestellt, dass jeder Prozess in endlicher Zeit drankommt, sofern die einer P-Operation folgende V-Operation stets in endlicher Zeit ausgeführt wird.
  • Wird für die Einreihung die Prozesspriorität benutzt, so besteht die Gefahr, dass niederpriore Prozesse nie drankommen (verhungern), wenn hochpriore Prozesse genügend oft die P-Operation aufrufen.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Anwendung der Semaphoren

Eine hervorragende Bedeutung fällt Semaphoren bei der Absicherung kritischer Bereiche zu, indem sie den wechselseitigen Ausschluss sicherstellen.

• Da ein kritischer Bereich jederzeit von maximal einem Prozess betreten werden darf, kommt ein binärer Semaphor zum Einsatz.
  • Betritt ein Prozess einen kritischen Bereich, so sperrt er diesen mithilfe des Semaphors ab.
  • Ein so eingesetzter Semaphor wird manchmal als Sperre (lock), die P- und V-Operationen als Sperren (lock) und Freigeben (release) bezeichnet.

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Anwendung der Semaphoren

• Konkret beinhaltet die Absicherung eines kritischen Bereichs die folgenden Elemente:

1. Den Semaphorzähler mit 1 initialisieren (eine Berechtigungsmarke bereitstellen, d.h. kritischer Bereich als frei markieren)
2. Die P-Operation vor dem Eintritt in den kritischen Bereich ausführen (= reservieren bzw. Berechtigungsmarke beziehen)
3. Die V-Operation beim Austritt aus dem kritischen Bereich ausführen (= freigeben bzw. Berechtigungsmarke an Semaphor zurückgeben)
4. Das Betriebssystem blockiert den Prozess bei der P-Operation, wenn die Berechtigungsmarke bereits vergeben ist
5. Das Betriebssystem weckt einen wartenden Prozess bei der nächsten V-Operation, die auf diesem Semaphor ausgeführt wird (da Berechtigungsmarke nun verfügbar ist)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Anwendung der Semaphoren

Absicherung kritischer Bereiche mittels Semaphor (Beispiel)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Anwendung der Semaphoren

Eine weiter Anwendung ist Kooperation ind Produzenten-Konsumenten Systemen mit einem Datenpuffer (Kapazität N Datensätze).

• Eine Menge von Prozessen P schreibt Daten in den Puffer (atomar)
• Ein oder mehrere Prozesse C lesen dei Daten aus dem Puffer (atomar) für weitere Verarbeitung

• Es gibt zwei Situationen die mit Semaphoren abgesichert werden können:

  • Der Puffer ist leer ⇒ Semaphor Empty(0)
  • Der Puffer ist voll ⇒ Semaphor Full(N)

• Die Operationen (Write, Read) verändern dann die Semaphoren und können blockieren (; ist ein Zeitschritt):

  • Read() ⇒ P(Empty) ; V(Full)
  • Write() ⇒ P(Full) ; V(Empty)

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Anwendung der Semaphoren

Synchronisierte Datenwarteschlange mit Semaphoren für Produzenten-Konsumenten Systeme

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Und es geht schief: Das Problem der fünf dinierenden Philosophen ist ein Beispiel für Deadlocks (Verklemmung) in verteilten und parallelen (asynchronen) Systemen mit Kommuniaktion!

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Implementierung mit Kanälen

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

Implementierung mit Kanälen

Protokoll: <ID>+ für V und <ID>- für P Operation und ID als Prozessnummer 1,2,3,..,N

channel req,ack1,ack2,... ;   waiters = [] ; counter = INIT
while (!terminate) {
  received=read(req)
  messages=split(received,2) // 1+2- => [1+,2-]
  for(message of messages) {
    switch (message[1]) {
      case '+': 
        if (length(waiters)) {
          next=head(waiters); waiters=tail(waiters)
          write(ack[next],'!')
        } else {
          counter++;
        } 
        write(ack[Number(message[0]),'!') ; break
      case '-':
        if (counter>0) {
          counter--;
          write(ack[Number(message[0]),'!')
        } else {
          push(waiters,Number(message[0]))
        } ; break
    }
  }
}

Der Semaphor Master Prozess

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Mutualer Ausschluss und Semaphor

function P() { 
  write(req,String(myid)+'-')
  reply=read(ack[myid])
}
function V() {
  write(req,String(myid)+'+')
  reply=read(ack[myid]) 
}

Der Semaphor Klienten Prozess

Stefan Bosse - Grundlagen der Betriebssysteme - Modul Y Kommunikation und Synchronisaztion von Prozessen :: Zusammenfassung

Zusammenfassung