I.Nebenläufigkeit - Distributed Systems (Uni Ulm) · I.3.Synchronisierung nebenläufiger Abläufe Mehrprogrammbetrieb: Programme greifen auf die gemeinsame Hardware & Software zu,

I.I. NebenläufigkeitNebenläufigkeit

I.1. Einordnung

Betriebssystemkonzepte:Nebenläufige Ausführung von Programmteilen,Nondeterminismen & Synchronisierung,Transaktionen, Threads und Prozesse.

L - / 29 Technische Informatik 1, Sommer 2009, © VS Informatik, Uni Ulm, P. Schulthess & F. Hauck

Elektronik: - Strom & Spannung, Transistoren, ICs

Architektur

Systemprogrammierung: - OS-Konzepte, OS-Kern, HW-Schnittstellen ...

„Höhere Informatik“: - Programmierung, Datenbanken, Verteilte Systeme, Theorie ...

Digitaltechnik: - Rechnerarithmetik, Schaltwerke, Gatter, Logik ...

Betriebssystemkonzepte: - Betriebsmittelvergabe, Nebenläufigkeit, Schutz

Betriebssystemkern: - Gerätetreiber, Interrupts, Speicherorg.

Direkte Programmierung: - Geräteregister, E/A-Adressraum, Hauptplatine

LC

E

G

KI

H

FD

I.2. Nebenläufigkeit

2 Abläufe (Threads) sind nebenläufig (concurrent), wenn die Verschränkung der Instruktionsausführung (Schreiben/Lesen) nicht deterministisch erfolgt.Der Frontside-Bus garantiert die Atomarität des Speicherzugriffs.


Th1 Th2 Physische Nebenläufigkeit, mehrere CPUs vorhanden, keine Kontextumschaltung.X

Th1 Th2

Logische Nebenläufigkeit, nur eine CPU vorhanden, Kontextumschaltung.

X

I.3. Synchronisierung nebenläufiger Abläufe

Mehrprogrammbetrieb: Programme greifen auf die gemeinsame Hardware & Software zu,viele Programme konkurrieren "gleichzeitig" um Ressourcen,z.B. Hauptspeicher, CPU(s), Disk, Devices, Interrupts ...

Race condition: zwischen nebenläufigen Prgrammen (Threads),Lesen & /Schreiben in unsicherer Reihenfolge,Resultat der Rechnung ist nicht deterministisch,"mal ist der eine, mal der andere zuerst da",könnte die Zuweisung von "1" entfallen?

Synchronisierung:erzwingt eine deterministische Ausführung,unterschiedl. Synchronisierungstechniken,z.B. mit Signal & Wait.


I.3.1. Zugriffskollisionen & Race Conditions3 Beispielvideos:

Entwurf & Modellierung: Sebastian Seiler,http://www-vs.informatik.uni-ulm.de/teach/ss08/ti1/media/Synchronisation/Billard/ No Collision: kollisionsfreier wechselweiser Variablenzugriff,Collision: gestörter Variablenzugriff mit Race-Condition,Synched: Synchronisierter Variablenzugriff.


http://www-vs.informatik.uni-ulm.de/teach/ss08/ti1/media/Synchronisation/Billard/

I.4. Kritische Abschnitte (= Critical Regions)

Programmabschnitte, die auf gemeinsame Variablen zugreifen und deshalb eines wechselseitigen Ausschlusses bedürfen:

wechselseitiger Ausschluss gewünscht max. 1 Thread im kritischen Abschnitt.keine Annahmen bezüglich CPU-Geschwindigkeit oder Anzahl der CPUs, ...Fairness: Wartezeit für Eintritt in kritischen Abschnitt muss begrenzt sein.Fortschrittsgarantie: keine Verklemmungen,in Java mit Schlüsselwort "synchronized".

Unterschiedliche Programmabschnitte nutzen dieselben Variablen. => Nicht Programmabschnitt, sondern Variablenobjekt wird geschützt.Metapher einer Strassenkreuzung:

Entwurf & Modellierung: Holger Bähren=> http://www-vs.informatik.uni-ulm.de/ teach/ss08/ti1/media/Synchronisation/Desert/





http://www-vs.informatik.uni-ulm.de/

I.4.1. Fehlerhafte Lösung - einfaches Busy-Flag:Vor dem Eintritt in die kritische Region wird das Flag geprüft:

Problem „Atomarität“: Testen und Setzen des Flags geschieht nicht atomar, bzw. nicht ununterbrechbar,evtl. wird beim Prüfen des Flags zwischen den Threads umgeschaltet, u.U. können beide Threads den kritischen Abschnitt betreten,=> keine sichere Verriegelung !!


boolean busyFlag = false ; …. while (busyFlag) ; // warten bis “not busy” busyFlag=true; // kritische Region “busy” count++; // hier lost update! vermeiden busyFlag=false; // kritische Region “not busy”

boolean busyFlag = false ; ….

while (busyFlag){} ; ► ◄ while (busyFlag) {};

// now both threads are in the critical region !! busyFlag=true; busyFlag=true; count++; count++; busyFlag=false; busyFlag=false;

I.4.2. Atomare Operation - „Test and Set“:Verbesserung:

Ersetzen der While-Schleife,while ( testAndSet ( & busyFlag) ) { };NB: „&“ soll heissen „Address of“.

„Testen und Setzen“:oft als atomare Maschineninstruktion,alten Wert lesen und merken, neuen Wert schreiben, alten Wert liefern.


Test and Set

true

??

boolean busyFlag = false ; ….

while ( testAndSet ( & busyFlag)){} ; ► ◄ while ( testAndSet ( & busyFlag)) {}

count++; // now thread-2 is locked out busyFlag=false; // thread-2 is in loop

count++;busyFlag=false;

I.4.3. Peterson's AlgorithmusWechselseitiger Ausschluss nur gestützt auf sequent. Speicherzugriff.Wissenheim Metapher mit 2 Automobilen:

Kritische Region als Strassenkreuzung,Schalter in der Fahrbahn betätigen Schranken:

Programmvariablen (Schranken):latest: später angekommener Pkw (rot),tryGreen: Pkw1 versucht Eintritt (hellblau),tryYello: Pkw2 versucht Eintritt (lila).


Entwurf & Gestaltung: Holger Bähren

I.4.4. Programm für Peterson-Synchronisation:Program Peterson;var latest: (green, yellow) // Wer ist an der Reihe? Var. wird von beiden geschrieben

tryGreen, tryYello: Boolean; // Warnvariablen werden jeweils nur von einem geschriebenBegin

tryGreen := false; tryYello := false;parbegin Process1; Process2 parend

end { Peterson }.


Process Process1;begin

tryGreen:= true;latest:= green;while tryYello and latest=green do { loop} ;KritischeRegion();tryGreen:= false;OtherStuff1

end { Process1 };

Process Process2;begin

tryYello:= true;latest:= yellow;while tryGreen and latest=yellow do {loop};KritischeRegion();tryYello:= false;OtherStuff2

end { Process2 };

I.5. Programmbeispiel "SyncDemo"I.5.1. Programmfunktionalität2 nebenläufige Programmteile:

Transaktion "SyncDemo" wird 109 mal aus der Plurix-Hauptschleife heraus aufgerufen,Timer-Interruptroutine wird 18,2 mal pro Sekunde aufgerufen,13 Inkrementierungen aus 109 gehen verloren.

Nebenläufige Programmteile inkrementieren 2 gemeinsame Variablen:Variable "syncCount" wird unter wechselseitigem Ausschluss inkrementiert,Variable "asyncCount" wird ohne weitere Synchronisierung inkrementiert,Inkrementierungen von "asyncCount" gehen verloren.


syncCount

asyncCount

109 × 2380 ×

I.5.2. Ausgabe des Programmes (verschönert)Eine Ausgabezeile jeweils nach 1000'000 Transaktionen:

durch Interruptsperre geschützte, synchrone Inkrementierungen,ungeschützte, asynchrone Inkrementierungen (asyn++),verlorengegangene asynchrone Inkrementierungen,Anzahl Aufrufe der Timer ISR-Routine,Anzahl der ausgeführten Transaktionen,Summe der Timer und TA-Aufrufe.

syn,asyn,lost,tim,ta,tot: 1000000 1000000 0 2 999998 1000000 ... syn,asyn,lost,tim,ta,tot: 77000000 77000000 0 182 76999818 77000000 ... syn,asyn,lost,tim,ta,tot: 220000000 220000000 0 519 219999481 220000000 ... syn,asyn,lost,tim,ta,tot: 738000000 737999988 12 1751 737998249 738000000 syn,asyn,lost,tim,ta,tot: 739000000 738999987 13 1754 738998246 739000000 ...syn,asyn,lost,tim,ta,tot: 1000000000 999999987 13 2380 999997620 1000000000

Während der ersten 25 Sekunden und 220 Mio Aufrufe scheint alles OK!Pentium IV Mobile mit 1,733 GHz => 7,7 Mio TAs/sec.


I.5.3. Hauptschleife, Tasks und Rainbow-Transaktionen Tasks werden aus der Hauptschleife heraus aufgerufen:

Tasks sind im Transaktionsvektor der jeweiligen Station eingetragen,Hauptschleife erschient als Methode "loop" in der Klasse Station,Die Tasks/Transaktionen beginnen & enden mit leerem Stack,teilen den Stack, aber mit der Interruptroutine.

private void Loop() // zentrale Hauptschleife{ int taIndex; // indiziert TAvektor

Transaction currentTA; // TA in Ausführung while (true) // Endlosschleife{ taIndex = ( taIndex+1 ) % freeTASlot; // nächste TA auswählen

currentTA = TAVector[ taIndex ]; // aus Transaktionsvektorif (currentTA.scheduleTime <= STATION.ticks) // nur wenn fällig

currentTA.run(); // Einstieg in die Task} }

Übrigens: In Rainbow-OS sind Tasks rücksetzbare Transaktionen:im verteilten Rainbow-OS können alle Änderungen falls nötig rückgängig gemacht werden.läuft eine Transaktion jedoch zu Ende, so werden deren Resultate "committed",ähnlich dem ACID-Konzept für Datenbank-Transaktionen.


I.5.4. Transaktionsklasse "SyncDemo"Alle User-Transaktionen müssen von Transaction abgeleitet werden:

User-Transaktionen erben die finalen Methoden Install() und Remove(),werden im Transaktionsvektor der Hauptschleife installiert,können Felder und Methoden hinzufügen,überschreiben die Methode run().

public class SyncDemo extends Transaction // only transactions can be installed{ public static int syncCount, asyncCount, timerCount, taCount; // shared variables

public void run(){ taCount++; // count TA invocations, no conflicts

asyncCount++; // expect interference hereMAGIC.Inline( 0xFA ); // CLI, clear interrupt flagsyncCount++; // interrupts are suppressedMAGIC.Inline( 0xFB ); // STI, set interrupt flagif ( syncCount>=1000000000) remove(); // uninstall the transactionif ( ( syncCount % 1000000) == 0) printIt(); // see below

} ... }


I.5.5. Timer-Routine:Während der Ausführung der ISR sind die Interrupts gesperrt:

weitere externe Interrupts sind hier nicht möglich (interne schon),kann nicht gestört werden, stört aber die reguläre Transaktion,die ISR-Methode läuft "atomar" ab (reicht aber nicht).

package devices; // timer must go into package devicespublic class Timer extends Device // Handle interval timer - through int. #0{ final int blinker = 0xb8000 + 3998; // last Screenposition, ... + 25 * 80 * 2 -2

public int ISR() { // second level handler onlySyncDemo.syncCount++; // static context accessibleSyncDemo.asyncCount++;SyncDemo.timerCount++; // Timer invocationsSTATION.ticks=STATION.ticks+1; // actual timer workif((STATION.ticks % 18) == 0 )

MAGIC.Mem32[blinker]=MAGIC.Mem32[blinker] ^ 0x7700; // alivereturn 1; // interrupt was handled

} }


I.6. Kontextumschaltung

Kontextelemente:Programmzähler, CPU-Register, Ausführungskeller (Stack), Flags & Prioritäten,Adressabbildung, Klassen- & Instanzvariablen, Dateien, Zugriffsrechte, . . .

Kontextcontainer ( Kontext-Abstraktion ?):als Konstrukte in verschiedenen Programmiersprachen zu finden.

hat eigenen => Scope Code PC concurrent Stack Adressraum Resourcen Objektinstanz ja nein nein nein nein nein neinModul/Klasse ja ja nein nein nein nein neinProzedur ja ja ja nein nein nein neinTransaktion ja ja ja ja nein nein neinThread ja ja ja ja ja nein neinProzess ja ja ja ja ja ja ja

Der getrennte Adressraum erschwert die Interprozesskommunikation.Resourcen sind zum Beispiel Zugriffsrechte, Priorität, Dateien, Heap ...Wichtig bei Transaktionen ist oft die isolierende Zugriffssemantik.


I.6.1. VerarbeitungsmodelleKooperatives Multitasking:

die einzelnen Tasks (Teilaufgaben) laufen solange, bis sie freiwillig die Kontrolle abgeben,keine "Preemption" von Tasks niedrigerer Priorität durch solche mit höherer Priorität,minimale Kontextumschaltung, entsprechend einem Prozeduraufruf, nur ein Stack ist vorhanden, der von allen genutzt wird,Interrupts als "accidental" Prozeduraufruf,ein gemeinsamer Adressraum,z.B.Plurix-Transaktionen.

Multitasking mit Koroutinen:explizite Umschaltung des Laufzeitkellers (Stack),enterCoroutine(), exitCoroutine() ...

Multithreading:Umschaltung des Laufzeitkellers durch das Betriebssystem,die verschiedenen Threads teilen sich den Adressraum.

Prozessumschaltung (!=Multiprocessing):zusätzlich zum Multithreading wird auch der Adressraum umgeschaltet,umfassende Isolation der einzelnen nebenläufigen Prozesse,wechselseitiger Zugriffschutz zwischen Prozessen,Interprozesskommunikation aufwendig,zeitaufwendige Prozessumschaltung.


I.7. SynchronisierungsmechanismenI.7.1. Übersicht über SynchronisierungstechnikenTest & Set: Besondere Maschineninstruktionen, auch für MP-Szenarien.Interruptsperre: verhindert Umschaltung, aber nur auf einer CPUSignal und Wait: Spezialfall einer BarrierenoperationMutex (Windows): Windowsvariante einer Semaphor-VariablenMonitore (P. Hansen): High-level Konstrukt z.B. für Concurrent Pascal.Semaphore (E. Dijkstra): Synchronisierungsvariable mit atomaren Op.Rendez-vous (ADA-Sprache): Gleichzeitiges Warten auf Eventgruppe.Synchronized Anweisung (Java-Sprache): ~ kritische Region.CSP - Communicating Sequential Processes (C. Hoare).Software-based mutual exclusion (Peterson's Algorithmus).


I.7.2. Atomare Maschinenoperationen Viele CPUs haben eine atomare Test-&-Set-Instruktion:Test: Speicherwort lesen & prüfen, Set: Speicherwort auf "true" setzen.

Instruktionsablauf mit atomarer / unteilbarer Bustransaktion:

kein Zugriff durch DMA oder Bus-Master.keine Interrupts an der eigenen CPU,Cache-Konsistenz gewährleistet,kein Zugriff durch andere CPUs,reservieren des Speicherbusses.

Sperre implementieren (mit Busy-Waiting):boolean Sperrflag = false;

void Sperren () { while ( Test_And_Set ( & Sperrflag )) ; // spin lock, busy } void Freigeben () { // Sperre aufheben Sperrflag = false; }


Speicher

Prozessoren & DMA

Bus

I.7.3. Sperren von Interrupts als „Thread-Umschaltsperre“Werden Threads rein zufällig umgeschaltet, so entstehen Nichtdeterminismen.

Durch Sperren der Interrupts wird das Umschalten vermieden:CLI, STI bedienen das Interrupt Enable Flag der CPU und sperren Interrupts,sind privilegierte x86-Instruktionen - nur für Treiber & OS zulässig,unbrauchbar für Multiprozessorszenarien.

Vorsicht beim Sperren der Interrupts:Nur für sehr kurze Abschnitte in Kern und Treibern empfohlen,sonst Scheduler, Effizienz und Fairness beeinträchtigt,rekursive Interrupt-Sperre ist heikel.

Problem einer verschachtelten Interrupt-Sperre:nur die äusserste Verschachtelung darf die Interrupts wieder einschalten !


void myFunction( ) { . . .

CLI() // disable Interrupts// kritischer Abschnitt. . .STI() // enable I.

}

...CLI()... // kritischer Abschnitt 2if ... then STI() // falls nesting=0

I.7.4. Semaphor-VariablenSemaphor: (Wortbedeutung aus dem Griechischen)

optischer Telegraph; Mast mit Armen, durch deren Verstellung Zeichen zur Nachrichtenübermittlung weitergeleitet werden; schon im Altertum bekannt; Im Eisenbahnwesen auch Bezeichnung für ein Hauptsignal; in der Schiffahrt zur Anzeige von Windrichtung und Windstärke von der Küste aus.

Variable zur Synchronisierung mit folgenden atomaren Operationen:

Initialisieren: InitSem( semVar ),"Passieren"?: P( semVar )"Vreigeben": V( semVar )

vorgeschlagen durch E. Djikstra, 1968.Binäre Semaphore mit Werten 0 oder 1.

Zählende Semaphore mit Werten 0 .. n.

Originalsprache Holländisch ...


semVar:=semVar+ 1;if { mindestens 1 Prozess wartet }

then anstossen( Prozess )

if semVar > 0 then semVar:=semVar-1else { warten auf V( semVar ) }

I.7.5. FunktionsmodellSemaphore werden z.B. mit Test&Set-Instruktionen implementiert:

Entweder direkt durch den Compiler oder durch die Laufzeitunterstützung ...

Semaphor-Variablen haben Queue zur Verwaltung wartender Threads.Beim Starten wartender Threads evt. Prioritäten berücksichtigen.Einträge verweisen auf Task-/Thread-/Process-Kontrollblöcke,kein Busy-Waiting, keine leeren CPU-Zyklen,alle wartenden Threads sind „blocked“.


sem=0

Warteschlange

sem>0

I.7.6. Beispiel einer Semaphor-Variablen in Windows NThSem dient hier dazu, die Anzahl der Nutzer einer Ressource zu beschränken:

#include <windows.h> HANDLE hSem;

void SomeUser() {WaitForSingleObject( hSem, INFINTE); // = P( ) Operation;use_resource( ); // kritischer Abschnitt// semaphor, release-cnt., before-cnt.ReleaseSemaphore( hSem, 1, NULL); // = V( ) Operation;

} int main() {

// security descriptor, start-cnt., max.-cnt., name hSem = CreateSemaphore( NULL, 20, 20, NULL); …

}


I.7.7. MonitoreKonstrukt für Synchronisierung:

"serially reusable Module".C.A. Hoare, P.B. Hansen, 1974.

Monitor-Prozeduren garantieren:kein externer Zugriff auf Monitorvariablen,jeweils nur ein Thread im Monitor,automatische Freigabe des Monitors beim Rücksprung.

Im Vergleich dazu sind Semaphore etc. low-level Sprachelemente:Grösseres Risiko von logischen Programmierfehlern,ohne V() tritt eventuell eine Verklemmung auf,ohne P() kein gegenseitiger Ausschluß.


I.7.8. Incrementer-Monitor (Beispiel in "Concurrent Pascal"):Die Laufzeitumgebung sorgt mit Unterstützung des Compilers dafür, daß sich nur ein Thread im Monitor befindet.Realisiert eine ge-schützte kritische Region oder meh-rere verbundene.Stützt sich in der Regel auf Sema-phore des Betriebs-systems ab.Im Prinzip bietet auch Java Monitore. An Stelle von Monitoren werden aber Instanzen und Klassen mit dem Attribut "synchronized" verwendet.


monitor Incrementer; { Concurrent Pascal } var zaehler: integer;

procedure PlusEins; { P( IncSem ) implizit } begin

zaehler:= zaehler+1 end { PlusEins }; { V( IncSem ) implizit }

procedure PlusZwei … end;

begin { initialize }zaehler := 0

end { Incrementer }.

I.7.9. Dining PhilosophersSzenarium:

Problemstellung nach Edsger W. Djikstra,N Philosophen sitzen um einen Tisch,Sie denken & wollen Spaghetti essen,Zum Essen jeweils 2 Gabeln nötig,hier angepasst auf Steak & Messer.

Wissenheim-Animation:Modellierung Björn Mantelars,Betreuung Markus Fakler,

www.wissenheim.de => play => Java Applet => Applet embedded => Philosopher Island=> Cursor Tasten ...


http://www.wissenheim.de/

Java Lösungsansatz: Zustand eines Philosophen: THINKING, HUNGRY, EATING, STARVED.Boole'scher Array forks[]: Besetzte Gabeln dürfen nicht genommen werden,Essen nur möglich, wenn kein Nachbar gerade isst.Links = i; Rechts = (i+1) mod N;Konstruktor für Philosophen.

public class Philosopher extends Thread {static final String blanks= ": ";static final int MXPH=7, // How many philosophers ?static final int delayTime=10111222; // delay instead of try & sleep static boolean[] fork= new boolean[MXPH]; // one fork for each philosopherString indent, state="thinking "; // initial state is thinkingint starvation, lnx, rxz; // how hungry? Which forks?

Philosopher(int idParm){ // construct a philosopherthis.lnx=idParm; rxz=(lnx+1)% MXPH; // left & right forksindent=blanks.substring(0,3+10*lnx); // indent output

}static void delay(long count){ // rather than try ... sleep ... catch

while( count-- >0);}


Hauptschleife eines einzelnen Philosophen:denkend, hungrig, essend und evtl. verhungert,Zustand auf Konsole ausgeben,CPU abgeben mit yield().

public void run() { // start philosopherwhile(true){ // loop forever

delay(delayTime); print(this); yield(); // spend time, print state ...if(state.equals("thinking ")) // for some delayTime already

state="hungry "; // even philosph. get hungryelse if(state.equals("eating ")){

dropForks(lnx,rxz); // make sure to dropstate="thinking "; // now finish eatingstarvation=0; // enough to eat

}else if(state.equals("hungry ")){ // will not eat if not hungry

if( takeForks(lnx,rxz) ) state="eating "; // takeForks successfulelse if(starvation++ >7) state="starved "; // starving until overflow ...

} }

}


Kritische Region synchronisieren:Methoden: Gabeln nehmen, Gabeln ablegen, Drucken,nur Synchronisierung auf ein Objekt oder auf eine Klasse möglich,hier also hinsichtlich der Philosophenklasse (forks kein Objekt!),nicht auf Instanz, sondern auf Klasse!

synchronized static boolean takeForks(int lnx,int rxz){ // synchronize on class !If( fork[lnx] | fork[rxz] ) return false; // forks not availablefork[rxz]=true; fork[lnx]=true; // avoid access collisionreturn true; // forks taken

}synchronized static void dropForks(int lnx, int rxz){

fork[rxz]=false; fork[lnx]=false; // avoid access collision}synchronized static void print(Philosopher p){

int i=0;while(i<MXPH) { // print state of all forks

if(fork[i++]) System.out.print('1'); else System.out.print('0');

}System.out.println(p.indent+p.state+p.lnx); // state of this philosopher

} }


Programmausgabe:1101100: eating 01101100: eating 31101100: hungry 61101100: starved 51101100: hungry 40001100: starved 20111100: thinking 01111101: eating 11110001: eating 61110111: thinking 31110111: eating 41110111: starved 51110111: hungry 01110111: starved 21000111: thinking 10000110: hungry 30000110: thinking 60000000: starved 50000000: thinking 41100000: starved 21100000: eating 01100000: hungry 11101100: eating 31101100: hungry 61101100: starved 51101100: hungry 40001100: starved 20111100: thinking 01111101: eating 11110001: eating 61110111: thinking 31110111: eating 41110111: starved 51110111: hungry 00110110: starved 20000110: thinking 60000000: thinking 10000000: thinking 41100000: hungry 31100000: eating 01100000: starved 5


Documents

I.Nebenläufigkeit - Distributed Systems (Uni Ulm) · I.3.Synchronisierung nebenläufiger Abläufe Mehrprogrammbetrieb: Programme greifen auf die gemeinsame Hardware & Software zu,