Erstellen und Beenden von Prozessen Inhalt Der Scheduler


SMP, Synchronisations- und Locking Mechanismen

SMP

Symmetrical Multiprocessing ist unter Linux seit Kernel 1.3.42 vorhanden. Allerdings ist es erst in diesem Kernel wirklich effektiv implementiert. SMP bedeutet, daß n Prozessoren gleichzeitig in einem System existieren ohne daß einer von die Rolle einer Master CPU einnimmt. Es sind also alle CPUs gleichberechtigt.
Unter Linux kann der Kernel mit SMP Support compiliert werden. Passiert dies wird auf jedem Prozessor ein eigener Scheduler ausgeführt, die sich aus der Runqueue die passenden Prozesse heraussuchen, wie dies passiert werden noch später sehen.
Wie man sich aber unschwer vorstellen kann führt dies zu einigen Problemen bei der Synchronisation. Ein Beispiel:
Prozess a möchte einen eine Variable i erhöhen und anschließend ihren Wert abfragen. Er befindet sich im Kernelmode und hat die Interrupts ausgeschaltet, so daß er weder vom Prozessor verdrängt werden kann, noch durch einen Interrupthandler gestört werden kann. Auf einem Einprozessorsystem würde dies völlig ausreichen, auf einem Multiprozessorsystem allerdings könnte, nachdem er i erhöht hat, ein Prozess auf einem anderen Prozessor auf i wieder dekrementieren und das Auslesen von i würde ein falsches Ergebnis zurückliefern.
Um dies (und andere Synchronisationsprobleme) zu verhindern, gibt es unter Linux verschiedene Synchronisationmechanismen:
  • Atomare Operationen
  • Semaphore
  • und Spinlocks,
die wir uns nun im Detail anschauen wollen.

Atomare Operationen

Hier gibt es zwei verschiedene Arten von atomaren Operationen: auf Bitebene und mit dem struct atomic_t.
Für Bitmaps gibt es hier folgende Operationen:
  • set_bit(): Setzt das Bit an der Stelle nr in der bitmap auf welche adress zeigt.
  • clear_bit(): Löscht ein Bit
  • change_bit(): Dreht ein Bit um
  • test_and_set_bit(): Setzt das Bit und liefert den alten Wert zurück
  • test_and_clear_bit(): Löscht das Bit und liefert den alten Wert zurück
  • test_and_change_bit: Dreht das Bit um und liefert den alten Wert zurück
Für arithmetische Operationen gibt es ebenfalls diverse atomare Operationen:
  • atomic_read(): Gibt den Wert von v zurück
  • atomic_set(): Setzt eine Wert
  • atomic_add(): Addiert i dazu
  • atomic_sub(): Subtrahiert i
  • atomic_sub_and_test(): Subtrahiert und liefert 1 zurück, falls der neue Wert 0 ist, sonst 1
  • atomic_inc(): Erhoeht den Wert um 1
  • atomic_dec(): Dekrementiert den Wert um 1
  • atomic_dec_and_test(): Dekrementiert den Wert und liefert 1 zurück, falls der neue Wert 0 ist, sonst 1
  • atomic_inc_and_test: Erhöht den Wert und liefert 1 zurück, falls der neue Wert 0 ist, sonst 1
  • atomic_add_negative: Addiert i zu v und liefert 1 zurück, wenn der Wert größer negativ ist. Ist er größer oder gleich 0 wird 0 zurückgeliefert.
Damit das oben genannte Beispiel nicht eintritt, während einer dieser Operationen wird ein sogenanntes lock Byte gesetzt. Dies ist ein Assemblerbefehl, der verhindert, daß der Bus während es gesetzt ist von einem anderen Prozess genutzt werden kann. Somit sind diese atomaren Operationen auch in Multiprozessorumgebungen sicher.

Spin Locks

Es gibt Situationen, in denen atomare Operationen nicht mehr ausreichen, wenn z.B. eine größere Anzahl an Instruktionen abgearbeitet werden muß. Hierfür gibt es zwei weitere Mechanismen: Spinlocks und Semaphore. In Einprozessorsystemen reicht es, um die ungestörte Arbeit eines Prozesses zu ermöglichen, sämtliche Interruptflags zu speichern, Interrupts zu verbieten und den kritischen Abschnitt auszuführen. Anschließend müssen lediglich die Flags wieder zurückgeschrieben werden. In Mehrprozessorsystemen sieht dies anders aus: Hier kann ein Prozess (siehe obiges Beispiel), der auf einem anderen Prozessor läuft, trotzdem in den kritischen Abschnitt eingreifen und das System in einen inkonsistenten Zustand bringen.
Hierfür gibt es Spinlocks. Setzt ein Prozess ein Spinlock auf eine Resource, so wird diese blockiert, ein anderer Prozess, der diese Resource ebenfalls haben möchte probiert nun solange sie zu bekommen, bis es klappt. (He keeps trying (spinning) until he gets the resource).
Somit sind Spinlocks nur auf Multiprozessorsystemen vorhanden, auf Einprozessorsystemen werden sie nicht mit in den Kernel heineinkopiert.
Es gibt drei verschiedene Arten von Spinlocks:
  • vanilla (basic): In diesem Fall hält ein Prozess den Lock, alle anderen müssen warten.
  • Read/Write: Hier kann es mehrere Reader, aber nur einen Writer geben. Es können also beispielsweise 3 Prozesse gleichzeitig lesend auf eine Resource zugreifen. Möchte ein vierter lesen, so kann er dies ohne weiteres tun. Möchte allerdings ein Prozess schreibend, auf die Resource zugreifen, so muß er sich den exklusiven writelock holen, d.h. warten bis alle Reader verschwunden sind. Hält ein Writer den Lock, so kann kein Reader auf ihn zugreifen.
  • Big-reader Spinlocks: Dies ist eine spezielle Form der Read/Write Spinlocks, die sehr optimiert für viele schnelle Reader ist. Es gibt allerdings immoment nur zwei davon: Einer in der Sparc64 Implementation und einer in den Netzwerkimplementationen.

Spinlocks gehen auf unterschiedliche Weise mit Interrupts um:
  • spin_lock(spl)/spin_unlock(spl): Kümmert sich nicht weiter Interrupts. Diese Form der Spinlocks schützt lediglich Kernel Resourcen, auf die nicht von Interrupt Handlern zugegriffen wird.
  • spin_lock_irq(spl)/spin_unlock_irq(spl): Unterdrückt Interrupts.
  • spin_lock_irqsave(spl, flags)/spin_unlock_irqsave(spl, flags): Speichert den IRQ Status vorher in flags ab, bzw. stellt ihn wieder her. Interrupts werden unterdrückt.

Semaphore

Die andere Möglichkeit um größere Blöcke sicher zu machen besteht in Semaphoren. Im Gegensatz zu Spinlocks funktionieren sie auch auf Einprozessorsystemen und können mehrere Prozesse gleichzeitig bedienen. Ein Prozess, der erfolglos versucht eine Resource zu bekommen wird in einer Waitqueue schlafen gelegt und bekommt den state TASK_INTERRUPTABLE oder TASK_UNINTERRUPTABLE. Semaphore haben zwei grundsätzliche Funktionen up() und down(). Intern halten sie einen Zähler, falls dieser größer als Null ist, so können genau so viele Geräte auf die Resource zugreifen. Ist der Zähler gleich oder kleiner Null, so zeigt er an wieviele Prozesse sich in der Waitqueue befinden. Grob gesagt macht die up() Funktion nichts anderes, als den Zähler zu prüfen und zu dekrementieren und den anfragenden Prozess je nach dem die Resource geben oder ihn in die Waitqueue packen. Die down() Funktion erhöht den Zähler wieder und weckt den nächsten Prozess auf.
Im Linux Kernel 2.4 wurden die Semaphoren komplett neu implementiert. Neben einer Erhöhung der Effizienz ist es nun möglich nur einen Task aus der Waitqueue aufzuwecken. Im Kernel 2.2 wurden alle aufgeweckt und in den state TASK_RUNNING versetzt.
Wie bei den Spinlocks gibt es auch bei den Semaphoren normale und read/write Semaphoren. Sie verhalten sich wie die Spinlocks.

Erstellen und Beenden von Prozessen Inhalt Der Scheduler