Parallele Programmierung und komplexe Datenstrukturen - wie macht man es?

[pumuckl]

Folgendes Szenario:

Ich habe eine Menge von Objekten (beliebige Anzahl), die sich gegenseitig referenzieren können, aber nicht müssen.
Dazu ist es möglich, Benutzerdefinierte Tasks auszuführen, die auf diesen Objekten arbeiten, das beinhaltet
- Werte von bestehenden Objekten lesen und verändern
- neue Objekte erstellen
- neue Referenzen erstellen und bestehende Referenzen löschen

Tasks haben eines der Objekte als Einstiegspunkt, und haben Zugriff auf alle Objekte die von diesem Einstiegspunkt aus direkt oder indirekt referenziert werden.
ein Beispiel:
4 Objekte (A-D)
Objekt A referenziert C und D
Objekt B referenziert A und D

2 Tasks, a und b:
Task a, Einstiegspunkt A (d.h. Zugriff auf A,C,D):
setze A.x = C.x + D.x
Task b, Einstiegspunkt B (d.h. Zugriff auf A,B,D):
setze D.x = A.x + B.x

Wie gehe ich vor, wenn beide Tasks parallel ausgeführt werden sollen? Ich muss z.B. die Zugriffe auf A und D synchronisieren und gleichzeitig deadlocks verhindern.

Wie gesagt, die Tasks sind benutzerdefiniert (werden zur Laufzeit gelesen/generiert), können lesende und schreibende Zugriffe usw. beinhalten. Wann diese Tasks gestartet werden und welches Objekt der Einstiegspunkt ist, wird auch von user gesteuert.
Sieht jemand eine Strategie, wie man das Problem sicher lösen könnte?

[besserwisser]

verstehe ich das richtig, dass jeder task zugriff auf alle objekte in seiner "reichweite" haben muss? in deinem beispiel, braucht task a zugriff auf A, C und D. es reicht nicht, wenn er zugriff auf A und C hat?

das problem ist noch die reichweite. du sagst direkt oder indirekt. das bedeutet doch, dass jeder task gleichzeitig auf alle objekte zugreifen kann. ist das netzwerk an objekten kein zusammenhänger graph?

[pumuckl@loggedoff]

besserwisser schrieb:

in deinem Beispiel, braucht task a zugriff auf A, C und D. es reicht nicht, wenn er zugriff auf A und C hat?

In meinem Beispiel wird lesend auf Attribute von C udn D zugegriffen und schreibend auf Attribute von A, der Task braucht also vollen Zugriff. Allerdings sind die Tatsachen, auf welche Objekte ein Task zugreift, erst zu der Zeit bekannt, wo er ausgeführt wird. Ein zusätzliches problem ist mir noch eingefallen: Die Referenzen dürfen während der Ausführung eines Tasks nicht von einem anderen umgebogen werden. Der Zugriff auf C erfolgt ja über eine solche Referenz. Ein Pseudocode-Beispiel:

Task a:
  A.x = A.getC.x + A.getD.x //1 - wie vorhin task a
  A.x += A.getD.x //2

Zwischen 1 und 2 darf die Referenz A.getD nicht umgebogen werden, damit das Ergebnis nicht inkosistent wird. Sprich

A.getD == A.getD

muss immer gelten (was bei parallelel Programmen ja nicht selbstverständlich ist).

das problem ist noch die reichweite. du sagst direkt oder indirekt. das bedeutet doch, dass jeder task gleichzeitig auf alle objekte zugreifen kann. ist das netzwerk an objekten kein zusammenhänger graph?

Das Netzwerk an Objekten als ganzes ist ein zusammenhängender Graph, ja. Es wird ein Wurzelobjekt geben von dem aus über beliebig viele referenzen alle anderen Objekte erreicht werden können. Allerdings müssen Tasks nicht das Wurzelobjekt als Einstiegspunkt haben, so dass die Teilgraphen, auf die zwei parallel laufende Tasks Zugriff haben, in den meisten Fällen disjunkt sind. Das liegt daran, dass Referenzen nicht bidirektional sind und der graph deshalb gerichtet ist.
Beispiel:

Wurzel -> A -> B -> C
Wurzel -> D -> E -> F
Wurzel -> G -> F
task a(A) //Task a mit Einstiegspunkt A
task b(D)
task c(G)

Task a und b können parallel laufen, Task a und c auch. Allerdings können sich task b und c ins Gehege kommen wenn beide indirekt auf F zugreifen.

Meine Idee war jetzt, dass ein Task sich den Graphen der von ihm benutzten Objekte lockt, seine Geschäfte ausführt und dann unlockt. Allerdings ist das nicht 100%ig sicher:

A -> B -> A, task a(A), task b(B)

Beide tasks versuchen A und B in unterschiedlichen Reihenfolgen zu lcoken, ein klassischer deadlock.
Wie kann ích den verhindern?

P.S.: ausgeloggt weil das blöde forum mcih wieder rausgeworfen hat *grml*

[mcr]

Wie groß sind denn die Tasks so?
Macht es überhaupt Sinn zu parallelisieren?

Vielleicht hilft dir ja die folgende Idee weiter:

-- an jedem Object speicherst du dir, welcher Thread Zugriff erhält.
 -- Es gibt einen Masterthread, der sich um die Vergabe von Zugriffsrechten
    kümmert.
 -- Jeder Thread darf nur auf die für ihn erlaubten Objekte zugreifen.

Der Master darf nur dann einen Task einem Thread zuweisen, wenn der Zugriff
auf alle benötigten Objekte möglich ist.

Mit diesem Ansatz benötigst du keine Locks, da der gleichzeitige lesende
Zugriff auf eine Speicherstelle "noch nicht" zu einer Kollision führt.

Das Problem bei diesem Ansatz könnte sein, dass der Verwaltungsaufwand
für den Masterthread so groß ist, dass der Parallelisierungsvorteil
verloren geht.

Gruß mcr

[pumuckl]

mcr schrieb:

Wie groß sind denn die Tasks so?

Wie oben schon gesagt, die Tasks sind benutzerdefiniert, also auch ihr Umfang, insbesondere der Rechenaufwand. Es kann also passieren, dass es Tasks gibt die einen gewissen Rechenaufwand mit sich bringen und vor allem eine gewisse Zeit brauchen, so dass andere Tasks nicht warten müssen.

Vielleicht hilft dir ja die folgende Idee weiter:

-- an jedem Object speicherst du dir, welcher Thread Zugriff erhält.
 -- Es gibt einen Masterthread, der sich um die Vergabe von Zugriffsrechten
    kümmert.
 -- Jeder Thread darf nur auf die für ihn erlaubten Objekte zugreifen.

Der Master darf nur dann einen Task einem Thread zuweisen, wenn der Zugriff
auf alle benötigten Objekte möglich ist.

Mit diesem Ansatz benötigst du keine Locks, da der gleichzeitige lesende
Zugriff auf eine Speicherstelle "noch nicht" zu einer Kollision führt.

Das Problem bei diesem Ansatz könnte sein, dass der Verwaltungsaufwand
für den Masterthread so groß ist, dass der Parallelisierungsvorteil
verloren geht.

Gruß mcr

Das eigentliche Problem an dem Ansatz ist soweit ich den verstanden habe der Mangel an Flexibilität. Wenn Referenzen zwischen Objekten bestehen, die verschiedenen Threads gehören, dann kann (und wird auch häufig) es vorkommen, dass tasks über diese Referenzen auf das Objekt im anderen Thread zugreifen müssen, dann müsste der Task entweder an den neuen thread gegeben werden (und später wieder zurück), oder ein Untertask im zweiten thread müsste aufgemacht werden, der erste Thread muss auf den zweiten warten usw. Das Synchronisieren könnte das System schnell in die Kniee zwingen, oder aber der Master müsste bei jeder Referenz-Umhängung die Zugangsrechte neu verteilen, wodurch aber andere Threads plötzlich auf verbotenen Objekten sitzen könnten.....

Ich bin am überlegen, verschiedene Ansätze für verschiedene Situationen zu verwenden:

1. "große" und "kleine" Tasks - eine Maßeinheit für die Größe könnte z.B. die Anzahl der Objektzugriffe sein.
2. "breite" und "schmale", sowie "kurze" und "lange" Graphen
   Zur Erklärung der Breite: Die Objekte im Graphen werden verschiedene Typen haben. ein gegebener benutzerdefinierter Task hat einen bestimmten Objekttyp als Einstigspunkt. Die Anzahl der Objekte des EinstiegsTyps ist also die Zahl der möglichen Einstiegspunkte. Die Anzahl der disjunkten Untergraphen mit einem Objekt des Einstiegstyps als Wurzel gibt mir die Breite. Je breiter der Graph, desto wahrscheinlicher können mehrere Tasks völlig unbehelligt nebeneinander herlaufen, ein Task kann dann problemlos den ganzen Untergraph blockieren auf den er potenziell Zugriff hätte. Natürlich setzen verschiedene Tasks an verschiedene Einstiegstypen an, weswegen bei mehreren userdefinierten Tasks mehrere Werte für die Breite rauskommen, aber daraus einen repräsentativen Wert zu berechnen ist Statistik und nicht unbedingt kompliziert.
   Erklärung der "Länge": Das ist schneller erklärt als die Breite, die Länge ergibt aus dem längsten Weg den man im Graphen zurücklegen kann ohne ein Objekt zweimal zu passieren.
   Bei einem Graph mit wenigen Objekten wird es sich eher nicht lohnen, überhaupt mehrere Threads zuzulassen, da die Wahrscheinlichkeit groß ist, dass verschiedene tasks auf das selbe Objekt zugreifen müssen. Der Gewinn durch Parallelisierung wäre nur gering und macht den zusätzlichen Aufwand nicht wett.
   Bei Graphen mit vielen Objekten gibts entweder breite, kurze oder schmale, lange. Schmale, lange Graphen dürften wie kleine Graphen dazu tendieren, dass parallele Tasks häufig auf das selbe Objekt zugreifen wollen. Allerdings sind bei langen Graphen auch größere Tasks wahrscheinlicher als bei kurzen. Vermutlich wäre da der beste Ansatz eine geringe Anzahl von Threads, wobei kleine Tasks von einem Thread nacheinander abgearbeitet werden, da hier der Parallelisierungsgewinn gering ist im Vergleich zur hohen Wahrscheinlichkeit, durch Locks ausgebremst zu werden. Für lange Threads/große Tasks sollte also der Aufwand im Falle von parallelen Zugriffen gering sein, da die wahrscheinlich sind.
   Breite Graphen können tendenziell von vielen Tasks parallel bearbeitet werden, da die sich wahrscheinlich nicht ins Gehege kommen. Hier sollte also der Aufwand für den Zugriffsschutz möglichst gering sein, der Performanceverlust durch Zugriffskonflikte ist dafür unkritisch, da sie tendenziell selten auftreten.
   Insgesamt wäre es also ideal wenn je nach den Bedingungen zwischen den drei Ansätzen (nicht parallel, sensibel (lange graphen/große tasks), unsensibel (breite graphen)) Bei Bedarf gewechselt werden kann. Wenn die Frequenz der Taskaufrufe gering genug ist wirds auch keinen Bedarf für Parallelisierungen geben, ungeachtet der Gestalt des Graphen.

[besserwisser]

also im prinzip hast du eine menge von knoten und dazu eine menge von wurzelbäumen, die diese knoten verbinden. disjunkt ist die menge an kanten und nicht die menge der knoten? ist das richtig so?

du wirst möglicherweise ein performance problem bekommen, wenn der graph sehr groß ist und du wirklich jedes einzelne objekt speichern willst. du müsstest zum locken eines baumes alle objekte erreichen. erst dann kannst du mit der arbeit loslegen.

kannst du beim erstellen des graphen jeden knoten so markieren, zu welchem baum er gehört?
im prinzip denke ich es mir ca so: task a beginnt bei einem knoten und lockt sich alle bäume, die zu diesem knoten direkt gehört, als schreibbar. alle bäume, die von schreibbar-gelockten bäumen nur lesbar verwendet werden (d.h. gemeinsame knoten außer dem aktuellen ausgangsknoten haben), müssen read-only gelockt werden. beim erstellen des graphen braucht es dafür aber zusätzliche arbeit, da man für jeden baum festlegen muss, mit welchen bäumen er zusammenhängt.

[also]

Das klingt für mich sehr gefährlich und verwirrend, nicht nur technisch, sondern auch für den Nutzer. Wenn jetzt zwei Tasks über Referenzen an das gleiche Objekt kommen und es verändern wird das einen Benutzer verwirren, weil erst der eine Task was ändert und dann der andere und der User sich dann fragt, warum die Änderung vom ersten nicht funktioniert hat, hat sie eigentlich schon, wurde aber sofort überschrieben, aber das kapiert keiner.

[mcr]

Ich habe, so glaube ich, immer noch nicht so recht verstanden,
was dein eigentliches Ziel ist. Du hast hier eine Abstraktion
deines Problems geschildert.

Wie bekommst du diese Tasks?

--  Stehen sie zu Beginn fest? Gibt es eine oder mehrere Dateien,
     in denen sie dem Programm übergeben werden?
     Dann kann dein Programm diese Analysieren und eine schnelle/gute
     Reihenfolge bestimmen.

 --  Oder werden die Tasks online übergeben?
     Dann bleiben Fragen offen wie: 
      - wie lange laufen die Tasks?
      - wartet der User auf die Ergebnisse?

Ist die Reihenfolge, in denen die Tasks ausgeführt werden wichtig?

All diese Frage zielen auf folgendes hinaus: macht es Sinn zu parallelisieren?

Ist das Problem akademischer Natur?

Gruß mcr

[pumuckl]

besserwisser schrieb:

also im prinzip hast du eine menge von knoten und dazu eine menge von wurzelbäumen, die diese knoten verbinden. disjunkt ist die menge an kanten und nicht die menge der knoten? ist das richtig so?

Ich habe eine Menge von Objekten die sich gegenseitig referenzieren. Durchaus vergleichbar mit C++-Objekten die Pointer auf andere Objekte haben. Durch die Menge der Objekte und der Referenzen untereinander wird der Graph aufgebaut. Zusätzlich gibts ein Basis-Verwaltungsobjekt durch das diverse Dinge (sowas wie Garbage-Collection etc.) geregelt werden, das ist das allgemeine Wurzel-Objekt von dem ich oben gesprochen hab.

du wirst möglicherweise ein performance problem bekommen, wenn der graph sehr groß ist und du wirklich jedes einzelne objekt speichern willst. du müsstest zum locken eines baumes alle objekte erreichen. erst dann kannst du mit der arbeit loslegen.

Dass da Performance-Probleme auftauchen könnten ist mir bewusst, deshalb versuche ich auch, mögliche Designs der ganzen Geschichte dreimal zu durchdenken. Eine Teilmenge der Objekte wird abgespeichert (z.B. in einer Datenbank), die zugehörigen Objekte werden über Proxies aus der DB geholt bei Bedarf - aber fürs Locken wird das ja nicht unbedingt nötig sein.

kannst du beim erstellen des graphen jeden knoten so markieren, zu welchem Baum er gehört?

Da die Bäume nicht fix sind sondern sich dynamisch ändern können (ändern der Referenzen) kann ich das nicht. Außerdem hängen ja alle Objekte direkt oder inidrekt unter dem Wurzelobjekt, so dass es im Grunde tatsächlich nur ein Baum ist. Deshalb gehts bei den Tasks um die zugänglichen Unterbäume.

Ich versuch mal ein typisches Szenario zu skizzieren. Der Admin (der, der die Objekte und den Ablauf der Tasks definiert) versucht, ein Spiel zu implementieren, es gibt folgende Objekttypen: Spieler, Einheiten, Felder, Gebäude. Ein typischer Task wäre z.B. einheit_bewegen (Parameter: PlayerID, Einheitsnummer, Richtung) und gebäude_bauen (Parameter: PlayerID, Einheitsnummer, GebäudeTypID)

Der Graph ist folgendermaßen aufgebaut:
- Das Wurzelobjekt referenziert alle Spieler und alle Felder.
- jedes Spieler-Objekt referenziert die Einheiten, die dem Spieler gehören
- jedes Einheits-Objekt referenziert das Fed auf dem es steht
- jedes Feld-Objekt referenziert die Gebäude die darauf stehen sowie die benachbarten Felder

Durch den task einheit_bewegen werden jetzt z.B. Referenzen geändert (die bewegte Einheit referenziert danach ein anderes Feld)
Der Task gebäude_bauen wiederum könnte zu konkurrierenden Zugriffen führen, wenn z.B. zwei verschiedene Einheiten auf dem selben Feld stehen und ein Gebäude bauen sollen: Enstiegspunkt für die Tasks wäre das jeweilige Einheitsobjekt, beide halten aber eine Referenz auf das gleiche Feld-Objekt, die beiden Tasks müssten also auf das selbe Feldobjekt zugreifen...

Solche und änhliche Situationen könnten in beliebiger Komplexität vorkommen, deshalb: ja, es ist technisch gewiss eine Herausforderung und kann auch zu Verwirrungen beim User (dem der die Ausführung der Tasks anstößt) führen, wenn der Admin die Tasks schlecht definiert.

Momentan denke ich, dass ich es von der Implementierung her recht simpel halten werde, und zwar so dass es entweder nicht-parallel abläuft oder aber so, dass ein Task sich zuerst den kompletten abhängigen Unterbaum locked und erst nach erfolgreichem kompletten Locken die Abarbeitung beginnt. Trifft beim Locken ein Task auf einen Lock eines anderen Tasks wird der Lockvorgang abgebrochen und der Task zurückgestellt bis der konkurrierende Task fertig ist. Das mag performancetechnisch unter Umständen nicht so umwerfend sein, aber Optimierungen kommen später. Derweil hab ich mir noch ein wenig Literatur zum Thema besorgt (siehe hier) - vielleicht bringt mich die ja noch auf neue Ideen...

[besserwisser]

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.

[pumuckl@logged_off]

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).

[Bitte ein Bit]

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.

[Badestrand]

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.

[pointercrash**]

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.

[pumuckl]

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!

[mathik]

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.

[Bitte ein Bit]

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 ?

[besserwisser]

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.

[pumuckl]

danke für die Tips soweit. Ich werd mir mal was über die Concurrency-Modelle verschiedener Datenbanken raussuchen und auch über rdf...