Zusammensetzbare Parallelität in Java oder einer anderen Programmiersprache

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

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.

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.

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.

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:

• http://dl.acm.org/citation.cfm?id=1454466
• http://dl.acm.org/citation.cfm?id=1924440

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

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.