In Vorlesung 10 über Mutex gibt es mehrere Übungen. Lösen Sie die Problemen/Beantworten Sie die Fragen, die in Vorlesung 10 als Übungen dargestellt werden.
Wir können von dem Wissenszustand eines Prozesses (sei es Prozess A) sprechen. Dies sindt die Informationen über den Zustand anderer Prozesse, die zum Zustand des Prozesses A gehören.
Wir definieren eine binäre Relation: happens-before. Ereignis a happens-before Ereignis b wird definiert:
a und b gehören zum gleichen Prozess und der Prozess macht a aus bevor er b macht; oder
a ist das Schicken einer Nachricht von einem Prozess und b ist der Empfang der gleichen Nachricht von einem anderen Prozess; oder
Es existiert ein Ereignis c ,und a happens-before c und c happens-before b; und
a happens-before b nur falls es folgt über eine endliche Anwendung der drei oben genannten Kriterien.
Entwickeln Sie drei Prozessen (in Pseudocode beschrieben), in denen es zwei Ereignisse a und b gibt, die entweder ein Schicken oder ein Empfang einer Nachricht sind, und die nicht zu einander die Relation happens-before haben.
Sei es, dass die drei Prozesse interne Uhren haben und obwohl diese Uhren die gleiche Frequenz haben sollen). Dies bedeutet nicht, dass die miteinander synchronisiert laufen.
Die Nachrichten werden nun mit einem Timestamp geschickt. D.h., wenn sie geschickt werden, beinhaltet eine Nachricht auch die Sendeuhrzeit laut der lokalen Uhr.
Wenn eine Nachricht ankommt, wird der Empfangsprozess seine Uhrzeit mit der Uhrzeit des Timestamps vergleichen, und seine Uhrzeit bis max(seine Uhrzeit, Timestamp + 1) setzen und die Uhrzeiten aller vorherigen Ereignisse bei ihm passend korrigieren (d.h., wenn er seine Uhr vier Ticks nach vorne setzen muss, dann setzt er die Uhrzeiten von allenvon ihm bekannten Ereignissen vier Ticks nach vorne).
Falls es wahr ist, beweisen Sie, dass wenn a happens-before b, dass in jedem Prozess die (korrigierte) Uhrzeit von a ist früher als die (korrigierte) Uhrzeit von b. (Bemerken Sie aber, dass die Prozessen müssen nicht alle die gleiche Uhrzeit für a und für b haben!)
Falls der oben genannte Satz nicht wahr ist, geben Sie ein Gegenbeispiel (d.h., Prozessen und einen Nachrichtablauf, in dem es ein a und ein b gibt mit a happens-before und ein Prozess gibt, in dem die lokale Uhrzeit von b früher ist als die lokale Uhrzeit von a).