Thread-sichere verkettete Liste

Hi,

ich bin etwas neu in der Thread-Programmierung; deshalb frage ich bei einigen Dingen gerne nach. Hier also folgendes Problem:

Ich habe mit dem Borland C++ Builder ein Programm geschrieben, welches über einen Server-Socket Datensätze mit mehreren Feldern empfängt (ca. 10.000/Minute). Diese Datensätze werden nach Empfang sofort in die einzelnen Felder aufgeteilt und in einer Struct "_TData" gespeichert. Die Daten werden in Form einer einfach-verketteten Liste gespeichert. Danach werden die Daten an eine API übergeben. Das verarbeiten der Daten und das Senden an die API würde ich gerne jeweils in einen eigenen Thread umprogrammieren. Dazu müßten beide Threads auf die verkettete Liste mit den Daten zugreifen. Der Thread zum Empfangen der Daten soll neue Datensätze am Schluß der verketteten Liste anhängen und der Thread zum Senden soll die Liste natürlich vom Anfang durcharbeiten. Wenn der "Senden-Thread" einen Datensatz weitergesendet hat, soll er aus der verketteten Liste gelöscht werden.

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?

Danke schon mal!

Korbinian

thread sicher heist nur, dass immer nur eine prozedur auf das dings zugreiffen kann. bei einer verketteten liste musst du folgendes sicherstellen:
- es darf nichts gelöscht werden, was grad in benutzung ist
- ein pointer darf nur von einem benutzt werden (wg. integrität: wenn 2 das dings benutzen und reinspeichern, kennt sich keiner mehr aus)

es gab da mal ein paar themen dazu. benutz doch mal die suchfunktion

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