Präsentation: Christoph PlatenVertieferseminar 07.11.02 Vertieferseminar Geoinformation WS 02/03 Parallele Programmierung von Signalverarbeitung in Java

Präsentation: Christoph PlatenVertieferseminar 07.11.02

VertieferseminarGeoinformation WS 02/03

Parallele Programmierung von

Signalverarbeitung in Java

Signalverarbeitung 07.11.02 Christoph Platen

Vortragsgliederung

1. Motivation

2. Prozesskonzepte

3. Zustandsübergänge von Threads

4. verwendete Methoden

5. Programmierung von Threads

6. Race Condition

7. Monitorkonzept


Motivation

GPS-Empfänger

Kompass

Pointman

Tastatur

PCNebenprogramm

Hauptprogramm

Die in einzelnen Nebenprogrammenaufbereiteten Datenwerden durch ein Hauptprogramm

verarbeitet

Projektsituation im Sommersemester 03 :


Motivation

• Signalübertragung vom GPS-Empfänger zum PC nur dann, wenn Daten vorliegen

• alle anderen Anwendungen sollen parallel ablaufen ( Download, Tastatur, Drucker etc. )

• keine Wartezeiten,bis ein Programm komplett ausgeführt ist

• Ziel: Ablauf verschiedener Prozesse soll quasi parallel sein


Prozesskonzepte

• aus Kostengründen hat jeder Rechner nur einen Prozessor• bis in die 60er Jahre wurden Batch-Betriebssysteme

verwendet• dies bedeutet das der Programmablauf sequentiell war• ein Programm konnte den Prozessor besitzen, Programme

mussten nacheinander ausgeführt werden

Programm A Programm B Programm C Prozessor

Sequentieller Programmablauf in einem Batch-Betriebssystem


Prozesskonzepte

• Konzept eines Betriebssystem-Prozesses brachte Idee hervor ein Programm unterbrechbar zu machen (d.h. dem Programm das Betriebsmittel (Prozessor) zu entziehen)

• Prozessor wird an andere Prozesse abgegeben; findet der Wechsel schnell genug statt,so merkt Beobachter den stetigen Prozesswechsel nicht

• Prozesse laufen quasi parallel ab

C B A C B A C B A Prozessor

Time-Sharing-Betriebssystem: Prozess bekommt vom Scheduler eine bestimmte Zeitscheibe zugeordnet


Prozesskonzepte

• ein klassischer Betriebssystem-Prozess stellt eine Einheit für das Memory Management und das Scheduling dar

• es wird Platz im Arbeitsspeicher zugeordnet und Rechenzeit durch den Scheduler gewährt

• da der Kontextwechsel eines Betriebssystem-Prozesses mit der Verwaltung des Arbeitsspeichers gekoppelt ist spricht man von einem schwergewichtigem Prozess


Prozesskonzepte

• Moderne Betriebssysteme bedienen sich sogenannter Threads

• Threads sind nur eine Einheit für das Scheduling

• innerhalb eines Betriebssystem-Prozesses können mehrere Threads gleichzeitig ablaufen

• da ein Thread nicht mit der Verwaltung des Arbeitsspeichers gekoppelt ist spricht man von einem leichtgewichtigen Prozess


Prozesskonzepte

BetriebssystemProzess 1

BetriebssystemProzess 2

Thread 1Thread 2

Thread 3BetriebssystemProzess 3

Schaubild Threads und Prozesse


Zustandsübergänge von Threads

• Threads können ähnlich wie Betriebssystem-Prozesse verschiedene Zustände haben

• Zustandsübergänge können erfolgen als Konsequenz von Methodenaufrufen

• oder durch Aktionen des Betriebssystems (virtuelle Maschine)

• Zustand eines Prozesses hängt davon ab,welche Betriebsmittel er gerade besitzt


Zustandsübergänge von Threads

Zustandsübergänge von Threadsals Folge von Methodenaufrufen und der virtuellen Maschine

I/O Zugriff

I/O b

eendet

Scheduler w

eist Prozessor zu

Prozessor w

ird entzogen

new ready-to-run

blocked running deadsleep()

join()

yield()

start()

Join

() bee

ndet

Sleep

() bee

ndet

run() wird beendet


Zustände New und Ready-To-Run

New• Thread wird durch den new-Operator generiert • er befindet sich in seinem Anfangszustand• er ist noch nicht ablauffähig• Datenfelder und Methoden können angesprochen werden

Ready-To-Run• Thread hat alle Betriebs-

mittel um zu laufen,bis auf

den Prozessor


Zustände Blocked und Running

• ein laufender Thread

macht eine I/O Operation

und verliert den Prozessor• Methodenaufrufe wie

sleep() oder join()

versetzen Thread in

diesen Zustand

Blocked Running• Thread bekommt vom Scheduler den Prozessor zugeteilt


Methode start() und yield()

start()• überführt einen Thread

vom Zustand „new“ in

den Zustand „ready-to-run“• wurde Thread bereits

gestartet,so wird eine

Fehlermeldung ausge-

geben

yield()• bricht die Verarbeitung

des gerade laufenden

Threads ab • überführt diesen wieder in

den Zustand „ready-to-run“


Methode sleep() und join()

join()• ein Thread kann diese Methode eines andere Threads aufrufen

• aufrufender Thread wird in den Zustand „blocked“ versetzt, bis der Thread, dessen join() Methode aufgerufen worden ist, beendet ist

• gezieltes Warten auf einen Thread möglich

sleep()• versetzt den gerade

laufenden Thread für

msec bzw. nsec in den

Zustand „blocked“• Schrittauflösung von 1ms

bzw. 1ns ist Betriebs-

system abhängig


Methode interrupt()

interrupt()• wird zu einem gerade blockierten Thread aufgerufen • überführt diesen in den Zustand „ready-to-run“• ein Thread kann so vorzeitig aufgeweckt werden,wenn er

z.B. durch eine sleep() oder join() Methode in den Zustand

„blocked“ versetzt wurde• es wird eine sogenannte InterruptedException geworfen


Programmierung von Threads

• schreiben einer Thread Klasse und diese direkt von der Klasse java.lang.Thread ableiten

• Methode run() der Klasse java.lang.Thread ist zu überschreiben

• der in der Methode run() enthaltene Code wird während des „running“ Zustandes ausgeführt

Thread

Sohn 1 Sohn 2

Implementieren von Threads durch das Ableiten von der Klasse Thread


Programmierung von Threads

Rechenzeit wird durch Scheduler zuge-wiesen und Methode run () ausgeführt

Nach Ablauf der Zeit geht Thread wieder in den Zustand „ready-to-run“

Die Klasse Time wird definiert,indem man direkt von der Klasse java.lang.Thread ableitet

In der Klasse Uhr wird mit new ein Objektder Klasse Time erzeugt und somit ein neuer Thread generiert

Geerbte Methode start() versetzt ThreadIn Zustand „ready-to-run“

Methode start() ruft Methode run() auf

Aktuelle Datum wird ausgegeben

Methode sleep() versetzt Thread für 100msec in den Zustand „Blocked“

Interrupt() Methode beendet bei Aufruf die Methode run()


Zugriff auf gemeinsame Ressourcen

• benutzen mehrere Threads dieselben Daten, so kann es zu Synchronisationsproblemen kommen

• beispielsweise bekommt ein schreibender Thread den Prozessor entzogen ehe er mit dem Schreiben der Datei fertig ist

• der Lese-Thread beginnt jedoch schon zu lesen und erhält inkonsistente Daten. ( Reader/Writer-Problem)

• man spricht von einer Race Condition, bei der das Ergebnis von der ausgeführten Reihenfolge der Threads abhängt

• um sinnvolle Ergebnisse zu erhalten ist eine Abarbeitungsreihenfolge ( Synchronisation) der Threads zwingend erforderlich


Race Condition

• Beispiel: Threads 1 und 2 greifen auf eine gemeinsam genutzte Variable (Array) zu

Thread 1 schreibt Messdaten in das Array beginnend ab Array-Index 1 und die Anzahl der Werte in die Variable Zähler

Thread 2 liest die Daten aus und quittiert das Auslesen, indem er die Zählvariable auf 0 setzt

es kann sein, dass schneller geschrieben als gelesen wird

Zähler

Wert 1

Wert 2

Wert n-2

0

1

3

2

n-1

2

7

37

Array mit einem Zähler für die benutzten Elemente


Race Condition

Sequenzdiagramm zur Darstelung einer Race Condition. Die Zeitachse t gibt den zeitlichen Verlauf an

Zähler lesen

Daten schreiben

Zähler erhöhen

Zähler lesen

Daten lesen

Zähler auf 0 setzen

Thread 1 Thread 2Gemeinsame

Variable

Thread2aktiv

Thread1aktiv

Thread2aktiv

t

Datenverlust


Kritische Abschnitte

• zur Vermeidung von Race Conditions wendet man das Prinzip des wechselseitigen Ausschlusses an (mutual exclusion)

• dazu führt man kritische Abschnitte ein• ein kritischer Abschnitt ist eine Folge von Befehlen,die

ein Thread nacheinander vollständig abarbeiten muss• Abgabe des Prozessors an einen anderen Thread

ändert an dieser Bedingung nichts• kein anderer Thread darf einen kritischen Abschnitt

betreten,solange der erstgenannte Thread mit der Abarbeitung der Befehlsfolge noch nicht fertig ist


Monitorkonzept

• Zur Realisierung der Problemstellung der kritischen Abschnitte wurde 1974 von Hoare das Monitorkonzept als Synchronisationsmittel entwickelt

• Grundidee eines Monitors ist, dass die Daten, auf denen die kritischen Abschnitte arbeiten, und die kritischen Abschnitte selbst in einem zentralen Konstrukt zusammengefasst werden

critical section

critical section

Monitorread()

write()

Daten

P 1P 3 P 2


MonitorkonzeptDie grundlegenden Eigenschaften eines Monitors sind:

• Kritische Abschnitte,die auf denselben Daten arbeiten,sind Methoden eines Monitors

• Ein Prozess betritt einen Monitor durch Aufruf einer Methode des Monitors

• Nur ein Prozess kann zur selben Zeit den Monitor benutzen• Jeder andere Prozess,der den Monitor aufruft,wird suspendiert

und muss warten,bis der Monitor verfügbar wird• In Java wird das Monitorkonzept mit Hilfe des Schlüsselwortes

synchronized realisiert

• synchronized kann als Schlüsselwort für Methoden verwendet werden oder einen synchronisierten Codeblock


Monitorkonzept

Erstens: Monitor für den gegenseitigen Ausschluss von synchronisierten Klassenmethoden einer Klasse

Methode1()

Methode2()

Monitor

Syn1Für alle synchronisierten Klassenmethoden einer Klasse wird ein Monitor angelegt,welcherdie Klassenmethoden überwacht

So kann nur ein einziger Thread zu einerbestimmten Zeit eine der synchronisierten Methoden bearbeiten


Monitorkonzept

Zweitens: Monitor für den gegenseitigen Ausschluss der Abarbeitung von synchronisierten Instanzmethoden zu einem speziellen Objekt

Werden eine oder mehrere Instanzmethoden mit dem Schlüsselwort synchronized versehen,so hat jedes Objekt, das von dieser Klasse geschaffen wird, einen eigenen Monitor, der den Zugriff auf die Instanzmethoden überwacht

Methode1()

Methode2()

Monitor

a:Syn

Methode1()

Methode2()

Monitor

b:Syn


Monitorkonzept

Drittens: Monitor für den gegenseitigen Ausschluss von einzelnen synchronisierten Codeblöcken

Eine synchronized Anweisung wird mit dem Schlüsselwort synchronized eingeleitet.In den runden Klammern erwartet die synchronized Anweisung eine Referenz auf ein Objekt.Dieses Objekt dient als Schlüssel,auch Lock genannt.

Nur der Thread,der den Schlüssel besitzt hat Zugang zum Monitor.

Wird eine synchronized Anweisung betreten, so wird nachgeschaut, ob das Schlüsselobjekt schon von einem anderen Thread benutzt wird.

Ist dies der Fall,so muss der Thread warten,bis das Schlüsselobjekt freigegeben wird.


Methode wait() und notify()

wait()• überführt einen Thread, der eine synchronisierte Anweisung abarbeitet in den Zustand“blocked“• dadurch wird der Monitor für einen anderen Thread frei

notify()• durch notify() wird ein Thread der zuvor durch den Aufruf von wait() in den Zustand „blocked“ gebracht wurde, wieder aufgeweckt

• Thread erhält Zustand „ready to run“


Lexikon

• Java virtuelle Maschine: läuft in einem Betriebssystem-Prozess ab,d.h. sollen mehrer Java-Programme in getrennten Betriebssystem-Prozessoren ablaufen,so hat jeder Prozess seine eigene virtuelle Maschine

• Thread: (engl. Faden) Ablauffaden des Programmcodes sprich Kontrollfluss

• Betriebsmittel: sind Mittel,die ein Prozess zum Laufen braucht,dies kann der Prozessor oder ein I/O–Kanal eines Programms zu einer Datei auf der Festplatte sein

• I/O-Kanäle: sind Eingabe- bzw. Ausgabeströme, sie können von der Tastatur,Platte kommen oder auf den Bildschirm,die Platte gehen

Documents

Präsentation: Christoph PlatenVertieferseminar 07.11.02 Vertieferseminar Geoinformation WS 02/03 Parallele Programmierung von Signalverarbeitung in Java