© Ulrike Lacour, Pixelio.de

Programme so zu schreiben, dass sie aktuelle Multicore-Prozessoren gleichmäßig auslasten, ist nicht trivial. Leichter geht das überraschenderweise mit der Shell. Die Bash-Skripte lassen sich nämlich mit Bordmitteln parallelisieren.

Will man Software dazu bewegen, verschiedene Dinge parallel auszuführen, dann liegt die erste Herausforderung darin, die Aufgabe in sinnvolle Teilprobleme aufzuteilen, die der Rechner gleichzeitig bearbeiten und deren Resultate er am Ende wieder zusammenführen kann. OpenMP ist eine Bibliothek, die bei dieser Spielart der Parallelisierung hilft. Für Bash-Skripte ist dagegen nicht das numerische Problem typisch, stattdessen sollen sie oft mehrere Dateien in gleicher Weise verarbeiten.

Klassisch seriell

Ein solches Skript sieht dann typischerweise aus wie Listing 1. Die Shellfunktion arbeitet darin alle Argumente der Reihe nach ab und übergibt sie an ein Programm (»doSomething«). Eine parallele Verarbeitung drängt sich hier förmlich auf. Dafür bieten sich verschiedene Strategien an.

Bevor sich der Skript-Autor aber ins Programmieren stürzt, lohnt es sich zu überlegen, ob eine Parallelisierung überhaupt sinnvoll und machbar ist.

01 doSeriell() {
02  local item
03  for item in "$@"; do
04   doSomething "$item"
05  done
06 }

Sinnfrage

Die Sinnfrage ist recht einfach zu beantworten, eine Hilfestellung gewährt hier der Befehl »sar -u -P ALL 1 0«. (Das Utility »sar« ist Teil des Sysstat-Pakets [1].) In einer zweiten Konsole startet der Tester anschließend das Bash-Skript. Der Sar-Befehl gibt im Sekundenabstand die Auslastung aller CPUs des Systems aus (Abbildung 1). Neben dem »%idle«-Wert ist auch der »%iowait«-Wert interessant: Er zeigt, ob die Berechnung womöglich pausiert, weil das System auf ausstehende I/Os wartet.

Abbildung 1: Die Ausgabe von »sar« zeigt die Auslastung aller CPUs. Nur wenn einige Kerne überlastet sind, während sich andere langweilen, lohnt sich Parallelisierung.

Die Sar-Werte erleichtern die Entscheidungsfindung sehr: Nur falls es überhaupt Prozessoren gibt, die sich langweilen, während gleichzeitig andere am Anschlag arbeiten (wie in Abbildung 1), lohnt sich eine Parallelisierung. Typische Anwendungsfälle sind CPU-lastige Bild- und Musikkonvertierungen oder das Parsen von Logdateien mit komplexen regulären Ausdrücken. Ungeeignet sind dagegen I/O-gebundene Prozesse. Zwar lässt sich durchaus das Kopieren von 200 Dateien von einem Verzeichnis in ein anderes parallelisieren, nur bringt das letztlich gar nichts, weil hier die Festplatte den Engpass bildet.

Die Machbarkeit der Parallelisierung bestimmt dagegen in erster Linie das Problem. Wenn die Verarbeitungsschritte voneinander abhängen oder wenn die Reihenfolge der Verarbeitung wichtig ist, dann ist eine sequenzielle Abfolge unvermeidlich. Eventuell hilft dabei ein anderer Algorithmus, die in diesem Artikel vorgeschlagenen einfachen Änderungen reichen in dieser Situation sicherlich nicht aus.

Außerdem sollte der Admin noch bedenken, dass es nicht immer sinnvoll ist, den Rechner voll auszulasten. Wenn er neben CPU-intensiven Aufgaben auch noch seiner regulären Tätigkeit am Rechner nachgehen will (Mailing, Internet, Texte schreiben und so weiter), wird er eine sequenzielle Verarbeitung im Hintergrund, die nur einen Kern beschäftigt, eher mögen als die schnelle Alternative, die den Rechner blockiert.

Brute Force

Mit nur minimalen Änderungen von Listing 1 wird die Verarbeitung massiv-parallel. Listing 2 startet für jedes Argument einen eigenen Prozess. In Zeile 6 wartet dann das Skript auf das Ende seiner Kindprozesse. Dieses Vorgehen kann aber nach hinten losgehen: Ist das System mit zu vielen Prozessen überlastet, dann steigt der Overhead durch die vielen Kontextwechsel. Kommt noch Speicherknappheit hinzu, beschäftigt sich das System bald nur noch mit dem Swapping einzelner Prozesse. Es gibt aber durchaus Anwendungsfälle, in denen dieser einfache Ansatz der Parallelisierung sinnvoll sein kann.

01 doMassiveParallel() {
02   local item
03   for item in "$@"; do
04     doSomething "$item" &
05    done
06  wait
07 }

Das Listing 2a, eine Variante von Listing 2, verdeutlicht dies. Hier sind die Argumente nicht vorher bekannt, stattdessen erzeugt sie ein eigener Prozess (»createWorkItems«) sequenziell – etwa ein »find« auf einem sehr großen Dateisystem. Wenn die Erzeugungs- und Verarbeitungsrate abhängig von der Anzahl der verfügbaren Prozessoren in etwa gleich ist, dann kommt es nicht zu einer Systemüberlastung.

01 doMassiveParallel2() {
02   local item
03   while read item; do
04   doSomething "$item" &
05 done
06 wait
07 }
08 
09 createWorkItems | doMassiveParallel

Teile und herrsche

Ist dieser Fall jedoch nicht gegeben, dann muss man etwas mehr Aufwand treiben. Das Skript in Listing 3 teilt die Argumente abhängig von der Anzahl Prozessoren auf und arbeitet die einzelnen Teilmengen sequenziell ab. Dazu bestimmt das Skript in Zeile 1 die Anzahl der Prozessoren (»PMAX«) auf dem System. Ist die Verarbeitung I/O-lastig, kann es durchaus Sinn ergeben, die Anzahl der Prozesse größer als »PMAX« zu wählen, damit ein Prozess arbeiten kann, während ein anderer auf I/O wartet.

01  ${PMAX:=`ls -1d /sys/devices/system/cpu/cpu* | wc -l`}
02 
03 doParallel() {
04   local items item currentProcess=0
05   for item in "$@"; do
06     items[$currentProcess]="${items[$currentProcess]} "$item""
07      shift
08     let currentProcess=$(( (currentProcess+1)%PMAX ))
09   done
10 
11   for (( currentProcess=0; currentProcess<PMAX; currentProcess++ )); do
12      [ -n "${items[$currentProcess]}" ] && 
        eval doSequentiell ${items[$currentProcess]} &
13    done
14  wait
15 }

Leider kennt die Bash nur eindimensionale Arrays, deshalb ist das Konstrukt in den Zeilen 6 und 13 etwas kompliziert. Für jeden Prozess erzeugt das Skript einen langen String innerhalb eines Array-Elements mit den Argumenten für den Prozess (Zeilen 5 bis 9). Anschließend startet das Skript »PMAX« parallele Prozesse (Zeilen 11 bis 14). Die Zeile 12 verhindert leere Verarbeitungen (etwa bei nur zwei Argumenten auf einem Quadcore-Rechner). Und das »eval« in Zeile 12 sorgt dafür, dass die Shell das Quoting aus Zeile 6 richtig interpretiert.

Gleichmäßig ist günstig

Dieses Verarbeitungsschema ist dann optimal, wenn die durchschnittliche Verarbeitungszeit je Item nicht stark schwankt. Leider ist das nicht immer der Fall. Bei der Konvertierung mehrerer Musikstücke etwa könnte eine ungünstige Verteilung von langen und kurzen Stücken dazu führen, dass einzelne Prozesse deutlich eher fertig sind als andere.

Ein weiteres ungünstiges Beispiel ist die Konvertierung von Bildern aus digitalen Kameras. Manche Kameras erzeugen neben der RAW-Datei auch eine JPG- oder Thumbnail-Datei. Wenn nur jede zweite Datei im RAW-Format vorliegt und tatsächlich zu konvertieren ist, dann langweilt sich die Hälfte der Konvertierungsprozesse, weil das Verarbeitungsschema einem Prozess alle RAW- und dem anderen Prozess alle JPG-Dateien zuteilt.

Unabhängig von diesen Problemen kämpft diese Verarbeitungsmethode mit dem Umstand, dass nicht notwendigerweise alle Argumente im Vorhinein bekannt sind. Fallen die späteren Argumente des Skripts nacheinander an, wäre es ungünstig, so lange zu warten, bis alle erzeugt sind, um sie erst dann auf die Verarbeitungsprozesse zu verteilen. Die Lösung für dieses Problem verwendet stattdessen Worker-Prozesse und einen dynamischen Dispatcher.

Abbildung 2: Dispatcher und Worker-Prozesse kommunizieren über Pipes.

Der dynamische Dispatcher

Die Verarbeitungslogik sieht dabei so aus: Das Skript startet eine Reihe von Worker-Prozessen. Ein Dispatcher nimmt Aufträge entgegen und verteilt sie möglichst intelligent auf die Worker. Im Gegensatz zur oben vorgestellten parallelen Lösung, bei der die Arbeitsprozesse alle Argumente beim Start erhalten, muss der Verteiler nun mit den Workern auch nach ihrem Start kommunizieren.

Als Kommunikationskanäle fungieren so genannte Named Pipes oder Fifos. Der Dispatcher unterhält eine Pipe je Worker, in die er die neuen Aufträge schreibt. Eine weitere, dem Dispatcher und den Workern gemeinsame Pipe dient als Rückkanal. Wenn ein Worker nichts zu tun hat, schreibt er seine ID in die Pipe. Der Dispatcher liest nach jedem Auftrag aus der Pipe eine ID aus und schickt den nächsten Auftrag an diesen Worker.

In Listing 4 ist eine solche Implementation abgedruckt. In den Zeilen 1 bis 4 setzt das Programm eine Reihe von Konstanten, falls noch nicht geschehen. Normalerweise definiert der Nutzer nur die Variable »_cmd«. Die Funktion »dispatchWork« in den Zeilen 54 bis 72 ist quasi der öffentliche Teil der Schnittstelle. Zuerst erzeugt die Funktion ein temporäres Verzeichnis für alle Pipes in Zeile 55 (im Skript »controlDir« genannt). Der Befehl »mkfifo« in Zeile 58 legt den Rückkanal an.

001: ${DEBUG:=0}
002: ${_cmd:=echo}
003: ${PMAX:=`ls -1d /sys/devices/system/cpu/cpu* | wc -l`}
004: ${FDOFF:=4}
005:
006: processWorkItem() {
007:   eval $_cmd "$1"
008: }
009:
010: processWorkItems() {
011:   local line workerFifo="$1" dispatcherFifo="$2" id="$3" fd
012:   exec 3<>"$dispatcherFifo"
013:   while ! echo "$id" >&3; do
014:     sleep 1
015:   done
016:   let fd=id+FDOFF
017:   while true; do
018:     read -r -u $fd line
019:     if [ $? -ne 0 ]; then
020:       break
021:     fi
022:     if [ "$line" = "EOF" ]; then
023:       break
024:     else
025:       processWorkItem "$line"
026:       while ! echo "$id" >&3; do
027:         sleep 1
028:       done
029:     fi
030:   done
031:   rm -f "$workerFifo"
032: }
033:
034: startWorker() {
035:   local i fd fifo
036:   for (( i=0; i<PMAX; ++i )); do
037:     workerFifo="$controlDir/worker-$i"
038:     mkfifo "$workerFifo"
039:     let fd=i+FDOFF
040:     eval exec $fd<> "$workerFifo"
041:     processWorkItems "$workerFifo" "$dispatcherFifo" "$i" &
042:   done
043: }
044:
045: stopWorker() {
046:   local i fifo
047:   for (( i=0; i<PMAX; ++i )); do
048:     fifo="$controlDir/worker-$i"
049:     echo "EOF" > "$fifo"
050:   done
051:   wait
052: }
053:
054: dispatchWork() {
055:   local idleId dispatcherFifo  controlDir=`mktemp -d`
056:
057:   dispatcherFifo="$controlDir/dispatcher"
058:   mkfifo "$dispatcherFifo"
059:   exec 3<>"$dispatcherFifo"
060:
061:   startWorker
062:
063:   while read -r -u 0 line; do
064:    read -u 3 idleId
065:    echo "$line" >>   "$controlDir/worker-$idleId"
066:   done
067:
068:   stopWorker
069:
070:   rm -f "$dispatcherFifo"
071:   rm -fr "$controlDir"
072: }

Erklärungsbedürftig ist die Zeile 59. Hier öffnet die Shell den Rückkanal lesend und schreibend, obwohl eigentlich nur ein lesender Zugriff notwendig ist. Das Problem ist, dass bei einem nur lesendem Zugriff auf eine Pipe der Systemcall blockiert. Ein ganz ähnliches Problem ergibt sich auch in der Funktion »startWorker()«. Sie erzeugt für jeden Worker-Prozess eine Pipe (ab Zeile 37) und öffnet sie wieder sowohl lesend als auch schreibend (Zeile 40).

Das zusätzliche »eval« in dieser Zeile ist notwendig, da der Bash-Parser die Eingabeumleitung sehr früh – noch vor der Variablensubstitution – bearbeitet. Deshalb sind auch die Backslashes vor dem Kleiner- und Größerzeichen notwendig. Der Rest sollte selbsterklärend sein.

Listing 4 besteht nur aus Funktionen – andere Skripte inkludieren diese Datei und nutzen dann die Funktion »dispatchWork«. Das Listing 1 sieht damit wie Listing 5 aus.

001 source workDispatcher
002 doDynamic() { _cmd="doSomething" local item for item in "$@"; do echo "$item" done | dispatchWork }

Stolperstellen

Das Skript aus Listing 4 kämpft mit ein paar kleineren Problemen: So hinterlässt ein Kill verwaiste Arbeitsprozesse (das ließe sich aber durch Setzen einer Timeout-Variablen verhindern). Und bei mehr als sechs Prozessen nutzt das Skript Filedeskriptoren (Kanalnummern) größer als 9. Laut Bash-Manual solle man damit “vorsichtig” sein – was immer das heißen mag -, da die Bash selbst diese Deskriptoren eventuell bereits intern nutzt. Als Ausweg kann man den Offset für die Kanalnummern (Zeile 4) anpassen.

Andere Implementierungen sind auch denkbar. So könnten Dispatcher und Worker über Dateien kommunizieren. Der Dispatcher schreibt die Aufträge dann in Worker-spezifische Dateien. Diese pollen auf die Existenz ihrer Worker-Datei, verarbeiten den darin enthaltenen Auftrag und löschen die Datei wieder. Der Dispatcher überprüft dagegen, welche der Worker-Dateien gerade nicht existiert, und weiß so, welcher Worker nichts zu tun hat. Diese Lösung wäre aber durch das ständige Pollen weniger effizient.

Eine Langfassung von Listing 4 findet sich auf dem FTP-Server des Linux-Magazins [2]. Sie erlaubt »dispatchWork« von der Kommandozeile aus aufzurufen:

$ dispatchWork -c "doSomething" Datei1 Datei2 [...] 

Darüber hinaus enthält diese längere Fassung auch einige zusätzliche Kommentare sowie außerdem Switches für optionale Debug-Ausgaben, die es dem Admin erlauben, den Ablauf des Skripts zu beobachten.

Über Rechnergrenzen hinweg

Wer nicht nur die Prozessoren eines einzelnen lokalen Rechners auslasten will, der kann das vorgestellte Prinzip um eine Stufe erweitern. Damit würde ein First-Level-Dispatcher dann mit mehreren Second-Level-Dispatchern auf verschiedenen Rechnern über TCP/IP kommunizieren. Diese Second-Level-Dispatcher würden ihrerseits wiederum mit den eigentlichen Worker-Prozessen reden. Dieses Verfahren wäre allerdings nur etwas für sichere Netze.

Fazit

Vorhandene Shellskripte sind mit wenigen Zeilen zu parallelisieren. Auch andere Skriptsprachen können dieses Schema nutzen, allerdings gibt es dort eventuell bessere Möglichkeiten. Python kennt etwa zusätzlich zur Pipe-Erzeugung (»os.pipe()«) noch das explizite Forken (»os.fork()«) – damit ist eine sehr C-nahe Lösung des Problems möglich. Vielleicht gibt es ja auch schon fertige Module für Python, Perl & Co. (jcb)