Modul: Programmierung (B-PRG) Grundlagen der ... · Abschnittskontrolle + Flusskontrolle durch Semaphore. 9 Prozess-kommunikation Grundlagen der Programmierung 1 - Teil 3 R.Brause:

1

Modul: Programmierung (B-PRG)Grundlagen der Programmierung 1 – Teil 3

ProzessProzess--synchronisationsynchronisation

Prof. Dr. R. BrauseAdaptive SystemarchitekturInstitut für Informatik Fachbereich Informatik und Mathematik (12)

Grundlagen der Programmierung 1 - Teil 3 R.Brause: Synchronisation und Kommunikation Folie 2

Race conditions

Beispiel: KontoführungParalleler Zugriff auf globale Variable

Parallele Prozesse von vielen Benutzern arbeiten gleichzeitig auf den Daten.

Falls gleichzeitig zwei Benutzer auf das gleiche Konto einzahlen möchten, so kann es sein, dass der Kontostand hinterher nicht stimmt.

Ein solcher Fehler wird von keinem Kunden toleriert!

Zeit

15:00 UhrKonto A= 300 €

15:01

15:04

15:03

15:02

Konto A = 200 €

500 € einzahlen 100 € abheben

B := read(A)

B := B + 500

B write(A)

C := read(A)

C := C -100

C write(A)

Eine Fehlbuchung tritt nur auf, wenn Prozess den Prozess überholt („race condition“)

2


Race conditions

Beispiel: Warteschlangeneintrag eines PCB

Einhängen A Aushängen B(1) Lesen des Ankers: PointToB (1) Lesen des Ankers: PointToB(2) Setzen des NextZeigers:=PointToB (2) Lesen des NextZeigers:PointToC(3) Setzen des Ankers:=PointToA (3) Setzen des Ankers:=PointToC

Problem: („Race conditions“: kontextbedingt, nicht-wiederholbare Effekte durch „überholende“ Prozesse) z.B.a) Unterbrechung beim Aushängen von B durch Einhängen von A

⇒ Prozeß A ist weg! b) Unterbrechung beim Einhängen von A durch Aushängen von B

⇒ Prozeß B bleibt erhalten!

Anker B CPointToB PointToC

APointToA

PCB(B) PCB(C)

PCB(A)


Lösung: Signale und Semaphoren

Peterson: Synchronisierung durch Signale (Interesse)

Allgemein: Das SemaphorSemaphor (Signalbarken, Dijkstra 1965)

Passieren Passieren P(s)P(s) waitFor (signal)Aufruf vor krit. Abschnitt, Warten falls besetzt

Verlassen Verlassen V(s)V(s) send (signal)Aufruf nach krit. Abschnitt, Aktivieren eines wart. Prozesses

Beispiel: paralleles Hochzählen z = 1, 2, 3, ... z global

Prozeß 1 Prozeß 2. . . . . .

P(s) P(s)

V(s) V(s)

. . . . . .

z :=z+1; WriteInteger(z)z :=z+1; WriteInteger(z)

warten

freigeben

3


Implementierung busy wait

Problem: spin locks können fairness verletzen: Prozesse hoher Prio im spin lock vs. niedr. Prio im krit. Abschnitt

Software Pseudo-Code Semaphor = Zähler, initial s=1

def P(s):while s<=0 :

UnunterbrechbarUnunterbrechbar !!NoOp;

s = s-1;

def V(s):s = s+1;

UnunterbrechbarUnunterbrechbar !!

krit. Abschnitt


Implementierung Schlafen

class Semaphor : value;list;

Software Pseudo-Code Initial: s.value = 1Datenstruktur

def P(s):s.value = s.value-1;if s.value < 0 :

einhängen(MyID,s.list); sleep;

def V(s):if s.value < 0 :

PID = aushängen(s.list); wakeup(PID);

s.value = s.value +1;

Problem: Ununterbrech-barer Code nötig!

4


Lösung: Atomare Aktionen

Beispiel: GeldtransaktionSie überweisen 2000 €.

Abbuchung 2000 € Empfänger-Gutbuchung 2000 €

Wo ist das Geld? Keine oder erneute Überweisung = Verlust!

Forderung: „Atomare Aktion“Entweder vollständige Transaktion oder gar keine !(bei Abbruch „roll back“ auf vorher definierten Zustand)

Computerabsturz !


HW-Implementierung: Atomare Aktionen

Interrupts ausschalten (Probleme: timer, power failure, I/O)

Atomare Instruktionsfolge

z.B. Fetch And Add (fetch and add value) Abfrage der akt. Anzahldef fetchAndAdd(s, value) :

tmp = s; s = tmp + value; return tmp;

Test And Set (test and set lock) Abfrage: bin ich erster?def TestAndSet(s) :

tmp = s; s = true; return tmp;

wird unkritisch nur von einem Prozess zurückgesetzt

5


memory

Prozesse

Semaphoren: Unix

lockf Sperren Dateizugriff P(s) lock file

msem_init Semaphorinit. zumSpeicherzugriffmsem_lock Sperren eines Semaphors P(s)msem_unlock Entsperren eines Semaphors V(s)msem_remove Entfernen eines Semaphors

semctl Semaphorkontrolloperationensemget hole Semaphorwertsemop Semaphoroperation


Semaphoren: Windows NT

ProzesseProzesseCreateSemaphore() ErzeugenOpenSemaphore() InitialisierenWaitForSingleObject(Sema,TimeOutVal) P(s)ReleaseSemaphore() V(s)

KernprozesseKernprozesseSpin locks: keine Referenzen zu Disk-Speicher, keine traps & syscalls

ThreadsThreadsSemaphore = Type CRITICAL_SECTIONInitializeCriticalSection(S)EnterCriticalSection(S) P(s)LeaveCriticalSection(S) V(s)

6


Semaphoren: Python

Class mutex() Datenstruktur mit binärem Semaphor s+ Warteschlange

Methoden

test() Ist s gesetzt?

testandset() Setze s atomar. RET: War s ungesetzt?

lock(KritAb,arg) Setze s und führe KritAb(arg) aus.s gesetzt: KritAb→Warteschlange

unlock() Setze s zurück.

Wenn Warteschlange ≠ 0, führe stattdessen ersten KritAb aus und rücke Wartschlange auf.


Semaphoren: Java

Konstruktsynchronized (<expression>) <statement>

Thread wartet, bis <expression> frei ist.

Innerhalb eines synchronized-Bereichs kann man

zusätzlich mit den Methoden wait() auf ein Signal

warten, das mit notify() gesendet wird.

7


Synchronisation von Prozessen

Präzedenzgraph

Implementierung mit Semaphoren

PROCESS A: TaskBodyA; V(b); V(c);

PROCESS B: P(b); TaskBodyB; V(d1);V(e); PROCESS C: P(c); TaskBodyC; V(d2); PROCESS D: P(d1); P(d2); TaskBodyD; PROCESS E: P(e); TaskBodyE;

Globale Variable b, c, d1, d2, e mit 0 initialisieren.

B E

A

C D

d1

d2

eb

c


Synchronisation von Prozessen

Rendez-vous-Konzept (Ada)Warten ohne Pufferung aufeinander

Senderprogramm

...

send(Empfänger,Msg);

...

Empfängerprogramm

...

receive(Sender,Msg)

...

8


Synchronisation Erzeuger-Verbraucher

Problem: race condition innerhalb der Flusskontrolle:Bei Umschaltung nach „used=0“ auf Erzeugererfolgt wakeup + Pufferfüllung, dann ewiges Schlafen vom Erzeuger und dann auch vom Verbraucher.

Erzeuger

LOOP

produce(item)

IF used=N THEN sleep();

putInBuffer(item);

used := used+1;

IF used=1

THEN wakeup(Verbraucher);

END LOOP

Verbraucher

LOOP

IF used=0 THEN sleep();

getFromBuffer(item);

used := used-1

IF used = N-1

THEN wakeup(Erzeuger);

consume(item);

END LOOP

Naiver AnsatzNaiver Ansatz Initial: used = 0

Umschaltung


Synchronisation Erzeuger-Verbraucher

LLöösungsungSignal speichern. Aber: unbekannte Prozesszahl...?Semaphore einführen: belegtePlätze:=0, freiePlätze:=N, mutex:=1

Erzeuger Verbraucher

LOOPproduce(item)P(freiePlätze);P(mutex);putInBuffer(item);V(mutex);V(belegtePlätze);

END LOOP

LOOPP(belegtePlätze);P(mutex);getFromBuffer(item);V(mutex);V(freiePlätze);consume(item);

END LOOP

krit. Abschnittskontrolle + Flusskontrolle durch Semaphore

9

ProzessProzess--kommunikationkommunikation


Prozeßkommunikation

Verbindungsanzahl

unicast multicast broadcast

•••

jede Art kann jede andere Art ersetzen!

10


Prozeßkommunikation

Verbindungsorientierte Kommunikation

openConnection(Adresse)

Feststellen, ob der Empfängerexistiert und bereit ist:Aufbau der Verbindung

send(Message)/receive(Message)

Nachrichtenaustausch;

closeConnection Leeren der Nachrichtenpuffer,Beenden der Verbindung

Verbindungslose Kommunikationsend (Adresse, Message) / receive(Adresse, Message)


Prozeßkommunikation: Adressierung

Eindeutige Adressierung: Qualifizierter ID mit IPAdresse = Prozeß-ID.RechnerName.Firma.Land

z.B. 5024.hera.rbi.uni-frankfurt.de

Problem: Prozeß wechselt ID bei Neustart, Aufgabe bleibt

Lösung: logische ID, nicht physische. Beispiel: „Drucker“

Prädikatsadresse: Spezifikationen als Adresse

(IFIF 386-CPU ANDAND Java_installiert ANDAND Drucker) = True: fühle dich angesprochen, sonst nicht. Arbeitsverteilung!

Mailbox = Nachrichtenpuffer mit Namen, unabh. vom Prozess

11


Prozeßkommunikation: Pipes

Unix pipe() unidirektionale Kommunikation„ Programm1 | Programm2 | .. | Programm N “

Windows NTCreatePipe() Bidirektionale pipes

write()

Programm 1

read()

Programm 2

Beliebige Prozesse: named pipesName den Prozessen vorher bekannt


Prozeßkommunikation : Named Pipes

Globales Konzept: Named pipe („Netzwerk/Pfadname“)

=> LAN-Interprozeß-Kommunikation

UnixNamed pipe = special device ⇒ nur IPC auf selbem Rechner, nicht NFSNamed pipe = SystemV: STREAM socket pair() / bind()

Windows NTCreateNamedPipe() : Objekt im globalen Namensraum, auch NetzPfad

IPC = ReadFile() / WriteFile()UNC-Name = „\\ComputerName\PIPE\PipeName“Lokale pipe: „\\ .\PIPE\PipeName“

Kommunikation zu Unix möglich, wenn LAN-Manager für Unix LM/U installiert.

12


Prozeßkommunikation: Signale

Problem: Synchrones Warten blockiert Prozesse

Abhilfe: Benachrichtigung durch asynchrone Signale(Software-Interrupts)

• Aufsetzen der Reaktion auf ein Signal, z.B. in UNIX mit sigaction(ISR)

• Abarbeiten des Hauptprogramms• Bei Signaleintritt: Abarbeiten der angegebenen ISR

• Weiterarbeiten im Hauptprogramm

Documents

Modul: Programmierung (B-PRG) Grundlagen der ... · Abschnittskontrolle + Flusskontrolle durch Semaphore. 9 Prozess-kommunikation Grundlagen der Programmierung 1 - Teil 3 R.Brause: