Kopie einer Datenstruktur mit gleichzeitiger Verwendung - wie macht man das?
-
Hallo - wohin mit meiner Frage?!
Ich habe folgendes Problem, in einem C Programm "clientA" das mit Sockets arbeitet benutze ich einen AVL Tree. Dieser wird permanent aktualisiert und hat mehrere tausend Elemente.
Nun will ich diesen Tree ueber einen Socket an einen anderen "clientB" mittels mehrerer Pakete ruebersenden - nur die Werte sind wichtig, muss aber nicht unbedingt die gleiche Veraestelung sein). Mein Problem ist, die Strategie dabei. Der Tree auf clientA soll waehrend der Zeit weiterhin benutzt werden koennen. Und da ein AVL Tree ja "rotation" betreibt um den Tree balanciert zu halten, wollte ich eigentlich Synchronisation (mutex, semaphore, etc) auf einzelne Blaetter vermeiden, also wenn etwa ein neues Blatt von clientA geschrieben oder ein altes geloescht wird. Andererseits eine Kopie vom Tree zu machen und diese zerstueckelt an ClientB zu senden scheidet auch aus, da die Kopie ja auch Zeit braucht, ausserdem gibt's da ja noch diese Sache mit der Rotation in Balancierten Baeumen. Ich habe dennoch ueberlegt den Tree nun zu lesen und zu zerstueckeln waehrend ich andererseits drauf schreibe (synchronisation?!) und zusammen mit neuen Daten (auch in Paketen verpackt) alles an den Socket von Client B zu senden. Finde mich da aber nur in neuen Problemen wieder.
Gibt es dazu allg. Ansaetze bzw. hat jemand da eine Idee, wie man bei sowas vorgehen kann?
-
Du könntest dir an dem Baum speichern, dass er nicht verändert werden darf, da
du ihn ja versenden möchtest. In der Zwischenzeit kannst mögliche Änderungen
z.B. in einer Liste speichern, die dann nach dem Versenden abgearbeitet werden.Da du ja Sicherstellen mußt, dass während eines Schreibvorganges kein weiterer
Zugriff auf den Baum geschieht, wirst du um Synchronisationsmechanismen wie
Mutexe nicht drumherum kommen.Gruß mcr
-
Hm, bist du dir wirklich sicher, dass das Kopieren des Baums signifikant Zeit verbraucht?
Denn selbst bei vielen tausend Elementen, wird das ganze wohl in weit unter einer Millisekunde erledigt sein. Wenn das ganze nicht hunderte Male pro Sekunde stattfinden muss oder auf sehr begrenzten Ressourcen laufen soll, dürfte es eigentlich nicht so das Problem sein.
-
Hallo,
Also ich habe mittlerweile weiterueberlegt, momentan denke ich ueber zwei Strategien nach:
1. ich sperre den Baum mit einem Mutex etwa und kopiere ein Backup, waehrend dessen stattfindende Aenderung speichere ich in einer Warteliste. Das Backup zerlege ich in Pakete und versende es an ClientB. Wenn ich die Warteliste auslese sende ich die Elemente ebenfalls gleichzeitig an Client B, da eben nur die Vollstaendigkeit der Info, aber nicht die Veraestelung wichtig ist.2. ich habe ueberlegt etwa einen index "noch_nicht_kopiert" einzufuegen und den Baum dahingehend zu erweitern, dass ich nur "insert"s oder "delete"s durchfuehre die kein Element beeinflussen, das das Flag "noch_nicht_koppiert" gesetzt hat. Diese sollen in eine Warteliste verschoben werden. Waehrenddessen laeuft ein anderer Thread auf dem Baum der nur "blattweise" sperrt, die Blaetter ausliest und die Pakete zum versenden erzeugt. Ist diser Kopierthread einmal durch werden die Operationen der Warteliste auf dem Baum ausgefuehrt und ebenfalls an den anderen ClientB gesendet.
Mein Problem ist eben, dass ich bisher noch recht wenig Ahnung habe, wie lange so ein Kopieren dauert, bzw so ein dauerverpacken. Genau deshalb wollte ich auch dieses Demo schreiben um versch. Moeglichkeiten mal auszuprobieren und zu sehen wo da generell die Flaschenhaelse sind.
Was haltet Ihr von den beiden o.g. Strategien?
-
oder so: der sende-thread lock'd das bäumchen, zieht sich einen snapshot, wenn der baum in balance ist (also nur die daten, so wie du's brauchst) und gibt ihn sofort wieder frei. dann kann er in aller ruhe sein abbild versenden, während der 'baum'-thread ungestört weiterarbeitet.
