Elixir II

Da ich das Glück hatte, an einer halbtägigen Elixir-Schulung teilzunehmen, möchte ich das Thema wieder aufgreifen.

Elixir ist eine relativ neue Programmiersprache, die sich von der Syntax an Ruby anlehnt. Die Programme laufen auf der Erlang-VM (BEAM). Diese VM ist anscheinend restriktiver als die Java-VM und so ist Elixir von den Konzepten her auch sehr nahe an Erlang.

Grundsätzlich ist Elixir wie Erlang eine funktionale Sprache, nicht wie Ruby objektorientiert. Es gibt aber die Möglichkeit, Strukturen aus Listen und Tupeln aufzubauen und weiterzugeben. Alle diese Strukturen sind immutable. Das heißt, dass Änderungen daran stets das Original unverändert lassen und eine Kopie mit den Änderungen generieren. Im Falle von verketteten Listen funktioniert das gut, wenn man nur am Anfang ein Element hinzufügt, weil dann kein eigentliches Kopieren erforderlich ist. Fügt man am Ende etwas hinzu, muss die Liste kopiert werden, was eine aufwändigere Operation ist. Es gibt keine Schleifen, wie in den meisten herkömmlichen Programmiersprachen, sondern man verwendet stattdessen Rekursion. Endrekursion sollte bevorzugt werden, weil das intern in Schleifen umgewandelt wird. Über die Parameterliste dieser Funktion kann man einen „Zustand“ weiterreichen.

Es ist sehr einfach und auch üblich, „Prozesse“ zu generieren. Dies sind nicht OS-Prozesse, sondern Konstrukte innerhalb von Erlang, man kann etwa an Aktoren denken, wie es bei Scala und Akka genannt wird. Wenn genug Hardware-Ressourcen vorhanden sind, kann man ohne weiteres mehrere Millionen solcher „Prozesse“ gleichzeitig haben. Jeder Prozess hat seinen eigenen Speicher und kann jedem anderen Prozess mit

send(...)

Nachrichten (messages) senden. Diese werden in eine sogenannte Mailbox (eine Warteschlange / engl. Queue) des Prozesses eingefügt und von diesem mit

receive(...)

empfangen. Das typische Muster ist, dass ein Prozess mittels Rekursion in einer Endlosschleife ist und jeweils mit receive Messages empfängt und verarbeitet.

Über diese Prozesse kann man doch so etwas wie einen Zustand modellieren. Man hat einfach einen Prozess mit so einer Endlosschleife und schickt ihm „set“- und „get“-Nachrichten. Die „set“-Nachrichten ändern den Zustand, der in der Endlosschleife über die Parameter weitergereicht wird, die get-Nachrichten lösen aus, dass eine Nachricht an den Absender geschickt wird, die dieser wiederum mit receive abfangen muss.

Funktionen mit gleichem Namen werden nach der Anzahl der Parameter, nicht aber nach dem Typ der Parameter, unterschieden. Die Sprache ist dynamisch typisiert. Man kann statt ein großes „if“ innerhalb einer Funktion zu haben, diese auch für verschiedene Fälle definieren und es wird für den tatsächlichen Aufrufparameter die richtige Teildefinition gefunden.

Share Button

Numerische Typen

Es geht hier nicht um dynamische oder statische Typsisierung, sondern eher darum, was von den Programmiersprachen an Funktionalität für numerische Typen angeboten wird. Irgendeine Form der Typisierung (dynamisch oder statisch) ist natürlich erforderlich, damit das funktionieren kann. Im Extremfall reicht vielleicht sogar der Ansatz, dass durch die Funktionsnamen unterschieden wird, als welche Typen die Eingabeparameter zu interpretieren sind, was z.B. bei Assemblersprachen praktisch durchgängig so üblich ist.

Was ich bei numerischen Typen sehr wichtig finde, ist dass man die Formeln, die die Berechnung beschreiben, so hinschreiben kann, wie sie sind, also z.B.

    \[ a = b \cdot c + d \cdot e \]

oder

a = b * c + d * e

oder gerne auch

a := b (*) c (+) d (*) e

statt

a = (b * c) + (d * e),

denn „Punktrechnung vor Strichrechnung“ lernt man in der Grundschule und das sollte zumindest bei Leuten, die sich mit Quelltexten von Software beschäftigen, im Erwachsenenalter sitzen. Damit will ich nicht sagen, dass man jeweils alle Präzendenzhierarchiestufen aller verwendeten Programmiersprachen kennen sollte, aber diese her schon. Smalltalk zwingt einen zu diesen Klammern.

Noch schlimmer ist Java, wo man für die meisten numerischen Typen etwa so etwas schreiben muss:

a = b.multiply(c).add(d.multiply(e));

Da erkennt kaum jemand die Formel wieder und Fehler sind vorprogrammiert…
Für Software, die in größerem Stil Dinge tut, die mit den primitiven numerischen Typen nicht machbar sind, ist Java nicht geeignet. Andere JVM-Programmiersprachen haben Operatorüberladung und erlauben es, mit geringerem Fehlerrisiko solche Dinge zu entwickeln. Eventuell kann auch ein Präprozessor eingesetzt werden, der eine Java-ähnliche Sprache mit einer Form von Operatorüberladung in Java übersetzt.

Was vielleicht auch geht, ist statt Infix auf Postfix- oder Präfixnotation zu wechseln. Ob man da die Formeln noch erkennt, ist ein bißchen eine Gewohnheits-, Geschmacks- und vielleicht auch Fähigkeitsfrage, wobei es sicher gute SW-Entwickler gibt, die einfach nicht den Blick dafür haben, Infix-Notation oder Postfix-Notation zu erkennen. Das sieht dann mit Präfixnotation in Lisp etwa so aus:

(setq a (+ (* b c) (* d e)))

oder mit Postfix-Notation, die man von alten HP-Taschenrechnern oder von Forth oder von der Druckersprache Postscript kennen könnte etwa so:

&a
b
c
*
d
e
*
+
=

oder etwa so:

b ENTER C * ENTER d ENTER e * + STO a

Angeblich soll das verständlicher sein als die Infixnotation, sagen manche HP-Taschenrechner-Fans aus den 80er Jahren.

In diesem Blogbeitrag über Zahlen steht ein bißchen dazu, auf was sich numerische Typen beziehen können. Eine 1:1-Zuordnung ist in der Regel nicht möglich, weil selbst „unbegrenzte“ Ganzzahlen wie bei Ruby oder Lisp in Wirklichkeit durch den Speicher des Rechners begrenzt sind. Aber man kann doch eine realistische Approximation erkennen.

  Ruby Perl Python Java Scala Clojure Elixir C C++
{\Bbb N}, {\Bbb N_0} ? ? ? (unsigned long eingeschränkt da, Überlauf) (unsigned long eingeschränkt da, Überlauf)
{\Bbb Z} nativ (Integer, BigNum) BigInt ? (BigInteger eingeschränkt wegen fehlendem Operator-Überladen) BigInteger nativ nativ (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb Q} Rational Math::BigRat Fraction (externe Libraries, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, eventuell Aufnahme in Standardlibrary geplant. nativ ? (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb R} Float, LongDecimal, BigDecimal ja ? Double, BigDecimal Double, BigDecimal ? ? double double
{\Bbb C} Complex ? ? externe Libraries ohne Operatorüberladung mühsam und fehleranfällig. ? ? ? complex ?

p-adische Zahlung und endliche Körper sind wohl schon zu sehr in der Mathematik angesiedelt und selten nativ in Programmiersprachen zu finden, außer in Programmiersprachen, die gezielt eine mathematiklastige Clientel ansprechen. Dabei sind gerade endliche Körper noch recht wichtig für Kryptographie und Codierungstheorie und werden dort natürlich auch benutzt.

Am schmerzhaftesten ist wohl immer noch, dass so wenige Programmiersprachen einen guten ganzzahligen numerischen Typ in die Sprache integriert haben, der es erlaubt, mit beliebig langen Zahlen (im Rahmen von Hauptspeicher) umzugehen.

Programmiersprachen, die so etwas wie Rational als numerischen Typ kennen, lassen ein gängiges Problem erkennen. Erfahrungsgemäß werden bei längeren Rechnungen Nenner und Zähler sehr sehr groß und die Berechnung entsprechend langsam. Dass man gut kürzen kann, ist eher die Ausnahme. Daran sollte man denken und entsprechende Performance- und Lasttests machen, um zu sehen, ob man in Laufzeit- und Speicherprobleme gerät.

Share Button

Shift- and Rotation Functions

Deutsch

In a comment to Carry Bit: How does it work the question about shift and rotation functions has been asked. Which exist and how they work exactly depends off course on the CPU architecture, but I will try to give a high level overview anyway.

The following aspects have to be considered:

  • 8, 16, 32, 64,… Bit: How many Bits are affected by the operation?
  • Shift vs. Rotate: Shift moves bits to the left or right, filling in 0 or 1 in the positions that get freed by this. The bits that get shifted out usually go to the carry bit, so the last one of these wins, if the shift is done by more than one bit. Rotation means what some English knowledge suggests: The bits shifted out are moved in on the other side.
  • ROL and ROR vs RCL and RCR: Rotation through Carry (RCL or RCR) means that the carry bit participates as bit 9., 17., 33. or 65. ROL and ROR leave the carry bit alone, at least do not use it as input.
  • Logical vs. Arithmetic Shift: This deals with the „sign“. For arithmetic Shift the number is considered to be signed in two’s complement. Therefore right shift does not necessarily introduce a 0 as new most significant bit, but depending on the sign introduces a 0 or a 1.

Current CPUs have barrel shifts or something like that built into the hardware, so shift and rotate operations by more than one bit position are much faster than sequences of single shifts. This technology has been around on better CPUs for decades and is not at all new.

How the commands are called exactly and possibly some details about there operations depend on the CPU architecture.

Examples (8 bit) for shifting and rotating by one bit position:

Vorher (Carrybit in Klammern)ROL
(rotate left)
RCL
(rotate left through carry)
ROR
(rotate right)
RCR
(rotate right through carry)
ASL / SHL
(arithmetic/logical shift left)
SHR
(logical shift right)
ASR
(arithmetic shift right)
00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000000 (1)00000000 (1)00000001 (0)00000000 (1)10000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000001 (0)00000010 (0)00000010 (0)10000000 (0)00000000 (1)00000010 (0)00000000 (1)00000000 (1)
00000001 (1)00000010 (1)00000011 (0)10000000 (1)10000000 (1)00000010 (0)00000000 (1)00000000 (1)
10000000 (0)00000001 (0)00000000 (1)01000000 (0)01000000 (0)00000000 (1)01000000 (0)11000000 (0)
10000000 (1)00000001 (1)00000001 (1)00000001 (1)11000000 (0)00000000 (1)01000000 (0)11000000 (0)
11111111 (0)11111111 (0)11111110 (1)11111111 (0)01111111 (1)11111110 (1)01111111 (1)11111111 (1)
11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111110 (1)01111111 (1)11111111 (1)

These shift and rotate operations are needed to express multiplications by powers of two and division by powers of two. In C, C++, C#, Perl, Java and some other porgramming languages these operations are included and written as „<<" (for ASL or SHL), ">>“ (for SHR) and „>>>“ for ASR.

Links

Share Button

Shift- und Rotationsfunktionen

English

Im Kommentar zu Carry Bit: How does it work ist nach den Shift- und Rotationsfunktionen gefragt worden. Welche es genau gibt, hängt natürlich von der Prozessorarchitektur ab, aber grundsätzlich muss man die folgenden Aspekte beachten:

  • 8, 16, 32, 64,… Bit: Wieviele Bits sind von der Operation betroffen?
  • Shift vs. Rotate: Beim Shift werden an einer Seite Bits als 0 oder 1 ergänzt und auf der anderen Seite wandern sie in das Carry-Bit, beim Rotieren werden Bits im Kreis rotiert, die herausfallenden Bits vom einen Ende werden am anderen Ende wieder eingefügt.
  • ROL und ROR vs RCL und RCR: Beim Rotieren durch Carry wird das Carry-Bit als 9., 17., 33. oder 65. Bit miteinbezogen.
  • Logical vs. Arithmetic Shift: Bezieht sich auf die Vorzeichenbehandlung. Für arithmetic Shift wird die Zahl als vorzeichenbehaftet im Zweierkomplement gelesen wird. Deshalb wird beim Right-Shift nicht zwingend eine 0 als höchstwertiges Bit eingefügt, sondern je nach Vorzeichen eine 0 oder eine 1.

Heutige CPUs haben Barrelshifter oder etwas vergleichbares eingebaut und können deshalb auch Shift- und Rotate-Operationen um mehr als eine Bit-Position schnell ausführen.

Wie die Befehle genau heißen, und welche es gibt, hängt vom Prozessor ab:

Beispiele (8 Bit), Verschiebung oder Rotation nur um eine Bitposition:

Vorher (Carrybit in Klammern)ROL
(rotate left)
RCL
(rotate left through carry)
ROR
(rotate right)
RCR
(rotate right through carry)
ASL / SHL
(arithmetic/logical shift left)
SHR
(logical shift right)
ASR
(arithmetic shift right)
00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000000 (1)00000000 (1)00000001 (0)00000000 (1)10000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000001 (0)00000010 (0)00000010 (0)10000000 (0)00000000 (1)00000010 (0)00000000 (1)00000000 (1)
00000001 (1)00000010 (1)00000011 (0)10000000 (1)10000000 (1)00000010 (0)00000000 (1)00000000 (1)
10000000 (0)00000001 (0)00000000 (1)01000000 (0)01000000 (0)00000000 (1)01000000 (0)11000000 (0)
10000000 (1)00000001 (1)00000001 (1)00000001 (1)11000000 (0)00000000 (1)01000000 (0)11000000 (0)
11111111 (0)11111111 (0)11111110 (1)11111111 (0)01111111 (1)11111110 (1)01111111 (1)11111111 (1)
11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111110 (1)01111111 (1)11111111 (1)

Diese Shift- und Rotate-Operationen braucht man vor allem, um Multiplikation mit Zweierpotenzen und Division durch Zwierpotennzen auszudrücken. In C, C++, Perl, Java und einigen anderen Programmiersprachen gibt es diese Operationen „<<" (für ASL oder SHL), ">>“ (für SHR) und „>>>“ für ASR.

Share Button

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

English

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