[JS]
[DE]
[PLUGIN] ../../build/popup.plugin
[PLUGIN] ../../build/lvm.plugin
[PLUGIN] ../../build/file.plugin
[TITLE] Parallel LUA / CSP
[AUTHOR] Stefan Bosse
[VERSION] 6.2020

# Parallel Lua / Csp Tutorial (Teil 1)

## Vorbereitung

- Es wird die parallele LuaJit VM *lvm* für das jeweilige eigene Betriebssystem benötigt
  + Momentan steht *lvm* für die Betriebssysteme *Linux 32bit*, *Linux 64bit*, *Solaris 32bit*, und *Windows 32bit* zur Verfügung. Da Microsoft Windows zu keinem guten Informatikkonzept kompatibel ist kann es dort zu funktionalen Abweichungen und Einschränkungen von *lvm* kommen → [lvm](http://edu-9.de/Lehre/vpp2k)
  + Lua/Csp Programme können direkt von der Konsole ausgeführt werden:
```
# lvm myprog.lua
```
  + Die Programme (oder Teile davon) können ebenso in diesem Notebook ausgeführt werden wenn *lvm* mit einem WEB Shell Wrapper gestartet wird (lokaler Rechner, Konsole):
```
# lvm weblvm.lua
Service thread 2 started.
[2@1592562880] HTTP server (2) listening to http://0.0.0.0:4610
Monitor thread 4 started.
[4@1592562880] HTTP server (4) listening to http://0.0.0.0:4611
```
  + Diese Variante erlaubt das schrittweise Erlernen von Lua/Csp. 
  + Alle Code Snippets in diesem Notebook haben dann den gleichen Ausführungskontext (d.h. globale Variablen und Funktionen können von den einzelnen Snippets geteilt werden!)
  + Dieser geteilte Kontext kann aber auch zu Problemen führen und bei Fehlern in parallelen Prozessen können Geisterprozesse übrig bleiben die nicht beendet werden können (ich arbeite daran dass das nicht eintritt und alle gestarten parallelen Prozesse == Threads abbrechbar sind)
  + **Ein Neustart des WEB Wrappers kann daher hin und wieder notwendig werden!**. Das Notebook muss dann nicht neu geladen werden und funktioniert sofort nach dem Neustart von *lvm* wieder. Nur der globale VM Kontext ist wieder "leer"!
  + Die Konsolenausgabe (mittels der *print* Anweisung) bei der Ausführung eines Programabschnitts wird automatisch weitergeleitet und hier angezeigt. Es kann aber nach einer gewissen Zeit erforderlich werden diese automatische Ausgabeweiterleitung wieder durch Drücken des Refresh Buttons anzustoßen (rechts an der *jeweiligen* Ausgabekonsole hier im Notebook) 
  + Jedes Codesnippet hat seine eigene Ausgabekonsole!
  
> Leider kann unter seltenen Bedingungen (Race conditions!) *lvm* fehlerhaft arbeiten und "abstürzen" → Auch ich als Autor von *lvm* habe mit den Tücken von parallelen und konkurrierenden Softwaresystem zu kämpfen!

## Lua Code Ausführen

1. Der Programmcode kann in dem oberen Teilfenster eines Snippets verändert werden.
2. Der Programmcode wird ausgfeührt durch Drücken der Playtaste ▸ im unteren Teilfenster (Ausgabekonsole).
3. Die Ausgabekonsole kann auf der rechten Seite gelöscht werden durch Drücken von ✗.
4. Hin und wieder kann eine Aktualisierung des Ausgabefensters durch Drücken des Knopfes ↻ erforderlich sein.
5. Bei parallelen Prozessen werden jeweils neue VM Instanzen in Threads gestartet. Wenn etwas schief läuft kann das Programm hängen und nicht terminieren (also der aktuelle Codeabschnitt). Der Abbruch kann versucht werden durch Drücken des Knopfes ◼.

[LVM] Eine einfache Textausgabe (1)
```lua
print(math.random())
```

## Prozesse

### Sequenzielle Prozesse

- Sequenzielle Prozesse werden in dem gleichen Thread und der gleichen Coroutine ausgeführt.
- Ein Scheduling ist nicht möglich, aber Blockierung!

[LVM] Eine einfache Textausgabe (2)
```lua
require 'Csp';
Seq({
  function () 
    print('Hello '..word)
  end,
  function ()
    print('Thank '..word)
  end
},{
  word='shared'
})
print('After Seq..')
```

[EXERCISE]
1. Füge in die beiden obigen seq. Prozesse die *sleep(millisec)* Funktion vor der Konsolenausgabe *print* ein (wähle für die verzögerung Werte im Bereich 100-500 ms)
2. Wie verhält sich das Programm? Füge die Ausgabe der Prozesszeit ein (`print(time())`)  vor und nach dem *sleep* Aufruf. Alternativ kann anstelle der *print* die *log* Anweisung verwendet werden. Diese gibt die aktuelle Prozesszeit in Millisekunden zusammen mit den Argumenten aus.
3. Was passiert wenn in einem Prozess ein Fehler auftritt? Also füge z.B. den Aufruf einer nicht definierten Funktion `foo(1)` ein...
[EXERCISE]

### Fehlerbehanldung

- Die Fehlerbehandlung (genau genommen die Behandlung von Excceptions und Signalen) erfolgt in einem sequenziellen Programm mit der `try .. catch (e) .. end` Anweisung (deterministisch)

- Die Fehlerbehandlung in parallelen Systemen ist nicht ohne weiteres möglich!

- Alle Prozesskonstruktoren werden dann mit einem Fehlersignal "EPROC" abgebrochen:

[LVM] Fehlerbehandlung
```lua
require 'Csp';
try 
  Seq({
    function () 
      print('Hello '..word)
    end,
    function ()
      foo(1)
      print('Thank '..word)
    end
  },{
    word='shared'
  })
catch (e)
  print "Caught exception:"
  print(e)
end
```

- Häufig ist bei der Fehlersuche der genaue Ort und eine Funktionsaufrufspur (trace) erforderlich. Diese Ausgabe kann durch die Option `debug=true` erreicht werden:

[LVM] Fehlerbehandlung
```lua
require 'Csp';
try 
  Seq({
    function () 
      print('Hello '..word)
    end,
    function ()
      foo(1)
      print('Thank '..word)
    end
  },{
    word='shared',
    debug=true,
  })
catch (e)
  print "Caught exception:"
  print(e)
end
```

### Parallele Prozesse

- Die verwendung des *Par* Konstruktors erzeugt echte parallele Prozesse.
- Parallele Prozesse können nur über definierte IPC Objekete wie Channels kommunizieren
- Variablen können von parallelen Proezsse "geteilt" werden, aber nur als Kopie
- Gemeinsam geteilte Objekte, Variablen und Funktionen müssen nach der Prozessfunktionsliste als Tabelle übergeben werden

[LVM] Eine einfache Textausgabe mit Prozesskommunikation (2)
```lua
require 'Csp';
log('Creating Par..')
Par({
  function () 
    local word = ch:read();
    log('Hello '..name..' '..word)
  end,
  function ()
    ch:write('World');
    log('Thank '..name)
  end
},{
  ch=Channel(1),
  name='Joe',
})
log('After Par ..')
```

### Kommunikationskanäle

- Ein Channel wird zwischen mindestens zwei Prozessen verwendet um synchronisiert Daten auszutauschen

- Ein Channel wird mit dem Konstruktor *Channel(n)* erzeugt. Die Puffergröße *n* gibt die maximale Anzahl zwischengespeicherter Daten an.

- Ein Channel mit *n*=0 kann nur von zwei Prozessen (einem Leser und einem Schreiber) verwendet werden → Rendezvous Protokoll

- Es gibt zwei Operationen: *channel:write(data)* und *channel:read()*

[EXERCISE]
1. Was läuft bei dem nächsten Beispiel falsch?
   + Hinweis: Wenn der *Par* Prozess nicht terminiert, benutze den ◼ Knopf bis die Meldung mit dem Signal *EPROC* erscheint!
2. Ändere das Programm so ab dass sich beide Prozesse richtig synchronisieren und der *Par* prozess terminiert.
[EXERCISE]

[LVM] Eine komplexere Textausgabe mit Prozesskommunikation (3)
```lua
require 'Csp';
log('Creating Par..')
Par({
  function () 
    local word = ch:read();
    log('Hello '..name..' '..word)
    ch:write('You')
  end,
  function ()
    ch:write('World');
    local word = ch:read();
    log('Thank '..name..' '..word)
  end
},{
  ch=Channel(1),
  name='Joe',
})
log('After Par ..')
```

### Semaphoren

- Das wichtigste Kommunikationsobjekt für Prozesse ist die Semaphore als ein geschützer Zähler

- Eine Semaphore wird für Produzenten-Konsumenten Systemen und für die Koordination eingesetzt

- Eine Semaphore wird mit dem Konstruktor *Semaphore(init)* erzeugt. Der Startwert gibt den initialen Zählerwert an → die richtige Wahl ist relevant und bestimmt die Anwendung!

- Es gibt zwei Operationen: *semaphore:up()* und *semaphore:down()*
  + Die Downoperation kann den Aufrufer blockieren wenn die Semaphoreninvariante verletzt wird
  
- Semaphoreinvariante (darf zu keinem Zeitpunkt verletzt werden):

$
sem_{counter} = init + \sum sem:up - \sum sem:down \ge 0
$

[LVM] Ein einfaches Produzenten-Konsumenten System
```lua
require 'Csp';
log('Creating Par..')
Par({
  function ()
    -- Der Master
    -- Distribute
    log('Master: Distributing..')
    for i=1,2 do prod:up() end
    -- Join
    log('Master: Collecting..')
    for i=1,2 do cons:down() end
    log('Master: Done.')
  end,
  function ()
    -- Worker 1
    prod:down()
    log('Worker 1: processing..')
    sleep(500)
    cons:up()
    log('Worker 1: Done.')
  end,
  function ()
    -- Worker 2
    prod:down()
    log('Worker 2: processing..')
    sleep(500)
    cons:up()
    log('Worker 2: Done.')
  end
},{
  prod=Semaphore(0),
  cons=Semaphore(0)
})
log('After Par ..')
```

[QUESTION]
Wie ist der zeitliche Ablauf?

[INPUT]

[QUESTION]
Welchen Wert haben die Semaphorenzähler von *prod* und *cons* am Ende?

[INPUT]

## Aufgabe

### Dinierende Philosophen

- Dinierende Philosophen ist ein paralleles System welches Semaphoren benutzt um physische Ressourcen abzubilden.
  + Es gibt N Philosophen (N ungradzahlig)
  + Jeder Philosoph kann sich in zwei Zuständen befinden: "Essend" oder "denkend"!
  + Um in den Zustand "Essend" zugelangen benötigt der Philosoph *i* zwei Gabeln *S*~i~ und *S*~i+1~. 
  + Jede Gabel wird durch eine binäre Semaphore repräsentiert
  + Die Philosophen und Gabeln stellen einen Ring dar, d.h. der letzte Philosopg *N* benötigt die letzte und erste Gabel.
  + Das DP Problem dient als klassisches Deadlock Problem und das Auftreten von Race Conditions (Wettrennen zwischen Threads)
  
[LVM] Zwei dinierende Philosopgen - der Auftakt!
```lua
require 'Csp';
log('Creating Par..')
Par({
  function ()
    log(1)
    sync:await()
    -- sleep(math.floor(math.random()*10))
    log('1: Thinking')
    fork1:down()
    -- yield()
    fork2:down()
    log('1: Eating')
    fork1:up()
    fork2:up()    
  end,
  function ()
    log(2)
    sync:await()
    -- sleep(math.floor(math.random()*10))
    log('2: Thinking')
    fork2:down()
    -- yield()
    fork1:down()
    log('2: Eating')
    fork2:up()
    fork1:up()    
  end
},{
  sync=Barrier(2),
  fork1=Semaphore(1),
  fork2=Semaphore(1)
})
log('After Par ..')
```
 
- Die Barriere dient hier nur für einen synchronisierten Start der Philosophenprozesse

[EXERCISE]
1. Starte eine Reihe (10) von Durchläufen. Ist die Ablaufreihenfolge deterministisch?
1. Führe in jedem Phil.prozess eine Zählschleife ein die den obigen Anweisungblock kapselt (*for*)
2. Experimentiere mit den auskommentierten random dely (*sleep* in Millisekunden) und der Threadwechsel mit *yield*
2. Führe den Prozess aus, mit z.b. M=20 Durchläufen. Was lässt sich beobachten?
3. Erweitere nun das parallele Prozesssystem auf N=5 Phils. Lässt sich ein Deadlock feststellen? Die Versuche müssen ggfs. vielfach wiederholt werden.

[EXERCISE]

[INPUT]

Parallel Lua / Csp Tutorial (Teil 1)

Vorbereitung

Es wird die parallele LuaJit VM lvm für das jeweilige eigene Betriebssystem benötigt
- Momentan steht lvm für die Betriebssysteme Linux 32bit, Linux 64bit, Solaris 32bit, und Windows 32bit zur Verfügung. Da Microsoft Windows zu keinem guten Informatikkonzept kompatibel ist kann es dort zu funktionalen Abweichungen und Einschränkungen von lvm kommen → lvm
- Lua/Csp Programme können direkt von der Konsole ausgeführt werden:
```
# lvm myprog.lua
```
- Die Programme (oder Teile davon) können ebenso in diesem Notebook ausgeführt werden wenn lvm mit einem WEB Shell Wrapper gestartet wird (lokaler Rechner, Konsole):
```
# lvm weblvm.lua
Service thread 2 started.
[2@1592562880] HTTP server (2) listening to http://0.0.0.0:4610
Monitor thread 4 started.
[4@1592562880] HTTP server (4) listening to http://0.0.0.0:4611
```
- Diese Variante erlaubt das schrittweise Erlernen von Lua/Csp.
- Alle Code Snippets in diesem Notebook haben dann den gleichen Ausführungskontext (d.h. globale Variablen und Funktionen können von den einzelnen Snippets geteilt werden!)
- Dieser geteilte Kontext kann aber auch zu Problemen führen und bei Fehlern in parallelen Prozessen können Geisterprozesse übrig bleiben die nicht beendet werden können (ich arbeite daran dass das nicht eintritt und alle gestarten parallelen Prozesse == Threads abbrechbar sind)
- Ein Neustart des WEB Wrappers kann daher hin und wieder notwendig werden!. Das Notebook muss dann nicht neu geladen werden und funktioniert sofort nach dem Neustart von lvm wieder. Nur der globale VM Kontext ist wieder "leer"!
- Die Konsolenausgabe (mittels der print Anweisung) bei der Ausführung eines Programabschnitts wird automatisch weitergeleitet und hier angezeigt. Es kann aber nach einer gewissen Zeit erforderlich werden diese automatische Ausgabeweiterleitung wieder durch Drücken des Refresh Buttons anzustoßen (rechts an der jeweiligen Ausgabekonsole hier im Notebook)
- Jedes Codesnippet hat seine eigene Ausgabekonsole!

Leider kann unter seltenen Bedingungen (Race conditions!) lvm fehlerhaft arbeiten und "abstürzen" → Auch ich als Autor von lvm habe mit den Tücken von parallelen und konkurrierenden Softwaresystem zu kämpfen!

Lua Code Ausführen

Der Programmcode kann in dem oberen Teilfenster eines Snippets verändert werden.
Der Programmcode wird ausgfeührt durch Drücken der Playtaste ▸ im unteren Teilfenster (Ausgabekonsole).
Die Ausgabekonsole kann auf der rechten Seite gelöscht werden durch Drücken von ✗.
Hin und wieder kann eine Aktualisierung des Ausgabefensters durch Drücken des Knopfes ↻ erforderlich sein.
Bei parallelen Prozessen werden jeweils neue VM Instanzen in Threads gestartet. Wenn etwas schief läuft kann das Programm hängen und nicht terminieren (also der aktuelle Codeabschnitt). Der Abbruch kann versucht werden durch Drücken des Knopfes ◼.

Eine einfache Textausgabe (1)

print(math.random())

▸

◼

✗

↻

Prozesse

Sequenzielle Prozesse

Sequenzielle Prozesse werden in dem gleichen Thread und der gleichen Coroutine ausgeführt.
Ein Scheduling ist nicht möglich, aber Blockierung!

Eine einfache Textausgabe (2)

require 'Csp';
Seq({
  function () 
    print('Hello '..word)
  end,
  function ()
    print('Thank '..word)
  end
},{
  word='shared'
})
print('After Seq..')

▸

◼

✗

↻

Aufgabe.

Füge in die beiden obigen seq. Prozesse die sleep(millisec) Funktion vor der Konsolenausgabe print ein (wähle für die verzögerung Werte im Bereich 100-500 ms)
Wie verhält sich das Programm? Füge die Ausgabe der Prozesszeit ein (print(time())) vor und nach dem sleep Aufruf. Alternativ kann anstelle der print die log Anweisung verwendet werden. Diese gibt die aktuelle Prozesszeit in Millisekunden zusammen mit den Argumenten aus.
Was passiert wenn in einem Prozess ein Fehler auftritt? Also füge z.B. den Aufruf einer nicht definierten Funktion foo(1) ein...

Fehlerbehanldung

Die Fehlerbehandlung (genau genommen die Behandlung von Excceptions und Signalen) erfolgt in einem sequenziellen Programm mit der try .. catch (e) .. end Anweisung (deterministisch)
Die Fehlerbehandlung in parallelen Systemen ist nicht ohne weiteres möglich!
Alle Prozesskonstruktoren werden dann mit einem Fehlersignal "EPROC" abgebrochen:

Fehlerbehandlung

require 'Csp';
try 
  Seq({
    function () 
      print('Hello '..word)
    end,
    function ()
      foo(1)
      print('Thank '..word)
    end
  },{
    word='shared'
  })
catch (e)
  print "Caught exception:"
  print(e)
end

▸

◼

✗

↻

Häufig ist bei der Fehlersuche der genaue Ort und eine Funktionsaufrufspur (trace) erforderlich. Diese Ausgabe kann durch die Option debug=true erreicht werden:

Fehlerbehandlung

require 'Csp';
try 
  Seq({
    function () 
      print('Hello '..word)
    end,
    function ()
      foo(1)
      print('Thank '..word)
    end
  },{
    word='shared',
    debug=true,
  })
catch (e)
  print "Caught exception:"
  print(e)
end

▸

◼

✗

↻

Parallele Prozesse

Die verwendung des Par Konstruktors erzeugt echte parallele Prozesse.
Parallele Prozesse können nur über definierte IPC Objekete wie Channels kommunizieren
Variablen können von parallelen Proezsse "geteilt" werden, aber nur als Kopie
Gemeinsam geteilte Objekte, Variablen und Funktionen müssen nach der Prozessfunktionsliste als Tabelle übergeben werden

Eine einfache Textausgabe mit Prozesskommunikation (2)

require 'Csp';
log('Creating Par..')
Par({
  function () 
    local word = ch:read();
    log('Hello '..name..' '..word)
  end,
  function ()
    ch:write('World');
    log('Thank '..name)
  end
},{
  ch=Channel(1),
  name='Joe',
})
log('After Par ..')

▸

◼

✗

↻

Kommunikationskanäle

Ein Channel wird zwischen mindestens zwei Prozessen verwendet um synchronisiert Daten auszutauschen
Ein Channel wird mit dem Konstruktor Channel(n) erzeugt. Die Puffergröße n gibt die maximale Anzahl zwischengespeicherter Daten an.
Ein Channel mit n=0 kann nur von zwei Prozessen (einem Leser und einem Schreiber) verwendet werden → Rendezvous Protokoll
Es gibt zwei Operationen: channel:write(data) und channel:read()

Aufgabe.

Was läuft bei dem nächsten Beispiel falsch?
- Hinweis: Wenn der Par Prozess nicht terminiert, benutze den ◼ Knopf bis die Meldung mit dem Signal EPROC erscheint!
Ändere das Programm so ab dass sich beide Prozesse richtig synchronisieren und der Par prozess terminiert.

Eine komplexere Textausgabe mit Prozesskommunikation (3)

require 'Csp';
log('Creating Par..')
Par({
  function () 
    local word = ch:read();
    log('Hello '..name..' '..word)
    ch:write('You')
  end,
  function ()
    ch:write('World');
    local word = ch:read();
    log('Thank '..name..' '..word)
  end
},{
  ch=Channel(1),
  name='Joe',
})
log('After Par ..')

▸

◼

✗

↻

Semaphoren

Das wichtigste Kommunikationsobjekt für Prozesse ist die Semaphore als ein geschützer Zähler
Eine Semaphore wird für Produzenten-Konsumenten Systemen und für die Koordination eingesetzt
Eine Semaphore wird mit dem Konstruktor Semaphore(init) erzeugt. Der Startwert gibt den initialen Zählerwert an → die richtige Wahl ist relevant und bestimmt die Anwendung!
Es gibt zwei Operationen: semaphore:up() und semaphore:down()
- Die Downoperation kann den Aufrufer blockieren wenn die Semaphoreninvariante verletzt wird
Semaphoreinvariante (darf zu keinem Zeitpunkt verletzt werden):

\[ sem_{counter} = init + \sum sem:up - \sum sem:down \ge 0 \]

Ein einfaches Produzenten-Konsumenten System

require 'Csp';
log('Creating Par..')
Par({
  function ()
    -- Der Master
    -- Distribute
    log('Master: Distributing..')
    for i=1,2 do prod:up() end
    -- Join
    log('Master: Collecting..')
    for i=1,2 do cons:down() end
    log('Master: Done.')
  end,
  function ()
    -- Worker 1
    prod:down()
    log('Worker 1: processing..')
    sleep(500)
    cons:up()
    log('Worker 1: Done.')
  end,
  function ()
    -- Worker 2
    prod:down()
    log('Worker 2: processing..')
    sleep(500)
    cons:up()
    log('Worker 2: Done.')
  end
},{
  prod=Semaphore(0),
  cons=Semaphore(0)
})
log('After Par ..')

▸

◼

✗

↻

Frage. Wie ist der zeitliche Ablauf?

Frage. Welchen Wert haben die Semaphorenzähler von prod und cons am Ende?

Aufgabe

Dinierende Philosophen

Dinierende Philosophen ist ein paralleles System welches Semaphoren benutzt um physische Ressourcen abzubilden.
- Es gibt N Philosophen (N ungradzahlig)
- Jeder Philosoph kann sich in zwei Zuständen befinden: "Essend" oder "denkend"!
- Um in den Zustand "Essend" zugelangen benötigt der Philosoph i zwei Gabeln S_i und S_i+1.
- Jede Gabel wird durch eine binäre Semaphore repräsentiert
- Die Philosophen und Gabeln stellen einen Ring dar, d.h. der letzte Philosopg N benötigt die letzte und erste Gabel.
- Das DP Problem dient als klassisches Deadlock Problem und das Auftreten von Race Conditions (Wettrennen zwischen Threads)

Zwei dinierende Philosopgen - der Auftakt!

require 'Csp';
log('Creating Par..')
Par({
  function ()
    log(1)
    sync:await()
    -- sleep(math.floor(math.random()*10))
    log('1: Thinking')
    fork1:down()
    -- yield()
    fork2:down()
    log('1: Eating')
    fork1:up()
    fork2:up()    
  end,
  function ()
    log(2)
    sync:await()
    -- sleep(math.floor(math.random()*10))
    log('2: Thinking')
    fork2:down()
    -- yield()
    fork1:down()
    log('2: Eating')
    fork2:up()
    fork1:up()    
  end
},{
  sync=Barrier(2),
  fork1=Semaphore(1),
  fork2=Semaphore(1)
})
log('After Par ..')

▸

◼

✗

↻

Die Barriere dient hier nur für einen synchronisierten Start der Philosophenprozesse

Aufgabe.

Starte eine Reihe (10) von Durchläufen. Ist die Ablaufreihenfolge deterministisch?
Führe in jedem Phil.prozess eine Zählschleife ein die den obigen Anweisungblock kapselt (for)
Experimentiere mit den auskommentierten random dely (sleep in Millisekunden) und der Threadwechsel mit yield
Führe den Prozess aus, mit z.b. M=20 Durchläufen. Was lässt sich beobachten?
Erweitere nun das parallele Prozesssystem auf N=5 Phils. Lässt sich ein Deadlock feststellen? Die Versuche müssen ggfs. vielfach wiederholt werden.

Created by the NoteBook Compiler Ver. 1.3.9 (c) Dr. Stefan Bosse (Fri Jul 31 2020 09:52:50 GMT+0200 (CET))