PD Stefan Bosse - VPP - Virtuelle Maschinen ::

Virtuelle Maschinen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

Virtualisierung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

Virtualisierung

$${V}:{A}{P}{I}_{{i}}\to{A}{P}{I}_{{o}},\Theta{\left({A}{P}{I}_{{o}}\right)}\gg\Theta{\left({A}{P}{I}_{{i}}\right)}$$

• VM für eingebettete Systeme:
  • Lua (eLua, 32 Bit, 64kB RAM, 256kB ROM, GC, speed-down 1:100)
  • FORTH (Mecrisp, 32 Bit (≥8), 1kB RAM, 16 kB ROM, JIT!, no GC, speed-down 1:10)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

A Computer System Architektur mit verschiedenen Ebenen (Software, Betriebssystem, Hardware) → verschiedene Virtualisierungsebenen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

Virtualisierung

     Java Application                     
           │                              
           │  Java VM jvm (bytecode)      
           ∇                              
       Linux IA32                         
           │                              
           │  VMWARE (x86)                
           ∇                              
      Windows IA32                        
           │                              
           │  Code Morphing (x86 ──▶ Risc)
           ∇                              
      Crusoe VLIW                         

Drei Ebenen von VMs. Eine Java-Anwendung, die auf einer Java-VM ausgeführt wird (Linux OS), die auf einer System-VM ausgeführt wird (Windows OS), die wiederum auf einem Code Morphing Prozessor VM läuft (VLIW: Very Large Instruction Word)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Prozessvirtualisierung

Prozessvirtualisierung

• Einzelne Ausführungsprozesse werden virtualisiert

• Häufig werden Programme in einer eigenen Metasprache und einem speziellen Anweisungsformat ausgeführt (Bytecode, Text)

  • Java Virtual Machine (jvm)
  • Lua Virtual Machine (lua, luajit, plvm)
  • JavaScript Virtual Machine (Google v8, jerryscript, spidermonkey)
  • OCaML Bytecode VM (funktionale Programmierung)

• Benötigt spezielle Verabeitung der Programme (nur auf dieser VM ausführbar)

• Abstraktion von Hardware und Betriebssystemebene

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Prozessvirtualisierung

A Prozessvirtualisierung (Abstraktion von Hardware und Software) → Highlevel Language VM → Parallelisierung auf VM Instanzebene (1:1 Zuordnung P:VM)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Systemvirtualisierung

Systemvirtualisierung

• Hier wird die Maschine (Hardware) virtualisiert

• Verschiedene Programme und Programmformate können konventionell ausgeführt werden

• Parallele Ausführung verschiedener gekapselter Betriebssysteme

  • Parallelisierung kann entsprechend des Betriebssystem auf OS und Prozessebene erfolgen
  • Die VM selbst kann parallele IO Ausführung nutzen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Systemvirtualisierung

Systemvirtualisierung

A Systemvirtualisierung (Abstraktion von Hardware) und Parallelisierung (1:1 Zuordnung einer VM Zone zu virtuellen Prozessor)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Systemvirtualisierung

Systemvirtualisierung

A Beispiel: Zwei Betriebssysteme werden auf virtualisierter Hardware (parallel) ausgeführt

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Compiler

Compiler

Klassischer Softwareentwurf mit Compiler und Linker (C)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Interpreter

Interpreter

Edit - Compile - Execute Zyklus bei einem Interpreter

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtuelle Maschine und Bytecode Interpreter

Virtuelle Maschine und Bytecode Interpreter

• Die Übersetzung des Quelltextes in Bytecode kann vor und während der Ausführung des Programms erfolgen!

• Bytecode kann privat und abstrakt sein (nur interne Datenstrukturen) oder öffentlich in kodierter Binär- oder Assemblerform.

• Ausführung des Bytecodes durch VM. Vorteile:

  • Unabhängig von Hostplattform
  • Virtuelle Maschine kann optimiert werden ohne dass der Bytecode neu erzeugt werden muss
  • Abstraktion der Speicherverwaltung (automatisches Speichermanagement)
  • Parallelisierung kann durch VM automatisch erfolgen (wenn möglich)
  • Abstraktion der IO Schnittstellen und Kommunikation
  • VM kann Bytecode zu Beginn der Ausführung oder zur Laufzeit dynamisch und nach Bedarf optimieren (JIT)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtuelle Maschine und Bytecode Interpreter

Virtuelle Maschine und Bytecode Interpreter

Python Vergleich Interpreter mit Bytcode Compiler-Interpreter System

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Bytecode Ausführung

Bytecode Ausführung

while not terminated do
  operation = decode(code[next])
  select operation.code of
    case OP1 => DO IT
    case OP2 => DO IT ..
  endcase
  compute next
  if scheduling point then yield endif
done

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Serialisierung

Serialisierung

• Da Bytecode unabhängig von der Hostplattform sein sollte, kann Bytecode einfach von einer Maschine zu einer anderen übertragen und ausgeführt werden

• Dazu ist eine Serialisierung von Daten und Code erforderlich (Flache Liste von Bytes), mit anschließender Deserialisierung (Wiederherstellung der Daten- und Codestruktur)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Serialisierung

Serialisierung

A Serialisierung transformiert ein Objekt in ein implementierungs- und systemunabhängiges Format (a) für die Netzwerkübertragung (Text!) (b) für die persistente Speicherung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Serialisierung

Peter Cawley Bytecode VM

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Lua Bytecode

Lua Bytecode

PD Stefan Bosse - VPP - Virtuelle Maschinen :: JIT Compiler

JIT Compiler

• Neben der Bytecode Ausführung kann während der Laufzeit des Programms der Bytecode stückweise optimiert werden → Erzeugung von Maschinencode durch einen Just-in-Time Compiler (JIT)

King Fahd University of Petroleum and Minerals Vergleich Bytecode VM Interpreter mit JIT Compiler-Interpreter Systemen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

Virtualisierung

Aufgabe

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung

Virtualisierung

• Rechenleistung, Speicherbedarf, und Ein-Ausgabe Durchsatz/Latenz sind wichtige Metriken für den Einsatz in Eingebetteten Systemen → Sensornetzwerke / Internet der Dinge (IoT)

B Typische Datenverarbeitungsebenen in Eingebetteten Systemen und Virtualisierung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: NODE.JS Architektur

NODE.JS Architektur

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Performanz von Interpretern

Performanz von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherbedarf von Interpretern

Speicherbedarf von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Automatisches Speichermanagement

Automatisches Speichermanagement

• In C/C++ muss für jedes zur Laufzeit dynamisch erzeugte Datenobjekt (Array, String, Record, ..) immer explizit Speicherplatz im Hauptspeicher angefragt werden (malloc,new) und wieder frei gegeben werden wenn das Datenobjket nicht mehr benötigt wird (free,delete)

• In Skriptsprachen gibt es i.A. ein automatisches Speichermanagement mit einem sog. Garbage Collector und Objektreferenzierung

• Jedes Datenobjekt welches verwendet wird (z.B. in Variablen oder Funktionen) besitzt eine Referenz

• Es muss eine Wurzeltabelle geben von der aus alle Referenzen auf verwendete Objekte auffindbar sind

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Objekte und Referenzen

Objekte und Referenzen

• Objekte: In C/C++/JAVA usw: Variablen, in Lua/JavaScript/OCaML: Werte!

local o1 = { a=1, b={1,2,3,4} }
local o2 = { op = o1, index=2 }
function show (o) print (o2.op.a-o.a } end; 
show(o1)

Beispiel von Objektreferenzierungen in Lua: Wo existieren Referenzen?

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Objekte und Referenzen

Variablen, Referenzen, Werte in Lua

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Objekte und Referenzen

Objekte und Referenzen

A Verschiedene Objekte: Objekte die nicht mehr referenziert sind, werden freigegeben

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherarchitektur von Programmen

Speicherarchitektur von Programmen

Code

Statischer oder dynamischer Speicherbereich mit Maschinenanweisungen (und eingebetteten Daten als Anweisungsoperanden)

Heap

Datenobjekte mit längerer Lebensdauer (Tabellen- oder Listenstruktur) → Benötigt Speichermanagement

Stack

Datenobjekte mit kurzer Lebensdauer (Stapelstruktur) → Benötigt kein Speichermanagement

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherarchitektur von Programmen

Speicherhierarchie von Programmen und Zusammenhang mit Maschinenanweisungen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherorganisation von Virtuellen Maschinen

Speicherorganisation von Virtuellen Maschinen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicher

Speicher

• Die meisten Objekte in Programmiersprachen benötigen Speicher

  • Lokale, temporäre, und globale Variablen
  • Objekte
  • Arrays
  • Zeichenketten
  • Funktionen (!)
  • Native Codereferenzen (Speicheradresse)

• Der Kontext von Speicherobjekten ist wichtig:

  • Modul → limitierte Programmsichtbarkeit
  • Lokal → stark limitierte Programmsichtbarkeit
  • Global → uneingeschränkte Sichtbarkeit

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicher und Variablen

Speicher und Variablen

• Beispiele: Die globale Variable Global ist überall, auch außerhalb des Definitionsmoduls, sichtbar, die Variable lokal ist im gesamtem Modul und den Funktionen f1 und f2 sichtbar, wo hingegen lokal1 und lokal2 jeweils nur ihrem Funktionskontext sichtbar sind.

Global = 1
local lokal = 2
function f1 () 
  local lokal1 = 3
end
function f2 () 
  local lokal2 = 3
end

• Nur wenn Variablen bei der Ausführung sichtbar sind belegen sie Speicher!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicher und Variablen

Speicher und Variablen

• Ein Teil des Speicher ist vorbelegt:

  • Globale Variablen
  • Funktionen, ausführbarer Code, ...

• Ein anderer Teil des Speichers wird zur Laufzeit auf dem Stack und Heap belegt und benötigt Verwaltung:

  • Lokale und temporäre Variablen, ..
  • Funktionen, ausführbarer Code, ...

• Achtung: Bei Programmiersprachen bei denen Funktionen Werte erster Ordnung sind befindet sich auch Code im Heap oder auf dem Stack!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Polymorphie und Dynamische Typisierung

Polymorphie und Dynamische Typisierung

• Nativer Maschinencode unterscheidet Operanden nach ihren Datentypen → Speicherumfang von Datentypen ist sehr unterschiedlich (Boolean, Float64, Int16, Arrays, Records, ..)

• HLL Skript Programmierung bietet häufig dynamische Typisierung, d.h., eine Variable hat zunächst keinen Datentyp

  • Der Datentyp einer Variable ergibt daher sich nur aus den Datentypen von konkreten Werten die die Variable referenziert!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Polymorphie und Dynamische Typisierung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Polymorphie und Dynamische Typisierung

Polymorphie und Dynamische Typisierung

typedef struct {  typedef union {
  int t;            GCObject *gc;
  Value v;          void *p;
} TObject;          lua_Number n;
                    int b;
                  } Value;

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speichersegmente und Fragmentierung

Speichersegmente und Fragmentierung

• Ein (statisches oder dynamische) Speichersegment ist ein linearer zusammenhängender Bereich

  • Mit Virtuellen Speichermanagement kann ein Segment aus einer Reihe verstreuter physischer Speicherbereiche zusammengesetzt werden
  • Es wird eine Speicherzuordnungsfunktion MMU(VA) → PA benötigt (LUT, nur in Hardware effizient)

• Hochsprachen haben kein Speichermodell, sondern nur Speicherobjekte (Variablen)

  • Man unterscheidet Name, Daten, Datenkontainer und Referenz auf Datenkontainer

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speichersegmente und Fragmentierung

• Für die Ausführung mit einer Maschinen müssen diese abstrakten Speicherobjekt
  • Speicherbereiche in Segmenten Seg belegen (allocate(O))
  • Diese Speicherbereiche referenzieren MMU(O) → Seg,SA
  • Speicherbereiche in Segmenten müssen wieder frei gegeben werden wenn Objekt nicht mehr verwendet wird (free(O))

Durch Speicherallokation und Freigabe Zyklen (Speicherbedarf der Objekte variiert) kommt es zu Fragmentierung, d.h., der einst lineare Speicherbereich eines Segments besteht aus einer irregulären Folge aus freien und belegten Bereichen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speichersegmente und Fragmentierung

            Segment S                                            
      alloc ┌───────┐  free ┌───────┐   compact ┌───────┐        
a:=1 ──────▶│  a=1  │       │  a=1  │           │  a=1  │        
b:=2 ───┐   ├───────┤  /b   ├───────┤           ├───────┤        
        │   │       │       │       │       ┌──▶│  c=3  │        
..      └──▶│  b=2  │       │       │       │   ├───────┤        
            ├───────┤       ├───────┤       │   │       │        
c:=3 ──────▶│  c=3  │       │  c=3  │       └───┤       │        
            └───────┘       └───────┘           └───────┘        
               (a)             (b)                 (c)           

(a) Speicherbelegung, (b) Freigabe, und (c) Kompaktierung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherverwaltung

Speicherverwaltung

Listen

Freie und belegte Speicherbereiche werden durch Listen (einfach- oder doppelt verkettet) verwaltet

Tabellen

Tabellen (Hashtabellen) werden zur Speicherverwaltung verwendet

Manuelle Verwaltung

Speicherbelegung explizit vom Programmierer und teils vom Compiler auszuführen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherverwaltung

Vorteile

• Optimale Speicherbelegung (tatsächlich naiv und falsch) und Performanz/Effizienz

Nachteile

• Speicherlecks (nicht mehr benötigter Speicher wird nicht frei gegeben)
• Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)
• Benutzung von Speicherobjekten nach Freigabe

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Speicherverwaltung

Speicherverwaltung

Automatische Verwaltung

Die Freigabe von Speicherbereichen wird automatisch durch einen Garbage Collector durchgeführt. Dieser bestimmt auch automatisch ob Speicherobjekte noch benötigt werden.

Vorteile

• Speicherlecks werden vermieden
• Keine Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)
• Keine Benutzung von Speicherobjekten nach Freigabe

Nachteile

• Nicht optimale Speicherbelegung und schlechtere Performanz/Effizienz

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Garbage Collection

Garbage Collection

• Wie soll der GC heraus finden ob ein Objekt noch benötigt wird?

1. Referenzzähler wird jedem Objekt hinzugefügt und bei jeder neuen Referenzierung erhöht (Allocate). Ein Objekt mit Referenzwert Null kann frei gegeben werden.
2. Der GC rechnet Objektabhängkeiten aus und markiert Objekte die freigegeben werden können

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Garbage Collection

Beispiel von Referenzen und Sichtbarkeit (Programmkontext)

local o1 = { x=100,y=200 }e1          [e1.ref=1(o1)]
local o2 = { pos=o1, color="red" }e2  [e1.ref=2(o2,o1)]
function draw (o)
  local o3 = { pos=o.pos, color="white" }e3  [e3.ref=1(o3), e1.ref=4(o3,..)]
  local o4 = { pos={x=o.pos.x,y=o.pos.y}e4, color="black" } [e1.ref=5(o4,o4,..)]
  draw(o3)
  draw(o4)
  → [e3.ref=0, e4.ref=0, e1.ref=3, e2.ref=2]
end
draw(o2)  [e2.ref=2(o,o2), e1.ref=3(o,o2,o1)]
o2=nil    [e2.ref=0, e1.ref=1(o1)]
o1=nil    [e1.ref=0]

• Wichtig: Referenzzähler beziehen sich auf Werte (e_i), nicht auf die Variablen selber (die nur Zeiger auf Werte besitzen)
  • D.h. wenn ein Wert als Referenz an eine weitere Variable zugewiesen wird erhöht sich der Referenzzähler!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Referenzzählung

GC: Referenzzählung

• Wenn ein Objekt (also ein Wert) erzeugt wird, wird der Referenzzähler auf Null gesetzt

• Jede weitere Referenzierung erhöht den Zähler um eins (also bereits das zuweisen eines Objektes an eine variable!)

• Wird eine Referenzierung vom Objekt entfernt (explizit → =null, oder implizit durch Entfernen des referenzierenden Objektes), dann wird der Zähler um eins erniedrigt

• Ist der Zähler wieder Null, dann wird der Speicher freigegeben

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Referenzzählung

GC: Referenzzählung

Nachteile

1. Zyklische Referenzen können nicht aufgelöst werden:

local o1 = { x=100,y=100 }
local o2 = { prev=o1 }
o1.next = o2

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Referenzzählung

GC: Referenzzählung

2. Daher werden u.U. nicht alle Objekte freigegeben → Speicherlecks
3. Der Referenzzähler belegt selber Speicher (gehört zum Objekt). Bei low-resource Plattformen wird z.B. eine Datenwortbreite von 16 Bit für den Zähler verwendet, und der maximale Referenzwert ist 65536 (jerryscript ist so ein Kandidat)!
4. Allokation ist langsamer (verlangsamt Zuweisung)

Vorteile

1. Einfach zu implementieren
2. Freigabe ist effizient (wenig Rechenaufwand)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Mark & Sweep

GC: Mark & Sweep

• Bestimmte Objekte sind direkt zugänglich, und es muss herausgefunden werden welche Objekte erreichbar sind → Graphensuche

• Es gibt einen Stammsatz von Speicherplätzen im Programm, dessen Objekte direkt erreichbar sind.

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Mark & Sweep

GC: Mark & Sweep

Mark-and-Sweep verläuft in zwei Phasen

Markierungsphase

• Erreichbare Objekte suchen:
  • Der Stammsatz wird zu einer Arbeitsliste hinzugefügt
  • Solange die Arbeitsliste nicht leer ist wird ein Objekt von der Liste entfernt. Wenn es nicht markiert ist, markiere es als erreichbar und alle Objekte die davon aus erreichbar sind werden zur Arbeitsliste hinzugefügt.

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Mark & Sweep

Sweepphase

• Für alle belegten Objekte:
  • Ist das Objekt nicht markiert so lösche es (Speicher freigeben)
  • Ist das Objekt markiert, lösche die Markierung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Mark & Sweep

GC: Mark & Sweep

Vorteile

1. Auch zyklische Referenzen können über die Arbeitsliste aufgelöst werden
2. Alle Objekte können frei gegeben werden
3. Allokation schnell

Nachteile

1. Rechenintensiv und langsam!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: GC: Mark & Sweep

Beispiel eines M&S Durchlaufes mit anschließender Freigabe von nicht mehr erreichbaren == benötigten Objekten

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Multitasking

Multitasking

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Prozesse, Threads, Fibers

Prozesse, Threads, Fibers

            (a)                      (b)                     (c)
┌─────────┐    ┌─────────┐  ┌─────────────────────┐  ┌─────────────────────┐
│         │    │         │  │ ┌───────┐ ┌───────┐ │  │            Fiber    │
│ Process │    │ Process │  │ │Thread ├─┤Thread │ │  │   Fiber             │
│         │    │         │  │ └───────┘ └───────┘ │  │       Fiber         │
└────┬────┘    └────┬────┘  └────┬────────────────┘  └─────┬───────────────┘
     │              │            │  Process                │  Process/Thread
┌────┴──────────────┴────────────┴─────────────────────────┴───────────────┐
│                         Operating System                                 │
└──────────────────────────────────────────────────────────────────────────┘

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung und Parallelisierung

Virtualisierung und Parallelisierung

Grundkonzept: Aufteilung einer Berechnung in eine Menge von Teilberechnungen die auf verschiedenen Prozessoren parallel ausgeführt werden.

• Auf generischen Mehrprozessorsystemen (Multicore) wird Multithreading unf Multiprocessing Kontrollpfade

• Auf spezialisierten Mehrprozessorsystemen (GPU) wird sowohl Mutlithreading als auch Datenpfadparallelität ausgenutzt (Mehrere Kontroll- und Datenpfade)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Virtualisierung und Parallelisierung

Aber: Bei Virtuellen Maschinen lassen sich diese Konzepte nicht direkt übertragen!

• Automatisches Speichermanagement ("stop the world" Phase) schwierig zur parallelisieren (Konkurrenz und Ressourcenkonflikte)

• Speicherraum einer VM ist gekapselt (man spricht von einer Ausführungsinstanz oder einem isolierten Kontainer)

• VM arbeiten daher i.A. mit nur einem einzigen Kontrollfluss (auf Programmierebene)!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Architekturen Paralleler VMs

Architekturen Paralleler VMs

1. Background/Foreground Systeme

   • Es gibt einem Hauptthread der das Programm ausführt (VM Main Loop)
   • Es gibt einen Nebenthread der die GC ausführt

2. Multithreading

   • Es gibt einen oder mehrere Threads die das Programm ausführen
   • Es gibt einen oder mehrere Threads die den GC ausführen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Architekturen Paralleler VMs

Architekturen Paralleler VMs

(a) Sequenzielles System (1 Prozess/Thread) Stop-the-world GC (b) Multithreading Stop-the-world GC (c) Multithreading und paralleler/nebenläufiger GC

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Parallelisierung des GC Algorithmus

Parallelisierung des GC Algorithmus

1. Parallele Markierung
2. Paralleles Kopieren
3. Paralleles Sweeping
4. Paralleles Kompaktieren

Es wird weiterhin Synchronisation zw. den parallel ausgeführten GC Threads und dem eigentlichen VM Ausführungsthread (oder mehreren) benötigt!

• Es gibt zwei Motivationen:
  • GC soll möglich wenig Rechenzeit des Hauptprogramms "kosten" (Horizontale Par.)
  • GC soll beschleunigt werden (Vertikale Par.)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Synchronisation

Synchronisation

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Synchronisation

Synchronisation

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Parallele vs. Konkurrierend

Parallele vs. Konkurrierend

• Und wieder muss zwischen paralleler und konkurrierender Ausführung unterschieden werden, was zu unterschiedlichen Abläufen des GC und der VM Main Loop führen
• Weitere Unterscheidung durch Horizontale und Vertikale Parallelisierung (Zeit/Raumdimension)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Parallele vs. Konkurrierend

Jones, 2012, TGCH (rot) Parallele und synchronisierte Ausführung (VM Main Loop angehalten) (blau) Konkurrierende Ausführung und überlappend mit VM Main Loop

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Parallele VM Instanzen

Parallele VM Instanzen

• Parallelität daher durch mehrere VM Instanzen möglich.

  • Eine Instanz ↠ Ein Prozess (Thread)

  • Aber: Die Start- und Initialisierungszeit einer VM Instanz kann hoch sein (JS nodejs/v8: 100ms, LuaJit: 1ms)

  • Weiterhin ist der Speicherbedarf einer VM Instanz zu beachten ("baseline" ohne Nutzprogramm, nodejs: 20MB, LuaJit: 1MB)

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Parallele VM Instanzen

Bei hoher Initialisierungszeit einer VM Instanz muss diese im voraus gestartet werden (in-advance) und über eine Service Loop auf Prozesscode warten.

Bei kleiner Initialisierungszeit einer VM Instanz kann ein VM Prozess ad-hoc und dynamisch gestartet werden.

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Stack vs Register vs Speichermaschinen

Stack vs Register vs Speichermaschinen

                                                                            
┌─────────┐          ┌─────────┐     ┌──────────┐        ┌─────────┐        
│  Stack  │          │  Code   │     │ Register │        │   RAM   │        
├─────────┤          ├─────────┤     ├──────────┤        ├─────────┤        
│         │◀───┐     │         │  ┌─▶│    R1    │     ┌──┤  Instr  │◀──┐    
│         │    │     │         │  │  │          │     │  │         │   │    
│  Instr  ├────┤     │  Instr  │◀─┼──┤    R2    │     │  │    Op   ├───┤    
│         │    │     │         │  │  │          │     │  ├─────────┤   │    
│    Op   ├────┤     │    Op   ├──┘  │    R3    │     │  │  Data   ├───┘    
│         │    │     │         │     │          │     │  │         │        
│    Op   ├────┘     │         │     │          │     └─▶│         │        
└─────────┘          └─────────┘     └──────────┘        └─────────┘        
    (a)                          (b)                          (c)           

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

Echtzeitverarbeitung

• Echtzeitverarbeitung bedeutet die Ausführung eines Tasks innerhalb eines vorgegebenen Zeitintervalls [t₀,t₁]
  • Soft Realtime: Zeitüberschreitung bei weicher Echtzeitanforderung → Tolerierbar
  • Hard Realtime: Zeitüberschreitung bei harter Echtzeitanforderung → Systemfehler

B Echtzeitspektrum: Weiche und harte Echtzeitanforderungen bei unterschiedlichen Applikationen

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

Echtzeitverarbeitung

B Periodische, sporadische, und aperiodische Tasks

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

Echtzeitverarbeitung

Preemption

• Wenn schon nicht alles Tasks gleichzeitig verarbeitet werden können, dann wenigstens die wichtigsten vorrangig ausführen

• Das erfordert aber:

  • Festlegung einer Priorität
  • Bei Echtzeitanforderungen die Unterbrechung von unterlegenen (kleiner Priorität) Tasks

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

B Unterschied preemptive und nicht preemptive Ausführung von Tasks

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

Echtzeitverarbeitung

Virtuelle Maschinen

• Schon die Parallelisierung der Programmausführung ist schwierig und eher schwergewichtig!

• Dis Ausführungszeiten von Programmen sind nicht im voraus bekannt und deterministisch

  • JIT beeinflusst die Ausführungszeit zur Laufzeit signifikant (Übersetzung kostet Zeit, Maschinenkode spart Zeit)
  • Automatisches Speichermanagement (GC) führt zu teils stark variierenden Laufzeiten und Performanz von Programmen
  • Bei längerer Laufzeit kann sich die Performanz (Latenz/Datendurchsatz) verringern. Warum?

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Echtzeitverarbeitung

Echtzeitfähigkeit bei automatischen Speichermanagement ("stop the world" Phase), JIT und umfangreiche Nutzung dynamischer Datenstrukturen kaum zu gewährleisten!

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Multiinstanz VM: Beispiel (P)LVM

Multiinstanz VM: Beispiel (P)LVM

┌──────────────┬─────┐         ┌─────┬──────────────┐          
│     VMI 1    │ GC  │  Ref.   │ GC  │      VMI 2   │          
│ X=1          │     │  Count  │     │ X=1          │          
│ local c=IPC  ├──▶  │ ◀─────▶ │  ◀──┤ local c=IPC  │          
│ function foo │     │ ┌─────┐ │     │ function foo │          
│   local x=X  │     │ │     │ │     │   local x=X  │          
│   c()   ◀────┬─────┬─┬─────┬─┬─────┬─▶ c()        │          
│              │     │ │ IPC │ │     │              │          
└──────────────┴─────┘ └─────┘ └─────┴──────────────┘          
                        alloc/free                             
┌───────────────────────────────────────────────────┐          
│ ┌──────────────────┐         ┌──────────────────┐ │          
│ │   Thread T1      │         │      Thread T2   │ │ Process P
│ └──────────────────┘         └──────────────────┘ │          
└───────────────────────────────────────────────────┘          

Zwei Lua LVM Instanzen mit gemeinsamen eng gekoppelten Interprozeßkommunikationsobjekten und implizite GC Kopplung über Referenzzählung

PD Stefan Bosse - VPP - Virtuelle Maschinen :: Zusammenfassung

Zusammenfassung