1

VE 11

Kruskal-Realisierung

Listen

2

Auf dem Weg zur Kruskal-Realisierung

Vorüberlegungen:• Der Graph könnte dargestellt werden als Menge von

Knoten, jeder Knoten kennt seine Nachbarn.• Der Spannbaum könnte dargestellt werden als Menge von

Kanten.• Die Partition könnte als Menge von Knotenmengen

dargestellt werden.• Gerade die Darstellung von Knotenmengen wird eine

zentrale Rolle spielen.

3

Auf dem Weg zur Kruskal-Realisierung

Vorüberlegungen:

• Deshalb: Welche Operationen auf Mengen werden gebraucht:• Initialisieren einer Menge als leere Menge• Prüfen, ob ein Element in einer Menge enthalten ist• Einfügen eines Elements in eine Menge• Entfernen eines Elements aus einer Menge• Iteration über die Elemente einer Menge• Finden eines Elements einer Partition (also einer Menge), das selbst

ein Element der Grundmenge enthält

4

class ObjElement

5

class ObjectListe

6

class Kante

7

class KantenListe

8

VE 11

Threads

9

Threads

• Bislang wurde ein Programmteil in unseren Beispielen nur einmal ausgeführt, nicht mehrmals parallel.

• Parallele Ausführung ist aber sinnvoll. Z.B. immer dann, wenn Ressourcen (auf Anwendungsebene!) geteilt werden sollen, z.B.:• Objekte und Attribute• Zugriff auf Datenbanken

• Paralleler Zugriff auf geteilte Ressourcen funktioniert über so genannte Threads („Fäden“). Threads sind Teile eines Programms, die innerhalb des Programms parallel ausgeführt werden.

10

Threads

• Der Zusammenhang zwischen den Threads ergibt sich dabei in der Regel gerade durch das Teilen der Ressourcen.

• Threads können auf einer Maschine mit nur einem Prozessor ablaufen und sich dabei aufführen, als ob sie eigene Prozesse wären.

• Ein Thread wird deshlab auch Ausführungskontext oder leichtgewichtiger Prozess genannt.

• Ihr Unterschied zu wirklich eigenständigen Prozessen ist, dass sie aus einem Hauptprogramm erzeugt werden.

• Ein Thread modelliert Objekte, die innerhalb eines umgebenden Prozesses einen eigenen Kontrollfluss haben.

11

Multithreading

• Multithreading bedeutet:

• Programmpfad wird in unterschiedliche Richtungen verzweigt, diese laufen parallel.

• Multithreading bedeutet nun, dass es möglich ist, mehrere Thread parallel laufen zu lassen (bei nur einem Prozessor ist dies natürlich keine echte Parallelität).

12

Threads

• Bisher: Single-Threaded Execution

• Neu: Multi-Threading

Methode a Methode b

Methode c

t

Methode a Methode b

t

Methode c

Methode c

13

Multithreading

• Probleme:• Konkurrierende Threads benutzen gleiche Ressourcen und Daten

=> Bei Zugriff auf gemeinsam genutzte Ressourcen muss Schutz greifen (nur ein Thread hat den Monitor, der die Ressource kontrolliert)

• Threads, die mehrere Ressourcen gleichzeitig benötigen, können sich gegenseitig blockieren (Deadlock), indem sie jeweils eine Ressource festhalten und auf die anderen warten.

• Nicht jede Virtual Machine verteilt CPU-Zeit automatisch gerecht(Es gibt Timeslicing-fähige und -unfähige Systeme)=> Laufende Threads sollten auch anderen eine Chance geben

• Mögliche Zustände oft schwer verständlich, da Parallelität nicht gerade intuitiv verständlich

14

Threads

• In Java: Threads sind Objekte, die Thread erweitern und damit dann auch das Interface Runnable implementieren

public class Thread implements Runnable { ... public void run(); public void start(); ...}

• Threads müssen die Methode run() überschreiben (dort passiert die Arbeit!)

• Wird von einem Thread-Objekt die (eingebaute) start()-Methode aufgerufen, startet eine Ausführung von run().

• Durch mehrfaches Aufrufen von start() können mehrere Ausführungen von run() parallel ausgeführt werden.

15

Beispiel

class AddThread extends Thread{ public void run(){

for(int i=0;i<10;i++){ MyThreadExample.count++; System.out.print("Add "); System.out.println

(MyThreadExample.count); } }}

16

Beispiel

class SubtractThread extends Thread{ public void run(){ for(int i=0;i<10;i++){ MyThreadExample.count--; System.out.print("Subtract "); System.out.println(MyThreadExample.count); } }

}

17

Beispiel

class MyThreadExample{

public static int count=0;

public static void main(String args[]){ AddThread a = new AddThread();

SubtractThread b = new subtractThread(); a.start(); b.start();

} }

18

Beispiel

Mögliches Ergebnis

Add 1 Add 2 Add 3 Add 4 Add 5 Subtract Add 5 5 Add Subtract5 Subtract 4 4 ...

19

Beispiel

class AddThread extends Thread{ public void run(){

for(int i=0;i<10;i++){ System.out.print("Add start ");

MyThreadExample.count++; System.out.println("Add end:"

+ MyThreadExample.count);

} }}

20

Beispiel

class SubtractThread extends Thread{ public void run(){ for(int i=0;i<10;i++){ System.out.print("Sub start");MyThreadExample.count--; System.out.println("Sub end:"+ MyThreadExample.count);} }

}

21

Beispiel

class MyThreadExample{ public static int count=0; public static void main(String args[]){

AddThread a = new AddThread(); SubtractThread b = new

subtractThread(); a.start(); b.start();

} }

22

Beispiel

Mögliches Ergebnis 1:Add start Sub start Sub end:0Add end:0Add start Sub start Add end:1Add start Sub end:0Add end:1Sub start Add start Sub end:1Add end:1Sub start Add start Sub end:0Sub start Add end:0Sub end:0Sub start Sub end:-1Add start Sub start Add end:-1Add start Add end:0Sub end:0Add start Add end:1Add start Add end:2Sub start Add start Add end:2Sub end:2Sub start Sub end:1Sub start Sub end:0

Mögliches Ergebnis 2:Add start Add end:1Add start Add end:2Add start Add end:3Add start Add end:4Add start Add end:5Add start Add end:6Add start Add end:7Add start Add end:8Add start Sub start Sub end:7Sub start Sub end:6Sub start Sub end:5Sub start Sub end:4Sub start Sub end:3Sub start Sub end:2Sub start Sub end:1Sub start Sub end:0Sub start Sub end:-1Sub start Sub end:-2Add end:-1Add start Add end:0

23

Thread / Runnable

• Ein Thread wird immer in einer run-Methode gestartet• public void run()• Diese Methode muss von einer Klasse implementiert werden,

dessen Objekt sich mit einem eigenen Thread ablösen möchte• Bei Start des Threads wird die run-Methode vom System

automatisch aufgerufen (nicht selbst aufrufen!)

• Ein thread-fähige Klasse kann durch zwei Möglichkeiten definiert werden:• Erben von der Klasse Thread, hier muss die run()-Methode der

Klasse Thread überschrieben werden• Implementieren des Interfaces Runnable, hier muss die run()-

Methode des Interfaces implementiert werden

24

Using the Runnable Interface

class AddThread extends SomeClass implements Runnable{ public void run(){

for(int i=0;i<10;i++) SyncThread.incCount();

} } ...// Where the thread shall be started// a new Thread Object is createdAddThread a = new AddThread();Thread this_is_the_Thread = new Thread(a);this_is_the_Thread.start();...

25

Warum zwei Möglichkeiten?

• Die einfachere Möglichkeit ist es, von Thread abzuleiten

• Aber: • Java kennt keine Mehrfachvererbung von Klassen, jedoch

Mehrfachvererbung von Interfaces• Es ist wünschenswert, auch Unterklassen multithreading-fähig zu

machen

=> Hier bleibt nur die Möglichkeit, Runnable zu implementieren

26

Methoden von Thread

• Konstruktoren:• public Thread()

• Muss von abgeleiteter Klasse durch super() aufgerufen werden

• public Thread(String name)• Muss von abgeleiteter Klasse durch super(name)

aufgerufen werden• Dem Thread wird hier ein Name gegeben

• public Thread(Runnable target)• Muss direkt aufgerufen werden, um Threads über das Runnable-Interface zu definieren

• Methoden:• public synchronized void start()

• Startet den Thread. Die virtuelle Maschine startet die run()-Methode in eigenem Programmpfad

• synchronized ist neues Schlüsselwort, später mehr

27

Methoden von Thread

• Methoden:• public static Thread currentThread()

• Klassenmethode, um den aktuell laufenden Thread zu ermitteln• public static void yield()

• Aufforderung, eventuell andere wartende Threads zum Zuge kommen zu lassen

• public static void sleep(long millis) throws InterruptedException

• Thread wartet angegebene Zeit. Andere Threads kommen zum Zuge, sofern sie nicht durch belegte Resourcen blockiert sind

• public final void setPriority(int newPriority)• Legt die Priorität des Threads fest. Threads höherer Priorität laufen

bevorzugt• public final String getName()

• Gibt den Namen des Threads zurück

28

Deaktivierung eines Threads

• Methoden:• sleep

• siehe oben• suspend

• Unterbricht die Arbeit eines Prozesses• wait

• veranlasst, dass ein Prozess eine vorgegebene Zeit wartet

• von Object ererbt

29

Aktivierung eines passiven Threads

• Methoden:• resume

• Gegenstück zu suspend• notify, notifyAll

• reaktiviert wartende Prozesse (Gegenstück zu wait)• von Object ererbt

30

Vernichten eines Prozesses

• Methoden:• stop

• anomale und sofortige Beendigung eines aktiven oder gerade erzeugten Prozesses (mit Aufräumarbeiten)

• destroy• wie stop aber ohne Aufräumarbeiten

31

• Ein neuer Thread (Zustand new), der noch nicht ausgeführt wurde, erfordert vor der ersten Ausführung erst mal die Zuweisung von Ressourcen (Speicher).

• Dann wird er mittels der Methode start() in den Zustand runnable überführt.

• Runnable bedeutet, dass der Prozess durchgeführt werden kann (also aktiv werden kann). Allerdings kann nur ein Prozess zu jeder Zeit aktiv sein.

• Die wartenden, schlafenden, unterbrochenen Prozesse sind im Zustand blocked.

• Wenn der aktive Prozess in den Zustand blocked übergeht, dann wird ein runnable Prozess aktiviert.

Zustandsübergänge von Threads

32

• Die JVM wählt aus der Menge der runnable Prozesse den durchzuführenden aus.

• Hier gibt es Unterschiede zwischen den JVMs auf verschiedenen Plattformen !!

• Ein Prozess verlässt den Zustand blocked, wenn• die Schlafperiode zu Ende geht,• er notifiziert wird (notify),• die I/O-Operation, auf die er wartet, terminiert,• wenn er per resume fortgesetzt wird.

Zustandsübergänge von Threads

33

• Threads gehen in den Zustand dead über, wenn• seine run()-Methode beendet wird, • seine stop()- oder destroy-Methode aufgerufen wird.

• Ein dead Thread kann nicht reaktiviert werden.

Zustandsübergänge von Threads

34

Prioritäten

• Jeder Thread hat eine Priorität.• Die JVM bevorzugt die Threads mit hohen Prioritäten,

wenn ein Thread von runnable in aktiv überführt werden soll.

• Ein Thread läuft solange bis:• er die yield()-Methode aufruft, • er nicht mehr runnable ist (z.B. weil er auf einen initiierten I/O

warten muss),• ein Thread mit höherer Priorität runnable wird.

35

Zustandsübergänge von Threads