Inhaltsverzeichnis

Passives vs. aktives Warten
Synchronisationsobjekte
- Boolesche Synchronisation (Lock, manchmal Mutex)
- Semaphoren
Schlafen auf Zeit
Leerlauf
- Tickless Kernel

Die zu implementierenden Synchronisationsobjekte sind grundlegend verschieden von den bereits programmierten Mechanismen Interrupts auszuschalten oder dem Guard. Während letztere auf der unteren Ebene die Konkurrenz zwischen ISRs und normalem Kontrollfluss, bzw. zwischen Prozessoren lösen, erlauben Synchronisationsobjekte den gegenseitigen Ausschluss zwischen Nutzerthreads. Für die Implementierung wird dennoch der Guard benötigt, da innerhalb der Synchronisationsobjekte kritische Abschnitte existieren, die mit den bestehenden Mechanismen geschützt werden müssen.

Letztlich bauen wir uns also auf Basis der bestehenden Synchronisierungsmechanismen einen neuen, der aber besser für Threads geeignet ist, weil er passives Warten erlaubt.

Synchronisation auf verschiedenen Ebenen des Systems

Passives vs. aktives Warten

Bereits implementierte Primitive wie das Spinlock oder das Ticketlock, welche für den gegenseitigen Ausschluss zwischen Prozessoren verwendet werden, warten aktiv in einer Schleife darauf, dass sich ein Wert ändert. Während sie auf die Freigabe des kritischen Abschnitts warten, kann kein anderer Kontrollfluss übernehmen, da der Dispatcher, der den Kontrollflusswechsel realisieren würde, selbst wieder auf das Spin-/Ticketlock angewiesen ist.

Beim passiven Warten auf eine Semaphore oder ein Lock kann bzw. muss der wartende Thread hingegen von anderen Threads verdrängt werden. Der wartende Thread wird nicht wieder ins Scheduling eingebracht, bis die Wartebedingung erfüllt ist. Somit kann das System mehr Fortschritt machen, als wenn der wartende Thread aktiv auf die Bedingung warten würde. In einem kooperativen Scheduling müssten wartende Threads die Kontrolle abgeben und dürfen nicht mehr eingeplant werden, bis die Bedingung erfüllt ist.

Aktives Warten kann auch in manchen Fällen für Nutzerapplikationen sinnvoll sein, da passives Warten einen Kontextwechsel provoziert, der u.U. teurer ist, als (kurz) aktiv zu warten.

Synchronisationsobjekte

Boolesche Synchronisation (Lock, manchmal Mutex)

Ein sehr einfaches Synchronisationsobjekt ist das Lock. Das Lock besteht aus einer booleschen Variable, die gesetzt wird, wenn der kritische Abschnitt betreten wird, und zurückgesetzt wird, wenn er verlassen wird. Der Zugriff auf die boolesche Variable muss gegen Race Conditions geschützt werden. Ist das Lock genommen, muss der Thread solange warten, bis der besitzende Thread es wieder frei gibt.

Semaphoren

Ein allgemeineres Konzept als das Lock ist die Semaphore. Mit Semaphoren können boolesche Locks ausgedrückt werden. Eine Semaphore beinhaltet eine Integer-Variable, die herunter (Semaphore::P(), „Prolaag“) und hoch (Semaphore::V(), „Verhoog“) gezählt werden kann. Wird der Zähler beim Eintritt in den kritischen Abschnitt (P()) null, muss der rufende Thread warten. Beim Verlassen des kritischen Abschnitts (V()) wird der Zähler erhöht und ggf. schlafende Threads geweckt. Außerdem kann der Startwert einer Semaphore vorgesetzt werden.

Für Semaphoren gibt es drei Einsatzmöglichkeiten:

Schutz eines kritischen Abschnitts
Signalisierung
Ressourcenbedarf begrenzen

Schutz eines kritischen Abschnitts (Verwendung als Mutex)

Wird der Startwert der Semaphore auf 1 initialisiert und zwischen Threads geteilt, kann sie zum Schutz kritischer Abschnitte, ähnlich wie ein boolesches Lock verwendet werden.

// shared semaphore
Semaphore s = newSemaphore ( 1 );
 
P(S)
// critical section
V(S)

Signalisierung

Eine Semaphore kann auch für die Signalisierung über die Ankunft von Daten verwendet werden. Bspw. könnte der Tastaturtreiber gerade ein neues Zeichen in den Zeichenpuffer gelegt haben. Dann erhöht er die Semaphore um eins, um der Nutzeranwendung anzuzeigen, dass es neue Zeichen im Puffer gibt. Der Nutzerthread wird in die Ready-List aufgenommen, später eingeplant und kann das Zeichen lesen. In einem der nächsten Durchläufe wird er bei der P()-Operation wieder hängen bleiben, wenn keine Zeichen mehr im Puffer sind.

// shared semaphore
Semaphore s = newSemaphore ( 0 );
 
// user thread
void usr_thread () {
    while ( 1 ) {
        s.P();
        // read character
    }
}
 
// keyboard driver
void keyboard_driver ( char newChar ) {
    // put character in buffer
    s.V()
}

Resourcenbedarf begrenzen

In der Kommunikation zwischen Threads könnte ein begrenzter Puffer verwendet werden. Dann kann ein Semaphore auf die Größe des Puffers vorinitialisiert werden. Der Schreiber führt P() aus und verringert damit den Zähler, der die übrigen Speicherplätze angibt. Der Leser kann mit V() wieder Speicher im Puffer freigeben, der bereits gelesen wurde.

#define N 42
int buffer[N];
 
// shared semaphore
Semapore s = newSemaphore ( N );
 
// reader
int reader () {
    int x = buffer[curPos];
    curPos++;
    s.V()
    return x;
}
 
// writer
int writer ( int x ) {
    buffer[curWritePos] = x;
    curWritePos++;
    s.P();
}

Schlafen auf Zeit

Threads wollen manchmal eine gewisse Zeit lang nichts tun. Dafür wird der Bellringer benötigt, der eine Liste von Bells verwaltet. Bells sind jeweils Waitingrooms.

Die Bell wird durch den Threads selbst erstellt, muss aber bei jedem Timer-Interrupt überprüft werden. Da die Überprüfung häufiger als das Einfügen ist, ist es sinnvoll die Datenstruktur so zu entwerfen, dass die Überprüfung sehr schnell ist. Die erstellte Bell kann auf den Stack des schlafen zu legenden Threads gelegt werden, weil wir das Bell-Objekt ohnehin nach dem Aufwachen nicht mehr brauchen.

Leerlauf

Wenn wir immer weiter und weiter Threads schlafen legen, kann es vorkommen, dass keine Threads mehr im System sind, die abgearbeitet werden können. Prozessoren allerdings brauchen immer etwas zu tun oder man muss sie schlafen legen (hlt).

Pro CPU soll deshalb ein IdleThread angelegt werden, der die CPU beschäftigt hält, wenn es nichts mehr zu tun gibt. Idlethreads dürfen niemals in die Ready-List gelangen!

void idle () {
    while (1);
}

Eine Endlosschleife würde funktionieren, tötet aber Eisbären. Daher legen wir den Prozessor lieber schlafen.

Zwischen Einlasten des Leerlaufthreads und der `hlt` Instruktion wird ein Thread ausführbar

Was passiert allerdings, wenn zwischen dem Moment, wo der Idlethread ausgewählt wird, und der ausgeführten hlt Instruktion doch noch ein Thread aktiv wird? Die Zustandsänderung des Threads bekommen wir nicht mit, was zu einer Lost Wakeup Situation führt. Der Prozessor legt sich schlafen, obwohl der Bellringer einen Thread aufgeweckt hat.

Zur Lösung des Problems sei gesagt, dass die Instruktionen sti; hlt; direkt hintereinander dazu führen, dass die beiden Instruktionen atomar ausgeführt werden. So kann zwischen sti und hlt kein Interrupt dazwischenfunken.

Tickless Kernel

Alle Interrupts wecken die CPU wieder auf. Das gilt auch für den Timerinterrupt. Speziell dieser führt aber oft zu einem ungewollten Aufwecken, da die CPU nur aufwacht, um zu prüfen, das immer noch keine Arbeit da ist. Aus diesen Grund bietet es sich an, einen Tickless Kernel zu implementieren, der im Leerlauffall den Timer ausschaltet, bevor die CPU schlafen gelegt wird.

void idle() {
    watch.block();
    CPU::idle();
    watch.unblock();
}

Leider funktioniert dieser Ansatz aber noch nicht ganz, da der Bellringer natürlich ebenfalls den Timer benötigt, um korrekt zu funktionieren. Dieser muss also gesondert behandelt werden.