Betriebssysteme

Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Betriebssysteme - Prozesse
→ [email protected]
Version: (8c45d65)
ARSnova 19226584
Alois Schütte
23. März 2016
1 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Inhaltsverzeichnis
Ein Prozess kann als die Abstraktion eines Programms, das von einem
Prozessor ausgeführt 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
5 Literatur
2 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozessmodell
1 Prozessmodell
Prozesszustände
Implementierung von Prozessen
Abstraktion des Prozessmodells in Java
2 Interprozesskommunikation
3 IPC Probleme
4 Scheduling
5 Literatur
3 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozessmodell
Um zu verstehen, wie unterschiedliche Aktivitäten scheinbar gleichzeitig
ablaufen, braucht man ein Modell eines sich in Ausführung befindenden
Programms.
Ein (sequentieller) Prozess ist ein sich in Ausführung befindendes
(sequentielles) Programm zusammen mit:
• dem aktuellen Wert des Programmzähler,
• den Registerinhalten,
• den Werten der Variablen und
• dem Zustand der geöffneten 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Sichtweisen
Beim Mehrprogrammbetrieb mit 4 Programmen (A-D) ergeben sich
damit folgende Sichtweisen:
5 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozess-Hierarchie
Ein Betriebssystem mit einen solchen Prozessmodell muss in der Lage
sein, dass von einem (Initial-) Programm andere Prozesse erzeugt werden
können.
• In Unix dient dazu der fork-Systemaufruf.
• Beim Hochfahren“ des Betriebssystems
werden” dann alle erforderlichen Prozesse
erzeugt für Systemdienste, wie
•
•
•
•
Scheduler,
Dateidienst,
Terminaldienst,
...
6 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozesskategorien und Ausführungsmodi
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-Funktionalität, um indirekt
auf Ressourcen zuzugreifen.
Heutige Prozessoren unterscheiden prinzipiell zwei Ausführungsmodi für
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
Auslösen eines Software Interrupts, d.h
• Inkrementieren des Programmzählers
• Umschalten in privilegierten Modus User
1
2
UserModus
3
Modus
3
Ausführen der Kernelfunktion
4
Speichern des Ergebnisses in Registern
5
Umschalten in Normalmodus
6
Zurückladen der Ergebnisse aus dem Register
7
Ausführen der nächsten Instruktion der
Anwendung
4
KernelModus
5
6
UserModus
7
8 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozesszustände
Prozesszustände
Eine Aufgabe des Betriebssystems ist das Multiplexen des physischen
Prozessors.
Diese Aufgabe übernimmt der Scheduler zusammen mit dem
Dispatcher.
Prozesse können sich in verschiedenen Zustände befinden.
1
rechnend (running)
der Prozessor ist dem Prozess zugeteilt
2
bereit (ready)
der Prozess ist ausführbar, aber ein anderer Prozess ist gerade
rechnend
3
blockiert (waiting)
der Prozess kann nicht ausgeführt werden, da er auf ein externes
Ereignis wartet (z.B. Benutzer hat Taste auf Tastatur gedrückt)
Diese Zuständen bilden eine Entscheidungsgrundlage für die Auswahl
eines geeigneten Kandidaten bei einem Prozesswechsel.
9 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozesszustände
Zustandsübergänge
1
2
Prozess wartet auf externes
Ereignis
Scheduler wählt anderen
Prozess aus, da die Zeitscheibe
des Prozesses abgelaufen ist
3
Scheduler wählt 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 Zustandsübergänge werden vom Dispatcher durchgeführt, die
Auswahl eines rechenbereiten Prozesses übernimmt der Scheduler.
10 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Prozesszustände
Modell für Prozesssystem
Damit ergibt sich ein Modell für 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 darüber und
haben einen sequentiellen Kontrollfluss.
• Somit gibt es stets einen Wechsel von Aktivitäten eines
(User-)Prozesses und des Kerns.
Prozesse
1
Kernel-Modus
2
3
...
n
User-Modus
Dispatcher / Scheduler
11 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Implementierung von Prozessen
Das o.g. Prozessmodell kann in einem Betriebssystem durch eine
Prozesstabelle, die für jeden Prozess einen Eintrag enthält, realisiert
werden.
Ein Eintrag muss alle Informationen enthalten, um einen Prozess wieder
anlaufen zu lassen, wenn er suspendiert wurde:
• Zustand,
• Programmzähler,
• Stack-Zeiger,
• belegten Speicher,
• Zustand der geöffneten 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 durchführt?
12 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 ausgelöst werden.
Dazu wird jeder Klasse von E/A-Geräten (Festplatten, Terminals, etc.)
ein Unterbrechungsvektor zugeordnet, der die Adresse einer
Unterbrechungsbehandlungsprozedur (Interrupt Routine) enthält.
Wenn z.B. ein Terminal eine Unterbrechung auslöst, dann wird
hardwareseitig (Microcode) folgendes getan:
1 Programmzähler des aktuell laufender Prozess und einiger Register
auf Stack legen
2 Aufruf der entsprechenden Unterbrechungsbehandlungsprozedur
Alle anderen Aktivitäten (Auswahl des nächsten Prozesses, der nach der
Unterbrechungsroutine laufen soll) muss durch die Betriebssystemsoftware erfolgen.
13 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Dämonen
In Unix werden Verwaltungsaufgaben von speziellen Programmen, die als
Hintergrundprozesse ablaufen, übernommen.
Beispiele sind:
cron Systemcronometer
at Ausführen eines Kommandos zu einer vorgegebenen Zeit
inetd Internet Service Dämon
sshd Secure Shell Dämon
Solche Prozesse werden oft beim Hochfahren des Betriebssystems
gestartet und erst beim Shutdown des Systems beendet.
Auf Shellebene kann man sich Dämonen ansehen durch das
ps-Kommando. Sie sind daran zu erkennen, dass die Spalte TTY“ ein
”
Fragezeichen ?“ enthält.
”
$ ps - el | grep \?
1277 ?
00:02:22 crond
1291 ?
00:00:00 atd
1578 ?
00:00:03 sshd
30045 ?
00:03:41 sendmail
14 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Diese Prozesse sind als Dämonen realisiert:
• Jeder Prozess (außer init) in Unix hat einen Vater und gehört zu
einer Prozessgruppe.
• Jede Prozessgruppe hat einen Prozess als Prozessgruppenleiter
und besitzt maximal ein Kontrollterminal. Das Kontrollterminal
liefert für alle Mitglieder der Prozessgruppe die Standardeinstellungen von stdin, stdout und stderr. Das Kontrollterminal
lässt sich immer unter dem Namen /dev/tty“ ansprechen.
”
• Ein Signal des Kontrollterminals wird an alle Mitglieder der
Prozessgruppe gesendet (die Shell schützt sich und alle von ihr
initiierten Prozesse allerdings davor).
• Prozesse, die zwar Mitglieder einer Prozessgruppe sind, aber kein
Kontrollterminal haben, nennt man Dämonen.
• Da sie kein Kontrollterminal besitzen, sind sie nicht über
Signale abzubrechen.
• Diese Dämonen treiben ihr Unwesen im Bauch der Maschine“.
”
15 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Zur Implementierung von Dämonen sollen folgende Regeln eingehalten
werden:
• Zunächst sollte ein fork ausgeführt werden, der Elternprozess sollte
danach ein exit ausführen. Dadurch wird folgendes erreicht:
1
2
Wird der Prozess von der Shell gestartet, so denkt die Shell, der
Prozess wäre 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 Prozessgruppenführer ist.
• Der nächste Schritt ist, den Systemaufruf setsid()“ auszuführen.
”
Dadurch wird eine neue Session erzeugt und der Aufrufer wird
Prozessgruppenführer.
• 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 führt, dass das Betriebssystem nicht heruntergefahren werden
kann.
• Die Maske zum Dateierzeugen (umask) wird auf 0 gesetzt, damit
nicht geerbte Maske vom Aufrufer dazu führt, dass der Dämon
Dateien nicht anlegen kann.
• Letztlich sollten alle nicht benötigten Filedeskriptoren geschlossen
16 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Beispiel Dämon
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Dämonen
$ ./ 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 Dämon kann man mit ps –xl“ sehen, dass der Dämon
”
aktiv ist und als Vater und den Prozess 1 besitzt.
Ein Problem bei Dämonen ist, dass es nicht möglich ist, stderr und
stdout zu verwenden. Also muss man eine Methode entwickeln, wie ein
Dämon die Aktivitäten protokollieren kann. In Unix existiert das syslog
Werkzeug, um Nachrichten geordnet zu verarbeiten.
18 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Implementierung von Prozessen
Zombies
Ein Prozess terminiert und hört 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 für ihn
ausgeführt hat, erhält einen besonderen Zustand, er wird ein Zombie:
• Der Prozess wird vom Scheduler nicht mehr berücksichtigt, 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
exit (0);
}
}
while (1) {
// father performs something
}
return 0;
}
23 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Abstraktion des Prozessmodells in Java
Abstraktion des Prozessmodells in Java
Um Eigenschaften und Probleme mit Prozessen zeigen zu können, 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 zunächst gezeigt, wie in Java Threads erzeugt werden
können.
24 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Abstraktion des Prozessmodells in Java
Erzeugen und Starten vonJava-Threads
Beim Start eines Java Programms wird ein Prozess erzeugt, der einen
Thread enthält, der die Methode main der angegebenen Klasse ausführt.
Der Code weiterer Threads muss in einer Methode mit Namen run
realisiert werden.
public void run () {
// Code wird in eigenem Thread ausgeführt
}
Ein Programm, das Threads erzeugt, erbt von der Klasse Thread und
überschreibt die Methode run() (auf Interfaces wird später eingegangen):
25 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 zunächst ein Thread
erzeugt (new ...), dann durch start die Methode run aufgerufen und
somit Hello World“ ausgegeben.
”
26 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Abstraktion des Prozessmodells in Java
mehrere Threads
Werden mehrere Thread erzeugt, so ist die Ausführungsreihenfolge 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
zusätzlich von Thread abgeleitet werden (Java unterstützt 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Dämon 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 könnte 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Abstraktion des Prozessmodells in Java
zum Üben für zu Hause
1
Testen des Verhaltens, wenn NUMBER OF SERVERS mit 1, 10,
100, 1.000, 10.000 und 100.00 gesetzt wird und Erklärung des
Ergebnisses.
2
Ändern der Metode run() und Test und Erklärung der Auswirkung
gegenüber 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Prozessmodell
Abstraktion des Prozessmodells in Java
Beenden von Threads per Programm
Die Klasse Thread besitzt die Methode stop(), 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 (später) ausführt und den Zustand eines
Objektes verändert und dies aber nicht bis zum Schluss durchführen
kann (wegen Stop()).
• 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 später nochmals darauf zurückkommen.
37 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Interprozesskommunikation
1 Prozessmodell
2 Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Kritischer Bereich
Lösungsansätze in Java
Semaphore
Monitore und andere Primitive
CSP - Communication Sequential Processes
Nachrichtenaustausch
3 IPC Probleme
4 Scheduling
5 Literatur
38 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Interprozesskommunikation
Betriebssysteme stellen unterschiedliche Mechanismen zur Verfügung, mit
denen zwei Prozesse kommunizieren können:
• beide Prozesse können sich den Arbeitsspeicher teilen, oder
• gemeinsamer Speicher ist nicht verfügbar, es werden externe Medien,
wie Dateien verwendet, auf die gemeinsam zugegriffen werden kann.
Die Probleme sind aber unabhängig davon, welcher der beiden
Mechanismen verwendet wird. Im folgenden werden die Probleme und
Lösungen für den Zugriff auf gemeinsam verwendete Ressourcen gezeigt.
39 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Probleme des gemeinsamen Zugriffs
Wenn mehrere Threads in Java gemeinsam auf Daten zugreifen, müssen
sich die einzelnen Threads verständigen“, wer wann was machen darf.
”
Dazu werden die Möglichkeiten, die Java bietet, am Beispiel von
Buchungen eines Bankkontos gezeigt.
Eine Bank wird modelliert durch 4 Klassen:
Die Klasse Konto repräsentiert 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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) für die Bank arbeiten können 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 müller =
new BankAngestel l te ( " Andrea Müller " , sparkasse );
B ankAngestellte schmitt =
new BankAngestel l te ( " Petra Schmitt " , sparkasse );
}
}
←
←
sparkasse ist das gemeinsam verwendete Objekt !
43 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
verlorene Buchungen
Bei dieser Bank können 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Verdeutlichung
Gehen wir von folgender Situation aus:
• Andrea Müller bucht -100 EUR auf Konto 47, es sollen also 100
EUR abgebucht werden. Der Kontostand sein 0.
• Petra Schmitt führt auch Buchungen für Konto 47 aus, es sollen
1000 EUR gutgeschrieben werden.
Thread Andrea Müller:
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 Müller
alterStand=0
neuerStand=1000
Konten[47]=1000
45 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Probleme des gemeinsamen Zugriffs
Verdeutlichung
Thread Andrea Müller:
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Abläufe (wie das Buchen des selben Kontos)
können vermieden werden, wenn sich zu keinem Zeitpunkt zwei
Prozesse in ihrem kritischen Bereich befinden.
Im folgenden werden Lösungsversuche (nicht korrekte) diskutiert.
47 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Kritischer Bereich
Lösungsversuch 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 möglich
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Kritischer Bereich
Lösungsversuch 1
Dies ist keine Lösung, 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 führt also 3 Anweisungen aus, wobei dann auch wieder
dazwischen umgeschaltet werden kann.
49 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Kritischer Bereich
Lösungsversuch 2 (Sperrvariable)
Die Idee ist die Verwendung von Sperrvariablen:
• Zu einem Zeitpunkt darf nur eine Angestellte eine Buchung
ausführen.
• Erst wenn die Buchung abgeschlossen ist, darf eine andere
Angestellte buchen.
Dies ist offensichtlich eine korrekte Lösung: 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 geändert.
50 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 können nur ausgeführt werden, falls die
Bank momentan nicht gesperrt ist. Ist die Bank gesperrt, wartet der
Thread, bis sie durch den sperrenden Thread wieder entsperrt wird.
Wie bewerten Sie diese Lösung ?
51 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Kritischer Bereich
Diese Realisierung ist auf den ersten Blick korrekt; es gibt aber folgende
Probleme:
1
Paralleles Arbeiten wird unmöglich: parallel könnten
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 Lösung in Java zu programmieren, sind in Java
Sprachelemente zur Synchronisation verfügbar.
52 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Lösungsansätze in Java
Die erste korrekte (aber ineffiziente) Lösung für die Probleme 2 (aktives
Warten) und 3 (verlorene Buchungen) nutzt die Möglichkeit von Java,
Methoden als synchronized zu kennzeichnen.
Dazu wird einfach die Klasse buchen mit dem Attribut synchronized
versehen – ansonsten ändert 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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
eine Exception).
54 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
acquire release Protokoll
• Wird eine Methode einer Klasse mit
synchronized gekennzeichnet, so muss diese
Sperre zuerst gesetzt werden, bevor die
Methode ausgeführt wird, hier versucht von
Thread B.
• Hat ein anderer Thread A die Sperre bereits
gesetzt (seine Methode ist in Ausführung), 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
berücksichtigt.
Sperre
Object
• Wenn die Methode des Thread A beendet ist,
wird die Sperre entfernt und der Thread B
wird wieder beim Scheduling wieder
berücksichtigt.
55 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Somit ist das Problem 2 und 3 gelöst. Diese Lösung 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,
Blöcke 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 Schlüsselwort synchronized versehen
und das Objekt, auf das sich die Sperre bezieht wird danach angegeben.
56 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Verwendung von synchronized
Wenn alle Threads nur lesend auf ein Objekt zugreifen, ist keine
Synchronisation erforderlich – hier würde durch synchronized ein
unnötiger Rechenaufwand erzeugt werden (Setzen und Lösen der Sperre).
Generell gilt folgende Regel:
Wenn von mehreren Threads auf ein Objekt zugegriffen
wird, wobei mindestens ein Thread den Zustand
(repräsentiert durch die Werte der Attribute) des Objekts
ändert, dann müssen alle Methoden, die auf den Zustand
lesend oder schreibend zugreifen, mit synchronized
gekennzeichnet werden.
57 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Petrinetz für 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Petrinetz für 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 höchstens ein
Thread eine der synchronized Methoden auf
ein Objekt anwenden.
59 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Test, ob eine Sperre gesetzt ist
Der Test, ob eine Sperre gesetzt ist, ist durch holdsLock möglich:
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Hörsaalübung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
→ Hörsaalübung
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 abzuändern, so dass die Ausgabe der
Intuition der Verwendung der Klasse Even entspricht?
62 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait und notify
Werden Objekte von mehreren Threads benutzt und dabei deren
Zustände verändert, dann gewährleisten synchronized-Methoden, dass ein
Thread immer einen konsistenten Zustand eines Objektes vorfindet.
In vielen Anwendungssituationen ist es erforderlich, dass eine Methode
nur dann ausgeführt wird,
• wenn zusätzlich zum konsistenten Zustand
• weitere anwendungsspezifische Bedingungen erfüllt sind.
63 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Beispiel Parkhaus
Ein Parkhaus wird modelliert, indem der Zustand durch die aktuell noch
freie Parkplätze beschrieben wird und Autos durch Threads mit
Methoden Einfahren (enter()) und Ausfahren (leave()) realisiert sind.
• Beim Einfahren vermindert sich die Anzahl der freien Plätze um 1;
beim Ausfahren eines Autos wird sie um 1 erhöht.
• Die freien Plätze können nicht erhöht werden, wenn das Parkhaus
voll ist (freie Plätze == 0).
• Da ein Parkhaus von mehreren Autos (Threads) benutzt wird und
der Zustand (=freie Plätze) durch ein Auto verändert wird, müssen
die Methoden enter() und leave() synchronized sein.
Zunächst werden zwei vergebliche Versuche, das Problem freie Plätze“
”
zu lösen gezeigt, dann eine korrekte Implementierung.
64 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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
← aktives Warten
leave () { // leave parking garage
Diese Lösung hat zwei Probleme:
1 Aktives Warten führt zu schlechter Performance.
65 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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
← aktives Warten
leave () { // leave parking garage
Diese Lösung hat zwei Probleme:
1 Aktives Warten führt zu schlechter Performance.
2 Die Lösung 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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
← aktives Warten
leave () { // leave parking garage
Diese Lösung hat zwei Probleme:
1 Aktives Warten führt zu schlechter Performance.
2 Die Lösung 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Korrekte Lösung 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 gelöst 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 müssen auf ein Objekt angewendet werden, das
durch synchronized gesperrt ist, ansonsten tritt die Ausnahme
IllegalMonitorStateException“ auf.
”
66 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 fügt den laufenden Thread in eine Menge (Waitingset)
ein, die mit dem Objekt assoziiert ist.
4
Der synchronization Lock für das Objekt wird freigegeben (released),
alle anderen Locks bleiben erhalten.
67 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
Ein notify bewirkt die folgenden Aktionen:
1
Ein zufälliger Thread t wird aus dem Waitingset des Objektes
ausgewählt.
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 hält, ihn freigegeben hat.
3
t wird nach erhalten des Lock nach seinem wait weitermachen.
Ein notifyAll arbeitet genauso, nur dass alle Threads im Waitingset
ausgewählt werden (Achtung: nur einer kann aber weitermachen, da die
anderen ja auf den Erhalt des Lock warten. sind.
68 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
69 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
70 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
71 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
72 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
wait, notify, notifyAll
73 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Parkhaus mit korrekter Lösung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Parkhaus mit korrekter Lösung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Parkhaus mit korrekter Lösung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 Lösung müsste 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 ausgewählt wird. Es
könnte ein anderer Thread, der gerade einfahren will ausgewählt werden,
der dann den freien Platz belegt.
Dies entspricht in der Realität dem Tatbestand, dass ein Auto vor dem
Einlass steht und von einem anderen dahinter stehenden Wartenden
überholt wird, der dann in die letzte Parklücke einfährt.
78 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Die Stelle checkCond1“ entspricht der Überprüfung 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 können 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
”
zusätzlich die Transition wakeup1“ schalten. Dadurch entsteht zwischen
”
wakeup1“ und notify2“ ein Konflikt. Durch Zuweisen einer höheren Priorität
”
”
an wakeup1“ erreicht man, dass nur die Transition wackup1“ schaltet. Die
”
”
Transition notify2“ soll nämlich 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Unkorrekte Lösung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Ein Lauf des Programms kann folgende Ausgabe bewirken (das hängt
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Ein Lauf des Programms kann folgende Ausgabe bewirken (das hängt
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
1
Alle Verbraucher c1, c2 und c3 können laufen. Da der Puffer
anfänglich 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
1
Alle Verbraucher c1, c2 und c3 können laufen. Da der Puffer
anfänglich 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
3
p1 läuft 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 für p3:
92 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
3
p1 läuft 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 für p3:
92 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
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 Lösung des Problems kann nun darin bestehen, dass nicht ein
Thread, sondern alle Thread geweckt werden. Da nur einer ausgewählt
wird und jeder in einer while-Schleife prüft, ob er arbeiten kann, wird das
funktionieren.
94 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Erklärung
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 Lösung des Problems kann nun darin bestehen, dass nicht ein
Thread, sondern alle Thread geweckt werden. Da nur einer ausgewählt
wird und jeder in einer while-Schleife prüft, ob er arbeiten kann, wird das
funktionieren.
94 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Korrekte Lösung 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 Lösung 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze in Java
Regel für notifyAll
Prinzipiell kann man immer notify() durch notifyAll() ersetzen, die
Umkehrung allerdings wäre 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 Veränderung des Zustands eines Objekts können mehrere
Threads weiterlaufen (Wert im Puffer - alle wartenden Verbraucher
können arbeiten).
96 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Lösungsansätze 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 grösser Null bedeutet, dass Wecksignale zu
berücksichtigen sind.
• Als Operationen wurde definiert DOWN“ (=p) und UP“ (=v).
”
”
• Down“ prüft, ob der Semaphore größ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 während der Ausführung der Operation
kein anderer Thread auf den Semaphore zugreifen kann.
98 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Gegenseitiger Ausschluss mit Semaphoren
Gegenseitiger Ausschluss bezeichnet eine Situation, in der ein bestimmtes
Programmstück zu einer Zeit von höchstens einem Thread
ausgeführt 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 Programmstück, das von
höchstens einem Thread betreten werden darf.
100 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Gegenseitiger Ausschluss mit Semaphoren
Im folgenden Beispiel werden die Aktionen, die ein Thread im kritischen
Abschnitt ausführt simuliert durch eine Sleep-Operation. In einer realen
Anwendung würde hier das Codefragment stehen, das auf die
gemeinsamen Objekte zugreift.
Der kritische Abschnitt wird durch Semaphore geschützt, indem
1
vor Betreten die Semaphor-Methode down(),
2
danach die Methode up()
aufgerufen wird.
101 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Frage
Was passiert durch Aufruf von
$ java MutualExclusion 0
105 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Hörsaalübung
Ändern 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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, führen gewisse Aktionen aus und müssen dann
warten, bis andere Threads Aktivitäten abgeschlossen haben.
Insgesamt lassen sich solche Abhängigkeiten durch einen Graphen
darstellen:
1 Knoten sind Threads,
2 eine Kante existiert von einem Thread T1 zu T2, falls T1 seine
Aktivitäten beendet haben muss, bevor T2 starten kann.
Das folgende Beispiel demonstriert eine solche Situation.
107 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Die Umsetzung in Java erfolgt durch Semaphore:
• Für jede Abhängigkeit (Kante im Graph) wird
eine Semaphore verwendet. Die Semaphoren
sind in einem Array sems zusammengefasst, so
dass die nebenstehend gezeigten
Abhängigkeiten definiert sind.
• Bevor eine Aktion ausgeführt wird, wird die
p()-Methode für alle Semaphoren, die den
eingehenden Kanten entsprechen, ausgeführt;
• 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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Aus Sicht des Threads i werden folgende Aktionen ausgeführt:
1
i führt p()-Operation aus: Warten auf v-Operation von i-1
2
i-1 hat v()-Operation ausgeführt: i kann Aktion ausführen
3
i führt v-Operation aus: i+1 kann aktiv werden
109 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Die Methoden p() und v() haben ein Integerargument, das angibt, um
welchen Wert erniedrigt bzw. erhöht werden soll.
Dieses Argument muss positiv sein, ansonsten könnte z.B. eine pOperation die Semaphore erhöhen.
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 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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. Würde notify()
verwendet werden, könnten u.U. mehrere Threads weiterlaufen.
118 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erhöht 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 führen p(3) aus.
• T1 wird ausgewählt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
119 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erhöht 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 führen p(3) aus.
• T1 wird ausgewählt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
• falsche Vorgehensweise:
• T1 und T2 führen jeweils p(1); p(1); p(1); aus.
• T1 wird ausgewählt und (p(1); p(1);) ist abgeschlossen (Semaphor
== 2), dann wird auf T2 umgeschaltet.
• T2 führt (p(1); p(1);) nun blockiert beim Aufruf p(1);
• T1 blockiert beim Aufruf p(1) → Verklemmung
119 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Der Programmcode zeigt, dass eine additive Semaphore auf einen
”
Schlag“ erhöht 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 führen p(3) aus.
• T1 wird ausgewählt und p(3) ist abgeschlossen. T2 blockiert beim
Aufruf P(3).
• falsche Vorgehensweise:
• T1 und T2 führen jeweils p(1); p(1); p(1); aus.
• T1 wird ausgewählt und (p(1); p(1);) ist abgeschlossen (Semaphor
== 2), dann wird auf T2 umgeschaltet.
• T2 führt (p(1); p(1);) nun blockiert beim Aufruf p(1);
• T1 blockiert beim Aufruf p(1) → Verklemmung
119 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Semaphorgruppen
Eine Semaphorgruppe ist eine Verallgemeinerung einer additiven
Semaphore:
• Ein Aufruf der Methode change() erhöht oder erniedrigt eine
Menge von Semaphoren, die zur selben Gruppe gehören.
• Die Änderungen werden nur durchgeführt, wenn alle Semaphoren
der Gruppe nicht durch die Änderung negativ werden; in diesem
Fall wird gewartet ohne dass eine Änderung vollzogen wird.
120 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Semaphore
Die Realisierung der Klasse SemaphoreGroup verwendet ein Integerarray
(values) zur Darstellung der Semaphorwerte. Die Umsetzung mit
mehreren Objekten vom Typ AdditiveSemaphore würde zu
Verklemmungssituationen führen.
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 öffentliche Methode changeValues() zur Änderung von Werten.
121 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 verändert werden soll: deltas[i] gibt an, wie values[i]
geändert werden soll; delta[i] kann positiv oder negativ sein.
122 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Änderungen durchführbar
sind oder nicht.
Die private Methode doChange führt die Änderungen durch. Danach werden in
changeValues() alle wartenden Thread informiert (notifyAll()).
Die öffentliche Methode getNumberOfMembers() dient zum Abfragen der
Größe der Semaphorgruppe.
Das Applet semgrp.html verdeutlicht den Gebrauch von Semaphorgruppen.
123 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Monitore und andere Primitive
Monitore und andere Primitive
Semaphore in ihren unterschiedlichen Ausprägungen 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 führten 1974 Pfadausdrucke ein.
• Atkinson und Hewitt diskutierten 1979 Serializer.
124 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
CSP - Communication Sequential Processes
• Communicating Sequential Processes ist eine von C.A.R. Hoare an
der Universität Oxford entwickelte Prozessalgebra zur Beschreibung
von Interaktion zwischen kommunizierenden Prozessen.
• CSP war Ausgangspunkt zur Entwicklung der Programmiersprache
Occam (vgl. CSP).
• CSP bildet die Grundlage für das Co-Routinen Konzept der
Programmiersprache go.
125 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - Das erste Programm
• Die Programmiersprache go ist von google als Sprache zur
Systemprogrammierung entworfen worden. (vgl. go).
• Wir werden go mit dem go-Routinen und Channel-Konzept
betrachten.
hello.go
1
package main
3
import " fmt "
5
func main () {
fmt . Println ( " Hello , world " )
}
6
7
126 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - goroutinen
g1.go
1
2
4
5
6
7
8
10
11
package main
import " fmt "
func f ( n int ) {
for i := 0; i < 10; i ++ {
fmt . Println (n , " : " , i )
}
}
func main () {
go f (0)
var input string
fmt . Scanln (& input )
13
14
15
←
}
2 go Routinen
• main
• go f(0)
127 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - goroutinen
g3.go
1
...
3
func f ( n int ) {
for i := 0; i < 10; i ++ {
fmt . Println (n , " : " , i )
amt := time . Duration ( rand . Intn (250))
time . Sleep ( time . Millisecond * amt )
}
}
4
5
6
7
8
9
11
12
13
14
func main () {
for i := 0; i < 10; i ++ {
go f ( i )
}
←
var input string
fmt . Scanln (& input )
16
17
18
←
}
• go run g3.go: Die Ausgabe ist nicht vorhersehbar - warum ?
• Wir benötigen Synchronisationskonzepte
128 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - channel
• Channel sind Kommunikationsmittel, mit denen goroutinen
Nachrichten austauschen können und sich dabei synchronisieren.
• Channel haben eine Typ und mit dem Operator ’< −’ können Werte
gesendet und empfangen werden.
g4.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func producer ( c chan int ) {
←
for i := 0; i <10; i ++ {
c <- i
←
}
}
func consumer ( c chan int ) {
←
for {
msg := <-c
←
fmt . Println ( msg )
time . Sleep ( time . Second * 1)
}
}
func main () {
var c chan int = make ( chan int )
go consumer ( c )
go producer ( c )
var input string
fmt . Scanln (& input )
}
←
129 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - channel
• Ein Sender kann einen Kanal schließen, um anzuzeigen, dass keine
Werte mehr gesendet werden
• Ein Empfänger kann testen, ob der Kanal noch offen ist:
’v, ok := <-ch’
g5.go
1
2
3
4
5
6
7
8
10
11
12
13
14
15
16
func fibonacci ( n int , c chan int ) {
x , y := 0 , 1
for i := 0; i < n ; i ++ {
c <- x
x, y = y, x+y
}
close ( c )
←
}
func main () {
c := make ( chan int , 5)
go fibonacci ( cap ( c ) , c )
for i := range c {
fmt . Println ( i )
}
}
←
←
130 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - select
• Ein select ermöglicht es, dass auf Kommunikation über mehrere
Kanäle reagiert wird.
• Ein select blockiert, bis auf einem seiner Kanäle Kommunikation
möglich ist. Bei gleichzeitigem Eintreffen wird zufällig ein Kanal
gewählt.
131 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
CSP - Communication Sequential Processes
go - select
g6.go
1
2
3
4
5
6
7
8
9
10
11
12
14
15
16
17
18
19
20
21
22
23
24
func fibonacci (c , quit chan int ) {
2 Kanäle
x , y := 0 , 1
for {
select {
case c <- x :
x, y = y, x+y
case <- quit :
fmt . Println ( " quit " )
return
}
}
}
func main () {
c := make ( chan int )
quit := make ( chan int )
go func () {
for i := 0; i < 10; i ++ {
fmt . Println ( < - c )
}
quit <- 0
}()
fibonacci (c , quit )
}
←
←
←
←
←
←
←
←
132 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 (Empfänger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empfänger wartet, bis er eine Nachricht erhalten hat.
133 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 (Empfänger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empfänger wartet, bis er eine Nachricht erhalten hat.
Als Kommunikationsprimitive sind erforderlich:
• send(destination, &message) und
• receive(source, &message).
133 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 (Empfänger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empfänger 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.
133 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 (Empfänger) eine
Nachricht sendet.
• Beide Prozesse synchronisieren sich automatisch, indem der
Empfänger 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.
133 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Nachrichtenaustausch
Zunächst wird ein Puffer mit n Elemente definiert, der es erlaubt, Daten
fester Grösse zwischen Sender und Empfänger auszutauschen.
Dann wird gezeigt, wie Daten beliebiger Länger transferiert werden
können.
134 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Puffer mit n Elementen
• Der Erzeuger fügt 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 Lösung?
135 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Puffer mit n Elementen
Das Reorganisieren kann vermieden
werden, wenn der Puffer zyklisch
organisiert wird:
136 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
}
137 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 erforderlich, da wir notifyAll() verwenden müssen. Wenn eine
freie Position vorhanden ist, wird der Wert gespeichert und die Variable
tail“ zyklisch inkrementiert, danach wird ein wartender Thread geweckt.
”
138 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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.
139 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
Nun wird gezeigt, wie Daten beliebiger Länge ausgetauscht werden
können.
Dabei muss die Nachrichtengrenze bewahrt bleiben, d.h. wird z.B.
Byte-Array gesendet so wird exakt diese Menge an Daten empfangen:
140 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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.
141 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Message Queues
MessageQueue.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
}
142 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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.
143 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Pipes
Message Queues bewahren die Nachrichtengrenzen; deshalb wird diese
Art der Kommunikation auch nachrichtenorientiert“ genannt.
”
Demgegenüber ist es für den Empfänger einer Nachricht bei
streamorientierten“ Kommunkation nicht möglich, die einzelnen
”
Nachrichten zu unterscheiden, die an der Kommunikation beteiligt
sind.
Diese Verhalten verdeutlicht die Kommunikation über Pipes (mit einem
Byte-Array fester Grösse)
→ pipe
144 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
}
145 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Die send()-Operation, die Daten in eine Pipe schreibt, muss als atomare
Operation realisiert werden: wenn die Nachricht grösser ist, als der noch
verfügbar freie Platz in der Pipe, muss der Sender blockieren, bis ein
Empfänger 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 {
...
146 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Wenn die gesamte Länge der Nachricht grösser ist, als die Kapazität der
Pipe, so wird die Nachricht in kleine Stücke geteilt und jeweils nur ein
Stück 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 ();
}
}
}
147 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Interprozesskommunikation
Nachrichtenaustausch
Beim Empfang einer Nachricht, muss blockiert werden, bis Daten in der
Pipe verfügbar sind. Ein Parameter beim receive() gibt die erwartete
Grösse der Nachricht an; wenn weniger Daten in der Pipe sind, wird nicht
blockiert, sondern nur der verfügbare 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
}
148 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
IPC Problem
1 Prozessmodell
2 Interprozesskommunikation
3 IPC Probleme
Problem speisender Philosophen
Lese-Schreiber Problem
Das Problem des schlafenden Friseurs
4 Scheduling
5 Literatur
149 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Problem speisender Philosophen
Problem speisender Philosophen (Dijkstra, 1965)
• Fünf 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 können, 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 für einen Philosophen zu finden, das, auf
alle Philosophen angewendet, nie dazu führt, dass einer der
Philosophen verhungert.
150 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Problem speisender Philosophen
Dieses Problem ist typisch für Betriebssysteme: es verdeutlicht den
Wettbewerb um eine begrenzte Anzahl von exklusiv nutzbaren
Betriebsmitteln, wie CPU oder E/A Geräte.
Eine offensichtliche (aber nicht korrekte) Lösung 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
Lösung?
151 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Lösung funktioniert nicht, wenn z.B. alle Philosophen gleichzeitig die
linke Gabel nehmen, da niemand die rechte Gabel nehmen kann und so
alle verhungern (Deadlock).
152 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Problem speisender Philosophen
Mit dem synchronized-Konzept von Java ist eine Lösung 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
153 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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
154 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 ) { }
}
155 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Lösung, die Semaphorgruppen verwendet, um die Operation
atomar zu machen.
Ein Applet verdeutlicht dies.
156 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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.
157 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Lösung dazu verwendet eine
Semaphore db, um den Zugriff auf die
Datenbank zu synchronisieren.
•
•
•
•
Der erste Leser (reader) ruft
für den Zugriff auf den
Datenbestand die Methode
down() mit der Semaphore
db“ auf,
”
nachfolgende Leser erhöhen
lediglich den Zähler rc“.
”
Wenn Leser den kritischen
Bereich verlassen, erniedrigen
sie den Zähler und
der letzte Leser ruft up() für
die Semaphore auf und weckt
einen potentiellen Schreiber.
Lösung in Java? → Übung
158 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Das Problem des schlafenden Friseurs
Das Problem des schlafenden Friseurs
In einem Friseursalon mit einem Friseurstuhl und n
Stühlen für wartende Kunden arbeitet ein Friseur.
• Falls kein Kunde die Haare geschnitten haben
möchte (also alle Stühle leer sind), setzt sich
der Friseur auf den Friseurstuhl und schläft.
• Ein eintreffender Kunde muss den Friseur
wecken, um die Haare geschnitten zu
bekommen.
• Während der Friseur Haare schneidet, müssen
weitere Kunden entweder Platz nehmen und
warten, bis der Friseur frei ist oder später
nochmal kommen (falls alle Stühle besetzt
sind).
Quelle: ’Moderne BS’,
Tannenbaum
Lösung mit Semaphoren oder Java Synchronisation als Übung.
159 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Das Problem des schlafenden Friseurs
Lösungsidee
Mittels Semaphore kann man das Problem lösen:
customers Anzahl der Wartenden Kunden
barbers Anzahl schlafender Frisöre
mutex für den Schutz der Zählvariablen für 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
160 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
IPC Probleme
Das Problem des schlafenden Friseurs
Frisör, 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
}
161 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling
1 Prozessmodell
2 Interprozesskommunikation
3 IPC Probleme
4 Scheduling
Round-Robin Scheduling
Scheduling mit Prioritäten
Shortest-Job-First
Garantiertes Scheduling
Zweistufiges Scheduling
Fallbeispiel: Linux Scheduler
5 Literatur
162 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling
Der Teil des Betriebssystems, der entscheidet,
• welcher der Prozesse,
• die im Zustand bereit“ sind,
”
• ausgewählt wird und dann
• den Prozessor zugeteilt bekommt,
heißt Scheduler.
Das Verfahren, wie ausgewählt wird, nennt man Scheduling-Algorithmus.
163 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Kriterien für Scheduling-Algorithmus
Fairness Jeder Prozess wird gleichermaßen berücksichtigt; es gibt
keine privilegierten Prozesse.
Effizienz Der Prozessor wird stets vollständig ausgelastet.
Antwortzeit Die Antwortzeit für die interaktiv arbeitenden Benutzer
wird minimiert.
Verweilzeit Die Zeit, die auf Ausgabe von Stapelaufträge gewartet
werden muss, ist minimal.
Durchsatz Die Anzahl der Jobs, die in einem gegebenen Zeitintervall
ausgeführt werden, wird maximiert.
Ressourcenbedarf Der für die Implementierung benötigte
Ressourcenbedarf ist minimal.
Nicht alle Kriterien sind gleichzeitig zu erfüllen, da sie teilweise
widersprüchlich sind (z.B. Antwortzeit – Verweilzeit).
164 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Kategorisierung
Ein Betriebssystem nutzt den Unterbrechungsmechanismus moderner
CPU’s, um sicher zu stellen, dass kein Prozess zu lange ausgeführt wird:
Wenn die Hardware einen Interrupt (etwa 100 mal pro Sekunde)
ausgelöst hat, erhält das Betriebssystem die Kontrolle und der
Scheduler wählt einen neuen Prozess aus.
Je nachdem, wie der Scheduler die Auswahl der Prozesse vornimmt,
werden Scheduling-Algorithmen unterschieden in:
• preemptive Scheduling:
rechnende Prozesse können unterbrochen werden.
• run to completion (non-preemptive) Scheduling:
der rechnende Prozess wird nicht unterbrochen.
Welche Unterschiede ergeben sich?
165 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Kategorisierung
Ein Betriebssystem nutzt den Unterbrechungsmechanismus moderner
CPU’s, um sicher zu stellen, dass kein Prozess zu lange ausgeführt wird:
Wenn die Hardware einen Interrupt (etwa 100 mal pro Sekunde)
ausgelöst hat, erhält das Betriebssystem die Kontrolle und der
Scheduler wählt einen neuen Prozess aus.
Je nachdem, wie der Scheduler die Auswahl der Prozesse vornimmt,
werden Scheduling-Algorithmen unterschieden in:
• preemptive Scheduling:
rechnende Prozesse können unterbrochen werden.
• run to completion (non-preemptive) Scheduling:
der rechnende Prozess wird nicht unterbrochen.
Welche Unterschiede ergeben sich?
165 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Round-Robin Scheduling
Ein einfaches und häufig angewendetes Verfahren ist das Round-Robin
Verfahren:
• Jeder Prozess erhält eine Zeitscheibe (Quantum), die er maximal
für die Ausführung zugeteilt bekommt.
• Ist diese Zeit abgelaufen, wird ihm der Prozessor entzogen und
• ein anderer Prozess wird ausgewählt.
• 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:
166 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Round-Robin Scheduling
Ein einfaches und häufig angewendetes Verfahren ist das Round-Robin
Verfahren:
• Jeder Prozess erhält eine Zeitscheibe (Quantum), die er maximal
für die Ausführung zugeteilt bekommt.
• Ist diese Zeit abgelaufen, wird ihm der Prozessor entzogen und
• ein anderer Prozess wird ausgewählt.
• 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:
166 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Dauer für das Quantum
Eine Implementierung dieses Verfahrens muss eine “richtige” Wahl für 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 während
Editorsitzung) bearbeitet wird.
167 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Dauer für das Quantum
Folgerung:
• Quantum zu klein → wegen häufiger 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 häufig vor Ablauf des Quantums
eine blockierende Systemfunktion aufrufen und damit den
Prozessor entzogen bekommen, werden durch Round-Robin
benachteiligt.
168 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Dauer für das Quantum
Folgerung:
• Quantum zu klein → wegen häufiger 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 häufig vor Ablauf des Quantums
eine blockierende Systemfunktion aufrufen und damit den
Prozessor entzogen bekommen, werden durch Round-Robin
benachteiligt.
168 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Round-Robin Scheduling
Dauer für 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
$
169 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Scheduling mit Prioritäten
Die Grundidee des Prioritäts-Scheduling ist:
• Jeder Prozess bekommt eine Priorität zugewiesen.
• Es wird immer der rechenbereite Prozess mit der höchsten Priorität
ausgeführt.
Problem:
Wird kein weiterer Mechanismus realisiert, so kommt es vor,
dass Prozesse mit hoher Priorität verhindern, dass ein Prozess
mit niedriger Priorität je den Prozessor bekommen
(Verhungern).
170 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Scheduling mit Prioritäten
Die Grundidee des Prioritäts-Scheduling ist:
• Jeder Prozess bekommt eine Priorität zugewiesen.
• Es wird immer der rechenbereite Prozess mit der höchsten Priorität
ausgeführt.
Problem:
Wird kein weiterer Mechanismus realisiert, so kommt es vor,
dass Prozesse mit hoher Priorität verhindern, dass ein Prozess
mit niedriger Priorität je den Prozessor bekommen
(Verhungern).
170 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Scheduling mit Prioritäten
Deshalb wird folgender Mechanismus als Lösung implementiert:
• Der Scheduler verringert die Priorität des rechnenden Prozesses bei
jedem Interrupt, der durch die interne Prozessoruhr ausgelöst wird.
• Damit fällt die Priorität des laufenden Prozesses irgendwann unter
die Priorität eines anderen rechenbereiten Prozesses;
• in diesem Fall wird ein solcher rechenbereiter Prozess mit höherer
Priorität ausgewählt.
171 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Prioritäten können statisch oder dynamisch vergeben werden.
statisch Die Priorität wird vor dem Prozessstart festgelegt. Z.B.
kann man folgende Regel anwenden:
Batchprozesse < Systemprozesse < Interaktive Prozesse <
...
dynamisch Dynamische Vergabe von Prioritäten wird häufig realisiert,
um Systemziele zu erreichen.
Z.B. Optimierung des I/O-Verhaltens: dann muss ein
Prozess, der bei E/A Ereignis rechenbereit wird, hohe
Priorität bekommen, damit das E/A Ereignis behandelt
werden kann.
172 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
In modernen Betriebssystemen werden Prozesse in Klassen eingeteilt,
wobei
• zwischen den Klassen Prioritäts-Scheduling und
• innerhalb der Klasse Round-Robin Scheduling
verwendet wird.
173 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Thread Prioritäten in Java
Die JVM soll plattformunabhängig implementierbar sein. Daher gibt
es in Java keine Vorgaben bzgl. des Scheduling.
Methoden, mit denen die Priorität eines Thread beeinflusst werden kann:
• Jeder Thread hat eine Priorität zwischen MIN PRIORITY und
MAX PRIORITY ([1,10]).
• Wird ein neuer Thread erzeugt, erbt er die Priorität vom Vater.
• Der Defaultwert, wenn ein Thread aus main() erzeugt wurde, ist
Thread.NORM PRIORITY (5).
• Die Methode getPriority() liefert die aktuelle Priorität eines Threads.
• Mit setPriority()kann die Priorität verändert werden.
174 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Thread Prioritäten in Java
Achtung:
• Prioritäten beeinflussen weder Semantik noch Korrektheit eines
Java Programms.
• Prioritäten dürfen beim Programmieren nicht als Ersatz für Locking
verwendet werden!
• Prioritäten dürfen nur verwendet werden, um die relative
Wichtigkeit unterschiedlicher Threads untereinander zu definieren.
175 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
3 Threads mit unterschiedlicher Priorität 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
176 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
3 Threads mit unterschiedlicher Priorität 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
";
}
177 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
3 Threads mit unterschiedlicher Priorität 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 ?
178 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Scheduling mit Prioritäten
Prozessprioritäten in Unix/Linux
In Linux ist die Priorität eines Prozesses ein Integer im Bereich -20 bis 20
(-20 ist höchste Priorität, Default ist 0).
Das folgende Programm zeigt, wie die Priorität 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);
}
179 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Shortest-Job-First
Die beiden letzten Verfahren sind für interaktive Systeme entworfen
worden.
Ein Verfahren für Systeme, bei denen die Ausführungszeiten der
einzelnen Prozesse im Voraus bekannt sind, benutzt eine Warteschlange
für die gleichgewichtigen Prozesse.
Der Scheduler wählt den Prozess mit der kürzesten
Ausführungszeit zuerst.
Gemäss dieser Methode wird die durchschnittliche Verweilzeit (Zeit,
die der Prozess im System verweilt ) von Prozessen minimiert:
180 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Shortest-Job-First
Die beiden letzten Verfahren sind für interaktive Systeme entworfen
worden.
Ein Verfahren für Systeme, bei denen die Ausführungszeiten der
einzelnen Prozesse im Voraus bekannt sind, benutzt eine Warteschlange
für die gleichgewichtigen Prozesse.
Der Scheduler wählt den Prozess mit der kürzesten
Ausführungszeit zuerst.
Gemäss dieser Methode wird die durchschnittliche Verweilzeit (Zeit,
die der Prozess im System verweilt ) von Prozessen minimiert:
180 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Gegeben seien 4 Prozesse mit folgenden Ausführungszeiten:
A 8 Sekunden
B 6 Sekunden
C 4 Sekunden
D 6 Sekunden
Ausführungsreihenfolge 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
181 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Gegeben seien 4 Prozesse mit folgenden Ausführungszeiten:
A 8 Sekunden
B 6 Sekunden
C 4 Sekunden
D 6 Sekunden
Ausführungsreihenfolge 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
182 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Behauptung:
Den Prozess mit der kürzesten Ausführungszeit zu wählen 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 ausgeführt 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 Ausführungszeit ist, B der Prozess mit
der zweit kleinsten Ausführungszeit, etc
183 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Ausführungszeit bestimmen
Das Problem bei interaktiven Betriebssystemen ist es, die
Ausführungszeit der Prozesse zu bestimmen.
Idee:
Schätze die Ausführungszeit auf Basis der gemessenen Zeit
der Vergangenheit M.
• Der Scheduler wählt dann den Prozess mit der kürzesten
geschätzten Zeit.
• Der neue geschätzte 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
zurückliegenden Periode auf die Schätzung angibt; Werte
nahe 1 ordnen der geschätzten Vergangenheit wenig
Stellenwert zu.
184 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Shortest-Job-First
Hörsaalübung
Gegeben seien 5 Prozesse mit folgenden Ausführungszeiten:
A 6 Sekunden
B 6 Sekunden
C 8 Sekunden
D 2 Sekunden
E 4 Sekunden
Welche Ausführungsreihenfolge führt zur optimalen durchschnittlichen
Verweilzeit?
Prozess
A
B
C
D
E
Verweilzeit
→ durchschnittliche Verweilzeit =
185 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Garantiertes Scheduling
Garantiertes Scheduling
Beim garantierten Scheduling wird einem Prozess eine gewisse
Performance versprochen und die Einhaltung garantiert.
Mögliche Versprechen:
• Bei interaktiven Systemen mit n Benutzern, erhält jeder 1/n der
verfügbaren Prozessorzeit
• Bei Echtzeitsystemen wird vom System garantiert, dass ein
Prozess innerhalb einer Zeitschranke abgeschlossen ist.
186 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Verhältnis von erhaltener Zeit e und
zustehender Zeit z.
Das Verhältnis 0,5 bedeutet, dass der Prozess halb so viel Zeit
verbraucht hat, wie ihm garantiert wurde.
Der Scheduler wählt immer den Prozess, mit dem
berechneten kleinsten Verhältnis 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
ausgewählter
Prozess
X
187 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 Verhältnis von erhaltener Zeit e und
zustehender Zeit z.
Das Verhältnis 0,5 bedeutet, dass der Prozess halb so viel Zeit
verbraucht hat, wie ihm garantiert wurde.
Der Scheduler wählt immer den Prozess, mit dem
berechneten kleinsten Verhältnis 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
ausgewählter
Prozess
X
187 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Garantiertes Scheduling
Echtzeit-Systeme
Bei Echtzeitsystemen wird vom System garantiert, dass ein Prozess
innerhalb einer Zeitschranke abgeschlossen ist.
Der Scheduler wählt den Prozess, bei dem die Gefahr am
grössten 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
ausgewählter
Prozess
X
188 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Garantiertes Scheduling
Echtzeit-Systeme
Bei Echtzeitsystemen wird vom System garantiert, dass ein Prozess
innerhalb einer Zeitschranke abgeschlossen ist.
Der Scheduler wählt den Prozess, bei dem die Gefahr am
grössten 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
ausgewählter
Prozess
X
188 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Garantiertes Scheduling
Hörsaalübung
1. Ein interaktives System sei geben durch:
Prozess
A
B
C
D
erhaltene
Zeit e
8
2
2
2
versprochene
Zeit z
e/z
ausgewählter
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
ausgewählter
Prozess
In welcher Reihenfolge werden die Prozesse in beiden Systemen
ausgewählt (jeweils 5 Kontextwechsel, Quantum 1 Sekunde)?
189 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Zweistufiges Scheduling
Zweistufiges Scheduling
Die bisherigen Scheduling-Verfahren haben gemeinsam, dass alle
rechenbereiten Prozesse im Hauptspeicher ablaufen.
• Wenn nicht genug Hauptspeicher verfügbar ist, müssen einige dieser
Prozesse auf der Festplatte abgelegt werden.
• Der Aufwand für einen Prozesswechsel ist aber höher, wenn ein
Prozess zunächst in den Hauptspeicher zurückgeladen werden muss.
190 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Zweistufiges Scheduling
Ein zweistufiges Verfahren teilt die
rechenbereiten Prozesse in 2 disjunkte
Teilmengen:
• Prozesse im Hauptspeicher H
• Prozesse auf Platte (Sekundärspeicher
S)
Es existieren zwei Scheduler:
• lokaler Scheduler wählt stets einen
Prozess aus H
• periodisch lagert ein globaler Scheduler
Prozesse von H und S aus und ersetzt
sie.
191 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Zweistufiges Scheduling
Als Verfahren für 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)?
• Priorität des Prozesses in S?
192 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Fallbeispiel: Linux Scheduler
Die Beschreibung basiert auf dem Beitrag Der O(1)-Scheduler im Kernel
”
2.6“ von Timo Hönig im Linux-Magazin.
193 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 hält alle Informationen
seines Prozesses fest (im Wesentlichen,
das was man mit ps sieht).
194 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Den Zustand eines Prozesses speichert die Variable
Prozessdeskriptors.
Der Scheduler kennt insgesamt fünf Zustände:
state des
1
TASK RUNNING kennzeichnet den Prozess als lauffähig.
Er muss auf kein Ereignis warten und kann daher vom Scheduler der
CPU zugeordnet werden. Alle Prozesse im Zustand
TASK RUNNING zieht der Scheduler für die Ausführung 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.
195 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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, zügig
eintritt, oder wenn der Prozess ohne Unterbrechung warten soll.
4
Wurde ein Prozess beendet, dessen Elternprozess noch nicht den
Systemaufruf wait4() ausgeführt 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 endgültig beendet, seine Datenstrukturen werden
gelöscht. Endet ein Elternprozess vor seinen Kindprozessen,
bekommt jedes Kind einen neuen Elternprozess zugeordnet. Dieser
ist nunmehr dafür verant- wortlich, wait4() aufzurufen, sobald
der Kindprozess beendet wird. Ansonsten könnten die Kindprozesse
den Zustand TASK ZOMBIE nicht verlassen und würden als Leichen
im Hauptspeicher zurückbleiben.
196 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
5
Den Zustand TASK STOPPED
erreicht ein Prozess, wenn er beendet
wurde und nicht weiter ausführbar ist.
In diesen Zustand tritt der Prozess ein,
sobald er eines der Signale
SIGSTOP, SIGTST,
SIGTTIN oder SIGTTOU erhält.
197 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Entwicklungsziele für den Scheduler
Neben den allgemeinen Zielen (Auslastung der CPU, ...) waren hier
zusätzlich folgende Punkte maßgebend:
• gute SMP-Skalierung
• geringe Latenz auch bei hoher Systemlast
• faire Prioritätenverteilung
• Komplexität der Ordnung O(1)
Alle Linux-Scheduler bisher besaßen eine Komplexität der Ordnung O(n): Die
Kosten für das Scheduling wuchsen linear mit der Anzahl n der lauffähigen
Prozesse. Bei einem Kontextwechsel wird in einer verketteten Liste nach einem
Prozess gesucht, dessen Priorität am niedrigsten ist.
198 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Prozessprioritäten
Die Prozessprioritäten entscheiden, welchen lauffähigen Prozess die CPU
beim nächsten Kontextwechsel zugeteilt bekommt - den mit der zum
Zeitpunkt des Kontextwechsels höchsten Priorität. Die Priorität eines
Prozesses ändert sich dabei dynamisch während seiner Laufzeit.
Es gibt zwei unterschiedliche Prioritäten:
• die statische Prozesspriorität, also die vom
nice-Wert bestimmte
static prio
Der Wertebereich des nice-Values reicht von -20 (dem höchsten)
bis 19 (dem niedrigsten).
• die dynamische (effektive) Prozesspriorität (prio), die der
Scheduler aufgrund der Interaktivität eines Prozesses berechnet.
199 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Linux 2.6 kennt standardmäßig 140
Prioritätslevels.
• Hierbei entspricht null der höchsten
und 139 der niedrigsten Priorität.
• Die Levels von eins bis 99 sind für
Tasks mit Echtzeitpriorität reserviert.
• Alle anderen Prozesse erhalten
zunächst gemäß ihres nice-Werts
eine Priorität: Der nice-Wert (-20
bis 19) wird einfach in den Bereich ab
101 gemappt.
• Während des Ablaufs eines Prozesses
verändert sich durch seinen
Interaktivitätsgrad aber seine Priorität.
200 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Alle lauffähigen 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 schützen */
spinlock_t lock ;
/* Zahl der lauffä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];
... }
201 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Neben Verweisen auf die gerade laufende Task, enthält 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 ]; /* Priorität - Bitmap */
/* Für jede Priorität eine Liste der Prozesse */
struct list_head queue [ MAX_PRIO ];
};
• Das
active-Array listet alle lauffähigen Prozesse, deren
Zeitscheibe noch nicht abgelaufen ist.
• Wenn die Zeitscheibe eines Prozesse abläuft, verschiebt der
Scheduler den Eintrag vom active- in das zweite Array
expired.
• Beide, das active- und das expired-Array, führen für jede
Priorität eine verkettete Liste der Prozesse mit entsprechender
Priorität.
• Eine Bitmap hält fest, für welche Priorität 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 Priorität des Prozesses das
korrespondierende Bit im Priorität-Bitmap auf eins.
202 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
• Startet ein Prozess mit dem Nice null, setzt
der Scheduler das 120. Bit des Priorität-Bitmaps im active-Array und reiht ihn in die
Prozessliste mit Priorität 120 ein.
• Analog dazu löscht sich das entsprechende Bit
im Priorität-Bitmap, sobald der Scheduler den
letzten Prozess einer gegebenen Priorität aus
einem der beiden Priority-Arrays austrägt.
• Der Scheduler muss nur das erste gesetzte Bit
des Priorität-Bitmaps finden (da Bitmap
konstante Größe hat folgt O(1)). Anschließend
führt der Scheduler den ersten Prozess aus der
verketteten Liste dieser Priorität aus. Prozesse
gleicher Priorität bekommen die CPU
nacheinander in einem Ringverfahren (Round
Robin) zugeteilt.
203 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Prozess-Zeitscheiben und Neuberechnung der Prioritäten
Die Größe der Zeitscheibe eines Prozesses ist von seiner Priorität
abhängig:
• Prozesse mit hoher Priorität erhalten mehr CPU-Zeit als solche
mit niedriger.
• Die kleinste Zeitscheibe beträgt 10, die längste 200 Millisekunden.
Ein Prozess mit dem nice-Wert null erhält 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
lauffähigen 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 Plätze.
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 länger.
204 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Die dynamische Priorität errechnet der Scheduler aus der statischen
und der Prozessinter- aktivität. Gemäß seiner Interaktivität erhält ein
Prozess vom Scheduler entweder einen Bonus oder ein Penalty (Malus).
Interaktive Prozesse gewinnen über einen Bonus maximal fünf
Prioritätslevels hinzu, während jene Prozesse, die eine geringe
Interaktivität aufweisen, maximal fünf Prioritätslevels durch ein Penalty
verlieren. Die dynamische Priorität eines Prozesses mit einem
nice-Wert fünf beträgt demnach im besten Fall null und im
schlechtesten zehn.
205 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Um den Grad der Interaktivität 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 können,
protokolliert der Kernel für 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
dafür eine Entsprechung in dem Wertebereich von null und zehn
(MAX SLEEP AVG).
Läuft 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 erhöht - 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.
206 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Mit der Funktion effective prio() berechnet der Scheduler die
dynamische Priorität prio basierend auf der statischen
static prio und der Interaktivität sleep avg des Prozesses. Zum
Berechnen der neuen Zeitscheibe greift der Scheduler auf die dynamische
Prozesspriorität zurück. 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 können
ihre Priorität jedoch nicht missbrauchen, um die CPU zu blockieren: Da
die Zeit, die der Prozess beim Ausführen 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 Priorität und seine große Zeitscheibe.
Ein Prozess mit sehr hoher Interaktivität erhält nicht nur eine hohe
dynamische Priorität und somit eine große Zeitscheibe: Der Scheduler
trägt den Prozess nach Ablauf seiner Zeitscheibe auch wieder sofort in
das active-Array ein, statt wie gewöhnlich ins expired-Array. Der
Prozess wird dadurch seiner Priorität gemäß wieder zugeordnet und muss
nicht auf das Austauschen der Priority-Arrays warten.
207 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
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 erhält.
Sobald das Ereignis eintritt, auf das der Prozess in einer Wait-Queue
wartet, wird er aufgeweckt, wechselt seinen Zustand in
TASK RUNNING zurück, verlässt die Wait-Queue und betritt die
Run-Queue. Falls der aufgewachte Prozess eine höhere Priorität besitzt
als der gerade ablaufende, unterbricht der Scheduler den aktuell
laufenden Prozess zugunsten des eben aufgewachten.
208 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Kernel-Preemption
Anders als Kernel 2.4 ist der neue Linux-Kernel preemptiv: Kernelcode,
der gerade ausgeführt wird, kann unterbrochen werden. Vor dem
Unterbrechen muss gewährleistet sein, dass sich der Kernel in einem
Zustand befindet, der eine Neuzuordnung der Prozesse zulässt.
Die Struktur thread info jedes Prozesses enthält zu diesem Zweck den
Zähler preempt count. Ist er null, ist der Kernel in einem sicheren
Zustand und darf unterbrochen werden. Die Funktion
preempt disable() erhöht den Zähler preempt count beim Setzten
eines so genannten Locks um eins; die Funktion
preempt enable() erniedrigt ihn um eins, sobald ein Lock aufgelöst
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.
209 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Realtimefähigkeit
Für Prozesse mit so Echtzeitpriorität (Priorität 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, läuft er so lange, bis er blockiert oder
freiwillig über die Funktion sched yield() den Prozessor abgibt.
Alle anderen Prozesse mit einer niedrigeren Priorität sind solange
blockiert und werden nicht ausgeführt.
SCHED RR
verfolgt die gleiche Strategie wie
mit vorgegebenen Zeitscheiben.
SCHED FIFO, aber zusätzlich
Die CPU-Bedürfnisse der Echtzeitprozesse gleicher Priorität befriedigt der
Scheduler per Round-Robin. Prozesse mit einer niedrigeren Priorität
kommen überhaupt nicht zum Zuge. Der Scheduler vergibt für
Echtzeitprozesse keine dynamischen Prioritäten. Prozesse ohne
Echtzeitpriorität führt er mit der Strategie SCHED OTHER aus.
210 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Realtimefähigkeit
Die Echtzeit-Strategien von Linux garantieren jedoch keine
Antwortzeiten, was die Voraussetzung für ein hartes
Echtzeit-Betriebssystem wäre.
Der Kernel stellt jedoch sicher, dass ein lauffähiger Echtzeit-Prozess
immer die CPU bekommt, wenn er auf kein Ereignis warten muss, er
freiwillig die CPU abgibt und wenn kein lauffähiger Echtzeitprozess
höherer Priorität existiert.
211 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Leistungsvergleich O(n) vs O(1) Scheduler
Benötigte Zeit zur Interprozess-Kommunikation in Abhängigkeit von der
Anzahl beteiligter Prozesse auf einem Singleprozessor-System mit Kernel
2.4 (rot) und 2.6 (grün):
212 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Scheduling
Fallbeispiel: Linux Scheduler
Benötigte Zeit zur Interprozess-Kommunikation in Abhängigkeit 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.
213 / 214
Betriebssysteme - Prozesse → [email protected] Version: (8c45d65)
ARSnova 19226584
Literatur
Literatur
Folgende Literatur wir ergänzend empfohlen:
• Alois Schütte, ’Programmieren in Occam’, Addison-Wesley
214 / 214