WikiDer > Verteilte Programmierung

Verteilte Programmierung (ebenfalls parallele Programmierung) ist ein Technik von Computerprogrammierung und Programm-Design, bei dem ein Computerprogramm aus mehreren Unterprogrammen besteht, die gleichzeitig ausgeführt werden können oder nicht. Mehrprozessormaschinen können durch diese Art der Programmierung eine bessere Leistung erzielen.

Operation

Die verteilte Programmierung teilt einen einzelnen Job in mehrere auf Teilaufgaben die relativ unabhängig berechnet und anschließend zu einem einzigen Ergebnis rekombiniert werden können. Dies kann sich auf einem einzelnen Computer befinden oder auf mehrere Systeme verteilt sein. Im zweiten Fall ist der Begriff verteiltes Rechnen anwendbar. Verteilte Programmierung ist am effektivsten für Aufgaben, die sich leicht in Teile zerlegen lassen, wie (einige) rein mathematische Probleme.

Verteiltes Rechnen (verteilte Arithmetik) kann als eine Methode definiert werden, bei der verschiedene Computer arbeiten, die über ein Kommunikationsnetzwerk verbunden sind.

Zu den Pionieren im Bereich der verteilten Programmierung gehören Edsger Dijkstraße und Tony Hoare.

Vergleich der sequentiellen Programmierung

Eine allgemeine Beschreibung, wie a Computer ist diejenige, in der ein Programm ein Rezept ist: eine Liste von Anweisungen, die nacheinander vom Computer vom Anfang bis zum Ende ausgeführt werden (siehe auch Von Neumann-Zyklus). Dieses Modell der Programmausführung durch einen Computer ist als sequentielle Programmausführung bekannt.

EIN verteiltes System ist ein Computerprogramm, das aus mehreren aufeinander folgenden Programmen besteht, die gleichzeitig ausgeführt werden können. Das heißt, jedes Unterprogramm wird auf die gleiche Weise wie ein sequentielles Programm ausgeführt, jedoch können die Befehle der Unterprogramme in Bezug aufeinander gleichzeitig ausgeführt werden.

Beispiel für ein verteiltes Programm:|[ || |[ || |[ x := x 1 || y := y 1 || z := z 1]| || ]| || ]|

Bei der verteilten Programmierung gibt es viele Variationen der präzisen Ausführung; die Unterprogramme können auf verschiedenen Prozessoren oder abwechselnd auf einem Prozessor ausgeführt werden. Es können mehrere Computer in einem Netzwerk oder ein einzelner Computer mit vielen Prozessoren verwendet werden. Jede Variante hat ihre Vor- und Nachteile.

Synchronisation und Atomarität

Verschachtelung

Die Technik der verteilten Programmierung gibt einem Softwareentwickler zusätzliche Flexibilität in seinem Design, denn er hat die Möglichkeit, ein großes Programm in separate Blöcke aufzuteilen, die zusammenarbeiten und möglicherweise sogar die Rechenleistung mehrerer Prozessoren gleichzeitig nutzen. Diese zusätzliche Flexibilität hat jedoch ihren Preis im Hinblick auf eine zusätzliche Komplexität beim Entwurf der Unterprogramme eines verteilten Programms.

In einem sequentiellen Programm, jedes Aussage wird im Programm in der Reihenfolge ausgeführt, in der die Anweisungen im Programm geschrieben werden. Die Abfolge von Aussagen und die Wirkung dieser Aussagen auf die Erinnerung des Computers ist eindeutig festgelegt. In einem verteilten Programm laufen jedoch mehrere Programme gleichzeitig und auch die genaue Reihenfolge, in der die Anweisungen der verschiedenen Unterprogramme ausgeführt werden, ist nicht festgelegt. Betrachten Sie das folgende Programm:

   Geteilt: var x : ganze Zahl; | x := 0; Unterprogramme:|[ || |[ wahr machen -> || tu wahr -> x := x 1 || x := x - 1 od || od]| || ]|

Die Anweisungen der Unterprogramme können in beliebiger Reihenfolge ausgeführt werden. Auch ist nichts über die Geschwindigkeit bekannt, mit der jedes Unterprogramm ausgeführt wird. Eine mögliche Abfolge von Anweisungen bei der Ausführung des Programms ist:

   x := x - 1 x := x 1 x := x 1 x := x 1 x := x 1 x := x 1 x := x 1 x := x - 1 x := x - 1 x : = x 1 x := x 1 { x hat jetzt den Wert 5 } .....

Aber auch folgendes könnte sein:

   x := x 1 x := x - 1 x := x 1 x := x - 1 x := x 1 x := x - 1 x := x 1 x := x - 1 { x hat jetzt den Wert 0 } .....

Darüber hinaus kann ein Computer das Inkrementieren von x intern wie folgt durchführen:

   y := x; z := y1; x := z

und die Absenkung in ähnlicher Weise, mit einer noch größeren Anzahl von Variationen in der genauen Reihenfolge der gegenseitigen Aussagen und ihrer Auswirkungen auf das Gedächtnis.

Dieses Phänomen (dass die verschiedenen Anweisungen in einem Programm in unterschiedlicher Reihenfolge ausgeführt werden können) nennt man Verschachtelung. Und eine gewisse Ordnung aus allen Möglichkeiten wird auch zu einem (spezifische) Verschachtelung erwähnt.

atomarität

Wie bereits erwähnt, stellt sich bei der verteilten Programmierung immer die Frage, wie genau Anweisungen ausgeführt werden und welche Anweisungen unterbrochen werden können und damit unerwartete Auswirkungen haben. Daher ist es bei der verteilten Programmierung immer wichtig zu wissen, welche Anweisungen unteilbar sind (d. h. nicht unterbrochen werden können und daher immer die erwartete Wirkung haben). Eine solche unteilbare Aussage wird a atomar Aussage genannt.

Es ist eine besondere Art von atomarer Aussageanweisung Ein-Punkt-Aussage: Dies ist eine Anweisung, in der höchstens eine Shared Variable höchstens einmal vorkommt (also auch: gelesen oder zugewiesen wird, aber nicht beides). Eine solche Anweisung ist immer atomar, weil sie sich die Tatsache zunutze macht, dass ein Computer nicht gleichzeitig von einer Stelle im Speicher des Computers lesen und schreiben kann. Wenn also nicht mehr als eine gemeinsam genutzte Position im Speicher verwendet wird, ist die Anweisung per Definition atomar. Das Algorithmendesign auf akademischem Niveau strebt daher oft nach Algorithmen, die auf Ein-Punkt-Aussagen basieren – ihre Funktionsweise hängt nicht von speziellen Maßnahmen in einer Programmiersprache ab, um Fehler zu vermeiden.

Synchronisation

Die Ein-Punkt-Aussage löst jedoch nicht alle Probleme. Für Unterprogramme in einem verteilten Programm ist es manchmal notwendig, einander auf einer höheren Ebene zu betrachten, als nur auf der Ebene des Zugriffs auf eine Position im Speicher. Erwägen Sie den Zugriff auf Peripheriegeräte, oder stellen Sie sicher, dass ein Unterprogramm allen anderen nicht zu weit voraus ist. Es ist dann erforderlich, die Ausführung von Teileprogrammen zu synchronisieren.

Synchronisation Dies bedeutet immer, dass ein Unterprogramm vorübergehend angehalten wird, bis eine bestimmte Bedingung erfüllt ist. Dafür gibt es viele Synchronisationsmechanismen; Beispiele dafür sind Semaphoren (oft in der Literatur Semaphoren erwähnt), Monitor, Kanäle blockieren oder beschäftigt warten.

Aber auch dieses Herunterfahren ist nicht unproblematisch: Wird ein verteiltes Programm ungenau gestaltet, besteht die Gefahr, dass Sackgasse (alle Unterprogramme stoppen und warten ewig aufeinander), Live-Sperre (Unterprogramme wiederholen nutzlose Aktionen als Reaktion auf andere Unterprogramme) oder individueller Hunger (das System als Ganzes läuft weiter, aber ein oder mehrere Unterprogramme werden so schnell ausgeführt, dass der Rest nicht mehr besprochen wird). Letztere Gefahr droht auch, wenn ein verteiltes Programm mit 'Prioritäten' arbeitet (wobei ein Unterprogramm mehr Recht auf Prozessorzeit hat als andere Unterprogramme).

Siehe auch Peterson-Algorithmus zum gegenseitigen Ausschluss

Die Vor- und Nachteile von verteilten Programmen

Im Allgemeinen ist der Entwurf eines verteilten Programms wesentlich komplizierter als der eines sequentiellen Programms. Außerdem kann ein verteiltes Programm nicht mehr Probleme lösen als ein sequentielles Programm (siehe auch Turing Maschine). Allerdings wird der verteilten Programmierung immer mehr Aufmerksamkeit geschenkt.

Dies liegt hauptsächlich daran, dass ein verteiltes Programm möglicherweise nicht leistungsfähiger ist als ein sequentielles Programm, aber es kann schneller sein. Verteilte Programme werden daher häufig eingesetzt, um die Rechenleistung vieler Rechner zur Lösung eines Problems zu bündeln (siehe auch verteiltes Rechnen, SETI, Grid-Computing).

Einige Nachteile

• Gleichzeitige Operationen auf oder mit gemeinsam genutzten Ressourcen (zB Variablen) werfen das Problem auf, sehen zu können, dass "jede mögliche" Ausführung eines verteilten Programms (dh alle Verschachtelungen der verschiedenen Unterprogramme) korrekt sind. Das heißt, die Spezifikationen des Systems erfüllen. Wenn dabei Fehler gemacht werden, kann dies zu absurden Ergebnissen führen.
• Manchmal muss man bei der Ausführung verteilter Prozesse den möglichen Absturz bestimmter Teile des Systems berücksichtigen. Bei Systemen, die nur aus einem Prozess bestehen, ist oft sofort klar, wie aber ein System am Laufen gehalten werden kann, wenn es aus vielen parallel laufenden Prozessen besteht. Kurz gesagt, Fehlerresistenz ist ein komplexeres Problem.

Einige Vorteile^[1][2]

• Durch Gleichzeitigkeit (das englische Wort für Gleichzeitigkeit) in Systemen wird es möglich, verschiedene Dinge nebeneinander zu tun. Denken Sie an Ihr Betriebssystem, das viele Programme (sprich: Prozesse) nebeneinander ausführen kann. Aber auch bei modernen Geräten ist es notwendig, verschiedene Peripheriegeräte (Mäuse und Tastaturen) gleichzeitig abzuhören, während der vorherige Befehl noch ausgeführt wird.
• Normalerweise ist weniger Programmierung erforderlich. Denn wenn keine Bestellung vorliegt, muss diese nicht codiert werden.
• Den Compilern und dem Betriebssystem wird viel abverlangt, wodurch die Effizienz auf einem höheren Niveau verbessert werden kann.
• Das System ist flexibler; Komponenten können leichter hinzugefügt oder geändert werden, wenn es keine feste Reihenfolge in der Ausführung gibt. (Sonst muss in der gesamten Sequenz ein Platz für die Funktion gefunden werden).

Varianten und Techniken der verteilten Programmierung

Im Laufe der Jahre wurden viele Varianten und Techniken der verteilten Programmierung entwickelt. Sowohl im Bereich der Hardwarearchitektur als auch der Softwareimplementierungen sind viele Variationen des Themas entstanden.

Hardware-Variationen

Wenn es um verteiltes Programmieren und Ausführen verteilter Programme geht, sind im Allgemeinen zwei Dinge beteiligt: ​​Prozessoren (die Anweisungen ausführen) und Speicher (in dem Daten gespeichert werden).

Prozessoren

Beim Ausführen verteilter Programme ist es möglich, einen oder mehrere Prozessoren zu verwenden. Bei mehreren ist eine beliebige Zahl zwischen 2 und der Anzahl der auszuführenden Unterprogramme möglich (mehr Prozessoren sind auch möglich, aber nicht sinnvoll) -- in diesem Fall spricht man oft von parallele Programmierung, denn Unterprogramme werden dann durchaus parallel ausgeführt. Falls es mehr Unterprogramme als Prozessoren gibt, ist es notwendig, dass ein darunterliegendes System (siehe Betriebssystem) sorgt dafür, dass jedes Unterprogramm regelmäßig auf einen Prozessor zugreift (siehe Aufgabenwechsel, Lastverteilung, Betriebssystem).

Bei mehreren Prozessoren sind auch Variationen möglich – denken Sie an mehrere Prozessoren verbunden mit a Bus, aber auch über ein Netzwerk verbundene Prozessoren sind möglich. Im letzteren Fall ist es möglich, dass ein speziell angeordnetes Netzwerk mit einer bestimmten Form verwendet wird oder ein generisches Netzwerk. Im ersten Fall kann die Form des Netzwerks beim Entwurf des Parallelprogramms berücksichtigt werden, um optimale Rechengeschwindigkeiten zu erreichen; bekannte Formen von Netzwerken sind das lineare Netzwerk (in Reihe geschaltete Prozessoren), das Zyklennetzwerk (eine Erweiterung des linearen Netzwerks, in dem ein Kreis gebildet wird) und der Taurus (ein Quadrat von Prozessoren, in dem jeder Prozessor verbunden ist). zu Nachbarn links, oben rechts und unten). Im zweiten Fall handelt es sich häufig um Netzwerke, deren Zusammensetzung nicht speziell für eine Aufgabe bestimmt ist, wie z LAN, WAN wenn es Internet (sehen Verteiltes Rechnen und Grid-Computing).

Erinnerungen

Auch bei der Verwendung des Speichers ist eine Variation möglich. Insbesondere stellt sich die Frage, ob sich alle Unterprogramme im verteilten Programm Speicher teilen oder ob jedes Unterprogramm (oder Prozessor) seinen eigenen Speicher hat. Dies betrifft hauptsächlich die Verwendung von Synchronisationsmechanismen: Semaphoren B. bei gemeinsam genutztem Speicher nützlicher sind, Blockieren von Kanälen bei individuellem Speicher einfacher.

Natürlich können auch Variationen von Prozessoren und Speichern kombiniert werden: beispielsweise vier Prozessoren für einen Speicher und mehrere solcher Blöcke. Siehe auch SIMD, MIMD.

Variationen in der Software

Auch bei der Softwareimplementierung des verteilten Programms sind viele Variationen aufgetreten, sowohl auf der höheren Ebene der Programmarchitektur als auch auf der unteren Ebene der Organisation von Unterprogrammen.

Architekturen

Im Allgemeinen gibt es drei Architekturen innerhalb verteilter Programme:

• Das Programm ist ein großes Programm, das intern mehrere Unterprogramme verwendet – das sind heute die meisten der bekannten Desktop-Programme wie such Textverarbeitungen und Tabellenkalkulationen: Programme, die eine klare Hauptaufgabe auf einem einzelnen Computer haben, aber Unterprogramme verwenden, um beispielsweise eine reaktionsschnellere Oberfläche zu erreichen.
• Das System besteht aus in sich geschlossenen Unterprogrammen - diese Architektur ist geeigneter, mehrere Prozessoren zu verwenden als die vorherige; es ist nicht notwendig, dass alle Unterprogramme gleich sind und nur unterschiedliche Daten verarbeiten, aber es ist üblich. Diese Kategorie umfasst: Peer-to-Peer-Programm, Programme wie SETI@Home und andere Grid-Computing-Implementierungen.
• Client-Server-Architektur - eine Architektur, bei der einige Programme andere Programme bitten, Arbeit für sie zu erledigen. Diese Architektur ist die Grundlage des heutigen Internets mit beispielsweise dem Netz, wo Browser Seiten von anderen Computern anfordern. Anders als bei der bisherigen Architektur gibt es hier eindeutig eine Hierarchie von „Chef“ und „Mitarbeiter“.

Prozesse und Threads

Auch auf einer niedrigeren Ebene sind Unterschiede bei der genauen Implementierung verteilter Programme aufgetreten. Bekannte Begriffe sind hier Prozesse und Threads (siehe auch Multitasking).

Die Verwendung von Prozessen ist bekannt als Mehrfachverarbeitung (wobei jedes Unterprogramm vom Betriebssystem als vollwertiges Programm mit eigenem Speicherblock und anderen Ressourcen angesehen wird). Bei Verwendung von Multiprocessing ist es möglich, jedem Unterprogramm die Flexibilität zu verleihen, die auch ein Vollprogramm besitzt. Dies ist jedoch eine schwere Belastung für ein System.

Die Verwendung von Fäden heißt Multithreading. Ein Thread ist eine Art "Unterprozess", der auf den Ressourcen und einem Teil des Speichers eines normalen Prozesses ausgeführt wird – wobei es möglich ist, mehrere Threads zu einem Prozess zu verbinden. Dadurch wird das System deutlich entlastet, allerdings ist ein Thread in Bezug auf den Zugriff auf das System weniger flexibel als ein vollwertiger Prozess. Es kommt jedoch oft genug vor, dass ein paralleles Programm keinen schweren Systemzugriff benötigt und somit problemlos Threads statt Prozesse verarbeiten kann.

Siehe auch

• Das Problem des Philosophen

Externe Links

• Das Transputer-Archiv—Informationen über Transputer, ein bekannter Computertyp, der für parallele Programme optimiert ist
• Das Occam-Archiv—Informationen über die Occam-Sprache, die speziell für die Erstellung paralleler Programme gedacht ist
• Orakel—Die offizielle Website von Oracle, den Herstellern der Java-Sprache mit integriertem Multithreading

Quellen

• ISO/IEC-Standard 9945-1: 1996: Die POSIX-Gewinde standard, eine Standard-Multithreading-Bibliothek.
• ISO/IEC 9945-1:2002 und ISO/IEC 9945-2:2002 : Der POSIX-Standard, in dem unter anderem eine Multiprocessing-Bibliothek definiert ist.