Ist id = 1 - id atomar?

74

Ab Seite 291 der OCP Java SE 6 Programmer Practice Exams, Frage 25:

public class Stone implements Runnable {
    static int id = 1;

    public void run() {
        id = 1 - id;
        if (id == 0) 
            pick(); 
        else 
            release();
    }

    private static synchronized void pick() {
        System.out.print("P ");
        System.out.print("Q ");
    }

    private synchronized void release() {
        System.out.print("R ");
        System.out.print("S ");
    }

    public static void main(String[] args) {
        Stone st = new Stone();
        new Thread(st).start();
        new Thread(st).start();
    }
}

Eine der Antworten lautet:

Die Ausgabe könnte sein P Q P Q

Ich habe diese Antwort als richtig markiert. Meine Argumentation:

  1. Wir starten zwei Threads.
  2. Zuerst tritt man ein run().
  3. Nach JLS 15.26.1 wird zunächst ausgewertet 1 - id. Ergebnis ist 0. Es wird auf dem Stapel des Threads gespeichert. Wir sind gerade dabei, das 0statisch zu speichern id, aber ...
  4. Boom, Scheduler wählt den zweiten Thread aus, der ausgeführt werden soll.
  5. Also tritt der zweite Thread ein run(). Statisch idist immer noch 1, also führt er die Methode aus pick(). P Qwird gedruckt.
  6. Der Scheduler wählt den ersten Thread aus, der ausgeführt werden soll. Es nimmt 0von seinem Stapel und speichert in statische id. Der erste Thread wird also auch ausgeführt pick()und gedruckt P Q.

In dem Buch steht jedoch geschrieben, dass diese Antwort falsch ist:

Dies ist falsch, da die Zeile id = 1 - idden Wert idzwischen 0und vertauscht 1. Es besteht keine Chance, dass dieselbe Methode zweimal ausgeführt wird.

Ich stimme nicht zu. Ich denke, es gibt eine Chance für das Szenario, das ich oben vorgestellt habe. Ein solcher Tausch ist nicht atomar. Liege ich falsch?

Adam Stelmaszczyk
quelle
Haben sie übrigens RSRS zugelassen?
Jon Skeet
1
@ JonSkeet Es gab keine solche Antwort. Sie ließ P Q R S, P R S Qund P R Q S, dem ich zustimmen.
Adam Stelmaszczyk
Ich denke, Sie haben den JLS-Abschnitt, auf den Sie sich beziehen, aus dem Zusammenhang gerissen. Dieser Abschnitt behandelt einfache Zuweisungen (wie in einem einzelnen Thread). Ich denke, Sie müssen JLS 17.4 überprüfen . Speichermodell .
Hfontanez
1
Sicher P R S Qund P R Q Sauch nicht möglich, da pickund releasesynchronisiert sind. Vermisse ich etwas (mein Java ist wahrscheinlich etwas rostig)?
Matt
2
Im ursprünglichen Codebeispiel (aus dem erwähnten Buch) ist die releaseMethode nicht statisch. Also P R S Qund P R Q S sind mögliche Lösungen in der Tat. Dies behebt jedoch nicht die Rennbedingung in der runMethode, daher ist das Buch in Bezug auf dieses Problem immer noch falsch.
isnot2bad

Antworten:

78

Liege ich falsch?

Nein, Sie haben absolut Recht - genau wie Ihre Beispielzeitleiste.

Zusätzlich dazu, dass es nicht atomar ist, kann nicht garantiert werden, dass das Schreiben idohnehin vom anderen Thread übernommen wird, da keine Synchronisation stattfindet und das Feld nicht flüchtig ist.

Es ist etwas beunruhigend, wenn Referenzmaterial wie dieses falsch ist :(

Jon Skeet
quelle
1
Vielen Dank, aber was meinst du damit , dass nicht garantiert ist, dass das Schreiben idtrotzdem vom anderen Thread übernommen wird ? Dass es irgendwie optimiert werden kann und es kein Schreiben iddurch den zweiten Thread geben kann? Ich verstehe diesen Teil nicht.
Adam Stelmaszczyk
9
@AdamStelmaszczyk: Nein, ich meine, Thread 1 könnte einen neuen Wert schreiben id, aber Thread 2 sieht ihn möglicherweise nicht sofort - er sieht möglicherweise den alten Wert.
Jon Skeet
25
Tief unter der Haube Ihrer CPU liegen Drachen. Das spezielle Problem, über das Jon spricht, heißt "Cache-Kohärenz". Wenn Sie nach dem Wert einer Variablen fragen, ist es zu langsam, jedes Mal in den Hauptspeicher zu wechseln (hunderte Male langsamer als gewünscht!). Um dies zu bewältigen, verfügen moderne Prozessoren alle über einen CPU-spezifischen oder kernspezifischen Speichercache, in den sie zuerst schauen. Dies bedeutet, dass ein Thread den "offiziellen" Wert von idim Speicher ändern kann und ein anderer Thread ihn nie sieht, weil er nie weiter als bis zu seinem eigenen Cache schaut.
Cort Ammon
6
Es gibt eine ganze Reihe von Tools für die Cache-Kohärenz, die von expliziten Cache-Flush-Befehlen über Atomics bis hin zur Synchronisation reichen. Zum Glück für diejenigen, die sich niemals mit diesen Drachen befassen wollen, macht die Synchronisation mit synchronizedoder Mutexen im Allgemeinen "das, was Sie denken, dass es tun sollte", solange Sie sie verwenden, um Ihre Daten mit den Standardmustern zu schützen (wie synchronizedim Beispiel) über). Es ist nur eine Schande, dass sie es falsch verstanden haben id.
Cort Ammon
9
Es ist erwähnenswert, dass der Autor sogar zugegeben hat , dass mit der Frage möglicherweise etwas nicht stimmt (da dies der Fall ist), obwohl sie sich wohl nie die Mühe gemacht haben, eine Liste von Errata zu erstellen.
Tim Stone
-3

Meiner Meinung nach ist die Antwort in den Übungsprüfungen richtig. In diesem Code führen Sie zwei Threads aus, die Zugriff auf dieselbe statische Variablen-ID haben. Statische Variablen werden auf dem Heap in Java gespeichert, nicht auf dem Stapel. Die Ausführungsreihenfolge von ausführbaren Dateien ist nicht vorhersehbar.

Um jedoch den Wert von id für jeden Thread zu ändern:

  1. erstellt eine lokale Kopie des in der Speicheradresse der ID gespeicherten Werts in der CPU-Registrierung.
  2. führt die Operation aus 1 - id. Genau genommen werden hier zwei Operationen ausgeführt (-id and +1);
  3. Verschiebt das Ergebnis zurück in den Speicherbereich von idauf dem Heap.

Dies bedeutet, dass, obwohl der ID-Wert von jedem der beiden Threads gleichzeitig geändert werden kann, nur der Anfangs- und der Endwert veränderbar sind. Zwischenwerte werden nicht voneinander geändert.

Darüber hinaus kann die Analyse des Codes zeigen, dass id zu jedem Zeitpunkt nur 0 oder 1 sein kann.

Beweis:

  • Startwert id = 1; Ein Thread ändert es in 0 ( id = 1 - id). Und der andere Thread bringt es zurück auf 1.

  • Startwert id = 0; Ein Thread ändert es in 1 ( id = 1 - id). Und der andere Thread bringt es zurück auf 0.

Daher ist der Wertezustand von id entweder 0 oder 1 diskret.

Ende des Beweises.

Für diesen Code gibt es zwei Möglichkeiten:

  • Möglichkeit 1. Thread eins greift zuerst auf die Variablen-ID zu. Dann wird der Wert von id ( id = 1 - idändert sich auf 0. Danach wird nur die Methode pick ()ausgeführt, die gedruckt wird P Q. Thread zwei wird die ID zu diesem Zeitpunkt auswerten id = 0; die Methode release()wird dann ausgeführt, indem R S P Q R Sgedruckt wird. Als Ergebnis wird gedruckt.

  • Möglichkeit 2. Thread zwei greift zuerst auf die Variablen-ID zu. Dann wird der Wert von id ( id = 1 - idändert sich auf 0. Danach wird nur die Methode pick ()ausgeführt, die gedruckt wird P Q. Thread eins wertet die ID zu diesem Zeitpunkt aus id = 0; die Methode release()wird dann ausgeführt, indem R S P Q R Sgedruckt wird. Als Ergebnis wird gedruckt.

Es gibt keine anderen Möglichkeiten. Es sollte jedoch beachtet werden, dass Varianten P Q R Swie P R Q Soder R P Q Susw. aufgrund pick()einer statischen Methode gedruckt werden können und daher zwischen den beiden Threads geteilt werden. Dies führt zur gleichzeitigen Ausführung dieser Methode, die dazu führen kann, dass die Briefe je nach Plattform in einer anderen Reihenfolge gedruckt werden.

In jedem Fall wird die Methode jedoch niemals pick()oder release ()zweimal ausgeführt, da sie sich gegenseitig ausschließen . Daher P Q P Qwird keine Ausgabe sein.

user2399800
quelle
2
In Schritt 2 wird das Ergebnis von 1 - d(Null) auf dem Stapel des Threads gespeichert. Jetzt kann der Scheduler vor Schritt 3 den laufenden Thread ändern. Der zweite Thread hat also auch Null von 1 - d. Bitte studieren Sie das Szenario, das ich in einer Frage vorgestellt habe, sorgfältig. Deshalb P Q P Qist es möglich. Wenn Sie von der bereits auf dieser Seite vorgestellten theoretischen Analyse immer noch nicht überzeugt sind, schauen Sie sich bitte auch den letzten Beitrag hier an , in dem empirisch gezeigt wird, dass dies möglich ist.
Adam Stelmaszczyk
Ihr "Beweis" lässt zwei Fälle aus - mit einem Startwert von 1 könnten beide Threads versuchen, ihn auf 0 zu ändern; und mit einem Startwert von 0 könnten beide Threads versuchen, ihn auf 1 zu ändern. Diese Antwort ist falsch.
Dawood ibn Kareem