Übung 6 - Parallel Lua / CSP Tutorial - Nachrichtenbasierte Kommunizierende Prozesse

Inhalt.

Übung 6 - Parallel Lua / CSP Tutorial - Nachrichtenbasierte Kommunizierende Prozesse

Vorbereitung und Verwendung

Channel

Der Alt Prozesskonstruktor

Kommunizierende Prozesse

Vorbereitung und Verwendung

Minimalanforderungen: lvm 1.1.18, luv 2.7.5

Es wird die parallele LuaJit VM lvm mit integrierten CSP Modul für das jeweilige eigene Betriebssystem benötigt
- Momentan steht lvm für die Betriebssysteme Linux 32bit, Linux 64bit, Solaris 32bit, Windows 32bit und MacOS X 64bit zur Verfügung. Unter Microsoft Windows kann es zu funktionalen Abweichungen und Einschränkungen von lvm kommen → lvm, die aber für die Übung nicht relevant sind.
- 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

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
- Ein Neustart des lvm 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!

Der Programmcode kann in dem oberen Teilfenster eines Snippets verändert werden.
Der Programmcode wird ausgefü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 ◼.

Ein Beispiel

function foo(x)
  return x+math.random()
end
print(foo(2))

▸

◼

✗

↻

≡

Channel

Der Kommuniaktionskanal wurde bereits eingeführt. Hier noch einmal die Zusammenfassung:

Ein Channel ist entweder ein FIFO Speicher (Puffer/Queue, N Zellen) oder ein Redezvouz Kontakt (N=0)
Es gibt zwei Operatione
- Lesen (Read)
- Schreiben (Write)
Als Queue gibt es zwei Synchronisationsereignisse die zur Blockierung des aufrufenden Prozesses führen kann:
- Keine Daten im Puffer (Empty) ⇒ Read Sync
- Kein freier Platz m Puffer für neue Daten (Full) ⇒ Write Sync

Ein Beispiel: Verwendung eines Chennels in Par Prozessen

require "Csp"
local ch = Channel(1)
Par({
  function ()
    local x = ch:read()
    print("Consumed "..x)
  end,
  function ()
    local x = "Data"
    print("Producing "..x)
    ch:write(x)
  end
},{
  ch=ch
})

▸

◼

✗

↻

≡

Aufgabe 1. 1. Füge eine Zeitmessung ein indem die log Funktion verwendet wird (anstelle print), sowohl vor als auch nach den Kanaloperationen. Füge vor dem Lesen aus dem Kanal eine Verzögerung sleep(100) ein. Wie ist das zeitliche Verhalten? 2. Was passiert wenn der Kanal mit n=0 (kein Puffer) erzeugt wird?

Lösung.

LS0gMS4gV3JpdGUgd2lyZCBuaWNodCBibG9ja2llcnQgdW5kIGRlciBQcm96ZXNzIDIgYXJiZWl0ZXQgdW5hYmjDpG5naWcgdm9uIFByb3plc3MgMQotLSAgICBELmguIChQMSAvLyBQMikgCi0tIDIuIFdyaXRlIHVuZCBSZWFkIHNpbmQgZ2Vrb3BwZWx0LCB1bmQgKFAxIHx8IFAyKSwgV3JpdGUgd2lyZCB2ZXJ6w7ZnZXJ0IApyZXF1aXJlICJDc3AiCmxvY2FsIGNoID0gQ2hhbm5lbCgxKQpsb2NhbCBjaCA9IENoYW5uZWwoMCkgIC0tIDIuClBhcih7CiAgZnVuY3Rpb24gKCkKICAgIHNsZWVwKDEwMCkKICAgIGxvZygiQmVmb3JlIFJlYWQiKQogICAgbG9jYWwgeCA9IGNoOnJlYWQoKQogICAgbG9nKCJDb25zdW1lZCAiLi54KQogIGVuZCwKICBmdW5jdGlvbiAoKQogICAgbG9jYWwgeCA9ICJEYXRhIgogICAgbG9nKCJQcm9kdWNpbmcgIi4ueCkKICAgIGNoOndyaXRlKHgpCiAgICBsb2coIkFmdGVyIFdyaXRlIikKICBlbmQKfSx7CiAgY2g9Y2gKfSk=

Der Alt Prozesskonstruktor

Der Alt Prozesskonstruktor implemtiert einen mutualen Ausschluss auf möglicherweise parallelen Ereignissen, und führt eine Auswahl und Sequenzialisierung ein. So kann mit einem Alt Prozesse parallel auf das Eintreten von Ereignissen gewartet werden, prominent das Warten auf Daten in mehreren Kanälen.

Ein Alt Prozesskonstruktor muss immer in einen Par Prozess eingebettet werden (oder Fork oder Co), ansonsten entsteht eine permanente Blockierung des aufrufenden Prozesses (Deadlock!)
Ein Alt Prozesse besteht aus Teilprozessen mit konditionalen Vor- und Nachprozessen
Kompakte Version: Der Vorprozess ist immer die erste Anweisung, der Nachprozess alle folgenden Anweisungen.
Derzeit wird nur das Lesen aus einem Channel als konditionaler Vorprozess unterstützt.

Ein Beispiel: Verwendung eines Alt Prozesses in Par Prozessen

require "Csp"
print('Before Par...')
local ch1 = Channel(1)
local ch2 = Channel(1)
local ch3 = Channel(1)
Par({
  function ()
    print('Before Alt..')
    Alt({
      function ()
        local x = ch1:read()
        print(x)
      end,
      function ()
        local x = ch2:read()
        print(x)  
      end,
      function ()
        local x = ch3:read()
        print(x)  
      end  
    })
    print('After Alt..')
  end,
  function (id)
    print('Master ..')
    ch1:write('A')
  end
},{
  ch1=ch1,
  ch2=ch2,
  ch3=ch3
})
print('After Par...')

▸

◼

✗

↻

≡

Aufgabe. Welcher Wert wird ausgegeben? Was passiert wenn vor dem Alt Operator ein Wert in den Channel 2 geschrieben wird (also ch2:write("B"), fügre ein sleep(100) vor dem Alt Operator ein)?

Lösung.

Kommunizierende Prozesse

In dieser Aufgabe sollen mehrere Prozesse mit einem Verwaltungsprozess kommunizieren. Der Verwaltungsprozess verwaltet und verteilte geteilte Ressourcen ohne Deadlock Gefahr. Ein Beispiel ist nachfolgend die Implementierung eines Semaphor durch einen Prozess. Die anderen Prozesse fragen die Ressource über Kommunikationskanäle an, und bekommen die Antwort über einen Kommunikationskanal. Es gibt zwei Kanäle pro Prozess und Ressource:

Anfrage (Request)
Antwort (Reply)

#semchann

Die Dinierenden Philosophen sind der Klassiker um Deadlock Szenarien und das randomisierte Verhalten von parallelen Systemen zu demonstrierem.

require('Csp')
local s = {Semaphore(1),Semaphore(1),Semaphore(1)}
local b = Barrier(3)
local function eat(id)
  print('Eating '..id)
end
local function think(id)
  print('thinking '..id)
end
Par({
  function () b:await(); for i = 1,10 do
    s[1]:down(); s[2]:down(); eat(1); s[2]:up(); s[1]:up(); think(1) 
  end end,
  function () b:await(); for i = 1,10 do
    s[2]:down(); s[3]:down(); eat(2); s[3]:up(); s[2]:up(); think(2) 
  end end,
  function () b:await(); for i = 1,10 do
    s[3]:down(); s[1]:down(); eat(3); s[1]:up(); s[3]:up(); think(3)
  end end
})
print('Done.')

Aufgabe. Implementiere die Dinierenden Philosophen mit einem zentralen Verwaltungsprozess der die N Gabeln verwaltet. Die Anfrage von Gabeln erfolgt über Kommunikationskanäle. Der Alt Prozesskonstruktor muss vom Verwaltungsprozess verwendet werden um auf allen Anfragekanälen Nachrichten empfangen zu können.

Implementierung der Dinierenden Philosophen ohne Deadlock mittels Alt, Par, und Kommunikationskanälen für Anfrage und Bestätigung von Ressourcen (hier die Gabeln)

-- Nicht fertig und vollstaendig!
local ch_p1_req = Channel(1)
local ch_p1_rep = Channel(1)
local ch_p2_req = Channel(1)
local ch_p2_rep = Channel(1)
local ch_p3_req = Channel(1)
local ch_p3_rep = Channel(1)
Par({
  function () 
    -- Philo 1
    for i=1,10 do
      req1:write({request={3,1}})
      local status = rep1:read()
      if status == 0 then continue end
      -- eat
      req1:write({back={3,1}})
      rep1:read()
    end
  end,
  function () 
    -- Philo 2
    for i=1,10 do
      req2:write({request={1,2}})
      local status = rep2:read()
      if status == 0 then continue end
      -- eat
      req2:write({back={1,2}})
      rep2:read()
    end
  end,
  function () 
    -- Philo 3
    for i=1,10 do
      req3:write({request={2,3}})
      local status = rep3:read()
      if status == 0 then continue end
      -- eat
      req3:write({back={2,3}})
      rep3:read()
    end
  end,
  function ()
    -- Verwaltung
    local used = { 0,0,0,0 }
    local msg,rep
    while true do
      Alt({
        function ()
          local x = req1:read()
          print(x)
          msg = x
          rep = rep1
        end,
        function ()
          local x = req2:read()
          print(x)
          req=x
          client=2
        end,      
        function ()
          local x = req3:read()
          print(x)
          req=x
          client=3
        end   
      })
      if msg.request ~= nil then
        if used[msg.request[1]]==0 and
           used[msg.request[2]]==0 then
           rep:write(2)
        else
          rep:write(0)
        end
      else -- back
        used[msg.back[1]]=0
        used[msg.back[2]]=0
      end
    end
  end
},{
  req1 = ch_p1_req,
  req2 = ch_p2_req,
  req3 = ch_p3_req,
  rep1 = ch_p1_rep,
  rep2 = ch_p2_req,
  rep3 = ch_p3_req
})

▸

◼

✗

↻

≡

Lösung.

PGI+bG9jYWw8L2I+IGNoX3AxX3JlcSA9IENoYW5uZWwoMSkKPGI+bG9jYWw8L2I+IGNoX3AxX3JlcCA9IENoYW5uZWwoMSkKUGFyKHsKICA8Yj5mdW5jdGlvbjwvYj4gKCkgCiAgICAtLSBQaGlsbyAxCiAgZW5kLAogIDxiPmZ1bmN0aW9uPC9iPiAoKSAKICAgIC0tIFBoaWxvIDIKICBlbmQsCiAgLS0gLi4uLgogIDxiPmZ1bmN0aW9uPC9iPiAoKQogICAgLS0gVmVyd2FsdHVuZwogICAgQWx0KHsKCiAgICB9KQogIDxiPmVuZDwvYj4KfSx7Cgp9KQ==

Frage 4. Wie müssen die Gabeln angefragt werden damit kein Deadlock auftreten kann? Können die Gabeln sequenziell nacheinander angefragt werden? Wo wird Atomarität verletzt (siehe auch Test & Set Probleme).

Lösung.

Paarweise - es gibt aber keine operationale Unterstützung dafür; ggfs. Verwendung eines globalen Mutex Locks (Schutz aller Gabeln) oder paarweise Lock (Schutz eines Paares)
Die Atomarität wird bei der Sequenz down-down verletzt. Selbst wenn man voher die Verfügbarkeit testet ist der Zugriff danach nicht mehr garantiert. Aber es gibt sems-try-down Operationen die wengistens bei verlorenen Wettbewerb nicht blockieren (und wenn schon erfolgt kann die erste ressource wieder freigegeben werden.

Hilfe

Einreichung (Assignment #2025-90824 )

Prüfen

Bewerten (Lehrer)

Created by the NoteBook Compiler Ver. 1.36.4 (c) Dr. Stefan Bosse (Tue Jul 08 2025 17:16:30 GMT+0200 (Central European Summer Time))