close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Betriebssysteme - Prozesse

EinbettenHerunterladen
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Betriebssysteme - Prozesse
→ alois.schuette@h-da.de
Version: WS2014(967c57d)
Alois Sch¨
utte
4. November 2014
1 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Inhaltsverzeichnis
Ein Prozess kann als die Abstraktion eines Programms, das von einem
Prozessor ausgef¨
uhrt wird, angesehen werden.
Hier wird behandelt, was Prozesse sind und wie sie in Betriebssystemen
implementiert werden, inklusive Prozesskommunikation, -synchronisation
und Scheduling.
1 Prozessmodell
2 Interprozesskommunikation
3 IPC Probleme
4 Scheduling
2 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozessmodell
1 Prozessmodell
Prozesszust¨ande
Implementierung von Prozessen
Abstraktion des Prozessmodells in Java
2 Interprozesskommunikation
3 IPC Probleme
4 Scheduling
3 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozessmodell
Um zu verstehen, wie unterschiedliche Aktivit¨aten scheinbar gleichzeitig
ablaufen, braucht man ein Modell eines sich in Ausf¨
uhrung befindenden
Programms.
Ein (sequentieller) Prozess ist ein sich in Ausf¨
uhrung befindendes
(sequentielles) Programm zusammen mit:
• dem aktuellen Wert des Programmz¨
ahler,
• den Registerinhalten,
• den Werten der Variablen und
• dem Zustand der ge¨
offneten Dateien und Netzverbindungen.
Konzeptionell besitzt jeder Prozess seinen eigenen Prozessor - in der
Praxis wird aber immer der reale Prozessor zwischen den Prozessen hinund hergeschaltet.
4 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Sichtweisen
Beim Mehrprogrammbetrieb mit 4 Programmen (A-D) ergeben sich
damit folgende Sichtweisen:
5 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozess-Hierarchie
Ein Betriebssystem mit einen solchen Prozessmodell muss in der Lage
sein, dass von einem (Initial-) Programm andere Prozesse erzeugt werden
k¨
onnen.
• In Unix dient dazu der fork-Systemaufruf.
• Beim Hochfahren“ des Betriebssystems
werden” dann alle erforderlichen Prozesse
erzeugt f¨
ur Systemdienste, wie
•
•
•
•
Scheduler,
Dateidienst,
Terminaldienst,
...
6 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozesskategorien und Ausf¨uhrungsmodi
Damit das Betriebssystem allein die Ressourcen verwalten kann, werden
die Prozesse in Kategorien unterteilt:
• Kernel-Prozesse laufen von anderen Prozessen abgeschottet; sie
sind privilegiert, direkt auf Ressourcen zuzugreifen.
• User Prozesse verwenden stets Kernel-Funktionalit¨
at, um indirekt
auf Ressourcen zuzugreifen.
Heutige Prozessoren unterscheiden prinzipiell zwei Ausf¨
uhrungsmodi f¨
ur
Instruktionen:
• privilegierten Modus (Kernel-Prozesse):
z.B. E/A-Befehle, Registerzugriff und Interruptmaskierung
• Normalmodus (User-Prozesse)
Ein Userprozess ruft u
¨ber Systemfunktionen (system calls) einen
Dienst im eigenen Adressraum auf.
Kein Prozess hat dabei direkten Zugriff auf den Speicher des Kerns.
7 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Trap-Mechanismus
Eine Kernel-Funktion wird stets u
¨ber den
Trap-Mechanismus (Kernel-Aufruf) aufgerufen:
1
2
Speichern des Funktionskodes und der
Parameter in ?speziellen Registern
Ausl¨
osen eines Software Interrupts, d.h
• Inkrementieren des Programmz¨
ahlers
• Umschalten in privilegierten Modus User
1
2
UserModus
3
Modus
3
Ausf¨
uhren der Kernelfunktion
4
Speichern des Ergebnisses in Registern
5
Umschalten in Normalmodus
6
Zur¨
uckladen der Ergebnisse aus dem Register
7
Ausf¨
uhren der n¨achsten Instruktion der
Anwendung
4
KernelModus
5
6
UserModus
7
8 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozesszust¨
ande
Prozesszust¨ande
Eine Aufgabe des Betriebssystems ist das Multiplexen des physischen
Prozessors.
Diese Aufgabe u
¨bernimmt der Scheduler zusammen mit dem
Dispatcher.
Prozesse k¨
onnen sich in verschiedenen Zust¨
ande befinden.
1
rechnend (running)
der Prozessor ist dem Prozess zugeteilt
2
bereit (ready)
der Prozess ist ausf¨
uhrbar, aber ein anderer Prozess ist gerade
rechnend
3
blockiert (waiting)
der Prozess kann nicht ausgef¨
uhrt werden, da er auf ein externes
Ereignis wartet (z.B. Benutzer hat Taste auf Tastatur gedr¨
uckt)
Diese Zust¨anden bilden eine Entscheidungsgrundlage f¨
ur die Auswahl
eines geeigneten Kandidaten bei einem Prozesswechsel.
9 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozesszust¨
ande
Zustands¨uberg¨ange
1
2
Prozess wartet auf externes
Ereignis
Scheduler w¨ahlt anderen
Prozess aus, da die Zeitscheibe
des Prozesses abgelaufen ist
3
Scheduler w¨ahlt diesen Prozess
aus
4
externes Ereignis ist eingetreten
5
ein neuer Prozess wird erzeugt
6
der Prozess terminiert
6
5
rechnend
2
1
3
bereit
blockiert
4
Die Zustands¨
uberg¨ange werden vom Dispatcher durchgef¨
uhrt, die
Auswahl eines rechenbereiten Prozesses u
¨bernimmt der Scheduler.
10 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Prozesszust¨
ande
Modell f¨ur Prozesssystem
Damit ergibt sich ein Modell f¨
ur ein Prozesssystem, bei dem
• die unterste Schicht die Unterbrechungen behandelt und das
Scheduling der Prozesse inklusive Erzeugung und Abbrechen von
Prozessen erledigt;
• alle anderen Prozesse befinden sich auf gleicher Ebene dar¨
uber und
haben einen sequentiellen Kontrollfluss.
• Somit gibt es stets einen Wechsel von Aktivit¨
aten eines
(User-)Prozesses und des Kerns.
Prozesse
1
Kernel-Modus
2
3
...
n
User-Modus
Dispatcher / Scheduler
11 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Implementierung von Prozessen
Das o.g. Prozessmodell kann in einem Betriebssystem durch eine
Prozesstabelle, die f¨
ur jeden Prozess einen Eintrag enth¨alt, realisiert
werden.
Ein Eintrag muss alle Informationen enthalten, um einen Prozess wieder
anlaufen zu lassen, wenn er suspendiert wurde:
• Zustand,
• Programmz¨
ahler,
• Stack-Zeiger,
• belegten Speicher,
• Zustand der ge¨
offneten Dateien und
• Verwaltungsinformationen (bisher belegte CPU Zeit,
Schedulinginformationen, etc.)
Welche Information muss auf Ebene des HAL bei Wechsel des
HAL-Programms/Prozesses gespeichert werden? Also was muss
passieren, wenn ein HAL-Prozessor einen Prozesswechsel durchf¨
uhrt?
12 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Prozesstabelle
Je nach Betriebssystem variieren diese Felder der Prozesstabelle.
$ ps -o " % p
PID
PGID
3427 3427
3496 3496
$
%r %c %a
COMMAND
bash
ps
%x %t"
COMMAND
TIME
- bash
00:00:00
ps -o % p % r % c % 00:00:00
Ein Prozesswechsel kann durch ein externes Ereignis ausgel¨ost werden.
Dazu wird jeder Klasse von E/A-Ger¨aten (Festplatten, Terminals, etc.)
ein Unterbrechungsvektor zugeordnet, der die Adresse einer
Unterbrechungsbehandlungsprozedur (Interrupt Routine) enth¨alt.
Wenn z.B. ein Terminal eine Unterbrechung ausl¨
ost, dann wird
hardwareseitig (Microcode) folgendes getan:
1 Programmz¨
ahler des aktuell laufender Prozess und einiger Register
auf Stack legen
2 Aufruf der entsprechenden Unterbrechungsbehandlungsprozedur
Alle anderen Aktivit¨aten (Auswahl des n¨achsten Prozesses, der nach der
Unterbrechungsroutine laufen soll) muss durch die Betriebssystemsoftware erfolgen.
13 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
D¨amonen
In Unix werden Verwaltungsaufgaben von speziellen Programmen, die als
Hintergrundprozesse ablaufen, u
¨bernommen.
Beispiele sind:
cron Systemcronometer
at Ausf¨
uhren eines Kommandos zu einer vorgegebenen Zeit
inetd Internet Service D¨amon
sshd Secure Shell D¨amon
Solche Prozesse werden oft beim Hochfahren des Betriebssystems
gestartet und erst beim Shutdown des Systems beendet.
Auf Shellebene kann man sich D¨amonen ansehen durch das
ps-Kommando. Sie sind daran zu erkennen, dass die Spalte TTY“ ein
”
Fragezeichen ?“ enth¨alt.
”
$ ps - el | grep \?
1277 ?
00:02:22 crond
1291 ?
00:00:00 atd
1578 ?
00:00:03 sshd
30045 ?
00:03:41 sendmail
14 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Diese Prozesse sind als D¨
amonen realisiert:
• Jeder Prozess (außer init) in Unix hat einen Vater und geh¨
ort zu
einer Prozessgruppe.
• Jede Prozessgruppe hat einen Prozess als Prozessgruppenleiter
und besitzt maximal ein Kontrollterminal. Das Kontrollterminal
liefert f¨
ur alle Mitglieder der Prozessgruppe die Standardeinstellungen von stdin, stdout und stderr. Das Kontrollterminal
l¨asst sich immer unter dem Namen /dev/tty“ ansprechen.
”
• Ein Signal des Kontrollterminals wird an alle Mitglieder der
Prozessgruppe gesendet (die Shell sch¨
utzt sich und alle von ihr
initiierten Prozesse allerdings davor).
• Prozesse, die zwar Mitglieder einer Prozessgruppe sind, aber kein
Kontrollterminal haben, nennt man D¨amonen.
• Da sie kein Kontrollterminal besitzen, sind sie nicht u
¨ber
Signale abzubrechen.
• Diese D¨
amonen treiben ihr Unwesen im Bauch der Maschine“.
”
15 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Zur Implementierung von D¨amonen sollen folgende Regeln eingehalten
werden:
• Zun¨
achst sollte ein fork ausgef¨
uhrt werden, der Elternprozess sollte
danach ein exit ausf¨
uhren. Dadurch wird folgendes erreicht:
1
2
Wird der Prozess von der Shell gestartet, so denkt die Shell, der
Prozess w¨
are terminiert, da der Vater beendet ist.
Das Kind erbt vom Vater die Prozessgruppe, bekommt aber (durch
fork) eine neue PID. Dadurch ist ausgeschlossen, dass der Prozess
ein Prozessgruppenf¨
uhrer ist.
• Der n¨
achste Schritt ist, den Systemaufruf setsid()“ auszuf¨
uhren.
”
Dadurch wird eine neue Session erzeugt und der Aufrufer wird
Prozessgruppenf¨
uhrer.
• Nun wird in das aktuelle Verzeichnis gesetzt. Es sollte das
Root-Verzeichnis sein, damit nicht ein eventuelle gemountetes
Dateisystem (wenn das das Home-Verzeichnis des Aufrufers war)
dazu f¨
uhrt, dass das Betriebssystem nicht heruntergefahren werden
kann.
• Die Maske zum Dateierzeugen (umask) wird auf 0 gesetzt, damit
nicht geerbte Maske vom Aufrufer dazu f¨
uhrt, dass der D¨amon
Dateien nicht anlegen kann.
• Letztlich sollten alle nicht ben¨
otigten Filedeskriptoren geschlossen
16 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Beispiel D¨amon
daemon.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# include < sys / types .h >
# include < sys / stat .h >
# include < fcntl .h >
int daemon_init ( void ) {
pid_t pid ;
if (( pid = fork ()) < 0)
return ( -1);
else if ( pid != 0)
exit (0);
/* parent goes bye - bye */
/* child */
setsid ();
/* become session leader */
chdir ( " / " );
/* change working directory */
umask (0);
/* clear our file mode creatio mask */
return (0);
}
int main () { /* ... * some initial tasks */
daemon_init (); /* make a daemon out of the program */
sleep (100);
/* daemon code , we see the
daemon with ps -x */
exit (0);
}
17 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
D¨amonen
$ ./ daemon
$ ps - xl
F
UID
PID PPID PRI
0
500 22873 22871 20
1
500 23030
1 20
0
500 23031 22873 20
$
WCHAN STAT TTY
wait
Ss
pts /0
hrtime Ss
?
R+
pts /0
TIME
0:00
0:00
0:00
COMMAND
- bash
./ daemon
ps - xl
←
Nach de Start des D¨amon kann man mit ps –xl“ sehen, dass der D¨amon
”
aktiv ist und als Vater und den Prozess 1 besitzt.
Ein Problem bei D¨amonen ist, dass es nicht m¨
oglich ist, stderr und
stdout zu verwenden. Also muss man eine Methode entwickeln, wie ein
D¨amon die Aktivit¨aten protokollieren kann. In Unix existiert das syslog
Werkzeug, um Nachrichten geordnet zu verarbeiten.
18 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Zombies
Ein Prozess terminiert und h¨
ort auf zu existieren, wenn zwei Ereignisse
eingetreten sind:
1 Der Prozess hat sich selbst beendet oder wurde durch ein Signal
beendet und
2 der Vaterprozess hat wait()“ aufgerufen.
”
Ein Prozess, der beendet wird, bevor der Vater einen wait-Aufruf f¨
ur ihn
ausgef¨
uhrt hat, erh¨alt einen besonderen Zustand, er wird ein Zombie:
• Der Prozess wird vom Scheduler nicht mehr ber¨
ucksichtigt, er wird
aber nicht aus der Prozesstabelle entfernt.
• Wenn der Vater dann einen wait-Aufruf veranlasst, wird der Prozess
aus der Prozesstabelle entfernt und der belegte (Haupt-) Speicher
wird frei gegeben.
ps -l:
0 laufend
S schlafend (sleeping)
R auf den Prozessor wartend (runable) ...
Z Zombie
19 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Beispiel Zombie
zombie.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Create zombie to illustrate " ps - el */
# include < stdio .h >
int main () {
int pid ;
if (( pid = fork ()) == -1)
fprintf ( stderr , " fork failed !\ n " );
if ( pid == 0) { /* Child */
printf ( " child : % d \ n " , getpid ());
exit (1); /* because father will not wait , a zombie is born */
} else { /* fahter */
printf ( " father : % d \ n " , getpid ());
sleep (30);
/* now you can use ps - el to see during 30 secs that
child is a zombie */
exit (0);
}
}
20 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Beispiel Zombie
$ ./ zombie &
[1] 23036
$ father : 23036
child : 23037
ps -l
F S
PID PPID
0 S
22873 22871
0 S
23036 22873
1 Z
23037 23036
0 R
23038 22873
$
WCHAN
wait
hrtime
exit
-
TTY
pts /0
pts /0
pts /0
pts /0
TIME
00:00:00
00:00:00
00:00:00
00:00:00
CMD
bash
zombie
zombie < defunct >
ps
←
←
21 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Zombies entfernen per SIGCHLD
Wenn ein Vater nicht auf die Beendigung seiner Kinder warten kann (z.B.
bei der Shell mit Hintergrundprozessen), kann man die Zombies
eliminieren, indem
• der Vater auf das Signal SIGCHLD reagiert
• die Signalbehandlungsroutine dann mittels waitpid den Zobmiestatus
des Kindes aufhebt.
zombie cleanup.c
/* Simplest dead child cleanup in a SIGCHLD handler .
* Prevent zombie processes but don 't actually do anything
* with the information that a child died .
*/
# include < sys / types .h >
...
/* SIGCHLD handler . */
static void sigchld_hdl ( int sig ) {
/* Wait for all dead processes .
* We use a non - blocking call to be sure this signal handler
* will not block if a child was cleaned up in another
* part of the program .
*/
while ( waitpid ( -1 , NULL , WNOHANG ) > 0) ;
←
}
22 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Implementierung von Prozessen
Zombies entfernen per SIGCHLD
int main ( int argc , char * argv []) {
int i ;
if ( signal ( SIGCHLD , sigchld_hdl )) {
perror ( " signal " );
return 1;
}
←
/* Make some children . */
for ( i = 0; i < 5; i ++) {
switch ( fork ()) {
case -1:
perror ( " fork " );
return 1;
case 0: // do something
return 0;
}
}
while (1) {
// father performs something
}
return 0;
}
23 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Abstraktion des Prozessmodells in Java
Um Eigenschaften und Probleme mit Prozessen zeigen zu k¨onnen, werden
Algorithmen in der Vorlesung in Java (oder C) beschrieben.
Betrachtet werden Java-Threads als Abstraktion von Prozessen eines
Rechners:
Java Prozess
Threads
Rechner
Prozesse
gemeinsamer
Speicher
Speicher
Deshalb wird hier zun¨achst gezeigt, wie in Java Threads erzeugt werden
k¨onnen.
24 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Erzeugen und Starten vonJava-Threads
Beim Start eines Java Programms wird ein Prozess erzeugt, der einen
Thread enth¨alt, der die Methode main der angegebenen Klasse ausf¨
uhrt.
Der Code weiterer Threads muss in einer Methode mit Namen run
realisiert werden.
public void run () {
// Code wird in eigenem Thread ausgef¨
u hrt
}
Ein Programm, das Threads erzeugt, erbt von der Klasse Thread und
u
¨berschreibt die Methode run() (auf Interfaces wird sp¨ater eingegangen):
25 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Hello World
MyThread.java
1
2
3
4
public class MyThread extends Thread {
public void run () {
System . out . println ( " Hello World " );
}
public static void main ( String [] args ) {
MyThread t = new MyThread ();
t . start ();
}
6
7
8
9
10
←
←
←
}
Die Methode start() ist in der Klasse thread definiert und startet den
Thread, genauer die Methode run(). Somit wird zun¨achst ein Thread
erzeugt (new ...), dann durch start die Methode run aufgerufen und
somit Hello World“ ausgegeben.
”
26 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
mehrere Threads
Werden mehrere Thread erzeugt, so ist die Ausf¨
uhrungsreihenfolge nicht
vorhersehbar!
Loop1.java
1
2
3
4
5
public class Loop1 extends Thread {
private String myName ;
public Loop1 ( String name ) {
myName = name ;
}
public void run () {
for ( int i = 1; i <= 10000; i ++) {
System . out . println ( myName + " ( " + i + " ) " );
}
}
7
8
9
10
11
public static void main ( String [] args ) {
Loop1 t1 = new Loop1 ( " Thread 1 " );
Loop1 t2 = new Loop1 ( " Thread 2 " );
Loop1 t3 = new Loop1 ( " Thread 3 " );
t1 . start ();
t2 . start ();
t3 . start ();
}
13
14
15
16
17
18
19
20
21
}
27 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Threads in komplexen Klassenhierarchien
Wenn sich die Methode run() in einer Klasse befinden soll, die selbst
bereits aus einer anderen Klasse abgeleitet ist, so kann diese Klasse nicht
zus¨atzlich von Thread abgeleitet werden (Java unterst¨
utzt keine
Mehrfachvererbung).
In diesem Fall kann das Interface Runnable des Package java.lang
verwendet werden.
MyRunnableThread.java
1
2
3
4
5
6
7
8
9
10
public class MyRunnabl e T h r e a d implements Runnable {
public void run () {
System . out . println ( " Hello World " );
}
public static void main ( String [] args ) {
M y RunnableThread runner = new M y R u n n a b l eT h r e a d ();
Thread t = new Thread ( runner );
t . start ();
}
}
←
←
←
28 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Threadtermination
Ein Thread terminiert, wenn seine run()-Methode (bzw. die Methode
main() im Fall des Ursprungs-Thread) beendet ist.
Sind alle von einem Prozess initiierten Threads beendet, so terminiert der
Prozess (falls es kein D¨amon ist).
Die Klasse Thread stellt eine Methode isAlive bereit, mit der abfragbar
ist, ob ein Thread noch lebt (schon gestartet und noch nicht terminiert
ist).
Damit k¨onnte aktives Warten etwa wie folgt programmiert werden:
1
2
3
4
5
6
// MyThread sei aus Thread abgeleitet
MyThread t = new myThread ();
t . start ();
while ( t . isAlive ())
;
// hier ist jetzt : t . isAlive == false , der Thread t ist terminiert
Man sollte es so aber nie tun, da aktives Warten sehr rechenintensiv ist.
wieso?
29 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Warten bis Thread beendet ist
Wenn in einer Anwendung auf das Ende eines Thread gewartet werden
muss, etwa um die Rechenergebnisse des Thread weiterzuverarbeiten,
kann die Methode join der Klasse Thread benutzt werden.
Der Thread wird blockiert, bis der Thread, auf den man wartet, beendet
ist.
1
2
3
4
5
// MyThread sei aus Thread abgeleitet
MyThread t = new myThread ();
t . start ();
t . join (); // blockiert , bis t beendet ist .
// auch hier jetzt : t . isAlive == false , der Thread t ist terminiert
wieso ist das besser?
30 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Verwendung von join zum Abfragen von Ergebnissen
Das folgende Beispiel verwendet Threads, um ein grosses Feld von
Boolean zu analysieren, indem mehrere Threads parallel arbeiten, wobei
je Thread ein Bereich des Feldes bearbeitet wird.
1
0
0
T1:1
0
1
0
1
1
0
T2:3
0
0
T3:0
0
1
1
1
1
T4:4
main: 8
31 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
1
2
3
4
5
class Service implements Runnable {
private boolean [] array ;
private int start ;
private int end ;
private int result ;
public Service ( boolean [] array , int start , int end ) {
this . array = array ;
this . start = start ;
this . end = end ;
}
7
8
9
10
11
public int getResult () {
return result ;
}
13
14
15
public void run () {
for ( int i = start ; i <= end ; i ++) {
if ( array [ i ])
result ++;
}
}
17
18
19
20
21
22
23
←
←
}
32 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
1
2
3
5
6
7
9
10
11
12
13
14
15
16
18
19
20
22
23
24
public class AsynchRequest {
private static final int ARRAY_SIZE = 100000;
private static final int N U M B E R _ O F _ S E R V E R S = 100;
←
←
public static void main ( String [] args ) {
// start time
long startTime = System . c u r r e n t T i m e M i l l i s ();
// array creation , init with random boolean values
boolean [] array = new boolean [ ARRAY_SIZE ];
for ( int i = 0; i < ARRAY_SIZE ; i ++) {
if ( Math . random () < 0.1)
array [ i ] = true ;
else
array [ i ] = false ;
}
←
// creation of array for service objects and threads
Service [] service = new Service [ N U M B E R _ O F _ S E R V E R S ];
Thread [] serverThread = new Thread [ N U M B E R _ O F _ S E R V E R S ];
←
←
←
int start = 0;
int end ;
int howMany = ARRAY_SIZE / N U M B E R _ O F _ S E R V E R S ;
33 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
1
2
3
4
5
6
7
8
10
11
12
13
14
16
17
18
19
20
// creation of services and threads
for ( int i = 0; i < N U M B E R _ O F _ S E R V E R S ; i ++) {
end = start + howMany - 1;
service [ i ] = new Service ( array , start , end );
serverThread [ i ] = new Thread ( service [ i ]);
serverThread [ i ]. start (); // start thread i
start = end + 1;
}
←
// wait for termination of each service ( thread )
try {
for ( int i = 0; i < N U M B E R _ O F _ S E R V E R S ; i ++)
serverThread [ i ]. join ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
←
// accumulate service results
int result = 0;
for ( int i = 0; i < N U M B E R _ O F _ S E R V E R S ; i ++) {
result += service [ i ]. getResult ();
}
←
←
←
←
←
←
34 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
// end time
long endTime = System . c u r r e n t T i m e M i l l i s ();
float time = ( endTime - startTime ) / 1000.0 f ;
System . out . println ( " computation time : " + time );
1
2
3
4
// print result
System . out . println ( " result : " + result );
} // main
6
7
8
9
}
$ java AsynchRequest
Rechenzeit : 0.11
Ergebnis : 9953
$
35 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
¨
zum Uben
f¨ur zu Hause
1
2
Testen des Verhaltens, wenn NUMBER OF SERVERS mit 1, 10,
100, 1.000, 10.000 und 100.00 gesetzt wird und Erkl¨arung des
Ergebnisses.
¨
Andern
der Metode run() und Test und Erkl¨arung der Auswirkung
gegen¨
uber dem Verhalten von 1.
public void run () {
for ( int i = start ; i <= end ; i ++) {
if ( array [ i ])
result ++;
}
try {
Thread . sleep (100);
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
36 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Prozessmodell
Abstraktion des Prozessmodells in Java
Beenden von Threads per Programm
Die Klasse Thread besitzt die Methode stopp(), zum Abbruch von
Threads.
Die Verwendung ist aber problematisch, da ein inkonsistenter Zustand
erreicht werden kann.
• Dies ist der Fall, wenn der Thread gerade eine
synchronized()-Methode (sp¨ater) ausf¨
uhrt und den Zustand eines
Objektes ver¨andert und dies aber nicht bis zum Schluss durchf¨
uhren
kann (wegen Stopp()).
• Durch Stopp werden alle Sperren aufgehoben, der Thread konnte
aber nicht fertig werden.
Eine Abhandlung zum Stoppen von Threads kann nachgelesen werden in
threadPrimitiveDeprecation oder HowToStopThreads.
Wir werden sp¨ater nochmals darauf zur¨
uckkommen.
37 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Interprozesskommunikation
1 Prozessmodell
2 Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Kritischer Bereich
L¨
osungsans¨atze in Java
Semaphore
Monitore und andere Primitive
Nachrichtenaustausch
3 IPC Probleme
4 Scheduling
38 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Interprozesskommunikation
Betriebssysteme stellen unterschiedliche Mechanismen zur Verf¨
ugung, mit
denen zwei Prozesse kommunizieren k¨
onnen:
• beide Prozesse k¨
onnen sich den Arbeitsspeicher teilen, oder
• gemeinsamer Speicher ist nicht verf¨
ugbar, es werden externe Medien,
wie Dateien verwendet, auf die gemeinsam zugegriffen werden kann.
Die Probleme sind aber unabh¨angig davon, welcher der beiden
Mechanismen verwendet wird. Im folgenden werden die Probleme und
L¨osungen f¨
ur den Zugriff auf gemeinsam verwendete Ressourcen gezeigt.
39 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Probleme des gemeinsamen Zugriffs
Wenn mehrere Threads in Java gemeinsam auf Daten zugreifen, m¨
ussen
sich die einzelnen Threads verst¨andigen“, wer wann was machen darf.
”
Dazu werden die M¨
oglichkeiten, die Java bietet, am Beispiel von
Buchungen eines Bankkontos gezeigt.
Eine Bank wird modelliert durch 4 Klassen:
Die Klasse Konto repr¨asentiert ein Konto mit dem Attribut kontostand
und den Methoden zum setzen und abfragen des aktuellen Kontostandes.
BankOperation.java
1
2
3
4
5
6
7
8
9
class Konto {
private float kontostand ;
public void setzen ( float betrag ) {
kontostand = betrag ;
}
public float abfragen () {
return kontostand ;
}
}
40 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Bank
Die Klasse Bank hat als Attribut ein Feld von Referenzen auf
Konto-Objekte (Konten). Die Methode buchen implementiert einen
Buchungsvorgang auf ein Konto.
1
2
class Bank {
private Konto [] konten ;
public Bank () {
konten = new Konto [100];
for ( int i = 0; i < konten . length ; i ++) {
konten [ i ] = new Konto ();
}
4
5
6
7
8
public void buchen ( int kontonr , float betrag ) {
float alterStand = konten [ kontonr ]. abfragen ();
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
}
10
11
12
13
14
15
}
41 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Bankangestellte
Die Klasse Bankangestellte ist aus der Klasse Thread abgeleitet. Der
Name der Angestellten wird der Name des Thread, da mehrere
Bankangestellte (Threads) f¨
ur die Bank arbeiten k¨
onnen sollen.
Buchungen werden in der run-Methode durch Zufallszahlen erzeugt.
1
2
3
4
5
6
class BankAngestellte extends Thread {
private Bank bank ;
public BankAngestell te ( String name , Bank bank ) {
super ( name ); this . bank = bank ;
start ();
}
public void run () {
for ( int i = 0; i < 10000; i ++) {
/* Kontonummer einlesen ; simuliert durch Wahl einer
Zufallszahl zwischen 0 und 99 */
int kontonr = ( int )( Math . random ()*100);
/* ¨
U be r we is u ng s b e t r a g einlesen ; simuliert durch Wahl einer
Zufallszahl zwischen -500 und +499 */
float betrag = ( int )( Math . random ()*1000) - 500;
bank . buchen ( kontonr , betrag );
}
}
8
9
10
11
12
13
14
15
16
17
18
19
}
42 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Bankbetrieb
In der Klasse Bankbetrieb wird eine Bank mit 2 Bankangestellten
simuliert.
Die Bankangestellten fangen an zu Arbeiten, wenn die Objekte erzeugt
werden (durch new und dann die Methode start im Konstruktor von
Bankangestellte).
1
2
3
4
5
6
7
8
9
public class Bankbetrieb {
public static void main ( String [] args ) {
Bank sparkasse = new Bank ();
B ankAngestellte m¨
u ller =
new BankAngestel l te ( " Andrea M¨
u ller " , sparkasse );
B ankAngestellte schmitt =
new BankAngestel l te ( " Petra Schmitt " , sparkasse );
}
}
←
←
sparkasse ist das gemeinsam verwendete Objekt !
43 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
verlorene Buchungen
Bei dieser Bank k¨
onnen aber Buchungen verloren gehen!
→ am Rechner
Jede der 2 Bankangestellten bebucht das
• Konto 1
• jeweils 1000 mal mit
• jeweils 1 EUR
Also muss das Konto 1 am Ende des Tages einen Kontostand von 2000
EUR aufweisen !
Dieses Problem tritt immer auf, wenn mehrere Threads auf ein
gemeinsam nutzbares Objekt (hier das Feld Konto der Klasse Bank)
zugreifen und es keine Schutzmechanismen gibt.
44 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Verdeutlichung
Gehen wir von folgender Situation aus:
• Andrea M¨
uller bucht -100 EUR auf Konto 47, es sollen also 100
EUR abgebucht werden. Der Kontostand sein 0.
• Petra Schmitt f¨
uhrt auch Buchungen f¨
ur Konto 47 aus, es sollen
1000 EUR gutgeschrieben werden.
Thread Andrea M¨
uller:
1
public void buchen ( int kontonr =47 , float betrag = -100) { Konten[47]=0
2
float alterStand = konten [ kontonr ]. abfragen ();
-> Umschalten auf Thread Petra Schmitt
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
}
3
4
5
6
alterStand=0
Thread Petra Schmitt:
1
2
3
4
5
6
public void buchen ( int kontonr =47 , float betrag =1000) { Konten[47]=0
float alterStand = konten [ kontonr ]. abfragen ();
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
}
-> Umschalten auf Thread Andrea M¨
uller
alterStand=0
neuerStand=1000
Konten[47]=1000
45 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Verdeutlichung
Thread Andrea M¨
uller:
1
2
3
public void buchen ( int kontonr =47 , float betrag = -100) { Konten[47]=0
float alterStand = konten [ kontonr ]. abfragen ();
-> Weiter nach Unterbrechung
alterStand=0
4
float neuerStand = alterStand + betrag ;
neuerStand=-100
5
konten [ kontonr ]. setzen ( neuerStand );
Konten[47]=-100
6
}
Nun ist die Gutschrift, die Petra Schmitt gebucht hat verloren! Der
aktuelle Kontostand ist -100 anstatt +900.
Die Ursache des Problems ist, dass eine Buchung aus mehreren
Java Anweisungen besteht und zwischen diesen Anweisungen
zwischen Threads umgeschaltet werden kann.
46 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
Kritischer Bereich
Das gezeigte Problem der verlorenen Buchungen kann auch abstrakt
formuliert werden.
Der Teil eines Programms, in dem auf gemeinsame Ressourcen
zugegriffen wird, wird kritischer Bereich genannt.
Zeitkritische Abl¨aufe (wie das Buchen des selben Kontos)
k¨onnen vermieden werden, wenn sich zu keinem Zeitpunkt zwei
Prozesse in ihrem kritischen Bereich befinden.
Im folgenden werden L¨osungsversuche (nicht korrekte) diskutiert.
47 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
L¨osungsversuch 1 (nur eine Anweisung)
In der Klasse Bank wird das Buchen durch eine Java Anweisung realisiert:
1
2
3
4
class Konto {
private float kontostand ;
public void buchen ( float betrag ) {
kontostand += betrag ;
}
5
6
}
8
class Bank {
private Konto [] konten ;
9
also kein Umschalten m¨
oglich
public Bank () {
konten = new Konto [100];
for ( int i = 0; i < konten . length ; i ++) {
konten [ i ] = new Konto ();
}
11
12
13
14
15
public void buchen ( int kontonr , float betrag ) {
konten [ kontonr ]. buchen ( betrag ); ←
}
17
18
19
20
← nur eine Anweisung
}
Wie beurteilen Sie den Ansatz ?
48 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
L¨osungsversuch 1
Dies ist keine L¨
osung, denn Java-Programme werden in Bytekode
u
¨bersetzt.
Dabei wird aus der einer Java-Anweisung
1
kontostand += betrag ;
schematisch etwa folgender Code:
1
2
3
LOAD ( kontostand );
ADD ( betrag );
STORE ( kontostand );
Die JVM f¨
uhrt also 3 Anweisungen aus, wobei dann auch wieder
dazwischen umgeschaltet werden kann.
49 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
L¨osungsversuch 2 (Sperrvariable)
Die Idee ist die Verwendung von Sperrvariablen:
• Zu einem Zeitpunkt darf nur eine Angestellte eine Buchung
ausf¨
uhren.
• Erst wenn die Buchung abgeschlossen ist, darf eine andere
Angestellte buchen.
Dies ist offensichtlich eine korrekte L¨
osung: der kritische Bereich wird zu
einem Zeitpunkt nur einmal betreten.
Ein Implementierungsversuch ist: Alle Klassen entsprechen den des
Ausgangsbeispiels; nur die Klasse Bank wird wie folgt ge¨andert.
50 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
1
2
3
class Bank {
private Konto [] konten ;
private boolean gesperrt ;
public Bank () {
konten = new Konto [100];
for ( int i = 0; i < konten . length ; i ++) {
konten [ i ] = new Konto ();
}
gesperrt = false ;
}
5
6
7
8
9
10
11
←
public void buchen ( int kontonr , float betrag ) {
while ( gesperrt );
←
gesperrt = true ;
←
float alterStand = konten [ kontonr ]. abfragen ();
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
gesperrt = false ;
←
}
13
14
15
16
17
18
19
20
21
←
}
Die 3 Anweisungen zum Buchen k¨
onnen nur ausgef¨
uhrt werden, falls die
Bank momentan nicht gesperrt ist. Ist die Bank gesperrt, wartet der
Thread, bis sie durch den sperrenden Thread wieder entsperrt wird.
51 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Kritischer Bereich
Diese Realisierung ist auf den ersten Blick korrekt; es gibt aber folgende
Probleme:
1
Paralleles Arbeiten wird unm¨
oglich: parallel k¨
onnten
unterschiedlichen Konten bebucht werden – dies ist hier
ausgeschlossen.
2
Durch das aktive Warten (while (gesperrt) ;) wird kostbare
Rechenzeit aufgewendet, um nichts zu tun.
3
Die Realisierung ist nicht korrekt. Das aktive Warten ist keine
unteilbare Aktion, denn der Bytekode sieht etwa wie folgt aus:
while ( gesperrt );
1: LOAD ( gesperrt );
2: JUMPTRUE 1;
gesperrt = true ;
3: LOADNUM ( TRUE );
4: STORE ( geperrt )
Wenn hierbei zwischen Befehl 1 und 2 umgeschaltet wird und die
Sperre frei ist (geperrt=false) so kann ein wartender Thread buchen.
Um eine korrekte L¨
osung in Java zu programmieren, sind in Java
Sprachelemente zur Synchronisation verf¨
ugbar.
52 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
L¨osungsans¨atze in Java
Die erste korrekte (aber ineffiziente) L¨
osung f¨
ur die Probleme 2 (aktives
Warten) und 3 (verlorene Buchungen) nutzt die M¨
oglichkeit von Java,
Methoden als synchronized zu kennzeichnen.
Dazu wird einfach die Klasse buchen mit dem Attribut synchronized
versehen – ansonsten ¨andert sich nichts.
1
2
class Bank {
private Konto [] konten ;
public Bank () {
konten = new Konto [100];
for ( int i = 0; i < konten . length ; i ++) {
konten [ i ] = new Konto ();
}
4
5
6
7
8
public synchronized void buchen ( int kontonr , float betrag ) {
float alterStand = konten [ kontonr ]. abfragen ();
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
}
10
11
12
13
14
15
}
53 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
synchronized
Die Java-Superklasse Object beinhaltet als Eigenschaft eine Sperre. Da
jede Klasse von Object abgeleitet ist, besitzen alle Klassen diese
Eigenschaft.
Das Sperren gehorcht dem acquire-release Protokoll“:
”
Die Sperre wird gesetzt (acquire), beim Betreten einer
synchronized-Methode (oder synchronized Blocks) und entfernt
(release) bei Verlassen des Blocks (auch bei Verlassen durch
einee Exception).
54 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
acquire release Protokoll
• Wird eine Methode einer Klasse mit
synchronized gekennzeichnet, so muss diese
Sperre zuerst gesetzt werden, bevor die
Methode ausgef¨
uhrt wird, hier versucht von
Thread B.
• Hat ein anderer Thread A die Sperre bereits
gesetzt (seine Methode ist in Ausf¨
uhrung), so
wird der aufrufende Thread B blockiert.
Thread B
Tread A
• Das Blockieren ist aber nicht durch aktives
Warten realisiert, sondern der Thread B wird
beim Thread-Umschalten nicht mehr
ber¨
ucksichtigt.
Sperre
Object
• Wenn die Methode des Thread A beendet ist,
wird die Sperre entfernt und der Thread B
wird wieder beim Scheduling wieder
ber¨
ucksichtigt.
55 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Somit ist das Problem 2 und 3 gel¨
ost. Diese L¨
osung ist aber ineffizient
(Problem 1), da die ganze Bank gesperrt wird, obwohl doch nur
Probleme auftauchen, wenn auf das selbe Konto gebucht wird.
Dies wird im Beispielprogramm umgesetzt,indem die Java-Eigenschaft,
Bl¨ocke als synchronized zu kennzeichnen, verwendet wird.
1
2
class Bank {
...
public void buchen ( int kontonr , float betrag ) {
synchronized(konten[kontonr]) {
float alterStand = konten [ kontonr ]. abfragen ();
float neuerStand = alterStand + betrag ;
konten [ kontonr ]. setzen ( neuerStand );
}
}
4
5
6
7
8
9
10
11
}
Ein Block (...) wird dabei mit dem Schl¨
usselwort synchronized versehen
und das Objekt, auf das sich die Sperre bezieht wird danach angegeben.
56 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Verwendung von synchronized
Wenn alle Threads nur lesend auf ein Objekt zugreifen, ist keine
Synchronisation erforderlich – hier w¨
urde durch synchronized ein
unn¨
otiger Rechenaufwand erzeugt werden (Setzen und L¨osen der Sperre).
Generell gilt folgende Regel:
Wenn von mehreren Threads auf ein Objekt zugegriffen
wird, wobei mindestens ein Thread den Zustand
(repr¨asentiert durch die Werte der Attribute) des Objekts
andert, dann m¨
ussen alle Methoden, die auf den Zustand
¨
lesend oder schreibend zugreifen, mit synchronized
gekennzeichnet werden.
57 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Petrinetz f¨ur synchronized
Betrachten wir folgendes Beispiel, ein Programm, bei dem alle Threads
auf demselben Objekt arbeiten:
1
2
3
4
5
6
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class K {
public synchronized void
public synchronized void
private void action1 () {
private void action2 () {
}
m1 () { action1 (); }
m2 () { action2 (); }
... }
... }
class T extends Thread {
private K einK ;
public T ( K k ) {
einK = k ;
}
public void run () {
while (...) {
switch (...) {
case ...: einK . m1 (); break ;
case ...: einK . m2 (); break ;
}
}
}
}
→ petrinet
58 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Petrinetz f¨ur synchronized
• Die Stellen des Petri-Netzes entsprechen den
Stellen zwischen den Anweisungen im
Programmtext.
• Die Transitionen sind die Anweisungen und die
Marken sind die Threads bzw. die Sperre des
gemeinsam benutzten K-Objektes, die durch
synchronized belegt wird.
• Zum Start eines Thread muss sowohl eine
Marke auf start“ als auch auf lock“ liegen.
”
”
• Schaltet eine Transition, so wird die Marke
von lock“ entfernt und erst wieder auf sie
”
gelegt, wenn die synchronized Methode
syncEnd“ erreicht hat.
”
• Damit kann zu einem Zeitpunkt h¨
ochstens ein
Thread eine der synchronized Methoden auf
ein Objekt anwenden.
59 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Test, ob eine Sperre gesetzt ist
Der Test, ob eine Sperre gesetzt ist, ist durch holdsLock m¨oglich:
Main.java
1
2
3
public class Main {
public static void main ( String [] argv ) throws Exception {
Object o = new Object ();
System . out . println ( Thread . holdsLock ( o ));
synchronized ( o ) {
System . out . println ( Thread . holdsLock ( o ));
}
5
6
7
8
←
}
9
10
←
}
60 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
H¨orsaal¨ubung
Welche Ausgabe erzeugt das Programm?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Test.java
class Even {
private int n = 0;
public int next () { // POST : next is always even ←
++ n ;
try { Thread . sleep (( long )( Math . random ()*10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) { }
++ n ;
return n ;
}
}
public class Test extends Thread {
private Even e ;
public Test ( Even e ) { this . e = e ;}
public void run () {
for ( int i = 1 ; i <= 1000; i ++) {
System . out . println ( getName ()+ " : " + e . next ());
}
}
public static void main ( String [] args ) {
Even e = new Even ();
Test t1 = new Test ( e ); t1 . start ();
}
}
61 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
→ H¨orsaal¨ubung
Welche Ausgabe erzeugt das Programm?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Test1.java
class Even {
...
}
public class Test1 extends Thread {
private Even e ;
public Test1 ( Even e ) {
this . e = e ;
}
public void run () {
for ( int i = 1 ; i <= 1000; i ++) {
System . out . println ( getName ()+ " : " + e . next ());
}
}
public static void main ( String [] args ) {
Even e = new Even ();
Test1 t1 = new Test1 ( e );
Test1 t2 = new Test1 ( e );
t1 . start ();
t2 . start ();
}
}
Wie ist das Programm Test1.java abzu¨andern, so dass die Ausgabe der
Intuition der Verwendung der Klasse Even entspricht?
62 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait und notify
Werden Objekte von mehreren Threads benutzt und dabei deren
Zust¨ande ver¨andert, dann gew¨ahrleisten synchronized-Methoden, dass ein
Thread immer einen konsistenten Zustand eines Objektes vorfindet.
In vielen Anwendungssituationen ist es erforderlich, dass eine Methode
nur dann ausgef¨
uhrt wird,
• wenn zus¨
atzlich zum konsistenten Zustand
• weitere anwendungsspezifische Bedingungen erf¨
ullt sind.
63 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Beispiel Parkhaus
Ein Parkhaus wird modelliert, indem der Zustand durch die aktuell noch
freie Parkpl¨atze beschrieben wird und Autos durch Threads mit
Methoden Einfahren (enter()) und Ausfahren (leave()) realisiert sind.
• Beim Einfahren vermindert sich die Anzahl der freien Pl¨
atze um 1;
beim Ausfahren eines Autos wird sie um 1 erh¨
oht.
• Die freien Pl¨
atze k¨
onnen nicht erh¨
oht werden, wenn das Parkhaus
voll ist (freie Pl¨atze == 0).
• Da ein Parkhaus von mehreren Autos (Threads) benutzt wird und
der Zustand (=freie Pl¨atze) durch ein Auto ver¨andert wird, m¨
ussen
die Methoden enter() und leave() synchronized sein.
Zun¨achst werden zwei vergebliche Versuche, das Problem freie Pl¨atze“
”
zu l¨
osen gezeigt, dann eine korrekte Implementierung.
64 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
unkorrekter Versuch
ParkingGarageOperation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
class ParkingGarage {
private int places ;
public ParkingGarage ( int
if ( places < 0) places
}
public synchronized void
while ( places == 0) ;
places - -;
}
public synchronized void
places ++;
}
}
places ) {
= 0; this . places = places ;
enter () { // enter parking garage
← actives Warten
leave () { // leave parking garage
Diese L¨
osung hat zwei Probleme:
1 Aktives Warten f¨
uhrt zu schlechter Performance.
65 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
unkorrekter Versuch
ParkingGarageOperation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
class ParkingGarage {
private int places ;
public ParkingGarage ( int
if ( places < 0) places
}
public synchronized void
while ( places == 0) ;
places - -;
}
public synchronized void
places ++;
}
}
places ) {
= 0; this . places = places ;
enter () { // enter parking garage
← actives Warten
leave () { // leave parking garage
Diese L¨
osung hat zwei Probleme:
1 Aktives Warten f¨
uhrt zu schlechter Performance.
2 Die L¨
osung arbeitet nicht korrekt, wenn ein Parkhaus einmal voll
geworden ist. Wenn ein Auto in ein volles Parkhaus einfahren will (Aufruf
Methode enter), dann kann das Parkhaus nicht mehr benutzt werden, weil
der Thread wegen synchronized und der while-Schleife die Sperre nie mehr
freigibt, da kein anderes Auto ausfahren kann (wegen der Sperre).
65 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
unkorrekter Versuch
ParkingGarageOperation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
class ParkingGarage {
private int places ;
public ParkingGarage ( int
if ( places < 0) places
}
public synchronized void
while ( places == 0) ;
places - -;
}
public synchronized void
places ++;
}
}
places ) {
= 0; this . places = places ;
enter () { // enter parking garage
← actives Warten
leave () { // leave parking garage
Diese L¨
osung hat zwei Probleme:
1 Aktives Warten f¨
uhrt zu schlechter Performance.
2 Die L¨
osung arbeitet nicht korrekt, wenn ein Parkhaus einmal voll
geworden ist. Wenn ein Auto in ein volles Parkhaus einfahren will (Aufruf
Methode enter), dann kann das Parkhaus nicht mehr benutzt werden, weil
der Thread wegen synchronized und der while-Schleife die Sperre nie mehr
freigibt, da kein anderes Auto ausfahren kann (wegen der Sperre).
65 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Korrekte L¨osung ohne aktives Warten
Das aktive Warten auf einen freien Platz ist weder im gesperrten Zustand
des Parkhaus-Objektes noch im nicht gesperrten Zustand korrekt.
Durch die Methoden wait() und notify() der Klasse Objekt kann das
Problem gel¨
ost werden.
public class Object {
...
public final void wait () throws I n t e r r u p t e d E x c e p t i o n {...}
public final void notify () { ...}
}
Diese beiden Methoden m¨
ussen auf ein Objekt angewendet werden, das
durch synchronized gesperrt ist, ansonsten tritt die Ausnahme
IllegalMonitorStateException“ auf.
”
66 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
Ein wait bewirkt die folgenden Aktionen:
1
Der laufende Thread blockiert.
2
Wenn der laufende Thread unterbrochen wurde, wird die Ausnahme
InterruptedException erzeugt.
3
Die JVM f¨
ugt den laufenden Thread in eine Menge (wait set) ein,
die mit dem Objekt assoziiert ist.
4
Der synchronization Lock f¨
ur das Objekt wird freigegeben (released),
alle anderen Locks bleiben erhalten.
67 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
Ein notify bewirkt die folgenden Aktionen:
1
Ein zuf¨alliger Thread t wird aus dem Waitingset des Objektes
ausgew¨ahlt.
2
t muss den Lock des Objektes wieder erhalten, d.h. Er blockiert
solange, bis der Thread der notify aufgerufen hat, den Lock besitzt
oder bis ein anderer Thread, der den Lock h¨alt, ihn freigegeben hat.
3
t wird nach erhalten des Lock nach seinem wait weitermachen.
Ein notifyAll arbeitet genauso, nur dass alle Threads im Waitingset
ausgew¨
ahlt werden (Achtung: nur einer kann aber weitermachen, da die
anderen ja auf den Erhalt des Lock warten. sind.
68 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
69 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
70 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
71 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
72 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait, notify, notifyAll
73 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Parkhaus mit korrekter L¨osung
ParkingGarageOperation.java
1
2
class ParkingGarage {
private int places ;
public ParkingGarage ( int places ) {
if ( places < 0)
places = 0;
this . places = places ;
}
4
5
6
7
8
public synchronized void enter () { // enter parking garage
while ( places == 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 ) {}
}
places - -;
}
10
11
12
13
14
15
16
17
public synchronized void leave () { // leave parking garage
places ++;
notify ();
←
}
19
20
21
22
23
}
74 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Parkhaus mit korrekter L¨osung
1
2
class Car extends Thread {
private ParkingGarage parkingGarage ;
public Car ( String name , ParkingGarage p ) {
super ( name );
this . parkingGarage = p ;
start ();
}
4
5
6
7
8
public void run () {
while ( true ) {
try {
sleep (( int )( Math . random () * 10000)); // drive before parking
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
parkingGarage . enter ();
System . out . println ( getName ()+ " : entered " );
try {
sleep (( int )( Math . random () * 20000)); // stay into the garage
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
parkingGarage . leave ();
System . out . println ( getName ()+ " : left " );
}
}
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
}
75 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Parkhaus mit korrekter L¨osung
1
2
3
4
5
6
7
8
public class P a r k i n g G a r a g e O p e r a t i o n {
public static void main ( String [] args ){
ParkingGarage parkingGarage = new ParkingGarage (10);
for ( int i =1; i <= 40; i ++) {
Car c = new Car ( " Car " +i , parkingGarage );
}
}
}
76 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Frage
1
2
class ParkingGarage {
...
public synchronized void enter () { // enter parking garage
while ( places == 0) {
← if anstelle von while
try {
wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
places - -;
}
4
5
6
7
8
9
10
11
public synchronized void leave () { // leave parking garage
places ++;
notify ();
}
13
14
15
16
}
Was passiert, wenn man in der Methode enter(), die while-Schleife durch
ein if ersetzt?
Die L¨osung m¨
usste immer noch korrekt sein, da der Thread doch erst
geweckt wird, wenn ein Platz frei wurde und somit kann er in das
Parkhaus einfahren. Ist die Argumentation korrekt?
77 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Antwort
Nein, denn obwohl er geweckt wird, wenn ein Platz frei geworden ist,
heißt das ja nicht, dass er auch vom Scheduler ausgew¨ahlt wird. Es
k¨onnte ein anderer Thread, der gerade einfahren will ausgew¨ahlt werden,
der dann den freien Platz belegt.
Dies entspricht in der Realit¨at dem Tatbestand, dass ein Auto vor dem
Einlass steht und von einem anderen dahinter stehenden Wartenden
u
ucke einf¨ahrt.
¨berholt wird, der dann in die letzte Parkl¨
78 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Modellierung von wait- und notify durch Petri-Netze
class K {
public synchronized void m1 () {
while (...)
wait ();
←
action1 (); }
public synchronized void m2 () {
action2 ();
notify ();
←
}
private void action1 () { ... }
private void action2 () { ... }
}
class T extends Thread {
private K einK ;
public T ( K k ) {
einK = k ;
}
public void run () {
while (...)
switch (...) {
case ...: einK . m1 (); break ;
case ...: einK . m2 (); break ;
}
}
}
79 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
¨
Die Stelle checkCond1“ entspricht der Uberpr¨
ufung der Wartebedingung. Der
”
Aufruf von wait() wird durch die Transition wait1“ modelliert. Die Anzahl der
”
Marken in der Stelle waiting1“ entspricht der Anzahl der wartenden Threads.
”
Das Schalten der Transition wait1“ bewirkt, dass eine Marke auf die Stelle
”
lock“ gelegt wird, dies entspricht der Freigabe der Sperre beim Aufruf von
”
wait() – dadurch k¨
onnen weitere Threads die Methode m1“ aufrufen.
”
Irgendwann wird ein Thread die Methode m2“ aufrufen. Dann wird nach
”
Schalten der Transition action2“ eine Marke auf der Stelle afterAction2“
”
”
liegen. Nun folgt notify(): die Transition notify2“ kann auf jeden Fall schalten.
”
Falls sich mindestens eine Marke in der Stelle waiting1“ befindet, kann
”
zus¨
atzlich die Transition wakeup1“ schalten. Dadurch entsteht zwischen
”
wakeup1“ und notify2“ ein Konflikt. Durch Zuweisen einer h¨
oheren Priorit¨
at
”
”
an wakeup1“ erreicht man, dass nur die Transition wackup1“ schaltet. Die
”
”
Transition notify2“ soll n¨
amlich nur Schal- ten, wenn sich keine Marke auf
”
waiting1“ befindet (dies ist die Semantik non notify(): notify() weckt genau
”
einen Thread, wenn es einen solchen gibt; ansonsten ist notify() wirkungslos).
80 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
wait() und notifyAll()
Probleme mit wait() und notify() entstehen, wenn mehrere Threads in
der Warteschlange stehen und der falsche Thread geweckt wird.
Dies wird am Erzeuger-Verbraucher Problem demonstriert.
81 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erzeuger-Verbraucher Problem
• Ein Erzeuger (producer) will Werte an
einen Verbraucher (consumer) senden.
• Erzeuger und Verbraucher sind Threads.
• Die Werte, die ausgetauscht werden, sind
in einem Puffer (implementiert durch
Integervariable) abgelegt, auf die beide
Threads Zugriff haben.
• Der Erzeuger verwendet die Methode
put(), um einen Wert in den Puffer zu
schreiben;
• der Verbraucher kann einen Wert aus dem
Puffer durch die Methode get() lesen.
82 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erzeuger-Verbraucher Problem
• Bei der Realisierung darf es nicht
vorkommen, dass ein Wert verloren geht,
etwa weil der Erzeuger einen neuen Wert
in den Puffer schreibt, bevor der
Verbraucher den alten Wert gelesen hat.
• Weiterhin darf ein Wert nicht mehrmals
gelesen werden, etwa wenn der
Verbraucher erneut liest, bevor der
Erzeuger einen neuen Wert geschrieben
hat.
• Diese Problematik soll durch Warten
realisiert werden:
• der Erzeuger wartet mit dem Schreiben,
bis der Verbraucher den Wert gelesen
hat;
• der Verbraucher wartet, bis ein neuer
Wert in den Puffer geschrieben ist.
83 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Unkorrekte L¨osung
Der Puffer wird durch die Klasse Buffer mit
• den Attributen
• data (Werte) und
• available (Flag zeigt an, ob Daten bereit stehen) und den
• Methoden
• put() und
• get()
realisiert.
84 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
ProduceConsume.java
1
2
3
class Buffer {
private boolean available = false ;
private int data ;
public synchronized void put ( int x ) {
while ( available ) {
try {
wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
data = x ;
available = true ;
notify ();
}
5
6
7
8
9
10
11
12
13
14
public synchronized int get () {
while (! available ) {
try {
wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
available = false ;
notify ();
return data ;
}
16
17
18
19
20
21
22
23
24
25
26
←
←
←
←
}
85 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erzeuger und Verbraucher werden als Threads modelliert, wobei im
Konstruktor eine Referenz auf das gemeinsam benutzte Objekt (buffer)
u
¨bergeben wird.
Der Erzeuger produziert 100 Werte, der Verbraucher konsumiert 100
Werte.
1
2
3
class Producer extends Thread {
private Buffer buffer ;
private int start ;
public Producer ( Buffer b , int s ) {
buffer = b ;
start = s ;
}
5
6
7
8
public void run () {
for ( int i = start ; i < start +100; i ++) {
buffer . put ( i );
}
}
10
11
12
13
14
15
}
86 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
1
2
class Consumer extends Thread {
private Buffer buffer ;
public Consumer ( Buffer b ) {
buffer = b ;
}
4
5
6
public void run () {
for ( int i =0; i <100; i ++) {
int x = buffer . get ();
System . out . println ( " got " + x );
}
}
8
9
10
11
12
13
14
}
87 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
In der Klasse ProduceConsume werden ein Puffer, ein Erzeuger und ein
Verbraucher erzeugt und die beiden Threads gestartet.
1
2
3
4
5
6
7
8
9
public class ProduceConsume {
public static void main ( String [] args ) {
Buffer b = new Buffer ();
Consumer c = new Consumer ( b );
Producer p = new Producer (b , 1);
c . start ();
p . start ();
}
}
Ein Aufruf des Programms bewirkt also:
$ java ProduceConsume
got 1
got 2
got 3
got 4
got 5
...
got 100
$
88 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Normalerweise hat man die Situation, dass mehrere Erzeuger und
mehrere Verbraucher parallel arbeiten:
ProduceConsume2.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ProduceConsu m e2 {
public static void main ( String [] args ) {
Buffer b = new Buffer ();
Consumer c1 = new Consumer ( b );
Consumer c2 = new Consumer ( b );
Consumer c3 = new Consumer ( b );
Producer p1 = new Producer (b , 1);
Producer p2 = new Producer (b , 101);
Producer p3 = new Producer (b , 201);
c1 . start ();
c2 . start ();
c3 . start ();
p1 . start ();
p2 . start ();
p3 . start ();
}
}
89 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Ein Lauf des Programms kann folgende Ausgabe bewirken (das h¨angt
von Betriebssystem und Java-Version ab):
$ java ProduceConsume2
got 1
got 101
got 2
got 102
got 103
got 201
got 3
got 104
got 202
...
got 230
got 231
got 33
got 8
got 232
D.h. das Programm bleibt stehen, es passiert nichts mehr; es wird keine
neue Ausgabe mehr erzeugt, das Programm ist aber noch nicht beendet.
Dieses Verhalten wurde verursacht, da durch notify() der falsche“
”
Thread geweckt wurde.
90 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Ein Lauf des Programms kann folgende Ausgabe bewirken (das h¨angt
von Betriebssystem und Java-Version ab):
$ java ProduceConsume2
got 1
got 101
got 2
got 102
got 103
got 201
got 3
got 104
got 202
...
got 230
got 231
got 33
got 8
got 232
D.h. das Programm bleibt stehen, es passiert nichts mehr; es wird keine
neue Ausgabe mehr erzeugt, das Programm ist aber noch nicht beendet.
Dieses Verhalten wurde verursacht, da durch notify() der falsche“
”
Thread geweckt wurde.
90 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
1
Alle Verbraucher c1, c2 und c3 k¨
onnen laufen. Da der Puffer
anf¨anglich leer ist, werden alle 3 Threads durch wait() innerhalb
get() blockiert und in die Warteschlange des Objektes b
aufgenommen.
2
Nun startet der Thread p1, der eine Wert in den Puffer b ablegt und
einen Verbraucher weckt, nehmen wir an c1.
Nun hat die Warteschlange und der Puffer folgendes Aussehen:
91 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
1
Alle Verbraucher c1, c2 und c3 k¨
onnen laufen. Da der Puffer
anf¨anglich leer ist, werden alle 3 Threads durch wait() innerhalb
get() blockiert und in die Warteschlange des Objektes b
aufgenommen.
2
Nun startet der Thread p1, der eine Wert in den Puffer b ablegt und
einen Verbraucher weckt, nehmen wir an c1.
Nun hat die Warteschlange und der Puffer folgendes Aussehen:
91 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
3
p1 l¨auft weiter und will einen Wert in den Puffer schreiben. Da der
Puffer voll ist, blockiert er und wird in die Warteschlange eingereiht:
4
Nehmen wir an, es wird auf den Erzeuger p2 umgeschaltet. Da der
Puffer immer noch voll ist, wird auch p2 blockiert. Dies wiederholt
sich f¨
ur p3:
92 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
3
p1 l¨auft weiter und will einen Wert in den Puffer schreiben. Da der
Puffer voll ist, blockiert er und wird in die Warteschlange eingereiht:
4
Nehmen wir an, es wird auf den Erzeuger p2 umgeschaltet. Da der
Puffer immer noch voll ist, wird auch p2 blockiert. Dies wiederholt
sich f¨
ur p3:
92 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
5
Der einzige Thread, auf den nun noch umgeschaltet werden kann, ist
der vorher geweckte Thread c1. Der nimmt nun einen Wert aus dem
Puffer. Dann wird einer der Threads in der Warteschlange
geweckt, gehen wir von c2 aus.
6
c1 arbeitet weiter und will einen Wert aus dem Puffer nehmen; der
Puffer ist leer, also wird c1 blockiert und es steht noch immer kein
Wert im Puffer:
93 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
5
Der einzige Thread, auf den nun noch umgeschaltet werden kann, ist
der vorher geweckte Thread c1. Der nimmt nun einen Wert aus dem
Puffer. Dann wird einer der Threads in der Warteschlange
geweckt, gehen wir von c2 aus.
6
c1 arbeitet weiter und will einen Wert aus dem Puffer nehmen; der
Puffer ist leer, also wird c1 blockiert und es steht noch immer kein
Wert im Puffer:
93 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
7
Der Thread, auf den als einziges umgeschaltet werden kann, ist der
Verbraucher c2. Er versucht einen Wert zu lesen, der Puffer ist leer,
also blockiert er:
Da nun alle Thread in der Warteschlange sind, kann keiner weiter
arbeiten, das Programm steht.
Schritt 5 hat außerdem gezeigt : der Verbraucher c1 hat einen
anderen Verbraucher (c2) geweckt. Dies war der falsche“ Thread.
”
94 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
7
Der Thread, auf den als einziges umgeschaltet werden kann, ist der
Verbraucher c2. Er versucht einen Wert zu lesen, der Puffer ist leer,
also blockiert er:
Da nun alle Thread in der Warteschlange sind, kann keiner weiter
arbeiten, das Programm steht.
Schritt 5 hat außerdem gezeigt : der Verbraucher c1 hat einen
anderen Verbraucher (c2) geweckt. Dies war der falsche“ Thread.
”
Die L¨
osung des Problems kann nun darin bestehen, dass nicht ein
Thread, sondern alle Thread geweckt werden. Da nur einer ausgew¨ahlt
wird und jeder in einer while-Schleife pr¨
uft, ob er arbeiten kann, wird das
funktionieren.
94 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Erkl¨arung
7
Der Thread, auf den als einziges umgeschaltet werden kann, ist der
Verbraucher c2. Er versucht einen Wert zu lesen, der Puffer ist leer,
also blockiert er:
Da nun alle Thread in der Warteschlange sind, kann keiner weiter
arbeiten, das Programm steht.
Schritt 5 hat außerdem gezeigt : der Verbraucher c1 hat einen
anderen Verbraucher (c2) geweckt. Dies war der falsche“ Thread.
”
Die L¨
osung des Problems kann nun darin bestehen, dass nicht ein
Thread, sondern alle Thread geweckt werden. Da nur einer ausgew¨ahlt
wird und jeder in einer while-Schleife pr¨
uft, ob er arbeiten kann, wird das
funktionieren.
94 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Korrekte L¨osung durch wait-notifyAll
Die Klasse Objekt besitzt neben dem einfachen notify(), eine weitere
Methode zum Aufwecken von Threads: notifyAll() weckt alle in der
Warteschlange eines Objekts befindlichen Threads.
Die korrekte L¨
osung besteht also darin, notify() durch notifyAll() zu
ersetzen: ProduceConsume3.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Buffer { ...
public synchronized void put ( int x ) {
while ( available ) {
try { wait ();} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
data = x ;
available = true ;
notifyAll ();
←
}
public synchronized int get () {
while (! available ) {
try { wait ();} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
available = false ;
notifyAll ();
←
return data ;
}
}
95 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Regel f¨ur notifyAll
Prinzipiell kann man immer notify() durch notifyAll() ersetzen, die
Umkehrung allerdings w¨are falsch (wie im letzten Beispiel gesehen).
Die Methode notifyAll() ist zu verwenden, wenn mindestens eine der
beiden folgenden Situationen zutrifft:
1
2
In der Warteschlange befinden sich Threads, mit unterschiedlichen
Wartebedingungen (z.B. Puffer leer, Puffer voll). Dann kann bei
Verwendung von notify() der falsche“ Thread geweckt werden.
”
Durch die Ver¨anderung des Zustands eines Objekts k¨onnen mehrere
Threads weiterlaufen (Wert im Puffer - alle wartenden Verbraucher
k¨onnen arbeiten).
96 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
L¨
osungsans¨
atze in Java
Modellierung von wait- und notifyAll durch Petri-Netze
class K {
public synchronized void m1 () {
while (...)
wait ();
←
action1 (); }
public synchronized void m2 () {
action2 ();
notifyAll ();
←
}
private void action1 () { ... }
private void action2 () { ... }
}
class T extends Thread {
private K einK ;
public T ( K k ) {
einK = k ;
}
public void run () {
while (...)
switch (...) {
case ...: einK . m1 (); break ;
case ...: einK . m2 (); break ;
}
}
}
97 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Semaphore
1965 wurde von Dijkstra das Konzept der Semaphore zur Synchronisation
vorgeschlagen.
• Eine Semaphore ist eine Integervariable, deren
• Wert Null anzeigt, dass kein Prozess (Thread) mehr zu wecken ist,
• ein Wert gr¨
osser Null bedeutet, dass Wecksignale zu
ber¨
ucksichtigen sind.
• Als Operationen wurde definiert DOWN“ (=p) und UP“ (=v).
”
”
• Down“ pr¨
uft, ob der Semaphore gr¨
oßer als Null ist, dann wird der
”
Wert vermindert; ist der Wert Null, wird der Thread schlafen gelegt
und die DOWN-Operation ist beendet.
• UP“ inkrementiert den Semaphore.
”
Sowohl UP“ als auch DOWN“ sind dabei atomare Operationen,
”
”
d.h. es ist sichergestellt, dass w¨ahrend der Ausf¨
uhrung der
Operration kein anderer Thread auf den Semaphore zugreifen kann.
98 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Semaphore Implementierung in Java
Semaphore.java
public class Semaphore {
private int value ;
public Semaphore ( int init ) {
if ( init < 0)
init = 0;
value = init ;
}
←
public synchronized void p () { ← Dijkstra’s
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 - -;
}
public synchronized void v () {
value ++;
notify ();
}
operation p=down
← Dijkstra’s operation v=up
←
}
99 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Gegenseitiger Ausschluss mit Semaphoren
Gegenseitiger Ausschluss bezeichnet eine Situation, in der ein bestimmtes
Programmst¨
uck zu einer Zeit von h¨
ochstens einem Thread
ausgef¨
uhrt werden darf.
• In Java kann dazu eine synchronized Methode verwendet werden:
auf ein Objekt kann dadurch zu einem Zeitpunkt nur von einem
Thread zugegriffen werden.
• Hier soll nun nicht mit synchronized gearbeitet werden, sondern es
wird eine Klasse mit einer Semaphore verwendet.
Als kritischen Abschnitt bezeichnet man das Programmst¨
uck, das von
h¨
ochstens einem Thread betreten werden darf.
100 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Gegenseitiger Ausschluss mit Semaphoren
Im folgenden Beispiel werden die Aktionen, die ein Thread im kritischen
Abschnitt ausf¨
uhrt simuliert durch eine Sleep-Operation. In einer realen
Anwendung w¨
urde hier das Codefragment stehen, das auf die
gemeinsamen Objekte zugreift.
Der kritische Abschnitt wird durch Semaphore gesch¨
utzt, indem
1
vor Betreten die Semaphor-Methode down(),
2
danach die Methode up()
aufgerufen wird.
101 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
MutualExclusion.java
1
2
class MutexThread extends Thread {
private Semaphore mutex ;
public MutexThread ( Semaphore mutex , String name ) {
super ( name );
this . mutex = mutex ;
start ();
}
4
5
6
7
8
public void run () {
while ( true ) {
mutex . p ();
←
System . out . println ( " kritischen Abschnitt betreten : "
+ getName ());
try { sleep (( int )( Math . random () * 100));}
catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
mutex . v ();
←
System . out . println ( " kritischen Abschnitt verlassen : "
+ getName ());
}
}
10
11
12
13
14
15
16
17
18
19
20
21
22
}
102 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
MutualExclusion.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class MutualExcl us io n {
public static void main ( String [] args ) {
int n o T h r e a d s I n C r i t i c a l S e c t i o n =1;
if ( args . length != 1) {
System . err . println (
" usage : java Mu t ua lE x cl us io n < NoThreadsInCriticalSection > " );
System . exit (1);
} else
n o T h r e a d s I n C r i t i c a l S e c t i o n = Integer . parseInt ( args [0]);
Semaphore mutex = new Semaphore ( n o T h r e a d s I n C r i t i c a l S e c t i o n );
for ( int i = 1; i <= 10; i ++) {
new MutexThread ( mutex , " Thread " + i );
}
}
}
103 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Der Aufruf zeigt, dass stets nur so viele Threads im kritischen Abschnitt
sind, wie man beim Aufruf angegeben hat:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ java MutualExclusion 1
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
...
$ java MutualExclusion 3
kritischen Abschnitt betreten :
kritischen Abschnitt betreten :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
kritischen Abschnitt verlassen :
kritischen Abschnitt betreten :
...
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
1
1
1
1
3
3
1
1
← 1
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
1
2
3
1
1
1
4
4
1
← 1
← 0
← 1
← 0
← 1
← 0
← 1
← 0
← 2
← 3
← 2
← 3
← 2
← 3
← 2
← 3
104 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Frage
Was passiert durch Aufruf von
$ java MutualExclusion 0
105 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
H¨orsaal¨ubung
¨
Andern
Sie das letzte Programm (EvenThread) so ab, dass die Klasse
Even ohne synchronized- Methoden auskommt.
Verwenden Sie dazu Semaphore. Test.java
1
2
3
4
5
6
7
8
9
10
class Even {
private int n = 0;
public int next () { // POST : next is always even
++ n ;
try { Thread . sleep (( long )( Math . random ()*10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) { }
++ n ;
return n ;
}
}
←
106 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Bearbeitungsreihenfolge von Threads festlegen
In vielen Anwendungen ist es erforderlich, dass Threads parallel arbeiten
und dennoch eine Abarbeitungsreihenfolge einzuhalten ist. Dabei starten
alle Threads gleichzeitig, f¨
uhren gewisse Aktionen aus und m¨
ussen dann
warten, bis andere Threads Aktivit¨aten abgeschlossen haben.
Insgesamt lassen sich solche Abh¨angigkeiten durch einen Graphen
darstellen:
1 Knoten sind Threads,
2 eine Kante existiert von einem Thread T1 zu T2, falls T1 seine
Aktivit¨aten beendet haben muss, bevor T2 starten kann.
Das folgende Beispiel demonstriert eine solche Situation.
107 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Die Umsetzung in Java erfolgt durch Semaphore:
• F¨
ur jede Abh¨angigkeit (Kante im Graph) wird
eine Semaphore verwendet. Die Semaphoren
sind in einem Array sems zusammengefasst, so
dass die nebenstehend gezeigten
Abh¨angigkeiten definiert sind.
• Bevor eine Aktion ausgef¨
uhrt wird, wird die
p()-Methode f¨
ur alle Semaphoren, die den
eingehenden Kanten entsprechen, ausgef¨
uhrt;
• nach der Aktion die v()-Methode auf allen
Semaphoren der ausgehenden Kanten.
• Der Einfachheit halber bekommen alle
Threads eine Referenz auf das
Semaphoren-Array, auch wenn nicht alle
Threads jede Semaphore benutzen.
108 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Aus Sicht des Threads i werden folgende Aktionen ausgef¨
uhrt:
1
i f¨
uhrt p()-Operation aus: Warten auf v-Operation von i-1
2
i-1 hat v()-Operation ausgef¨
uhrt: i kann Aktion ausf¨
uhren
3
i f¨
uhrt v-Operation aus: i+1 kann aktiv werden
109 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
class T1 extends Thread {
private Semaphore [] sems ;
public T1 ( Semaphore [] sems ) {
this . sems = sems ;
start ();
}
4
5
6
7
private void a1 () {
System . out . println ( " a1 " );
try {
sleep (( int )( Math . random () * 10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
9
10
11
12
13
14
public void run () {
a1 ();
sems [0]. v ();
sems [1]. v ();
sems [2]. v ();
}
16
17
18
19
20
21
22
}
110 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
class T2 extends Thread {
private Semaphore [] sems ;
public T2 ( Semaphore [] sems ) {
this . sems = sems ;
start ();
}
4
5
6
7
private void a2 () {
System . out . println ( " a2 " );
try {
sleep (( int )( Math . random () * 10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
9
10
11
12
13
14
public void run () {
sems [0]. p ();
←
a2 ();
sems [3]. v ();
←
}
16
17
18
19
20
21
}
111 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
class T3 extends Thread {
private Semaphore [] sems ;
public T3 ( Semaphore [] sems ) {
this . sems = sems ;
start ();
}
4
5
6
7
private void a3 () {
System . out . println ( " a3 " );
try {
sleep (( int )( Math . random () * 10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
9
10
11
12
13
14
public void run () {
sems [1]. p ();
a3 ();
sems [4]. v ();
}
16
17
18
19
20
21
}
112 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
class T4 extends Thread {
private Semaphore [] sems ;
public T4 ( Semaphore [] sems ) {
this . sems = sems ;
start ();
}
4
5
6
7
private void a4 () {
System . out . println ( " a4 " );
try {
sleep (( int )( Math . random () * 10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
9
10
11
12
13
14
public void run () {
sems [2]. p ();
a4 ();
sems [5]. v ();
}
16
17
18
19
20
21
}
113 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
class T5 extends Thread {
private Semaphore [] sems ;
public T5 ( Semaphore [] sems ) {
this . sems = sems ;
start ();
}
4
5
6
7
private void a5 () {
System . out . println ( " a5 " );
try {
sleep (( int )( Math . random () * 10));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
9
10
11
12
13
14
public void run () {
sems [3]. p ();
sems [4]. p ();
sems [5]. p ();
a5 ();
}
16
17
18
19
20
21
22
}
114 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
TimingRelation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public class TimingRelation {
public static void main ( String [] args ) {
Semaphore [] sems = new Semaphore [6];
for ( int i = 0; i < 6; i ++) {
sems [ i ] = new Semaphore (0);
}
new T4 ( sems );
new T5 ( sems );
new T1 ( sems );
new T2 ( sems );
new T3 ( sems );
}
}
$ java TimingRelation
a1
a3
a2
a4
a5
$ java TimingRelation
a1
a2
a3
a4
a5
$
115 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Additive Semaphoren
Semaphoren sind Integerwerte, wobei die p()- und v()-Operationen den
Integerwert jeweils um eins inkrementieren bzw. dekrementieren.
Eine Verallgemeinerung davon stellen additive Semaphore dar:
der Integer kann um beliebige Werte inkrementiert bzw.
dekrementiert werden.
116 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Die Methoden p() und v() haben ein Integerargument, das angibt, um
welchen Wert erniedrigt bzw. erh¨
oht werden soll.
Dieses Argument muss positiv sein, ansonsten k¨
onnte z.B. eine pOperation die Semaphore erh¨
ohen.
AdditiveSemaphore.java
1
2
public class Add iti veS e m a p h o r e {
private int value ;
public synchronized void p ( int x ) {
if ( x <= 0)
return ;
while ( value - x < 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 -= x ;
}
4
5
6
7
8
9
10
11
12
13
14
...
16
17
}
117 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
AdditiveSemaphore.java
1
2
3
4
5
6
8
9
10
11
12
13
public synchronized void v ( int x ) {
if ( x <= 0)
return ;
value += x ;
notifyAll (); // NOT notify
←
}
public void change ( int x ) {
if ( x > 0)
v ( x );
else if ( x < 0)
p ( - x );
}
Die Methode v(int) muss notifyAll() verwenden. W¨
urde notify()
verwendet werden, k¨
onnten u.U. mehrere Threads weiterlaufen.
118 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erh¨
oht oder erniedrigt wird.
Dies bedeutet, dass die Verwendung von einer p-Operation p(n) nicht
identisch ist mit n p-Operationen p(1):
• Nehmen wir an, zwei Threads verwenden eine additive Semaphore
zur Synchronisation; der aktuelle Wert sei 4. Beide wollen den Wert
um 3 erniedrigen.
• richtige Vorgehensweise:
• T1 und T2 f¨
uhren p(3) aus.
• T1 wird ausgew¨
ahlt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
119 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erh¨
oht oder erniedrigt wird.
Dies bedeutet, dass die Verwendung von einer p-Operation p(n) nicht
identisch ist mit n p-Operationen p(1):
• Nehmen wir an, zwei Threads verwenden eine additive Semaphore
zur Synchronisation; der aktuelle Wert sei 4. Beide wollen den Wert
um 3 erniedrigen.
• richtige Vorgehensweise:
• T1 und T2 f¨
uhren p(3) aus.
• T1 wird ausgew¨
ahlt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
• falsche Vorgehensweise:
• T1 und T2 f¨
uhren jeweils p(1); p(1); p(1); aus.
• T1 wird ausgew¨
ahlt und (p(1); p(1);) ist abgeschlossen (Semaphor
== 2), dann wird auf T2 umgeschaltet.
• T2 f¨
uhrt (p(1); p(1);) nun blockiert beim Aufruf p(1);
• T1 blockiert beim Aufruf p(1) → Verklemmung
119 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erh¨
oht oder erniedrigt wird.
Dies bedeutet, dass die Verwendung von einer p-Operation p(n) nicht
identisch ist mit n p-Operationen p(1):
• Nehmen wir an, zwei Threads verwenden eine additive Semaphore
zur Synchronisation; der aktuelle Wert sei 4. Beide wollen den Wert
um 3 erniedrigen.
• richtige Vorgehensweise:
• T1 und T2 f¨
uhren p(3) aus.
• T1 wird ausgew¨
ahlt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
• falsche Vorgehensweise:
• T1 und T2 f¨
uhren jeweils p(1); p(1); p(1); aus.
• T1 wird ausgew¨
ahlt und (p(1); p(1);) ist abgeschlossen (Semaphor
== 2), dann wird auf T2 umgeschaltet.
• T2 f¨
uhrt (p(1); p(1);) nun blockiert beim Aufruf p(1);
• T1 blockiert beim Aufruf p(1) → Verklemmung
119 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Semaphorgruppen
Eine Semaphorgruppe ist eine Verallgemeinerung einer additiven
Semaphore:
• Ein Aufruf der Methode change() erh¨
oht oder erniedrigt eine
Menge von Semaphoren, die zur selben Gruppe geh¨oren.
¨
• Die Anderungen
werden nur durchgef¨
uhrt, wenn alle Semaphoren
¨
der Gruppe nicht durch die Anderung
negativ werden; in diesem
¨
Fall wird gewartet ohne dass eine Anderung
vollzogen wird.
120 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
Die Realisierung der Klasse SemaphoreGroup verwendet ein Integerarray
(values) zur Darstellung der Semaphorwerte. Die Umsetzung mit
mehreren Objekten vom Typ AdditiveSemaphore w¨
urde zu
Verklemmungssituationen f¨
uhren.
SemaphoreGroup.java
1
2
public class SemaphoreGroup {
private int [] values ;
public SemaphoreGroup ( int nu m be rO fM e mb er s ) {
if ( numberOfMembers <= 0)
return ;
values = new int [ n um be r Of Me mb e rs ];
}
...
4
5
6
7
8
9
10
}
Die Anzahl der Elemente der Semaphorgruppe wird im Konstruktor
u
¨bergeben.
Es gibt keine p()- und v()-Methode mehr; die Implementierung benutzt
¨
nur die ¨
offentliche Methode changeValues() zur Anderung
von Werten.
121 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
SemaphoreGroup.java
1
2
3
4
5
6
7
8
9
10
public synchronized void changeValues ( int [] deltas ) {
if ( deltas . length != values . length )
return ;
while (! canChange ( deltas )) {
try { wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
doChange ( deltas );
notifyAll ();
}
Der Parameter der Methode changeValues gibt an, um welchen Wert die
Semaphore jeweils ver¨andert werden soll: deltas[i] gibt an, wie values[i]
ge¨andert werden soll; delta[i] kann positiv oder negativ sein.
122 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Semaphore
SemaphoreGroup.java
private boolean canChange ( int [] deltas ) {
for ( int i = 0; i < values . length ; i ++)
if ( values [ i ] + deltas [ i ] < 0)
return false ;
return true ;
1
2
3
4
5
6
}
8
private void doChange ( int [] deltas ) {
for ( int i = 0; i < values . length ; i ++)
values [ i ] = values [ i ] + deltas [ i ];
}
9
10
11
13
14
15
public int ge tN u mb e r O f M e m b e r s () {
return values . length ;
}
¨
Die private Methode canChange() gibt an, ob alle Anderungen
durchf¨
uhrbar
sind oder nicht.
¨
Die private Methode doChange f¨
uhrt die Anderungen
durch. Danach werden in
changeValues() alle wartenden Thread informiert (notifyAll()).
Die ¨
offentliche Methode getNumberOfMembers() dient zum Abfragen der
Gr¨
oße der Semaphorgruppe.
Das Applet semgrp.html verdeutlicht den Gebrauch von Semaphorgruppen.
123 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Monitore und andere Primitive
Monitore und andere Primitive
Semaphore in ihren unterschiedlichen Auspr¨agungen sind Primitive der
Interprozesskommunikation. Andere Primitive wurden entwickelt, sie sind
aber alle jeweils durch Semaphore abbildbar, z.B.:
• Hoare und Brich Hansen haben 1975 Monitore vorgeschlagen:
ein Monitor ist eine gekapselte Datenstruktur, in der eine
Bindungsvariable durch die Operationen WAIT und
SIGNAL verwaltet wird.
(vgl. Java Beispiele mit wait und notify)
• Campell und Habermann f¨
uhrten 1974 Pfadausdrucke ein.
• Atkinson und Hewitt diskutierten 1979 Serializer.
124 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Die bisher betrachteten Primitive haben vorausgesetzt, dass es einen
gemeinsam nutzbaren Speicher gibt.
Die Idee des Nachrichtenaustausch ist es,
• ein Kommunikationsmedium (etwa ein Netz, einen Bus) zu
verwenden, so dass
• ein Prozess (Sender) einem anderen Prozess (Empf¨
anger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empf¨anger wartet, bis er eine Nachricht erhalten hat.
125 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Die bisher betrachteten Primitive haben vorausgesetzt, dass es einen
gemeinsam nutzbaren Speicher gibt.
Die Idee des Nachrichtenaustausch ist es,
• ein Kommunikationsmedium (etwa ein Netz, einen Bus) zu
verwenden, so dass
• ein Prozess (Sender) einem anderen Prozess (Empf¨
anger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empf¨anger wartet, bis er eine Nachricht erhalten hat.
Als Kommunikationsprimitive sind erforderlich:
• send(destination, &message) und
• receive(source, &message).
125 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Die bisher betrachteten Primitive haben vorausgesetzt, dass es einen
gemeinsam nutzbaren Speicher gibt.
Die Idee des Nachrichtenaustausch ist es,
• ein Kommunikationsmedium (etwa ein Netz, einen Bus) zu
verwenden, so dass
• ein Prozess (Sender) einem anderen Prozess (Empf¨
anger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empf¨anger wartet, bis er eine Nachricht erhalten hat.
Als Kommunikationsprimitive sind erforderlich:
• send(destination, &message) und
• receive(source, &message).
Diese Thematik wird u.a. in der Vorlesung Verteilte Systeme“
”
behandelt. Hier wird wieder mittels Java auf
• Message Queues und
• Pipes
eingegangen.
125 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Die bisher betrachteten Primitive haben vorausgesetzt, dass es einen
gemeinsam nutzbaren Speicher gibt.
Die Idee des Nachrichtenaustausch ist es,
• ein Kommunikationsmedium (etwa ein Netz, einen Bus) zu
verwenden, so dass
• ein Prozess (Sender) einem anderen Prozess (Empf¨
anger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empf¨anger wartet, bis er eine Nachricht erhalten hat.
Als Kommunikationsprimitive sind erforderlich:
• send(destination, &message) und
• receive(source, &message).
Diese Thematik wird u.a. in der Vorlesung Verteilte Systeme“
”
behandelt. Hier wird wieder mittels Java auf
• Message Queues und
• Pipes
eingegangen.
125 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Zun¨achst wird ein Puffer mit n Elemente definiert, der es erlaubt, Daten
fester Gr¨
osse zwischen Sender und Empf¨anger auszutauschen.
Dann wird gezeigt, wie Daten beliebiger L¨
anger transferiert werden
k¨onnen.
126 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Puffer mit n Elementen
• Der Erzeuger f¨
ugt Daten am
Pufferende (Position tail ) ein.
• Der Verbraucher entnimmt den Wert
am Pufferanfang (an Position 0
head )) und
• reorganisiert den Puffer, d.h. alle
Elemente werden nach oben
verschoben.
Was halten Sie von dieser L¨
osung?
127 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Puffer mit n Elementen
Das Reorganisieren kann vermieden
werden, wenn der Puffer zyklisch
organisiert wird:
128 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Puffer in Java
BufferN.java
1
2
3
4
5
public class BufferN {
private int head ;
private int tail ;
private int numberOf E l e m e n t s ;
private int [] data ;
public BufferN ( int n ) {
data = new int [ n ];
head = 0;
tail = 0;
n u mberOfElements = 0;
}
...
7
8
9
10
11
12
13
14
}
129 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Puffer in Java
BufferN.java
1
2
3
4
5
6
7
8
9
10
11
12
public synchronized void put ( int x ) {
while ( numberOfElem e n t s == data . length ) {
try {
wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
data [ tail ++] = x ;
if ( tail == data . length )
tail = 0;
n u mberOfElements ++;
notifyAll ();
}
Wenn der Puffer voll geworden ist, muss die Methode put() warten. Die
Schleife ist erforder- lich, da wir notifyAll() verwenden m¨
ussen. Wenn eine
freie Position vorhanden ist, wird der Wert gespeichert und die Variable
tail“ zyklisch inkrementiert, danach wird ein wartender Thread geweckt.
”
130 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Puffer in Java
BufferN.java
1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized int get () {
while ( numberOfElem e n t s == 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 ) {}
}
int result = data [ head ++];
if ( head == data . length )
head = 0;
numberOfElements - -;
notifyAll ();
return result ;
}
Die Methode get() funktioniert analog.
131 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
Nun wird gezeigt, wie Daten beliebiger L¨
ange ausgetauscht werden
k¨onnen.
Dabei muss die Nachrichtengrenze bewahrt bleiben, d.h. wird z.B.
Byte-Array gesendet so wird exakt diese Menge an Daten empfangen:
132 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
MessagaQueue.java
1
2
3
4
5
6
public class MessageQueue {
private byte [][] msgQueue = null ;
private int qsize = 0;
// size of message queue as
// number of entries ( not number of bytes )
private int head = 0;
private int tail = 0;
public MessageQueue ( int capacity ) {
if ( capacity <= 0)
return ;
msgQueue = new byte [ capacity ][];
}
...
8
9
10
11
12
13
14
}
Damit der Sender die Orginal Nachricht bearbeiten kann, nachdem er sie
gesendet hat, wird zuerst eine Kopie erstellt.
133 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
MessagaQueue.java
1
2
3
4
5
6
public synchronized void send ( byte [] msg ) {
while ( qsize == msgQueue . length ) {
try {
wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
msgQueue [ tail ] = new byte [ msg . length ]; // copy message
// and store the copy
for ( int i = 0; i < msg . length ; i ++)
msgQueue [ tail ][ i ] = msg [ i ];
qsize ++;
tail ++;
if ( tail == msgQueue . length )
tail = 0;
notifyAll ();
8
9
10
11
12
13
14
15
16
17
}
134 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
MessagaQueue.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public synchronized byte [] receive () {
while ( qsize == 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 ) {}
}
byte [] result = msgQueue [ head ];
msgQueue [ head ] = null ;
qsize - -;
head ++;
if ( head == msgQueue . length )
head = 0;
notifyAll ();
return result ;
}
Durch ein Applet kann das Verhalten von MessagaQueue demonstriert
werden.
135 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Pipes
Message Queues bewahren die Nachrichtengrenzen; deshalb wird diese
Art der Kommunikation auch nachrichtenorientiert“ genannt.
”
Demgegen¨
uber ist es f¨
ur den Empf¨anger einer Nachricht bei
streamorientierten“ Kommunkation nicht m¨
oglich, die einzelnen
”
Nachrichten zu unterscheiden, die an der Kommunikation beteiligt
sind.
Diese Verhalten verdeutlicht die Kommunikation u
¨ber Pipes (mit einem
Byte-Array fester Gr¨
osse)
→ pipe
136 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Pipe in Java
Pipe.java
1
2
3
4
5
public class Pipe {
private byte [] buffer = null ;
private int bsize = 0;
private int head = 0;
private int tail = 0;
public Pipe ( int capacity ) {
if ( capacity <= 0)
return ;
buffer = new byte [ capacity ];
}
...
7
8
9
10
11
12
13
}
137 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Die send()-Operation, die Daten in eine Pipe schreibt, muss als atomare
Operation realisiert werden: wenn die Nachricht gr¨
osser ist, als der noch
verf¨
ugbar freie Platz in der Pipe, muss der Sender blockieren, bis ein
Empf¨anger durch receive() Platz in der Pipe gemacht hat.
Pipe.java
1
2
3
4
5
6
7
9
10
11
12
13
14
15
16
17
18
19
public synchronized void send ( byte [] msg ) {
if ( msg . length <= buffer . length ) {
// sent as atomic operation
while ( msg . length > buffer . length - bsize ) {
try { wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
// copy message into buffer
for ( int i = 0; i < msg . length ; i ++) {
buffer [ tail ] = msg [ i ];
tail ++;
if ( tail == buffer . length )
tail = 0;
}
bsize += msg . length ;
notifyAll ();
} else {
...
138 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Wenn die gesamte L¨ange der Nachricht gr¨
osser ist, als die Kapazit¨at der
Pipe, so wird die Nachricht in kleine St¨
ucke geteilt und jeweils nur ein
St¨
uck gesendet.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public synchronized void send ( byte [] msg ) {
...
else { // send in portions
int offset = 0;
int stillToSend = msg . length ;
while ( stillToSend > 0) {
while ( bsize == buffer . length ) {
try { wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
int sendNow = buffer . length - bsize ;
if ( stillToSend < sendNow ) sendNow = stillToSend ;
for ( int i = 0; i < sendNow ; i ++) {
buffer [ tail ] = msg [ offset ];
tail ++;
if ( tail == buffer . length ) tail = 0;
offset ++;
}
bsize += sendNow ; stillToSend -= sendNow ;
notifyAll ();
}
}
}
139 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Interprozesskommunikation
Nachrichtenaustausch
Beim Empfang einer Nachricht, muss blockiert werden, bis Daten in der
Pipe verf¨
ugbar sind. Ein Parameter beim receive() gibt die erwartete
Gr¨
osse der Nachricht an; wenn weniger Daten in der Pipe sind, wird nicht
blockiert, sondern nur der verf¨
ugbare Teil gelesen.
Pipe.java
public synchronized byte [] receive ( int noBytes ) {
while ( bsize == 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 ) {}
}
if ( noBytes > bsize )
noBytes = bsize ;
byte [] result = new byte [ noBytes ];
for ( int i = 0; i < noBytes ; i ++) {
result [ i ] = buffer [ head ];
head ++;
if ( head == buffer . length )
head = 0;
}
bsize -= noBytes ;
notifyAll ();
return result ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
}
140 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
IPC Problem
1 Prozessmodell
2 Interprozesskommunikation
3 IPC Probleme
Problem speisender Philosophen
Lese-Schreiber Problem
Das Problem des schlafenden Friseurs
4 Scheduling
141 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
Problem speisender Philosophen (Dijkstra, 1965)
• F¨
unf Philosophen sitzen um einen runden Tisch.
• Jeder hat einen Teller mit Spagetti vor sich auf
dem Teller.
• Zwischen jedem Teller liegt eine Gabel. Um Essen
zu k¨onnen, braucht man immer zwei Gabeln.
• Das Leben eines Philosophen besteht aus Essen
und Denken.
• Wenn ein Philosoph hungrig wird, versucht er die
linke und rechte Gabel zu nehmen und zu Essen.
Das Problem:
Es ist ein Programm f¨
ur einen Philosophen zu finden, das, auf
alle Philosophen angewendet, nie dazu f¨
uhrt, dass einer der
Philosophen verhungert.
142 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
Dieses Problem ist typisch f¨
ur Betriebssysteme: es verdeutlicht den
Wettbewerb um eine begrenzte Anzahl von exklusiv nutzbaren
Betriebsmitteln, wie CPU oder E/A Ger¨ate.
Eine offensichtliche (aber nicht korrekte) L¨
osung in C
ist:
1
2
3
4
5
6
7
8
9
10
11
const int N =5;
philosophers ( int i ) {
while ( true ) {
think ();
takeFork ( i );
take_fork (( i +1)% N );
eat ();
putFork ( i );
putFork (( i +1)% N );
}
}
// take left fork
// take right fork
// put left fork back
// put right fork back
Die Funktion takeFork() wartet, bis die entsprechende
Gabel frei ist und nimmt dann die Gabel. Ist die Gabel
nicht frei, wird eine Zeit lang gewartet und erneut
versucht, die Gabel zu nehmen.
Was halten Sie
von dieser
L¨osung?
143 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
1
2
3
4
5
6
7
8
9
10
11
const int N =5;
philosophers ( int i ) {
while ( true ) {
think ();
takeFork ( i );
take_fork (( i +1)% N );
eat ();
putFork ( i );
putFork (( i +1)% N );
}
}
// take left fork
// take right fork
// put left fork back
// put right fork back
Die L¨
osung funktioniert nicht, wenn z.B. alle Philosophen gleichzeitig die
linke Gabel nehmen, da niemand die rechte Gabel nehmen kann und so
alle verhungern (Deadlock).
144 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
Mit dem synchronized-Konzept von Java ist eine L¨
osung realisierbar,
denn das Nehmen einer Gabel wird atomar: Philosophers.java
1
2
4
5
6
7
8
10
11
12
14
15
16
17
18
19
class Table {
private boolean [] usedFork ;
public Table ( int numberForks ) {
usedFork = new boolean [ numberForks ];
for ( int i = 0; i < usedFork . length ; i ++)
usedFork [ i ] = false ;
}
private int left ( int i ) {
return i ;
}
private int right ( int i ) {
if ( i +1 < usedFork . length )
return i +1;
else
return 0;
}
20
145 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
21
22
23
24
25
26
27
28
29
31
32
33
34
35
36
public synchronized void takeForks ( int position ) {
while ( usedFork [ left ( position )]
|| usedFork [ right ( position )]) {
try { wait ();
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
}
usedFork [ left ( position )] = true ;
usedFork [ right ( position )] = true ;
}
public synchronized void p o s i t i o n B a c k F o r k s ( int position ) {
usedFork [ left ( position )] = false ;
usedFork [ right ( position )] = false ;
notifyAll ();
}
} // Table
37
146 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
38
39
40
42
43
44
45
46
48
49
50
51
52
53
54
55
57
58
59
60
61
62
63
class Philosoph extends Thread {
private Table Table ;
private int position ;
public Philosoph ( Table Table , int position ) {
this . Table = Table ;
this . position = position ;
start ();
}
public void run () {
life of a philosoph
while ( true ) {
thinking ( position );
Table . takeForks ( position );
eating ( position );
Table . po sit ion Ba c k F o r k s ( position );
}
}
private void thinking ( int position ) {
System . out . println ( " Philosoph " + position
+ " is thinking . " );
try {
sleep (( int )( Math . random () * 20000));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) { }
}
147 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Problem speisender Philosophen
private void eating ( int position ) {
System . out . println ( " Philosoph " + position
+ " starts eating . " );
try {
sleep (( int )( Math . random () * 20000));
} catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
System . out . println ( " Philosoph " + position
+ " finished eating . " );
}
65
66
67
68
69
70
71
72
73
74
}
76
public class Philosophers {
private static final int numberForks = 5;
77
public static void main ( String [] args ) {
Table Table = new Table ( numberForks );
for ( int i = 0; i < numberForks ; i ++)
new Philosoph ( Table , i );
}
79
80
81
82
83
84
}
Hier eine L¨
osung, die Semaphorgruppen verwendet, um die Operation
atomar zu machen.
Ein Applet verdeutlicht dies.
148 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Lese-Schreiber Problem
Lese-Schreiber Problem
Das Lese-Schreiber Problem modelliert den Zugriff auf eine Datenbank:
Auf einen Datenbestand wollen mehrere Prozesse gleichzeitig
zugreifen.
• Es ist erlaubt, dass mehrere Prozesse gleichzeitig lesen,
• aber nur einer darf zu einem Zeitpunkt schreiben.
• Wenn geschrieben wird, darf kein Prozess (auch kein
lesender) zugreifen.
149 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Lese-Schreiber Problem
1
2
3
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
semaphore mutex = 1; // controls access to rc
semaphore db = 1; // controls access to DB
int rc = 0; // # processes reading or wanting to
reader () {
while ( true ) { // repeat forever
down ( mutex );
rc ++;
if ( rc == 1) down ( db ); // for first reader
up ( mutex );
read _data_base ();
down ( mutex );
rc - -;
if ( rc == 0) up ( db ); // release if last reader
up ( mutex );
use_data_read ();
}
}
writer () {
while ( true ) {
think_up_data ();
down (& db );
w ri te _data_base ()(); // update the data
up ( db ); /
}
}
Die L¨
osung dazu verwendet eine
Semaphore db, um den Zugriff auf die
Datenbank zu synchronisieren.
•
•
•
•
Der erste Leser (reader) ruft
f¨
ur den Zugriff auf den
Datenbestand die Methode
down() mit der Semaphore
db“ auf,
”
nachfolgende Leser erh¨
ohen
lediglich den Z¨
ahler rc“.
”
Wenn Leser den kritischen
Bereich verlassen, erniedrigen
sie den Z¨
ahler und
der letzte Leser ruft up() f¨
ur
die Semaphore auf und weckt
einen potentiellen Schreiber.
¨
L¨
osung in Java? → Ubung
150 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Das Problem des schlafenden Friseurs
Das Problem des schlafenden Friseurs
In einem Friseursalon mit einem Friseurstuhl und n
St¨
uhlen f¨
ur wartende Kunden arbeitet ein Friseur.
• Falls kein Kunde die Haare geschnitten haben
m¨
ochte (also alle St¨
uhle leer sind), setzt sich
der Friseur auf den Friseurstuhl und schl¨aft.
• Ein eintreffender Kunde muss den Friseur
wecken, um die Haare geschnitten zu
bekommen.
• W¨
ahrend der Friseur Haare schneidet, m¨
ussen
weitere Kunden entweder Platz nehmen und
warten, bis der Friseur frei ist oder sp¨ater
nochmal kommen (falls alle St¨
uhle besetzt
sind).
Quelle: ’Moderne BS’,
Tannenbaum
¨
L¨
osung mit Semaphoren oder Java Synchronisation als Ubung.
151 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Das Problem des schlafenden Friseurs
L¨osungsidee
Mittels Semaphore kann man das Problem l¨
osen:
customers Anzahl der Wartenden Kunden
barbers Anzahl schlafender Fris¨
ore
mutex f¨
ur den Schutz der Z¨ahlvariablen f¨
ur wartende Kunden
1
2
3
4
5
# define chairs 5
typedef int semaphore ;
semaphore customers = 0;
semaphore barbers = 0;
int waiting = 0;
//
//
//
//
//
# chairs for waiting customers
use your imagination
# customers waiting for service
# barbers waiting for customers
customers are waiting , not being cut
152 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
IPC Probleme
Das Problem des schlafenden Friseurs
Fris¨or, Kunde
1
2
3
4
5
6
7
8
9
10
12
13
14
15
16
17
18
19
20
21
22
void barber ( void ) {
while ( true ) {
down (& customers );
down (& mutex );
waiting - -;
up (& mutex );
up (& barbers );
cut_hair ();
}
}
//
//
//
//
//
go to sleep if # customers =0
acquire access to waiting
dec . count of waiting customers
release waiting
one barber is now ready to cut hairs
void customer ( void ) {
down (& mutex );
// enter critic region
if ( waiting < chairs ) { // if there are no free chairs , leave
waiting ++;
up (& customers );
// wake up barber if necessary
up (& mutex );
// release access to waiting
down (& barbers );
// go to sleep if # of free barbers is 0
get_haircut ();
} else
up (& mutex );
// shop is full ; do not wait
}
153 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling
1 Prozessmodell
2 Interprozesskommunikation
3 IPC Probleme
4 Scheduling
Round-Robin Scheduling
Scheduling mit Priorit¨aten
Shortest-Job-First
Garantiertes Scheduling
Zweistufiges Scheduling
Fallbeispiel: Linux Scheduler
154 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling
Der Teil des Betriebssystems, der entscheidet,
• welcher der Prozesse,
• die im Zustand bereit“ sind,
”
• ausgew¨
ahlt wird und dann
• den Prozessor zugeteilt bekommt,
heißt Scheduler.
Das Verfahren, wie ausgew¨ahlt wird, nennt man Scheduling-Algorithmus.
155 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Kriterien f¨ur Scheduling-Algorithmus
Fairness Jeder Prozess wird gleichermaßen ber¨
ucksichtigt; es gibt
keine privilegierten Prozesse.
Effizienz Der Prozessor wird stets vollst¨andig ausgelastet.
Antwortzeit Die Antwortzeit f¨
ur die interaktiv arbeitenden Benutzer
wird minimiert.
Verweilzeit Die Zeit, die auf Ausgabe von Stapelauftr¨age gewartet
werden muss, ist minimal.
Durchsatz Die Anzahl der Jobs, die in einem gegebenen Zeitintervall
ausgef¨
uhrt werden, wird maximiert.
Ressourcenbedarf Der f¨
ur die Implementierung ben¨
otigte
Ressourcenbedarf ist minimal.
Nicht alle Kriterien sind gleichzeitig zu erf¨
ullen, da sie teilweise
widerspr¨
uchlich sind (z.B. Antwortzeit – Verweilzeit).
156 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Kategorisierung
Ein Betriebssystem nutzt den Unterbrechungsmechanismus moderner
CPU’s, um sicher zu stellen, dass kein Prozess zu lange ausgef¨
uhrt wird:
Wenn die Hardware einen Interrupt (etwa 100 mal pro Sekunde)
ausgel¨ost hat, erh¨alt das Betriebssystem die Kontrolle und der
Scheduler w¨ahlt einen neuen Prozess aus.
Je nachdem, wie der Scheduler die Auswahl der Prozesse vornimmt,
werden Scheduling-Algorithmen unterschieden in:
• preemptive Scheduling:
rechnende Prozesse k¨
onnen unterbrochen werden.
• run to completion (non-preemptive) Scheduling:
der rechnende Prozess wird nicht unterbrochen.
Welche Unterschiede ergeben sich?
157 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Kategorisierung
Ein Betriebssystem nutzt den Unterbrechungsmechanismus moderner
CPU’s, um sicher zu stellen, dass kein Prozess zu lange ausgef¨
uhrt wird:
Wenn die Hardware einen Interrupt (etwa 100 mal pro Sekunde)
ausgel¨ost hat, erh¨alt das Betriebssystem die Kontrolle und der
Scheduler w¨ahlt einen neuen Prozess aus.
Je nachdem, wie der Scheduler die Auswahl der Prozesse vornimmt,
werden Scheduling-Algorithmen unterschieden in:
• preemptive Scheduling:
rechnende Prozesse k¨
onnen unterbrochen werden.
• run to completion (non-preemptive) Scheduling:
der rechnende Prozess wird nicht unterbrochen.
Welche Unterschiede ergeben sich?
157 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Round-Robin Scheduling
Ein einfaches und h¨aufig angewendetes Verfahren ist das Round-Robin
Verfahren:
• Jeder Prozess erh¨
alt eine Zeitscheibe (Quantum), die er maximal
f¨
ur die Ausf¨
uhrung zugeteilt bekommt.
• Ist diese Zeit abgelaufen, wird ihm der Prozessor entzogen und
• ein anderer Prozess wird ausgew¨
ahlt.
• Bei Blockierung wg. E/A wird dem Prozess der Prozessor entzogen,
auch wenn sein Quantum noch nicht abgelaufen ist.
Zur Implementierung verwaltet der Scheduler eine Queue mit
rechenbereiten Prozessen, wobei ein aktiver Prozess nach Ablauf des
Quantums wieder hinten in die Liste eingereiht wird:
158 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Round-Robin Scheduling
Ein einfaches und h¨aufig angewendetes Verfahren ist das Round-Robin
Verfahren:
• Jeder Prozess erh¨
alt eine Zeitscheibe (Quantum), die er maximal
f¨
ur die Ausf¨
uhrung zugeteilt bekommt.
• Ist diese Zeit abgelaufen, wird ihm der Prozessor entzogen und
• ein anderer Prozess wird ausgew¨
ahlt.
• Bei Blockierung wg. E/A wird dem Prozess der Prozessor entzogen,
auch wenn sein Quantum noch nicht abgelaufen ist.
Zur Implementierung verwaltet der Scheduler eine Queue mit
rechenbereiten Prozessen, wobei ein aktiver Prozess nach Ablauf des
Quantums wieder hinten in die Liste eingereiht wird:
158 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Dauer f¨ur das Quantum
Eine Implementierung dieses Verfahrens muss eine “richtige” Wahl f¨
ur die
Dauer des Quantums finden:
Angenommen, ein Kontextwechsel dauert 5 Millisekunden.
• Quantum=20 Millisekunden
→ 5/20 ∗ 100 = 25% Verwaltungsaufwand sind zu viel.
• Quantum=500 Millisekunden
→ 5/500 ∗ 100 = 1% Verwaltungsaufwand bedeutet, dass u.U. ein
Benutzer zu lange warten (5 Sekunde, wenn 10 Benutzer gleichzeitig
arbeiten) muss, bevor seine Anfrage (Tastendruck w¨ahrend
Editorsitzung) bearbeitet wird.
159 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Dauer f¨ur das Quantum
Folgerung:
• Quantum zu klein → wegen h¨
aufiger Kontextwechsel sinkt
Prozessorausnutzung
• Quantum zu gross → schlechte Antwortzeiten bei vielen kurzen
Anfragen
• Erfahrungswert: Quantum=50 Millisekunden ist guter Kompromiss
Beurteilung Round Robin:
E/A intensive Prozesse, die h¨aufig vor Ablauf des Quantums
eine blockierende Systemfunktion aufrufen und damit den
Prozessor entzogen bekommen, werden durch Round-Robin
benachteiligt.
160 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Dauer f¨ur das Quantum
Folgerung:
• Quantum zu klein → wegen h¨
aufiger Kontextwechsel sinkt
Prozessorausnutzung
• Quantum zu gross → schlechte Antwortzeiten bei vielen kurzen
Anfragen
• Erfahrungswert: Quantum=50 Millisekunden ist guter Kompromiss
Beurteilung Round Robin:
E/A intensive Prozesse, die h¨aufig vor Ablauf des Quantums
eine blockierende Systemfunktion aufrufen und damit den
Prozessor entzogen bekommen, werden durch Round-Robin
benachteiligt.
160 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Round-Robin Scheduling
Dauer f¨ur das Quantum
In Unix/Linux kann das Quantum des aktuellen Prozesses wie folgt
ermittelt werden (in C):
getQuantum.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# include < stdio .h >
# include < unistd .h >
# include < sched .h >
←
/*
struct timespec {
time_t tv_sec ;
long
tv_nsec ; // Nanosekunden =10** -9 Sekunden
} ;
*/
int main () {
struct timespec t ;
if ( s c h e d _ r r _ g e t _ i n t e r v a l ( getpid () ,& t )==0)
←
printf ( " sec : % d millisec : % ld \ n " , t . tv_sec , t . tv_nsec /1000000);
}
$ getQuantum
sec : 0 millisec : 24
$
161 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Scheduling mit Priorit¨aten
Die Grundidee des Priorit¨ats-Scheduling ist:
• Jeder Prozess bekommt eine Priorit¨
at zugewiesen.
• Es wird immer der rechenbereite Prozess mit der h¨
ochsten Priorit¨at
ausgef¨
uhrt.
Problem:
Wird kein weiterer Mechanismus realisiert, so kommt es vor,
dass Prozesse mit hoher Priorit¨at verhindern, dass ein Prozess
mit niedriger Priorit¨at je den Prozessor bekommen
(Verhungern).
162 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Scheduling mit Priorit¨aten
Die Grundidee des Priorit¨ats-Scheduling ist:
• Jeder Prozess bekommt eine Priorit¨
at zugewiesen.
• Es wird immer der rechenbereite Prozess mit der h¨
ochsten Priorit¨at
ausgef¨
uhrt.
Problem:
Wird kein weiterer Mechanismus realisiert, so kommt es vor,
dass Prozesse mit hoher Priorit¨at verhindern, dass ein Prozess
mit niedriger Priorit¨at je den Prozessor bekommen
(Verhungern).
162 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Scheduling mit Priorit¨aten
Deshalb wird folgender Mechanismus als L¨
osung implementiert:
• Der Scheduler verringert die Priorit¨
at des rechnenden Prozesses bei
jedem Interrupt, der durch die interne Prozessoruhr ausgel¨ost wird.
• Damit f¨
allt die Priorit¨at des laufenden Prozesses irgendwann unter
die Priorit¨at eines anderen rechenbereiten Prozesses;
• in diesem Fall wird ein solcher rechenbereiter Prozess mit h¨
oherer
Priorit¨at ausgew¨ahlt.
163 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Priorit¨aten k¨
onnen statisch oder dynamisch vergeben werden.
statisch Die Priorit¨at wird vor dem Prozessstart festgelegt. Z.B.
kann man folgende Regel anwenden:
Batchprozesse < Systemprozesse < Interaktive Prozesse <
...
dynamisch Dynamische Vergabe von Priorit¨aten wird h¨aufig realisiert,
um Systemziele zu erreichen.
Z.B. Optimierung des I/O-Verhaltens: dann muss ein
Prozess, der bei E/A Ereignis rechenbereit wird, hohe
Priorit¨at bekommen, damit das E/A Ereignis behandelt
werden kann.
164 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
In modernen Betriebssystemen werden Prozesse in Klassen eingeteilt,
wobei
• zwischen den Klassen Priorit¨
ats-Scheduling und
• innerhalb der Klasse Round-Robin Scheduling
verwendet wird.
165 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Thread Priorit¨aten in Java
Die JVM soll plattformunabh¨
angig implementierbar sein. Daher gibt
es in Java keine Vorgaben bzgl. des Scheduling.
Methoden, mit denen die Priorit¨at eines Thread beeinflusst werden kann:
• Jeder Thread hat eine Priorit¨
at zwischen MIN PRIORITY und
MAX PRIORITY ([1,10]).
• Wird ein neuer Thread erzeugt, erbt er die Priorit¨
at vom Vater.
• Der Defaultwert, wenn ein Thread aus main() erzeugt wurde, ist
Thread.NORM PRIORITY (5).
• Die Methode getPriority() liefert die aktuelle Priorit¨
at eines Threads.
• Mit setPriority()kann die Priorit¨
at ver¨andert werden.
166 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Thread Priorit¨aten in Java
Achtung:
• Priorit¨
aten beeinflussen weder Semantik noch Korrektheit eines
Java Programms.
• Priorit¨
aten d¨
urfen beim Programmieren nicht als Ersatz f¨
ur Locking
verwendet werden!
• Priorit¨
aten d¨
urfen nur verwendet werden, um die relative
Wichtigkeit unterschiedlicher Threads untereinander zu definieren.
167 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
3 Threads mit unterschiedlicher Priorit¨at in Java I
ThreadPriority.java
1
2
4
5
6
7
8
import java . util .*;
import java . io .*;
class ThreadPriority {
public static void main ( String [] args )
{
ThreadPriority t = new Thr eadPrio rity ();
t . doIt ();
}
public void doIt ()
{
MyThread t1 = new MyThread ( " Thread One : " );
t1 . setPriority ( t1 . getPriority () -4); // Default is 5
MyThread t2 = new MyThread ( " Thread Two : " );
MyThread t3 = new MyThread ( " Thread Three : " );
t3 . setPriority (10);
t1 . start ();
t3 . start ();
t2 . start ();
}
10
11
12
13
14
15
16
17
18
19
20
}
21
168 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
3 Threads mit unterschiedlicher Priorit¨at in Java II
ThreadPriority.java
22
23
24
class MyThread extends Thread {
static String spacerString = " " ;
public String filler ;
public MyThread ( String ThreadNameIn ) {
filler = spacerString ;
spacerString = spacerString + "
setName ( ThreadNameIn );
}
26
27
28
29
30
public void run () {
for ( int k =0; k < 5; k ++) {
System . out . println ( filler +
Thread . currentThread (). getName () +
" Iteration = " + Integer . toString ( k ) ) ;
}
}
32
33
34
35
36
37
38
39
";
}
169 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
3 Threads mit unterschiedlicher Priorit¨at in Java
ThreadPriority.java
$ java ThreadPriority
Thread
Thread
Thread
Thread
Thread
One :
One :
One :
One :
One :
Thread
Thread
Thread
Thread
Thread
Iteration = 0
Iteration = 1
Iteration = 2
Iteration = 3
Iteration = 4
Two :
Two :
Two :
Two :
Two :
Thread Three :
Thread Three :
Thread Three :
Thread Three :
Thread Three :
Iteration = 0
Iteration = 1
Iteration = 2
Iteration = 3
Iteration = 4
Iteration
Iteration
Iteration
Iteration
Iteration
=
=
=
=
=
0
1
2
3
4
Versuche Sie das Programm auf Ihrem Rechner.
Ist die Ausgabe genau so ?
170 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Scheduling mit Priorit¨
aten
Prozesspriorit¨aten in Unix/Linux
In Linux ist die Priorit¨at eines Prozesses ein Integer im Bereich -20 bis 20
(-20 ist h¨
ochste Priorit¨at, Default ist 0).
Das folgende Programm zeigt, wie die Priorit¨at eines Prozesses gesetzt
und abgefragt werden kann: getPriority.c
1
2
3
4
6
7
8
9
10
11
12
13
14
15
# include
# include
# include
# include
< stdio .h >
< sched .h >
< sys / resource .h > // wg . PRIO_USER
< errno .h >
extern int errno ;
int main () {
int prio = 0;
if ( setpriority ( PRIO_USER , 0 , 10) != 0) {
←
fprintf ( stderr , " Error setpriority : % s \ n " , strerror ( errno ));
exit (1);
}
printf ( " % d \ n " , getpriority ( PRIO_USER , 0)); ←
exit (0);
}
171 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Shortest-Job-First
Die beiden letzten Verfahren sind f¨
ur interaktive Systeme entworfen
worden.
Ein Verfahren f¨
ur Systeme, bei denen die Ausf¨
uhrungszeiten der
einzelnen Prozesse im voraus bekannt sind, benutzt eine Warteschlange
f¨
ur die gleichgewichtigen Prozesse.
Der Scheduler w¨ahlt den Prozess mit der k¨
urzesten
Ausf¨
uhrungszeit zuerst.
Gem¨ass dieser Methode wird die durchschnittliche Verweilzeit (Zeit,
die der Prozess im System verweilt ) von Prozessen minimiert:
172 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Shortest-Job-First
Die beiden letzten Verfahren sind f¨
ur interaktive Systeme entworfen
worden.
Ein Verfahren f¨
ur Systeme, bei denen die Ausf¨
uhrungszeiten der
einzelnen Prozesse im voraus bekannt sind, benutzt eine Warteschlange
f¨
ur die gleichgewichtigen Prozesse.
Der Scheduler w¨ahlt den Prozess mit der k¨
urzesten
Ausf¨
uhrungszeit zuerst.
Gem¨ass dieser Methode wird die durchschnittliche Verweilzeit (Zeit,
die der Prozess im System verweilt ) von Prozessen minimiert:
172 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Gegeben seien 4 Prozesse mit folgenden Ausf¨
uhrungszeiten:
A 8 Sekunden
B 6 Sekunden
C 4 Sekunden
D 6 Sekunden
Ausf¨
uhrungsreihenfolge A, B, C, D:
A
B
C
D
Verweilzeit
8
8 + 6 = 14
8 + 6 + 4 = 18
8 + 6 + 4 + 6 = 24
→ durchschnittliche Verweilzeit = (8 + 14 + 18 + 24)/4 = 16
173 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Gegeben seien 4 Prozesse mit folgenden Ausf¨
uhrungszeiten:
A 8 Sekunden
B 6 Sekunden
C 4 Sekunden
D 6 Sekunden
Ausf¨
uhrungsreihenfolge C, B, C, A:
C
B
D
A
Verweilzeit
4
4 + 6 = 10
4 + 6 + 6 = 16
4 + 6 + 6 + 8 = 24
→ durchschnittliche Verweilzeit = (4 + 10 + 16 + 24)/4 = 13, 5
174 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Behauptung:
Den Prozess mit der k¨
urzesten Ausf¨
uhrungszeit zu w¨ahlen ist
optimal bzgl. der mittleren Verweilzeit.
Beweis:
Gegeben seien 4 Prozesse A-D mit den jeweiligen Verweilzeiten
a, b, c, d, die in der Reihenfolge A,B,C,D ausgef¨
uhrt werden.
Verweilzeit
A
a
B
a+b
C
a+b+c
D a+b+c +d
→ durchschnittliche Verweilzeit = (4a + 3b + 2c + d)/4
d.h. a beeinflusst die durchschnittliche Verweilzeit am meisten,
gefolgt von b und c; daraus folgt:
die durchschnittliche Verweilzeit ist minimal, wenn zuerst A der
Prozess mit der kleinsten Ausf¨
uhrungszeit ist, B der Prozess mit
der zweit kleinsten Ausf¨
uhrungszeit, etc
175 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
Ausf¨uhrungszeit bestimmen
Das Problem bei interaktiven Betriebssystemen ist es, die
Ausf¨
uhrungszeit der Prozesse zu bestimmen.
Idee:
Sch¨
atze die Ausf¨
uhrungszeit auf Basis der gemessenen Zeit
der Vergangenheit M.
• Der Scheduler w¨
ahlt dann den Prozess mit der k¨
urzesten
gesch¨
atzten Zeit.
• Der neue gesch¨
atzte Wert S zum Zeitpunkt n+1 wird aus
dem gewichteten Durchschnitt des aktuellen und des
vorherigen Wertes gebildet.
Sn+1 = α ∗ Mn + (1 − α) ∗ Sn
α(0 ≤ α ≤ 1) ist dabei der Faktor, der den Einfluss der
zur¨
uckliegenden Periode auf die Sch¨atzung angibt; Werte
nahe 1 ordnen der gesch¨atzten Vergangenheit wenig
Stellenwert zu.
176 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Shortest-Job-First
H¨orsaal¨ubung
Gegeben seien 5 Prozesse mit folgenden Ausf¨
uhrungszeiten:
A 6 Sekunden
B 6 Sekunden
C 8 Sekunden
D 2 Sekunden
E 4 Sekunden
Welche Ausf¨
uhrungsreihenfolge f¨
uhrt zur optimalen durchschnittlichen
Verweilzeit?
Prozess
A
B
C
D
E
Verweilzeit
→ durchschnittliche Verweilzeit =
177 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
Garantiertes Scheduling
Beim garantierten Scheduling wird einem Prozess eine gewisse
Performance versprochen und die Einhaltung garantiert.
M¨
ogliche Versprechen:
• Bei interaktiven Systemen mit n Benutzern, erh¨
alt jeder 1/n der
verf¨
ugbaren Prozessorzeit
• Bei Echtzeitsystemen wird vom System garantiert, dass ein
Prozess innerhalb einer Zeitschranke abgeschlossen ist.
178 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
interaktive Systeme
Zu jeder Benutzersitzung sei die insgesamt erhaltene Prozessorzeit seit
Sitzungsbeginn e.
Der Scheduler berechnet die dem Benutzer zustehende Zeit z
und ermittelt das Verh¨altnis von erhaltener Zeit e und
zustehender Zeit z.
Das Verh¨altnis 0,5 bedeutet, dass der Prozess halb so viel Zeit
verbraucht hat, wie ihm garantiert wurde.
Der Scheduler w¨
ahlt immer den Prozess, mit dem
berechneten kleinsten Verh¨
altnis e/z.
Beispiel
Prozess
A
B
C
erhaltene
Zeit e
14
11
20
versprochene
Zeit z
(14+11+20)/3=15
(14+11+20)/3=15
(14+11+20)/3=15
e/z
14/15=0,93
11/15=0,73
20/15=1,33
ausgew¨
ahlter
Prozess
X
179 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
interaktive Systeme
Zu jeder Benutzersitzung sei die insgesamt erhaltene Prozessorzeit seit
Sitzungsbeginn e.
Der Scheduler berechnet die dem Benutzer zustehende Zeit z
und ermittelt das Verh¨altnis von erhaltener Zeit e und
zustehender Zeit z.
Das Verh¨altnis 0,5 bedeutet, dass der Prozess halb so viel Zeit
verbraucht hat, wie ihm garantiert wurde.
Der Scheduler w¨
ahlt immer den Prozess, mit dem
berechneten kleinsten Verh¨
altnis e/z.
Beispiel
Prozess
A
B
C
erhaltene
Zeit e
14
11
20
versprochene
Zeit z
(14+11+20)/3=15
(14+11+20)/3=15
(14+11+20)/3=15
e/z
14/15=0,93
11/15=0,73
20/15=1,33
ausgew¨
ahlter
Prozess
X
179 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
Echtzeit-Systeme
Bei Echtzeitsystemen wird vom System garantiert, dass ein Prozess
innerhalb einer Zeitschranke abgeschlossen ist.
Der Scheduler w¨ahlt den Prozess, bei dem die Gefahr am
gr¨
ossten ist, dass die Zeitschranke nicht eingehalten werden
kann.
Beispiel
Prozess
A
B
C
zugesicherte
Zeitschranke
14
11
20
bisher erhaltene Zeit
10
9
15
Dauer bis Ablauf
der Zeitschranke
14-10=4
11-9=2
20-15=5
ausgew¨
ahlter
Prozess
X
180 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
Echtzeit-Systeme
Bei Echtzeitsystemen wird vom System garantiert, dass ein Prozess
innerhalb einer Zeitschranke abgeschlossen ist.
Der Scheduler w¨ahlt den Prozess, bei dem die Gefahr am
gr¨
ossten ist, dass die Zeitschranke nicht eingehalten werden
kann.
Beispiel
Prozess
A
B
C
zugesicherte
Zeitschranke
14
11
20
bisher erhaltene Zeit
10
9
15
Dauer bis Ablauf
der Zeitschranke
14-10=4
11-9=2
20-15=5
ausgew¨
ahlter
Prozess
X
180 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Garantiertes Scheduling
H¨orsaal¨ubung
1. Ein interaktives System sei geben durch:
Prozess
A
B
C
D
erhaltene
Zeit e
8
2
2
2
versprochene
Zeit z
e/z
ausgew¨
ahlter
Prozess
2. Ein Echtzeitsystem sei gegeben durch:
Prozess
A
B
C
D
zugesicherte
Zeitschranke
4
2
2
6
bisher erhaltend Zeit
1
1
1
2
Dauer bis Ablauf
der Zeitschranke
ausgew¨
ahlter
Prozess
In welcher Reihenfolge werden die Prozesse in beiden Systemen
ausgew¨ahlt (jeweils 5 Kontextwechsel, Quantum 1 Sekunde)?
181 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Zweistufiges Scheduling
Zweistufiges Scheduling
Die bisherigen Scheduling-Verfahren haben gemeinsam, dass alle
rechenbereiten Prozesse im Hauptspeicher ablaufen.
• Wenn nicht genug Hauptspeicher verf¨
ugbar ist, m¨
ussen einige dieser
Prozesse auf der Festplatte abgelegt werden.
• Der Aufwand f¨
ur einen Prozesswechsel ist aber h¨oher, wenn ein
Prozess zun¨achst in den Hauptspeicher zur¨
uckgeladen werden muss.
182 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Zweistufiges Scheduling
Ein zweistufiges Verfahren teilt die
rechenbereiten Prozesse in 2 disjunkte
Teilmengen:
• Prozesse im Hauptspeicher H
• Prozesse auf Platte (Sekund¨
arspeicher
S)
Es existieren zwei Scheduler:
• lokaler Scheduler w¨
ahlt stets einen
Prozess aus H
• periodisch lagert ein globaler Scheduler
Prozesse von H und S aus und ersetzt
sie.
183 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Zweistufiges Scheduling
Als Verfahren f¨
ur den lokalen Scheduler
kommt einer der vorherigen Algorithmen in
Frage.
Der globale Scheduler kann folgende
Kriterien zur Auswahl des Plattenspeicher
Prozesses, der ausgetauscht werden soll:
• Wie lange ist der Prozess schon in S?
• Wie groß ist der Prozess in S (es
passen mehrere kleine in den
Hauptspeicher)?
• Priorit¨
at des Prozesses in S?
184 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Fallbeispiel: Linux Scheduler
Die Beschreibung basiert auf dem Beitrag Der O(1)-Scheduler im Kernel
”
2.6“ von Timo H¨
onig im Linux-Magazin.
185 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Prozessverwaltung
• Linux verwaltet alle Prozessinformationen
mit Hilfe einer doppelt verketteten Liste der Taskliste.
• Die Listenelemente sind die
Prozessdeskriptoren ( task struct ) der
Prozesse.
• Der Deskriptor h¨
alt alle Informationen
seines Prozesses fest (im Wesentlichen,
das was man mit ps sieht).
186 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Den Zustand eines Prozesses speichert die Variable
Prozessdeskriptors.
Der Scheduler kennt insgesamt f¨
unf Zust¨ande:
state
des
1
TASK RUNNING kennzeichnet den Prozess als lauff¨
ahig.
Er muss auf kein Ereignis warten und kann daher vom Scheduler der
CPU zugeordnet werden. Alle Prozesse im Zustand
TASK RUNNING zieht der Scheduler f¨
ur die Ausf¨
uhrung in
Betracht.
2
TASK INTERRUPTIBLE kennzeichnet blockierte Prozesse.
Der Prozess wartet auf ein Ereignis. Ein Prozess im Zustand
TASK INTERRUPTIBLE wird u
¨ber zwei unterschiedliche Wege in
den Zustand TASK RUNNING versetzt:
1
2
Entweder tritt das Ereignis ein, auf das er gewartet hat,
oder der Prozess wird durch ein Signal aufgeweckt.
187 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
3
TASK UNINTERRUPTIBLE gleicht dem Zustand
TASK INTERRUPTIBLE, mit dem Unterschied, dass ein Signal den
Prozess nicht aufwecken kann.
Der Zustand TASK UNINTERRUPTIBLE wird nur verwendet, wenn
zu erwarten ist, dass das Ereignis, auf das der Prozess wartet, z¨
ugig
eintritt, oder wenn der Prozess ohne Unterbrechung warten soll.
4
Wurde ein Prozess beendet, dessen Elternprozess noch nicht den
Systemaufruf wait4() ausgef¨
uhrt hat, verbleibt er im Zustand
TASK ZOMBIE. So kann auch nach dem Beenden eines
Kindprozesses der Elternprozess noch auf seine Daten zugreifen.
Nachdem der Elternprozess wait4() aufgerufen hat, wird der
Kindprozess endg¨
ultig beendet, seine Datenstrukturen werden
gel¨
oscht. Endet ein Elternprozess vor seinen Kindprozessen,
bekommt jedes Kind einen neuen Elternprozess zugeordnet. Dieser
ist nunmehr daf¨
ur verant- wortlich, wait4() aufzurufen, sobald
der Kindprozess beendet wird. Ansonsten k¨
onnten die Kindprozesse
den Zustand TASK ZOMBIE nicht verlassen und w¨
urden als Leichen
im Hauptspeicher zur¨
uckbleiben.
188 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
5
Den Zustand TASK STOPPED
erreicht ein Prozess, wenn er beendet
wurde und nicht weiter ausf¨
uhrbar ist.
In diesen Zustand tritt der Prozess ein,
sobald er eines der Signale
SIGSTOP , SIGTST ,
SIGTTIN oder SIGTTOU erh¨alt.
189 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Entwicklungsziele f¨ur den Scheduler
Neben den allgemeinen Zielen (Auslastung der CPU, ...) waren hier
zus¨atzlich folgende Punkte maßgebend:
• gute SMP-Skalierung
• geringe Latenz auch bei hoher Systemlast
• faire Priorit¨
atenverteilung
• Komplexit¨
at der Ordnung O(1)
Alle Linux-Scheduler bisher besaßen eine Komplexit¨
at der Ordnung O(n): Die
Kosten f¨
ur das Scheduling wuchsen linear mit der Anzahl n der lauff¨
ahigen
Prozesse. Bei einem Kontextwechsel wird in einer verketteten Liste nach einem
Prozess gesucht, dessen Priorit¨
at am niedrigsten ist.
190 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Prozesspriorit¨aten
Die Prozesspriorit¨aten entscheiden, welchen lauff¨ahigen Prozess die CPU
beim n¨achsten Kontextwechsel zugeteilt bekommt - den mit der zum
Zeitpunkt des Kontextwechsels h¨
ochsten Priorit¨at. Die Priorit¨at eines
Prozesses ¨andert sich dabei dynamisch w¨ahrend seiner Laufzeit.
Es gibt zwei unterschiedliche Priorit¨aten:
• die statische Prozesspriorit¨
at, also die vom
nice -Wert bestimmte
static prio
Der Wertebereich des nice -Values reicht von -20 (dem h¨ochsten)
bis 19 (dem niedrigsten).
• die dynamische (effektive) Prozesspriorit¨
at ( prio ), die der
Scheduler aufgrund der Interaktivit¨
at eines Prozesses berechnet.
191 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Linux 2.6 kennt standardm¨aßig 140
Priorit¨atslevels.
• Hierbei entspricht null der h¨
ochsten
und 139 der niedrigsten Priorit¨at.
• Die Levels von eins bis 99 sind f¨
ur
Tasks mit Echtzeitpriorit¨at reserviert.
• Alle anderen Prozesse erhalten
zun¨achst gem¨aß ihres nice -Werts
eine Priorit¨at: Der nice -Wert (-20
bis 19) wird einfach in den Bereich ab
101 gemappt.
• W¨
ahrend des Ablaufs eines Prozesses
ver¨andert sich durch seinen
Interaktivit¨atsgrad aber seine Priorit¨at.
192 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Alle lauff¨ahigen Prozesse verwaltet der Scheduler in einer Run-Queue (pro
CPU). Sie ist die zentrale Datenstruktur, auf der der Scheduler arbeitet.
struct runqueue {
/* Spinlock um Run - Queue zu sch¨
u tzen */
spinlock_t lock ;
/* Zahl der lauff¨
a higen Prozesse */
unsigned long nr_running ;
/* Zahl der bisherigen Kontextw echsel */
unsigned long nr_switches ;
/* Zeitstempel des letzten Tauschs von active - und expired - Array */
unsigned long exp ire d _ t i m e s t a m p ;
/* Zahl der Prozess im Zustand T A S K _ U N I N T E R R U P T I B L E */
unsigned long n r_ un i n t e r r u p t i b l e ;
/* Verweis auf Pro ze s s d e s k r i p t o r des momentan ablaufenden Prozesses */
task_t * curr ;
/* Verweis auf Pro ze s s d e s k r i p t o r der Idle - Task */
task_t * idle ;
/* Verweis auf Memory Map des zuletzt ablaufenden Prozesses */
struct mm_struct * prev_mm ;
/* Verweise auf active - und expired - Array */
prio_array_t * active , * expired ;
/* Priority - Arrays */
prio_array_t arrays [2];
... }
193 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Neben Verweisen auf die gerade laufende Task, enth¨alt die Run-Queue
Verweise zu den zwei Priority-Arrays active und expired .
struct prio_array {
int nr_active ; /* Zahl der Prozesse */
unsigned long bitmap [ BITMAP_SIZE ]; /* Priorit¨
a t - Bitmap */
/* F¨
u r jede Priorit¨
a t eine Liste der Prozesse */
struct list_head queue [ MAX_PRIO ];
};
• Das
active -Array listet alle lauff¨
ahigen Prozesse, deren
Zeitscheibe noch nicht abgelaufen ist.
• Wenn die Zeitscheibe eines Prozesse abl¨
auft, verschiebt der
Scheduler den Eintrag vom active - in das zweite Array
expired .
• Beide, das active - und das expired -Array, f¨
uhren f¨
ur jede
Priorit¨at eine verkettete Liste der Prozesse mit entsprechender
Priorit¨at.
• Eine Bitmap h¨
alt fest, f¨
ur welche Priorit¨
at mindestens eine Task
existiert. Alle Bits werden bei der Initialisierung auf null gesetzt.
Beim Eintragen eines Prozesses in eines der beiden Priority-Arrays,
wechselt entsprechend der Priorit¨at des Prozesses das
korrespondierende Bit im Priorit¨at-Bitmap auf eins.
194 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
• Startet ein Prozess mit dem Nice null, setzt
der Scheduler das 120. Bit des Priorit¨at-Bitmaps im active -Array und reiht ihn in die
Prozessliste mit Priorit¨at 120 ein.
• Analog dazu l¨
oscht sich das entsprechende Bit
im Priorit¨at-Bitmap, sobald der Scheduler den
letzten Prozess einer gegebenen Priorit¨at aus
einem der beiden Priority-Arrays austr¨agt.
• Der Scheduler muss nur das erste gesetzte Bit
des Priorit¨at-Bitmaps finden (da Bitmap
konstante Gr¨
oße hat folgt O(1)). Anschließend
f¨
uhrt der Scheduler den ersten Prozess aus der
verketteten Liste dieser Priorit¨at aus. Prozesse
gleicher Priorit¨at bekommen die CPU
nacheinander in einem Ringverfahren (Round
Robin) zugeteilt.
195 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Prozess-Zeitscheiben und Neuberechnung der Priorit¨aten
Die Gr¨
oße der Zeitscheibe eines Prozesses ist von seiner Priorit¨
at
abh¨
angig:
• Prozesse mit hoher Priorit¨
at erhalten mehr CPU-Zeit als solche
mit niedriger.
• Die kleinste Zeitscheibe betr¨
agt 10, die l¨angste 200 Millisekunden.
Ein Prozess mit dem nice -Wert null erh¨alt die StandardZeitscheibe von 100 Millisekunden.
Ist die Zeitscheibe eines Prozesses aufgebraucht, muss der Scheduler
sie neu berechnen und den Prozess aus dem active - in das
expired -Array verschieben. Sobald active leer ist - alle
lauff¨ahigen Prozesse haben ihre Zeitscheibe aufgebraucht -, tauscht der
Scheduler einfach das active - gegen das expired -Array aus.
Effektiv wechseln nur die zwei Pointer der Run-Queue die Pl¨atze.
In Linux 2.4 werden die Zeitscheiben aller Prozesse auf einmal neu berechnet - immer dann, wenn alle Prozesse ihre Zeitscheiben
aufgebraucht haben. Mit steigender Prozesszahl dauert die Berechnung immer l¨
anger.
196 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Die dynamische Priorit¨
at errechnet der Scheduler aus der statischen
und der Prozessinter- aktivit¨
at. Gem¨aß seiner Interaktivit¨at erh¨alt ein
Prozess vom Scheduler entweder einen Bonus oder ein Penalty (Malus).
Interaktive Prozesse gewinnen u
unf
¨ber einen Bonus maximal f¨
Priorit¨atslevels hinzu, w¨ahrend jene Prozesse, die eine geringe
Interaktivit¨
at aufweisen, maximal f¨
unf Priorit¨atslevels durch ein Penalty
verlieren. Die dynamische Priorit¨at eines Prozesses mit einem
nice -Wert f¨
unf betr¨agt demnach im besten Fall null und im
schlechtesten zehn.
197 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Um den Grad der Interaktivit¨
at eines Prozesses zu bestimmen, muss
bekannt sein, ob der Prozess eher I/O-lastig oder eher CPU-intensiv ist.
Um Prozesse einer der beiden Kategorien zuordnen zu k¨onnen,
protokolliert der Kernel f¨
ur jeden Prozess, wie viel Zeit er mit
Schlafen verbringt, und wie lange er die CPU in Anspruch nimmt. Die
Variable sleep avg (Sleep Average) im Prozessdeskriptor speichert
daf¨
ur eine Entsprechung in dem Wertebereich von null und zehn
( MAX SLEEP AVG ).
L¨
auft ein Prozess, verringert seine sleep avg mit jedem
Timer-Tick ihren Wert. Sobald ein schlafender Prozess aufgeweckt wird
und in den Zustand TASK RUNNING wechselt, wird
sleep avg entsprechend seiner Schlafzeit erh¨
oht - maximal bis zu
MAX SLEEP AVG . Der Wert von sleep avg ist somit maßgebend,
ob ein Prozess I/O- oder Processor-Bound ist. Interaktive Prozesse haben
eine hohe sleep avg , minder interaktive eine niedrige.
198 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Mit der Funktion effective prio() berechnet der Scheduler die
dynamische Priorit¨at prio basierend auf der statischen
static prio und der Interaktivit¨at sleep avg des Prozesses. Zum
Berechnen der neuen Zeitscheibe greift der Scheduler auf die dynamische
Prozesspriorit¨at zur¨
uck. Dazu mappt er den Wert in den
Zeitscheibenbereich MIN TIMESLICE (Default: 10 Millisekunden) bis
MAX TIMESLICE (200 Millisekunden).
Interaktive Prozesse mit hohem Bonus und großer Zeitscheibe k¨onnen
ihre Priorit¨at jedoch nicht missbrauchen, um die CPU zu blockieren: Da
die Zeit, die der Prozess beim Ausf¨
uhren im Zustand
TASK RUNNING verbringt, in die Berechnung der
sleep avg -Variablen eingeht, verliert solch ein Prozess schnell seinen
Bonus und mit ihm seine hohe Priorit¨at und seine große Zeitscheibe.
Ein Prozess mit sehr hoher Interaktivit¨at erh¨alt nicht nur eine hohe
dynamische Priorit¨at und somit eine große Zeitscheibe: Der Scheduler
tr¨agt den Prozess nach Ablauf seiner Zeitscheibe auch wieder sofort in
das active -Array ein, statt wie gew¨
ohnlich ins expired -Array. Der
Prozess wird dadurch seiner Priorit¨at gem¨aß wieder zugeordnet und muss
nicht auf das Austauschen der Priority-Arrays warten.
199 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Kontextwechsel
Alle blockierten Prozesse werden in den so genannten Wait-Queues
verwaltet. Prozesse, die von TASK RUNNING in den Zustand
TASK INTERRUPTIBLE oder TASK
UNINTERRUPTIBLE wechseln, gelangen in diese Warteschlange.
Anschließend ruft der Kernel schedule() auf, damit ein anderer
Prozess die CPU erh¨alt.
Sobald das Ereignis eintritt, auf das der Prozess in einer Wait-Queue
wartet, wird er aufgeweckt, wechselt seinen Zustand in
uck, verl¨asst die Wait-Queue und betritt die
TASK RUNNING zur¨
Run-Queue. Falls der aufgewachte Prozess eine h¨
ohere Priorit¨at besitzt
als der gerade ablaufende, unterbricht der Scheduler den aktuell
laufenden Prozess zugunsten des eben aufgewachten.
200 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Kernel-Preemption
Anders als Kernel 2.4 ist der neue Linux-Kernel preemptiv: Kernelcode,
der gerade ausgef¨
uhrt wird, kann unterbrochen werden. Vor dem
Unterbrechen muss gew¨ahrleistet sein, dass sich der Kernel in einem
Zustand befindet, der eine Neuzuordnung der Prozesse zul¨asst.
Die Struktur thread info jedes Prozesses enth¨alt zu diesem Zweck den
Z¨ahler preempt count . Ist er null, ist der Kernel in einem sicheren
Zustand und darf unterbrochen werden. Die Funktion
preempt disable() erh¨
oht den Z¨ahler preempt count beim Setzten
eines so genannten Locks um eins; die Funktion
preempt enable() erniedrigt ihn um eins, sobald ein Lock aufgel¨ost
wird. Das Setzten des Locks (und damit das Verbot der
Kernel-Preemption) wird immer dann notwendig, wenn beispielsweise eine
von zwei Prozessen genutzte Variable vor konkurrierenden Zugriffen zu
sichern ist.
201 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Realtimef¨ahigkeit
F¨
ur Prozesse mit so Echtzeitpriorit¨at (Priorit¨at 1 bis 99) gibt es zwei
Strategien:
•
SCHED FIFO
ist ein einfacher First-in/First-out-Algorithmus, der ohne
Zeitscheiben arbeitet. Wird ein Echtzeitprozess mit
SCHED FIFO gestartet, l¨auft er so lange, bis er blockiert oder
freiwillig u
¨ber die Funktion sched yield() den Prozessor abgibt.
Alle anderen Prozesse mit einer niedrigeren Priorit¨at sind solange
blockiert und werden nicht ausgef¨
uhrt.
•
SCHED RR
verfolgt die gleiche Strategie wie
mit vorgegebenen Zeitscheiben.
SCHED FIFO , aber zus¨atzlich
Die CPU-Bed¨
urfnisse der Echtzeitprozesse gleicher Priorit¨at befriedigt der
Scheduler per Round-Robin. Prozesse mit einer niedrigeren Priorit¨at
kommen u
ur
¨berhaupt nicht zum Zuge. Der Scheduler vergibt f¨
Echtzeitprozesse keine dynamischen Priorit¨aten. Prozesse ohne
Echtzeitpriorit¨at f¨
uhrt er mit der Strategie SCHED OTHER aus.
202 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Realtimef¨ahigkeit
Die Echtzeit-Strategien von Linux garantieren jedoch keine
Antwortzeiten, was die Voraussetzung f¨
ur ein hartes
Echtzeit-Betriebssystem w¨
are.
Der Kernel stellt jedoch sicher, dass ein lauff¨ahiger Echtzeit-Prozess
immer die CPU bekommt, wenn er auf kein Ereignis warten muss, er
freiwillig die CPU abgibt und wenn kein lauff¨ahiger Echtzeitprozess
h¨
oherer Priorit¨at existiert.
203 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Leistungsvergleich O(n) vs O(1) Scheduler
Ben¨
otigte Zeit zur Interprozess-Kommunikation in Abh¨angigkeit von der
Anzahl beteiligter Prozesse auf einem Singleprozessor-System mit Kernel
2.4 (rot) und 2.6 (gr¨
un):
204 / 205
Betriebssysteme - Prozesse → alois.schuette@h-da.de Version: WS2014(967c57d)
Scheduling
Fallbeispiel: Linux Scheduler
Ben¨
otigte Zeit zur Interprozess-Kommunikation in Abh¨angigkeit von der
Anzahl beteiligter Prozesse auf Systemen mit ein, zwei, vier und acht
CPUs.
Es ist deutlich zu sehen, dass Linux 2.6 bei steigender Prozesszahl auf
allen vier Systemen ungleich besser skaliert als der alte Kernel.
205 / 205
Document
Kategorie
Technik
Seitenansichten
96
Dateigröße
5 788 KB
Tags
1/--Seiten
melden