Übungen zu Systemprogrammierung 2(SP2)
Ü 7 – Ringpuffer
C. Erhardt, J. Schedel, A. Ziegler, J. Kleinöder
Lehrstuhl für Informatik 4Verteilte Systeme und Betriebssysteme
Friedrich-Alexander-UniversitätErlangen-Nürnberg
WS2015 – 11. bis 15. Juni 2015
https://www4.cs.fau.de/Lehre/WS15/V_SP2
27-ABA_handout
Agenda
7.1 Hinweise zur Evaluation7.2 Synchronisation des Ringpuffers7.3 ABA-Problem bei der Verwendung von CAS7.4 Vorteile nicht-blockierender Synchronisation
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer 7–1
27-ABA_handout
Agenda
7.1 Hinweise zur Evaluation7.2 Synchronisation des Ringpuffers7.3 ABA-Problem bei der Verwendung von CAS7.4 Vorteile nicht-blockierender Synchronisation
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.1 Hinweise zur Evaluation 7–2
eval:20
16-01-09
Hinweise zur Evaluation
Bei Kommentaren, die sich auf einen bestimmten Übungsleiterbeziehen, bitte dessen Namen in jedem Feld voranstellen
Kommentarfelder werden in der Auswertung durcheinandergewürfelt
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.1 Hinweise zur Evaluation 7–3
eval:20
16-01-09
Agenda
7.1 Hinweise zur Evaluation7.2 Synchronisation des Ringpuffers7.3 ABA-Problem bei der Verwendung von CAS7.4 Vorteile nicht-blockierender Synchronisation
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–4
27-ABA_handout
Über-/Unterlaufsituationen
Leerer Ringpuffer:
0 11
buf
ri wi
Weiteres Lesen würde noch nicht gefüllten Slot liefern → Unterlauf!
Voller Ringpuffer:
0 11
buf
wi ri
Weiteres Schreiben würde vollen Slot überschreiben → Überlauf!
Synchronisation mit Hilfe zweier Semaphore
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–5
27-ABA_handout
Wettlauf der Leser
Auslesen des Slots und Inkrementieren des Leseindex ri geschiehtnicht atomar
Mehrere Threads könnten nebenläufig den selben Slot auslesen
Es existiert keine Abhängigkeit der Leser untereinander→ Nicht-blockierende Synchronisation möglich
Synchronisation mittels Compare and Swap (CAS)
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–6
27-ABA_handout
Wettlauf der Leser
12
sem_full
0
sem_free0 11
buf
wi ri
Erhöhen des Leseindex mittels CAS – vollständig korrekt?
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.12Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ Erhöhung des Leseindex mittels CAS
0
wibuf
sem_full sem_free
12 0
ri11
int get(void) {int fd, pos, npos;P(sem_full);do { // Wiederhole...
pos = ri; // Lokale Kopie des Werts ziehennpos = (pos + 1) % 12; // Folgewert lokal berechnen
} while(!cas(&ri, pos, npos)); // ... bis CAS erfolgreichfd = buf[pos];V(sem_free);return fd;
}
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–7
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
12
sem_full
0
sem_free0 11
buf
wi ri
Überlaufsituation: Schreiber blockiert, weil keine Slots frei
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.13Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ Überlaufsituation: Schreiber blockiert, weil keine freien Slots verfügbar
0
wibuf
sem_full sem_free
12 0
ri11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;
} while(!cas(&ri, pos, npos));fd = buf[pos];V(sem_free);return fd;
}
W
void add(int val) {P(sem_free);
buf[wi] = val;wi = (wi + 1) % 12;
V(sem_full);}
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–8
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
11
sem_full
0
sem_free0 11
buf
wi ri
R1 sichert sich Leseindex 4, wird nach erfolgreichem CAS verdrängt
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.14Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ R1 sichert sich Leseposition 4, wird nach erfolgreichem CAS verdrängt
0
wibuf
sem_full sem_free
11 0
ri
11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;
} while(!cas(&ri, pos, npos));fd = buf[pos];V(sem_free);return fd;
}
W
void add(int val) {P(sem_free);
buf[wi] = val;wi = (wi + 1) % 12;
V(sem_full);}
R1
pos: 4
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–9
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
10
sem_full
1
sem_free0 11
buf
wi ri
R2 durchläuft get() komplett, entnimmt Datum in Slot 5
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.15Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ R2 durchläuft get() komplett, entnimmt Datum in Slot 5
0
wibuf
sem_full sem_free
10 1
ri
11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;
} while(!cas(&ri, pos, npos));fd = buf[pos];V(sem_free);return fd;
}
W
void add(int val) {P(sem_free);
buf[wi] = val;wi = (wi + 1) % 12;
V(sem_full);}
R1 R2
pos: 4 pos: 5
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–10
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
11
sem_full
0
sem_free0 11
buf
wi ri
W wird deblockiert, komplettiert add() und überschreibt Slot 4
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.16Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ Schreiber W wird deblockiert, komplettiert add(), überschreibt Slot 4
0
wibuf
sem_full sem_free
11 0
ri
11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;
} while(!cas(&ri, pos, npos));fd = buf[pos];V(sem_free);return fd;
}
W
void add(int val) {P(sem_free);
buf[wi] = val;wi = (wi + 1) % 12;
V(sem_full);}
R1 R2
pos: 4 pos: 5
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–11
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
11
sem_full
0
sem_free0 11
buf
wi ri
Ursache: FIFO-Entnahmeeigenschaft des Puffers nicht sichergestellt
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.17Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ Problem: FIFO-Entnahmeeigenschaft nicht sichergestellt
0
wibuf
sem_full sem_free
11 0
ri
11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;
} while(!cas(&ri, pos, npos));fd = buf[pos];V(sem_free);return fd;
}
W
void add(int val) {P(sem_free);
buf[wi] = val;wi = (wi + 1) % 12;
V(sem_full);}
R1 R2
pos: 4 pos: 5
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–12
27-ABA_handout
Wettlauf der Leser Vorsicht bei CAS!
10
sem_full
2
sem_free0 11
buf
wi ri
Lösung: Entnahme des Datums innerhalb der CAS-Schleife
Systemprogrammierung — Übungen© Michael Stilkerich, Jens Schedel, Christoph Erhardt • Universität Erlangen-Nürnberg • Informatik 4, 2012 U06.fm 2012-06-26 10.28
U6.18Reproduktion jeder Art oder Verwendung dieser Unterlage, außer zu Lehrzwecken an der Universität Erlangen-Nürnberg, bedarf der Zustimmung des Autors.
SP
- Ü
U6-1 Synchronisation eines Ringpuffers
4 Wettlauf der Leser
■ Lösung: Entnahme des Datums vor Durchführung von CAS
0
wibuf
sem_full sem_free
10 2
ri
11
int get(void) {int fd, pos, npos;P(sem_full);do {
pos = ri;npos = (pos + 1) % 12;fd = buf[pos]; // Datum bereits vorsorglich entnehmen
} while(!cas(&ri, pos, npos));V(sem_free);return fd;
}
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–13
27-ABA_handout
Brauchen wir das volatile-Schlüsselwort?
Schreibindex
Szenario: nur ein Produzenten-ThreadKein nebenläufiger Zugriff auf den Schreibindexvolatile nicht erforderlich
Leseindex
Szenario: mehrere Konsumenten-Threads möglichNebenläufiger Zugriff auf den Leseindex möglichGCC-Doku: [__sync_bool_compare_and_swap() is] considered afull barrier. That is, no memory operand will be moved across theoperation, either forward or backward. Further, instructions will beissued as necessary to prevent the processor from speculating loadsacross the operation and from queuing stores after the operation.volatile also nicht falsch, aber nicht zwangsläufig erforderlich
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.2 Synchronisation des Ringpuffers 7–14
27-ABA_handout
Agenda
7.1 Hinweise zur Evaluation7.2 Synchronisation des Ringpuffers7.3 ABA-Problem bei der Verwendung von CAS7.4 Vorteile nicht-blockierender Synchronisation
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–15
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
5
T2
r
w
full empty
62 0Aktiver
Thread
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–16
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
5
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–17
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–18
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
5
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–19
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
7
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–20
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
7
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–21
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
7
T2
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–22
27-ABA_handout
ABA-Problem bei der Verwendung von CAS
bbGet() liefert 5 statt 7 zurückCAS schlägt nicht fehl, weil r nach dem Wiedereinlasten des Threadsden selben Wert hat wie vor dessen VerdrängungZwischenzeitliche Wertänderung von r wird nicht erkannt
Grundsätzliches Problem von inhaltsbasierten Elementaroperationenwie CAS
Erhöhte Auftrittswahrscheinlichkeit, je kleiner der Puffer und jehöher die Systemlast
Gegenmaßnahmen siehe Vorlesung C | X-4 S. 24ff.
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–23
27-ABA_handout
ABA-Problem in den Griff bekommen
Einführen eines Generationszählers, der bei jeder erfolgreichenOperation inkrementiert wird
ABA-Situation: Leseindex hat nach Umlaufen des Ringpufferswieder den alten Wert – aber Generationszähler hat anderen Wert→ CAS schlägt fehl
Möglichkeit 1: separate ZählvariableErfordert Double-Word-CAS
Möglichkeit 2: eingebetteter GenerationszählerNutzung der oberen Bits des Leseindex
Keine hundertprozentige Sicherheit möglich:Generationszähler hat begrenzten Wertebereich und kann überlaufenJe nach Größe des Zählers und konkretem Szenario (hoffentlich)ausreichend unwahrscheinlich
c© ce, js, az, jk SP2 (Ü 7 | WS 2015) 7 Ringpuffer | 7.3 ABA-Problem bei der Verwendung von CAS 7–24
27-ABA_handout
Agenda
7.1 Hinweise zur Evaluation7.2 Synchronisation des Ringpuffers7.3 ABA-Problem bei der Verwendung von CAS7.4 Vorteile nicht-blockierender Synchronisation
c© ce, js, az, jk SP2 (Ü 7 | WS2015) 7 Ringpuffer | 7.4 Vorteile nicht-blockierender Synchronisation 7–25
27-ABA_handout
Vorteile nicht-blockierender Synchronisation
Vorteile gegenüber sperrenden oder blockierenden Verfahren(Auswahl):
Rein auf Anwendungsebene, keine teuren SystemaufrufeGeringere Mehrkosten als bei Locking, wenn die CAS-Operation aufAnhieb funktioniertKonkurrierende Fäden werden vom Scheduler nach dessen KriterieneingeplantDurch Locks wird eine Abhängigkeit vom Halter des Locks geschaffen:
Halter des Locks wird möglicherweise im kritischen Abschnitt verdrängtDer „Zweite“, „Dritte“ usw. werden durch den „Ersten“ verzögert
In unserem konkreten Anwendungsbeispiel kommen diese Vorteilenicht wirklich zum Tragen
Übungsbeispiel zum Begreifen des Konzepts
c© ce, js, az, jk SP2 (Ü 7 | WS2015) 7 Ringpuffer | 7.4 Vorteile nicht-blockierender Synchronisation 7–26
27-ABA_handout