Parallelität in Softwaresystemen beschleunigt die Abarbeitung und ermöglicht reaktionsschnelle Benutzerschnittstellen und Serverprogramme. Mittel und Wege können - wie die Resultate - gänzlich unterschiedlich sein. Linux will sich mit einer neuen Thread-Generation dem POSIX-Standard weiter nähern.
Unterthema: iX-TRACT
Unterthema: QUELLEN
Unterthema: LMbech lat_ctx
Unterthema: ERGEBNISSE DES LMBENCH LAT_CTX
Unterthema: Glossar
Neben der traditionellen Technik des IO-Multiplexing via select()/poll() oder der Verwendung mehrerer Prozesse, können Threads zu einem einfacheren Aufbau der Programmlogik führen. In der langen Unix-Geschichte wurden drei Arten von Thread-Modellen implementiert - alle haben ihre Vor- und Nachteile. Unter Linux kommen bisher die Linux-Threads (1 : 1, siehe Kasten `Fäden und Knäuel' in [3]) zum Einsatz. Inzwischen existiert eine Alternative: die Next Generation POSIX Threads mit M:N-Modell (NGPT). Sie sind wesentlich performanter, funktionsreicher als die Linux-Threads, näher am POSIX-Standard und heute verfügbar.
Eine bewährte und hohe Form von Modularisierung von Software stellt das Zusammenspiel mehrerer Prozesse zur Bewältigung anstehender Aufgaben dar. Jeder Unix-Benutzer kennt die Option, über Pipes mehrere Filter zur Manipulation von Daten zu verknüpfen. Typische Serveranwendungen wie Web- oder Datenbankserver erlauben mehreren Clients den quasi gleichzeitigen Zugriff. Würden die Anfragen einfach sequenziell abgearbeitet, entstünden lange Antwortzeiten. Um Nebenläufigkeit zu erreichen, stellt der Apache-Webserver bis zur Version 1.3 mehrere Prozesse bereit, auf die er die Anfragen verteilt. Hier sind Abläufe zu synchronisieren beziehungsweise Daten untereinander auszutauschen.
In der Version 2 bietet Apache mehrere Techniken zum gleichzeitigen Bedienen der Anforderungen: Zum einen gibt es die unter dem Vorgänger verwendete Gruppe von Arbeitsprozessen (preforked), aber auch die Kombination von einer festen Anzahl Prozesse mit variabler Anzahl Threads (perchild) und einem ähnlichen Modell, bei dem nur ein Thread die Anfragen auf einen der Arbeits-Threads (Worker) verteilt. Wählen kann man aus einem dieser Modelle zur Kompilationszeit. Wie der Artikel Reality Check [1] beschreibt, bestimmen die Plattform sowie eine Abwägung zwischen Performanz und Fehlerverhalten die Entscheidung.
In manchen Anwendungsfällen stellt sich heraus, dass Systemaufrufe zu `teuer' sind - gemessen an ihrer Häufigkeit und der Nettoarbeit, die sie verrichten. So ist es günstiger, oft bearbeitete Dateien mit mmap() in den Speicher der Anwendung einzublenden, um Aufrufe von read() und write() zu vermeiden, da der Wechsel von User- in Kernelland (dem Umschalten vom speichergeschützten Anwendungsadressraum in den privilegierten Systemmodus) relativ zeitintensiv ist. Für ein-/ausgabeintensive Anwendungen lohnt sich die Verwendung der SFIO-Bibliothek von AT&T (Safe and Fast IO, siehe Kasten `Quellen').
Ähnliches gilt für große Anwendungssysteme mit Dutzenden von Prozessen beziehungsweise Threads. Letztere sollen ja gerade die Kooperation von Abläufen leichtgewichtiger - somit effizienter - machen, indem sie keine Prozessgrenzen überschreiten müssen. Ein gehöriger Anteil beim Prozesswechsel stellt das Umschalten der Speicherverwaltung mit ihren Seitentabellen dar - bei einem Thread-Wechsel ist dies unnötig und fließt im Scheduler von Linux bei der Bestimmung des nächsten Prozesses schon seit langem ein (MM_AFFINITY_BONUS). Wie die Grafik `Ergebnisse des LMbench' zeigt, lassen sich durch die Trennung von Ausführungskontext und Adressraum sehr schnelle Kontextwechsel messen.
In Diskussionen taucht das häufige Überschreiten von Speicherschutzgrenzen immer wieder als Grund dafür auf, dass microkernelbasierte Systeme langsamer seien als monolithische. Die beschränkte Anzahl von TLBs (Translation Lookaside Buffer) fordert hier Tribut: muss die MMU (Memory Management Unit) den Seitentabelleneintrag erst lesen, wartet der Prozessor. Prozesswechsel sollte man, soweit machbar, vermeiden, da man eventuell die TLBs neu lesen muss. Auch hier steckt noch Optimierungspotenzial: Benutzt man große Speicherseiten (Large Pages) mit mehreren Megabyte Umfang, statt der üblichen 4 oder 8 kByte, verringert sich die Anzahl der Tabelleneinträge erheblich - für 4 MByte Arbeitsspeicher benötigt ein x86-System 1024 Seiteneinträge. Alle Großkonsumenten von RAM, etwa Datenbanken, profitieren davon, da die Häufigkeit eines TLB Miss sinkt.
Ein Wechsel von User- nach Kernelland kann noch so schnell sein: er kostet trotzdem Zeit. In massiv parallelen Systemen, mit feinen aber deshalb vielen Synchronisationssperren, entfällt ein nicht unerheblicher Anteil des Overheads allein auf das Sperren und Entsperren. Häufig stellt sich heraus, dass eine Sperre frei ist, vor allem wenn sie nur für kurze Zeit gehalten wird. Daraus ergibt sich die Optimierung, den Kernel nur im Falle eines Konflikts in Anspruch zu nehmen. Voraussetzung dafür ist eine atomare `Compare-and-Swap'-Anweisung des Prozessors - ein i386 kommt dafür also nicht infrage, aber alle seine Nachfolger. Die Systembibliothek versucht mit der atomaren Anweisung die Sperre zu erlangen, schlägt dies fehl, vermerkt sie dies in der Sperre und legt den Thread mit dem Systemaufruf sys_futex(WAIT) schlafen. Bei der Freigabe der Sperre überprüft die Bibliotheksfunktion auf etwaige Schläfer und weckt diese gegebenenfalls mit Hilfe des Kernels via pthread_cond_signal, der in sys_futex(WAKE) mündet. Schwierigkeiten bereitet hier allerdings das ungewollte Ableben eines Sperrenbesitzers: bei getrennten Prozessen warten die anderen bis in alle Ewigkeit, es sei denn, das System verfügt über einen Lock-Manager, der die Sperren periodisch auf `tote' Sperren überprüft. Der Kernel kann diese Aufgabe nicht übernehmen, da er nicht (ohne einen komplizierten Algorithmus) wissen kann, wer die Sperre besitzt. Eine einfachere Variante bildet der auch in Solaris implementierte Robust Mutex. Dieser prüft bei Interprozesssperren vor dem Blockieren mit kill(pid,0), ob der Sperrenbesitzer noch existiert.
Eine N:1-Zuordnung bildet mehrere Threads innerhalb eines Prozesses ab. Die Verwaltung erfolgt komplett im Userspace über eine Threading-Bibliothek. Es existieren etliche unterschiedliche Implementierungen, die bekanntesten (freien) dürften die MIT-Threads, DCE-Threads sowie die Gnu Portable Threads (siehe Kasten `Quellen') sein. Die Gnu Portable Threads kommen ohne maschinenabhängige Sonderwege aus und nutzen - wenn möglich - swapcontext(), sigaltstack() oder sigsetjmp()/siglongjmp().
Bei N : 1 sieht der Kernel die Threads gar nicht (Abb. 1).
Um eine Nebenläufigkeit innerhalb des Prozesses zu erreichen, muss die Threading-Bibliothek durch einen Wrapper diverse blockierende Systemaufrufe überschreiben. Dies geschieht entweder über eine korrekte Link-Reihenfolge beim Erzeugen des ausführbaren Programms, der Verwendung der syscall-Funktion oder einer festen Verdrahtung. Dazu ersetzt sie die blockierenden Systemaufrufe (wenigstens: read, write, connect, listen und sleep) durch nicht blockierende Gegenstücke, die regen Gebrauch von poll()/select() machen, um mehrere ausstehende Vorgänge synchron zu multiplexen.
Für jeden Thread einer Applikation erzeugt pthread_create() via clone() ein Kernel-Scheduler-Objekt (Kernel-Thread). Dabei teilen sich die Threads den Adressraum und die Dateideskriptoren. Das Umschalten übernimmt der Kernel. Es bedarf keiner besonderen Vorkehrung für blockierende Systemaufrufe.
Bei der Signalbehandlung verhalten sich die Linux-Threads nicht POSIX-konform. So ist es nicht möglich, ein SIGCHLD eines mittels fork(2) abgespaltenen Kind-Prozesses an einen anderen, als dem Thread, der die Geister rief, zustellen zu lassen. POSIX schreibt vor, dass via pthread_sigmask() regelbar ist, welcher Thread das Signal erhält. Das erscheint auf den ersten Blick kein erwähnenswertes Handicap zu sein - doch ist es in einer Multithreaded-Umgebung häufig sinnvoll und leichter, nur einen bestimmten Thread mit der Signalbehandlung zu belästigen - indem er etwa in sigtimedwait() oder sigsuspend() wartet und alle anderen die Signale blockieren. Möchte man trotz Multithreading nicht auf asynchrone Ein-/Ausgabe verzichten (siehe Kasten `Quellen'), bietet sich diese Art der Signalbehandlung ebenfalls an.
Die heutigen Linux-Threads schaffen es nicht, die Signale POSIX-konform auszuliefern (Abb. 2).
Durch die frühere Entscheidung von Linus Torvalds, dass der Kernel nichts weiter als den jetzigen clone()-Systemaufruf unterstützen müsse, um ein effektives Threading zu ermöglichen, leiden die heutigen Linux-Threads unter einer ganzen Reihe von Designmängeln. Weder POSIX-Mutexe noch Condition-Variablen sind über Prozessgrenzen (PROCESS_SHARED) in Linux 2.4 und Glibc 2.2 vorhanden - sie lassen sich aber etwa mit System-V-Semaphoren emulieren.
Im September hat Ulrich Drepper, Glibc-Maintainer, den designierten Nachfolger der heutigen Linux-Threads ausgerufen, die Native POSIX Threads Library (NPT). In enger Zusammenarbeit mit Ingo Molnar entsteht eine 1:1-Threading-Bibliothek, die durch Hilfe des Linux-Kernels viele der jetzigen Unzulänglichkeiten überwindet. Von diesen Neuerungen werden aber erst Benutzer von Systemen mit Kernel 2.6, Glibc 2.3 und brandneuen binutils profitieren können.
Nach langen Überlegungen haben sich die Entwickler hier weiterhin für ein 1:1-Modell entschieden. Mit dem effektiven O(1)-Scheduler (Order of One - konstante Laufzeit, unabhängig von der Anzahl lauffähiger Prozesse/Threads) und einer ähnlichen Maßnahme bei Beendigung eines Prozesses/Threads durch exit/pthread_exit, sowie der Erweiterung des clone()-Systemaufrufes, die Thread-ID auf Anforderung in den Userspace zu kopieren, erscheint der Mehraufwand zweier eventuell gegenläufiger Scheduler und der wachsenden Komplexität nicht gerechtfertigt.
Im NGPT-Projekt (Next Generation POSIX Threads) arbeitet man an einer komplett POSIX-konformen Thread-Implementierung, die auf einem M:N-Modell beruht. Diese führt eine Anzahl `m' Threads auf `n' Kernel-Scheduler-Objekten aus. Dabei kann sich die Anzahl der virtuellen Prozessoren in Abhängigkeit sonstiger Systemaktivitäten ändern.
Kompliziert aber flexibel - bringt das M:N-Modell Geschwindigkeitsvorteile? (Abb. 3)
Über pthread_setconcurrency() teilt die Anwendung dem Thread-Scheduler mit, von wie vielen Kernel-Threads sie profitieren könnte. Um ein Intra-Prozess-Scheduling zu ermöglichen, sind blockierende Systemaufrufe (wie die schon genannten read, write, connect, sleep) durch Wrapper ersetzt, die via select()/poll() auf eine nicht blockierende Bedingung des Systemaufrufes warten und somit erst ein Umschalten ermöglichen.
In jeder Instanz eines Kernel-Threads läuft eine kooperierende Instanz des Thread-Scheduler. Auf einem Mehrwegesystem verteilen sich die Threads dynamisch auf die Kernel-Threads und ermöglichen tatsächliche Nebenläufigkeit.
Wenn man so will: ein SMP-System in sich. Die Vorteile sind die gute Skalierbarkeit auf SMP-Systemen, bei denen sich eine wirkliche Nebenläufigkeit erreichen lässt. Dieser Ansatz vermeidet aber auch den Nachteil des größeren Aufwands, gerade bei Uniprozessorsystemen, da diese weniger Kernel-Threads verwalten müssen. Nicht zuletzt verspricht die Thread-Umschaltung im Userspace effizienter zu sein, da sie Wechsel zwischen Kernel- und Userland vermeidet. Bei Anwendungen mit sehr vielen Threads und einer relativ geringen Konkurrenz um die synchronisierenden Sperren (und einer kurzen Haltezeit) bietet sich der Einsatz von Sperren im User-Land an, wie den Futexen. Der Zeitgewinn resultiert daraus, dass der Kernel bei einer freien Sperre nicht involviert wird - somit kein Wechsel in den Kernelmode erfolgt.
Eine Implementierung eines M:N-Modells erreicht allerdings schnell eine hohe Komplexität. Die Wrapper erzeugen potenziell mehr Systemaufrufe, und es ergeben sich Probleme bei Page Faults, dem Laden einer Speicherseite in den Arbeitsspeicher. Gerade bei der Verwendung von gemappten Dateien hat der Prozess kaum Kontrolle über dieses Ereignis. Fortgeschrittene M:N-Modelle, wie bei NetBSD (siehe Kasten `Quellen'), greifen auf einen Scheduler Activations (SA) genannten Mechanismus zurück. Hier unterrichtet der Kernel über so genannte Upcalls einen registrierten User-Level-Scheduler von Ereignissen wie Preemption, Signalen und der Verfügbarkeit von Ein-/Ausgabekanälen. Scheduler Activations betreffen etliche strategische Punkte im Kernel, daher ist es fraglich, ob eine Implementierung jemals Aufnahme in den offiziellen Linux-Kernel finden wird.
Schließlich hält man neuerdings den ganzen Aufwand eines M:N-Modells für überflüssig. Mit dem O(1)-Scheduler, den bekannten schnellen Kontextwechseln und diverser anderer Maßnahmen, sei ein 1:1-Modell weniger komplex und damit effizienter. Die Existenz bisheriger M:N-Modelle wird mit der Behäbigkeit der dort eingesetzten Betriebssysteme erklärt.
Möchte man jetzt oder in näherer Zukunft POSIX-konforme und schnelle Threads unter Linux verwenden, sind die NGPT zu empfehlen. Die `neuen' Linux-Threads müssen zwar erst zeigen, dass sie halten, was sie versprechen, doch alle Zeichen deuten darauf hin. Durch die schnellen Kontextwechsel sowie die Laufzeitunabhängigkeit des Scheduler von der Anzahl der Threads im System entfallen gewichtige Argumente für ein M:N-Modell. Nicht zuletzt diktiert der Speicherbedarf ihrer Stacks die Anzahl, egal ob User- oder Kernel-Threads. Gute Voraussetzungen dafür, dass die ganze Thread-Diskussion von vorn beginnt. (avr)
ist Softwareentwickler mit Schwerpunkt Unix, embedded Systems und IP-Netzen.
[1] Gerald Richter; Webserver; Reality Check; Apache 2.0: neue und angepasste Module; iX 9/2002, S. 86
[2] Azundris; Open Source; Bibliotheksbaustelle; Schnelle Desktops und polyglotte Server mit der Glibc 2.3; iX 9/2002, S. 111
[3] Andreas Nolte; Linux/ SMP; Kernfrage; Multiprozessorfähige Linux-Versionen auf SMP-Systemen; iX 3/1998, S. 64
Die Verwendung von Threads statt separater Prozesse vermeidet zeitaufwendiges Synchronisieren zwischen den Prozessen.
Linux unterstützt im Kernel derzeit nur Threads nach dem 1:1-Modell - pro Applikations-Thread ein Gegenstück auf Kernelseite.
Mit den Next Generation POSIX Threads steht ein Nachfolger auf Basis eine M:N-Modells in den Startlöchern.
| AT&T SFIO | www.research.att.com/sw/tools/sfio/ |
| Gnu Portable POSIX Threads | www.gnu.org/software/pth/ |
| LMbench | www.bitmover.com/lmbench/ |
| NGPT | www-124.ibm.com/pthreads/ |
| Portable Multithreading | www.gnu.org/software/pth/rse-pmt.ps |
| POSIX async I/O | www.kvack.org/~blah/aio/ |
| Scheduler Activations on NetBSD | web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html |
Beim LMbench (siehe Kasten `Quellen') handelt es sich um einen in C geschriebene Low-Level-Benchmark-Suite für Unix-Systeme. Ein Microbenchmark daraus, der LMbech 2alpha8 Context Switching Benchmark lat_ctx, misst den Zeitbedarf für den Wechsel zwischen Prozessen. Dabei ermittelt er nicht nur eine einzelne Zeit, da diese durch den Einfluss heutiger Speichercaches kaum Aussagen über reale Bedingungen erlauben würde.
Vielmehr misst er für Vergleiche die Zeiten, die das System braucht, um ein Zeichen zwischen einer Anzahl Prozesse herumzureichen. Mit der Emulation unterschiedlicher Prozessgrößen zeigt lat_ctx die Abhängigkeit von der Effizienz der Caches auf. Dafür referenziert er vor dem Weiterreichen des Zeichens ein komplettes Array, um die Datencaches zu füllen.
Die Ergebnisse staffeln sich nach Anzahl der beteiligten Prozesse sowie der Größe des benutzten Arrays. In der Spalte 2P/0K finden sich die Zeiten eines Kontextwechsels bei `heißem' Cache.
Wie die Werte zeigen, ist Darwin mit seinem Mach-Kernel im Vergleich zu Linux sehr träge. Der Athlon besitzt im Vergleich zum G3/iBook einen effizienteren Cache. Die QNX-Werte belegen, dass nicht alle Microkernel träge sein müssen - zumindest wenn es nicht auf Datendurchsatz ankommt.
1:1-Modell: Thread-Modell, bei dem der Kernel alle Threads verwaltet; die Threads erzeugt der Systemaufruf clone(). Sie belegen jeweils einen Eintrag in der Prozesstabelle, teilen sich aber den Adressraum sowie die Dateideskriptoren.
Asynchronous I/O: nicht blockierende, das heißt nicht wartende Ein-/Ausgabeoperation; benötigt einen Benachrichtigungsmechanismus über den Ausgang.
Condition-Variable: Mechanismus, um auf eine Bedingung zu warten, dessen Eintreffen von einem anderen Codeteil signalisiert wird.
Context Switch: Wechsel des Ausführungskontextes von einem Prozess zu einem anderen - auch Wechsel zwischen Kernel-Threads.
Futex: Kunstwort für Fast Userspace MuTEX, Sperre außerhalb des Kernels; der Kernel wird nur bei Konflikten konsultiert.
Goodness: Gewichtung eines adaptiven Schedulers bei der Zuordnung des Prozessors.
MMU: Memory Management Unit; Hardware-Einheit zum Übersetzen und Verwalten von in Seiten aufgeteiltem Speicher. Ermöglicht virtuellen Speicher.
Mutex: Mutual Exclusion, exklusive Sperre; umschließt kritische Sektionen (Datenmanipulation), die nicht zeitlich geschachtelt ausgeführt werden dürfen.
N:1-Modell: Ein Kernelobjekt veraltet die Threads, die Umschaltung erfolgt im Userspace; kommt häufig auf Systemen zum Einsatz, deren Kernel keinen Thread-Support bietet.
N:M-Modell: Flexibles, aber kompliziertes System, bei dem sich die Verteilung der Threads dynamisch der Systemumgebung anpasst; kann bei Anwendungen mit sehr vielen Threads den Scheduler entlasten.
Page Fault: Benachrichtigung der MMU, dass eine referenzierte Speicherseite nicht vorhanden ist.
Preemption: vor Ablauf des Zeitquantums erfolgte Verdrängung eines Prozesses von der virtuellen Maschine.
Upcall: Benachrichtigung des Kernels an einen Userspace Scheduler über eine anstehende Verdrängung (Page Fault, Preemption) - siehe Scheduler Activation.
Scheduler: Modul für die Zuteilung des Prozessors an Programme.
Scheduler Activation: Mechanismus im Kernel zur Zusammenarbeit von Kernel- und Userland-Schedulern.