Gleichzeitiges Rechnen - Wikipedia

Gleichzeitiges Rechnen ist eine Form des Rechnens, bei der mehrere Berechnungen während überlappender Zeitperioden ausgeführt werden gleichzeitig anstelle von sequentiell (einer, der vor dem nächsten Start beginnt). Dies ist eine Eigenschaft eines Systems - dies kann ein einzelnes Programm, ein Computer oder ein Netzwerk sein - und es gibt einen separaten Ausführungspunkt oder "Kontroll-Thread" für jede Berechnung ("Prozess"). Ein paralleles System ist ein System, bei dem eine Berechnung voranschreiten kann, ohne auf den Abschluss aller anderen Berechnungen zu warten. ^[1]

Als Programmierparadigma ist Concurrent Computing eine Form der modularen Programmierung, nämlich das Faktorisieren einer Gesamtberechnung in Unterberechnungen kann gleichzeitig ausgeführt werden. Zu den Pionieren im Bereich Concurrent Computing zählen Edsger Dijkstra, Per Brinch Hansen und C.A.R. Hoare

Einleitung [ edit ]

Das Konzept des Concurrent Computing wird häufig mit dem verwandten, aber unterschiedlichen Konzept des Parallel Computing verwechselt, ^[2][3] obwohl beide als "mehrere ausgeführte Prozesse" bezeichnet werden können im gleichen Zeitraum ". Beim parallelen Rechnen findet die Ausführung zum selben physikalischen Zeitpunkt statt, beispielsweise auf separaten Prozessoren einer Multiprozessor-Maschine, mit dem Ziel, Berechnungen zu beschleunigen. Parallelberechnungen sind auf einem (einkernigen) Einzelprozessor nur als ein Prozessor möglich Die Berechnung kann zu jedem Zeitpunkt (während eines einzelnen Taktzyklus) erfolgen. ^[a] Im Gegensatz dazu besteht das gleichzeitige Berechnen aus Prozesslebenszeiten die sich überlappen, die Ausführung muss jedoch nicht zum selben Zeitpunkt erfolgen. Ziel ist es, Prozesse in der Außenwelt zu modellieren, die gleichzeitig ablaufen, z. B. mehrere Clients, die gleichzeitig auf einen Server zugreifen. Die Strukturierung von Softwaresystemen, die aus mehreren gleichzeitigen, kommunizierenden Teilen bestehen, kann nützlich sein, um die Komplexität in Angriff zu nehmen, unabhängig davon, ob die Teile parallel ausgeführt werden können. ^{[4]: 1}

Beispielsweise können gleichzeitig ablaufende Prozesse gleichzeitig ausgeführt werden Kern durch Verschachteln der Ausführungsschritte jedes Prozesses über Timesharing-Slices: Es wird jeweils nur ein Prozess ausgeführt, und wenn er während seiner Zeitscheibe nicht abgeschlossen ist, wird er angehalten ein anderer Prozess beginnt oder wird fortgesetzt. und später wird der ursprüngliche Prozess wieder aufgenommen. Auf diese Weise werden mehrere Prozesse zu einem einzigen Zeitpunkt teilweise durchlaufen, aber zu diesem Zeitpunkt wird nur ein Prozess ausgeführt. ^{[ Zitat erforderlich ]}

Gleichzeitige Berechnungen parallel ausgeführt werden, ^[2][5] indem zum Beispiel jeder Prozess einem separaten Prozessor oder Prozessorkern zugeordnet wird oder eine Berechnung über ein Netzwerk verteilt wird. Im Allgemeinen sind die Sprachen, Werkzeuge und Techniken für die parallele Programmierung jedoch möglicherweise nicht für die gleichzeitige Programmierung geeignet und umgekehrt. ^{[ Zitat benötigt ]}

Der genaue Zeitpunkt für die Ausführung von Aufgaben Ein gleichzeitiges System wird abhängig von der Zeitplanung ausgeführt, und Aufgaben müssen nicht immer gleichzeitig ausgeführt werden. Zum Beispiel, gegeben zwei Aufgaben, T1 und T2: ^{[ Zitat benötigt ]}

• T1 kann vor T2 oder und ausgeführt und beendet werden sequentiell)
• T1 und T2 können abwechselnd ausgeführt werden (seriell und gleichzeitig).
• T1 und T2 können gleichzeitig zum gleichen Zeitpunkt (parallel und ) ausgeführt werden ] concurrent)

Das Wort "sequential" wird als Antonyme für "concurrent" und "parallel" verwendet. Wenn diese explizit unterschieden werden, werden concurrent / sequential und parallel / serial als entgegengesetzte Paare verwendet. Ein Zeitplan, in dem Aufgaben einzeln (seriell, ohne Parallelität) ausgeführt werden, ohne Interleaving (sequentiell, keine Parallelität: keine Aufgabe beginnt, bis die vorherige Aufgabe endet) wird als serieller Zeitplan bezeichnet. Eine Reihe von Aufgaben, die seriell geplant werden können, ist serialisierbar was die gleichzeitige Steuerung vereinfacht. ^{[ Zitat benötigt ]}

Koordinierung des Zugriffs auf gemeinsam genutzte Ressourcen [ ] edit ]

Die Hauptherausforderung beim Entwerfen gleichzeitiger Programme ist die gleichzeitige Steuerung: Sicherstellung der korrekten Sequenzierung der Interaktionen oder Kommunikationen zwischen verschiedenen rechnerischen Ausführungen und Koordination des Zugriffs auf Ressourcen, die zwischen den Ausführungen gemeinsam genutzt werden. ^[5] Mögliche Probleme Dazu gehören Race-Bedingungen, Deadlocks und Ressourcenhunger. Stellen Sie sich beispielsweise den folgenden Algorithmus vor, um Abhebungen von einem Girokonto vorzunehmen, das durch die gemeinsam genutzte Ressource repräsentiert wird :

 1  Bool   Rücknahme  ( Int   Rücknahme )   2  3             Balance  > =   Abzug )   4      {  5          Saldo   -   Abzug ;   6   ] return   true ;   7     }    8      return   false ;   9 }  

balance = 500 und zwei gleichzeitige -Fäden machen die Aufrufe (300) und (350) zurückziehen. Wenn Zeile 3 in beiden Operationen vor Zeile 5 ausgeführt wird, werden beide Operationen feststellen, dass balance> = Rückzug auf true ausgewertet wird, und die Ausführung wird den Abzugsbetrag abziehen. Da jedoch beide Prozesse ihre Abhebungen durchführen, wird der Gesamtbetrag mehr als der ursprüngliche Kontostand sein. Diese Art von Problemen mit gemeinsam genutzten Ressourcen profitieren von der Verwendung der Parallelitätssteuerung oder nicht blockierender Algorithmen.

Vorteile [ edit ]

Gleichzeitiges Rechnen hat die folgenden Vorteile:

• Erhöhter Programmdurchsatz: Durch die parallele Ausführung eines gleichzeitigen Programms kann die Anzahl der in einer bestimmten Zeit abgeschlossenen Aufgaben proportional zur Anzahl der Prozessoren nach dem Gustafson-Gesetz steigen.
• Hohe Reaktionsgeschwindigkeit für Eingabe / Ausgabe - Eingabe / Ausgabe-intensiv Programme warten meistens darauf, dass Eingabe- oder Ausgabeoperationen abgeschlossen sind. Durch gleichzeitige Programmierung kann die Zeit, die zu warten aufgewendet wird, für eine andere Aufgabe verwendet werden. ^{[ Zitat benötigt ]}
• Eine geeignetere Programmstruktur - einige Probleme und Problembereiche sind gut geeignet Darstellung als gleichzeitige Aufgaben oder Prozesse. ^{[ Zitat benötigt ]}

Es gibt verschiedene Modelle des Concurrent Computing, mit denen gleichzeitige Systeme verstanden und analysiert werden können. Diese Modelle umfassen:

Implementierung [ edit ]

Dieser Abschnitt muss erweitert werden . Sie können helfen, indem Sie etwas hinzufügen. ( Februar 2014 )

Eine Reihe verschiedener Methoden kann verwendet werden, um gleichzeitige Programme zu implementieren, z. B. die Implementierung jeder Computerausführung als Betriebssystem verarbeiten oder die rechnerischen Prozesse als Threads innerhalb eines einzigen Betriebssystemprozesses implementieren.

Interaktion und Kommunikation [ edit ]

In einigen gleichzeitigen Computersystemen ist die Kommunikation zwischen den gleichzeitigen Komponenten für den Programmierer verborgen (z. B. durch die Verwendung von Futures), während dies bei anderen erforderlich ist explizit behandelt werden. Explizite Kommunikation kann in zwei Klassen unterteilt werden:

Kommunikation mit gemeinsamem Speicher

Gleichzeitige Komponenten kommunizieren durch Ändern des Inhalts von Speicherorten für gemeinsam genutzte Speicher (am Beispiel von Java und C #). Diese Art der gleichzeitigen Programmierung erfordert normalerweise die Verwendung einer Form von Sperren (z. B. Mutexe, Semaphore oder Monitore), um zwischen Threads zu koordinieren. Ein Programm, das eines dieser Programme ordnungsgemäß implementiert, gilt als Thread-sicher.

Message Passing Communication

Gleichzeitige Komponenten kommunizieren durch den Austausch von Nachrichten (am Beispiel von Scala, Erlang und Occam). Der Austausch von Nachrichten kann asynchron ausgeführt werden oder kann einen synchronen "Rendezvous" -Stil verwenden, bei dem der Sender blockiert, bis die Nachricht empfangen wird. Die asynchrone Nachrichtenübermittlung kann zuverlässig oder unzuverlässig sein (manchmal als "Senden und Beten" bezeichnet). Nebenläufigkeit beim Durchreichen von Nachrichten ist in der Regel viel einfacher zu begründen als bei gleichzeitiger Verwendung von gemeinsam genutzten Speichern und wird normalerweise als eine robustere Form der gleichzeitigen Programmierung betrachtet. ^{[ Zitat benötigt} Eine große Vielfalt von Es gibt mathematische Theorien zum Verständnis und zur Analyse von Message-Passing-Systemen, einschließlich des Aktormodells und verschiedener Prozesskalküle. Die Weitergabe von Nachrichten kann effizient durch symmetrische Multiprocessing mit oder ohne Cache-Kohärenz des gemeinsam genutzten Speichers implementiert werden.

Gemeinsam genutzter Speicher und gleichzeitige Weitergabe von Nachrichten weisen unterschiedliche Leistungseigenschaften auf. In der Regel (wenn auch nicht immer) ist der Overhead pro Prozessspeicher und Taskwechsel bei einem Nachrichtenübermittlungssystem geringer, der Overhead der Nachrichtenübergabe ist jedoch größer als bei einem Prozeduraufruf. Diese Unterschiede werden oft von anderen Leistungsfaktoren überfordert.

Geschichte [ edit ]

Concurrent Computing entwickelte sich aus früheren Arbeiten zu Eisenbahnen und Telegrafie des 19. und frühen 20. Jahrhunderts, und einige Begriffe stammen aus dieser Zeit, beispielsweise aus Semaphoren . Diese Fragen beschäftigten sich mit der Frage, wie mehrere Züge in demselben Eisenbahnsystem behandelt werden sollen (Kollisionen vermeiden und die Effizienz maximieren) und wie mehrere Übertragungen über einen bestimmten Satz von Leitungen (Verbesserung der Effizienz) abgewickelt werden sollen, beispielsweise durch Zeitmultiplexing (1870er Jahre) ).

Die akademische Studie gleichzeitiger Algorithmen begann in den 1960er-Jahren, wobei Dijkstra (1965) die erste Arbeit auf diesem Gebiet galt, in der gegenseitige Ausgrenzung identifiziert und gelöst wurde. ^[7]

Prevalence [ edit ]

Parallelität ist im Computerwesen allgegenwärtig und tritt von Hardware auf einem einzigen Chip bis zu weltweiten Netzwerken auf. Beispiele folgen.

Auf der Ebene der Programmiersprache:

Auf Betriebssystemebene:

Auf Netzwerkebene sind vernetzte Systeme in der Regel parallel, da sie aus separaten Geräten bestehen.

Sprachen, die gleichzeitiges Programmieren unterstützen [ edit ]

Gleichzeitige Programmiersprachen sind Programmiersprachen, die Sprachkonstrukte für Parallelität verwenden. Diese Konstrukte können Multithreading, Unterstützung für verteiltes Rechnen, Nachrichtenweiterleitung, gemeinsam genutzte Ressourcen (einschließlich gemeinsam genutzten Speichers) oder Zukünften und Versprechen umfassen. Solche Sprachen werden manchmal als Parallelitäts-orientierte Sprachen oder Parallelitäts-orientierte Programmiersprachen (COPL) beschrieben. ^[8]

Heute sind die am häufigsten verwendeten Programmiersprachen das haben spezifische Konstrukte für Parallelität sind Java und C #. Beide Sprachen verwenden grundsätzlich ein Shared-Memory-Parallelitätsmodell, wobei das Sperren durch Monitore bereitgestellt wird (obwohl Message-Passing-Modelle zusätzlich zum zugrunde liegenden Shared-Memory-Modell implementiert werden können und wurden). Von den Sprachen, die ein Parallelitätsmodell für die Nachrichtenübermittlung verwenden, ist Erlang derzeit wahrscheinlich die am weitesten verbreitete Sprache. ^{[ Zitat benötigt ]}

Viele parallele Programmiersprachen wurden eher als Forschung entwickelt Sprachen (zB Pict) und nicht als Sprachen für die Produktion. Sprachen wie Erlang, Limbo und Occam wurden jedoch in den letzten 20 Jahren zu verschiedenen Zeitpunkten industriell genutzt. Sprachen, in denen Parallelität eine wichtige Rolle spielt, sind:

• Ada - Universeller Zweck, mit systemeigener Unterstützung für Message Passing und Monitor-basierte Parallelität
• Alef - gleichzeitig mit Threads und Message Passing - zur Systemprogrammierung in frühen Versionen von Plan 9 von Bell Labs
• Alice - Erweiterung bis Standard-ML fügt Unterstützung für Parallelität über Futures hinzu
• Ateji PX - Erweiterung von Java mit parallelen Primitiven, die vom π-Kalkül inspiriert sind
• Axum - domänenspezifisch, gleichzeitig, basierend auf dem Actor-Modell und der .NET-Common-Language-Laufzeit mit einem C- wie Syntax
• BMDFM - Binary Modular DataFlow Machine
• C ++ - std :: thread
• Cpp-Taskflow - Moderne aufgabenbasierte parallele Programmierbibliothek für C ++
• Cω (C omega) - für die Forschung, erweitert C #, verwendet asynchrone Kommunikation
• C # - Unterstützt Concurrent Computing mit Hilfe von Lock, Yield, auch seit Version 5.0 async und erwartet Schlüsselwörter
• Clojure - moderner, funktionaler Dialekt von Lisp auf der Java-Plattform
• Concurrent Clean - Funktionsprogr Amming, ähnlich wie Haskell
• Concurrent Collections (CnC) - Erzielt einen impliziten Parallelismus unabhängig vom Speichermodell durch explizite Definition des Datenflusses und der Steuerung.
• Concurrent Haskell - träge funktionale gleichzeitige Prozesse mit gemeinsamem Speicher
• Concurrent ML - gleichzeitige Erweiterung von Standard ML
• Concurrent Pascal - von Per Brinch Hansen
• Curry
• D - Multi-Paradigmasystem-Programmiersprache mit expliziter Unterstützung für die gleichzeitige Programmierung (Actor-Modell)
• E - Versprechen dazu Deadlocks ausschließen
• ECMAScript verwendet Versprechen für asynchrone Operationen
• Eiffel - über seinen SCOOP-Mechanismus, der auf den Konzepten von Design by Contract basiert
• Elixir - dynamische und funktionale Meta-Programmiersprache, die auf der Erlang-VM ausgeführt wird
• ] Erlang - verwendet asynchrone Nachrichtenübermittlung ohne gemeinsame Nutzung.
• FAUST - Echtzeitfunktion, für die Signalverarbeitung stellt der Compiler automatische Parallelisierung bereit Die Konfiguration über OpenMP oder einen speziellen Work-Stealing-Scheduler
• Fortran-Coarrays und machen gleichzeitig einen Teil des Fortran-Standards von 2008
• Go - für die Systemprogrammierung mit einem auf CSP basierenden Concurrent-Programmiermodell [19659020] Hume - funktional und gleichzeitig für Umgebungen mit begrenztem Raum und Zeit, in denen Automatenprozesse durch synchrone Kanalmuster und Nachrichtenweiterleitung beschrieben werden
• Io - akteursbasierte Parallelität
• Janus - unterschiedliche -Fragen und . Kassierer zu logischen Variablen, Beutelkanälen; ist rein deklarativ
• Java - Thread-Klasse oder Runnable-Schnittstelle
• Julia - "Gleichzeitige Programmierprimitive: Aufgaben, async-wait, Channels." ^[9]
• JavaScript - über Web-Workern. Versprechen und Rückrufe in einer Browser-Umgebung.
• JoCaml - gleichzeitige und verteilte, kanalbasierte Erweiterung von OCaml, implementiert den Join-Kalkül von Prozessen
• Join Java - Concurrent, basierend auf der Java-Sprache
• Joule - Dataflow -basiert, kommuniziert durch Message Passing
• Joyce - gleichzeitig lernend, basierend auf Concurrent Pascal mit Funktionen von CSP von Per Brinch Hansen
• LabVIEW - grafische Datenflussfunktionen sind Knoten in einem Diagramm, Daten sind Verbindungen zwischen den Knoten ; enthält objektorientierte Sprache
• Limbo - Verwandter von Alef, zur Systemprogrammierung in Inferno (Betriebssystem)
• MultiLisp - Schemavariante zur Unterstützung der Parallelität
• Modula-2 - zur Systemprogrammierung von N. Wirth as ein Nachfolger von Pascal mit nativer Unterstützung für Coroutinen
• Modula-3 - modernes Mitglied der Algol-Familie mit umfangreicher Unterstützung für Threads, Mutexe, Zustandsvariablen
• Newsqueak - für die Forschung mit Kanälen als erstklassigen Werten; Vorgänger von Alef
• occam - stark beeinflusst durch die Kommunikation sequentieller Prozesse (CSP)
• Orc - stark parallel, nichtdeterministisch, basierend auf Kleene-Algebra
• Oz-Mozart - Multiparadigm, unterstützt Parallelität im gemeinsamen Status und Nachrichtenübermittlung sowie Futures
• ParaSail - objektorientiert, parallel, ohne Zeiger, Rennbedingungen
• Abb. - im Wesentlichen eine ausführbare Implementierung von Milners π-Kalkül
• Perl mit AnyEvent und Coro
• Perl 6 enthält standardmäßig Klassen für Threads, Versprechen und Kanäle ^[10].
• Python mit Twisted Greenlet und Gevent, oder Verwendung von Stackless Python
• Reia verwendet asynchrone Nachrichten zwischen Shared-Nothing-Objekten
• Red / System - für die Systemprogrammierung, basierend auf Rebol
• Ruby mit gleichzeitiger Ruby und Celluloid
• Rust— zur Systemprogrammierung unter Verwendung von Message-Passing mit Move-Semantik, Shared Immutable Memory und Shared Mutable Memory. ^[11]
• SALSA - akteursbasiert mit Token-Passing, Join und First-Class-Fortsetzungen für verteilen Computing über das Internet
• Scala - Allzweck, entwickelt, um gebräuchliche Programmiermuster auf prägnante, elegante und typsichere Weise darzustellen.
• SequenceL - Allzweckfunktionell. Hauptzielsetzungen sind einfache Programmierung, Code-Klarheit. Lesbarkeit und automatische Parallelisierung für die Leistung auf Multicore-Hardware und nachweislich frei von Rennbedingungen
• SR - for Research
• StratifiedJS - kombinatorbasierte Parallelität, basierend auf JavaScript
• SuperPascal - gleichzeitig für den Unterricht, basierend auf Concurrent Pascal und Joyce von Per Brinch Hansen
• Unicon - for research
• Termite Scheme - fügt Erlang-ähnliche Parallelität zu Scheme
• TNSDL hinzu ) - IEEE STD-1076
• XC - Von XMOS entwickelte, von der XMOS entwickelte, gemeinsam genutzte Teilmenge der C-Sprache, die auf der Kommunikation aufeinanderfolgender Prozesse basiert, eingebaute Konstrukte für Progr Ammable I / O

Viele andere Sprachen bieten Unterstützung für Parallelität in Form von Bibliotheken auf Ebenen, die mit der obigen Liste in etwa vergleichbar sind.

Siehe auch [ edit ]

1. ^ Hierbei wird der Parallelismus innerhalb eines Prozessorkerns, z. Eine Einkern-, Einprozessor- -Maschine kann zu einem gewissen Parallelismus fähig sein, beispielsweise mit einem Coprozessor, der Prozessor allein jedoch nicht.

Referenzen [ edit ]

Quellen [ edit ]

• Patterson, David A .; Hennessy, John L. (2013). Computerorganisation und -design: Die Hardware / Software-Schnittstelle . Die Morgan-Kaufmann-Serie für Computerarchitektur und Design (5 ed.). Morgan Kaufmann. ISBN 978-0-12407886-4.

Weiterführende Literatur [ edit ]

Externe Links []