Sequentialisierung

Unter Sequentialisierung oder Sequenzialisierung versteht man das Schaffen einer Ordnung für eine Menge von Aktionen entlang der Kausalordnung, die z. B. 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ögliche Sequenzialisierungen, die aber alle zu dem gleichen Ergebnis führen (sonst wären es eben keine korrekten Sequenzialisierungen).

Die Sequenzialisierung ist das Gegenteil der Parallelisierung.

Anwendung

Die Sequenzialisierung von Operationen ist insbesondere bei der Ressourcenplanung (Scheduling) wichtig, um eine Verklemmung (Deadlock) zu vermeiden. Auch für die Integrität von Transaktionssystemen ist sie entscheidend. Anwendung findet hier zum Beispiel der Peterson-Algorithmus oder der Dekker-Algorithmus. Ein anschaulichen Beispiel für das Problem der Ressourcenplanung bietet das Philosophenproblem.

Die nachträgliche Sequenzialisierung von Nachrichten auf Grund von Zeitstempeln ist dagegen in Verteilten Systemen wichtig, sowohl im Betrieb als auch zur Analyse (siehe dazu Logische Uhr).

Beispiel

Beispiel eines Funktionsbaums für Spaghetti Bolognese

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 Sequenzialisierungen (wenn wir außer Acht lassen, dass die Spaghetti kalt werden könnten etc.):

• Gemüse schnippeln, Hackfleisch braten, zusammenrühren, Sauce kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
• Hackfleisch braten, Gemüse schnippeln, zusammenrühren, Sauce kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
• Wasser kochen, Hackfleisch braten, Gemüse schnippeln, Spaghetti kochen, zusammenrühren, Sauce kochen, Spaghetti Bolognese.
• …und noch einige andere Kombinationen.

Dagegen sind die folgenden Reihenfolgen keine korrekten Sequenzialisierungen:

• Gemüse schnippeln, Spaghetti kochen (Abbruch: kann keine Spaghetti kochen, weil das Wasser noch nicht heiß ist).
• Gemüse schnippeln, zusammenrühren (Abbruch: kann nicht zusammenrühren, weil Hackfleisch noch nicht gebraten wurde).
• Gemüse schnippeln, Hackfleisch braten, zusammenrühren, Sauce kochen, Wasser kochen, Spaghetti Bolognese (Abbruch: Spaghetti fehlen).
• …und so weiter.

Siehe auch

• Topologische Sortierung