Die POSIX Thread Bibliothek unter Linux & Fuss, Futex und Furwocks

Inhaltsverzeichnis

1 Die POSIX Thread Bibliothek unter Linux
1.1 Einleitung
1.2 Die weitere Entwicklung der Bibliothek
1.3 Probleme
1.4 Anforderungen an eine Neuimplementierung
1.5 Design Entscheidungen
1.5.1 Das 1-zu-1 oder M-zu-N Modell
1.5.2 Signal Behandlung
1.5.3 Der Managerthread
1.5.4 Synchronisations Primitiven
1.5.5 Speicheranforderungen
1.5.6 Kernel Erweiterungen

2 Fuss, Futex und Furwocks
2.1 Einleitung
2.2 Die Ziele der Implementierung
2.3 Die Implementierung

Zusammenfassung

Das erste Kapitel dieser Arbeit beschreibt die Neuerungen der POSIX Thread Bi- bliothek unter Linux. Das Hauptaugenmerk liegt dabei darauf, die POSIX-Bibliothek skalierbar zu machen und dabei Kernelerweiterungen zu benutzen, die bis 2003 noch nicht in der Bibliothek implementiert wurden. Weiters werden Kernelerwei- terungen besprochen, die auf die Neuerungen der Thread Bibliothek abgestimmt wurden.

Im zweiten Kapitel werden die in Kapitel eins angesprochenen Futexes genauer erläutert. Dazu wird erklärt was Futexes sind, warum sie eingesetzt werden, welche Ziele für die Implementierung wichtig waren und welche Mechanismen zur Umsetzung verwendet wurden.

Kapitel 1 Die POSIX Thread Bibliothek unter Linux

1.1 Einleitung

Nahezu alle modernen Betriebssysteme benutzen heute präemptives Multitasking um mehrere Aktivitäten auf die Resourcen Prozessor und Speicher aufzuteilen. Dazu gibt es die gängige Variante über Prozesse und die effizientere über Threads, welche zum Beispiel zur Implementierung von schneller Middleware nötig ist. Prozesse behandelt jede Unix-Implementierung gleich, bei Threads dagegen gibt es mehrere Möglichkeiten diese zu implementieren. Die folgende Abbildung zeigt einige davon. [LM03]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Überblick: Thread Bibliotheken [LM03]

Nun möchte ich näher auf die Implementierung zu Linuxthreads eingehen. Die alte Implementierung der Posix Bibliothek von 1996/97 hatte den Nachteil, dass für die Umsetzung der 1-zu-1 Abbildung von User-level Threads auf Kernel Threads zusätzlich ein Thread gestartet werden musste, der sich um die Prozess- verwaltung wie zum Beispiel um Signale und Thread Erzeugung kümmert. Das größte Problem war wohl, dass es keine geeigneten Synchronisationsprimitiven auf Kernelebene gab. Dies wurde durch Signale gelöst.

1.2 Die weitere Entwicklung der Bibliothek

In den folgenden 6 Jahren (1996-2002) wurde der Kernel in zwei Bereichen verbessert: Die ABI und der Linux-Kernel.

Um die lokalen Daten bzw. den Stack von Threads schneller allozieren zu können, wurden Threadregister in der ABI eingeführt. Bei der Implementierung für IA-32 wurden dazu beispielsweise die Register %fs and %gs verwendet. Mittels dieser Register kann die Segmentadresse von Datenstrukturen bestimmt werden. Dazu muss in einer Deskriptor-Tabelle nachgesehen werden, was nur im Kernel Modus erlaubt ist und dadurch zu Performanzeinbußen führt, da zwischen Kernel- und Benutzermodus gewechselt werden muss. Eine Einschränkung durch die Adres- sierung mit Segment Registern ergibt sich daraus, dass in jenen nur 8192 Adressen unterschieden werden können.

Insgesamt haben die erläuterten Erweiterungen jedoch eine Verbesserung der Per- formanz, der Flexibilität und die Vervollständigung der API gebracht. Die weitere Intention ist nun auch noch den Thread zur Verwaltung (Manager Thread) zu eli- minieren.

1.3 Probleme

Die beschriebene Implementierung funktionierte bei vielen Anwendungen einwandfrei, hatte aber einige Probleme bei hoher Beanspruchung.
-Wenn beispielsweise der Manager-Thread eines Prozesses abstürzt, muss der Rest des Prozesses händisch aufgeräumt werden. Außerdem wird der Manager-Thread zum Flaschenhals, da er die Thread Erzeugung und Ent- fernung regelt.
-Das Signal System ist nicht POSIX konform, da beispielsweise ein Signal nicht an einen Prozess als ganzes gesendet werden kann, wenn dieser meh- rere Threads hat. So ist es einem Benutzer nicht möglich, einen Prozess, der mehrere Threads hat, mittels SIGSTOP zu stoppen bzw mit SIGCONT fortzusetzen. [SIGC]
-Die Verwendung des Signal Systems zur Implementierung von Synchroni- sationsprimitiven ist problematisch, da die Antwortzeit von Operation sehr hoch ist und die Signalverarbeitung noch komplizierter wird. Wenn zum Beispiel ein Thread wartet bis eine Bedingung eintritt, legt er sich bis dahin schlafen. Dabei kommt es öfters vor, dass er zuvor aufgeweckt wird, was natürlich umgangen werden muss. [Spur]
-Da Threads verschiedene Prozess ID’s hatten, gab es hier Kompatibiliätsprobleme mit anderen Posix Implementierungen.
-Die Anzahl der Threads ist in der IA-32 Implementierung auf 8192 begrenzt und stellt für manche Anwendungen ein Problem dar.

Beim Kernel gab es auch einige Probleme.

-Das „/proc“ Dateisystem wird schnell unübersichtlich, wenn jeder Thread als Prozess aufscheint.
-Die vorher beschriebenen Probleme mit SIGSTOP und SIGCONT müssen vom Kernel gelöst werden um die gewünschte Funktionalität bereitzustel- len.
-Der Ansatz Signale zur Synchronisation zu verwendet ist eine komplizierte Lösung und schlecht für die Performanz.

1.4 Anforderungen an eine Neuimplementierung

Bei der Neuimplementierung der Posix Thread Bibliothek gab es Einschränkungen durch den aktuellen Linux Kernel. Eine komplett neue Implementierung wäre nötig. Das Ziel hier war es jedoch ABI kompatibel zu sein. Die Anforderungen für eine geeignete Implementierung waren folgende.

-Das höchste Ziel ist Posix-kompatibel zu sein um bei verschiedenen Plattformen Quellcodekompatibilität zu gewährleisten.
-Die effektive Benutzung von SMP ist ein weiteres Ziel. Durch das Hinzufügen einer CPU zum System soll auch möglichst ein linearer Geschwindigkeitszuwachs erzielt werden. Dazu sollte die Last mindestens in so viele Threads aufgeteilt werden, wie CPU’s vorhanden sind.
-Beim Erzeugen von Threads soll möglichst wenig Overhead entstehen, da- mit es sich auch für kleine Arbeitspakete auszahlt einen Thread zu erzeugen.
-Die Bibliothek soll möglichst wenig Einfluss auf Programme haben, die keine Threads benutzen aber mit der Bibliothek „verlinkt“ werden.
-Die Binärkompitibiliät mit der ABI für LinuxThreads soll gegeben sein.
-Gute Hardware Skalierbarkeit soll durch die Voraussetzungen wie in Punkt zwei und drei beschrieben worden ist, gegeben sein. So soll der Verwaltungsaufwand bei mehreren Prozessoren nicht wesentlich ansteigen.
-Um Software Skalierbarkeit zu gewährleisten, sollte eine unbegrenzte Anzahl an Threads möglich sein.
-Möglichst effiziente Unterstützung für verschiedene Maschinen Architekturen wie zum Beispiel Großrechner. Dabei sollte das Programm möglichst gut mit der Funktionalität des Betriebssystems umgehen können.
-NUMA-Architekturen sollen geeignet unterstützt werden. Bei einem NumaSystem haben bestimmte Speicherbereiche unterschiedliche Zugriffszeiten, da der Speicher beispielsweise zu einer anderen CPU gehört. Die Eigenschaften dieser Architektur müssen bei der Implementierung der Thread Bibliothek beachtet werden.

1.5 Design Entscheidungen

1.5.1 Das 1-zu-1 oder M-zu-N Modell

Dieses Kapitel beschäftigt sich mit der Zuordnung von Threads vom Benutzer- und zum Kernelmodus. Grundsätzlich reichen Threads im Benutzermodus nicht aus, da man sonst keinen Nutzen von Multiprozessorsystemen haben könnte. Beim 1-zu-1 Modell der alten Implementierung wird jedem Thread auf Benut- zerebene ein Thread auf Kernelebene zugeordnet. Dadurch hat man den Vorteil, dass die Thread Bibliothek über den Kernelfunktionen relativ klein ausfällt. Beim M-zu-N Modell werden Threads auf Benutzerebene verfügbare Threads auf Kernelebene zugeteilt. Dadurch braucht man zwei Scheduler die eng miteinan- der kooperieren. Die beiden Scheduler tauschen dabei Information aus, welche Threads gerade als Kernelthread laufen und welche Threads als nächstes als Ker- nelthreads laufen sollten. Dieses Modell passt jedoch nicht ins Linux Konzept, weil die nötige Infrastruktur unter Linux nicht vorhanden ist und der Implemen- tierungsaufwand für die Thread Bibliothek relativ hoch ist. So wurde wieder das 1-zu-1 Modell gewählt, jedoch mit einigen Verbesserungen.

1.5.2 Signal Behandlung

Benutzt man das M-zu-N Modell kann die Signal Behandlung vereinfacht werden. Auf Kernelebene wird die Anzahl der Threads niedrig gehalten und die Filterung welcher Thread welche Signale bekommt, wird auf Benutzerebene durchgeführt. Dabei gibt es 2 Möglichkeiten mit Signalen umzugehen:

-Ein zusätzlicher Thread behandelt die Signale. Der Aufwand für den Thread und die Serialisierung der Signale ist dabei nicht unerheblich. Außerdem stellt er einen Flaschenhals dar, weil alle Signale erst einmal von diesem Thread behandelt werden müssen. Als Lösung könnte man hier mehrere Threads zur Behandlung von Signalen einführen.
-Die andere Variante wäre, dass ein Aufrufmechanismus Threads aufweckt, wenn ein Signal für ihn ansteht. Dazu muss im Kernel ein Zustellungsmechanismus implementiert werden und auf Benutzerebene müssen verschiedenen Funktionen um Signale zu behandeln emuliert werden.

Die Signalbehandlung ist also auch unter dem M-zu-N Modell möglich, ist aber mit höherem Implementierungsaufwand verbunden und normale Operatio- nen der Bibliothek werden durch die komplexe Struktur des Modells langsamer. Die andere Möglichkeit ist, dass der Kernel die POSIX Signalbehandlung imple- mentiert. Dazu muss aber das 1-zu-1 Modell verwendet werden, da der Kernel bestmöglich entscheiden muss, welcher Thread das Signal bekommt. Dabei wer- den Signale nur Threads zugestellt die nicht blockiert sind, wodurch keine unnö- tigen Unterbrechungen durch Signale entstehen und dadurch Zeit gespart wird.

1.5.3 Der Managerthread

In der alten Implementierung der Thread Bibliothek bearbeitete der Managerthread zentral und sequentiell verschiedene interne Arbeiten wie beispielsweise das Erzeugen von Threads. Dabei hatte er folgende Aufgaben:

-Die Überwachung aller „Kinder“ eines Prozesses und Behandlung von Fehlersignalen durch beispielsweise beenden des Prozesses mit all seinen Kindern. Diese Aufgabe kann nur von einem bestimmten Thread oder vom Kernel selbst durchgeführt werden.
-Die Deallokation des Speichers wie zum Beispiel des Stacks oder anderen lokalen Daten muss nach dem Beenden jedes Threads durchgeführt werden,
-Auf das Beenden von Threads muss gewartet werden, damit sie nicht als verwahrloste Threads Speicher belegen, obwohl kein Prozess mehr auf sie zugreift.
-Wenn der Haupt-Thread „pthread_exit“ aufruft, legt er sich schlafen um auf seine Kindsprozesse zu warten. Die Aufgabe des Managerthreads ist es, den Haupt-Thread wieder aufzuwecken, wenn der Prozess beendet wird.

[...]