Sequentialisierung

Unter Sequentialisierung versteht man das schaffen einer Ordnung für eine Menge von Aktionen entlang der Kausalordnung, die zum Beispiel durch einen Funktionsbaum gegeben ist. Der Sinn ist es, eine Reihenfolge zu finden, in der die Aktionen hintereinander ausgeführt werden können, so dass jede Aktion, die das Ergebnis einer anderen benötigt, erst ausgeführt wird, wenn dieses Ergebnis vorliegt. Die Reihenfolge, in der dabei nebenläufige (kausal unabhängige) Aktionen ausgeführt werden, ist beliebig. So ergeben sich oft mehrere mögliches Sequentialisierungen, die aber alle zu dem gleichen Ergebnis führen (sonst wären es eben keine korrekten Sequentialisierungen).

Die Sequentialisierung ist das Gegenteil der Parallelisierung.

Anwendung

Die Sequentialisierung von Operationen ist insbesondere bei der Resourcenplanung (Scheduling) wichtig um Deadlocks zu vermeiden. Auch für die Integrität von Transaktionssystemen ist sie entscheident. Die nachträgliche Sequentialisierung von Nachrichten auf Grund von Zeitstempeln ist in Verteilten Systemen wichtig, sowohl im Betrieb, als auch zur Analyse (siehe dazu Logische Uhr).

Beispiel

Die Abbildung zeigt einen stark vereinfachten Funktionsbaum für die Zubereitung von Spaghetti bolognese. Wenn wir nun einen Koch hätten, der immer nur eine Aufgabe auf einmal erfüllen kann, müssen wir eine Reihenfolge festlegen, in denen er diese Dinge tun muss. Aus der Abbildung ergeben sich mehrere möglichen Sequentialisierungen (wenn wir außer Acht lassen, dass die Spaghetti kalt werden könnten, etc):

Gemüse schnippeln, Hackfleisch braten, Zusammenrühren, Sosse kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
Hackfleisch braten, Gemüse schnippeln, Zusammenrühren, Sosse kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
Wasser kochen, Hackfleisch braten, Gemüse schnippeln, Spaghetti kochen, Zusammenrühren, Sosse kochen, Spaghetti Bolognese.
...und noch einige andere Kombinationen.

Dagegen sind die folgenden Reihenfolgen keine korrekten Sequentialisierungen:

Gemüse schnippeln, Spaghetti kochen (Abbruch: kann keine Spaghetti kochen, weil das Wasser noch nicht heiß ist).
Gemüse schnippeln, Hackfleisch braten, Zusammenrühren, Sosse kochen, Wasser kochen, Spaghetti Bolognese (Abbruch: Spaghetti fehlen).
...und so weiter.