Wikipedia · einfach zusammengefasst · Stand
Bernstein-Bedingung
Die Bernstein-Bedingung ist ein Begriff aus der Informatik, speziell aus dem Bereich Multiprocessing, und beschreibt, unter welchen Bedingungen zwei Programm …
Inhalt3 Abschnitte
Definition und Bedeutung
Die Bernstein-Bedingung ist ein Begriff aus der Informatik, besonders aus dem Bereich Multiprocessing. Sie beschreibt, wann zwei Programmabschnitte parallel ausgeführt werden können, ohne dass sich das Ergebnis gegenüber einer sequentiellen Ausführung ändert. Das ist wichtig, weil parallele Programme nur dann korrekt arbeiten, wenn gleichzeitig ausgeführte Abschnitte sich nicht gegenseitig durch Lese- oder Schreibzugriffe auf Variablen beeinflussen.
Variablenmengen
Gegeben sind zwei Programmabschnitte P_1 und P_2. Für jeden Abschnitt P_i gibt es zwei Mengen von Variablen:
- I_i ist die Menge der Variablen, auf die Abschnitt P_i lesend zugreift.
- O_i ist die Menge der Variablen, die Abschnitt P_i während der Ausführung verändert.
Lesender Zugriff bedeutet, dass ein Programmabschnitt den Wert einer Variablen verwendet. Verändern bedeutet, dass ein Programmabschnitt einen neuen Wert in eine Variable schreibt.
Die drei Bedingungen
Die Programmabschnitte P_1 und P_2 können genau dann parallel ausgeführt werden, ohne das Ergebnis dieser oder nachfolgender Berechnungen zu ändern, wenn alle drei folgenden Schnittmengen leer sind:
- I_1 ∩ O_2 = ∅: P_1 darf keine Variable lesen, die P_2 verändert.
- I_2 ∩ O_1 = ∅: P_2 darf keine Variable lesen, die P_1 verändert.
- O_1 ∩ O_2 = ∅: P_1 und P_2 dürfen keine gemeinsame Variable verändern.
Das Zeichen ∩ bedeutet Schnittmenge, also die gemeinsamen Elemente zweier Mengen. Das Zeichen ∅ bedeutet leere Menge, also dass es keine gemeinsamen Variablen gibt.