Sortieren mit Multithreading

Eine Barriere muss man sich so vorstellen, dass verschiedene Threads jeweils ihre eigene Aufgabe durchführen und dann auf die Barriere „warten“, was bedeutet, dass sie darauf warten, dass alle anderen beteiligten Threads auch auf die Barriere warten, also die davor angesetzte Aufgabe abgeschlossen haben.

Als Anwendung für die sogenannte „Barriere“ habe ich einmal ein kleines C-Programm geschrieben, das eingelesene Zeichenketten sortiert. Über einen Parameter kann man wählen, ob Heapsort oder Flashsort oder Quicksort verwendet wird. Dafür habe ich zwei Funktionen (mit Header-Datei) hsort und hsort_r geschrieben, die das gleiche Interface wie qsort und qsort_r haben, so dass man sie austauschbar nutzen kann. Entsprechend auch drei Funtkionen fsort, fsort_r und fsort_f (mit Headern), die sich an das Interface von qsort anlehnen, aber noch einen zusätzlichen Funktionisparameter haben, der eine Art monotone Hash-Funktion nach double darstellt. Die gegebenen Zeichenketten werden zu möglichst gleichen Teilen auf eine frei wählbare Anzahl Threads verteilt. Jeder Thread sortiert seinen Teil mittels hsort_r oder fsprtr oder qsort_r. Anschließend wird mit einer Barriere sichergestellt, dass alle Threads ihren Teil sortiert haben und dann werden baumartig die Ergebnisse von jeweils zwei Threads zusammengefügt, jeweils gefolgt von einer weiteren Verwendung Barriere. An Schluss bleibt ein Thread mit seinem Ergebnis übrig und das ist das Sortierergebnis.

Bei einer Beispieleingabe mit 8603049 Wörtern war fsort mit einem Thread etwas schneller als qsort und qsort war etwa viermal so schnell wie hsort, aber mit einer größeren Anazhl Threads ließen sich alle drei beschleunigen.
Interessant war auf einem Rechner mit 4 Core-CPU und Hyperthreading, also 8 logischen CPUs, die unter /proc/cpuinfo angezeigt wurden, dass das Sortieren mit mehr Threads bei hsort mehr profitierte als bei qsort und um Faktor 5 schneller wurde, während fsort nur um Faktor 2 schneller wurde.

Das erklärt sich wohl vor allem durch das assymptotisch gute Verhalten von fsort (O(n)), was beim Sortieren großer Datenmengen in einem Thread besonders stark zum Tragen kommt. hsort ist im „worst case“ auch noch O(n \log n)

Threads Messwert Quicksort Heapsort Flashsort
1 real 4.090s 16.909s 3.757s
1 user 4.028s 16.815s 3.686s
1 sys 0.053s 0.053s 0.062s
           
2 real 2.753s 8.915s 2.672s
2 user 4.177s 16.457s 3.925s
2 sys 0.074s 0.054s 0.066s
           
3 real 2.333s 6.584s 2.392s
3 user 4.261s 16.676s 4.159s
3 sys 0.070s 0.064s 0.067s
           
4 real 2.027s 5.288s 2.093s
4 user 4.331s 16.202s 4.137s
4 sys 0.067s 0.072s 0.077s
           
5 real 2.151s 5.013s 2.254s
5 user 4.681s 17.423s 4.567s
5 sys 0.060s 0.056s 0.076s
           
6 real 2.039s 4.519s 2.104s
6 user 5.264s 18.511s 4.892s
6 sys 0.072s 0.062s 0.078s
           
7 real 1.928s 4.127s 2.092s
7 user 5.333s 18.878s 5.265s
7 sys 0.080s 0.056s 0.094s
           
8 real 1.862s 3.879s 1.931s
8 user 5.638s 19.338s 5.380s
8 sys 0.080s 0.061s 0.069s
           
9 real 2.032s 4.079s 2.174s
9 user 5.484s 19.594s 5.460s
9 sys 0.072s 0.066s 0.081s
           
10 real 2.017s 4.040s 2.130s
10 user 5.426s 19.091s 5.356s
10 sys 0.084s 0.080s 0.090s
           
11 real 1.954s 4.055s 2.081s
11 user 5.427s 19.240s 5.460s
11 sys 0.077s 0.081s 0.095s
           
12 real 1.928s 3.842s 2.053s
12 user 5.409s 18.860s 5.462s
12 sys 0.078s 0.075s 0.092s
           
13 real 1.923s 3.884s 2.040s
13 user 5.384s 19.123s 5.511s
13 sys 0.077s 0.072s 0.080s
           
14 real 1.870s 3.793s 2.037s
14 user 5.482s 18.566s 5.610s
14 sys 0.064s 0.070s 0.089s
           
15 real 1.895s 3.679s 1.979s
15 user 5.578s 18.549s 5.554s
15 sys 0.090s 0.067s 0.084s
           
16 real 1.861s 3.790s 1.979s
16 user 5.576s 19.033s 5.640s
16 sys 0.088s 0.085s 0.101s
           
17 real 2.025s 3.885s 2.181s
17 user 5.647s 18.699s 5.799s
17 sys 0.090s 0.076s 0.102s
           
18 real 2.019s 3.879s 2.156s
18 user 5.688s 18.532s 5.723s
18 sys 0.069s 0.107s 0.095s
           
19 real 2.022s 3.918s 2.140s
19 user 5.774s 18.783s 5.681s
19 sys 0.093s 0.085s 0.091s
           
20 real 1.975s 3.774s 2.129s
20 user 5.588s 18.095s 5.732s
20 sys 0.093s 0.087s 0.105s
           
100 real 1.978s 3.263s 2.099s
100 user 5.686s 15.371s 6.034s
100 sys 0.150s 0.115s 0.141s
           
400 real 2.013s 2.996s 2.092s
400 user 5.719s 13.150s 6.184s
400 sys 0.242s 0.185s 0.259s
           
1000 real 1.992s 2.876s 2.106s
1000 user 5.802s 12.608s 6.469s
1000 sys 0.325s 0.250s 0.392s

Man sieht also, was auch zu erwarten ist, dass Parallelisierung beim Sortieren hilfreich sein kann. In diesem Fall eignet sich der Algorithmus gut für die Parallelisierung, weil im ersten Schritt jeder Thread seinen getrennten Bereich sortiert und in den weiteren Schritten jeweils ein Thread die eigenen Daten mit denen eines anderen Threads zusammenfügt, während dieser andere Thread nur auf die Barriere wartet. Es gibt sicher noch bessere Verfahren, das zu parallelisieren, aber man sieht, dass es sich lohnt, wenn man wirklich genug CPUs zur Verfügung hat.

Share Button

Threads oder Prozesse

Zur Parallelisierung einer Software kann man auf Threads und Prozesse zugreifen. Es lohnt sich, diese beiden Ansätze etwas genauer anzuschauen, um die geeignete Wahl treffen zu können.

Warum Parallelisierung?

  • Mehr CPUs nutzen
  • Moore’s law: Anzahl der Transistoren in IC verdoppelt sich ca. alle 2 Jahre.
  • Bis vor ca. 10 Jahren verdoppelte sich die CPU-Leistung auch regelmäßig.
  • Seit ca. 10 Jahren nur noch mehr Cores
  • Nur nutzbar durch Parallelisierung
  • Parallelisierung kann aber auch Dinge vereinfachen.
  • Beispiel Pipes:
cat `find /usr/bin/* -type d -prune -o -type f -print` \
| perl -p -e 's/sch/\\v s/g;s/\r/\n/g;' | strings \
| sort > /tmp/out.log &
  • Startet pro Pipe-Komponente einen Prozess, viel flexibler und meist perfomanter als wenn man Zwischenergebnisse in Dateien zwischenspeichern muss.
  • Integration verschiedener Software-Komponenten.
  • Typische Beispiele:
    • Datenbank
    • Messaging-System
    • SAP
    • Heterogene Software (mehrere Programmiersprachen…)

Probleme bei Parallelisierung

Unabhängig von der verwendeten Technologie muss man sich mit u.a. diesen Problemen auseinandersetzen:

  • Deadlocks (Verklemmung)
  • Fehler bei gleichzeitigem Ressourcenzugriff
  • Overhead der Parallelisierung
  • Erschwerte Fehlersuche

Deadlocks

Beispiel für Deadlock:

  • Zwei parallel laufende Programmteile A und B greifen exklusiv auf zwei Ressourcen X und Y zu.
  • A reserviert sich erst X und dann Y, B reserviert sich erst Y und dann X.
  • Bei ungünstigem Verlauf wartet A endlos auf Y und B endlos auf X.

Fehler bei gleichzeitigem Ressourcenzugriff

  • Beispiel Datenstruktur wird von Programmteil A und Programmteil B gleichzeitig verwendet.
  • Wenn beide Zugriffe nur lesend sind, ist das ok.
  • Wenn einer schreibt, kann es Inkonsistenzen geben, wegen Pointern sogar Programmabstürze, merkwürdige Fehler u.s.w.
  • Schwierig zu finden
  • Tritt oft erst auf dem Produktivsystem auf, beim Testen scheint alles gut zu sein.

Overhead

Wenn man Software parallelisiert muss man zusätzlich Dinge tun, die man sonst nicht braucht:

  • Locking
  • Kommunikation
  • Synchronisation
  • Memory
  • Mehr Entwicklungsaufwand

Das kann sich aber lohnen.
Besser frühzeitig daran denken!!!

Wie zähmt man die Parallelisierung?

  • In Applikationsentwicklung mit geeigneten Werkzeugen, Frameworks,…
  • In der Praxis viele Probleme und oft wenig Gewinn
  • Aber es gibt Wege die funktionieren..
  • Traum: Compiler parallelisiert automatisch
  • Aber für Systemprogrammierung explizite Kontrolle wichtig!

Threads oder Prozesse

Threads oder Prozesse???

Man kann für die Parallelisierung drei Wege gehen (oder Kombinationen daraus):

  • Prozesse
  • Threads auf OS-level
  • Eigener Mechanismus (User Threads)

Prozesse

  • Prozesse haben ihren eigenen Speicherbereich
  • Können auf verschiedenen Rechnern laufen
  • Explizite Kommunikation
  • Mit shared memory kann man auch gemeinsamen Speicher nutzen
  • Mehr Overhead als Threads

Threads

  • Threads laufen auf derselben Maschine
  • Teilen sich dasselbe Memory
  • Trennung muss man explizit erzwingen

Funktionsweise Prozess (POSIX)

  • Ein neuer Prozess wird mit fork() erzeugt
  • Dupliziert den ganzen Speicher
  • Effizient wegen copy-on-write
  • Achtung: overcommit
  • Danach (meistens) exec

Unter MS-Windows wird das Erzeugen eines neuen Prozesses und das Starten eines neuen Programms gleichzeitig in einem Schritt ausgeführt.

IPC

Interprozesskommunikation:

  • Signale
  • Pipe (named oder anonym)
  • Semaphore (Locks)
  • Shared Memory
  • Socket
  • Message Queue
  • File
  • Memory-mapped File
  • High-Level-Mechanismen (DB, Messaging, Corba, Rest, Soap, RPC,…)

Threads (Posix)

  • Mit pthread_create(…) erzeugen
  • Mit pthread_join(…) “einsammeln”
  • Funktion void *f(void *) übergeben
  • In C++ 11 in die Sprache integriert

Was soll man bevorzugen

Es hängt von der Ausgangslage ab.

Entwickelt man mit Ruby oder Perl, sind vielleicht mehrere Prozesse besser, weil Threads in diesen Sprachen nicht so gut unterstützt werden. Entwickelt man mit Scala oder Java, sind Threads vielleicht besser, weil das dort das gängige und gut unterstützte Parallelisierungsverfahren ist und weil JVM-Prozesse jeweils recht schwergewichtig sind, was den Speicherverbrauch betrifft.

Entwickelt man in C oder C++ und hat mehr oder weniger alle Möglichkeiten des Betriebssystems zur Verfügung, dann sind beide Wege gut gangbar. Man kann mit Shared Memory und anderen IPC-Mechanismen mehrere Prozesse zusammenspannen, aber auch mehrere Threads. Man muss sich in jedem Fall darum kümmern, dass gemeinsam genutzte Ressourcen konsistent bleiben und insbesondere nicht in inkonsistentem Zustand gelesen werden.

Man sollte beide Möglichkeiten kennen und im Einzelfall entscheiden, welcher Weg sich am besten eignet.

Share Button

Java 8

Java 8 ist erschienen.
Das bedeutendste neue Feature sind die Lambda-Expressions, die es unter anderem erleichtern, funktional zu programmieren.

Share Button

Mathematical Formulas in WordPress

Deutsch

This blog uses the Plugin WP QuickLaTeX which gets its \LaTeX-rendering done by QuickLaTeX.

If only a page starts with [{\sf latexpage}], formulas can be embedded with \backslash(\ldots\backslash) or \backslash[\ldots\backslash]. They have to be written in LaTeX-notation.

So this blog can use formulas like for example:

    \[ \bigwedge_{z\in\Bbb C}\, \sin z = \sum_{k=0}^\infty \frac{(-1)^k z^{2k+1}}{(2k+1)!}=z-\frac{z^3}{6}+\frac{z^5}{120}-\frac{z^7}{5040}+\ldots \]

    \[ \bigwedge_{z\in\Bbb C}\, \cos z = \sum_{k=0}^\infty {\frac{(-1)^k z^{2k}}{(2k)!}}=1-\frac{z^2}{2}+\frac{z^4}{24}-\frac{z^6}{720}+\ldots \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \tan z = \frac{\sin z}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \cot z = \frac{\cos z}{\sin z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \sec z = \frac{1}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \csc z = \frac{1}{\sin z} \\ \end{align} \]

    \[ \sec(z) = 4\pi \, \sum_{k=0}^{\infty} \frac{(-1)^k(2k+1)} {(2k+1)^2 \pi^2 - 4 z^2 } \]

    \[ \csc(z) = \frac{1}{z} - 2z \, \sum_{k=1}^{\infty}\frac{(-1)^k} {k^2\pi^2-z^2} = \sum_{k=-\infty}^\infty \frac{(-1)^k \, z}{z^2-k^2\pi^2} \]

So I am making use of this, whenever it seems to make sense, so it can be avoided to write mathematical formulas in some unintelligable ASCII-text.

Why don’t we have that in the development environments of modern programming languages? If a formula is given, it could be written in a much nicer way, at least in the comments. I understand that Donald E. Knuth has introduced the concept of literate programming many decades ago. The source file is a .web, .cweb or .fweb file from which the illiterate source and the TeX-documentation can be produced using weave and tangle or cweave and ctangle or fweave and ftangle. This allows for excellent readable printouts and compilable programs from the common (literate) source file. A little bit of this idea has gone into the idea of javadoc and rubydoc and perldoc, but a conveniant and powerful mechanism for mathematical formulas would still be appreciated.

Share Button

Dämonisierung von Prozessen

Auf Unix- und Linux-artigen Systemen laufen immer einige sogenannte Daemon-Prozesse. Diese laufen im Hintergrund, haben also keine Verbindung mit einem Terminal.
Beim Start kann man eine sogenannte Daemonisierung verwenden. Man startet von dem interaktiv gestarteten Prozess einen Child-Prozess. Dieser hat noch Verbindung zum ersten und damit zum Terminal. Nun startet man von diesem den eigentlichen Daemon-Prozess und beendet den Child-Prozess. Nun ist die Verbindung zum Parent-Prozess gekappt und der Daemon-Prozess wird damit zum Child-Prozess des Init-Prozesses. Wenn sich der Daemon beendet, wird durch init regelmäßig wait() aufgerufen und damit verhindert, dass dieser als Zombie-Prozess noch lange im System unterwegs ist. Nun muss der Daemon-Prozess aber informiert werden, wann der Child-Prozess beendet ist.
Dies kann wie folgt erfolgen:

/* (C) IT Sky Consulting GmbH 2014
 * http://www.it-sky-consulting.com/
 * Author: Karl Brodowsky
 * Date: 2014-02-27
 * License: GPL v2 (See https://de.wikipedia.org/wiki/GNU_General_Public_License )
 */

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <signal.h>

int daemonized = 0;

void signal_handler(int signo) {
  daemonized = 1;
}

int main(int argc, char *argv[]) {
  int fork_result;
  int ret_code;
  int status;
  int pid = getpid();

  /* set pgid to pid */
  setpgid(pid, pid);
  signal(SIGUSR1, signal_handler);

  /* first fork() to create child */
  fork_result = fork();
  if (fork_result == 0) {
    printf("In child\n");

    /* second fork to create grand child */
    fork_result = fork();
    if (fork_result != 0) {
      /* exit child, make grand child a daemon */
      printf("exiting child\n");
      exit(0);
    }
    
    /* in daemon (grand child) */
    pid = getpid();
    while (! daemonized) {
      pause();
    }

    printf("daemon has pid=%d pgid=%d ppid=%d\n", pid, getpgid(pid), getppid());

    /* do daemon stuff */
    sleep(30);
    printf("done with daemon\n");
    exit(0);
  }
  printf("parent waiting for child\n");
  wait(&status);
  printf("child terminated\n");
  kill(-getpid(), SIGUSR1);
  printf("parent done\n");
}

Durch das Setzen einer Prozessgruppen-ID ist es möglich, den Parent-Prozess, den Child-Prozess und den Daemonprozess auch über diese gemeinsame Gruppen-Id anzusprechen, ohne die eigentliche pid zu kennen. Negative Werte als Funktionsparameter für Funktionenen, die dort eine Prozess-Id (pid) erwarten, werden oft als pgid (Prozessgruppen-ID) interpretiert. Wenn der Child-Prozess beendet ist, wird das wait im Parent-Prozess beendet und dieser schickt ein Signal an den Daemon-Prozess, das von diesem ignoriert wird, aber zur Beendigung des Wait-Prozesses führt.

Für ein kleines Beispiel mag es noch akzeptabel sein, nach stdout zu schreiben, aber die Ausgaben eines Daemons sollten natürlich am Ende in einer Log-Datei landen. Das kann durch Ausgabeumleitung oder noch schöner durch Verwendung von syslog geschehen, ist aber ein Thema für sich.

Share Button

Logging

Software enthält häufig eine Log-Funktionalität. Üblicherweise werden dort ein- oder mehrzeilige Einträge in eine Datei, nach syslog oder in die Standardausgabe geschrieben (und letzlich in eine Datei umgeleitet), die etwas darüber sagen, was die Software so macht. Normalerweise kann man das alles ignorieren, aber sobald dort etwas mit „ERROR“ auftritt oder schlimmer noch sogenannte Stacktraces, ist eigentlich angesagt, dass man dem Problem auf den Grund geht. Da nun leider Software häufig von minderer Qualität ist, was durchaus von den Unzulänglichkeiten der verwendeten Libraries und Frameworks kommen kann, sieht man das leider recht oft, teilweise so oft, dass man denen nicht mehr wirklich nachgeht. Ärgerlich ist vor allem, dass der eigentliche Fehler oft vorher an einer ganz anderen Stelle aufgetreten ist, sich aber in der Log-Datei nicht nachvollziehen lässt.

Nun ist es schön, dass die Log-Dateien einen gewissen Aufbau der Einträge einhalten. Meist beginnen sie mit einer Zeitangabe im ISO-Format, oft auf die Millisekunde genau. Da in der Regel mehrere Prozesse oder mehrere Threads gleichzeitig laufen, werden deren Einträge natürlich mehr oder weniger wild gemischt. Das ist gut erträglich, wenn auch mehrzeilige Log-Einträge (z.B. Stack-Traces) zusammen bleiben und wenn sich Anfang und Ende von mehrzeiligen Log-Einträgen gut erkennen lassen. Man kann dann mit Splunk oder mit Perl- oder Ruby-Scripten die Log-Dateien analysieren und jeweils für einzelne Threads die Abläufe nachvollziehen. Das Zusammenhalten mehrzeiliger Einträge lässt sich realisieren, indem man ein atomares write verwendet oder indem man einen „Logger-Thread“-hat und alle Log-Einträge diesem Thread in einer Queue zur Verfügung stellt, die dieser dann abarbeitet und herausschreibt.

Insgesamt ist das ganze Thema aber unübersichtlich und unhandhabbar geworden. In der Java-Welt hatte man früher log4j und eine relativ einfache Konfigurations-Datei im properties-Format. Das wurde dann irgendwann durch XML ersetzt und es kamen andere Logging-Frameworks dazu und jeweils immer wieder etwas, was alle diese vereinheitlichte. Letztlich wurde es dadurch komplizierter und unübersichtlicher.

Es stellt sich die Frage, wie viel von der Logik für die Handhabung der Log-Dateien in die Software selbst gehört. Muss die Software wissen, in welche Datei geloggt wird? Muss sie Log-Rotation kennen? Muss es sein, dass eine Software überhaupt nicht startet, nur weil man es nicht schafft, die komplizierte Log-Konfiguration richtig einzustellen? Letztlich müssen die Log-Dateien am Ende den Systemadministrator zufriedenstellen, der die Software auf dem Produktivsystem betreibt. Soll man diesem zumuten, für jede Software eine spezielle Konfiguration des Logging zu pflegen? Oder für diesen Zweck jeweils von den Entwickerln eine neue Software-Version anzufordern, weil die Konfiguration als Teil des Deployments „hardcodiert“ ist? Interessant wird es auch dann, wenn man auf Technologien wie „Platform as a Service“ (PAAS) setzt, wo man Applikationsserver, Framework, Datenbank u.s.w. zur Verfügung hat, aber wo die Software ohne weiteres den Server wechseln kann und damit Dateien verloren gehen.

Ist es vielleicht einfach die bessere Lösung, unter Einhaltung eines vernünftigen Formats nach stdout zu loggen die Software so laufen zu lassen, dass deren Standardausgabe (stdout oder stderr) in einen logmanager geleitet wird? Dieser kann dann für alle Software, die auf dem System läuft, verwendet werden und vom Systemadministrator einheitlich konfiguriert werden. Einheitlich heißt nicht nur, für alle Java-Programme gleich, sondern für alle Software, die sich dazu bringen lässt, ihre Log-Ausgabe nach stdout zu schreiben und gewisse Mindestanforderungen an das Format einzuhalten. Im Prinzip ließe sich mit named-Pipes auch eine beliebig hard-codierte Log-Datei unterstützen, aber das macht die Dinge nur komplizierter. Wenn dann das Logging-Framework der Software selbst noch Log-Rotation unterstützt, kann das natürlich durcheinandergeraten, wenn etwa nach n geschriebenen Bytes oder m Sekunden die named-pipe geschlossen, umbenannt und eine neue Datei angelegt wird, was je nach Schreibrechten in dem Verzeichnis zu verschiedenen Fehler führt.

Was ist jetzt mit Software, die selbst als Filter fungiert, wo also stdout Teil der Funktionalität ist? Solche Software findet man üblicherweise in Form kleinerer Programme oder Skripte, die nicht unbedingt Log-Dateien schreiben müssen oder in Form von gut ausgetesteter Software, die Teil der Installation ist. Oft kann man hier mit stderr für Log-Ausgaben, in diesem Fall meist für Fehlermeldungen, auskommen. Oder man könnte eine Log-Datei auf der Kommandozeile angeben, was dann auch wieder für den Systemadminstrator leicht zugänglich wäre und auf eine named-pipe umleiten könnte.

Share Button