Betriebssysteme
Besprechung: 2. Synchronisation
https://ess.cs.tu-dortmund.de/DE/Teaching/SS2020/BS/
Horst Schirmeier
horst.schirmeier@tu-dortmund.de
http://ess.cs.tu-dortmund.de/~hsc
AG Eingebettete Systemsoftware Informatik 12, TU Dortmund
Theoriefragen: Scheduling (1)
Wie sieht die Prozesszuteilung nach dem Virtual-Round- Robin-Verfahren aus?
●
Prozess
CPU-Burst
I/O-Burst
A
6
2
B
3
3
C
2
4
Theoriefragen: Scheduling (1)
Wie sieht die Prozesszuteilung nach dem Virtual-Round- Robin-Verfahren aus?
●
Prozess
CPU-Burst
I/O-Burst
A
6
2
B
3
3
C
2
4
A B C
0
10
t[ms] 20 30
Theoriefragen: Scheduling (2)
Wie sieht die Prozesszuteilung nach dem First-Come-First- Served-Verfahren aus?
●
Prozess
CPU-Burst
I/O-Burst
A
6
2
B
3
3
C
2
4
Theoriefragen: Scheduling (2)
Wie sieht die Prozesszuteilung nach dem First-Come-First- Served-Verfahren aus?
●
Prozess
CPU-Burst
I/O-Burst
A
6
2
B
3
3
C
2
4
A B C
0
10
t[ms] 20 30
Theoriefragen: Scheduling (3)
Was ist der Vorteil des Verfahrens Virtual Round Robin gegenüber Round Robin?
●
Theoriefragen: Scheduling (3)
Was ist der Vorteil des Verfahrens Virtual Round Robin gegenüber Round Robin?
E/A-lastige Prozesse werden durch die Vorzugsliste fairer an der CPU beteiligt.
●
Theoriefragen: Semaphoren
Beschreibt in eigenen Worten, wozu man Semaphoren verwendet.
●
Theoriefragen: Semaphoren
Beschreibt in eigenen Worten, wozu man Semaphoren verwendet.
Zur Synchronisation des Zugriffs auf geteilte Ressourcen
●
Programmierung a)
int kundencounter;
int kundencounter;
void *kasse(void *);
void *kasse(void *);
int main(void) {
int main(void) {
kundencounter = 42;
kundencounter = 42;
pthread_t kassen[5];
pthread_t kassen[5];
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
int retval =
int retval =
pthread_create(&kassen[i], NULL, &kasse, NULL);
pthread_create(&kassen[i], NULL, &kasse, NULL);
if (retval != 0) { /* Fehlerbehandlung */ }
if (retval != 0) { /* Fehlerbehandlung */ }
}
printf("Kunden übrig: %d\n", kundencounter);
printf("Kunden übrig: %d\n", kundencounter);
pthread_exit(NULL);
pthread_exit(NULL);
}
}
}
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
int retval = pthread_join(kassen[i], NULL); int retval = pthread_join(kassen[i], NULL);
if (retval != 0) { /* Fehlerbehandlung */ }
if (retval != 0) { /* Fehlerbehandlung */ }
}
}
Programmierung a)
int kundencounter;
int kundencounter;
void *kasse(void *);
void *kasse(void *);
int main(void) {
int main(void) {
kundencounter = 42;
kundencounter = 42;
pthread_t kassen[5];
pthread_t kassen[5];
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
int retval =
int retval =
pthread_create(&kassen[i], NULL, &kasse, NULL);
pthread_create(&kassen[i], NULL, &kasse, NULL);
if (retval != 0) { /* Fehlerbehandlung */ }
if (retval != 0) { /* Fehlerbehandlung */ }
}
printf("Kunden übrig: %d\n", kundencounter);
printf("Kunden übrig: %d\n", kundencounter);
pthread_exit(NULL);
pthread_exit(NULL);
}
}
}
for (int i = 0; i < 5; i++) {
for (int i = 0; i < 5; i++) {
int retval = pthread_join(kassen[i], NULL); int retval = pthread_join(kassen[i], NULL);
if (retval != 0) { /* Fehlerbehandlung */ }
if (retval != 0) { /* Fehlerbehandlung */ }
}
}
Achtung, Fehler in den Vorbesprechungsfolien: perror() kann bei pthread_*() nicht direkt genutzt werden, da diese Funktionen (anders als z.B. sem_wait(3)) die Variable errno nicht setzen. Eine Möglichkeit ist, errno manuell auf den Rückgabewert zu setzen:
if ((errno = pthread_create(...)) != 0) { perror("pthread_mutex_lock");
exit(1);
}
Programmierung a) (2)
void *kasse(void *arg)
void *kasse(void *arg)
{
{
puts("Kasse geöffnet");
puts("Kasse geöffnet");
while (kundencounter > 0) {
while (kundencounter > 0) {
printf(“Kunden: %d\n”, kundencounter);
printf(“Kunden: %d\n”, kundencounter);
int sleeptime = 3;
int sleeptime = 3;
while (sleeptime > 0) {
while (sleeptime > 0) {
sleeptime = sleep(sleeptime); sleeptime = sleep(sleeptime);
}
puts(“Kasse geschlossen”);
puts(“Kasse geschlossen”);
pthread_exit(NULL);
pthread_exit(NULL);
}
}
kundencounter–;
kundencounter–;
}
}
}
Analyse b)
Wahrscheinlich wird euch aufgefallen sein, dass Kunden den Supermarkt mehrfach verlassen, bzw. dass, wenn das Programm endet, weniger als 0 Kunden im Supermarkt sind.
Wie nennt man eine solche Situation?
●
●
Analyse b)
Wahrscheinlich wird euch aufgefallen sein, dass Kunden den Supermarkt mehrfach verlassen, bzw. dass, wenn das Programm endet, weniger als 0 Kunden im Supermarkt sind.
Wie nennt man eine solche Situation?
Race Condition
●
●
–
Analyse b) (2)
Beschreibt schrittweise anhand von zwei parallel ausgeführten Threads, wie eines der beobachteten Probleme entstehen kann.
Beispiel: kundencounter = 1
Beide Threads testen, ob kundencounter > 0:
true
Beide Threads warten 3s Kundencounter wird in beiden Threads dekrementiert kundencounter = -1
●
●
●
● ●
●
●
void *kasse(void *_)
void *kasse(void *_)
{
{
puts(“Kasse geöffnet”);
puts(“Kasse geöffnet”);
while (kundencounter > 0) { while (kundencounter > 0) {
printf(“Kunden: %d\n”, kundencounter);
printf(“Kunden: %d\n”, kundencounter);
int sleeptime = 3;
int sleeptime = 3;
while (sleeptime > 0) {
while (sleeptime > 0) {
sleeptime = sleep(sleeptime); sleeptime = sleep(sleeptime);
}
puts(“Kasse geschlossen”);
puts(“Kasse geschlossen”);
pthread_exit(NULL);
pthread_exit(NULL);
}
}
kundencounter–;
kundencounter–;
}
}
}
Programmierung c)
…
…
pthread_mutex_t lock;
pthread_mutex_t lock;
…
…
int main(void)
int main(void)
{
{
…
}
…
}
…
int retval = pthread_mutex_init(&lock, NULL); int retval = pthread_mutex_init(&lock, NULL);
if (retval) { /* Fehlerbehandlung */ }
if (retval) { /* Fehlerbehandlung */ }
for (int i = 0; i < 5; i++) { /* Threads erzeugen */ }
for (int i = 0; i < 5; i++) { /* Threads erzeugen */ }
for (int i = 0; i < 5; i++) { /* Auf Threads warten */ }
for (int i = 0; i < 5; i++) { /* Auf Threads warten */ }
retval = pthread_mutex_destroy(&lock); retval = pthread_mutex_destroy(&lock);
if (retval) { /* Fehlerbehandlung */ }
if (retval) { /* Fehlerbehandlung */ }
...
Programmierung c) (2)
void *kasse(void *_)
void *kasse(void *_)
{
{
...
}
...
}
...
for (;;) {
for (;;) {
int retval = pthread_mutex_lock(&lock); int retval = pthread_mutex_lock(&lock);
if (retval) { /* Fehlerbehandlung */ }
if (retval) { /* Fehlerbehandlung */ }
}
// kundencounter--; entfernt
}
...
// Kundenanzahl ausgeben
// Kundenanzahl ausgeben
if (kundencounter <= 0) {
if (kundencounter <= 0) {
retval = pthread_mutex_unlock(&lock); retval = pthread_mutex_unlock(&lock);
if (retval) { /* Fehlerbehandlung */ }
if (retval) { /* Fehlerbehandlung */ }
break; // Schleife abbrechen, um den Thread zu beenden
break; // Schleife abbrechen, um den Thread zu beenden
}
}
kundencounter--;
kundencounter--;
retval = pthread_mutex_unlock(&lock); retval = pthread_mutex_unlock(&lock);
if (retval) { /* Fehlerbehandlung */ }
if (retval) { /* Fehlerbehandlung */ }
// 3 Sekunden warten
// 3 Sekunden warten
// kundencounter--; entfernt
#define MAX_CAPACITY 42
#define MAX_CAPACITY 42
...
...
pthread_cond_t free_capacity;
pthread_cond_t free_capacity;
void *eingang(void *);
void *eingang(void *);
...
...
int main(void)
int main(void)
{
{
...
}
pthread_t eingaenge[2];
pthread_t eingaenge[2];
kundencounter = MAX_CAPACITY;
kundencounter = MAX_CAPACITY;
int retval = pthread_mutex_init(&lock, NULL); // Fehlerbehandlung
int retval = pthread_mutex_init(&lock, NULL); // Fehlerbehandlung
retval = pthread_cond_init(&free_capacity, NULL); // Fehlerbehandlung retval = pthread_cond_init(&free_capacity, NULL); // Fehlerbehandlung
for (int i = 0; i < 5; i++) { /* Kassenthreads erzeugen */ } for (int i = 0; i < 5; i++) { /* Kassenthreads erzeugen */ }
for (int i = 0; i < 2; i++) { /* Eingangsthreads erzeugen */ } for (int i = 0; i < 2; i++) { /* Eingangsthreads erzeugen */ }
for (int i = 0; i < 5; i++) { /* Auf Kassenthreads warten */ } for (int i = 0; i < 5; i++) { /* Auf Kassenthreads warten */ }
for (int i = 0; i < 2; i++) { /* Auf Eingangsthreads warten */ } for (int i = 0; i < 2; i++) { /* Auf Eingangsthreads warten */ }
}
...
Zusatzaufgabe d)
Zusatzaufgabe d) (2)
void *kasse(void *_)
void *kasse(void *_)
{
{
...
}
}
}
...
for (;;) {
for (;;) {
int retval = pthread_mutex_lock(&lock);
int retval = pthread_mutex_lock(&lock);
}
// 3 Sekunden warten
// Fehlerbehandlung
// Fehlerbehandlung
printf("Kunden: %d\n", kundencounter);
printf("Kunden: %d\n", kundencounter);
if (kundencounter > 0) {
if (kundencounter > 0) {
kundencounter–;
kundencounter–;
retval = pthread_cond_signal(&free_capacity); retval = pthread_cond_signal(&free_capacity);
}
// Fehlerbehandlung
}
// Fehlerbehandlung
retval = pthread_mutex_unlock(&lock);
retval = pthread_mutex_unlock(&lock);
// Fehlerbehandlung
// Fehlerbehandlung
// 3 Sekunden warten
Zusatzaufgabe d) (3)
void *eingang(void *_)
void *eingang(void *_)
{
{
puts(“Eingang geöffnet”);
puts(“Eingang geöffnet”);
for (;;) {
for (;;) {
int retval = pthread_mutex_lock(&lock); // FEHLERBEHANDLUNG
int retval = pthread_mutex_lock(&lock); // FEHLERBEHANDLUNG
while (kundencounter > MAX_CAPACITY – 3) {
while (kundencounter > MAX_CAPACITY – 3) {
retval = pthread_cond_wait(&free_capacity, &lock); // FEHLERBEH. retval = pthread_cond_wait(&free_capacity, &lock); // FEHLERBEH.
}
}
}
}
// 2 Sekunden warten
}
}
printf(“Einlass: %d -> %d\n”, kundencounter, kundencounter + 3);
printf(“Einlass: %d -> %d\n”, kundencounter, kundencounter + 3);
kundencounter += 3;
kundencounter += 3;
if (kundencounter <= MAX_CAPACITY – 3) {
if (kundencounter <= MAX_CAPACITY – 3) {
retval = pthread_cond_signal(&free_capacity); // FEHLERBEH. retval = pthread_cond_signal(&free_capacity); // FEHLERBEH.
}
}
retval = pthread_mutex_unlock(&lock); // FEHLERBEHANDLUNG
retval = pthread_mutex_unlock(&lock); // FEHLERBEHANDLUNG
// 2 Sekunden warten