Frage Multi-Threading mit langer verketteter Liste


Ich habe hier eine Algorithmusfrage. Es gibt 10 Threads im System und Sie erhalten eine Linkliste mit 10 K Elementen darin. Wie machst du die Thread-Synchronisation (Additionslöschung etc.) so, dass sie für die Performance optimiert ist? Es ist nicht ratsam, einen Mutex für die Liste zu verwenden, da dies die Leistung beeinträchtigt.


6
2018-05-23 10:04


Ursprung


Antworten:


Die Datenstruktur der verknüpften Liste geht davon aus, dass alle Operationen sequenziellen Regeln folgen. Sieh dir das an gleichzeitig verknüpfte Liste 

Ganz gleich, um welche Art von Maschinen es sich handelt, die   Schnittstelle und erwartetes Verhalten implizieren sequentielle Logik.


1
2018-05-23 11:47



Wenn auf alle Positionen mit der gleichen Häufigkeit zugegriffen wird und Sie den Listenknoten ändern können, können Sie für jeden Knoten einen Mutex hinzufügen:

typedef struct node{ 
   char* data;
   struct listNode *next;
   pthread_mutex_t lock; 
} listNode ;

Kommt auch auf die Größe der Daten des Knotens an. Wenn es sehr klein ist, kann dies aufgrund des Mutex-Speichers, der Erstellung und des Löschens einen Overhead verursachen.

Wenn es sich um einen Overhead handelt oder der Knoten nicht geändert werden kann, können Sie die Liste z. B. in 100 Gruppen von 100 Elementen aufteilen und einen Mutex für jede Gruppe verwenden


2
2018-05-23 10:37



Sie können den Linux-Systemaufruf futex zur Synchronisation verwenden.


0
2018-05-23 10:32



Es hängt von der Operation ab, die Sie in der Linkliste ausführen möchten und ob die Liste sortiert ist.

  1. Wenn Sie Bedenken haben, dass 2 Threads den Wert eines Knotens ändern, fügen Sie Mutex für jedes Nore hinzu, wie hier erwähnt.
  2. Wenn Sie Bedenken bezüglich der Listenoperation haben (hinzufügen, entfernen): Es ist davon abhängig, ob Sie mehr lesen als schreiben - verwenden Sie die Schreibsperre, wenn jeder Thread auf einem Teil der Liste arbeitet, können Sie nur den relevanten Thread entfernen

0
2018-05-23 10:47



Ich finde das Antwort von Evans ist richtig. Aber ich würde vorschlagen, zu verwenden Spinlocks Anstatt von Mutexe. Spinlocks sind effizienter im Falle von geringe Nebenläufigkeit und kurze Haltezeiten.

typedef 
struct ListNode { 
   void * data;
   struct ListNode * next;
   pthread_spinlock_t lock;
}
ListNode;

0
2018-05-23 11:07



Die richtige Lösung hängt stark von den Arbeitsfrequenzen auf dem Objekt ab, das synchronisiert werden soll (die Liste in Ihrem Fall). Operationen auf dem Container sind Container-Erstellung, Container-Änderung, Container-Traversal und Artikelmodifikation. Wenn zum Beispiel die Liste größtenteils durchlaufen und gelesen wird, könnte es sein, dass die Liste ein falscher Container für den Job ist. Vielleicht brauchen Sie wirklich eine Art Map (auch Dictionary genannt), die einen wirklich schnellen Lesezugriff bietet, wenn Sie einen Schlüsselwert haben. In diesem Fall gibt es überhaupt keine Traversierung, und es könnte sein, dass die Synchronisation des gesamten Kartencontainers die effizienteste ist, einfach weil wir den Typ des Containers geändert haben.


0
2018-05-23 11:39



Erstens angenommen, dass das Hinzufügen / Entfernen von Elementen zu der Liste nicht der Grund dafür ist, Multithread zu sein (stattdessen ist die Logik zum Bestimmen / Erzeugen dieser Elemente der Steuerprozess) Sie sollten Ihre Datenstruktur überdenken.

Als nächstes wird angenommen, dass jeder Thread nicht miteinander interagiert (ein Thread löscht keinen Datensatz, der von einem anderen eingefügt wurde) und dass jeder Thread eine endliche Menge an Arbeit hat. Lassen Sie jeden Thread die tatsächliche verknüpfte Liste nicht berühren, stattdessen muss jeder Thread zwei zusätzliche Listen führen.

Es funktioniert so:

  1. Jeder Thread wird ausgeführt und erstellt zwei zusätzliche Listen mit zu löschenden und einzufügenden Datensätzen

  2. Wenn der Thread unsortiert ist, wenn der Thread fertig ist, können wir einfach die Listen "zusätzliche neue Elemente" für jeden Thread an den Anfang oder das Ende der bestehenden Liste anhängen.

  3. Als nächstes für gelöschte Objekte, führen wir die Liste der Elemente zusammen, die aus jedem Thread gelöscht werden sollen, und dann durchqueren wir die ursprüngliche verknüpfte Liste und entfernen die Elemente, wenn wir auf sie stoßen (die Leistung kann hier verbessert werden, indem a hashtable für die Liste der zu löschenden Elemente.

Dies funktioniert sehr gut, vorausgesetzt, die beiden Annahmen zu Beginn sind erfüllt. Es bedeutet auch, dass keine Mutexe oder Locks benötigt werden. Ihre Hauptliste wird erst am Ende von einem einzelnen Thread aktualisiert, nachdem alle Threads wieder in den Hauptthread eingebunden sind.


0
2018-05-23 12:03