Praktische Informatik 1
Yüklə 3,49 Mb.
|
9.4 ParallelitätIm objektorientierten Paradigma bedeutet Berechnung die Interaktion von Objekten. Das bedeutet, dass mehrere Objekte gleichzeitig existieren. In der sequentiellen Programmierung ist jedoch immer nur eines dieser Objekte aktiv. Anfangs gibt es nur das statische Main-Objekt. Dieses erzeugt andere Objekte und ruft diese auf. Jeder Aufruf ist blockierend, d.h. der Aufrufer muss warten, bis das aufgerufene Objekt fertig ist und die Kontrolle zurückgibt. Folglich ist zu einem gegebenen Zeitpunkt immer nur ein Objekt rechnend. Parallelität bedeutet, dass mehrere Handlungsstränge zur selben Zeit ablaufen. Dies ist
Es gibt in Java mehrere Arten der Parallelität:
Threads in Java In Java gibt es zwei Arten der Definition
Beispiel (1): Wir erzeugen eine Erweiterungsklasse von Thread mit Methode run. Diese wird dann vom aufrufenden Programm aus gestartet. class Toe extends Thread { public void run() { System.out.println("Prozess Toe gestartet"); }
Toe toe = new Toe(); toe.start(); System.out.println("Prozess Toe beendet"); } } Achtung: Das Ergebnis ist (in dieser Reihenfolge!): Prozess Toe beendet Prozess Toe gestartet
Thread faden; private int wer; public TicTac(int w) { faden = new Thread(this); wer=w;}
System.out.println("Prozess T"+((wer==1)?"i":"a")+"c gestartet"); } } public static void main(String[] args) { TicTac tic = new TicTac(1); TicTac tac = new TicTac(2); tic.faden.start(); tac.faden.start(); try {tic.faden.join(); tac.faden.join(); } catch (Exception e) {} System.out.println("alles beendet"); } } Wie das Beispiel zeigt, kann der Aufrufer auch auf die Beendigung eines Threads warten. Beispiel (3) zeigt, dass man bei der parallelen Programmierung vorsichtig sein muss, weil sich leicht Fehler einschleichen. Wir inkrementieren und dekrementieren eine gemeinsame Variable in zwei verschiedenen Threads gleich oft. class TicTac implements Runnable{ static int summe = 0; Thread faden; private int wer; public TicTac(int w) { faden = new Thread(this); wer=w; }
for(int i=1; i<10000; i++) { if(wer==1) summe = summe + 1; else summe = summe - 1; } } public static void main(String[] args) { TicTac tic = new TicTac(1); TicTac tac = new TicTac(2); tic.faden.start(); tac.faden.start(); try {tic.faden.join(); tac.faden.join(); } catch (Exception e) {} System.out.println("Summe=" + summe); } } Der Thread tic zählt die Variable summe hoch, der Thread tac zählt sie runter. Das Ergebnis ist aber nicht in jedem Fall 0, sondern unvorhersagbar. (Für „kleine“ Schleifen ergibt sich jedoch immer 0). Interpretation der Ergebnisse
Interleaving Durch verzahnt Ausführung (wie bei einem Reißverschluss) können mehrere Prozesse auf nur einem Prozessor ausgeführt werden. Jeder Prozess erhält dabei der Reihe nach eine Zeitscheibe einer bestimmten Dauer zugewiesen (die Dauer ist nicht notwendigerweise immer gleich (Bild „Einfädeln“ von Autos bei einer Baustelle). Beim Zugriff auf gemeinsame Variable kann es dabei zu unerwarteten Ergebnissen kommen: Der Befehl {s++} wird zur Befehlsfolge {load s; add 1; store s} übersetzt. Analog bedeutet {s--} in Maschinensprache {load s; sub 1; store s}. Verschiedene Prozesse benutzen dabei verschiedene Register für die Rechnung. Bei zwei Prozessen, die beide auf dieselbe Variable zugreifen ergeben sich jedoch bei der quasiparallelen Ausführung von s++ || s-- folgende Szenarien: s=5 (z.B.)
aber auch:
oder
Das bedeutet, wenn man s simultan inkrementiert und dekrementiert, ist das Ergebnis zufällig s oder s+1 oder s-1! Wenn wir diesen Effekt oft wiederholen (for (int i = 0; i<1000000; i++)) verstärkt sich der Fehler. Prozess-Zustände Prozesse können dem Laufzeit- oder Betriebssystem selbst ankündigen, ob sie nach Ablauf ihrer Zeitscheibe weiter ausgeführt werden sollen oder nicht. Das nennt man präemptives Multitasking. 
Zur Synchronisation von Prozessen gibt es in Java folgende Möglichkeiten:
Ein Monitor ist eine Klasse, die die Unteilbarkeit auf die von ihr verwalteten Ressourcen garantiert. Dies geschieht mit dem Schlüsselwort synchronized vor einer Methode. class Monitor { private int i = 0; synchronized void inc() { i++;} synchronized void dec() { i--;} int val() { return i; } class TicTacMon implements Runnable{ static Monitor summe = new Monitor(); Thread faden; private int wer; public TicTacMon(int w) { faden = new Thread(this); wer=w;}
System.out.println("Prozess " + wer + " gestartet"); for(int i=1;i<10000000;i++) { if(wer==1) summe.inc(); else summe.dec(); } System.out.println("Prozess "+ wer + " beendet"); } public static void main(String[] args) { TicTacMon tic = new TicTacMon(1); TicTacMon tac = new TicTacMon(2); tic.faden.start(); tac.faden.start(); try {tic.faden.join(); tac.faden.join();} catch (Exception e) {} System.out.println("Summe=" + summe.val()); } }
synchronisierte Methoden Für jedes Objekt gibt es ein intrinsisches Schloss, welches den Zugang einschränkt. Während des Ablaufs einer synchronisierten Methode wird das Schloss verschlossen, daher kann keine andere synchronisierte Methode dieses Objekts gleichzeitig ablaufen. Diese muss ggf. warten (Gefahr der Verklemmung (deadlock)!) Mit einer Synchronisationsanweisung lässt sich der gleiche Effekt wie mit einem Monitor erzielen: class Mutex {}; class TicTac implements Runnable{ static Mutex m = new Mutex(); ...
public void run() { for(int i=1;i<10000000;i++) { synchronized(m) { if(wer==1) summe++; else summe--; } ... Dinierende Philosophen Dieses Standardbeispiel von E.W.Dijkstra verdeutlicht die Probleme, die bei der Koordinierung paralleler Abläufe durch die Konkurrenz um gemeinsame Betriebsmittel auftreten können. 5 Philosophen sitzen um einen runden Tisch, in der Mitte steht eine Schüssel Spaghetti. Zwischen je zwei Philosophen ist eine Gabel (bzw. ein Ess-Stäbchen). Jeder Philosoph betätigt sich zyklisch nur mit den Tätigkeiten denken – essen – denken – essen – denken – essen – denken –... Zum Essen benötigt ein Philosoph allerdings zwei Gabeln / Ess-Stäbchen, nämlich die zu seiner linken und zu seiner rechten. Ein einfacher Algorithmus für jeden Philosophen wäre also: wiederhole immer wieder: denke
warte, bis linke Gabel frei, dann nimm sie warte, bis rechte Gabel frei, dann nimm sie iss gib beide Gabeln wieder frei In Java lässt sich das etwa wie folgt formulieren: public class Gabel { private boolean benutzt = false; private int welche; Gabel (int i){welche = i;} synchronized void aufnehmen() throws InterruptedException { while (benutzt) wait(); System.out.println("Gabel " + welche + " aufgenommen"); benutzt = true; }
benutzt = false; System.out.println("Gabel " + welche + " hingelegt"); } }
private int wer; private static int n = 5; private static Gabel [] gabel = new Gabel [n]; private static Philosoph [] phil = new Philosoph [n]; Philosoph (int i){wer = i;} public void run (){ System.out.println("Philosoph " + wer + " gestartet"); try{ while (true){ System.out.println("Philosoph " + wer + " denkt"); sleep((long)(10000*Math.random())); // Denken System.out.println("Philosoph " + wer + " hungrig"); gabel[(wer==0)?n-1:wer-1].aufnehmen(); gabel[wer].aufnehmen(); System.out.println("Philosoph " + wer + " isst"); sleep((long)(10000*Math.random())); // Essen gabel[(wer==0)?n-1:wer-1].hinlegen(); gabel[wer].hinlegen(); } } catch(InterruptedException e){} } public static void main(String[] args) { for (int i=0; i<n; i++){ gabel[i] = new Gabel (i); phil[i] = new Philosoph(i); }
phil[i].start(); } }
Diese Lösung ist allerdings verklemmungsbedroht! Es kann passieren, dass jeder Philosoph individuell seine linke gabel nimmt (damit liegt keine Gabel mehr auf dem Tisch) und dann wartet, bis er die rechte nehmen kann (was aber nie passieren wird). Allgemein ist eine Verklemmung (deadlock) ein zyklischer Wartezustand: A wartet auf B, B wartet auf C, …, Y wartet auf Z und Z wartet auf A. Ein Applet, um diesen Effekt auszuprobieren, findet sich z.B. unter http://www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html  
Ein etwas besserer Algorithmus vermeidet das Verklemmungsproblem. Jeder Philosoph macht folgendes: wiederhole immer wieder denke wiederhole solange bis beide Gabeln genommen wurden: warte, bis linke Gabel frei, dann nimm sie falls rechte Gabel nicht da, gib linke wieder frei warte, bis rechte Gabel frei, dann nimm sie falls linke Gabel nicht da, gib rechte wieder frei iss gib beide Gabeln wieder frei Obwohl diese Lösung nachweislich verklemmungsfrei ist, hat sie einen anderen gravierenden Nachteil: Es ist möglich, dass sich einzelne oder alle Philosophen endlos in einer sinnlosen Beschäftigung verlieren, in dem sie abwechselnd die linke und rechte Gabel aufnehmen und wieder ablegen. Solch eine Situation nennt man manchmal Endlosschleife (livelock); formal ist das eine Situation, in der intern immer dieselben Handlungen ausgeführt werden, ohne dass nach außen irgend ein Fortschritt erkennbar wäre. Ein noch besserer Algorithmus vermeidet dieses Problem, indem durch einen geeigneten Synchronisationsalgorithmus das Aufnehmen beider Gabeln simultan erfolgt. Jeder Philosoph macht also folgendes: wiederhole immer wieder denke warte, bis beide Gabeln frei, dann nimm sie (beide gleichzeitig) iss gib beide Gabeln wieder frei (und teile dies ggf. den Nachbarn mit) Das simultane Aufnehmen der beiden Gabeln kann in Java dadurch programmiert werden, dass ein Monitor den Zugriff auf die Gabeln regelt. Die Lösung hat jedoch immer noch eine Schwäche: Es kann sein, dass zwei Philosophen sich zusammentun, um den zwischen ihnen sitzenden „auszuhungern“: Philosoph 2 ist hungrig, aber erst isst Philosoph 1 (und 2 wartet auf die linke Gabel), und dann Philosoph 3 ( und 2 wartet auf die rechte Gabel). Allgemein ist ein System aushungerungsfrei (starvation free), wenn garantiert ist, dass jeder kontinuierlich fortsetzungswillige Prozess auch irgendwann fortgesetzt wird. Aushungerungsfreiheit ist ein spezieller Fall der so genannten Fairness, die garantiert, dass kein Prozess immer wieder benachteiligt wird. Allgemeine Fairness-Eigenschaften lassen sich programmtechnisch nur schwer garantieren; pragmatische Lösungsmöglichkeiten bestehen darin
Yüklə 3,49 Mb. Dostları ilə paylaş:
|