Alte Klausuraufgabe Threads

[DaSt]

Hallo,

in der letzten Klausur war folgende Aufgabe zu Threads dran:

"Programmieren Sie eine Klasse mit dem Namen Counter, die sich als Thread starten lässt. Wird ein solcher Thread gestartet, gibt er in der Command-Line die Zahlen von 1 bis 500.000 aus. Wenn mehrere Threads dieser Klasse gleichzeitig laufen, darf keine Zahl mehrfach ausgegeben werden. Es darf aber auch keine Zahl ausgelassen werden. Sichern Sie diese Eigenschaft in Ihrem Quellcode ab. Bemerkung: Sie müssen die Threads nicht starten."

Die Lösung war folgende:

public class Counter extends Thread {

   private static final int MAX = 500000;
   private static int currentCount = 0;


  @Override
  public void run() {
     while ( incrementIfValid() );
  }

    private synchronized boolean incrementIfValid() {
    
       if ( currentCount < MAX ) {
            System.out.println(++currentCount);
            return true;
            }
       return false;
      }
}

Wieso ist denn hier sichergestellt, dass keine Zahl ausgelassen bzw. doppelt vorkommen kann?

Danke

 

[thecain]

synchronized

 

[DaSt]

ok, synchronized haben wir noch nicht besprochen. Im Netz habe ich folgende def. gefunden:
"Um Klassen threadsicher zu machen, kann man Methoden der Klassen als synchronized deklarieren. Die Qualifizierung mit synchronized bewirkt, dass zuerst eine begonnene synchronized Methode zu Ende ausgeführt wird, bevor eine neue synchronized Methode in einem anderen Thread begonnen werden kann. Das heißt, synchronized Methoden können nicht konkurrierend zueinander ablaufen, sondern werden immer sequentiell nacheinander ausgeführt. In dieser Ausgabe unserer Kolumne werden wir uns die Details von synchronized genauer ansehen."

Aber dann sind es doch eig. nur zwei Methoden die nacheinander aufgerufen werden oder?

 

[nvidia]

Ich stelle die Hypothese auf, die Lösung ist falsch. Der Grund, das synchronized, wie im Code dargestellt, wirkt auf eine Instanzmethode, d.h. auf ein lebendes Objekt und in dem Falle dient das Objekt selbst als Lock. D.h. werden 3 Counter erstellt new Counter().start, new Counter.start() usw. wird auf das jeweilige voneinander unterschiedliche Counter-Objekt synchronisiert. Der zu verändernde Wert ist jedoch eine statische Klassenvariable und deshalb müsste auf die Klasse synchronisiert werden, das geht aber wiederrum nur wenn der Methode incrementIfValid noch ein static vorangestellt wird. Das es so scheint als ob es funktioniert ist Zufall.

Das wird auch richtig deutlich wenn man n-Threads wirklich gleichzeitig startet und das Erhöhen des Zählers aus dem IO rauszieht. Wäre es ordentlich synchronisiert dürfte nichts passieren. Bei dem folgenden Testprogramm wird bei mir jedoch regelmäßig 3x die 3 ausgegeben (man muss sich natürlich alle Zahlen sortieren, in Excel z.B.) und die 1er fehlen ganz. Die CyclicBarrier ist dafür um zu warten bis alle Threads soweit sind.

Um die Lösung zu korrigieren müsste die Methodendefinition wie folgt aussehen private static synchronized boolean incrementIfValid()

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

/**
* Beispiel für fehlerhafte Synchronisation
*/

class Counter extends Thread {

    private static final int MAX = 500000;
    private static int currentCount = 0;

    @Override
    public void run() {
        try {
            Test.gate.await();
        } catch(InterruptedException e) {
            e.printStackTrace();
        } catch(BrokenBarrierException e) {
            e.printStackTrace();
        }

        while(incrementIfValid())
            ;
    }

    private synchronized boolean incrementIfValid() {

        if(currentCount < MAX) {
            ++currentCount;
            System.out.println(currentCount);
            return true;
        }
        return false;
    }
}

public class Test {

    public static final CyclicBarrier gate = new CyclicBarrier(3);

    public static void main(String... args) {
        new Counter().start();
        new Counter().start();
        new Counter().start();
    }
}

 

[DaSt]

Danke, werde unseren Tutor, der die Lösung angefertigt hat, darauf ansprechen

 

[kneitzel]

Also die Funktion incrementIfValid wird ja in einer While Schleife immer wieder aufgerufen. Wenn nun mehrere Threads laufen, dann soll das synchronized dazu führen, dass die Ausführung in allen Threads immer so lange wartet, bis die Ausführung in einem anderen Thread beendet ist.

Im übertragenen Sinne ist das also sozusagen das Schloss an der Klotür. Synchronized ist ein Schloss an der Klotür. Es kann immer nur ein Thread rein. Durch das synchronized wird sicher gestellt, dass beim Eintritt direkt die Tür geschlossen ist und andere müssen draussen warten.

Der Einwand von nvidia ist nun, dass diese Klotür ja Instanzgebunden ist, d.h. wenn ich drei Instanzen von der Klasse erstelle, dann habe ich auch drei Klotüren. Und das führt dann zu Problemen, denn nun können mehrere Threads gleichzeitig aufs Klo und genau das galt es ja zu verhindern.

Und das kann man ja einfach einmal testen. Zum Test einfach einmal eine kleine main Routine geschrieben:

public static void main(String[] args) {
    int numberOfCounter = 5;

    Counter[] counter = new Counter[numberOfCounter];

    // Create counter
    for (int i = 0; i<numberOfCounter; i++)
        counter[i] = new Counter();

    // Start counter
    for (int i=0; i<numberOfCounter; i++)
        counter[i].start();

    // wait for counter to finish
    for (int i=0; i<numberOfCounter; i++) {
        try {
            if (counter[i].isAlive()) counter[i].wait();
        } catch (InterruptedException ex) {
            // Nothing to do!
        }
    }
}

Und dann im Test erhalten:

499977
499885
499979
499980
499981
499982
499983
499984
499985
499986
499987
499988
499989
499990
499991
499992
499993
499994
499995
499996
499997
499998
499999
500000
499868
499866

==> Lösung ist schlicht falsch.

Die Funktion incrementIfValid static gemacht und schon sieht die Ausgabe besser aus [/code]

 

[thecain]

Ist natürlich korrekt, da war ich wohl ein bisschen schnell im lesen...

Zur Ergänzung, möglich wäre auch:

private boolean incrementIfValid() {
    synchronized (Counter.class) {
        if (currentCount < MAX) {
            System.out.println(++currentCount);
            return true;
        }
        return false;
    }
}

oder

private static final Object kloTuerSchloss = new Object();
private boolean incrementIfValid() {
    synchronized (kloTuerSchloss) {
        if (currentCount < MAX) {
            System.out.println(++currentCount);
            return true;
        }
        return false;
    }
}

Um nochmal auf die Klotüren zu kommen

 

[kneitzel]

Wobei mir die Lösung mit der statischen Variable kloTuerSchloss mit Abstand am Besten gefällt

 

[DaSt]

danke nochmals ;-)

 

[DaSt]

nachdem wir synchronized jetzt in der Vorlesung besprochen haben, habe noch eine Frage: Warum brauche ich extra eine boolean incrementIfValid() Funktion , die ja eig. nichts anderes macht als bis nach MAX zu erhöhen.

Also warum geht z.B. folgendes nicht:

private final static Object o = new Object

private static void zaehlen(){
  synchronized(o){
         for(int i = 0; i<MAX; i++){
          System.out.println("Nr. "+i);
         }
}

Danke

 

[Tobse]

Der Code, den du da gepostet hast, funktioniert so auch nicht. Damit Zählt der erste Thread, der startet, auf MAX und die anderen machen garnix. Wenn dann:

static int counter = 0;
public void run() {
    while(counter < MAX) {
        synchronized(o) {
            if (counter < MAX)
                System.out.println(i++);
        }
    }
}

P.S.: Was der Code hier macht nennt sich double-lock. Zu Threading bringe ich auch immer gerne dieses Bild:

Multithreading ist ein komplexes Thema und es gibt viel Literatur, die sich nur damit beschäftigt. Das in 1-2 Vorlesungen abzufrühstucken geht nicht.