TUD Logo

TUD Startseite » ... » Lehre » Verteilte Betriebssysteme » Parallele Architekturen

Betriebssysteme

Übung: Parallele Architekturen

In der Übungstunde werden alle Lösungen von Studenten vorgeführt. Bitte erscheinen Sie für alle Fragen vorbereitet, da die Übung sich auf Diskussion konzentriert, nicht auf das Verstehen der Fragen und Zusammentragen des Wissens. Einige anspruchsvolle Fragen sind in der Regel deutlich schwieriger und erfordern oft die Aneignung von Wissen, das nicht in der Vorlesung gebracht wurde.

1. Lock-frei

Implementieren Sie 2-Adressen-Compare-and-Swap mit Hilfe von Compare-and-Swap.

2. Cache-Kohärenz und Locks

Cache-Kohärenz ist teilweise ein kritischer Skalierungsfaktor für Lock-Implementierungen, da sie unnötige Bus-Nachrichten erzeugen und somit die Abarbeitung des CPUs verlangsamen.

2.1. Test-and-Set Locks

Die in der Vorlesung besprochenen Test-and-Set Locks haben ein Skalierungsproblem durch ihre exclusiven Schreibzugriffe auf die Lockvariable selbst wenn der kritische Bereich, gerade belegt ist.

Eine möglich Implementierung eines Test-and-Set Locks sieht wie folgt aus:

class TSLock {
   private:
    unsigned int _lock

   public:
    TSLock() : _lock(0) {}

    void lock() {
        while (test_and_set(_lock) == 1) {}
    }

    void unlock() {
        _lock = 0;
    }
};

Überprüfen Sie die in der Vorlesung getroffene Aussage, indem Sie die unten stehende Tabelle vervollständigen.

Die erste Spalte gibt an, welcher CPU gerade eine Instruktion ausführt. Spalte 2 gibt die ausgeführte Operation an. Spalte 3 gibt an wie der Zustand der Lockvariable nach Ausführung der Instruktion. Die nächsten 4 Spalten enthalten den MESI Zustand der Cachezeile der Lockvariable für den jeweiligen Prozessors.

CPU Operation Lock P1 P2 P3 P4
0 I I I I
1 lock (T&S) 1 M I I I
2 wait (T&S) 1 I M I I
4 wait (T&S) 1 I I I M
2 wait (T&S)
3 wait (T&S)
4 wait (T&S)
3 wait (T&S)
1 unlock
3 lock (T&S)
2 wait (T&S)
4 wait (T&S)
3 unlock
2 lock (T&S)
4 wait (T&S)
4 wait (T&S)
2 unlock

2.2. Test-Test-and-Set Locks

In der Vorlesung wurde eine Erweiterung des Test-and-Set Locks vorgestellt, der eine zusätzliche Test-Operation vor dem blockieren des Locks ausführt.

Eine möglich Implementierung eines Test-Test-and-Set Locks sieht wie folgt aus:

class TTSLock {
   private:
    unsigned int _lock

   public:
    TTSLock() : _lock(0) {}

    void lock() {
        while (true) {
            while (_lock == 1) {}

            if (test_and_set(_lock) == 0)
                break;
         }
    }

    void unlock() {
        _lock = 0;
    }
};

Wiederholen sie die obige Aufgabe unter Berücksichtigung der zusätzlichen Test-Operation des Test-Test-and-Set Locks. Berücksichtigen Sie, dass die Test-Operation nur ein normaler Lesezugriff ist.

CPU Operation Lock P1 P2 P3 P4
0 I I I I
1 test 0 E I I I
2 test 0 S S I I
1 lock (T&S) 1 M I I I
2 lock (T&S)
3 wait
4 wait
2 wait
3 wait
4 wait
1 unlock
3 test
3 lock (T&S)
2 wait
4 wait
3 unlock
2 test
4 test
2 lock (T&S)
4 lock (T&S)
4 wait
4 wait
2 unlock

2.3. False Sharing

In der letzten Übung wurde false sharing (unechte gemeinsame Nutzung) besprochen. Beschreiben Sie kurz die Auswirkungen, wenn bei zwei unabhängige Lockvariablen l1 und l2 in der selben Cacheziele liegen.

3. Skalierbare Leser-Schreiber-Locks

Faire Leser-Schreiber-Locks schützen einen kritischen Abschnitt so, dass mehrere Leser den kritischen Abschnitt gleichzeitig betreten können, solange kein Schreiber das Lock hält oder an diesem blockiert. Zu jedem Zeitpunkt darf höchstens ein Schreiber im kritischen Abschnitt sein, aber auch nur, wenn keine Leser im kritischen Abschnitt sind.

3.1. Implementierung eines Leser-Schreiber Locks

Implementieren Sie ein Leser-Schreiber-Lock mit Hilfe der atomaren Read-Modify-Write-Instruktionen aus der Vorlesung. Stellen Sie sicher, dass das Lock fair ist. Das heißt, sowohl Leser als auch Schreiber erhalten nach begrenzter Zeit das Lock.

3.2. Faires schnelles skalierbares Leser-Schreiber Lock

In ihrer Arbeit "A Fair Fast Scalable Reader-Writer Lock", präsentieren Krieger et al. eine skalierbare Leser-Schreiber-Lock-Implementierung basierend auf dem in der Vorlesung besprochenen MCS-Lock.

  1. Suchen Sie nach Tippfehlern in der readerUnlock-Funktion und korrigieren Sie sie. Begründen Sie, warum ein Fehler vorliegt. Wenn Sie keinen Fehler finden, begründen Sie, warum die Funktion korrekt ist.
  2. Beschreiben Sie, wie die readerUnlock-Funktion arbeitet.
  3. Anspruchsvolle Frage: Die Leser-Schreiber-Lock-Implementierung ist fair, obwohl eigentlich unfaire Spinlock-Implementierungen in der Funktion readerUnlock verwendet werden. Warum?

Materialien

Stand: 16.6.2016, 14:39 Uhr
Autor: Dr.-Ing. Marcus Völp

Kontakt
Dr.-Ing.
Carsten Weinhold

Tel.: 463 38056
Fax: 463 38284
E-Mail-Kontaktformular

Regelungen
  • ModuleModule: INF-BI-1, INF-BAS4, INF-VERT4, DSE-E3
  • Credits6 Leistungspunkte
  • 2/1/0 = 3 SWS
Zeit und Ort
  • Vorlesung, wöchentlich
    TimeMo, 11:10 Uhr PlaceAPB E008
  • Übung, zweiwöchentlich
    TimeDi, 9:20 Uhr PlaceAPB E006
Mailingliste