Sequentialisierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel erläutert den allgemeinen Begriff, zu anderen Bedeutungen siehe Sequenz.

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[Bearbeiten]

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[Bearbeiten]

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, Soße kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
  • Hackfleisch braten, Gemüse schnippeln, Zusammenrühren, Soße kochen, Wasser kochen, Spaghetti kochen, Spaghetti Bolognese.
  • Wasser kochen, Hackfleisch braten, Gemüse schnippeln, Spaghetti kochen, Zusammenrühren, Soße 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, Hackfleisch braten, Zusammenrühren, Soße kochen, Wasser kochen, Spaghetti Bolognese (Abbruch: Spaghetti fehlen).
  • …und so weiter.

Siehe auch[Bearbeiten]

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.