Betriebssysteme
Besprechung: A3 – Deadlock
https://ess.cs.tu-dortmund.de/DE/Teaching/SS2020/BS/
Horst Schirmeier
horst.schirmeier@tu-dortmund.de
https://ess.cs.tu-dortmund.de/~hsc
AG Eingebettete Systemsoftware mit Material von Olaf Spinczyk, Informatik 12, TU Dortmund Universität Osnabrück
1) Betriebsmittel
Was ist das Betriebsmittel, und ist es konsumierbar oder wiederverwendbar?
Betriebsmittel sind die Zutatenkisten.
Sie sind wiederverwendbar, weil sie nach der Benutzung zum gemeinsamen Kühlschrank zurückgebracht werden und nie aufgebraucht werden.
● ●
2
2) Verklemmungsbedingungen (1) Wodurch werden die Bedingungen in der Mensa erfüllt?
Ein Koch behält die Kisten für sich und nutzt sie nicht gemeinsam.
Die Köche holen die Kisten nach und nach und nicht alle auf einmal.
●
–
●
–
●
–
Die Kisten werden erst nach Fertigstellung des Gerichts zurück gebracht (und nicht vorher).
mutual exclusion
hold and wait
no preemption
3
2) Verklemmungsbedingungen (2)
Situation, bei der eine Verklemmung aufgetreten ist (circular wait):
Koch A hat alle Kisten einer Zutat, die Koch B benötigt, um sein Gericht fertig zu stellen. Koch B wiederum hat alle Kisten einer anderen Zutat, die Koch A zur Fertigstellung benötigt.
ist belegt von A
Koch: A
wird benötigt von A
●
Zutatenkiste 1
wird benötigt von B
Koch: B
ist belegt von B
Zutatenkiste 2
4
3) Verklemmungsvorbeugung
Was bewirkt die Benutzung des Mutex in Programmieraufgabe c), und welche Vorbedingung wird dadurch entkräftet?
Es können keine Verklemmungen mehr auftreten, weil jeder Koch sich alle Kisten auf einmal holt.
Es wird hold and wait entkräftet, weil die Zutatenkisten nun auf einmal und nicht schrittweise geholt werden.
●
●
●
–
Dieses Verfahren ist ineffizient:
ein Koch wartet auf eine Kiste (er blockiert den Kühlschrank)
währenddessen wollen andere Köche Zutaten holen
Dies ist aber nicht möglich, selbst wenn die Zutaten im Kühlschrank vorhanden sind, da dieser blockiert ist!
→ Köche müssen unnötig warten
–
●
5
Programmierung in C – Teil a)
Grundstruktur der work()-Funktion
●
void *work(void *arg) {
void *work(void *arg) {
int my_num = *((int*) arg);
int my_num = *((int*) arg);
for (int i = 0; i < MEAL_PER_CHEF; i++) {
for (int i = 0; i < MEAL_PER_CHEF; i++) {
ingredient_t *meal[MEAL_SIZE];
ingredient_t *meal[MEAL_SIZE];
}
pthread_exit(NULL);
pthread_exit(NULL);
}
}
}
}
get_meal(meal);
get_meal(meal);
for (int j = 0; j < MEAL_SIZE; j++) {
for (int j = 0; j < MEAL_SIZE; j++) {
if (sem_wait(&(meal[j]->sem))) //Fehlerbehandlung if (sem_wait(&(meal[j]->sem))) //Fehlerbehandlung
sleep(meal[j]->time_needed); //Fehlerbehandlung sleep(meal[j]->time_needed); //Fehlerbehandlung
}
}
for (int j = 0; j < MEAL_SIZE; j++) {
for (int j = 0; j < MEAL_SIZE; j++) {
if (sem_post(&(meal[j]->sem))) //Fehlerbehandlung if (sem_post(&(meal[j]->sem))) //Fehlerbehandlung
}
6
void *work(void *arg) {
void *work(void *arg) {
}
pthread_exit(NULL);
pthread_exit(NULL);
}
//…
//…
for (int i = 0; i < MEAL_PER_CHEF; i++) {
for (int i = 0; i < MEAL_PER_CHEF; i++) {
ingredient_t *meal[MEAL_SIZE];
ingredient_t *meal[MEAL_SIZE];
}
if (pthread_mutex_lock(&lock)) //Fehlerbehandlung if (pthread_mutex_lock(&lock)) //Fehlerbehandlung
for (int j = 0; j < MEAL_SIZE; j++) //Holen der Kisten wie in a) for (int j = 0; j < MEAL_SIZE; j++) //Holen der Kisten wie in a)
if (pthread_mutex_unlock(&lock)) //Fehlerbehandlung if (pthread_mutex_unlock(&lock)) //Fehlerbehandlung
for (int j = 0; j < MEAL_SIZE; j++) //Verarbeiten wie in a)
for (int j = 0; j < MEAL_SIZE; j++) //Verarbeiten wie in a)
for (int j = 0; j < MEAL_SIZE; j++) //Zurückbringen wie in a)
for (int j = 0; j < MEAL_SIZE; j++) //Zurückbringen wie in a)
}
get_meal(meal);
get_meal(meal);
Programmierung in C – Teil b)
Verklemmungsvorbeugung: Entkräftung von „hold and wait“
●
7
int get_max_wait() {
int get_max_wait() {
int current_max = 0;
int current_max = 0;
for (int i = 0; i < INGREDIENT_NUM; i++) {
for (int i = 0; i < INGREDIENT_NUM; i++) {
if (ingredients[i].time_needed > current_max) { if (ingredients[i].time_needed > current_max) {
current_max = ingredients[i].time_needed; current_max = ingredients[i].time_needed;
}
return current_max * MEAL_SIZE; return current_max * MEAL_SIZE;
}
}
}
}
}
void reset() {
void reset() {
restart = 1;
restart = 1;
for (int i = 0; i < CHEF_NUM; i++) {
for (int i = 0; i < CHEF_NUM; i++) {
if (pthread_equal(chefs[i], pthread_self()) == 0) { if (pthread_equal(chefs[i], pthread_self()) == 0) {
pthread_cancel(chefs[i]); // Fehlerbehandlung pthread_cancel(chefs[i]); // Fehlerbehandlung
}
pthread_exit(NULL);
pthread_exit(NULL);
}
}
}
}
}
Programmierung in C – Zusatzaufgabe c)
Verklemmungsauflösung: Hilfsfunktionen
●
8
void *work(void *arg) {
void *work(void *arg) {
}
pthread_exit(NULL);
pthread_exit(NULL);
}
//...
//...
for (int i = 0; i < MEAL_PER_CHEF; i++) {
for (int i = 0; i < MEAL_PER_CHEF; i++) {
}
for (int j = 0; j < MEAL_SIZE; j++) //Zurückbringen wie in a) for (int j = 0; j < MEAL_SIZE; j++) //Zurückbringen wie in a)
}
//...
//...
for (int j = 0; j < MEAL_SIZE; j++){
for (int j = 0; j < MEAL_SIZE; j++){
struct timespec time;
struct timespec time;
if (clock_gettime(CLOCK_REALTIME, &time)) //Fehlerbehandlung if (clock_gettime(CLOCK_REALTIME, &time)) //Fehlerbehandlung
time.tv_sec += get_max_wait(); time.tv_sec += get_max_wait();
if (sem_timedwait(&(meal[j]->sem), &time)) { if (sem_timedwait(&(meal[j]->sem), &time)) {
if (errno == ETIMEDOUT){reset();} //Fehlerbeh. im else-Fall if (errno == ETIMEDOUT){reset();} //Fehlerbeh. im else-Fall
for (int j = 0; j < MEAL_SIZE; j++) //Verarbeiten wie in a)
for (int j = 0; j < MEAL_SIZE; j++) //Verarbeiten wie in a)
}
}
Programmierung in C – Zusatzaufgabe c)
Verklemmungsauflösung: nur gewisse Zeit warten
●
9