Verteilte und Parallele Programmierung

PD Stefan Bosse

Universität Bremen, FB Mathematik & Informatik

SS 2020
Version 2020-06-10

sbosse@uni-bremen.de

Parallele Programmierung

Überblick

Lua :: Daten und Variablen

Variablen werden mit dem Schlüsselwort local definiert → Erzeugung eines Datencontainers!
Es gibt keine Typendeklaration in Lua! Kerntypen:

T_core={number, boolean, table, string, function}
Alle Variablen sind polymorph und können alle Werttypen aufnehmen (auch dynamisch wechselnd zur Laufzeit).
Bei der Variabledefinition kann ein Ausdruckswert zugewiesen werden

local v = ε,..;  v = ε;

Lua :: Funktionen

Funktionen können mit einem Namen oder anonym definiert werden
Funktionen sind Werte 1. Ordnung → Funktionen können Variablen oder Funktionsargumenten zugewiesen werden
Eine Funktion kann einen Wert mit der return Anweisung zurückgeben. Ohne explizite Wertrückgabe → undefined
Es wird nur Call-by-value Aufruf unterstützt - jedoch werden Objekte, Funktionen und Arrays als Referenz übergeben; Parameter p_i sind an Funktionsblock gebunden

function name (p₁,p₂,..) statements ; return ε end ⇒ name(ε₁,ε₂,..)

Lua :: Funktionen

Da in JavaScript Funktionen Werte erster Ordnung sind können
- Funktionen an Funktionen übergeben werden und
- Funktionen neue Funktionen zurückgeben (als Ergebnis mit return)
Es können daher anonyme Funktionen function (..) {..} definiert werden die entweder einer Variablen als Wert oder als Funktionsargument übergeben werden.

local x = function (p_i) ε(p_i) end
array.forEach(function(elem,index) ε(p_i) end

Lua :: Datenstrukturen

In Lua sind Objekte universelle Datenstrukturen (sowohl Datenstrukturen als auch Objekte) die mit Hashtabellen implementiert werden. Arrays werden in Lua ebenfalls als Hashtabelle implementiert!. D.h. Objekte == Datenstrukturen == Arrays == Hashtabellen.

Es gibt kein nutzerdefinierbares Typensystem in Lua.
Eine Datenstruktur kann jederzeit definiert und verändert werden (d.h. Attribute hinzugefügt werden)

local dataobject = {
  a=ε,
  b=ε, ..
  f=function () { .. }
}
..
dataobject.c = ε

Lua :: Datenstrukturen

Dadurch dass Objekte und Arrays mit Hashtabellen implementiert (d.h. Elemente werden durch eine Textzeichenkette referenziert) werden gibt es verschiedene Möglichkeiten auf Datenstrukturen und Objektattribute zuzugreifen:

dataobject.attribute
dataobject["attribute"]
array[index]
array["attribute"]

Lua :: Objekte

Objekte zeichnen sich in der objektorientierten Programmierung durch Methoden aus mit der ein Zugriff auf die privaten Daten (Variablen) eines Objekts möglich wird.
In Lua kann auf Variablen eines Objekts (die Attribute) immer direkt zugegriffen werden.
Attribute können Funktionen sein - jedoch können die Funktionen nicht wie Methoden direkt auf die Daten des Objektes zugreifen.
Daher definiert man Methoden über Prototypenerweiterung in Lua.
Die Methoden können über die self Variable direkt auf das zugehörige Objekt zugreifen (also auch auf die Variablen/Attribute)
Es gibt eine Konstruktionsfunktion für solche Objekte mit Prototypendefinition der Methoden
Objekte werden mit dem new Operation durch die Konstruktionsfunktion erzeugt.

Lua :: Objekte

constructor=class()
function constructor:init (p_i)
  self.x=ε
  ..
end
function constructor:method_i (..) {
  self.x=ε;
  ..
}
...
 
local obj =  constructor:new(..);

Lua :: Objekte

Lua - Ausführungsmodelle

Prozesse

Isolierte Programmprozesse ohne direkte Synchronisation und Dateaustausch zwischen den VMs
Synchronsiation nur über
- Dateien
- Sockets (lokal, TCP, UDP)
- Pipes (Streams)
Jeder Prozess führt eine VM aus

Lua - Ausführungsmodelle

Threads

Es werden parallele Prozesse auf Threads abgebildet die bestenfalls 1:1 auf den CPUs / Cores ausgeführt werden, ansonsten durch einen Scheduler im Zeitmultiplexverfahren ausgeführt werden
Prozesse können synchronisiert auf geteilte Objekte (konkurrierend) zugreifen:
- Channel
- Semaphore, Mutex
- Event, Timer
- Shared Memory Store
Prozessblockierung blockiert den gesamten Thread (somit auch alle Fibers)
Jeder parallele Prozess in einem Thread läuft in eigener VM Instanz
Daten können nicht zwischen VMs ausgetauscht werden (Automatsisches Speichermanagement und GC) → nur Austtausch über Serialisierung und Kopie von Daten!

Lua - Ausführungsmodelle

Fibers und Coroutinen

Es werden pseudo-parallele Prozesse (Coroutinen) auf Fibers abgebildet die grundsätzlich nicht parallel aber durch einen Scheduler im Zeitmultiplexverfahren ausgeführt werden.
Diese Prozesse können synchronisiert auf geteilte Objekte (nicht konkurrierend) zugreifen:
- Channel
- Semaphore
- Event, Timer
Prozessblockierung blockiert nur einen Fiber
Alle parallelen Prozesse mit Fibers laufen in einer VM Instanz

Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

Neben Thread, Fibers, und Prozessen kann auch die Parallelisierung von Ein- und Ausgabeoperation genutzt werden
Asynchrone IO wird sowohl in nodejs (JavaScript) als auch in Lua (lvm) mittels der libuv Bibliothek implementiert
- Verwendung von Callback Funktionen für die Daten- und Ereignisverarbeitung
- Anders als in JavaScript (nodejs) wird asynchrone IO in Lua eher seltener verwendet
Fibers (Coroutinen) werden in Lua direkt durch die Lua VM verarbeitet
Threads werden über die libuv einzelnen VM Instanzen zugeordnet
- Verbindung der Instanzen über libuv
- Jede VM Instanz hat ihre eigene Event Loop!

Lua - Ausführungsmodelle

Lua - Ausführungsmodelle

LVM

Parallel LuaJit Virtual Machine

Serialisierung

Fibers teilen sich eine VM Instanz und können direkt auf geteilte Datenobjekte zugreifen (gleicher Gültigkeistbereich der Daten für alle Fibers)
Threads können keine Daten teilen. Nur Datenkopien können geteilt werden:
- Serialisierung der Lua Daten in Bytecode in einem Thread/Prozess T₁
- Übertragung des entkoppelten Bytecodes an an anderen Thread/Prozess T₂
- Deserialisierung des Bytecodes in Lua Daten in Thread/Prozess T₂
Da Funktionen Werte erster Ordnung sind können auch Funktionen serialisiert werden
- Es müssen aber auch alle Abhängigkeiten (referenzierte andere Funktionen und Daten) serialisiert werden
- Daher auf lokale Funktionen ohne globale/externe Referenzen beschränkt!

Lua :: Csp.lua

Die Csp.lua Bibliothek implementiert das CCSP Multiprozessmodell mittels Multithreading von lvm
Die Bibliothek muss mittels require('Csp') geladen werden

Ausführungsmodell

Prozesse
Threads
Fibers
Anweisungen

Lua :: Csp.lua

Prozesskonstruktoren

Seq({f₁,f₂,..}): Der Seq Konstruktor erzeugt eine sequenzielle Komposition von Prozessen (über einer Array von Funktionen definiert). Da Lua inhärent sequenziell ausgeführt wird ist dies gleichbedeutend mit: f₁();f₂();..
Par({f₁,f₂,..},{shared}): Der Par Konstruktor erzeugt eine parallele Komposition von Prozessen (über einer Array von Funktionen definiert). Alle Subprozesse werden nach Erzeugung automatisch gestartet. Der aufrufende Prozess wird blockiert bis alle Subprozesse terminiert sind. Ein shared environment kann mit geteilten (IPC) Objekten übergeben werden.

Lua :: Csp.lua

Fork({f₁,f₂,..},{shared}): Der Fork Konstruktor erzeugt eine parallele Komposition von Prozessen (über einer Array von Funktionen definiert). Alle Subprozesse werden nach Erzeugung automatisch gestartet. Der aufrufende Prozess wird nicht blockiert! Ein shared environment kann mit geteilten (IPC) Objekten übergeben werden.

Geteilte Ressourcen

Prozesse können sich Ressourcen teilen:
- Interprozesskommunikation (Channel, Semaphore, ..)
- Arrays (Matrizen)
Geteilte Ressourcen müssen explizit erzeugt werden und als zweites Argument an die Prozesskonstruktoren übergeben werden.

Lua :: Csp.lua

Par({
  function process₁ () 
    local x;
    x=ch:read();
    print(x);
  end,
  function process₂ ()
    local x=math.random();
    ch:write(x);
    print(x);
  end
},{
  ch=Channel(1)
})

Lua :: Csp.lua

Fehlerbehandlung

In einem sequenziellen Prozess führt ein nicht behandelter Fehler zum Abbruch dieses Prozesses und wenn es der einzige ist zum Abbruch des Programms (Standard in der Programmierung). Aber:
Wenn ein Teilprozess eines parallelen Metaprozesses einen Fehler verursacht (also ein Ausnahmefehlersignal erzeugt) wird nur die Ausführung dieses Teilprozesses beendet.
- Die anderen Teilprozesse laufen weiter!
- Dieses könnten auf den abgebrochenen Prozess warten.
- Was soll passieren?
Der Par Kosntruktor wartet auf Terminierung aller Teilprozesse. Mittels eines optionalen greedy Arguments kann der Metaprozess auch bei einem Fehler terminieren.
- Die Par Funktion gibt dann einen Fehlerwert zurück (sonst nil)

Lua :: Csp.lua

Weitere Prozesskonstruktoren:

Alt({{f_1,cond,f_1,do},{f_2,cond,f_2,do,..},{shared}): Der Alt Konstruktor erzeugt eine parallele Komposition von Prozessen (über ein Array von Funktionsarrays definiert) von denen aber nur ein blockierter konditionaler Prozess selektiert (aktiviert) wird. Jeder konditionale Prozess kann eine blockierende Operation ausführen. Der erste bereite Prozess wird ausgeführt mit nachfolgender Aktivierung (eines optionalen) do Prozesses. Der aufrufende Prozess wird blockiert bis ein Subprozess terminiert ist.

Alternative Prozesskonstruktoren werden eingesetzt um
- Auf eine Menge von synchronisierenden Kommunikationskanälen selektiv auswählend zugreifen zu können

Lua :: Csp.lua

Par({
  function () 
    Alt({
      function process_1,cond ()
        x=ch1:read();
        print('ch1: hello '..x);
      end,
      function process_2,cond ()
        x=ch2:read();
        print('ch2: hello '..x);
      end,
      ..
    })
  end,
  function () 
    ch2:write('world')
  end,
  {
      ch1=Channel(1), ch2=Channel(1), ..
  })

Lua :: Csp.lua

ParArray: Der ProcessArray Konstruktor erzeugt eine parallele Komposition von einem Array von N Prozessen (über eine einzige Funktion definiert). Alle Subprozesse werden nach Erzeugung automatisch gestartet. Den Prozessen wird beim Start ein Index als Argument übergen. Der aufrufende Prozess wird blockiert wenn wait auf True gesetzt wird (Verhalten wie Par Konstruktor), ansonsten wird er nicht blockiert (Verhalten wie Fork Konstruktor)!

ParArray(function (index) 
  ..
  end,
  N,,
  {shared}
  wait?
)

Lua :: Csp.lua :: IPC

IPC Objekte

Channel(depth): Ein Channel stellt synchronisierten Datenaustausch zwischen Prozessen her. Ein Channel mit depth=0 (oder kein Argument) implementiert das klassische Rendezvous System: Schreiber wird blockiert bis Leser zugreift und umgekehrt. Ansonsten gibt depth die Anzahl der Speicherzellen des FIFOs an. Ein Channel ist polymorph und kann gelesen oder beschrieben werden mit folgenden Operationen:

channel = Channel:new(depth)
x = channel:read()
channel:write(ε)

Semaphore(init): Eine Sempahore stellt Synchronisation in Produzenten-Konsumenten Systemen über einen geschützten Zähler her. Der Startwert init des Zählers muss angegeben werden. Der Zähler kann um eins erhöht oder erniedrigt werden.

Lua :: Csp.lua :: IPC

Es stehen folgende Operationen zur Verfügung:

semaphore = Semaphore:new(init)
semaphore:up()
semaphore:down()

… weitere folgen …

Lua :: Csp.lua :: IPC

Shared Memory

Es stehen zwei verschiedene geteilte Speicherobjekte zur Verfügung:

Matrix(dims:number [],init?:number|function): Eine n-dimensionale Float Matrix die zwischen parallelen Prozessen geteilt werden kann.; Der Zugriff auf die Zellen der Matrix erfolgt mit den Operationen m:read(index₁:number, index₂:number, ..) → number und m:write(val:number,index₁:number, index₂, ..). Es gibt die Möglichkeit die Float Matrix mittels der m:slice(range₁:(number|number []|nil), range₂, ..) Operation in ein (nicht teilbares) natives Array zu wandeln. Der Platzhalter nil wählt den gesamten Indexbereich der jeweiligen Dimension der Matrix aus.
Buffer(size): Ein Byte Buffer (Elementtyp unsigned byte).; Der Zugriff auf die Zellen der Matrix erfolgt mit den Operationen m:read(index:number) → number und m:write(val:number,index:number).

Lua :: Csp.lua :: IPC

Beispiele

local m1 = Matrix({1000,1000},function () return math.random() end);
local m2 = Matrix({1000},function () return math.random() end);
Par({
  function ()
   for i=1,500 do
     for j=1,500 do 
       m1:write(i,j,m1:read(i,j)*m2:read(j));
     end end
  end,
  function ()
   for i=501,1000 do
     for j=501,1000 do 
       m1:write(i,j,m1:read(i,j)*m2:read(i));
     end end
  end
},{
  m1:m1,
  m2:m2
});