In der Informatik wird seit gut 10 Jahren die Mehrkernkrise (multi­core crisis) als Motivation für verschiedenste Lösungsansätze genannt. Dies ist ein Versuch, das Problem für Nicht-Informatiker zu verdeutlichen.

Seit Jahrzehnten verdoppelt sich die Anzahl an Transistoren auf einem Computerchip alle 18 Monate. Bis ungefähr 2001 bedeutete das, dass Rechner immer schneller wurden und damit auch die Software schneller lief. Man erinnere sich an frühere Werbeprospekte, wo Rechner mit 1GHz, 2GHz und dann 3GHz angeboten wurden. Heute wird nicht mehr die GHz-Zahl gesteigert, weil wir hier an physikalische Grenzen gestoßen sind. Stattdessen baut man einfach mehrere Rechnerkerne auf einen Prozessor. In den Werbeprospekten liest man nun von Single-Core, Dual-Core und Quad-Core. Voraussichtlich geht der Trend weiter, so dass wir irgendwann hunderte von Kernen in unseren Rechnern haben. Das Problem dabei ist, das unsere Software dadurch nicht automatisch schneller wird.

Damit Programme mehrere Kerne ausnutzen können, müssen sie nebenläufig programmiert sein und das ist schwieriger als normale sequentielle Programmierung. Die Mehrkernkrise besteht im Kern aus Milliarden Seiten von altem Code, der zwar funktioniert, der aber umgeschrieben werden muss. Dabei müssen meistens ganz neue Algorithmen verwendet oder erfunden werden.

Aber warum ist nebenläufiges Programmieren schwieriger als Sequentielles?

Beispiel für Nebenläufigkeit

Als Analogie nehmen wir mal an, wir betreiben ein kleines Kino. Wir haben einen Ticketschalter und einen Angestellten names Kevin, der leider ziemlich dumm ist. Deswegen geben wir im detaillierte Anweisungen, was er zu tun hat. Kevin arbeitet diesen Algorithmus stur ab.

Schauen wir uns die Teil mit der Platzreservierung genauer an. Wenn Kevin ein Ticket verkauft, reserviert er gleich ein Platz mit. Dazu zeigt er dem Besucher welche Plätze frei sind und dieser sucht sich einen aus. Dann markiert Kevin den Platz als besetzt. Das ist ein einfacher sequentieller Algorithmus mit zwei Schritten (Auswählen und Markieren).

Nehmen wir nun an, das Geschäft blüht und sehr viel mehr Besucher wollen ins Kino. Ein Schalter und ein Angestellter reichen nicht mehr aus. Also wird Jaqueline eingestellt, die an einem zweiten Ticketschalter sitzt. Und wie stimmen sich die beiden im Bezug auf die freien Plätze ab? Naja, wenn einer einen Platz blockiert, dann sagt er das dem anderen, so dass auch dort der Platz markiert wird.

Leider kann es nun ein Problem beim Reservieren geben. Jeweils ein Besucher bei Kevin und Jaqueline bekommen im gleichen Moment die gleiche Auswahl an freien Plätzen gezeigt. Dummerweise suchen sie den gleich Platz aus. Kevin und Jaqueline drehen sich im selben Moment zueinander um und melden den Platz als vergeben. Falls die beiden schlau wären, könnte man ja einen der Besucher umbuchen. Leider kommt der Fall in unserem Algorithmus nicht vor, so dass weder Kevin noch Jaqueline einen Finger krümmen. Im Kino streiten sich die beiden Besucher um den Platz und verderben die Vorführung für den Rest der Besucher.

Wir brauchen bessere Anweisungen, die mit solchen nebenläufigen Situationen umgehen können. Ein paar Ideen:

  1. Kevin vergibt die Plätze auf der rechten Seite und Jaqueline die linken Plätze. Funktioniert nicht für große Gruppen, die eine ganze Reihe reservieren möchten. Außerdem könnten wir in die Situation kommen, dass Kevin einen Besucher heimschickt, weil alle seine Plätze voll sind, obwohl Jaqueline noch Platz gehabt hätte.
  2. Es gibt nur ein Blatt, wo die Plätze als blockiert markiert werden. Kevin und Jaqueline müssen dieses Blatt austauschen. Das funktioniert korrekt, macht das Ganze aber fast genauso langsam, als ob wir nur einen Schalter hätten, weil immer einer von beiden die ganze Zeit auf das Blatt wartet.
  3. Es gibt für jede Sitzreihe ein eigenes Blatt zum Markieren. Das ist in vielen Fällen schneller, wenn man davon ausgeht, dass Besucher sich selten gleichzeitig die selbe Reihe aussuchen.

Die dritte Idee sieht doch ganz praktikabel aus, aber ich denke es ist klar, dass das etwas komplizierter ist, als in der Zeit als Kevin alleine war.

Das war im Prinzip die Dual-Core Version. Wie steht es im Fall von hunderten von Ticketschaltern? Man denke da zum Beispiel an Plätze im Flugzeug, die ja von vielen Reisebüros und Flughafenschaltern aus reserviert werden können.

Der motivierte Leser darf darüber weiter nachdenken. Warum nebenläufige Programme komplizierter sind als Sequentielle sollte bereits deutlich geworden sein.

© 2012-03-02
qznc