Synchronisation

Transcript

Gliederung 1. Einführung und Übersicht 2. Prozesse und Threads 3. Interrupts 4. Scheduling Synchronisation 5. Synchronisation 6. Interprozesskommunikation 7. Speicherverwaltung BS-I / Cl. Schnörr / HM Synchronisation 1 BS-I / Cl. Schnörr / HM Gliederung Synchronisation 2 Einführung (1) Wozu Synchronisation ? Übersicht:
Einführung
Threads und z.T. Prozesse haben gemeinsamen Zugriff auf bestimmte Daten, z.B.  Threads des gleichen Prozesses:
Race-Condition  gemeinsamer virtueller Speicher
Kritische Abschnitte  öffnen der gleichen Datei zum Lesen/Schreiben
Mechanismen des BS und Standard-Primitive  Prozesse mit Shared-Memory (--> IPC)
Tips zur praktischen Anwendung:  SMP-System: Scheduler (je einer pro CPU):  Deadlocks vermeiden  Mutex-Objekt  Zugriff auf gleiche Prozesslisten / Warteschlangen  Datenbanken:  Zugriff über eine globale Datenbank-Verbindung (DB-Connect) BS-I / Synchronisation Cl. Schnörr / HM 3 BS-I / Synchronisation Cl. Schnörr / HM 4 Einführung (2) Einführung (3) Beispiel: gleichzeitiger Zugriff auf Datenstruktur: Beispiel: gleichzeitiger Zugriff auf Datenstruktur:
zwei Threads erhöhen einen gemeinsamen Zähler:
gewünscht: eine der folgenden koordinierten Reihenfolgen: BS-I / Cl. Schnörr / HM Synchronisation 5 BS-I / Synchronisation Einführung (4) Beispiel: Datenbanken:
Ursache:
Datenbank: analoges Problem: Cl. Schnörr / HM 8 exec sql CONNECT ... exec sql SELECT kontostand INTO $var FROM KONTO WHERE kontonummer = $knr $var = $var - abhebung exec sql UPDATE Konto SET kontostand = $var WHERE kontonummer = $knr exec sql disconnect  erhoehe_zaehler() arbeitet nicht atomar:  Scheduler kann Funktion unterbrechen (anderer Thread arbeitet weiter)  Funktion kann auf mehreren CPUs gleichzeitig laufen
Lösung: stelle sicher, dass  paralleler Zugriff auf gleichen Datensatz potentiell fehlerhaft  immer nur ein Prozess/Thread gleichzeitig auf gemeinsame Daten zugreift
--> Definition der (Datenbank-) Transaktion, die  bis Vorgang abgeschlossen ist  u.a. atomar und isoliert erfolgen muss  == gegenseitiger Ausschluß (Mutual Exclusion) Synchronisation 6 Einführung (5) Beispiel: gleichzeitiger Zugriff auf Datenstruktur: BS-I / Cl. Schnörr / HM Cl. Schnörr / HM 7 BS-I / Synchronisation Race-Condition (1) Race-Condition (2) Eigenschaften: Race-Condition als Sicherheitslücke
Race Condition
Race-Conditions sind auch Sicherheitslücken  mehrere parallele Threads/Prozesse nutzen gemeinsame Ressource
wird vom Angreifer genutzt  Zustand hängt von Reihenfolge der Ausführung ab:
einfaches Beispiel:  Ergebnis nicht vorhersagbar / nicht reproduzierbar read( command ); f = open( “/tmp/script“, “w“ ); write( f, command ); close( f ); chmod( “/tmp/script“, “a+x“ ); system( “/tmp/script“ );  Race: Threads liefern sich ein „Rennen“ um den ersten/schnellsten Zugriff Warum Race-Conditions vermeiden?
Ergebnisse paralleler Berechnungen sind potentiell falsch
Angreifer ändert Dateiinhalt vor dem chmod()  Programmtests können „funktionieren“, später die Anwendung aber versagen BS-I / Cl. Schnörr / HM Synchronisation / Race-Condition --> Programm läuft mit Rechten des Opfers 9 BS-I / Synchronisation / Race-Condition Race-Condition (3) Zugriff via Flag / Lock auf Thread/Prozess beschränken: erhoehe_zaehler() { flag = read( lock ); if ( flag == LOCK_NOT_SET ) { set( lock ); //Start kritischer Bereich w = read( adr ); w = w + 1; write( adr, w ); //Ende kritischer Bereich release( lock ); } }
Problem: Lock-Variable nicht geschützt BS-I / Synchronisation / Race-Condition 10 Kritischer Bereich Was ist ein „kritischer Bereich“ ? Aspekte einer Lösung
Idee: Cl. Schnörr / HM
kein Problem:
Programmteil, der auf gemeinsame Daten zugreift  gleichzeitiges Lesen von Daten
Block zwischen erstem und letztem Zugriff  Threads, die “disjunkt“ sind, d.h.
Formulierung: kritischen Bereich  betreten / verlassen (enter / leave critical section)  keine gemeinsame Daten haben / nutzen Anforderungen an parallele Threads:
problematisch:
maximal ein Thread gleichzeitig in kritischem Bereich  mehrere Prozesse/Threads
kein Thread außerhalb kritischem Bereich darf anderen blockieren (--> potentiell Deadlock)  greifen gemeinsam auf Objekt zu,
kein Thread soll ewig auf Freigabe eines kritischen Bereichs warten  davon mindestens einer schreibend
Deadlocks zu vermeiden, z.B.  zwei Threads in verschiedenen kritischen Bereichen blockieren sich gegenseitig Cl. Schnörr / HM 11 BS-I / Synchronisation / kritischer Bereich Cl. Schnörr / HM 12 Gegenseitiger Ausschluß Programmtechnische Synchronisation
Gegenseitiger Ausschluß (Mutual Exclusion, kurz Mutex):
Idee war:  nie mehr als ein Thread betritt kritischen Bereich  Zugriff via Flag / Lock auf Thread/Prozess beschränken  es ist Aufgabe des Programmierers, dies zu garantieren
Problem:  das BS bietet Mechanismen und Hilfsmittel, gegenseitigen Ausschluß durchzusetzen  Lock-Variable nicht geschützt  Verantwortung für Fehlerfreiheit liegt beim Programmierer:
Lösung:  Compiler können i.d.R. Fehler aus Nebenläufigkeit nicht erkennen  eine Lock-Variable atomar testen und setzen  dies kann per Programmlogik über mehrere Variable erreicht werden (--> Lit.: Dekker1966, Petersons Algorithmus)  ist kompliziert bei mehr als zwei Threads/Prozessen
besser: Nutzung von „standard“ BS-Mechanismen BS-I / Cl. Schnörr / HM Synchronisation / Mutex 13 BS-I / Cl. Schnörr / HM Synchronisation 14 Test-and-Set-Lock (TSL)
Maschineninstruktion (moderner CPUs)  mit dem Namen TSL = Test and Set Lock  die atomar eine Lock-Variable liest (testet) und setzt, also garantiert ohne Unterbrechung  im Fall mehrerer CPUs: Synchronisation  TSL muss Speicherbus sperren, damit kein Thread auf anderer CPU in gleicher Weise zugreifen kann Mechanismen und Standard-Primitive enter: tsl register, flag cmp register, 0 jnz enter ret leave: mov flag, 0 ret BS-I / Synchronisation / Mechanismen Cl. Schnörr / HM 15 BS-I / ; ; ; ; Variable in Register kopieren und dann Variable auf 1 setzen war Variable 0 ? nicht 0: Lock war gesetzt, also Schleife(pollen) ; 0 in flag speichern: Lock freigeben Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 16 Aktives und passives Warten (1) Aktives und passives Warten (2)
Aktives Warten (busy waiting):
Passives Warten (sleep and wake):  Ausführen einer Schleife, bis eine Variable einen bestimmten Wert annimmt  Thread blockiert und wartet auf Ereignis, das ihn in den Zustand „bereit“ versetzt  Thread ist bereit und belegt die CPU  blockierter Thread verschwendet keine CPU-Zeit  Variable muss von einem anderen Thread gesetzt werden  anderer Thread muss Eintreten des Ereignisses bewirken  (kleines) Problem, wenn anderer Thread endet  (großes) Problem, wenn der andere Thread endet  bei Ereignis muss blockierter Thread geweckt werden  (großes) Problem, wenn anderer Thread -- z.B. wegen niedriger Priorität -- nicht dazu kommt, Variable zu setzen  explizit durch anderen Thread  durch Mechanismen des BS
auch Pollen/Polling genannt BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 17 BS-I / Synchronisation / Mechanismen+Primitive Erzeuger-Verbraucher-Problem (1) Cl. Schnörr / HM 18 Erzeuger-Verbraucher-Problem (2)
Synchronisation:
Erzeuger-Verbraucher-Problem (producer-consumer problem, bounded-buffer problem)  Puffer nicht überfüllen:  zwei kooperierende Threads:  wenn Puffer voll, muß Erzeuger warten, bis Verbraucher ein weiteres Paket abgeholt hat  Erzeuger speichert Informationspaket in beschränktem Puffer  nicht aus leerem Puffer lesen:  Verbraucher liest Informationen aus diesem Puffer  wenn Puffer leer, muß Verbraucher warten, bis Erzeuger ein weiteres Paket abgelegt hat
Realisierung mit passivem Warten:  eine gemeinsame Variable „count“ zählt belegte Positionen im Puffer  wenn Erzeuger ein Paket einstellt und Puffer leer war (count == 0) --> wecken des Verbrauchers  wenn Verbraucher ein Paket abholt und Puffer voll war (count == max) --> wecken des Erzeugers BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 19 BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 20 Erzeuger-Verbraucher mit sleep-wake #define N 100 int count = 0; Deadlock-Problem bei sleep / wake (1) //Anzahl der Plätze im Puffer //Anzahl der belegten Plätze im Puffer  Verbraucher liest Variable count, die den Wert 0 hat producer() { while (TRUE) { // Endlosschleife produce( item ); // Erzeuge etwas für den Puffer // Wenn Puffer voll: schlafen legen if (count == N) sleep(); enter( item ); // In den Puffer einstellen count = count + 1; //Zahl belegter Plätze inkrementieren if (count == 1) wake(consumer); //war der Puffer vorher leer? } }  Kontextwechsel zum Erzeuger:  Erzeuger stellt etwas in den Puffer,  erhöht count und  weckt Verbraucher, da count==0 war consumer() { while (TRUE) { // Endlosschleife // Wenn Puffer leer: schlafen legen if (count == 0) sleep(); remove_item (item); // Etwas aus dem Puffer entnehmen count = count - 1; // Zahl belegter Plätze dekrementieren if (count == N-1) wake(producer); //war der Puffer vorher voll? consume_item (item); // Verarbeiten } } BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM
Race-Condition im vorigen Programm --> potentieller Deadlock, z.B. 21  Kontextwechsel zum Verbraucher: Verbraucher legt sich schlafen, da count==0 gelesen wurde  Erzeuger schreibt Puffer voll und legt sich auch schlafen BS-I / Synchronisation / Mechanismen+Primitive Deadlock-Problem bei sleep / wake (2) Cl. Schnörr / HM 22 Cl. Schnörr / HM 24 Standardprimitive zur Synchronisation
Ursache des Problems: Welche Standardprimitive zur Synchronisation gibt es ?  Wakeup-Signal für einen -- noch nicht -- schlafenden Prozess wird ignoriert
Mutex (mutual exclusion) = binärer Semaphor  --> Weckaufruf „irgendwie“ aufbewahren
Semaphor
Lösungsmöglichkeit:
Event (ähnlich Condition-Variable)  Systemaufrufe sleep() und wake() verwenden „wakeup pending bit“
Monitor  bei wake() für nicht schlafenden Thread dessen wakeup-pending-bit setzen
Locking  bei sleep() das wakeup-pending-bit des Threads prüfen und falls gesetzt, nicht schlafen legen
aber:  Lösung lässt sich nicht verallgemeinern (mehrere Prozesse benötigen weitere Bits). BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 23 BS-I / Synchronisation / Mechanismen+Primitive Mutex (1) Mutex (2)  wait() und signal()-Operationen sind selbst kritische Abschnitte --> atomar realisiert
Mutex (mutual exclusion) = binärer Semaphor  Implementierung als System-Calls und Verhinderung von Kontext-Wechseln (z.B. durch kurzzeitiges Ausschalten von Interrupts)  zur Synchronisation eines kritischen Bereichs bzw. gemeinsamer Daten  kann nur 2 Zustände / Werte annehmen: Zugang erlaubt  true / frei:  false / gesperrt: Zugang gesperrt wait( mutex ) { if ( mutex == 1 ) mutex = 0; else BLOCK_CALLER; }  Anforderungs- und Freigabe-Operationen:  Anforderung: wait() / lock() / get() signal() / unlock() / release()  Freigabe:  Anforderung: ein Thread, der eine bereits vergebene Mutex anfordert, blockiert --> Warteschlange  Freigabe:  Warteschlange enthält Threads  Warteschlange leer BS-I / --> einen wecken --> Mutex auf true Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 25 BS-I / Synchronisation / Mechanismen+Primitive Semaphor (1) 26 Cl. Schnörr / HM 28
Varianten:  Integer- (Zähler-) Variable  negative Semaphor-Werte:  mit festgelegtem Anfangswert N („Anzahl verfügbarer Ressourcen“)  Anforderung (wait()): - Wert immer um 1 reduzieren - --> Wert entspricht Zahl blockierter Threads in Warteschlange  Anforderung (wait()): Wert um 1 reduzieren Thread blockieren --> Warteschlange  Freigabe (signal()): - Wert immer um 1 erhöhen  Freigabe (signal()):  falls Warteschlange nicht leer:  falls Warteschlange leer:  nicht-blockierend: z.B. bool ret = try_lock(); einen Thread wecken Wert um 1 erhöhen  pthreads-Semaphore:  sind auch zwischen Prozessen verwendbar (Standard: nur Threads)  SysV-IPC Semaphore:  arbeiten prozessübergreifend  sind nach Prozessende noch vorhanden wait( &sem ); // Kode, der die Ressource nutzt signal( &sem ); BS-I / Cl. Schnörr / HM Semaphor (2)
Semaphor:  falls >= 1:  falls == 0: signal( mutex ) { if ( P in QUEUE(mutex)) { wakeup( P ); remove( P, QUEUE ); } else mutex = 1; } Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 27 BS-I / Synchronisation / Mechanismen+Primitive Semaphor (3) Erzeuger-Verbraucher-Problem mit Semaphoren Beispiel:
Verbraucher: Threads A,B,C: wait()
Erzeuger: signal() Thread D: typedef int semaphore; semaphore mutex = 1; semaphore empty = N; semaphore full = 0;
Semaphore s zählt verfügbare Ressource BS-I / Cl. Schnörr / HM Synchronisation / Mechanismen+Primitive 29 // Kontrolliert Zugriff auf Puffer // Zählt freie Plätze im Puffer // Zählt belegte Plätze im Puffer producer() { while (TRUE) { produce_item(item); wait(empty); wait(mutex); enter_item(item); signal(mutex); signal(full); } } // // // // // // // Endlosschleife Erzeuge etwas für den Puffer Leere Plätze dekrementieren bzw. blockieren Eintritt in den kritischen Bereich In den Puffer einstellen Kritischen Bereich verlassen Belegte Plätze erhöhen, evtl. consumer wecken consumer() { while (TRUE) { wait(full); wait(mutex); remove_item(item); signal(mutex); signal(empty); consume_entry(item) } } // // // // // // // Endlosschleife Belegte Plätze dekrementieren bzw. blockieren Eintritt in den kritischen Bereich Aus dem Puffer entnehmen Kritischen Bereich verlassen Freie Plätze erhöhen, evtl producer wecken Verbrauchen BS-I / Cl. Schnörr / HM Synchronisation / Mechanismen+Primitive Events (1) 30 Events (2)
Events: Beispiel:  kein Thread besitzt einen Event (<-> Mutex)  wait() blockiert, falls Event nicht im signalisierten Zustand  automatischer Event: thread A . event.wait() . . thread B . . event.signal(); . manual automatic t # threads waiting after each call:  jedes wait() setzt Event automatisch zurück (reset) 2 2 0 1 0 0 0 0 0 0 0 1 0 2 0 0 manual automatic signalled  falls mehrere Threads warten: bei einem signal() kehrt nur genau ein Thread von seinem wait() zurück non-signalled Zeit t  manueller Event: signal() signal() signal() signal() wait() wait() reset()  Event muß manuell zurückgesetzt werden (reset)  falls mehrere Threads warten: bei einem signal() kehren alle Threads von ihren wait() zurück BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 31 BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 32 Monitor (1) Monitor (2)
Problem bei Arbeit mit Mutexen und Semaphoren:  Programmierer gezwungen, kritische Bereiche mit wait() und signal() abzusichern  schon bei einem Fehler --> Synchronisierung versagt
Monitor:  muss von Programmiersprache unterstützt werden (z.B. Java, Concurrent-Pascal)  Sammlung von Prozeduren, Variablen, speziellen Bedingungsvariablen:  Prozesse können Prozeduren des Monitors aufrufen, aber  nicht auf dessen Datenstrukturen zugreifen  kapselt kritische Bereiche  zu jedem Zeitpunkt nur ein einziger Prozess im Monitor aktiv (Monitor-Prozedur ausführen)  Freigabe durch Verlassen der Monitor-Prozedur BS-I / Cl. Schnörr / HM Synchronisation / Mechanismen+Primitive 33 BS-I / Synchronisation / Mechanismen+Primitive Monitor (3)
Monitor-Konzept erinnert an
Kapselung: nur Zugriff über public-Prozeduren wait( disc_access ); // Daten lesen signal( disc_access ); 36 Was tun, wenn Prozess im Monitor blockieren muss ?
Condition-Variablen (Zustandsvariable): gleiches Beispiel: mit Monitor: Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM  „Klasse“, bei der jede public-Methode synchronisiert ist wait( disc_access ); // Daten schreiben signal( disc_access ); BS-I /
Monitor wird von Programmiersprache / Compiler bereitgestellt  nicht der Programmierer ist für gegenseitigen Ausschluß verantwortlich Beispiel: Zugriff auf Festplatte mit Mutex: monitor disc { entry read( discaddr, memaddr ) { // Daten lesen }; entry write( discaddr, memaddr ) { //Daten schreiben }; init() { // Gerät initialisieren }; }; 34 Monitor (4)  Klassen (Objektorientierung)  Module mutex disc_access = 1; Cl. Schnörr / HM  Idee: Prozess muss auf Eintreten einer Bedingung (Condition) warten monitor disc;  m_wait( var ): aufrufenden Prozess sperren (er gibt den Monitor frei) disc.read( da, ma );  m_signal( var ): disc.write( da, ma );  gesperrte(n) Prozess(e) wecken  erfolgt unmittelbar vor Verlassen des Monitors Cl. Schnörr / HM 35 BS-I / Synchronisation / Mechanismen+Primitive Monitor (5) Process 1 Monitor Monitor (6) Prozess 2
Gesperrte Prozesse landen in Warteschlange zu entsprechender Condition-Variable
Interne Warteschlangen haben Vorrang vor Prozesszugriffen von außen Daten ConditionVariable Prozedur Prozedur BS-I / f() cv
Implementierung mit Mutex / Semaphor: g() f() { wait( cv); ... } m_wait(cv) Zeit t conditionVariable { g() { ... signal( cv); } Synchronisation / Mechanismen+Primitive wait() { m.lock(); queueSize++; m.release(); waiting.down(); } Cl. Schnörr / HM 37 BS-I / 38
Locking  erweitert Funktionalität von Mutexen  durch Unterscheidung verschiedener Lock-Modi (Zugriffsarten)  und Festlegung derer „Verträglichkeit“ entry append( item x ) { while (count == N-1) m_wait(nonfull); put(buffer, x); // count += 1; m_signal(nonempty); }  Concurrent Read: Lesezugriff, andere Schreiber erlaubt entry remove(item x) { while (count == 0) m_wait(nonempty); get(buffer, x); // count -= 1; m_signal(nonfull); } // Initialisierung } z.B. auf oberen Lock-Hierarchien in Datenbanken  Concurrent Write: Schreibzugriff, andere Schreiber erlaubt  Protected Read: Lesezugriff, andere Leser erlaubt, aber keine Schreiber (share lock)  Protected Write: Schreibzugriff, andere Leser erlaubt, aber kein weiterer Schreiber (update lock)  Exclusive: Lese/Schreibzugriff, keine anderen Zugriffe erlaubt  Thread fordert Lock in bestimmtem Modus an. Ist Lock-Modus zu einem Lock eines anderen Threads unverträglich -> Blockierung } Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM Locking (1) monitor iostream { item buffer; int count; const int N = 64; condition nonempty, nonfull; BS-I / }; Synchronisation / Mechanismen+Primitive Erzeuger-Verbraucher-Problem mit Monitor init() { count = 0; } signal() { m.lock(); while( queueSize > 0 ) { // alle wecken queueSize--; waiting.up(); } m.release(); } int queueSize = 0; mutex m; semaphore waiting; m_signal(cv) Cl. Schnörr / HM 39 BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM 40 Locking (2) Lock-“Verträglichkeiten“: concurrent concurrent protected read write read protected exclusive write access sharing concurrent read read write + + + + - concurrent write write write + + - - - protected read read read + - + - - protected write write read + - - - - exclusive write -- - - - - - BS-I / Synchronisation / Mechanismen+Primitive Cl. Schnörr / HM Praxisbeispiele 41 BS-I / Praxis: Übersicht
Typ atomic_t (24 Bit Integer):  Initialisierung: atomic_t var = ATOMIC_INIT( 0 );  Atomare Operationen  auf Integer-Variablen  Bit-Operationen auf Bitvektoren  Spin-Locks  Reader-Writer-Locks  Wert setzen: atomic_set( &var, wert );  Addieren: atomic_add( wert, &var );  ++: atomic_inc( &var );  Subtrahieren: atomic_sub( wert, &var );  Semaphore / Reader-Writer Semaphore
Synchronisation in C++  Threads, Mutexe  atomare Befehle  Mutex-Objekt in C++ Synchronisation / Praxis 42 Praxis / Linux-Kernel: Atomare Integer-Operationen
Synchronisation im Linux-Kernel BS-I / Cl. Schnörr / HM Synchronisation / Praxis  --: atomic_dec( &var );  Auslesen: int i = atomic_read( &var );
res = atomic_sub_and_test( i, &var );  subtrahiert i atomar von var  return true, falls Ergebnis 0, sonst false Cl. Schnörr / HM 43 BS-I / Synchronisation / Praxis / Linux-Kernel
res = atomic_add_negative( i, &var );  addiert i atomar zu var  return true, falls Ergebnis negativ, sonst false Cl. Schnörr / HM 44 Praxis / Linux-Kernel: Atomare Bit-Operationen Praxis / Linux-Kernel: Spin-Locks (1)
Einzelne Bits in Bitvektoren setzen
Spin-Lock:
Datentyp: beliebig, z.B. unsigned long bitvektor = 0;  Lock mit Mutex-Funktion: gegenseitiger Ausschluß  nur über Pointer anzusprechen  Anzahl der nutzbaren Bits abhängig vom verwendeten Datentyp  Test-and-Set-Operationen geben zusätzlich vorherigen Wert des jeweiligen Bits zurück  set_bit( i, &bv );  clear_bit( i, &bv );  change_bit( i, &bv ); i-tes Bit setzen i-tes Bil löschen i-tes Bit kippen  Code, der Spin-Lock anfordert und nicht erhält  blockiert nicht (kein aufwendiger Wechsel in Kernel-Mode)  sondern läuft weiter (spinning), bis Lock verfügbar  b = test_and_set_bit( i, &bv );  b = test_and_clear_bit( i, &bv );  b = test_and_change_bit( i, &bv );  nur zu verwenden  bei kurzen „Wartezeiten“ auf Lock,  bei Mehrprozessorsystemen
Einzelne Bits auslesen:  b = test_bit( i, &bv );  sind nicht „rekursiv“, also z.B. nicht in rekursiven Funktionen verwendbar
Suchfunktionen:
Typ spinlock_t spin_lock( &slock ): /* kritischer Abschnitt */ spin_unlock( &slock );  pos = find_first_bit( &bv, length );  pos = find_first_zero_bit( &bv, length ); BS-I / Cl. Schnörr / HM Synchronisation / Praxis / Linux-Kernel 45 BS-I / Praxis / Linux-Kernel: Spin-Locks (2) Cl. Schnörr / HM Synchronisation / Praxis / Linux-Kernel 46 Praxis / Linux-Kernel: Reader-Writer-Locks
da Spin-Locks nicht schlafen/blockieren, sind diese in Interrupt-Handlern verwendbar
Reader-Writer-Locks:
in diesem Fall: zusätzlich Interrupts sperren:  Alternative zu normalen Locks, die mehrere Lesezugriffe zulässt, spinlock_t slock = SPIN_LOCK_UNBLOCKED; unsigned long flags; spin_lock_irqsave( &slock, flags ); /* ktitischer Abschnitt */ spin_unlock_irq_restore( &slock, flags ); spinlock_t slock = SPIN_LOCK_UNLOCKED  aber bei schreibendem Zugriff exklusiv ist (wie normaler Lock)
// aktuelle Interrupts sichern // dann sperren // ursprüngl. Zustand restaurieren
wenn zu Beginn alle Interrupts aktiviert sind, geht es auch einfacher: spinlock_t slock = SPIN_LOCK_UNBLOCKED; spin_lock_irq( &slock ); /* ktitischer Abschnitt */ spin_unlock_irq( &slock ); BS-I / Synchronisation / Praxis / Linux-Kernel
auch Varianten für Interrupt-Behandlung: // aktuelle Interrupts sperren Cl. Schnörr / HM - read_lock_irq / read_unlock_irq - read_lock_irqsave / read_unlock_irqrestore 47 BS-I / Synchronisation / Praxis / Linux-Kernel - write_lock_irq / write_unlock_irq - write_lock_irw_save / write_unlock_irqrestore Cl. Schnörr / HM 48 Praxis / Linux-Kernel: Semaphore (1) Praxis / Linux-Kernel: Semaphore (2)
Typ: semaphore
Kernel-Semaphore  sind „schlafende“ Locks  statische Deklaration: static DECLARE_SEMAPHORE_GENERIC( name, count ); static DECLARE_MUTEX( name );  wartende Prozesse werden in Warteschlange gestellt, bei Freigabe wird erster geweckt  eignen sich für Sperren, die über längeren Zeitraum gehalten werden (<-> Spin-Lock) // count = 1  dynamische Deklaration:  sind nur im Prozess-Kontext, nicht in Interrupt-Handlern einsetzbar (Interrupt-Handler werden nicht vom Scheduler behandelt) sema_init( &sem, count ); init_MUTEX( &sem );  Code, der Semaphore verwendet, darf nicht bereits normalen Lock besitzen (Semaphore-Zugriff kann zum „schlafen-legen“ führen // count = 1;  Verwendung mit up() und down(): down( &sem ); /* kritischer bereich */ up( &sem ); BS-I / Cl. Schnörr / HM Synchronisation / Praxis / Linux-Kernel 49 BS-I / Synchronisation / Praxis / Linux-Kernel Praxis / Linux-Kernel: Semaphore (3) 50 Cl. Schnörr / HM 52 Praxis: Synchronisation in C++ (1)
Reader-Writer-Semaphore:  analog zu Reader-Writer-Locks: Cl. Schnörr / HM
Threads, Mutexe, usw.: Typ rw_semaphore, der spezielle Up- und DownOperationen für Lese- und Schreibzugriffe erlaubt  pthreads-Bibliothek (UL-Threads):  quasi-Standard in Unix/Linux  wenig gebräuchlich unter Windows (<-> Win-API)  alle RW-Semaphore sind Mutexe (bei Initialisierung count=1) Lesender Code: Schreibender Code: #include , linken mit libpthreads static DECLARE_RWSEM( rwsem ); init_rwsem( &rwsem ); down_read( &rwsem ); //read-only Abschnitt up_read( &rwsem );  C++0x/C++11-Standard:  Thread/Mutex-API: down_write( &rwsem ); //lesen+schreiben-Abschnitt up_write( &rwsem ); #include  OpenMP-Standard:  Parallelisierung von Schleifen mittels Threads #include #pragma omp parallel for num_threads(NCPU) for ( long y = ylow; y <= yhigh; ++y ) {...} BS-I / Synchronisation / Praxis / Linux-Kernel Cl. Schnörr / HM 51 BS-I / Synchronisation / Praxis / C++ Praxis: Synchronisation in C++ (2) Praxis: Synchronisation in C++ (3) Nachbildung eines Monitors mittels pthreads struct ProducerConsumer { pthread_mutex_t count_mtx; //zu initialisieren pthread_cond_t full, empty; int count; ErzeugerVerbraucherprogramm void producer() { produce_item(); pc.enter(); } void remove() remove() { pthread_mutex_lock( pthread_mutex_lock( &count_mtx ); while ( count == 0 ) pthread_cond_wait( pthread_cond_wait( &empty, &count_mtx ); remove_item(); count--; if (count == N-1) pthread_cond_signal( pthread_cond_signal( &full ); pthread_mutex_unlock( pthread_mutex_unlock( &count_mtx ); } }; BS-I / Synchronisation / Praxis / C++  #pragma omp atomic newline statement_expression void consumer() { pc.remove(); consume_item(); }  #pragma omp critical { statements; ... }  Compiler-Unterstützung:  Cl. Schnörr / HM 53 Kontextwechsel vor return --> Vor Rückgabe Veränderung von refcount durch andere Threads möglich refcount; //not ok! }
Lösung: Mutex in Konstruktor und Destruktor class MutexObj { private: MutexObj( pthread_mutex_t & lock ) : _lock(lock) { pthread_mutex_lock( &_lock ); } ~MutexObj() { pthread_mutex_unlock( &_lock ); } pthread_mutex_t & / _lock; BS-I / Synchronisation Praxis / C++ }; __sync_lock_test_and_set( &lock, val );  InterlockedExchange( (long *)&lock, val );
Mutex-Objekt: return #include  OpenMP-Standard: Praxis: Synchronisation in C++ (4) int RefCount::dec_refcount() { pthread_mutex_lock( &lock ); --refcount; pthread_mutex_unlock( &lock );  C++0x/C++11-Standard: ProducerConsumer pc;  Atomic-API: void enter() enter() { pthread_mutex_lock( pthread_mutex_lock( &count_mtx ); while ( count == N-1 ) pthread_cond_wait( pthread_cond_wait( &full, &count_mtx ); enter_item(); count++; if ( count == 0 ) pthread_cond_signal( pthread_cond_signal( &empty ); pthread_mutex_unlock( pthread_mutex_unlock( &count_mtx ); } RefCount::refcount; //in mehreren Objekten
Atomare Befehle (--> Literatur): int RefCount::dec_refcount() { MutexObj lock( refcount_lock ); return --refcount; //ok } Synchronisation von refcount bis nach lokaler Kopie bei return Aber: nur ok bei return-per-value ! Cl. Schnörr / HM 55 BS-I / Synchronisation / Praxis / C++ // g++, testAndSet( _lock, 0 ); // msvc, , testAndSet( _lock, 0 ); Cl. Schnörr / HM 54