Java Gleichzeitigkeit: Sperreffizienz

Question

Mein Programm hat 100 Threads.

Jeder einzelne Thread tut dies:

1) Wenn arrayList leer ist, füge ein Element mit bestimmten Eigenschaften hinzu

2) wenn arrayList nicht leer ist, durchlaufen Sie die Elemente in arrayList, wenn Sie ein passendes Element gefunden haben (das bestimmten Eigenschaften entspricht), holen Sie es und entfernen Sie die arrayList

Das Problem dabei ist, dass, während ein Thread durch die arrayList iteriert, andere 99 Threads auf die Sperre für arrayList warten.

Was würden Sie mir vorschlagen, wenn ich möchte, dass alle 100 Threads im sperrfreien Zustand funktionieren? Damit sie alle etwas zu tun haben?

Danke

Answer 1

Haben Sie sich angesehen gemeinsam vs. exklusiv Sperren? Sie könnten eine gemeinsame Sperre für die Liste verwenden und dann eine Eigenschaft "deleted" für die Listenelemente haben. Das Prädikat, das Sie verwenden, um die Listenelemente zu überprüfen, müsste sicherstellen, dass das Element nicht als "gelöscht" markiert ist, zusätzlich zu allen anderen Abfragen, die Sie haben - auch aufgrund potenzieller Lese-Schreib-Konflikte, müssten Sie auf jedes Element sperren, wie Sie durchlaufen. Dann erhalten Sie in regelmäßigen Abständen eine exklusive Sperre für die Liste, um die Löschvorgänge wirklich durchzuführen.

Die Lesesperre ermöglicht eine hohe Gleichzeitigkeit in der Liste. Die exklusiven Sperren für jedes Element der Liste sind nicht so schön, aber Sie müssen das Speichermodell zwingen, Ihre "deleted"-Flag für jeden Thread zu aktualisieren, so gibt es keine Möglichkeit, dies zu umgehen.

Answer 2

Erstens, wenn Sie nicht auf einem Rechner mit 64 oder mehr Kernen arbeiten, sind Ihre 100 Threads wahrscheinlich selbst ein Leistungsfresser.

Dann ist eine ArrayList für das, was du beschreibst, sicherlich keine gute Wahl, da das Entfernen eines Elements nicht pas in amortisierter konstanter Zeit, sondern in linearer Zeit O(n) ablaufen. Das ist also ein zweiter Leistungsfresser. Wahrscheinlich möchten Sie eine LinkedList anstelle Ihrer ArrayList verwenden (wenn Sie darauf bestehen, eine Liste zu verwenden).

Nun bezweifle ich natürlich sehr, dass Sie jedes Mal, wenn Sie ein Element suchen, über Ihre gesamte Liste iterieren müssen: Wäre eine andere Datenstruktur nicht angemessener? Vielleicht, dass die Elemente, die Sie in Ihre Liste setzen, ein Konzept wie "Gleichheit" haben und daher eine Map mit einer O(1)-Lookup-Zeit stattdessen verwendet werden könnte?

Das ist nur der Anfang: Wie ich Ihnen gezeigt habe, gibt es mindestens zwei schwerwiegende Probleme bei den Leistungen, die Sie beschrieben haben.... Vielleicht sollten Sie Ihre Frage präzisieren, wenn Sie mehr Hilfe wünschen.

Answer 3

Wenn Ihre Vorstellung von "geeignetem Element (das bestimmten Eigenschaften entspricht)" mit einer Comparator dann eine PriorityBlockingQueue würde es jedem Thread ermöglichen, die Warteschlange abzufragen und das nächste Element zu nehmen, ohne die Liste durchsuchen oder ein neues Element einreihen zu müssen, wenn die Warteschlange leer ist.

Nachtrag: Thilo einen wesentlichen Punkt ansprechen: Wenn Sie Ihren Ansatz weiterentwickeln, sollten Sie empirisch ermitteln, wie viele Threads optimal sind.

Answer 4

Der Schlüssel dazu ist, die Objektsperre für arraylist nur dann zu verwenden, wenn es wirklich notwendig ist.

Eine gute Idee wäre es, die Unterklasse arraylist zu bilden und Synchro für einzelne Lese-, Schreib- und Löschvorgänge anzubieten.

Dadurch wird eine feine Granularität beim Sperren gewährleistet, während die Threads die Array-Liste durchlaufen können und die Semantik der Array-Liste geschützt wird.

Answer 5

Ein einziger Thread soll das Array besitzen und dafür verantwortlich sein, es zu erweitern und darüber zu iterieren, um eine zu erledigende Aufgabe zu finden. Sobald eine Arbeitseinheit gefunden ist, legen Sie die Arbeit in eine BlockingQueue. Alle Arbeits-Threads sollen take() verwenden, um Arbeit aus der Warteschlange zu entfernen.

Auf diese Weise können mehrere Arbeitseinheiten pro Durchlauf durch das Array entdeckt und relativ effizient an wartende Worker-Threads weitergegeben werden.