Die Begriffe sequenziell und nebenläufig beziehen sich auf zeitliche Abläufe, wie sie auf Rechnern, zum Beispiel bei der Abarbeitung von Programmbefehlen, entstehen. Computer sind taktgesteuert, und jeder Rechner enthält dafür einen Taktgeber. Das ist ein regelmäßig schwingender Kristall, aus dessen Schwingungen durch Zählung die Systemuhr und alle anderen Uhren des Rechners abgeleitet werden. Eine Uhr ist ein Zähler, und der Ablauf der Zeit führt zu einem monotonen Steigen des Zählerstands. Ein Zeitpunkt auf einem Rechner ist ein bestimmter Zählerstand und wird durch eine natürliche Zahl repräsentiert. Von zwei Zeitpunkten t1 und t2 kann durch einen Zahlenvergleich immer festgestellt werden, in welcher Beziehung sie zueinander stehen. Entweder es gilt
Gehören zwei Zeitpunkte t1 und t2 zu ein und derselben Uhr und ist t1 < t2, dann beschreibt diese Kleiner-Beziehung zwischen den beiden Zählerständen ein zeitliches Vorher bzw. ein zeitliches Nachher.
Gehören die beiden Zeitpunkte jedoch zu verschiedenen Uhren, dann kann ihnen nicht so ohne weiteres ein Vorher oder Nachher zugeordnet werden. Dazu betrachte man zwei Rechner eines verteilten Systems, die nach Vorgabe autonom arbeiten und über keine gemeinsame Uhr verfügen. Die Taktgeber der beiden Rechner schwingen unabhängig voneinander. Sie sind zu verschiedenen Zeitpunkten gestartet worden und auch ihre Schwingungsdauern stimmen nicht genau überein. Die folgende Grafik zeigt zwei Rechner mit ihren beiden Uhren und drei hervorgehobenen Zeitpunkten t1, t2 und t3:
Ein Zahlenvergleich zwischen t1 und t3 würde zu dem falschen Ergebnis führen, dass der Zeitpunkt t3 (mit dem Zählerstand 118) vor dem Zeitpunkt t1 (mit dem Zählerstand 121) liegt. Eine solche Fehlinterpretation eines Zahlenvergleichs kann, wie das folgende Beispiel zeigt, fatale Folgen haben. Angenommen, auf dem Rechner1 der Grafik arbeite ein Java-Entwicklungswerkzeug, das zu einer Java-Quelldatei jeweils vermerkt, zu welchem Zeitpunkt sie letztmalig kompiliert worden ist. Das Entwicklungswerkzeug soll so arbeiten, dass es jedes Mal, wenn ein Java-Programm gestartet werden soll, prüft, ob zugehörige Quelldateien seit dem letzten Kompilieren verändert worden sind. Ist das der Fall, werden diese (und nur diese) Quelldateien neu übersetzt. Dann erst wird das Programm gestartet. Dieses Entwicklungswerkzeug auf dem Rechner1 der Grafik soll eine Java-Quelldatei A.java zum Zeitpunkt t1 (mit dem Zählerstand 121) letztmals kompiliert haben.
Weiter angenommen, die Java-Quelldatei A.java werde auf dem Rechner2 der Grafik mit einem Texteditor verändert und der Editiervorgang zum Zeitpunkt t3 (mit dem Zählerstand 118) beendet. Wird diese Datei noch vor dem Zeitpunkt t2 zum Rechner1 übertragen und dessen Java-Entwicklungssystem zum Zeitpunkt t2 (mit dem Zählerstand 127) aufgefordert, das zugehörige Programm zu starten, dann prüft das Entwicklungssystem, ob ein Kompilieren von A.java erforderlich ist und stellt durch einen Zahlenvergleich fest, dass seit dem letzten Kompilieren (zum Zeitpunkt t1 mit Zählerstand 121) die Quelldatei A.java nicht verändert worden ist. A.java wird nicht neu kompiliert, was ein fehlerhaftes Verhalten darstellt.
Die Vorher-Nachher-Beziehung zwischen Zeitpunkten, die zu ein und derselben Uhr gehören, ist transitiv. Das bedeutet, dass für drei Zeitpunkte t1, t2 und t3 einer Uhr gilt:
Diese Feststellung ist sofort einsichtig, da die Vorher-Nachher-Beziehung bei Zeitpunkten auf einer Uhr auf der Kleiner-Beziehung bei den natürlichen Zahlen beruht.
Werden zwei oder mehr Rechner unabhängig voneinander betrieben, dann haben sie im Verlauf ihres Betriebs nichts miteinander zu tun, und das Feststellen eines Vorher oder Nachher von zeitlichen Abläufen zwischen ihnen ist nicht erforderlich. Nur dann, wenn Ereignisse, wie die Abarbeitung eines Befehls, auf dem einem Rechner Ereignisse auf einem anderen Rechner beeinflussen, dann muss feststellbar sein, was früher stattgefunden hat und was erst später. Wie im Abschnitt 1.1 (Begriff verteiltes System) ausgeführt wurde, gibt es in einem verteilten System keine, allen Komponenten gemeinsame Uhr, auf die lokale Zählerstände bezogen werden könnten. Eine Synchronisation aller Systemuhren mit einer externen Uhr, ist, wenn Genauigkeit verlangt wird, aufwändig. Allerdings ist in einem verteilten System kein Bezug auf eine reale Uhrzeit erforderlich, denn es ist ausreichend, wenn festgestellt werden kann, in welcher Reihenfolge Ereignisse auf den beteiligten Rechnern stattgefunden haben. Es genügt, auf jedem Rechner einen Ereigniszähler zu installieren, der monoton steigende Zählerstände erzeugt.
Die Rechner eines verteilten Systems können sich ausschließlich durch einen Nachrichtenaustausch gegenseitig beeinflussen. Wird jeder zu übertragenden Nachricht der Zählerstand des lokalen Ereigniszählers des Absenders mitgegeben, was als Zeitstempel bezeichnet wird, dann kann der Empfänger durch einen Zählerstandsvergleich feststellen, ob ein bestimmtes Ereignis auf dem sendenden Rechner (oder auf seinem eigenen) bereits stattgefunden hat.
Präzisiert wird diese Überlegung durch das Konzept der logischen Uhr. Dabei wird auf jedem, an einem verteilten System beteiligten Rechner ein Zähler, logische Uhr genannt, eingerichtet, der bei jedem auf dem Rechner stattfindenden Ereignis, insbesondere beim Senden einer Nachricht, um 1 erhöht wird. Dieser erhöhte Zählerstand wird der zu sendenden Nachricht als Zeitstempel mitgegeben. Erhält ein Rechner des verteilten Systems eine Nachricht von einem anderen Rechner, dann vergleicht er den Zeitstempel dieser Nachricht mit seiner eigenen logischen Uhr. Angenommen, tS sei der Zeitstempel der erhaltenen Nachricht (Sendezeit) und tE der Zählerstand der logischen Uhr des Empfängers (Empfangszeit), dann verfährt der Empfänger wie folgt:
Die Transitivität der Vorher-Nachher-Beziehung gilt durch die logische Uhr jetzt auch rechnerübergreifend. Als Beispiel für eine Umstellung einer logischen Uhr betrachte man die folgende Grafik:
Sie zeigt zwei Rechner mit ihren logischen Uhren und eine durch einen dicken Pfeil symbolisierte Nachrichtenübertragung vom Rechner1 zum Rechner2. Absendezeitpunkt der Nachricht auf dem Rechner1 ist tS mit dem Zählerstand 35. Diese Nachricht erreicht den Rechner2 zum Zeitpunkt tE mit dem Zählerstand 13. Da tS ≥ tE ist, stellt der Rechner2 seine logische Uhr auf den Zählerstand (tS+1), also auf 36. Damit ist jetzt durch einen Zahlenvergleich feststellbar, ob eine Uhrzeit (ein Zählerstand), der zu einem der beiden Rechner gehört, vor TE liegt.
Die Vorher-Nachher-Beziehung führt unmittelbar zu den Begriffen Sequenzialität und Nebenläufigkeit. Zwei Zeitpunkte t1 und t2 sind genau dann in Sequenz, wenn zwischen ihnen eine Vorher-Nachher-Beziehung besteht. Dann kommt entweder
Sie sind genau dann nebenläufig, wenn zwischen ihnen keine Vorher-Nachher-Beziehung besteht. Dann liegt weder
Die folgende Grafik liefert einige Beispiele für die beiden Begriffe:
Zu sehen sind zwei Rechner und eine Nachrichtenübertragung zwischen ihnen (dicker Pfeil). Eingezeichnet sind sechs Zeitpunkte, von denen je drei zu einer der beiden logischen Uhren gehören. Von jedem Zeitpunktepaar kann festgestellt werden, ob sie in einer Vorher-Nachher-Beziehung stehen oder nicht. Beispielsweise sind
Ereignisse nehmen Zeit in Anspruch. Das heißt, dass zu jedem Ereignis ein zeitlicher Ablauf und zu diesem wiederum ein abgeschlossenes Zeitintervall [t1, t2] gehört, wobei t1 vor t2 kommt oder mit t2 identisch ist. Beim Zeitpunkt t1 beginnt der Ablauf, beim Zeitpunkt t2 endet er. Ein Spezialfall liegt vor, wenn die beiden Zeitpunkte zusammenfallen. Das Zeitintervall ist in diesem Fall mit einem Zeitpunkt identisch.
Zeitliche Abläufe werden im Folgenden durch Großbuchstaben bezeichnet. Sind dabei die jeweiligen Anfangs- und Endzeitpunkte von Bedeutung, werden sie in eckigen Klammern an den jeweiligen Großbuchstaben angefügt. Es wird also von einem zeitlichen Ablauf A oder A[ti, tj] gesprochen.
Die Vorher-Nachher-Beziehung zwischen Zeitpunkten kann auf zeitliche Abläufe übertragen werden. Ein zeitlicher Ablauf A[t1, t2] erfolgt genau dann vor einem Ablauf B[t3, t4] (bzw. B erfolgt nach A), wenn t2 vor t3 kommt. Man schreibt dafür
Dafür sagt man oft auch:
Man beachte, dass es, wenn A vor B kommt, zwischen A und B keine zeitlichen Überschneidungen, auch nicht auf den Randpunkten, gibt.
Auch die Begriffe sequenziell und nebenläufig können auf zeitliche Abläufe übertragen werden. Zwei zeitliche Abläufe A und B sind genau dann in Sequenz, wenn zwischen ihnen eine Vorher-Nachher-Beziehung besteht. Es gilt dann
Zwei zeitliche Abläufe A und B sind genau dann nebenläufig, wenn zwischen ihnen keine Vorher-Nachher-Beziehung besteht. Das heißt, dass sich die zeitlichen Abläufe ganz oder teilweise überschneiden können.
Dass zwischen zeitlichen Abläufen keine Vorher-Nachher-Beziehung besteht, kann zwei Ursachen haben:
Eine Nebenläufigkeit, die durch eine redundante Hardware entsteht, wird als Parallelität bezeichnet. Es kann sich um ganze Rechner, Prozessoren, Festplatten, Drucker usw. handeln, die parallel betrieben werden können.
Werden die zeitlichen Abläufe durch ein Time Sharing gesteuert, dann führt dieses Verfahren ebenfalls auf eine Nebenläufigkeit. Als Beispiel betrachte man einen Rechner mit genau einem Prozessor und einer Prozessverwaltung des Betriebssystems, die bei Programmabarbeitungen ein Time Sharing einsetzt. Die folgende Grafik veranschaulicht einen Sachverhalt, bei dem den beiden Programmabarbeitungen A und B abwechselnd der (einzig vorhandene) Prozessor zugeteilt wird:
Zwischen den beiden Programmabarbeitungen A und B besteht keine Vorher-Nachher-Beziehung. Sie finden nebenläufig statt. Diese Art von Nebenläufigkeit wird als Quasi- oder als Pseudoparallelität (pseudo heißt falsch) bezeichnet.
Verteilte Systeme bestehen aus mehreren Rechnern, außerdem enthält nahezu jeder moderne Rechner meist mehrere Prozessorkerne und alle modernen Betriebssysteme steuern ihre Programmabarbeitungen durch ein Time Sharing. Deshalb ist beim Programmieren verteilter Systeme die vorhandene Nebenläufigkeit zu beachten. Ein Nichtbeachten kann zu erheblichen Fehlern führen.
Es gibt zeitliche Abläufe, die müssen, um der Korrektheit des Ergebnisses Willen, sequenziell erfolgen. Werden sie nebenläufig durchgeführt, dann können falsche oder nicht eindeutige Ergebnisse entstehen. Als Beispiel sei die Abarbeitung von zwei Java-Befehlen angeführt, die in einem Programm direkt aufeinander folgen sollen:
Bei einer sequenziellen Abarbeitung der beiden Befehle steht nach dem zweiten Befehl in der Variablen i der Wert 8. Bei einer nebenläufigen Abarbeitung beider Befehle muss das nicht der Fall sein. Das Beschreiben einer int-Variablen in Java erfolgt üblicherweise atomar, das heißt, dass es durch das Time Sharing nicht unterbrochen werden kann. Aber es ist nicht vorhersagbar, welche der beiden Befehlsabarbeitungen als letzte die Variable i beschreibt. Anschaulich gewinnt diese das Wettrennen um das Beschreiben der Variablen i. Im Englischen spricht man von einer race condition.
Auf der anderen Seite gibt es zeitliche Abläufe, die problemlos nebenläufig durchgeführt werden dürfen. Dazu gehört beispielsweise die Abarbeitung der beiden folgenden Befehle:
Die beiden Beispiele zeigen deutlich, dass zwei Programmabarbeitungen, egal aus wie vielen Befehlen sie jeweils bestehen, nur dann nebenläufig erfolgen dürfen, wenn die Reihenfolge der beiden Abarbeitungen keine Rolle spielt. In dem Beispiel mit den Variablen i und k ist dies der Fall, denn es ist gleichgültig, welcher der beiden Befehle zuerst auf seine Variable schreibt. Wenn beide Befehle abgearbeitet sind, steht in i der Wert 7 und in k der Wert 8.
Beim ersten Beispiel ist das anders. Hier spielt die Reihenfolge eine Rolle, denn je nachdem, welcher der beiden Befehle zuerst durchgeführt wird, steht nach der Abarbeitung beider Befehle in der Variablen i entweder 7 oder 8. Man beachte, dass es unschädlich ist, wenn zwei Befehle, die nebenläufig abgearbeitet werden können, sequenziell ausgeführt werden. Das Umgekehrte gilt jedoch nicht: Zwei Befehle, bei denen die Reihenfolge ihrer Abarbeitung wichtig ist, müssen sequenziell durchgeführt werden.
Offensichtlich gibt es zeitliche Abläufe, die nicht nebenläufig erfolgen dürfen, und andere, bei denen Nebenläufigkeit nicht schadet. Liegt Nebenläufigkeit vor und ist sie in bestimmten Situationen schädlich, dann muss durch geeignete Maßnahmen, zum Beispiel durch das Setzen von Sperren, in diesen Situationen eine Sequenzialität der Abläufe erzwungen werden. Man spricht von einer Synchronisation der zeitlichen Abläufe. Im Abschnitt 1.3.3 (Threadsicherheit) wird dafür eine hilfreiche Java-Sprachkonstruktion vorgestellt. Eine allgemeinere Behandlung der Synchronisationsproblematik durch Semaphore und Monitore bleibt einer Vertiefungsveranstaltung vorbehalten.