Parallele Programmierung und komplexe Datenstrukturen - wie macht man es?
-
ist das beispiel DER anwendungsgrund oder nur wirklich ein beispiel?
mir ist nicht klar, wie du auf die idee kommst, dass in diesem szenario ein baum nötig ist. was hat die bewegung einer einheit auf dem spielfeld mit den restlichen einheiten zu tun? erst, wenn sich beide einheiten um die gleiche dritte (einheit, resource, ...) bemühen, musst du locken. das klappt aber problemlos ohne baum. einer einheit eine neue aufgabe zu geben, unterbricht die aktuelle aufgabe der einheit, berechnet die neue und führt sie aus.
die frage ist also, weiso du alles in diesem baum speichern willst.ehrlich gesagt, wundert mich dein beispiel, da es vorher so klang, dass alle knoten des baums des gleichen typs sind und eine art berechnung durchführen.
sollte ich das jetzt falsch verstanden haben, so muss ich dir leider sagen, dass dein problem über meine fähigkeiten hinaus geht. da es sich wohl um eine art graphentheoretisches problem handelt, könnten du vielleicht von jester die richtige antwort bekommen. soweit ich weiß, sind graphen eines seiner gebiete.
-
Es ist wirklich nur ein Beispiel.
Was ich implementiere ist die Umgebng, die es einem Anwender erlaubt, verschiedene Arten von Objekten zu definieren (in meinem Beispiel also Einheiten, Felder usw.), die mit verschiedenen Attributen und Beziehungen (=Referenzen) zu anderen Objekten ausgestattet sind. Da ich nicht vorhersehen kann wie die Definitionen des Anwenders (was ich oben Admin genannt hatte) aussehen, habe ich eine Klasse von Objekten die ich je nach Ausprägung (im Beispiel Einheit, Feld, Gebäude) dynamisch um eben diese Attribute erweitere. Des weiteren kann der Admin parametrisierte Tasks definieren, die ich ebensowenig vorhersehen kann. Abgebildet wird das durch eine Sequenz aus Einzelschritten (suche Objekt Nr. Xyz, folge Referenz Nr. abc, ändere Wert Nr. hij, ...). Das gibt eine sehr breite Palette von möglichen Konstellationen der Objekte, ihrer Referenzen untereinander und der Tasks die darauf arbeiten, was allerdings beabsichtigt ist. Aus dem Grund muss meine Sicht so abstrakt sein, und aus dem abstrakten Blickwinkel ist es eben so dass die Objekte die Knoten und die Referenzen die Kanten eines gerichteten Graphen sind. Die Tasks wiederum arbeiten jeweils auf einer Untermenge der Knoten. Ein Objekt/Knoten ist der Einstiegspunkt für den task, also das Objekt, bei dem die Schrittsequenz beginnt.
Tasks können nur auf den Objekten arbeiten, die vom Einstiegsobjekt aus durch bestehende Referenzen direkt oder indirekt erreicht werden können. Die Menge der Objekte, auf denen ein Task also überhaupt arbeiten kann ist ein Untergraph des Gesamtgraphen (habe ich fälschlicherweise als Baum bezeichnet, tut mir leid), und die Menge der Objekte auf denen der task tatsächlich arbeitet ist wiederum ein Untergraph dieses potentiell erreichbaren Graphen. (in meinem Beispiel oben sind sämtliche Felder der Karte im potentiell bearbeiteten Untergraph von bewege_einheit, da alle Felder über die Nachbarschaftsbeziehung miteinander vernetzt sind. Im tatsächlich bearbeiteten Untergraph sind aber nur das Feld auf dem die Einheit steht sowie das Nachbarfeld auf das die Einheit zieht).
-
Ich habe deine Beiträge mal duchgelesen und ich würde dir eine komplette objektorientierte Analyse + Design in UML empfehlen. Denn ich habe trotz lesen keinen Schimmer was deine Anforderungen sind. Mehr noch, ich glaube deine Anforderungen sind hier nicht nach dem Motto "Sortiere mir eine Liste, suche mir ein Element seiner Liste, ...". Deine Software, die du entwickeln willst, scheint komplex zu sein. Und genau dann benötigt man eine detailierte Analyse des Problems.
Wenn du hingehst und ein Modell deines Problems mittels UML darstellst, wirst du sicherlich noch selbst so einige Fragen/Dinge an deinem Programm entdecken und diese mittels Modellierung lösen, noch ehe ein Zeile Code implementiert wurde.
Generell gibt es für Nebenläufigkeit/Verteilte System viele Design Patters wie:
- Broker Pattern
- Bridge Pattern
- Proxy Pattern
- Client/Server Pattern
- Observer Pattern
...PS:
Referenzen dürften dir in dieser Phase der Programmentwicklung unbekannt sein.
-
Kann sein, dass ich da zu primitiv denke, aber mich erinnert das irgendwie an Datenbanken. Wenn da eine mehrschrittige Operation fehlschlägt, werden afaik die vorherigen Schritte zurückgerollt und abgebrochen oder nach einer gewissen Zeitspanne wiederholt versucht.
Also wäre ein Lösungsansatz evtl (wenn ich die ganze Sache überhaupt richtig verstehe, ich bin mir unsicher): Den Task abarbeiten, dabei alle Objekte, mit denen interagiert wird und wurde, locken. Wenn auf ein gelocktes Objekt gestoßen wird, alle Operationen rückgängig machen (hast ja noch die Locks drauf) und Locks freigeben, damit kein Deadlock entsteht.
-
Badestrand schrieb:
Kann sein, dass ich da zu primitiv denke, aber mich erinnert das irgendwie an Datenbanken.
Muß Dir zustimmen, wahrscheinlich wäre pumuckl mit einer objektrelationalen DB am besten bedient. Als ich mich zuletzt damit befaßt habe, waren die zwar noch grauenhaft instabil und lahm, aber das ist schon über zehn Jahre her, da dürfte sich doch was getan haben.
Aber die ganzen Mechanismen, die er will, stecken da schon drin und wie das Ding auf die Hardware skaliert, sollte nicht mehr seine Sorge sein.
-
Bitte ein Bit schrieb:
Deine Software, die du entwickeln willst, scheint komplex zu sein. Und genau dann benötigt man eine detailierte Analyse des Problems.
Die Software die ich entwicklen will ist in der Tat ziemlich komplex. Der Teil um den es hier geht ist nur ein Modul eines größeren Projektes.
In genau der Phase der Analyse befinde ich mich zur Zeit - und zur Analyse gehört eben auch die Analyse von Möglichkeiten der Parallelität, dabei war ich eben auf das geschilderte Problem gestoßen.Wenn du hingehst und ein Modell deines Problems mittels UML darstellst, wirst du sicherlich noch selbst so einige Fragen/Dinge an deinem Programm entdecken und diese mittels Modellierung lösen, noch ehe ein Zeile Code implementiert wurde.
Selbstverständlich kann eine gute Modellierung einige Probleme lösen, für andere wiederum muss man erst noch ein gutes Modell finden (wie z.B. ein Modell für die Nebenläufigkeit). Man ist dabei natürlich nicht nur auf UML beschränkt, UML ist schließlich auch nicht omnipotent.
Ich bin zur Zeit dabei nach und nach meinen Papierwust hier weiter zu überarbeiten und in elektronische Form zu bringen, ich werde erste Ergebnisse online stellen sobald ich sie habe.
PS:
Referenzen dürften dir in dieser Phase der Programmentwicklung unbekannt sein.Ich rede auch nicht von C++-Referenzen oder Java-Referenzen, sondern allein von der Tatsache, dass die Objekte in Bezug zueinander stehen.
Im Grunde erstellt der Anwender innerhalb der Software ein Modell (den Graphen), und zwar indem er die Beschaffenheit seiner Bestandteile definiert (die Attribute der Objekte) sowie die Art und Weise, wie das Modell, ausgehend von einem festen immer gleichen Bestandteil (dem Wurzelobjekt das ich weiter oben erwähnt habe) aufgebaut und verändert wird. Die einzelnen Vorgänge des Aufbaus und der Veränderungen sind die Tasks.
Der Grund für diesen Thread ist einfach, dass es möglich sein soll, dass mehrere Tasks parallel das Modell (den Graphen) verändern, solang diese Veränderung in Teilen des Modells ablaufen, die sich nicht überschneiden (also in paarweise disjunkten Untergraphen).Badestrand schrieb:
Wenn da eine mehrschrittige Operation fehlschlägt, werden afaik die vorherigen Schritte zurückgerollt und abgebrochen oder nach einer gewissen Zeitspanne wiederholt versucht.
Klingt gut, werde ich mich mal mit beschäftigen. Danke für den Tip!
-
alternativ zur pessimistischen variante (alles locken und im falle eines deadlocks ein rollback machen), kannst du auch die optimistische variante in erwägung ziehen, falls du erwartest, dass konflikte relativ selten auftreten und die tasks schwergewichtig sind.
bei der optimistischen variante erstellst du für jeden task on demand eine kopie von deinen objekten (hier evtl. proxies verwenden um das zu kapseln), auf das der task zugreift. hierfür hat jeder task einen "rucksack" von objekten, die er angefasst hat. wenn der task fertig ist, überschreibst du die originalobjekte mit den kopien. dabei kann man feststellen, falls es bereits einen anderen task gab, der das objekt bereits aktualisiert hat. in diesem fall musst du dann einen rollback machen.
-
Selbstverständlich kann eine gute Modellierung einige Probleme lösen...
Ein gutes Modell sollte alle Probleme deines Projektes lösen, so dass der Implementierungschritt trivial (unter guten Vorausssetzungen) ist!
Ich rede auch nicht von C++-Referenzen oder Java-Referenzen, sondern allein von der Tatsache, dass die Objekte in Bezug zueinander stehen.
Ok, ich kenne das Ganze halt unter dem UML-Begriff Relation.
Der Grund für diesen Thread ist einfach, dass es möglich sein soll, dass mehrere Tasks parallel das Modell (den Graphen) verändern, solang diese Veränderung in Teilen des Modells ablaufen, die sich nicht überschneiden (also in paarweise disjunkten Untergraphen).
Welche Problem gibt es eigentlich, wenn ein Thread nur einen Teilgraphen lockt? Kann man zu einem Thread direkt beim Start sagen, dass er nur auf diesen Teilgraphen arbeiten wird? Oder ist das Ganze variabel ?
-
Badestrand schrieb:
Wenn da eine mehrschrittige Operation fehlschlägt, werden afaik die vorherigen Schritte zurückgerollt und abgebrochen oder nach einer gewissen Zeitspanne wiederholt versucht.
wenige datenbanken (wenn überhaupt welchen) könnten von selbst den versuch erneut starten. meistens gibt es dabei fehlemeldungen an den client. bei postgresql beispielweise ist es so.
mathik beschreibt das, was man multi-version concurrency control nennt. neben postgresql können das fast alle andere auch. innodb von mysql beispielweise. sinnvoll wäre die kombination dieser methode und der, die badestrand beschrieben hat.
du lockst jedes element vom oben nach unten. jeder task hat zu einem zeitpunkt ein wurzelelement gelockt, das man als "am höchsten bewertet" ansehen kann. kommt ein task, der ein höher bewertetes wurzelelement hat zu einem knoten, der von einem task mit einem niederwertigen element gelockt ist, so signalisiert der hochwertige dem niederwertigen task, dass er abbrechen soll. der bricht ab und beginnt neu.
kommt ein task zu einem knoten, der schon von einem höherwertigen task gelockt ist, so bricht er selbstständig ab und beginnt ebenso von neuem.das war badestrands teil. der mvcc teil von mathik kommt jetzt: solange ein task mit seiner aufgabe nicht vollkommen fertig ist, ändert er die knoten des graphen nicht, sondern schreibt sich selbst nur die neuen knoten auf. erst wenn der task beim letzten knoten angelangt ist, wird die ganze reihe der knoten ersetzt, die der task aber natürlich vorher alle auf read-only gelockt hat.
es kann bei dieser methode dazu führen, dass tasks, die immer an niederwertigen stellen beginnen, immer von höherwertigen tasks blockiert werden. um das zu verhindern, sollte der wert eines tasks nicht nur vom höchstwertigen knoten bestimmt werden sondern auch von der anzahl an versuchen, die er schon unternommen hat. irgendwann ist er dann hochwertig genug, um gegen andere (von sich aus) hochwertige tasks zu gewinnen.
das ganze funktioniert aber nur mit einem baum.
man könnte noch darüber diskutieren, wo ein abgebrochener task wieder anfängt und ob er beispielweise einfach bei dem knoten wartet, an dem er von einem höherwertigen task unterbrochen wurde. das klappt in dem fall, da jeder task von dem der höherwertige abhängig sein könnte automatisch schon höherwertig als er selbst und damit vor ihm und dem abgebrochenen task fertig ist. ein problem der methode ist aber, dass ein task, der bei der wurzel des gesamten baumes beginnt, automatisch den ganzen baum und damit alle tasks abbrechen (bzw. unterbrechen) lässt. deshalb ist es eben nötig, die versuche pro task aufzuzeichnen.
möglicherweise hast du erfolg mit row-level locking unter postgresql. eine andere methode der speicherung wäre rdf. das ist genau für solche graphen gemacht worden.
@Bitte ein Bit
ich halte es für grundfalsch, verschiedene stufen der entwicklung derart exzessiv zu trennen. man sollte nicht so dogmatisch vorgehen.
-
danke für die Tips soweit. Ich werd mir mal was über die Concurrency-Modelle verschiedener Datenbanken raussuchen und auch über rdf...