Zusammensetzbare Parallelität in Java oder einer anderen Programmiersprache

8

Während ich ein Forschungspapier über Parallelität namens Software und die Parallelitätsrevolution ( HTML- Version) las . Ich bin auf folgende Zeilen gestoßen:

Obwohl Sperren funktionieren, stellen sie leider ernsthafte Probleme für die moderne Softwareentwicklung dar. Ein grundlegendes Problem bei Schlössern besteht darin, dass sie nicht zusammensetzbar sind . Sie können nicht zwei korrekte, auf Sperren basierende Codeteile nehmen, sie kombinieren und wissen, dass das Ergebnis immer noch korrekt ist. Die moderne Softwareentwicklung basiert auf der Fähigkeit, Bibliotheken zu größeren Programmen zusammenzusetzen. Daher ist es eine ernsthafte Schwierigkeit, dass wir nicht auf sperrbasierten Komponenten aufbauen können, ohne deren Implementierungen zu untersuchen.

  1. Ich habe darüber nachgedacht, wie Java eine komponierbare Parallelität garantiert oder ob es sogar eine Möglichkeit gibt, diese Szenarien zu erstellen.

  2. Und wie können wir Daten in einer oder mehreren Bibliotheken synchronisieren? Kann ein Programmierer dies von seinem Programm aus tun oder liegt es an der Bibliothek, die Dinge zu synchronisieren?

  3. Wenn nicht Java, gibt es dann eine andere Sprache, die sperrenbasierte Parallelität verwendet und eine zusammensetzbare Parallelität garantiert?

Folgendes stammt ebenfalls aus demselben Papier:

Es gibt mindestens drei Hauptprobleme bei synchronisierten Methoden. Erstens sind sie nicht für Typen geeignet, deren Methoden virtuelle Funktionen für andere Objekte aufrufen (z. B. Java's Vector und .NET's SyncHashTable), da das Aufrufen von Code von Drittanbietern bei gehaltener Sperre die Möglichkeit eines Deadlocks eröffnet . Zweitens können synchronisierte Methoden zu viele Sperren durchführen, indem Sperren für alle Objektinstanzen erfasst und freigegeben werden, auch für diejenigen, die niemals über Threads hinweg geteilt werden (normalerweise die Mehrheit). Drittens können synchronisierte Methoden auch zu wenig Sperren durchführen, indem die Atomizität nicht erhalten bleibt, wenn ein Programm mehrere Methoden für ein Objekt oder für verschiedene Objekte aufruft. Betrachten Sie als einfaches Beispiel für Letzteres eine Überweisung: account1.Credit (Betrag); account2.Debit (Betrag) ...

Hinweis: Das Papier wurde im September 2005 veröffentlicht

Mücke
quelle
@ErikEidt Papier haben 94 Zitate
3
Keine Antwort auf die Frage, aber Sie erhalten eine viel bessere Parallelität, wenn Sie die Interaktionen auf die Nachrichtenübermittlung beschränken: Prozesse (vollständige Prozesse, nicht nur Threads), die über asynchrone Nachrichtenwarteschlangen kommunizieren. Es ist zwar nicht so leistungsfähig wie das bedrohungsbasierte Modell, aber wenn das Senden einer Nachricht nicht blockiert werden kann, können Sie keinen Deadlock durchführen, es sei denn, Ihre Nachrichten haben eine echte zirkuläre Datenabhängigkeit. Am wichtigsten ist, dass jede Nachricht trivial als atomare Operation komponiert / interpretiert wird, sodass alle Kopfschmerzen eines konsistenten Zustands verschwinden.
cmaster - wieder einsetzen Monica
1
Software Transactional Memory ist ein Parallelitätskonstrukt, das zusammengesetzt werden kann. Haskell hat eine STM-Bibliothek.
Comingstorm
1
@penguin: Parallelität! = Parallelität. Javascript (node.js) ist ein gutes Beispiel für eine Sprache mit sehr hoher Parallelität (tatsächlich sind alle E / A gleichzeitig), aber mit einem Thread. Java hat dafür ein ziemlich gutes Framework in Form von Futures (CompletionStage). Wie sperrfrei Ihr Code ist, hängt natürlich von der Implementierung ab, aber die Tools stehen Ihnen zur Verfügung.
Slebetman

Antworten:

7

Es ist nicht die Java-Sprache. Es liegt in der Natur von Schlössern (Mutexen).

Es gibt bessere Möglichkeiten, um die Parallelität zu verbessern und gleichzeitig die Korrektheit zu gewährleisten. Diese Möglichkeiten sind sprachunabhängig:

  1. Verwenden Sie unveränderliche Objekte, damit Sie keine Sperren benötigen.
  2. Versprechungen und einen Stil, der die Fortsetzung übergibt.
  3. Verwenden sperrenfreier Datenstrukturen.
  4. Verwenden des Software-Transaktionsspeichers zum sicheren Teilen des Status.

Alle diese Techniken ermöglichen eine verbesserte Parallelität ohne Verwendung von Sperren. Keiner von ihnen hängt speziell von der Java-Sprache ab.

Robert Harvey
quelle
3

Ich habe darüber nachgedacht, wie Java eine komponierbare Parallelität garantiert oder ob es sogar eine Möglichkeit gibt, diese Szenarien zu erstellen.

Wie der Artikel sagt, ist es nicht möglich, die Kompositionsfähigkeit zu gewährleisten, wenn Sperren zusammen mit virtuellen Methoden (oder ähnlichen Mechanismen wie der Übergabe von Funktionen als Parameter) verwendet werden. Wenn ein Codeteil Zugriff auf virtuelle Methoden hat, die von einem anderen Codeteil stammen und beide möglicherweise Sperren verwenden, müssen Sie den Quellcode von überprüfen, um die beiden Codeteile sicher (dh ohne das Risiko eines Deadlocks) zu erstellen beide.

Und wie können wir Daten in einer oder mehreren Bibliotheken synchronisieren? Kann ein Programmierer dies von seinem Programm aus tun oder liegt es an der Bibliothek, die Dinge zu synchronisieren?

Im Allgemeinen muss der Programmierer die Bibliotheken für die Synchronisierung verwenden. Auf diese Weise weiß der Programmierer, wo sich alle Sperren befinden, und kann sicherstellen, dass sie nicht blockieren.

Wenn nicht Java, gibt es dann eine andere Sprache, die sperrenbasierte Parallelität verwendet und eine zusammensetzbare Parallelität garantiert?

Auch hier geht es in dem Artikel darum, dass dies nicht möglich ist.

svick
quelle
Das Papier wurde 2005 veröffentlicht. Ihre Antwort basiert auf demselben Papier. Die Sprachen haben sich seit 2005 stark weiterentwickelt. Können Sie eine aktuelle Referenz angeben oder Ihre Antwort erneut bestätigen?
2
In diesem Artikel wird nichts Spezifisches für 2005 erwähnt. Es wird auch im Jahr 2105 zutreffen, dass sperrbasierte Bibliotheken nicht zusammensetzbar sind.
Svick
Java aktualisiert ständig seine Sperrkonstrukte. Sie können das Java-Parallelitätspaket in Java5 mit Java8 vergleichen.
Es spielt keine Rolle. Java 8 hat die Möglichkeit eines Deadlocks bei der Verwendung von Sperren sicherlich nicht ausgeschlossen, daher hat sich daran nichts geändert.
Svick
2
@penguin - Es ist unmöglich, eine Sprache vollständig zusammensetzbar zu machen, wenn sie nicht zusammensetzbare Funktionen enthält, da Sie nicht garantieren können, dass geschlossene Module sie nicht auf gefährliche Weise verwenden. Sie können Ihren Code zusammensetzbar machen, selbst wenn Sie Sperren verwenden (obwohl Sie in diesem Fall vorsichtig sein müssen, wie Sie sie verwenden), aber Sie können nicht sicher sein, dass beliebige Bibliotheken und / oder Systemkomponenten dies nicht tun.
Jules
1

Low-Level-Verriegelungsmechanismen sind von Natur aus nicht zusammensetzbar. Dies liegt hauptsächlich daran, dass Sperren unter die Welt reichen, um die Maschine zu beeinflussen, die die Anweisungen ausführt.

Nachfolgende Java-Bibliotheken haben immer höhere Mechanismen hinzugefügt, um einen korrekten Multithread-Betrieb sicherzustellen. Sie tun dies, indem sie die Verwendung von lock()und volatileauf bestimmte bekannte und kontrollierbare Umstände beschränken. Beispielsweise weist eine gleichzeitige Warteschlangenimplementierung ein sehr lokalisiertes Verhalten auf und ermöglicht das Überlegen von Vorher- und Nachher-Zuständen. Die Verwendung von Mechanismen auf höherer Ebene bedeutet, dass Sie weniger von der Spezifikation oder dem Code lesen müssen, um sie richtig zu machen. Aber, und das ist ein großes Problem, Sie müssen immer noch das Sperrmodell aller Subsysteme und deren Interaktion verstehen. Außerdem beziehen sich die Änderungen in Java für die Parallelität nach Java 5 fast ausschließlich auf die Bibliotheken und nicht auf die Sprache.

Das Hauptproblem bei jedem Sperrmechanismus besteht darin, dass er den Status beeinflusst und im Zeitbereich arbeitet. Weder Menschen noch Computer denken über Zustand oder Zeit gut nach. Es ist die Fähigkeit, über Wert und Struktur nachzudenken, die es Informatikern ermöglichte, Monaden zu entwickeln, das erste, was mir in Bezug auf die Kompositionsfähigkeit in einer Sprache in den Sinn kommt.

Am nächsten kommen wir der Kommunikation sequentieller Prozesse . Dies erfordert weiterhin einen Mechanismus auf hoher Ebene, wie z. B. Postfächer und Nachrichtenübermittlung. Meiner bescheidenen Meinung nach geht CSP weder mit großen Systemen (dem ultimativen Ziel komponierbarer Software) noch mit zeitbasiertem Denken angemessen um.

BobDalgleish
quelle
1
Dies beantwortet meine Frage nicht. Ich wollte wissen, ob Java zusammensetzbar ist oder gibt es eine andere Sprache? Nach zwei Antworten ist Java nicht zusammensetzbar, aber beide Antworten liefern keine konkreten Beweise.
Wollten Sie einen Beweis dafür, dass Java, das nur Sperren verwendet, nicht zusammensetzbar ist? Wenn Sie den obigen CSP-Artikel lesen, werden Sie eine Reihe von Sprachen sehen, die zusammengesetzt werden können. Meine Kommentare beziehen sich auf jede Sprache, in der lock()und volatilesind die Granularität der Thread- oder Prozesssynchronisation.
BobDalgleish
Okay, da ist etwas, das mich interessiert. In Ihrer Antwort sagten Sie: "Am nächsten sind wir gekommen ..." Was meinen Sie damit? Wie haben Sie herausgefunden, dass CSP am nächsten ist?
1

Zunächst danke ich allen Mitgliedern, die diese Frage beantwortet haben, insbesondere Robert Harvey, dessen Antwort meiner sehr nahe zu sein scheint.

Ich habe zwei Jahre lang an Parallelitätskonzepten geforscht und nach meinen Erkenntnissen bietet keine Sprache eine Garantie dafür, dass ihre Parallelitätskonstrukte zusammensetzbar sind. Perfekt laufender Code mit unveränderlichen Datenstrukturen und STM kann auch zu unerwarteten Ergebnissen führen, da STM unter der Haube Sperren verwendet. STM ist sehr gut für atomare Operationen geeignet. Wenn wir jedoch über die Zusammensetzbarkeit von Parallelitätskontrasten zwischen Modulen sprechen, besteht eine (sehr geringe) Wahrscheinlichkeit, dass STM möglicherweise nicht wie erwartet funktioniert.

Dennoch können wir die Unsicherheit minimieren, indem wir Folgendes verwenden (Techniken / Methoden / Konstrukte):

  1. Vermeiden von Sperren und Synchronisation
  2. STM verwenden
  3. Verwendung persistenter (unveränderlicher) Datenstrukturen
  4. Freigabestatus vermeiden
  5. Reine Funktionen
  6. Asynchroner Programmierstil
  7. Vermeiden häufiger Kontextwechsel
  8. Das Multithreading-Paradigma und die Art seiner Umgebung spielen eine große Rolle

Der vielleicht grundlegendste Einwand [...] ist, dass sperrbasierte Programme nicht komponieren: Richtige Fragmente können beim Kombinieren fehlschlagen. - Tim Harris et al., "Composable Memory Transactions", Abschnitt 2: Hintergrund, S. 2

Aktualisieren

Dank Jules stehe ich korrigiert. STM verwendet verschiedene Implementierungen und die meisten von ihnen sind sperrenfrei. Aber ich glaube immer noch, dass STM hier eine gute Lösung ist, aber nicht die perfekte, und es hat Nachteile:

Jedes Lesen (oder Schreiben) eines Speicherorts innerhalb einer Transaktion wird durch einen Aufruf einer STM-Routine zum Lesen (oder Schreiben) von Daten ausgeführt. Bei sequentiellem Code werden diese Zugriffe von einem einzelnen CPU-Befehl ausgeführt. STM-Lese- und Schreibroutinen sind erheblich teurer als entsprechende CPU-Anweisungen, da sie normalerweise Buchhaltungsdaten über jeden Zugriff verwalten müssen. Die meisten STMs prüfen auf Konflikte mit anderen gleichzeitigen Transaktionen, protokollieren den Zugriff und protokollieren im Falle eines Schreibvorgangs den aktuellen (oder alten) Wert der Daten, zusätzlich zum Lesen oder Schreiben des Speicherorts, auf den zugegriffen wird. Einige dieser Vorgänge verwenden teure Synchronisationsanweisungen und greifen auf gemeinsam genutzte Metadaten zu, was ihre Kosten weiter erhöht. All dies reduziert die Single-Threaded-Leistung im Vergleich zu sequentiellem Code. - Warum STM mehr als ein Forschungsspielzeug sein kann - Seite 1

Siehe auch diese Papiere:

Diese Papiere sind einige Jahre alt. Die Dinge mögen sich geändert / verbessert haben, aber nicht alle.

CanProgram
quelle
"Ein perfekt laufender Code mit unveränderlichen Datenstrukturen und STM kann auch zu unerwarteten Ergebnissen führen, da STM unter der Haube Sperren verwendet." Können Sie ein Beispiel für ein solches unerwartetes Ergebnis geben? Soweit mir bekannt ist, wird STM als zuverlässig und zusammensetzbar angesehen, aber vielleicht wissen Sie etwas, was ich nicht bin ...?
Jules
Sie geben auch an, dass STM "Sperren verwendet", dies ist jedoch nur ein Implementierungsdetail einiger Versionen davon. STM kann mithilfe atomarer Updates in einem vollständig sperrfreien System implementiert werden. siehe dl.acm.org/citation.cfm?id=1941579
Jules
1

Ich habe von angesehenen Forschern gehört, dass jeder nützliche Synchronisationsmechanismus verwendet werden kann, um einen Deadlock zu konstruieren. Der Transaktionsspeicher (ob Hardware oder Software) ist nicht anders. Betrachten Sie beispielsweise diesen Ansatz zum Schreiben einer Thread-Barriere:

transaction {
    counter++;
}

while (true) {
    transaction {
        if (counter == num_threads)
            break;
    }
}

(Hinweis: Das Beispiel stammt aus einem Artikel von Yannis Smaragdakis auf der PACT 2009)

Wenn wir die Tatsache ignorieren, dass dies keine gute Möglichkeit ist, eine große Anzahl von Threads zu synchronisieren, scheint dies korrekt zu sein. Aber es ist nicht zusammensetzbar. Die Entscheidung, die Logik in zwei Transaktionen zu unterteilen, ist wesentlich. Wenn wir dies von einer anderen Transaktion aus aufrufen würden, sodass alles zu einer Transaktion abgeflacht wäre, würden wir wahrscheinlich nie abschließen.

Gleiches gilt für Nachrichtenübermittlungskanäle: Kommunikationszyklen können Deadlocks verursachen. Die Ad-hoc-Synchronisation mit C ++ - Atomics kann zu Deadlocks führen. RCU, Sequenzsperren, Lese- / Schreibsperren, Bedingungsvariablen und Semaphore können zum Erstellen von Deadlocks verwendet werden.

Das heißt nicht, dass Transaktionen oder Kanäle (oder Sperren oder RCU) schlecht sind. Es ist vielmehr zu sagen, dass einige Dinge einfach nicht möglich scheinen. Skalierbare, zusammensetzbare, pathologiefreie Parallelitätskontrollmechanismen sind wahrscheinlich nicht möglich.

Der beste Weg, um Probleme zu vermeiden, besteht nicht darin, nach einem Silberkugelmechanismus zu suchen, sondern rigoros gute Muster zu verwenden. In der Welt des parallelen Rechnens ist die strukturierte parallele Programmierung ein guter Ausgangspunkt : Muster für eine effiziente Berechnung von Arch Robison, James Reinders und Michael McCool. Für die gleichzeitige Programmierung gibt es einige gute Muster (siehe Kommentar von @ gardenhead), aber C ++ - und Java-Programmierer werden sie wahrscheinlich nicht verwenden. Ein Muster, das mehr Menschen verwenden könnten, besteht darin, Ad-hoc-Synchronisierungen in Programmen durch eine Warteschlange mit mehreren Herstellern und mehreren Verbrauchern zu ersetzen. Und TM ist definitiv besser als Sperren, da es den Abstraktionsgrad erhöht, sodass sich Programmierer auf das konzentrieren, was atomar sein muss , nicht auf das, was atomar sein musswie man ein cleveres Sperrprotokoll implementiert, um Atomizität sicherzustellen . Wenn sich Hardware-TM verbessert und Sprachen mehr TM-Unterstützung hinzufügen, werden wir hoffentlich einen Punkt erreichen, an dem TM im allgemeinen Fall Sperren ersetzt.

Mike Spear
quelle
1
"Bei gleichzeitiger Programmierung sind die Muster nicht so gut entwickelt." Dies ist offensichtlich falsch. Gleichzeitige Rechenmodelle reichen Jahrzehnte zurück. Das Schauspieler-Modell wurde in den frühen 70er Jahren erfunden, und seitdem wurden auch verschiedene Formen von Prozesskalkülen erfunden und untersucht. Das Problem liegt nicht bei guten Rechenmodellen; Es liegt an Programmierern, die nicht bereit sind, diese Modelle zu verwenden, und möglichen Ineffizienzen bei ihrer Implementierung.
Gardenhead
Hervorragender Punkt, @gardenhead. Die Modelle wurden entwickelt, es ist nur so, dass niemand sie benutzt. Ich werde meine Antwort bearbeiten.
Mike Spear