Ich versuche den Peterson's N-Process Algorithmus zu verstehen und bin auf diese Frage gestoßen.
Frage: Angenommen, drei Prozesse haben Prozess-IDs 0, 1 and 2 . Diese Prozesse laufen gleichzeitig auf einem Uniprozessor und verwenden den N-Prozessalgorithmus von Peterson, um die Ausführung des kritischen Abschnitts zu steuern. Jeder Prozess führt den folgenden Pseudocode aus:
wobei lock() und unlock() Funktionen wie
Angenommen, der Status des Systems zu einem bestimmten Zeitpunkt wird durch <flags[0], flags[1], flags[2], turn[0], turn[1]> -Werte und die ID des gerade ausgeführten Prozesses definiert. Angenommen, der aktuelle Status des Systems ist <0,0,0,2,-1> mit dem Prozess 0 , der gerade ausgeführt wird . Zeigen Sie eine bestimmte Methode an, damit drei Prozesse ab diesem Status ausgeführt werden können. Wenn Sie die gleichzeitige Ausführung von drei Prozessen verfolgen, zeigen Sie den Status des Systems bei jedem Schritt an.
Meine Beobachtungen
Prozesse, die gleichzeitig auf einem Uni-Prozessor ausgeführt werden, können nicht gleichzeitig auf der CPU ausgeführt werden. Nur einer von ihnen kann gleichzeitig auf der CPU ausgeführt werden. Während ein Prozess auf der CPU ausgeführt wird, kann er einen beliebigen Teil seines Codes ausführen.
%Vor% - Für i = 0
- Für i = 1
- Für i = 2
Meine Frage ist, dass Wo kann ich anfangen, den Code zu verfolgen? Es wird flags[0]=0, flags[1]=0, flags[2]=0, turn[0]=2, turn[1]=-1 angegeben, aber wie wird es uns helfen, den Code nachzuverfolgen?
Wenn wir direkt vor der for-Schleife des Prozesses 0 beginnen, dann werden alle
Turn-Werte würden auf andere Werte als die angegebenen gesetzt werden
zu uns.
Wenn wir davon ausgehen, dass die Frage ausgeführt wird, bedeutet dies, dass 0 in ihrem ist
kritischer Abschnitt wird dann die for - Schleife des nächsten Prozesses gesetzt
Wende Werte auf etwas anderes.
Warum erhalten sie uns Statuswerte und wie sie uns dabei helfen können, den Code zu verfolgen?
Es wäre großartig, wenn ich einen Hinweis bekommen würde, der mir hilft, den Code nachzuverfolgen.
Danke und Entschuldigung für die lange Frage.
Da Sie nicht nach der Antwort auf die Frage gefragt haben und Sie eine vernünftige und vernünftige Frage gestellt haben, bin ich zuversichtlich, dass ich Sie in die richtige Richtung lenken kann, ohne Ihre Hausaufgaben (oder was auch immer) für Sie zu machen.
Zuerst ist der Schlüssel der Frage hier:
Angenommen, der Status des Systems zu einem bestimmten Zeitpunkt wird durch
<flags[0], flags[1], flags[2], turn[0], turn[1]>-Werte und die ID des gerade ausgeführten Prozesses definiert. Angenommen, der aktuelle Status des Systems ist<0,0,0,2,-1>mit dem Prozess 0 , der gerade ausgeführt wird .
Daraus können wir annehmen, dass das System normal gestartet wurde und während der Ausführung in diesem Zustand angekommen ist. Also müssen wir einen Punkt finden, wo das System in diesem Zustand sein kann und der Prozess 0 ausgeführt wird. Der nächste Teil gibt uns etwas Spielraum:
Zeigen Sie einen bestimmten Weg für drei Prozesse an, die ab diesem Status ausgeführt werden.
Es gibt also mehrere Möglichkeiten, um diese Variablenwerte mit dem Prozess 0 zu erreichen, aber es ist in Ordnung, einen zu finden und von dort aus das System zu vervollständigen.
Außerdem können wir sehen, dass alle Prozesse einmal ausgeführt werden und sich beenden - es gibt eine Schleife, aber wir können auch sehen, dass sie die Werte von flags bei jeder Runde erhöht, so dass wir nur vermuten können Klicken Sie einmal auf dieses Szenario für die Variablenwerte. Aber wir sollten es durcharbeiten, um es herauszufinden.
Die Prozesse laufen gleichzeitig, aber auf einem einzelnen Prozessor. In der Realität wird also nur einer ausgeführt, aber eine höhere Macht (zum Beispiel ein Betriebssystem) wechselt zwischen ihnen auf eine Weise, die wir nicht bestimmen können. Du sagst:
Während ein Prozess auf der CPU ausgeführt wird, kann er einen Teil seines Codes ausführen.
Ich denke, Sie haben das nur schlecht formuliert. Ich vermute, Sie verstehen, dass jeder Prozess von Anfang an beginnt und bis zum Ende läuft. "Während ein Prozess auf der CPU ausgeführt wird, fängt er dort an, wo er aufgehört hat und laufen kann eine beliebige Anzahl von Anweisungen, bis das Recht, auf der CPU zu laufen, verloren geht (die Anzahl der Anweisungen hängt davon ab, was das System steuert) "ist eine genauere Aussage.
Der einfachste Weg ist also, am Anfang zu beginnen und den Griff zu drehen. Die Frage sagt das nicht, aber Flags und Turn werden normalerweise auf -1 initialisiert, also haben wir am Anfang:
Da die Dinge gleichzeitig laufen, nehmen wir einfach an, dass jeder Prozess effektiv jede Zeile zur gleichen Zeit ausführt. Es macht keinen Unterschied, wie Sie hoffentlich später selbst sehen können.
%Vor%OK, count = 0 für alle Prozesse und sie gehen alle zur nächsten Zeile:
%Vor%So jetzt:
%Vor%So weit, so gut - nächste Zeile:
%Vor%OK, das ist problematisch - jeder Prozess versucht dieselbe Variable zu setzen. Einer von ihnen wird gewinnen, aber wir wissen nicht, welcher:
%Vor% Außer wir tun, wie es in der Frage ist. Wir können turn[0] = 2 machen. Wir befinden uns also in einem geeigneten Zustand mit den Variablen, wir können annehmen, dass Prozess 0 die Kontrolle hat und wir wissen, dass es in dieser Zeile steht:
Um Sie für Prozess 0 zu starten, zählen Sie count = 0 und i = 0 also
%Vor% Sie können sehen, dass die or -Klausel falsch ist, also wird Prozess 0 die Schleife erneut durchlaufen. Also wird Prozess 1. Die for all k -Klausel ist für niemanden wahr. Daher wird Prozess 2 wegen des Wertes von turn[0] warten - Sie können auch sehen, dass sich dies nie ändern wird, also ist Prozess 2 jetzt gesperrt und wartet darauf, dass die for all k -Klausel wahr wird - tatsächlich ist das der Schlüssel dazu System funktioniert. Wenn Sie der Logik folgen, um die Frage zu beantworten, werden Sie sehen, wie sich die Prozesse gegenseitig blockieren, so dass jeweils nur einer den kritischen Abschnitt ausführt. Mach weiter, was ich oben getan habe, da du nur einen Weg finden musst, um Linien gleichzeitig auszuführen, und wenn es einen möglichen Konflikt gibt, wähle einfach einen Wert und gehe von dort aus weiter.
Sie können auch sehen, dass, wenn Prozess 2 alle Zeilen auf einmal ausgeführt hat, bevor die anderen eine Chance hatten, und dann 1 verarbeiten und dann 0 verarbeiten, würden Sie am selben Ort landen. Wenn Sie das gesamte System auf verschiedene Arten bearbeiten, werden Sie das Muster ähnlich finden (beachten Sie, dass es keine Garantie für die Reihenfolge gibt, in der die Prozesse ihre kritischen Abschnitte ausführen, es kommt darauf an, wer in den strittigen Zeilen gewinnt).
Also zurück zur ursprünglichen Frage, es gibt nur wenige Stellen, an denen Prozess 0 die Kontrolle über diesen Systemzustand haben kann. Entweder in der wait -Zeile oder in der for -Zeile, wenn die Anzahl auf 1 erhöht wird (nachdem es umläuft) oder in der Zeile, in der flag[0] gesetzt wird. Danach ist der Systemzustand nicht derselbe. Es ist am besten, den frühesten Prozess anzunehmen, da Prozess 1 (noch) nicht blockiert ist und auch den Zustand ändern könnte.
Eine letzte Falte, der Vollständigkeit halber. Es gibt einen anderen Ort, an dem dieser Prozess kontrolliert werden kann und der Systemzustand kann so sein. Und es ist kurz vor der turn[count] = i; -Zeile.In diesem Szenario hat der Prozess 2 gerade die Variable gesetzt und der Prozess 0 wird ihn überschreiben. Sie können von hier aus fortfahren, aber es werden die Prozesse 1 und 2 sein, die die Schleife durchlaufen. Ich schließe das voraus, indem ich einen Kommentar dazu ablehne. Ich behaupte nicht, dass Sie dies als Ausgangspunkt verwenden, obwohl es absolut gültig ist. Die Frage erwartet fast sicher, dass Sie von den Prozessen 0 und 1 ausgehen, wobei 2 blockiert sind, um zu sehen, was von dort passiert.
Viel Glück damit.
Tags und Links algorithm c concurrency process