Thread-sichere verkettete Liste

Dezipaitor

naja
lesen dürfen sie alle,
aber es darf eben nur einer etwas löschen oder ändern evtl. auch hinzufügen.

Ich hatte es mir vielleicht so gedacht:

Ich mache aus den Daten eine doppelt verkette Liste. Der Thread, der die Daten verarbeitet, könnte in einem Pointer immer die Adresse gespeichert haben, wo er den letzten Datensatz gespeichert hat, so muß ich die Liste nicht von vorne durchlaufen, um zu dem letzten Eintrag zu kommen. Dann kann es dem "Verarbeiten-Thread" eigentlich egal sein, was mit den ersten Einträgen der Liste passiert.

Wenn ich nun noch eine bool-Variable "Closed" in die Datensätze anfüge, könnte ich diese Variable doch immer auf true setzen, wenn der Datensatz noch hinzugefügt wird und danach wieder auf false.

Der "Senden-Thread" arbeitete die Liste nun nur so weit durch, bis er keinen Datensatz mehr oder einen "Closed" Datensatz findet.

Funktionieren würde es (nehme ich zumindest an... )

Was haltet Ihr von der Lösung? Elegant? Performant?

Mir ist gerade aufgefallen, daß ich dafür gar keine doppelt-verkettete Liste bräuchte. Ansonsten wollte ich es aber komplett so machen, wie oben beschrieben.

Falls Euch elegantere und vor allen Dingen schnellere Möglichkeiten einfallen, wäre ich wirklich für jeden Vorschlag offen.

Danke.

Gerard

also zu zeit beitet der standard kein threads an, da du mit borland builder arbeitest verschibe ich den thread mal in bcb forum

AndreasW

Hi,

http://www.inf.hs-zigr.de/~fatman98/builder_threads.php

ist ein Anfang.

Ansonsten ist glaub ihc ein Beispiel im Examples- Ordner. Sicher bin ich aber nicht.
Wenn du nciht weiter kommst, stelle detailierte Frage und zeig mal,m was du schon hast oder worans hapert.

AndreasW

Lange Rede, kurzer Sinn: Ich habe die verkette Liste "manuell" programmiert, greife also nicht auf irgendwelche Komponenten von Borland zu. Ist eine solche verkettete Liste Thread-sicher oder muß ich doch eine Komponente verwenden?

suche mal nach Thread und Synronisize hier im Forum. Gibt schon ne Menge Thread drüber.

Ein Thread muss streng in sich gekapselt sein und darf nicht auf Resoursen anderer Threads zugreifen.
Wenn du eine Liste im Hauptthread erstellst und im neuen Thread benutzt greifst du auf Ressourcen zu, die nicht zum Thread gehören. Dieses sollten man stets verhindern.

Bei VCL- Klassen muss man drauf achten, das Objekte, welche auf dem Heap gelegt werden nicht Unsynchronisiert erstellt oder zerstört werden. Destruktoren sind da besonders empfindlich.
Da der "eigentliche Thread" innerhalb der Methode "Execute" läuft, müssen also die Konstruktoraufrufe, Zugriffe und Destruktoraufrufe außerhalb dieser Methode vorgenommen oder Syncronisiert werden.

Beachte aber, dass wenn du ständig synchronisierst praktisch kein Thread mehr hast sonder ein aufeinander wartendes Gebilde.

Vielleicht habe ich was verpasst. Aber wenn "Senden an eine API" bedeutet, dass eine Funktion aufgerufen wird mit einer _TData als Parameter: wozu brauchst du dann die verkettete Liste? Aber nun gut.

Bin zwar betrunken, aber mir kommt folgender Gedanke:
* die Zeiger, die die beiden Threads in die Liste hinein verwenden, für beide Threads sichtbar machen (meinetwegen global)
* ebenso eine Instanz eines TCriticalSection
* jeder Thread achtet bei seiner Hampelei darauf, die Integrität der Liste zu erhalten
- dazu berücksichtigt er auch den jeweils anderen Zeiger
- und greift nur innerhalb eines ->Acquire()..->Release() - Blocks auf die Zeiger (und die Listendaten) zu.

Macht das Sinn?

Zur Erheiterung empfehle ich noch TMultiReadExclusiveWriteSynchronizer. Das ist glaube ich der lustigste Klassenname, den die VCL kennt. Auch wenn sie hier keine Rolle spielt.

Was die Hampelei angeht: es hilft, dass jeder Thread weiss, wo der andere gerade in der Liste hinguckt.

Bei näherer Betrachtung ist es aber nur wichtig, dass der "sendende" Thread den "empfangenden" nicht überholt. Also braucht nur der sendende Thread aufzupassen.

Trotzdem muss bei beiden Threads die Verwendung und Inkrementierung der Zeiger in eine critical section eingebettet werden, ansonsten gibt's Salat.

PAD

Du erzeugst dein neues DataPackage erst außerhalb der Liste der Pointer to next wird mit Null gefüllt

Wenn du jedem Element der Liste eine Boolvariable verpasst namens InUse Kannst du in einer Critical Sektion diese InUse of On setzen das neue Listenelement einfügen und anschließend InUse auf OFF setzen.
Solange InUse On ist darf der Sender nicht aktiv werden.
So hast du auf sichere Art eine Element hinzugefügt. Wenn der Sender und Vernichter eines Listenelements sieht das der Pointer to next auf null steht weis er dasd er am Ende der Liste ist.

Das selbe sollte der Sender machen damit nicht beim Anfügen der Daten auf ein leeres Element zugegriffen wird (last node Problematik)

Somit braucht kein Thread etwas vom anderen wissen er "prüft & setzt" in einer atomic Operation InUse
und stellt so sicher das der andere keine Aktion auf dem Element durchführt.

Alternative Lösung ist eine Mutex System.
Derjenige der eine Aktion vorhat wartet das er einen Mutex bekommt,
Der Sender erzeugt eine lokale Kopie des Elements, löscht den Orginalsatz gibt den Mutex frei Nachdem der Mutex frei ist führt er die weiteren aktionen auf der lokalen kopie aus.
Der Empfänger erzeugt die Daten wartet auf den Mutex kopiert den Pointer auf die Daten in die Liste und gibt den Mutex frei.

Critikal Sektion, Atomic Operation, Mutexe findest du in der OS-Beschreibung, dies sind alles API-calls

Viel Spaß

@Tilsiter:
Unter "Senden an API" ist leider etwas mehr gemeint, als nur ein Prozeduraufruf mit einem _TData-Objekt. Du mußt die einzelnen Felder mit einem seperatem Aufruf inkl. Feld-ID an die API übergeben. Die Feld-ID muß in manchen Fällen noch ermittelt werden -> ist keine API von mir, sondern Vorgabe.

Das mit dem Überholen habe ich mir auch gedacht. Es muß eigentlich nur den sendende Thread auf das achten, was der empfangende Thread tut.

Aber vielen Dank auf jeden Fall an alle. Ich werde jetzt wohl einige Tage damit verbringen, mich etwas genauer in Thread-Programmierung einzuarbeiten.

Danke, danke...