Threadsicheres wait() [lock erst mit wait() abgeben]

[theseus]

Hallo

Ich hab folgendes Problem. Ich weiß während meines Programmablaufs erst kurz vor einem wait() ob und auf welches (wait-)Objekt wirklich gewartet werden muss.
Das wait-Objekt auf das gewartet werden soll wird während des Programmablaufs abh. von den weiteren existieren wait-Objekten erstellt.
Ob gewartet werden soll ist abhängig von allen anderen wait-Objekten für sämtliche Threads.

Die Bedingung ob gewartet werden muss und das erstellen eines neuen Threads dürfen also nicht gleichzeitig ausgeführt werden. Gleichzeitig muss aber auch das warten auf das Objekt direkt im Anschluss geschehen, sodass sich die Bedingungen nicht direkt vor dem warten ändern kann.

Pseudoprogramm

synchronized(lock);
{
  WaitObject wo = createNewWaitObject_AndPutItIntoList(listOfAllOtherWaitObjects); 
}
if (true == DoIHaveToWait(listOfAllOtherWaitObjects))
{
  wo.wait();
}

Die Methode DoIHaveToWait(...) ist ebenfalls durch ein synchronized(lock) geschützt.

Der Übersicht halber habe ich den code stark gekürzt, so ist das natürlich nicht lauffähig
Das Problem ist das sich der Zustand der Liste vor Beginn wo.wait() und nach der Methode DoIHaveToWait noch ändern kann. Es muss aber gewährleistet sein, das dies nur passieren kann wenn der Thread wartet.
(Wichtig ist vielleicht noch das wartende Threads nur innerhalb der Methode createNewWaitObject_AndPutItIntoList(...) benachrichtigt werden kann)

Gibt es da vielleicht eine Möglichkeit, dass Thread A Threadsicher vor einem wait() alle locks auf irgendwelche Objekte ab gibt, sodass ein anderer Thread B erst dann das lock erhalten kann sobald A sicher wartet? In diesem Fall könnte ich den synchronized Block auch um die den wo.wait() Aufruf ziehen

Viele Grüße

 

[Marco13]

Um trotz der fortgeschrittenen Stunde meiner elaborierten Eloquenz duch ein weiteres chef-d'œuvre Ausdruck zu verleihen: Häh? :autsch:

Also, ich hab's nicht verstanden Aber ... das java.util.concurrent-Package kennst du? Sowas wie CopyOnWriteArrayList oder BlockingQueues, oder auch Locks und Conditions mit feingranularerer Kontrolle, können für solche Sachen hilfreich sein.

 

[theseus]

Ich hab gestern schon befürchtet das ich das zu kompliziert ausgedrückt habe

Danke für deine Antwort. Ich habe aber leider bei den "normalen" Mechanismen zur Threadsicherheit nicht ganz das gefunden was ich suche. Ich lasse mich aber gerne eines besseren belehren

Also noch einmal eine kurze Problembeschreibung:

Ich will das ein Thread A ein lock auf ein Objekt X hält bis A sicher mit Objekt Y wartet.
Zurzeit sieht es so aus:

Thread A bekommt das lock auf Objekt X
Thread A macht irgendwas
Thread A gibt das lock ab
Thread A ruf Y.wait() auf und wartet

Zwischen Zeile 3 und 4 besitzt Thread A das lock auf Objekt X nicht mehr, wartet aber auch nicht. In dieser Zeit könnte ein Thread B das lock auf Objekt X anfordern und anfangen zu arbeiten.
Ich will also diesen Zustand verhindern: Thread A hat lock auf X abgegeben, wartet aber noch nicht und Thread B hat lock auf X angefordert und macht irgendwas.
Leider dürfen das lock X und das wait-Objekt Y nicht identisch sein.

Mir ist bisher nur eine Möglichkeit eingefallen wie sich das lösen lässt, der Ansatz dazu gefällt mir aber nicht:

Thread A bekommt das lock auf Objekt X
Thread A wartet bis alle Threads in einer Liste xyz warten
Thread A trägt sich in Liste xyz ein
Thread A macht irgendwas
Thread A gibt das lock ab
Thread A ruf Y.wait() auf und wartet
Thread A löscht sich aus der Liste xyz

In diesem Fall kann ich mir sicher sein das der interessante Teil des Programms immer nur ausgeführt wird wenn alle anderen Threads warten oder in einem anderen Teil des Programms arbeiten.

Ich hoffe meine Frage ist so verständlicher, ansonsten kann ich auch gerne versuchen das noch einmal um zu formulieren ;-)

Viele Grüße

 

[FArt]

Kaum Verständlicher.

Ich komme noch mal auf Marco zurück... Häh?

Sagt dir der Begriff "Barriere" aus dem Bereich des Concurrency etwas? Ist es das was du möchtest?

Wenn nein, dann versuche mal einen typsichen Anwendungsfall zu beschreiben, ohne dabei auf deine "gedachte Lösung" zurückzugreifen. Und als Tipp: ein Anwendungsfall kennt keine Locks auf Objekt xyz...

 

[theseus]

Das Problem mit dem Concurrent Package ist das jedes lock das ein Thread behält meines wissens nach aktiv wieder zurückgeben werden muss. (Mit Ausnahme des Objekts dessen wait Methode aufgerufen wird).
Ein Thread A der wartet kann aber kein lock abgeben, ein Thread A der das lock zurückgibt bevor er wartet geht das Risiko ein das ein anderer Thread B das lock bekommt bevor A wartet.

Mein Anwendungsfall liegt in der Simulation mehrerer parallel zu einander arbeitender Computer (je ein Thread) die mehr oder weniger synchron zueinander arbeiten müssen. Die Fragestellung resultiert aus einem Teilproblem des Synchronizers, der für die Simulation benutzt wird.
Ich bin speziell an der Lösung des oben genannten Problems interessiert, da einen funktionierenden Synchronizer zu entwickeln nicht das Problem darstellt. Ich würde aber gerne verschiedene meiner "gedachten Lösungen" und ihre fertigen Implementierungen auf ihre Performance testen
Wenn es zu der Frage keine gute Lösung gibt ist das auch in Ordnung, aber leider gibt es in diesem speziellen Fall für mich keine Alternative in der Implementierung

Ich versuche aber gerne nochmal die Fragestellung (abstrakt) neu zu formulieren. Ich habe einen Block A der nur von einem Thread gleichzeitig betreten werden soll. Am Ende dieses Blocks soll der Thread warten. Das Objekt dessen wait Methode der Thread aufruft wird aber erst im Block A erzeugt.

Ich will also so etwas wie das hier:

synchronized (lock){
  // do something
  WaitObject wo = new WaitObject();
  wo.wait();
}

In diesem Fall wäre sichergestellt das der ganze Block von Zeile 1 bis incl. wait Aufruf nur von einem Thread betreten wird. Problem ist jedoch das der Thread das lock auf lock nicht wieder abgibt sobald dieser mit "wo" wartet. Lasse ich den synchronized Block jedoch schon vor dem wait Aufruf enden, kann es sein das ein anderer Thread diesen Block betritt bevor der erste Thread wo.wait() aufgerufen hat (s.O)

Ich weiß bisher nur das es mit locks, conditions, synchronized Blöcken und Barrieren nicht geht, oder zumindest wüsste ich nicht wie.

Viele Grüße

 

[FArt]

Das wird so nicht funktionieren, du wirst zwangsläufig Deadlocks erhalten.

Mein Anwendungsfall liegt in der Simulation mehrerer parallel zu einander arbeitender Computer (je ein Thread) die mehr oder weniger synchron zueinander arbeiten müssen.

Das würde man mit einer oder mehreren Barriere(n) erreichen.

Ich versuche aber gerne nochmal die Fragestellung (abstrakt) neu zu formulieren. Ich habe einen Block A der nur von einem Thread gleichzeitig betreten werden soll. Am Ende dieses Blocks soll der Thread warten. Das Objekt dessen wait Methode der Thread aufruft wird aber erst im Block A erzeugt.

Das ist nicht abstrakt. Du beschreibst eine von dir erdachte mögliche Lösung des eigentlichen Problems. Das ist nicht die eigentliche Anforderung, die mir helfen könnte das Problem zu durchdringen und somit mögliche Lösungen anzubieten

Ist dein Problem, dass nach verlassen der kritischen Sektion irgendeiner der wartenden Threads drankommt? Du möchtest hier lieber einen FIFO Mechanismus? Das wäre dann etwas wie "blocking queue".

 

[theseus]

Wie gesagt ich habe mehrere Versionen funktionierender Synchronizer. Mir ist gerade dieser Lösungsweg (sofern möglich) wichtig. Mir geht es nicht um andere Lösungswege, auch wenn mir klar ist das sich das auf x- Weisen lösen lässt

Ich will kein FIFO implementieren. Ich möchte innerhalb eines bestimmten Threadkritischen Programmteils ein Objekt erzeugen auf das gewartet wird. Ebenfalls will ich jedoch in diesem Threadkritischen Programmteil wartende Threads benachrichtigen, die dann weiter laufen können.

Es wäre also schlecht wenn ich mit einem synchronized Block, lock, condition oder Barrieren arbeite, weil so der Thread erst sein exklusives lock ab gibt und dann wartet. Im ungünstigsten Fall ist ein anderer Thread so schnell das er den Threadkritischen Block betritt, den noch nicht wartenden Thread benachrichtigt und dann ebenfalls wartet. Schwupps habe ich zwei Threads die warten und vielleicht keinen weiteren mehr der sie aufweckt.

Wenn du willst kannst du das als Frage nach einem "Design Pattern" verstehen die ist auch Anwendungsfallunabhängig

Also nochmal in Codeform und ausführlicher, sinngemäß so wie ich es implementieren will:

WaitObject wo = null;
// Diese Liste ist für alle Threads gleich und speichert alle Objekte auf denen Threads warten 
ArrayList<WaitObjekt> woList = getwoList();
synchronized (lock){
  // irgendwas weiteres Threadsicheres ausführen
  //...
  wo = new WaitObjekt();
  // anderen Threads das eventuell neue WaitObjekt bekanntgeben.
  woList.put(wo);
  // aus der Liste ein Objekt holen damit einer der wartenden Threads benachrichtigt werden kann
  WaitObject notifyMe = getWaitCurrentObject(woList);
  notifyMe.notifyAll();
}
wo.wait();

Bei dieser Implementierung ist das Problem das in Zeile 10 ein Thread A das lock abgibt ein Thread B also den kritischen Block betreten kann. Erreicht nun Thread B Zeile 9 bevor Thread A Zeile 11 erreicht hat und wartet, geht das notify ins leere und es kann zu einem Deadlock kommen.

Meine Bisherige Lösung ist es jeden Thread der sich ein WaitObjekt erzeugt ebenfalls in eine Liste aus Threads eintragen zu lassen. Im kritischen Block wird erst einmal überprüft ob alle Threads aus dieser Liste warten, dann geht es erst weiter.:

WaitObject wo = null;
// Diese Liste ist für alle Threads gleich und speichert alle Objekte auf denen Threads warten
ArrayList<WaitObjekt> woList = getwoList();
ConcurrentLinkedQueue<Thread> threadLock = new ConcurrentLinkedQueue<Thread>();
synchronized (lock){
  // irgendwas weiteres Threadsicheres ausführen
 
  while (threadLock.size() > 0) {
    for (Thread temp : threadLock) {
      if (State.WAITING == temp.getState()) {
      threadLock.remove(temp);
      }
    }
  }

  threadLock.put(Thread.currentThread())
  // ...
  wo = new WaitObjekt();
  // anderen Threads das eventuell neue WaitObjekt bekanntgeben.
  woList.put(wo);
  // aus der Liste ein Objekt holen damit einer der wartenden Threads benachrichtigt werden kann
  WaitObject notifyMe = getWaitCurrentObject(woList);
  notifyMe.notifyAll();
}
wo.wait();
threadLock.remove(Thread.currentThread());

durch die while Schleife wird sichergestellt das alle anderen Threads sicher warten sobald ein weiterer Thread versucht sie zu wecken. Auch wenn das so funktioniert ist das durch diese while Schleife nicht das gelbe vom Ei. daher meine Frage nach Alternativen ein Threadsicheres wait() zu implementieren

Viele Grüße

 

[FArt]

Zum ersten Beispiel:
Aus der Doku zu Object#wait:

The current thread must own this object's monitor.

Dein wo.wait() ist nicht in einer kritischen Sektion und hält somit nicht den Monitor. Wie kann das funktionieren?

Zum zweiten Beispiel:
Aus der Doku zu Thread#getState:

Returns the state of this thread. This method is designed for use in monitoring of the system state, not for synchronization control.

Diese Methode sichert zu, dass sie nicht so verwendet werden kann, wie du es gerade machst ;-)
Außerdem gilt noch der Hinweis aus dem ersten Beispiel, das scheint hier wieder so zu sein.

Aus deiner Beschreibung:

Im kritischen Block wird erst einmal überprüft ob alle Threads aus dieser Liste warten

Das hört sich irgendwie nach Barriere an... in dem Fall aber über eine Methode (Thread#getState) realisiert, die nicht dafür geeignet ist. Ausserdem ist das im Endeffekt "busy waiting" und somit trügt dich dein Gefühl nicht: uncool.

Mir geht es nicht um andere Lösungswege, auch wenn mir klar ist das sich das auf x- Weisen lösen lässt

Ok. Aber die wird m.E. nie funktionieren.

 

[theseus]

Zum ersten Beispiel:
Aus der Doku zu Object#wait:

Dein wo.wait() ist nicht in einer kritischen Sektion und hält somit nicht den Monitor. Wie kann das funktionieren?

Da es mir um ein prinzipielles Problem geht, will ich nicht per se lauffähige Programme posten. Einen synchronized Block habe ich der Übersicht halber weggelassen.

Das hört sich irgendwie nach Barriere an... in dem Fall aber über eine Methode (Thread#getState) realisiert, die nicht dafür geeignet ist. Ausserdem ist das im Endeffekt "busy waiting" und somit trügt dich dein Gefühl nicht: uncool.

Inwiefern ist das eine Barriere? Ich will das lock direkt im Statusübergang zu wait abgeben. Es darf also keinen Zwischenraum zwischen 1. Thread A hat das lock und 2. Thread A wartet geben. Wenn ich eine Barriere benutze der ich sage "Ich bin soweit ich werde jetzt sofort im nächsten Schritt warten" schützt mich nicht davor das ein anderer Therad das lock bekommt, wenn Thread A noch nicht wartet.
Wenn du mir aber zeigen kannst, wie du das obige Beispiel mith. einer Barriere implementieren würdest, wäre ich dir sehr dankbar ;-)

Viele Grüße

 

[FArt]

Wenn du mir aber zeigen kannst, wie du das obige Beispiel mith. einer Barriere implementieren würdest, wäre ich dir sehr dankbar

Kann ich leider nicht, weil ich immer noch nicht weiß, was du für eine Problematik eigentlich lösen willst.

Beispiel - Wikipedia erklärt Producer - Consumer - Problem :

The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer. The producer's job is to generate a piece of data, put it into the buffer and start again. At the same time the consumer is consuming the data (i.e. removing it from the buffer) one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

The solution for the producer is to go to sleep if the buffer is full. The next time the consumer removes an item from the buffer, it wakes up the producer who starts to fill the buffer again. In the same way, the consumer goes to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer.

The solution can be reached by means of inter-process communication, typically using semaphores. An inadequate solution could result in a deadlock where both processes are waiting to be awakened.

1. Teil: Problembeschreibung
2. Teil: Lösungsansatz (allgemein)
3. Teil: Lösungsansatz (etwas konkreter)

Wie du siehst, kommen in der Problembeschreibung keine Objekte, Monitore, sleeps, waits, notifys, ... vor. Ohne diese Beschreibung kann ich dir nicht helfen, weil ich nicht weiß was du erreichen möchtest. Deine angedachten Lösungsversuche führen m.E. zu Deadlockverhalten, im besten Fall zu unnötig blockierten Threads, auf jeden Fall nicht zum Ziel.

Zur Verdeutlichung noch mal ein Ausschnitt aus dem Dokument, welches in meiner Signatur verlinkt ist: Wie man Fragen richtig stellt: eine Anleitung wie man Fragen erfolgreich in Usenet, Mailing Listen und Webforen stellt.

 

[theseus]

Zur Verdeutlichung noch mal ein Ausschnitt aus dem Dokument, welches in meiner Signatur verlinkt ist: Wie man Fragen richtig stellt: eine Anleitung wie man Fragen erfolgreich in Usenet, Mailing Listen und Webforen stellt.

Gut extra für dich

Ich möchte ein Java Design-Pattern um sicher zu stellen das ein ein wartender Thread alle locks die er hält, während er wartet (oder reicht genau ab dem Zeitpunkt ab dem er wartet), wieder freigibt.

Mir ist klar das du dir gerne mehr darunter vorstellen willst und es einfacher wäre das Problem zu umgehen. Ich bin aber an einer Lösung genau für dieses Problem interessiert. Das es eine Möglichkeit gibt das zu tun habe ich unten gezeigt, dass diese Möglichkeit ungeschickt ist weiß ich selber. Die Frage bleibt ob es eine bessere Lösung für ein solches Design-Pattern gibt

Viele Grüße

 

[FArt]

Ich möchte ein Java Design-Pattern um sicher zu stellen das ein ein wartender Thread alle locks die er hält, während er wartet (oder reicht genau ab dem Zeitpunkt ab dem er wartet), wieder freigibt.

Das ist immer noch keine Problembeschreibung sondern ein erster Lösungsansatz, der wie ich schon sagte m.E. so nicht funktioniert. Was fehlt bei deinem Lösungsversuch z.B.: worauf wartet der Thread (vermutich auf das Betreten einer weiteren kritischen Sektion?). Was bedeutet freigeben (komplett oder im Sinne von wait() auf Fortfürhrung warten)? Soll das ein wait() werden, der automatisch mit allen von dem Thread bisher betretenen kritischen Sektionen funktioniert? Wie willst du dann sichertstellen (angenommen es sind alle möglichen Kombinationen von Threads und kritischen Sektionen möglich), dass Threads nicht verhungern?

Ich denke immer noch, dass das eignetliche Problem anders gelöst werden könnte, z.B. mit AbstractQueuedSynchronizer (Java 2 Platform SE 5.0)

Ich gebe jetzt auf, da ich mangels ausreichender Informationen (Beschreibung, vollständiger Pseudocode) hierzu in vertretbarer Zeit keine sinnvolle Antworten schreiben kann.

 

[Marco13]

Ich bin auch kurz vor'm Aufgeben. Rumspekulieren, ob du denn vielleicht ein CountDownLatch (Java Platform SE 6) suchst, bringt vermutlich nicht so viel.

Vielleicht (!) würde ein KSKB helfen, aber... das ist bei solchen Threading-Sachen vielleicht schwierig.

 

[theseus]

Ja das mit den Thread Beispielen ist in der Tat recht verwirrend, daher habe ich das nicht versucht.
Mir ist inzwischen eine sauberere Lösung eingefallen wie ich in einem Threadsicheren Block ein Objekt erzeugen kann, Threads die auf ein solches Objekt warten, wecken kann und auch im direkten Anschluss darauf warten kann. Das alles so, dass ein Thread nur dann geweckt wird wenn er wirklich schläft.
Danke für den Tipp mit der CountDownLatch, die schaue ich mir mal genauer an.

Noch einmal zu den Bedingungen:
Ein Block soll nur von einem Thread betreten werden
Innerhalb dieses Blocks wird ein WaitObject erzeugt
Innerhalb dieses Blocks können Threads die auf eine beliebige Instanz des WaitObject warten wieder geweckt
Im direkten Anschluss soll der Thread warten und das so das er auch geweckt wird wenn ein anderer Thread den Block betritt bevor er seinen Zustand auf "WAITING" gesetzt hat.

Ich habe die Bedingungen ein wenig aufgeweicht, anstatt verhindern zu wollen das ein anderer Thread den Block überhaupt betritt will ich mit dem folgenden Code nur noch verhindern das die notify Methode des WaitObjekts zu früh aufgerufen wird.

Lock lock = new ReentrantLock();
WaitObject waitObject = null;

// ab hier beginnt der Block der Threadsicher sein soll
lock.lock();

// wecke gegebenfalls alte Threads dies kann nur aufgerufen werden wenn auch alle 
// Threads schlafen, da dieser notify-synchronized-Block nicht gleichzeitig mit dem 
// wait-synchronized-Block für dasselbe Objekt aufgerufen werden kann. wenn also 
// oldWaitObject des einen Threads das gleiche wie wo des anderen Threads ist.
synchronized(oldWaitObject){
 oldWaitObject.notifyAll();
}
//erstelle das neue waitObject
wo = getNewWaitObject();

synchronized (wo){
 lock.unlock();
 wo.wait();
}

Ich gebe zu das ist nicht ganz das was ich wollte, es kommt aber sehr nah an diese Sache heran. Im Sinne meiner Topicüberschrift würde das obige Beispiel sogar reichen. Ich kann hier keinen Thread wecken der noch nicht wartet. Auf der anderen Seite kann ich alle locks innerhalb des wait-synchronized Blocks loswerden, die ich nicht mehr benötige. Der kritische Teil in dem man noch nicht genau weiß ob der Thread wartet, oder eben noch nicht, kann auf die Stellen vor Zeile 11 beschränkt werden.

 

[Marco13]

Ein Problem ist, neben der Tatsache, dass das wohl ziemlich kompliziert ist (nicht notwendigerweise inhärent kompliziert, aber kompliziert beschrieben), auch die Tatsache, dass du "vereinfachten" Code postest - mal weiß man nicht, was "lock" ist und wo das definiert wird, mal weißt man nicht, was "oldWaitObject" ist, was die Methode "getWaitCurrentObject" macht, und ob die Klasse "WaitObject" eine Funktionalität hat, die über die von "Object" hinausgeht, und die spannende Frage, wo eine Methode anfängt und aufhört wird auch nicht beantwortet.

Dass jetzt die Bedinungen verändert wurden könnte die provokative Schlussfolgerung zulassen: Entweder, die Bedingungen waren vorher überflüssigerweise zu stark, oder sind jetzt zu schwach

Das erste Codestück aus http://www.java-forum.org/allgemein...s-wait-lock-erst-wait-abgeben.html#post579936 war ja schon nah dran. In bezug auf die Zeilen, die du dort nennst, ist ein bißchen Phantasie nötig, aber man kann erahnen, welche Zeilen gemeint sind. Aber wenn solche Fragen offen bleiben, wie z.B. wie "notifyMe.notifyAll()" aufgerufen werden können soll, wenn darauf gar nicht synchronized ist, macht das Antworten schwierig...

 

[theseus]

In der Tat ich fand es, und finde es immer noch nicht, einfach das Problem zu beschreiben. Wahrscheinlich war es auch ein wenig fahrlässig von mir vermeintlich unwichtige Teile des Codes bzw. der Fragestellung zu kürzen.
Meine Frage ist in Bezug auf meinen ersten Beitrag immer noch nicht befriedigend gelöst, aber immerhin bezüglich des Betreffs des gesamten Topics. Das kommt der Antwort auf meine Frage schon ziemlich nahe erfüllt sie aber wie gesagt nicht ganz.
Die Bedingungen habe ich angepasst um eine weitere Idee dessen vor zu stellen, was ich versuche zu erreichen. Mit der Lösung in meinem letzten Post kann ich erreichen das ein Thread nicht geweckt wird der noch nicht im Status WAITING ist. Ich habe damit aber immernoch nicht erreicht das ein Thread den gesamten Threadkritischen Block nicht betreten kann, wenn irgendein weiterer Thread hinter diesem Block aber nicht im Zustand WAITING ist, aber es im nächsten Takt sein könnte.

Ich sehe ein das die Codefragmente die ich in dieser Frage gestreut habe auch sehr gut verwirren können. Vielleicht habe ich an den falschen Stellen gespart. Das ändert aber nichts daran das ich immernoch an einer Lösung (abweichend von http://www.java-forum.org/allgemeine-java-themen/91500-threadsicheres-wait-lock-erst-wait-abgeben.html#post579936) interessiert bin. Wenn noch etwas zu der Fragestellung unklar ist versuch ich das gerne zu klären. Wenn du/ihr sagt für das Problem gibt es keine Lösung so ist das auch ok. Eine alternative Implementierung ist für mich leider nicht drin, da das System an und für sich schon läuft und es nur darum auf welche Arten sich das noch lösen lässt.

Viele Grüße

-----------------------edit-----------------------

Es reicht so doch Zwar kann der gesamte Block betreten werden, aber das ist glücklicherweise in diesem Fall nicht wichtig. Die Bedingung (1.Beitrag) ob ein Thread ein neues Objekt erzeugen soll hängt nicht vom Status der anderen Threads ab, sondern von den restlichen erzeugten Objekten auf die gewartet werden kann. Diese Liste ist frühzeitig bekannt und somit ist es ok das ein anderer Thread das lock erfragt, während ein weiterer es abgegeben hat un dnoch nicht wartet. Voraussetzung natürlich ein Thread der noch nicht wartet auch auch nicht geweckt werden

 

[FArt]

In der Tat ich fand es, und finde es immer noch nicht, einfach das Problem zu beschreiben.

Das ist ein deutliches Zeichen dafür, dass du das Problem selber noch nicht vollständig erfasst hast, die Lösung somit nicht zwingend vollständig sein muss.

 

[theseus]

Das ist ein deutliches Zeichen dafür, dass du das Problem selber noch nicht vollständig erfasst hast, die Lösung somit nicht zwingend vollständig sein muss.

Ich bin mir schon während des ganzen Threads hier unsicher ob du mir wirklich helfen willst, oder versuchst mir einfach durch die Blume zu sagen dass ich ein Idiot bin.
Belassen wirs einfach dabei.

 

[FArt]

Ich bin mir schon während des ganzen Threads hier unsicher ob du mir wirklich helfen willst, oder versuchst mir einfach durch die Blume zu sagen dass ich ein Idiot bin.

Das würde ich direkt sagen, wenn ich es denn meinen sollte.

Wenn du meine Meinung wissen willst, musst du nur meine Antworten lesen.

 

[Marco13]

Ja, Opinions ... ... ... ... : Everybody has got one

*rantast* : Die Methode
WaitObject notifyMe = getWaitCurrentObject(woList);
muss doch immer das Objekt liefern, auf das gerade gewartet wird?! Oder soll DAS erst gemacht werden, wenn ALLE warten, und dann "irgendein" Objekt liefern?

 

[theseus]

WaitObject notifyMe = getWaitCurrentObject(woList);

Ja die Methode soll aus einer Liste von Objekten eins zurückgeben auf das ein anderer Thread gerade wartet. Dieser Thread wird dann durch dieses Objekt wieder aufgeweckt. In dem Codeblock fehlt natürlich das synchronized(notifyMe) um den Befehl notifyMe.notifyAll(); auf zu rufen. dasselbe gilt für den Befehl wo.wait(); zwei Zeilen darunter, hier fehlt auch der synchronized Block. Das Beispiel ganze sieht dann folgendermaßen aus:

WaitObject wo = null;
// Diese Liste ist für alle Threads gleich und speichert alle Objekte auf denen Threads warten 
ArrayList<WaitObjekt> woList = getwoList();
synchronized (lock){
  // irgendwas weiteres Threadsicheres ausführen
  //...
  wo = new WaitObjekt(time);
  // anderen Threads das eventuell neue WaitObjekt bekanntgeben.
  woList.put(wo);
  // aus der Liste ein Objekt holen damit einer der wartenden Threads benachrichtigt werden kann
  WaitObject notifyMe = getWaitCurrentObject(woList);
  synchronized(notifyMe){  
    notifyMe.notifyAll();
  }
}
synchronized(wo){
  wo.wait();
}

Das WaitObject unterscheidet sich von einem normalen Object nur dadurch das es weitere Eigenschaften in Form von unter anderem eines Zeitparameters (time) bekommt. Man könnte man zB. mit WaitObject.getTime(); bzw. WaitObject.setTime(long time); darauf zu greifen.

Die Lösung um zu verhindern das ein notify ins leere läuft sieht in diesem Codeblock dann folgendermaßen aus:

private static class WaitObject{
  private long time;

  WaitObject(long time){
    this.time = time;
  }

  public long getTime(){
    return time;
  }
  public void setTime(long time){
    this.time = time;
  }
}

WaitObject wo = null;
Lock lock = new ReentrantLock();

public updateTimeAndNotify(long time){

  // Diese Liste ist für alle Threads gleich und speichert alle Objekte auf denen Threads warten 
  ArrayList<WaitObjekt> woList = getwoList();
  lock.lock();
  // irgendwas weiteres Threadsicheres ausführen
  //...
  wo = new WaitObjekt();
  // anderen Threads das eventuell neue WaitObjekt bekanntgeben.
  woList.put(wo);
  // aus der Liste ein Objekt holen damit einer der wartenden Threads benachrichtigt werden kann
  WaitObject notifyMe = getWaitCurrentObject(woList);
  synchronized(notifyMe){ 
    lock.unlock(); 
    notifyMe.notifyAll();
  }
}
synchronized(wo){
  wo.wait();
}

Die woList habe ich im original jedoch als ConcurrentHashMap<Thread, WaitObject> implementiert. sie ist jedem Thread bekannt der diese Funktion betritt. In dem obigen Beispiel habe ich sie aus Übersichtsgründen nur eine ArrayList beschrieben.

oldWaitObject im letzten CodeBlock ist das gleiche wie notifyMe in diesem, es geht um das zuvor schon kreierte (daher old) Objekt das nun geweckt werden soll (daher notifyMe).

Ich hoffe das ist nun diesmal wirklich alles relevante

 

[Marco13]

Ganz Unrecht hat FArt vermutlich nicht: Das klingt nach einem Problem, das man (bei abstrakt-distanzierterer Sichtwiese) bestimmt mit einer der vorgefertigten Concurrency-Klassen lösen könnte.

Im Moment hört es sich, wenn man versucht, das etwas distanzierter zu betrachten, so an, als ob dort immer nur ein Thread laufen sollte (!?), der das macht, was du als "irgendwas Threadsicheres" bezeichnet hast, und wenn er damit fertig ist, soll ein anderer Thread seinen "irgendwas Threadsicheres"-Teil machen...

Aber gut. *weiter rantast* Warum gibt es mehrere Wait-Objekte? Wenn ich das richtig verstanden habe, gibt es ja nicht für jeden Thread eins...? Ich frag' mich nur gerade, wie man aus einer Liste das Objekt rausfindet, auf welches gerade ein Thread wartet... vermutlich gar nicht, und vermutlich wird nur irgendein WaitObject zum notifien verwendet.

 

[theseus]

Es laufen immer beliebig viele Threads. Es können also auch recht viele Threads 1000+ werden. Ab und zu ruft ein Thread die Methode updateTimeAndNotify() auf und entscheidet anhand der angelegt waitObjects, ob er sich schlafen legen soll oder weiter macht. Legt er sich schlafen sucht er anhand einer Liste von waitObjects eines mit dem zu ihm passenden time Parameter raus raus (bzw. erstellt ggf. ein neues) und ruft dessen wait() Funktion auf. Außerdem wird innerhalb dieser Methode auch eine weitere Liste von WaitObejcts mit bestimmten time Parameter herausgesucht und die Threats die darauf warten aufgeweckt.
Die Zuordnung der Threads zu den WaitingObjects findet mithilfe einer ConcurrentHashMap statt. Im oberen Beispiel habe ich das nur anhand zweier Objekte "notifyMe" und "wo" skizziert.

Natürlich geht das auch anders:
Alternativ zum wecken anhand individueller WaitObjects könnten auch alle Threads auf ein und dasselbe WaitObject warten. Bei einem notify könnten dann alle Threads die gerade im Zustand WAITING sind überprüfen ob sie weiter weiter warte, oder anfangen zu arbeiten sollen.

Warum ich individuelle WaitObjects für jeden Thread möchte:
Da mitunter aber von den 1000+ auch sehr viele Threads im Zustand WAITING sein können, von denen bei einem Aufruf der updateTimeAndNotify() Methode nur wenige geweckt werden müssen, versuche ich nur die Threads zu wecken die auch wirklich geweckt werden müssen. Ich erhoffe mir durch die verminderte Threadkomunikation durch weniger Threads die auf ein notify reagieren, einen Performancegewinn.

Auf ein globales WaitObject zu warten hätte bei folgendem Szenario Nachteile:
angenommen 500 Thread sind im Zustand WAITING
1 Thread betritt die Methode updateTimeAndNotify
1 Thread soll geweckt werden
500 Threads müssen nach einem notifyAll auf dem globalen WaitObject ihre Wartebedingung überprüfen
1 geht in den Zustand RUNNABLE über
499 gehen erneut in den Zustand WAITING

In diesem Szenario sieht die zweite Möglichkeit ungleich besser aus:
500 Thread sind im Zustand WAITING
1 Thread betritt die Methode updateTimeAndNotify
1 Thread soll geweckt werden
1 Thread überprüft seine wait Bedingung nach einem notifyAll auf dem WaitObject für diesen Thread
1 geht in den Zustand RUNNABLE über
499 Threads ändern ihren Zustand nicht.

Viele Grüße

 

[Marco13]

Außerdem wird innerhalb dieser Methode auch eine weitere Liste von WaitObejcts mit bestimmten time Parameter herausgesucht und die Threats die darauf warten aufgeweckt.

*weiter abklopf* Es wird also in der echten Anwendung nicht auf EINEM WaitObjekt notifyAll aufgerufen, sondern auf mehrern (auf allen, für die eine bestimmte Bedingung zutrifft)?. Wie werden die herausgefunden, bzw. die Bedinung überprüft?
Hast du die ganze Sache mit den WaitObjects, der ConcurrentHashMap und den Synchronisationsproblemem, die zu diesem langen Thread hier im Forum geführt haben und immernoch andauern nur aufgrund der Spekulation auf dich genommen, es könnte effizienter sein, in EINEM Thread 500 Kriterien überprüfen, als in 500 Threads jeweils EIN Kriterium?

 

[theseus]

Wie schon erwähnt ich mache Performancetests, daher interessiert mich genau die Frage wieviel ein solche Änderung bringt. Die Anzahl der Bedingungen die überprüft werden müssen sind zwar in beiden Szenarien gleich, aber es müssen weniger Threads ihren Zustand wechseln. Warte ich mithilfe eines einzigen Objekts kommen die Kosten die unnötigen Kosten für das aufwecken hinzu. Dh der Thread muss neu gestartet werden um sich danach wieder schlafen zu legen. Da der Prozessor die Threads nicht wirklich parallel abarbeitet müssen nicht nur alle Bedingungen nacheinander abgearbeitet werden, sondern auch alle Threads nacheinander wieder ins Leben berufen und ggf. danach wieder schlafen geschickt werden.

Ich habe ehrlich gesagt noch keine so große Vorstellung davon wieviel Zeit das bringt, der Synchronizer (zu dem diese Methode gehört) ist jedoch ein sehr zentraler Bestandteil des gesamten Projekts und erste Tests sehen vielversprechend aus .

Zu der Bedingung ob ein Thread aufgeweckt werden soll oder nicht:
Der Methode wird ein time Parameter mitgegeben und dieser kann mit time der WaitObjekts verglichen werden. Im einfachsten Fall wecke ich die Threads auf, deren time aus dem Waitobjekt kleiner als der Übergabeparamter time ist.

 

[Marco13]

Ich hab' jetzt ernsthaft versucht, mir da ein KSKB zu basteln, aber es gelingt mir nicht, da auch nur den Hauch eines Sinnes renizuspekulieren.

 

[Marco13]

Erledigt wäre das ja, wenn du ein synchronized auf ALLE wait-Objekte machen könntest. Sowas kann man nachbauen. Aber... naja.

 

[theseus]

Ich denke es ist gar nicht so schlimm wenn der Block durch einen zweiten Thread B betreten wird, wenn ein Thread A nach diesem Block in einem unbekannte Zustand (RUNNABLE oder WAITING) ist. Thread B wird den Block betreten und vielleicht andere Threads aufwecken, im schlimmsten Fall ist ein Thread (A) darunter dessen Zustand wir zu diesem Zeitpunkt noch nicht kennen.

Nun gibt es zwei Möglichkeiten:
(Wichtig ist, dass der wait Befehl in einem eigenem synchronized Block liegt)

1.)A ist schon im Zustand WAITING. In dem Fall Wird A von B (eventuell) geweckt und alles ist gut.
2.)A ist noch im Zustand RUNNING. Wenn B jetzt A wecken könnte, würde das unweigerlich zu einem Deadlock führen. A besitzt aber noch das lock des waitObjects auf das es wartet, es ist ja schließlich in einem synchronized Block dafür. Wenn Thread B Thread A wecken will muss B erst das waitingObject-lock anfordern. Das gibt A aber erst frei wenn die wait() Methode des Objekts aufgerufen wurde.

Der unbekannte Zustand der einzelnen Threads kann also beschränkt werden auf das Codestück bevor andere Threads geweckt werden.

Ich beziehe mich auf den Code: java-forum.org - Antworten

Theroetisch gibt es noch eine weitere Möglichkeit:
Thread B versucht Thread A zu wecken, bevor Thread A den synchronized Block des waitinObjects betreten hat und somit das lock des waitingObjects besitzt. Dieser Zustand kann ebenfalls nicht auftreten da erst erst kurz vor der wait Methode, nachdem das waitingObject-lock angefordert wurde, der kritische Bereich freigegeben wird.

Das sollte doch reichen

Auf was bezig sich deine Frage nach dem Sinn?

 

[Marco13]

Bei dem Link ist was schiefgegangen.
Aber nur nochmal nebenbei (was FArt schon angedeutet hatte) : Du redest von den States - die sollten aber nicht für solche Zwecke verwendet werden - ich gehe mal davon aus, das du das nicht tust.

Und sonst ...Dieser Zustand kann ebenfalls nicht auftreten da erst erst kurz vor der wait Methode, nachdem das waitingObject-lock angefordert wurde, der kritische Bereich freigegeben wird.

Also kann er auftreten. Es ist vielleicht extrem unwahrscheinlich, aber nicht ausgeschlossen.

EDIT: Das mit dem Sinn: Mir ist einfach nicht klar, was du da für ein abstruses Ding programmierst, dass du meinst, so ein verqueres Thread-Handling verwenden zu müssen...

 

[theseus]

Ich habe in meinem letzten Beitrag von den States der einzelnen Threads geredet da das ganze Problem sich auf den unsicheren Status einen Thread zu einem bestimmten Zeitpunkt reduzieren lässt.

Und sonst ...Dieser Zustand kann ebenfalls nicht auftreten da erst erst kurz vor der wait Methode, nachdem das waitingObject-lock angefordert wurde, der kritische Bereich freigegeben wird.
Er kann eben nicht auftreten. Ich schütze den gesamten Bereich der das erstellen eines neuen waitObjects und das wecken der einzelnen waitObjects mit einschließt durch einen sepparaten lock Mechanismus. Dieses eine lock wird erst freigegeben wenn ein Thread das lock seines waitObjects besitzt. Es kann also nicht passieren das dieser Thread durch einen anderen Thread geweckt wird, da dieser exakt dieses lock dafür brauchen würde. Ich schreib das mal salopp auf:

anfordern eines globalen locks GLOBAL_LOCK
erstelle WAITOBJECT
fordere nacheinander das lock aller waitObjects an, dessen notify Methode aufgerufen werden soll
anfordern des locks auf das eigene WAITOBJECT
erst danach abgeben des globalen locks GLOBAL_LOCK
rufe WAITOBJECT.wait() auf (dieser Befehl gibt implizit das lock auf WAITOBJECT wieder frei)

dasselbe in JavaCode:

Lock GLOBAL_LOCK = new ReentrantLock();

public kritischeMethode(){

 GLOBAL_LOCK.lock();
  WaitObject WAITOBJECT = IrgendeineFunktionDieMirDasPassendeObjektLiefert();
  
  //iteriere eine Liste aller waitObjects frage nach ob sie geweckt werden sollen, wenn ja führe aus
  ...
  synchronized(IchSollGewecktWerden){
    IchSollGewecktWerden.notify();
  }

  //nun frage nach ob der Thread sich schlafen legen soll und führe dann aus:
  ...
  synchronized(WAITOBJECT){
    GLOBAL_LOCK.unlock();
    WAITOBJECT.wait()
  }

Nochmal die Liste die Ich eben aufgestellt habe:

1.)A ist schon im Zustand WAITING. In dem Fall Wird A von B (eventuell) geweckt und alles ist gut.

Dieser Fall ist Narrensicher, hier kann nichts passieren .-)

2.)A ist noch im Zustand RUNNING. Wenn B jetzt A wecken könnte, würde das unweigerlich zu einem Deadlock führen. A besitzt aber noch das lock des waitObjects auf das es wartet, es ist ja schließlich in einem synchronized Block dafür. Wenn Thread B Thread A wecken will muss B erst das waitingObject-lock anfordern. Das gibt A aber erst frei wenn die wait() Methode des Objekts aufgerufen wurde.

Gut A ist im Zustand RUNNING, befindet sich also noch vor Zeile: 18, nehmen wir an er hat Zeile 16 schon passiert (im obigen Code). Angenommen B betritt nun den gesicherten Block (hat also das global_lock angefordert). Jetzt versucht Thread B Thread A zu wecken in Zeile 10/11. A kann von B nur geweckt werden wenn das Objekt IchSollGewecktWerden aus der instanz von Thread B gleich dem Objekt WAITOBJECT der Instanz des Threads A ist. A befindet sich aber hinter Zeile 16 (laut Annahme) und besitzt daher das lock das Thread B durch das Objekt IchSollGewecktWerden anfordert. B kann folglich A nicht wecken.

Thread B versucht Thread A zu wecken, bevor Thread A den synchronized Block des waitinObjects betreten hat und somit das lock des waitingObjects besitzt. Dieser Zustand kann ebenfalls nicht auftreten da erst erst kurz vor der wait Methode, nachdem das waitingObject-lock angefordert wurde, der kritische Bereich freigegeben wird.

Die einzige Möglichkeit die noch aussteht, ist sich Thread A vor Zeile 16 befindet (also das lock auf WAITOBJECT noch nicht angefordert hat). Jetzt könnte es zu Problemen kommen, wenn Thread B Thread A wecken will. Thread B kann aber Zeile 5 nicht überschreiten, da Thread A in Zeile 16 noch das lock global_lock besitzt, das Thread B anfordert.

Ich kann also einen Deadlock ausschließen

-------------edit-------------
Hab ich nicht richtig aufgepasst, oder verschwindet eine "Thread gelöstMarkierung" wenn man diesen weiter benutzt?

 

[Marco13]

Dann ist ja gut. Im Endeffekt ist das immernoch das, was schon auf der ersten Seite stand, aber wenn's funktioniert, keine Deadlogs geben kann, und effizient ist, ist's ja gut.

 

[theseus]

Ja das ist richtig, Ende gut alles gut