6.5. Kritische Abschnitte sichern

Der Schutz kritischer Abschnitte innerhalb des Betriebssystemkerns gehört zu den diffizilsten Aspekten der Kernelprogrammierung. Damit ein solcher Schutz bei zugleich effizientem Code gewährleistet werden kann, gibt Linux dem Treiberprogrammierer einen Satz ganz verschiedener Funktionen an die Hand.

Kritische Abschnitte entstehen immer dann, wenn Parallelität stattfindet. Konkurrieren beispielsweise zwei Rechenprozesse um ein Betriebsmittel, liegt ein kritischer Abschnitt vor. Ebenso, wenn zwei Prozesse auf die gleiche Datenstruktur zugreifen. Oder auch, wenn sich zwei Prozesse synchronisieren.

Bleiben kritische Abschnitte unbeachtet bzw. ungeschützt, kommt es zur so genannten Race Condition. Bei einer Race Condition hängt das Ergebnis einer Operation vom aktuellen Prozessfortschritt – und damit letztlich vom Zufall – ab.

In vorherigen Linuxversionen waren Kernelfunktionen nicht unterbrechbar. Weniger Parallelität und somit auch weniger zu schützende kritische Abschnitte waren die Folge. Nur beim Schreiben von Code für Multiprozessorsysteme hatte man sich detailliert mit dem Thema auseinander zu setzen. Diese Situation hat sich inzwischen grundlegend geändert: Bedingt durch die zunehmenden Anforderungen nach besseren Echtzeiteigenschaften sind in 2.6 Systemfunktionen unterbrechbar. Darüber hinaus stellt die Mehrprozessormaschine keine Ausnahme mehr dar. Der Treiberentwickler muss inzwischen zu beinahe jedem Zeitpunkt davon ausgehen, dass Funktionen real (SMP) oder zumindest quasi (UP) parallel ablaufen. Damit hat das Thema »Schutz kritischer Abschnitte« für die Kernelprogrammierung enorm an Bedeutung gewonnen.

Das Zauberwort, mit dem kritische Abschnitte geschützt und Race Conditions verhindert werden sollen, heißt »gegenseitiger Ausschluss«. Parallelität hin oder her – der Zugriff auf Daten ist jederzeit nur einer Instanz gestattet. Konkurrieren mehrere miteinander, werden sie der Reihe nach abgefertigt. Das funktioniert nur, wenn sich alle Beteiligten kooperativ verhalten.

Kernel 2.6 stellt zum Schutz kritischer Abschnitte die folgenden Mechanismen zur Verfügung:

6.5.1. Atomare Operationen

Jeder Zugriff auf ein globales Objekt kann ein kritischer Abschnitt sein, unabhängig davon, ob das Objekt schlichtweg eine einfache Variable oder ein komplexer Datensatz ist. Zur Absicherung einfacher Variablenzugriffe sind die atomaren Operationen ideal. Der Betriebssystemkern garantiert, dass atomare Operationen in jedem Fall unteilbar und in einem Zug stattfinden. Sie werden weder durch einen Interrupt unterbrochen noch bei einem SMP-System parallel abgearbeitet. Um die Datentypen verwenden zu können, muss die Header-Datei <asm/atomic.h> inkludiert werden.

Abbildung 6-7. Race Condition beim Zugriff auf eine gemeinsam genutzte Variable

Der Zugriff auf eine gemeinsam genutzte Variable vollzieht sich zumeist in 3 Schritten:

  1. Kopie der Variable in ein internes Prozessorregister lesen.

  2. Operation auf das Prozessorregister ausüben.

  3. Inhalt des Prozessorregisters in die Variable zurückschreiben.

In Abbildung Race Condition beim Zugriff auf eine gemeinsam genutzte Variable ist dargestellt, wie es bei einem derartigen Zugriff zu einer Race Condition kommen kann, falls diese drei Schritte nicht atomar (unteilbar) ablaufen. Zwei unabhängige Codestücke wollen hier die Variable GlobalVar inkrementieren. Nachdem Codestück 1 den Wert der Variablen ins Prozessorregister kopiert hat, wird die Bearbeitung unterbrochen und Codestück 2 wird abgearbeitet. Codestück 2 kopiert ebenfalls den Wert von GlobalVar in ein internes Prozessorregister. Danach erhöhen beide den Inhalt ihres Prozessorregisters und schreiben einer nach dem anderen den Wert zurück. Jetzt weist die Variable aber nicht – wie erwartet – den Wert sieben auf, sondern den falschen Wert sechs.

Um in diesem Fall das richtige Ergebnis zu erhalten, müssen beide Codestücke ungeteilt (atomar) und nacheinander abgearbeitet werden. Dazu stellt Linux atomare Operationen zum Lesen, Schreiben oder Modifizieren zur Verfügung. Es gibt sie sowohl für Integer-Variablen (atomare Integer-Operationen) als auch für Bitwerte (atomare Bit-Operationen). Sämtliche atomare Operationen sind in Tabelle Atomare Operationen in der Übersicht dargestellt.

Tabelle 6-1. Atomare Operationen in der Übersicht

Integer-OperationenBit-Operationen
int atomic_read(atomic_t *v); void set_bit(int nr, volatile unsigned long * addr);
int atomic_set(atomic_t *v, int i); void clear_bit(int nr, volatile unsigned long * addr);
int atomic_add(int i, atomic_t *v); void change_bit(int nr, volatile unsigned long * addr);
int atomic_sub(int i, atomic_t *v); int test_and_set_bit(int nr, volatile unsigned long * addr);
int atomic_inc(atomic_t *v); int test_and_clear_bit(int nr, volatile unsigned long * addr);
int atomic_dec(atomic_t *v); int test_and_change_bit(int nr, volatile unsigned long* addr);
int atomic_sub_and_test(int i, atomic_t *v); int test_bit(int nr, const volatile void * addr);
int atomic_inc_and_test(atomic_t *v);  
int atomic_dec_and_test(atomic_t *v);  
int atomic_add_negative(int i, atomic_t *v);  

Atomare Integer-Operationen. Atomare Integer-Operationen (<asm/atomic.h>) arbeiten auf dem Datentyp atomic_t, einem der wenigen Typedefs im Linux-Kernel. Dieser Datentyp war aus Gründen der Portabilität bis Kernel 2.6.3 auf maximal 24 Bit ausgelegt; ab 2.6.3 können alle 32 Bit der atomaren Variable verwendet werden. Mit der Funktion ATOMIC_INIT kann eine atomare Integer-Variable initialisiert werden:

atomic_t index = ATOMIC_INIT(0);

Mit der Funktion atomic_read lässt sich ein Wert lesen; atomic_set schreibt einen Wert. In beiden Fällen wird ein Pointer auf die Variable übergeben.

    atomic_set( &index, 4 );
    old_index=atomic_read( &index );

Zur Addition dient die Funktion atomic_add, zur Subtraktion atomic_sub. In beiden Fällen muss wieder ein Zeiger auf die atomare Integer-Variable übergeben werden.

    atomic_add( 2, &index );
    ...
    atomic_sub( 3, &index );

Soll die Variable nur inkrementiert bzw. dekrementiert werden, kann der Treiberentwickler auf die zugehörigen Funktionen atomic_inc bzw. atomic_dec zurückgreifen.

    atomic_inc( &index );
    atomic_dec( &index );

Darüber hinaus stehen auch komplexere Operationen zum gleichzeitigen Verändern und Testen des Variablenwertes zur Verfügung. Die Funktion atomic_sub_and_test subtrahiert den übergebenen Wert von der Atomic-Variablen und gibt »wahr« (true, nicht 0) zurück, falls das Ergebnis »0« ist. In den übrigen Fällen wird »falsch« (false, 0) zurückgegeben.

    if( atomic_sub_and_test( 5, &index ) ) {
        pr_info( "5 Plaetze sind frei\n" );
    }

Soll wiederum nur dekrementiert werden, kann die Funktion atomic_dec_and_test verwendet werden. Zum Inkrementieren ist die Funktion atomic_inc_and_test bestimmt.

    if( atomic_dec_and_test( &index ) ) {
        pr_debug( "Feld ist jetzt leer.\n" );
    }
    ...
    while( atomic_inc_and_test( &index )==0 ) {
        pr_debug( "Index ist negativ!\n");
    }

Die Funktion (atomic_add_negative) schließlich addiert einen Wert auf die atomare Integer-Variable auf und testet das Ergebnis daraufhin, ob es negativ ist oder nicht. Bei einem negativen Ergebnis wird »wahr« zurückgegeben. Ist das Ergebnis gleich oder größer als Null, wird »falsch« returniert.

    if( atomic_add_negative( 7, &index ) ) {
        pr_debug( "... immer noch negativ!\n" );
    }

Atomare Bit-Operationen. Atomare Bit-Operationen dienen vorwiegend dem Aufbau dedizierterer Schutzkonzepte. Sie sind in der Header-Datei <asm/bitops.h>definiert.

Wie der Name bereits verrät, werden atomare Bit-Operationen ausschließlich auf einzelne Bits einer (meist 32-Bit-)Variablen angewendet. Die Bits werden dabei von 0 (niederwertigstes Bit) bis 31 (höchstwertigstes Bit) durchgezählt.

Die Funktion set_bit setzt ein Bit, gelöscht wird es mit clear_bit.

    unsigned long bitvar;

    set_bit( 5, &bitvar ); // setzt das 6. Bit (Nr. 5) der Variable bitvar
    clear_bit( 2, &bitvar ); // löscht das 3. Bit (Nr.2)

Ein Bit kann durch Aufruf der Inlinefunktion change_bit getoggelt werden (ist das Bit vor Aufruf der Funktion »1«, wird es gelöscht; ist es gelöscht, wird es gesetzt).

Die Funktion test_and_set_bit gibt den Zustand des ausgewählten Bits zurück, bevor dieses gesetzt wird. Am Ende der Funktion ist das Bit immer gesetzt, unabhängig davon, ob es zuvor bereits gesetzt war oder nicht. War das Bit vorher »0«, gibt die Funktion »0« zurück, ansonsten »nicht 0«.

    while (test_and_set_bit(TASKLET_STATE_SCHED, &t->state)) {
        do
            yield();
        while (test_bit(TASKLET_STATE_SCHED, &t->state));
    }

Die Funktion test_and_clear_bit gibt den Zustand des ausgewählten Bits zurück, bevor dieses – unabhängig von seinem vorigen Zustand – gelöscht wird. War das Bit vor dem Löschen bereits »0«, gibt die Funktion auch »0« zurück, ansonsten »nicht 0«.

Die Funktion test_and_change_bit schließlich testet das Bit und toggelt es anschließend. Auch hier stellt der Returnwert den Wert des ausgewählten Bits vor der Operation dar.

Ein Bit zu überprüfen, ohne dass es geändert wird, ermöglicht das Makro test_bit.

6.5.2. Semaphore

Abbildung 6-8. Kritischer Abschnitt beim Zugriff auf eine Liste

Abbildung Kritischer Abschnitt beim Zugriff auf eine Liste zeigt, wie es beim Zugriff auf eine globale Liste zu einer Race Condition kommen kann. Ist das zu schützende Objekt mehr als 32 Bit breit oder handelt es sich gar um eine komplexe Datenstruktur (wie die Liste), müssen andere Methoden weiterhelfen. Dem Applikationsprogrammierer könnten hier die vom Niederländer Dijkstra konzipierten Semaphore einfallen.

Ein Semaphor ist nichts weiter als eine Integer-Variable, für die die beiden Operationen P und V definiert sind. Sie ist zunächst mit einem positiven Wert vorinitialisiert, der vor dem Betreten des kritischen Abschnittes dekrementiert wird. Weist die Variable nun einen Wert gleich oder größer Null auf, darf der kritische Abschnitt betreten werden. Ist der Wert hingegen kleiner als Null, wartet der Prozess so lange, bis die Variable den Wert Null angenommen hat. Diese Operation, die vor dem Betreten des kritischen Abschnitts ausgeführt wird, ist die P-Operation (P steht hierbei für das niederländische »passeren«, was soviel bedeutet wie durchmarschieren). Verlässt ein Prozess einen kritischen Abschnitt wieder, wird die so genannte V-Operation ausgeführt (vom niederländischen »vrijgeven«, freigeben): Die Variable wird inkrementiert. Gibt es Prozesse, die noch darauf warten, den kritischen Abschnitt betreten zu dürfen, wird zumindest einer dieser Prozesse geweckt.

Abbildung 6-9. Einsatz eines Semaphors

Der Initialwert des Semaphors legt fest, wie viele Instanzen zu einem Zeitpunkt gleichzeitig einen kritischen Abschnitt betreten dürfen. Im Regelfall ist dies genau ein Prozess, so dass das Semaphor mit »1« vorinitialisiert ist. Ein solches Semaphor wird Mutex (von »mutual exclusion«, gegenseitiger Ausschluss) genannt.

Auch wenn der Linux-Kernel keine Prozesse im klassischen Sinn enthält, stehen dem Treiberentwickler Semaphore (<asm/semaphore.h> und <linux/rwsem.h>) zur Verfügung. Die P- und V-Operationen lauten hierbei allerdings down bzw. down_interruptible und up. Die Namenswahl erinnert daran, dass bei der P-Operation die Integer-Variable dekrementiert bzw. bei der V-Operation inkrementiert wird.

Im Unterschied zu down kann down_interruptible den schlafenden Kernel-Thread bzw. die schlafende Treiberinstanz aufwecken, wenn ein Signal eintrifft. In diesem Fall gibt down_interruptible »-EINTR« zurück, ansonsten den Wert »0«.

    if( down_interruptible( &list_mutex )==-EINTR ) {
        return -ERESTARTSYS;
    }

Bevor ein Programm ein Semaphor verwenden kann, muss es es definieren. Zur statischen Definition (durch den Compiler) stehen dem Entwickler die Makros DECLARE_MUTEX, DECLARE_MUTEX_LOCKED und DECLARE_SEMAPHORE_GENERIC zur Verfügung. Als Parameter wird der Name des Mutex bzw. Semaphors übergeben. Beim Semaphor definiert ein zweiter Parameter zusätzlich noch den Initialwert, der bestimmt, wie viele Prozesse sich gleichzeitig im kritischen Abschnitt aufhalten dürfen.

DECLARE_MUTEX( listen_mutex );
__DECLARE_SEMAPHORE_GENERIC( doppel_liste, 2 );

Um ein Semaphor während der Laufzeit zu initialisieren, können die Funktionen init_MUTEX, init_MUTEX_LOCKED oder sema_init verwendet werden.

static struct semaphore listen_mutex;
static struct semaphore doppel_liste;
...
static int __init mod_init(void)
{
    ...
	init_MUTEX( &listen_mutex );
	sema_init( &doppel_liste, 2 );

Neben den vorgestellten (blockierenden) Funktionen sei noch die Funktion down_trylock erwähnt. Sie versucht nicht blockierend, das Semaphor zu akquirieren. Gelingt dies, gibt die Funktion »0« zurück, ansonsten einen Fehlercode. Zum Verlassen des kritischen Abschnitts wird wiederum die Funktion up verwendet.

Ein Semaphor versetzt bei Zugriffskonflikten einen Prozess in den Wartezustand. Warten aber können nur Funktionen, die im Prozess-Kontext abgearbeitet werden. Semaphore lassen sich folglich nicht zum Schutz von Datenstrukturen (bzw. anderer Betriebsmittel) einsetzen, auf die innerhalb von Interrupt-Service-Routinen oder Softirqs (Timer, Tasklets) zugegriffen wird. Sie sind allerdings sehr wohl innerhalb von Kernel-Threads (Workqueue und Event-Workqueue) geeignet.

Beispiel 6-13. Verwendung von Semaphoren in Kernel-Threads

/* vim: set ts=4: */
#include <linux/module.h>
#include <linux/version.h>
#include <linux/init.h>
#include <linux/completion.h>
#include <linux/sched.h>
#include <asm/semaphore.h>

MODULE_LICENSE("GPL");

static int thread_id1=0, thread_id2=0;
DECLARE_COMPLETION( cmpltn );
DECLARE_MUTEX( list_mutex );

static int thread_code( void *data )
{
    unsigned long timeout;
    int i;
    wait_queue_head_t wq;

    daemonize("Thread-Test");
    init_waitqueue_head(&wq);
    allow_signal( SIGTERM ); 
    for( i=0; i<30; i++ ) {
        timeout=HZ;
        if( down_interruptible( &list_mutex )==-EINTR ) {
            pr_debug( "Durch Signal unterbrochen!\n");;
            break;
        }
        // Eigentliche Verarbeitung findet jetzt statt
        timeout=wait_event_interruptible_timeout(wq, (timeout==0), timeout);
        up( &list_mutex );
        printk("Thread %d: woke up ...\n", current->pid);
        if( timeout==-ERESTARTSYS ) {
            pr_debug( "Durch Signal unterbrochen!\n");;
            break;
        }
    }
    complete_and_exit( &cmpltn, 0 );
    return 0;
}

static int __init kthread_init(void)
{
    thread_id1=kernel_thread(thread_code, "Thread1", CLONE_KERNEL);
    if( thread_id1 ) {
        thread_id2=kernel_thread(thread_code, "Thread2", CLONE_KERNEL);
        if( thread_id2 )
            return 0;
        // Init fehlgeschlagen - aufraeumen
        kill_proc( thread_id1, SIGTERM, 1 );
        wait_for_completion( &cmpltn );
    }
    return -EIO;
}

static void __exit kthread_exit(void)
{
    kill_proc( thread_id1, SIGTERM, 1 );
    kill_proc( thread_id2, SIGTERM, 1 );
    wait_for_completion( &cmpltn );
    wait_for_completion( &cmpltn );
}

module_init( kthread_init );
module_exit( kthread_exit );

In Beispiel Verwendung von Semaphoren in Kernel-Threads allozieren zwei (identische) Kernel-Threads ein Semaphor. Der eigentliche kritische Abschnitt besteht nur aus einem Warten – im Normalfall fände hier die eigentliche Operation, zum Beispiel die Modifikation einer Liste, statt. Das im Beispielcode verwendete »Completion-Objekt« wird im Abschnitt Bis zum »Ende« erläutert.

Die bislang vorgestellten Semaphor-Operationen down, down_interruptible sperren ungeachtet dessen, ob Prozesse lesend oder schreibend auf Daten zugreifen wollen, den kritischen Abschnitt. Oftmals ist jedoch nur der konkurrierende schreibende Zugriff kritisch. Vielfach dürfen mehrere Prozesse »einen kritischen Abschnitt betreten«, falls diese keine Modifikationen an Daten durchführen (lesender Zugriff). Das Schreiben aber ist immer nur einem Prozess erlaubt. Da unnötiges Warten die Latenzzeiten des Betriebssystemkerns erhöht, bietet Linux spezielle Semaphore an, die dediziert gemäß lesendem bzw. schreibendem Zugriff verwendet werden können (<linux/rwsem.h>).

Solche Lese-/Schreib-Semaphore sind vom Typ rw_semaphore. Sie werden mit Hilfe der Funktion init_rwsem initialisiert. Soll ein kritischer Abschnitt zum Lesen betreten werden, wird die Funktion down_read aufgerufen. Ein schreibwilliger Prozess ruft down_write auf. Die Gegenstücke zu diesen Funktionen heißen entsprechend up_read bzw. up_write (siehe Beispiel Verwendung eines Lese-/Schreib-Semaphors).

Auch bei den Lese-/Schreib-Semaphoren wurde an die nicht blockierenden Varianten gedacht. Sie heißen down_read_trylock bzw. down_write_trylock. Falls der kritische Bereich betreten werden darf, geben die Funktionen »1« zurück, ansonsten »0«.

Überdies besteht die Möglichkeit, ein zum Schreiben alloziertes Semaphor zu einem Lese-Semaphor herabzustufen. Dazu ist die Funktion downgrade_write aufzurufen.

Beispiel 6-14. Verwendung eines Lese-/Schreib-Semaphors

struct rw_semaphore listen_rwsema;

static int __init mod_init(void)
{
    ...
    init_rwsem( &listen_rwsema );
    ...
}
...
static listen_element *element_lesen( struct liste *root )
{
    down_read( &listen_rwsema );
    ...
    up_read( &listen_rwsema );
}

static listen_element *element_einfuegen( struct liste *root, listen_element *new)
{
    down_write( &listen_rwsema );
    ...
    up_write( &listen_rwsema );
}

6.5.3. Spinlocks

Der Einsatz von Semaphoren funktioniert nur bei Prozessen bzw. Routinen, die im Prozess-Kontext aktiv sind. Oftmals jedoch müssen Treiberprogrammierer kritische Abschnitte schützen, die nicht nur zwischen Treiberinstanzen und Kernel-Threads bestehen, sondern im Zusammenhang mit Interrupt-Service-Routinen stehen. Funktionen im Interrupt-Kontext aber – und das gilt für Hardirqs ebenso wie für Softirqs (Tasklets, Timer) – dürfen nicht passiv warten, das heißt: Sie dürfen sich nicht schlafen legen. Da Semaphore Prozesse schlafen legen wollen, helfen sie in diesem Fall nicht weiter.

Bei Einprozessormaschinen könnte der Entwickler ganz einfach den Interrupt für die Zeit eines Zugriffs sperren (siehe Kapitel Interruptsperre und Kernel-Lock). Ein Beispiel dazu: Bearbeiten ein Kernel-Thread und eine ISR eine globale Liste, sperrt der Kernel-Thread den Interrupt, sobald er den kritischen Abschnitt betritt. Die ISR muss nichts weiter unternehmen, da sie nicht durch den Kernel-Thread unterbrochen werden kann.

Auf Mehrprozessormaschinen greift dieses Verfahren allerdings nicht. Hier können Kernel-Thread und ISR auf jeweils unterschiedlichen Prozessoren laufen, so dass der Kernel-Thread zunächst das Ende der gerade aktiven ISRs auf sämtlichen Prozessoren abwarten müsste, um sie im Anschluss sperren zu können. Für ein auf Effizienz ausgerichtetes Betriebssystem wie Linux ist dies keine Alternative.

Damit bleibt für Mehrprozessorsysteme nur eine Lösung übrig: Aktives Warten. Hierbei wartet die ISR so lange (aktiv), bis der Zugriff auf das gemeinsame Betriebsmittel (wie auf die Liste) durch das andere Codestück abgeschlossen ist. Anstelle zu schlafen und die CPU einem anderen Rechenprozess zur Verfügung zu stellen, wird so lange eine Schleife durchlaufen, bis der kritische Abschnitt frei ist. Eine solche Methode heißt »Spinlocking«, das aktive Warten in der Schleife selbst ist das »Spinning«.

Der Einsatz von Spinlocks zieht folgende Konsequenzen nach sich:

  1. Spinlocks lassen sich nur auf Mehrprozessorsystemen einsetzen.

  2. Um kurze Latenzzeiten zu erreichen, ist der kritische Abschnitt so kurz wie möglich zu halten.

  3. Während eines durch Spinlocks gesicherten Bereichs darf man den zugreifenden Prozess nicht schlafen legen.

Glücklicherweise muss sich der Treiberentwickler um die Differenzierung – Interruptsperre auf Einprozessormaschinen, Spinlocks bei SMP – keine Gedanken machen. Denn tatsächlich kann er in Linux Spinlocks scheinbar auch auf Einprozessormaschinen verwenden. Für ihn transparent expandiert der Compiler die zugehörigen Makros automatisch zu einer einfachen Interruptsperre.

Bei den Spinlocks lassen sich insgesamt drei Varianten unterscheiden, die ihrerseits wiederum in unterschiedlichen Ausprägungen (z.B. mit oder ohne Interruptsperre) auftreten:

  1. Normale Spinlocks,

  2. Lese-/Schreib-Spinlocks und

  3. Sequencelocks, die separat beschrieben werden sollen.

Um einen Spinlock zu verwenden, muss der Entwickler ihn als Objekt definieren und initialisieren. Dazu bindet er in seinen Code zunächst die Header-Datei <asm/spinlock.h> ein. Zur Auswahl stehen die Typdefinitionen spinlock_t und rwlock_t (rw steht hierbei für die Ausprägung eines Read-/Write-Spinlocks). Statisch (vom Compiler) können Spinlocks über das Define SPIN_LOCK_UNLOCKED bzw. RW_LOCK_UNLOCKED initialisiert werden, das Spinlock ist in der Regel also anfänglich frei. Eine Initialisierung zur Laufzeit (also innerhalb einer Funktion) ist über spin_lock_init möglich.

#include <asm/spinlock.h>
...
static spinlock_t list_lock=SPIN_LOCK_UNLOCKED;
static spinlock_t buf_lock; // wird zur Laufzeit initialisiert
static rwlock_t hash_lock=RW_LOCK_UNLOCKED;
...
static int __init mod_init(void)
{
    ...
    spin_lock_init( &buf_lock );
    ...

Die Handhabung von Spinlocks ist zwar prinzipiell einfach (und den Semaphoren ähnlich), allerdings trifft man auf eine Vielzahl von Varianten. Die sicherste ist spin_lock_irqsave. Dieses Makro bekommt neben dem Spinlock noch eine Integer-Variable vom Typ unsigned long für die Speicherung des Interruptflags mit. Nach dem Aufruf des Makros ist das Spinlock im Besitz der aufrufenden Funktion, die damit den kritischen Abschnitt betreten darf. Der kritische Abschnitt wird mit dem Makro spin_unlock_irqrestore wieder verlassen. Das Makro spin_lock_irqsave rettet den Zustand des Interruptflags, sperrt Interrupts auf dem lokalen Prozessor und überprüft schließlich, ob der kritische Abschnitt bereits belegt ist oder nicht. Ist der Abschnitt belegt, wird so lange aktiv gewartet (»gespinnt«), bis er wieder frei ist. Erst wenn der kritische Abschnitt betreten werden kann, beendet sich das Makro.

{
    unsigned long iflags;
    ...
    spin_lock_irqsave( &list_lock, iflags );
    ... // kritischer Abschnitt ist hier
    spin_unlock_irqrestore( &list_lock, iflags );
    ...
}

Noch ein Hinweis: Zur Abspeicherung der Flags (Variable iflag) darf keine globale Variable verwendet werden. Vielmehr muss die Variable zu Beginn der Funktion, die das Spinlock anfordert, definiert werden. Dadurch wird der zugehörige Speicher lokal auf dem Stack angelegt und es wird verhindert, dass auf die Variable außerhalb der entsprechenden Funktion zugegriffen wird.

Wenn der Zustand des Interruptflags genau bekannt ist, können die Spinlock-Makros spin_lock_irq und spin_unlock_irq verwendet werden. Weil hierbei das Flag nicht gerettet werden muss, ist diese Variante leicht effizienter.

    spin_lock_irq( &buf_lock );
    ...
    spin_unlock_irq( &buf_lock );

Eine weitere Variante von Spinlocks lässt Hardwareinterrupts zu, sperrt aber Softirqs. Ihr Name lautet leider nicht spin_lock_softirq, sondern aus historischen Gründen spin_lock_bh respektive spin_unlock_bh. Sollte ein Kernel-Thread mit einem Tasklet oder Treiber um ein Betriebsmittel konkurrieren, nicht aber mit einer ISR, dann ist diese Technik am besten geeignet.

Die letzte Variante so genannter »normaler« Spinlocks schließlich sperrt keine Interrupts (spin_lock und spin_unlock). Das Makro gibt die Kontrolle an die aufrufende Funktion zurück, sobald die Funktion das Spinlock besitzt und mit der Bearbeitung im kritischen Abschnitt beginnen kann. Dieses Paar von Makros darf ähnlich den Semaphoren nur verwendet werden, wenn der kritische Abschnitt von Funktionen verwendet wird, die im Prozess-Kontext (Treiberinstanzen, Kernel-Threads, Workqueues, Event-Workqueue) aktiv sind. Andernfalls könnte es zu einer Verklemmung (Deadlock) kommen, wenn eine Instanz das Lock hält, dann ein Interrupt auftritt und auf dem gleichen Prozessor die Interrupt-Service-Routine bzw. ein Tasklet gestartet wird. Wird dann innerhalb der Interrupt-Service-Routine versucht, das Spinlock zu erhalten, »spinnt« die Interrupt-Service-Routine ununterbrochen und die Instanz, die das Spinlock besitzt, kommt nicht zum Zuge, um den kritischen Abschnitt wieder zu verlassen.

Wie bei Semaphoren auch, verfügen Spinlocks über Lese-/Schreib-Versionen. Die Funktionen für den rein lesenden Zugriff lauten: read_lock, read_unlock, read_lock_irq, read_unlock_irq, read_lock_irqsave, read_unlock_irqrestore, read_lock_bh und read_unlock_bh.

Für den schreibenden Zugriff heißen die Funktionen entsprechend: write_lock, write_unlock, write_lock_irq, write_unlock_irq, write_lock_irqsave, write_unlock_irqrestore, write_lock_bh und write_unlock_bh.

In einem durch einen Spinlock geschützten Abschnitt darf ein Prozess nicht schlafen gelegt werden. Das heißt: Funktionen wie wait_event, schedule_timeout oder kmalloc (zumindest mit der Option GFP_USER) dürfen nicht aufgerufen werden!

Ein typisches Einsatzszenario für Spinlocks ist der Schutz von Ein- bzw. Ausfügeoperationen einzelner Elemente aus einer Liste, wie in Beispiel Kritische Abschnitte bei der Listenverarbeitung vorgeführt. Das dargestellte Kernelmodul erzeugt zwei Kernel-Threads, die jeweils fünf Listenelemente erzeugen und in die gemeinsame Liste einhängen. Danach werden die fünf Elemente direkt wieder aus der Liste entfernt. Da beide Threads auf die Liste zugreifen, muss der jeweilige Zugriff geschützt werden. Da es sich um Kernel-Threads handelt, könnten hier auch Semaphore verwendet werden. Sobald aber eine ISR beteiligt ist, muss auf die Spinlocks zurückgegriffen werden.

Die Liste im Beispielcode wird an zwei Stellen manipuliert. Beide Male wird dieser Bereich durch das Spinlock gesichert. Wichtig ist noch, dass die Funktion kmalloc außerhalb des kritischen Abschnittes aufgerufen wird; schließlich kann diese Funktion den Kernel-Thread schlafen legen – für einen über Spinlock geschützten kritischen Abschnitt undenkbar.

Das Beispiel Kritische Abschnitte bei der Listenverarbeitung verdeutlicht aber auch, wie der Kernel Treiber bei der Listenverarbeitung unterstützt. Meist werden mit Hilfe von Listen Datenstrukturen aneinander gekettet. In die zu verkettende Datenstruktur wird ein Element vom Typ struct list_head als Root-Zeiger eingefügt. Der Root-Zeiger wird entweder statisch mit Hilfe des Makros LIST_HEAD oder dynamisch über INIT_LIST_HEAD initialisiert. Danach können durch Aufruf der Funktion list_add Elemente in die Liste eingehängt werden. Mit list_del werden diese später wieder entfernt.

Das Makro list_for_each_safe schließlich erlaubt den Zugriff auf die einzelnen Listenelemente. Es stellt den Kopf einer for-Schleife dar, die in der Variablen, die als erster Parameter übergeben wurde, den aktuellen Listenzeiger enthält. Um aufgrund des Listenzeigers an die eigentliche Datenstruktur zu gelangen, muss noch das Makro list_entry eingesetzt werden. Allerdings kann auch direkt die Variante list_for_each_entry_safe genutzt werden. Dann enthält die Variable, die als erster Parameter übergeben wurde, die Adresse der eigentlich gesuchten Datenstruktur.

Beispiel 6-15. Kritische Abschnitte bei der Listenverarbeitung

#include <linux/module.h>
#include <linux/init.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Demo für die Listenfunktionen im Linux-Kernel.");

static int thread_id1=0, thread_id2=0;
DECLARE_COMPLETION( cmpltn );
static spinlock_t sl;

struct my_list {
    struct list_head link;
    int counter;
};
struct my_list rootptr;

static int thread_code( void *data )
{
    int i;
    struct my_list *newelement;
    struct list_head *loopvar, *tmp;

    daemonize( (char *)data );
    allow_signal( SIGTERM ); 
    printk("thread_code %d startet ...\n", current->pid );
    for( i=0; i<5; i++ ) {
        // kmalloc darf nicht innerhalb der critical section verwendet werden!
        newelement = kmalloc( sizeof(struct my_list), GFP_USER );
        spin_lock( &sl );
        newelement->counter = i;
        pr_debug( "element: %p- %d\n", newelement, i );
        list_add( &newelement->link, &rootptr.link );
        spin_unlock( &sl );
        printk("Thread %d: left critical section ...\n", current->pid);
    }
    // clean up list
    spin_lock( &sl );
    list_for_each_safe( loopvar, tmp, &rootptr.link ) {
        i = list_entry( loopvar, struct my_list, link )->counter;
        pr_debug( "deleting %p - %d\n", loopvar, i );
        list_del( loopvar );
        kfree( loopvar );
    }
    spin_unlock( &sl );
    complete( &cmpltn );
    return 0;
}

static int __init kthread_init(void)
{
    thread_id1=kernel_thread(thread_code, "Thread1", CLONE_KERNEL);
    INIT_LIST_HEAD( &rootptr.link );
    if( thread_id1 ) {
        thread_id2=kernel_thread(thread_code, "Thread2", CLONE_KERNEL);
        if( thread_id2 )
            return 0;
        // Init fehlgeschlagen - aufraeumen
        kill_proc( thread_id1, SIGTERM, 1 );
        wait_for_completion( &cmpltn );
    }
    return -EIO;
}

static void __exit kthread_exit(void)
{
    kill_proc( thread_id1, SIGTERM, 1 );
    kill_proc( thread_id2, SIGTERM, 1 );
    wait_for_completion( &cmpltn );
    wait_for_completion( &cmpltn );
}

module_init( kthread_init );
module_exit( kthread_exit );

6.5.4. Sequencelocks

Sequencelocks sind mit Kernel 2.6 neu eingeführt worden. Basierend auf Spinlocks, stellen sie eine Abwandlung der Read-Write-Locks dar. Sie sind für kurze kritische Abschnitte, insbesondere für den schnellen Zugriff auf Daten, gedacht und stehen für kurze Latenzzeiten.

Abbildung 6-10. Lesender Zugriff bei Sequencelocks

Die Besonderheit der Sequencelocks liegt darin, einen schreibenden Zugriff sofort zu gewähren. Allenfalls wenn mehrere, voneinander unabhängige Funktionen gleichzeitig schreibend zugreifen wollen, wird aktiv gewartet. Ein lesender Zugriff hingegen blockiert zwar generell nicht, nach dem Zugriff muss aber die Gültigkeit des gerade gelesenen Wertes überprüft werden (siehe Abbildung Lesender Zugriff bei Sequencelocks). Damit ergibt sich für lesende Prozesse beim Zugriff auf den kritischen Abschnitt eine leicht geänderte Softwarestruktur: Hier wird nicht die ansonsten typische Abfolge »Betreten, Zugreifen, Freigeben« abgearbeitet, sondern es wird in einer Schleife so lange gelesen, bis sichergestellt ist, dass der Lesevorgang nicht durch einen Schreibvorgang unterbrochen wurde.

Technisch ist die Identifikation, ob ein Schreibvorgang erfolgte oder nicht, durch einen einfachen Zähler realisiert. Der Zählerwert vor dem Lesen wird mit dem nach dem Lesevorgang verglichen. Sind beide Werte gleich, ist alles im grünen Bereich. Stimmen die Werte jedoch nicht überein, springt der Prozess zum Anfang der Schleife und wiederholt den Lesevorgang.

Um ein Sequencelock verwenden zu können, muss zunächst ein Objekt vom Typ seqlock_t definiert und initialisiert werden. Die Initialisierung kann statisch, durch den Compiler,

    seqlock_t zeit_lock = SEQLOCK_UNLOCKED; // statische Initialisierung
    ...

oder dynamisch, innerhalb einer Funktion

	seqlock_t zeit_lock;          // Definition des Locks
	...
    seqlock_init(&zeit_lock); // Initialisierung zur Laufzeit
erfolgen.

Prototypen und Makros finden Sie in der Header-Datei <linux/seqlock.h>.

Der schreibende Zugriff auf den kritischen Abschnitt ähnelt dem auf Semaphore und »reine« Spinlocks. Er erfolgt über zwei Funktionen: Vor dem eigentlichen Zugriff (Betreten des kritischen Abschnittes) wird die Funktion write_seqlock aufgerufen. Das Ende des Zugriffs wird dem Kernel über die korrespondierende Funktion write_sequnlock (Verlassen des kritischen Abschnittes) mitgeteilt. Schreibt zum gleichen Zeitpunkt bereits ein anderer Prozess auf den kritischen Abschnitt, muss der später kommende so lange warten, bis der Schreibvorgang des Vorgängers abgeschlossen ist.

	write_seqlock_irq(&zeit_lock);
	zeit.tv_sec = value;
	zeit.tv_nsec = 0;
	write_sequnlock_irq(&zeit_lock);

Ein »Warten« – gepaart mit dem Verzicht, den kritischen Abschnitt zu betreten, falls dieser gesperrt ist – kann über die von den Spinlocks her bekannte Funktion write_tryseqlock erreicht werden. Der Rückgabewert der Funktion gibt Aufschluss darüber, ob der kritische Abschnitt betreten werden kann (Rückgabewert »0«) oder bereits ein anderer Prozess schreibend auf die Daten zugreift.

Der lesende Zugriff vollzieht sich nicht analog dem schreibenden Zugriff sequentiell, sondern – wie bereits erwähnt – in einer Schleife. Zunächst muss eine Variable vom Typ »long« definiert werden, die den Zustand des Sequencelocks vor dem lesenden Zugriff aufnimmt. Mit Hilfe der Funktion read_seqbegin lässt sich der Zustand der Variable erfassen. Anschließend erfolgt der lesende Zugriff auf die geschützten Daten. Nach dem Zugriff überprüft die Funktion read_seqretry, ob sich der Zustand des Sequencelocks geändert hat. Ist der Zustand unverändert, kann der Prozess fortfahren. Andernfalls war ein Schreibvorgang aktiv, so dass der Prozess erneut an den Schleifenanfang springt und den Lesezugriff wiederholt.

Innerhalb eines mit Seqlocks geschützten Bereiches werden Daten nicht direkt verarbeitet. Die Technik eignet sich allein dazu, eine Kopie der Daten anzufertigen. Erst nach dem Check, dass diese Kopie in Ordnung ist, kann die eigentliche Verarbeitung (zum Beispiel Ausgabe der Werte) erfolgen.

    unsigned long seq;

    do {
        seq = read_seqbegin(&zeit_lock);
        now = zeit;
    } while( read_seqretry(&zeit_lock,seq) );
	// Jetzt können die Werte in ,,now'' verwendet werden.

Wie Spinlocks verfügen auch die Sequencelocks über unterschiedliche Ausprägungen, nämlich

Während write_seqlock und write_sequnlock einen kritischen Abschnitt schützen können, der von Treiberfunktionen und Kernel-Threads verwendet wird, sind die Funktionen write_seqlock_bh und write_sequnlock_bh notwendig, sobald Softirqs (Tasklets, Timer) beteiligt sind. Die anderen beiden Varianten werden eingesetzt, wenn der Zugriff auf die zu schützenden Daten innerhalb einer Interrupt-Service-Routine erfolgt. Ist dabei der Zustand des IRQ-Flags bekannt, kommen die Funktionen write_seqlock_irq und write_sequnlock_irq zum Einsatz, ansonsten ist das Funktionspaar write_seqlock_irqsave und write_sequnlock_irqrestore zu verwenden.

Werden diese Funktionen für den schreibenden Zugriff verwendet, müssen für den lesenden Zugriff ebenfalls die IRQ-Varianten eingesetzt werden (read_seqbegin_irqsave und read_seqretry_irqrestore).

Innerhalb des Kernels werden Sequencelocks zum Schutz für den Zugriff auf Datenstrukturen, insbesondere der xtime-Struktur verwendet (siehe Kapitel Relativ- und Absolutzeiten).

6.5.5. Interruptsperre und Kernel-Lock

Bei Einprozessorsystemen werden zum Schutz kritischer Abschnitte, die unter anderem von Interrupt-Service-Routinen betreten werden, Interrupts gesperrt. Mit dieser Maßnahme läuft die aktive Funktion ohne Unterbrechung. Da in 2.6 der Schutz kritischer Abschnitte zwischen Ein- und Mehrprozessorsystemen transparent ist, können alternativ auch spinlock-Funktionen kodiert werden.

Dennoch besteht manchmal die Notwendigkeit, dediziert Interrupts zu sperren. Linux bietet hierzu unterschiedliche Funktionen an.

Hardware-Interrupts (Hardirqs) auf der lokalen CPU lassen sich über die Funktion local_irq_disable sperren und über die Funktion local_irq_enable wieder zulassen. Die lokale CPU ist dabei jeweils die CPU, auf der die Funktion local_irq_disable aufgerufen wird. Der Aufruf verhindert allerdings nicht, dass eine andere CPU Interrupts bearbeitet.

Mit Hilfe der Funktionen local_bh_disable und local_bh_enable kann der Treiberentwickler verhindern, dass auf dem aktuellen Prozessor ein Softirq abgearbeitet wird. Mit diesen Funktionen kann nicht verhindert werden, dass auf anderen Prozessoren Softirqs parallel bearbeitet werden. Die Namenswahl dieser beiden Funktionen ist historisch zu sehen, sicherlich wäre local_softirq_disble bzw. local_softirq_enable der geeignetere Name gewesen.

Der Kernel bietet darüber hinaus den so genannten »großen Kernel Lock«. Dabei handelt es sich um einen globalen Spinlock, der zum Schutz kritischer Abschnitt innerhalb des Betriebssystemkerns verwendet wird. Um einen derartigen kritischen Abschnitt zu betreten, muss das Makro lock_kernel aufgerufen werden. Es fordert den Spinlock an, der mit unlock_kernel (Verlassen des kritischen Abschnitts) wieder freigegeben wird.

Lange kritische Abschnitte bzw. das Sperren von Interrupts über einen längeren Zeitraum hinweg verschlechtern das Zeitverhalten des Betriebssystems. Daher sind sie grundsätzlich zu vermeiden.

6.5.6. Synchronisiert warten

Der parallele Zugriff auf globale Variablen stellt die einfachste Form eines kritischen Abschnitts dar. Entsprechend leicht ist es, die Gefahr zu erkennen und mit den bereits vorgestellten Mechanismen zu vermeiden. Anders sieht die Situation aus, wenn es um kritische Abschnitte geht, die aufgrund der Synchronisation zwischen unabhängigen Verarbeitungssträngen entstehen. Dass in vorherigen Kernelversionen einzig der Entwickler für die Synchronisation zuständig war, führte zu vielen Fehlern insbesondere in Treibern. Mit der Einführung spezieller Funktionen (wait_event und wait_event_interruptible) und so genannter »Completion-Objekte« hat die Torvalds'sche Entwicklergemeinde nun für Besserung gesorgt.

6.5.6.1. Immer der Reihe nach

Möchte eine Treiberinstanz Daten lesen oder Daten schreiben, während die Daten noch nicht bereitstehen bzw. noch nicht geschrieben werden können, legt der Treiber im Falle eines blockierenden Zugriffes die zugehörige Treiberinstanz schlafen (Zustand TASK_INTERRUPTIBLE). Sobald die Zugriffe der Treiberinstanz möglich sind, wird sie wieder aufgeweckt.

Der Bereich des Überprüfens, ob der Zugriff (»lesen« oder »schreiben«) möglich ist, sowie das Schlafenlegen stellen einen kritischen Abschnitt dar, der zu schützen ist. Abbildung Beispiel einer Race Condition verdeutlicht die mögliche Race Condition.

Abbildung 6-11. Beispiel einer Race Condition

Direkt nach der Abfrage

    if( no_data_available )
kommt der Interrupt, der signalisiert, dass die Daten zur Verfügung stehen. Daraufhin werden sämtliche Prozesse, die auf die Daten warten, geweckt. Ungünstigerweise legt sich die Treiberinstanz aber erst nach diesem Aufwecken schlafen. Somit schläft der Prozess, obwohl die Daten bereitstehen.

Dieser kritische Abschnitt ist mit Hilfe von Semaphoren und Spinlocks nicht ohne weiteres zu sichern. Aus diesem Grund stellt Linux eigene Funktionen zur Verfügung: wait_event_interruptible und wait_event.

Innerhalb der Funktionen wird sichergestellt, dass die Abfrage und das Schlafenlegen atomar, also unteilbar stattfinden. Die Funktion gibt die Kontrolle erst dann der aufrufenden Routine zurück, wenn die mit dem Aufruf spezifizierte Bedingung erfüllt ist.

Die Funktionen lösen die aus früheren Kernelversionen bekannten Funktionen interruptible_sleep_on und sleep_on ab (siehe Anhang Portierungs-Guide).

6.5.6.2. Bis zum »Ende«

Signalisiert ein Teil des Treibers einem anderen Teil, er möge sich beenden und wartet der erste Teil so lange, bis ihm dieses Ende angezeigt wird, liegt ein typischer, kritischer Abschnitt vor. Wird beispielsweise ein Modul entladen, das einen Kernel-Thread gestartet hat, muss der Kernel-Thread beendet sein, bevor das Modul wirklich entladen wird.

Das zugehörige, fehlerhafte Codefragment könnte folgendermaßen aussehen:

static int kernelthread( void *data )
{
    ...
    if( signal_pending(...) ) {
        wake_up_interruptible(...);
        return 0;
    }
    ...
}

static void __exit mod_exit(void)
{
    kill_proc( thread_id, SIGTERM, 1 );
    interruptible_sleep_on(...);
    ...
}

Nach dem Aufruf der Funktion kill_proc wird der Kernel-Thread aktiv. Die Funktion mod_exit wird aufgeweckt, obwohl sie sich noch gar nicht aktiv schlafen gelegt hat. Daher wird sie sich gleich wieder schlafen legen (interruptible_sleep_on, die Funktion wird es in den folgenden Linux-Versionen nicht mehr geben) und vergeblich auf das Aufwecken durch den Kernel-Thread warten.

Die Sicherung dieses kritischen Abschnittes, insbesondere auch für Multiprozessorsysteme (SMP) ist nicht trivial. Linux bietet hier einen speziellen Satz von Funktionen bzw. Makros an.

Die Synchronisation zwischen den beteiligten Komponenten (im Beispiel der Entladefunktion mod_exit und dem Kernel-Thread) findet über ein Completion-Objekt (struct completion) statt.

Dieses Objekt kann statisch (also durch den Compiler) über das Makro DECLARE_COMPLETION definiert und initialisiert werden. Zur dynamischen Initialisierung innerhalb einer Funktion steht init_completion zur Verfügung.

Die Funktion mod_exit signalisiert dem Kernel-Thread in gewohnter Weise, dass er sich beenden soll. Danach wartet er auf das Ende des Kernel-Threads, indem er die Funktion wait_for_completion aufruft. Da sich im Rahmen dieser Funktion der Prozess schlafen legt, kann die Funktion wait_for_completion nur im Prozess-Kontext verwendet werden.

Sobald sich der Kernel-Thread beendet hat, ruft er die Funktion complete auf. Falls sich ein Kernel-Thread gleichzeitig beenden möchte, muss er die Variante complete_and_exit verwenden. Diese Funktionen wecken den möglicherweise schlafenden Prozess wieder auf.

DECLARE_COMPLETION( on_exit );

...
static int kernelthread( void *data )
{
    ....
    if( signal_pending(current) ) {
        complete( &on_exit );
        return 0;
    }
    ...
    complete_and_exit( &on_exit );
    return 0;
}

static void __exit mod_exit(void)
{
    kill_proc( thread_id, SIGTERM, 1 );
    wait_for_completion( &on_exit );
    ...
}

Zu jedem wait_for_completion gehört genau ein complete. Erfolgt der Aufruf von complete vor dem Warteaufruf, wird dieses im Completion-Objekt registriert. Dabei wird auch mitgezählt, wie oft die Funktion complete aufgerufen wird – entsprechend oft kann wait_for_completion aufgerufen werden. Ohne ein complete wartet der Prozess ewig.

Die Funktion complete weckt genau einen Prozess wieder auf, wenn mehrere Instanzen/Prozesse die Funktion wait_for_completion aufgerufen haben (er weckt zwar mehrere auf, aber bis auf einen legen sich alle anderen gleich wieder schlafen).

6.5.7. Memory Barriers

Eine weitere Ursache für eine Race Condition liegt im so genannten Reordering moderner Compiler und Prozessoren. Solange das Endergebnis einer aus mehreren Befehlen bestehenden Operation identisch bleibt, ist die Reihenfolge der Befehlsabarbeitung ja schließlich egal. Das gilt aber nicht in jedem Fall.

Abbildung 6-12. Race Condition durch Reordering

Eine durch Reordering ausgelöste Race Condition ist auf Einprozessormaschinen nur im Kontext von Hardwarezugriffen zu erwarten. Auf Mehrprozessormaschinen kann dagegen Reordering auch bei normalen Zugriffen zu Problemen führen. Abbildung Race Condition durch Reordering zeigt eine solche Situation. Im Beispiel hängt ein Kernel-Thread ein neues Element in eine globale Liste ein. Vollzieht sich das Einhängen in der richtigen Reihenfolge, kann zu jedem Zeitpunkt ein zweiter Prozess auf die Liste zugreifen. Anders sieht es aus, wenn die Befehle in einer geänderten Reihenfolge abgearbeitet werden. Das Endergebnis als solches ist gleich, auch in diesem Fall ist das Element korrekt eingehängt. Wenn allerdings nach Schritt 2a zum Beispiel ein zweiter Kernel-Thread, der auf einem anderen Prozessor abläuft, auf den Pointer act zugreift, liest er möglicherweise den nicht initialisierten Zeiger des Elementes new aus.

Ein zweites Beispiel für eine Race Condition, die durch ein Reordering hervorgerufen werden kann, ist der Zugriff auf Hardware. Oft ist hier die Reihenfolge entscheidend, mit der Register der Hardware beschrieben werden. So muss beispielsweise erst ein Hardwaredienst beschrieben werden und dann dieser Dienst durch Schreiben auf ein weiteres Register aktiviert werden. Da Compiler und Prozessor diesen Zusammenhang aber nicht kennen, könnten sie reordern. Aus ihrer Sicht enthalten die Hardware-Register nach der Schreiboperation die geforderten Werte.

Der im ersten Beispiel dargestellte kritische Abschnitt kann durch ein Spinlock gesichert und damit die Race Condition verhindert werden. Ein Spinlock ist aber teurer (zeitlich betrachtet), als die Zugriffe in der spezifizierten Reihenfolge auszuführen. Im zweiten Beispiel wäre ein Spinlock erst gar keine Lösung, da die Hardware völlig unabhängig von der Software arbeitet. Reordering zu verhindern ist hier die einzige Lösung.

Um die Befehle in der definierten Reihenfolge abarbeiten zu lassen, können die so genannten Memory Barriers eingesetzt werden. Die Prototypen der zugehörigen Makros befinden sich in der Header-Datei <asm/system.h>. Wird in den Code eine Memory Barrier mit Hilfe des Makros mb eingesetzt, werden vor dem der Barrier nachfolgenden Befehl sämtliche Schreib- oder Leseaufträge durchgeführt.

Memory Barriers lassen sich noch feiner granular einsetzen. Mit Hilfe von rmb werden vor dem nächsten Lesevorgang alle zuvor angestoßenen Lesevorgänge abgeschlossen. Wird eine wmb in den Code eingefügt, werden vor dem nächsten Schreibvorgang sämtliche bereits angestoßenen Schreibaufträge abgearbeitet.

Darüber hinaus hat der Treiberentwickler die Möglichkeit, das Reordering des Compilers nur selektiv auszuschalten. Hierzu dient das Makro barrier. Ein Reordering durch die CPU kann danach immer noch stattfinden. Dieses Makro stellt sicher, dass der Compiler keinen der direkt nachfolgenden Lese- oder Schreibaufträge vor einem bereits erteilten Schreib- oder Leseauftrag ausführt.

6.5.8. Fallstricke

Die Verwendung und insbesondere die richtige Verwendung von Schutzmechanismen kritischer Abschnitte gehört zu den schwierigsten Kapiteln der Treiberentwicklung. Zum einen müssen kritische Abschnitte überhaupt richtig erkannt werden, zum anderen müssen die geeigneten Techniken ausgewählt und korrekt angewendet werden. Die Codefragmente erscheinen zwar recht einfach, sind aber aufgrund der Parallelität der Abläufe sehr komplex.

Die richtige Auswahl und der entsprechende Einsatz von Schutzmethoden sind Voraussetzung für eine gute Absicherung. Welche der vielfältigen Methoden eingesetzt werden kann, lässt sich aufgrund einer Analyse der beteiligten Instanzen ableiten. Sind die Arten der beteiligten Instanzen evaluiert, können die geeigneten Methoden aus Tabelle Der Schutz kritischer Abschnitte aufgrund der beteiligten Instanzen herausgesucht werden.

Gibt es beispielsweise einen kritischen Abschnitt zwischen einer Treiberinstanz und einem Tasklet, können Semaphore nicht eingesetzt werden. Semaphore eignen sich allenfalls für die Absicherung zwischen zwei Prozessen (bzw. Instanzen im Prozess-Kontext). Tabelle Der Schutz kritischer Abschnitte aufgrund der beteiligten Instanzen gibt hier an, dass der Treiberentwickler entweder ein spin_lock_bh oder ein spin_lock_irqsave verwenden darf.

Tabelle 6-2. Der Schutz kritischer Abschnitte aufgrund der beteiligten Instanzen

Semaphore lassen sich verwenden, wenn sämtliche Instanzen, die auf den kritischen Abschnitt zugreifen wollen, im Prozess-Kontext ablaufen. Das gilt für Treiberinstanzen (Funktionen des Kernels, die durch die Applikation getriggert werden) und für Kernel-Threads. Hiervon ausgenommen sind allerdings Workqueues und insbesondere die Event-Workqueue: Da beide von mehreren Subsystemen des Kernels bzw. Treibern genutzt werden, soll hier jegliches »Schlafen« vermieden werden.

Ob normale Semaphore oder Lese-/Schreib-Semaphore eingesetzt werden können, hängt davon ab, ob nur der schreibende Zugriff innerhalb des kritischen Abschnittes vor dem konkurrierenden Zugriff zu sichern ist oder auch der lesende. Da die Lese-/Schreib-Semaphoren wesentlich effizienter sind, gebührt ihnen der Vorzug.

Spinlocks sind grundsätzlich überall verwendbar. Da Spinlocks – im Gegensatz zu den Semaphoren – aktiv warten (busy loop, spinning), sollten mit ihrer Hilfe nur schnell abzuarbeitende (kurze) kritische Abschnitte geschützt werden. Gerade bei Spinlocks gilt es, nur die wirklich kritischen Zugriffe abzusichern. Sobald der Spinlock nicht mehr unbedingt erforderlich ist, wird er wieder freigegeben (lieber häufiger und dafür kürzer). So ist es oft möglich, einen längeren kritischen Abschnitt in mehrere kürzere kritische Abschnitte zu teilen:

	spin_lock( &liste );
	...                   // kritischer Abschnitt, 1. Teil
	spin_unlock( &liste );
	...
	spin_lock( &liste );
	...                   // kritischer Abschnitt, 2. Teil
	spin_unlock( &liste );


Lizenz