You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Im folgenden Blog werden die beiden theoretischen Modelle zur Nebenläufigkeit Aktor Modell und CSP vorgestellt. Die beiden Programmiersprachen Elixir und Go haben in Anlehnung an diesen Modellen eine eigene Implementierung der Konzepte verwirklicht. Vorgestellt werden hier sowohl die Programmiersprachen selbst, die Syntax zur Nebenläufigkeit als auch die Implementierung in der Laufzeitumgebung, welches das Hauptaugenmerk dieses Blogs ist.
Was ist Concurrency?
Zuerst wird die Frage beantwortet: "Was ist überhaupt Nebenläufigkeit oder Concurrency?". Im Englischen gibt es die Begriffe Concurrency und Parallelism, welche öfters gleichbedeutend genutzt werden, jedoch unterschiedliche Eigenschaften beschreiben. Concurrency ist eine Eigenschaft des Codes. Es beschreibt dabei die Möglichkeit, dass unterschiedliche Blöcke des Codes nebeneinander ausgeführt werden können, ohne dabei zu unterschiedlichen Ergebnissen zu kommen. Parallelism ist hierbei eine Eigenschaft des laufenden Programmes. Es beschreibt, dass Teile des Programmes während der Ausführung gleichzeitig durchgeführt werden. Innerhalb des Studiums trifft man auf die klassischen Modelle, welche Concurrency und Parallelism ermöglichen. Dieses nutzten die Prozesse und Threads des Betriebssystems. In den meisten Programmiersprachen findet man diese beiden Modelle. Die Implementierungen, die in diesem Blog vorgestellt werden, befinden sich eine Abstraktionsebene über den OS-Threads. Diese "Threads" werden jeweils von der Laufzeitumgebung der Programmiersprache gesteuert und versuchen das Arbeiten mit Concurrency im Vergleich zu den herkömmlichen Modellen zu vereinfachen.
Aktor Modell
Das erste theoretische Modell ist das Aktor Modell. Dieses wurde erstmals 1973 von Carl Hewitt, Peter Bishop und Richard Steiger vorgestellt. Es wurde im Rahmen des Planner Projekts ausgearbeitet. Planner ist eine Programmiersprache gewesen für "Automated Planing" im Bereich der künstlichen Intelligenz. Das vorgestellte mathematische Modell hatte als Grundbaustein die Aktoren. Dies waren Recheneinheiten, die sich untereinander Nachrichten senden konnten. Ein Aktor kann auf eine Nachricht unterschiedlich reagieren. Folgende Aktionen kann ein Aktor dabei durchführen:
Nachrichten an andere Aktoren senden
Neue Aktoren erstellen
Verhalten für das Bearbeiten der nächsten Nachrichten einstellen
Damit ein Aktor Nachrichten an andere Aktoren schicken kann, müssen diese miteinander verbunden sein. Ob dies durch Hardware oder Software, wie zum Beispiel Namen von Aktoren realisiert wird, ist offen.
Die Aktoren bearbeiten die Nachrichten nach dem FIFO-Prinzip ab.
Elixir
Die Programmiersprache Elixir enthält eine Implementierung des Aktor Modells. Entwickelt wurde die Programmiersprache von José Valim in 2011. Sie ist ein Open-Source-Projekt, an dem mehrere hundert Personen bereits mitgewirkt haben. Sie ist funktional und nebenläufig. Typisiert ist sie stark und dynamisch. Der Elixir Code kompiliert über den Elixir AST in Beam Code. Beam (Bogumil’s/Björn’s Abstract Machine) ist eine Register-basierte Erlang Virtual Machine. In Elixir kann dabei auch auf Funktionalität aus Erlang zurückgegriffen werden. Elixir versucht das Arbeiten hier deutlich zu vereinfachen. Gerade durch Vereinfachung des Codes sowie einem Build Tool, Mix. Zudem lassen sich Makros einfach definieren, da aus Elixir Code Makros definiert werden können. Das Hauptaugenmerk von Elixir war es, dass Tooling von Erlang zu modernisieren.
Elixir Prozesse
In Elixir und Erlang werden Aktoren Prozesse genannt. In der Abbildung ist ein solcher Prozess zu sehen. Mit dem def keyword können wir eine Funktion definieren, welche bis zum gleich eingerückten end geht. Mit dem receive keyword können wir einen Block definieren, in welchem wir angeben können, auf welche Nachrichten wir reagieren. Die Nachrichten werden dabei mit sogenannten atoms definiert (:ping). Dies sind Konstanten, dessen Wert der eigene Name ist. Dadurch lassen sich die Namen der Nachrichten definieren. An den weiteren Stellen, hinter dem Namen der Nachricht, können weitere Variablen definiert werden. Wir senden hier im Beispiel, wenn wir eine :ping Nachricht bekommen eine :pong Nachricht zurück an den Prozess der übergeben wurde. Danach rufen wir uns rekursiv auf, um auf neue Nachrichten reagieren zu können. Im zweiten Bild starten wir dann einen Prozess, der die server Funktion aufruft mit spawn. Diesem senden wir dann eine Nachricht mit der Hauptprozess als source_alias. Im Hauptprozess definieren wir dann auch ein receive und bekommen dann die :pong Nachricht vom server Prozess und geben diese aus.
Weitere Elixir Aktor Abstraktionen
Im normalen Elixir Gebrauch werden die Prozesse nicht genutzt, sondern höhere Abstraktion die Elixir bietet. Zu Aktor Darstellung wurden die normalen Prozesse genutzt. Hier eine Liste von Abstraktionen die Prozesse nutzen:
Agent -> Prozess für veränderbaren Zustand
Applikation -> Funktionen für die Applikation (Starten, Updaten, Beenden)
Genserver -> Client-Server API
Registry -> Key-Value Speicher
Supervisor -> verwaltet Prozesse mit Strategien, falls ein Prozess abstürzt
Task -> Prozess für Berechnungen
Task.Supervisor -> Supervisor für Tasks
Erlang
Erlang wird entwickelt von der Telekommunikationsfirma Ericsson seit dem Jahr 1987. Sie ist wie Elixir funktional, nebenläufig und stark, dynamisch typisiert. Sie wurde vor allem für ein skalierbares zuverlässiges System entwickelt, welches für ein Telekommunikationsnetz nötig ist. Dabei sollen vor allem wenig bis gar keine Downtime erreicht werden und bei Fehlern sollte nicht das ganze System abstürzen. Auch hier wird der Code in Beam Bytecode kompiliert und die Beam führt den Code aus und verwaltet die Prozesse.
Erlang Node
Bevor wir zu den Prozessen in der Runtime kommen, schauen wir uns an, wie ein typisches Elixir Programm beim Starten aussieht. Beim Starten wird eine Erlang Node gestartet, welche in einem Kern eines Prozessors läuft. Diese Node besteht dabei aus mehreren Layern. Im obersten Layer befindet sich dabei der eigene Code der Applikation und der Code der Third Party libraries. Darauf ist die Elixir Umgebung und die Standardbibliothek. Darunter befindet sich OTP(Open Telecom Protocol), welches die Standardbibliothek von Erlang ist. Dann kommt die Beam Virtual Machine und ganz unten dann das ERTS(Erlang Runtime System). Im Bild zu sehen ist, dass für jeden Kern eine Node gestartet werden kann. Die Erlang Nodes können miteinander auf demselben sowie auf anderen Rechner verbunden werden und Aktoren können dann zu Aktoren anderen Nodes Nachrichten schicken.
Erlang Prozesse
Nun werden die Erlang Prozesse vorgestellt und wie sie in der Beam implementiert sind. In der Abbildung sieht man eine Übersicht über die Speicherbausteine eines Prozesses, welche nun genauer erklärt werden. Ein Erlang Prozess ist eine isolierte Einheit, in dem Code ausgeführt wird. Die Mindestgröße liegt bei 326 words (ungefähr 652 byte). Er besitzt einen Stack für Rücksprungadressen, Variablen und
Funktionsargumente, sowie einen Heap für größere Strukturen, wie Listen. Die M-box und m-buf Elemente sind für das Nachrichtensenden und werden gleich genauer erklärt. Der Process Control Block (PCB) ist der einzige Speicher mit einer statischen Größe. Dieser speichert das Verhalten und den derzeitigen Status des Prozesses ab. Das Process Dictionary (PD) ist ein lokaler Key-Value Speicher. Stack, Heap, M-box können dynamisch größer und kleiner werden. Der Garbage Collector gibt Speicher frei, wenn der Speicher voll ist und legt dabei einen neuen größeren Speicher an. Dabei werden die weiterhin genutzten Daten in den neuen Speicherblock kopiert und der alte Speicherbereich dann freigelassen. Ältere Daten werden in einen neuen Speicherblock Old Heap abgespeichert. Dieser wird erst bei einem "Major Collection" des GC freigegeben. Der Stack und der Heap ist ein Speicherblock. Der Stack geht zu den niedrigeren Speicheradressen und der Heap zu den Höheren.
Erlang Nachrichten senden
Jetzt wird gezeigt, wie das Senden von Nachrichten in Erlang funktioniert. Als Beispiel haben wir zwei Prozesse P1 und P2, wobei P1 dem Prozess P2 eine Nachricht sendet. Folgende Schritte werden dabei von P1 ausgeführt:
Größe der Nachricht berechnen
Speicher für Nachricht allokieren
Nachricht zum allokierten Speicher kopieren
Nachricht in ErlMessage struct einpacken
Struct in Queue verlinken (ErlMsgQueue oder ErlMsgInQueue)
Der Ort wo der Speicher in P2 allokiert wird, hängt von der jeweiligen Strategie ab. Diese kann eingestellt werden. Als Standard ist "on_heap" gesetzt, die andere Möglichkeit ist "off_heap".
Beim Senden mit der Strategie "on_heap" gibt es zwei Möglichkeiten, wo der Speicher allokiert wird. Falls der Speicher vom Heap von P2 nicht voll ist und P1 den main lock von P2 bekommen kann, wird die Nachricht direkt auf den Heap von P2 geschrieben. Falls dies nicht der Fall ist, wird die Nachricht in einen m-buf geschrieben und die Nachricht wird in die M-box intern verlinkt. Bei dem nächsten GC wird die Nachricht dann in den Heap von P2 gebracht. In m-buf Fragmente können andere Prozesse sicher Nachrichten schreiben.
Bei der Strategie "off_heap" sieht es anders aus. Hier wird immer die Nachricht in ein m-buf geschrieben und die Nachricht wird in die M-box inq verlinkt. Die Nachricht kommt erst auf den Heap von P2, wenn sie von einem anderen Objekt auf dem Heap gebraucht wird.
Erlang Scheduler
Damit die Prozesse effizient ausgeführt werden, gibt es den Scheduler, welcher die Prozesse verwaltet. Dies ist ein preemptive auf cooperative scheduler. Ein Prozess kann nur an bestimmten Punkten die Ausführung entzogen werden. Die Ausführungszeit ist eingeschränkt mit Reductions. Reductions sind nicht genau definiert, jedoch zählt jeder Funktionsaufruf als Reduction. Da Erlang und Elixir keine Schleifen haben und generell es keine längere Zeit gibt, ohne Funktionsaufruf ist dies ein Mittel um die Ausführungszeit des Prozesses zu limitieren. Der Prozess geht im Status dann von running zu runnable. Die Prozesse verlieren zudem die Ausführung, wenn sie in ein receive gehen und keine passende Nachrichten vorhanden ist. Sie gehen dann in den waiting Status. Sie kommen in runnable Status wieder, wenn sie eine Message bekommen oder ein Timeout abgelaufen ist. Jeder Scheduler hat Zwei Queues, eine für die runnable und eine für die im waiting Status stehenden Prozesse. Die Ready Queue(runnable) ist zudem auf 3 Queues verteilt, je nach Priorität. Es werden erst Prozesse aus der Queue mit Priorität Max genommen, dann mit High und dann aus Normal, Low. In der Normal, Low Queue werden den Normal Prozessen einen Counter von 1 und den Low Prozessen einen Counter von 7 zugewiesen. Dieser wird reduziert, wenn ein Prozess ausgeführt werden soll. Ist der Counter auf 0, wird der Prozess ausgeführt andernfalls wird er ans Ende der Queue gesetzt. Falls ein Scheduler keine Prozesse hat, kann er Prozesse anderer Scheduler stehlen. Im SMP Mode kann zudem für jeden OS Thread ein Scheduler genutzt werden.
CSP (Comunicating sequential processes)
Das zweite theoretische Paper handelt von CSP (Comunicating sequential processes). Vorgestellt wurde es von C.A.R. Hoare in 1978. Die Hauptprämisse von ihm war es, das input, output und concurrency primitives einer Programmiersprache seien sollen. Er erwähnte, dass sonst erst nach dem Erstellen einer Programmiersprache diese Konzepte behandelt wurden. Er stellte in seinem Paper eine Beispielprogrammiersprache auf, welche zeigen soll, wie die Konzepte in einer Programmiersprache eingebunden werden können. Dabei löst er mit dieser Programmiersprache bekannte Probleme wie das Philosophenproblem. Die Prozesse in seiner Sprache können mit Kommandos miteinander kommunizieren, wie in der Abbildung zu sehen. Dabei kann mit dem ? Operator aus einem Quellprozess in eine Variable geschrieben werden und mit dem ! Operator einen Ausdruck in einen Prozess gegeben werden. Hierbei müssen die Prozesse sich untereinander mit dem Namen kennen. Er zeigt im Paper selbst alternative Konzepte auf. Eines davon ist die Kommunikation über benannte Ports in denen Variablen gesendet und gelesen werden können. Dieses Konzept ähnelt dem der Programmiersprache Go, welche als nächstes belichtet wird.
Go
Go ist eine Programmiersprache, welche von Mitarbeitern von Google 2009 entwickelt wurde. Sie ist objektorientiert, funktional und nebenläufig.
Die Typisierung ist statisch und stark. Wichtige Themen für das Erstellen von Go war der Development Speed. Die Syntax sollte einfach und prägnant sein(nur 25 Keywords). Der Compiler soll schnell sein und es sollte ein Mittelweg zwischen Sprachen wie C++ und Python gefunden werden. Auch Concurrency war ein wichtiger Teil. Go code kompiliert zu einer binary executeable, welche ein Runtime beinhaltet mit GC und weiteren Funktionalitäten.
Goroutines
Goroutines sind die Lösung für Concurrency in Go. In der Abbildung sieht man ein Beispiel, wie diese genutzt werden. Wir haben hier erst eine Funktion definiert, die ein string bekommt und diesen 5 Mal in 1 Sekunden Abschnitten ausgibt. In unserer main Funktion rufen wir diese Funktion zweimal mit "world" und "hello" auf. Wichtig ist hierbei das "go" keyword, welches dafür sorgt, dass die Funktion in einer Goroutine läuft. Das "go" keyword kann hierbei auch vor einer Funktionsdefinition stehen. Der Output zeigt, dass die Funktionen nicht sequentiell ausgeführt werden, sondern gleichzeitig.
Wenn wir nun zwischen Goroutines kommunizieren möchten, können wir dies mit Channels. Einen Channel können wir mit make(chan int) definieren. Wir können hierbei definieren, welchen Typen wir für den Channel benutzen. In den Channel schreiben wir mit c <- var und lesen mit var <- c. In dem Beispiel berechnen wir die Summe, jedoch mit zwei Goroutinen, welche jeweils die Hälfte des Arrays an Werten bekommen. Diese schreiben die Werte in den Channel und diese Werte werden ausgelesen in die Variablen x und y. Das Lesen und Schreiben blockiert die derzeitige Goroutine solange kein anderer aus dem Channel liest oder sendet je nach Operation.
Dafür gibt es Buffered Channels, diese können mehre Werte aufnehmen je nachdem, wie viele spezifiziert wurden. Das Schreiben, blockiert dadurch erst, wenn der Buffer voll ist oder der Buffer leer ist und gelesen wird.
Das select statement ermöglicht es auf mehrere Channel zu lauschen und falls einer einen Wert hat, wird dieser ausgeführt. Wenn mehrere ausgeführt werden können, wird einer von diesen ausgewählt. Im Beispiel wird dies genutzt, um die Funktion abzubrechen, wenn keine Zahlen mehr gesendet werden.
Goroutines in der Laufzeitumgebung
Goroutines sind in der Laufzeitumgebung als type g struct definiert. In der Abbildung kann man ein paar der wichtigen Attribute einer Goroutine erkennen. Die Goroutine besitzt eines Stack dessen Mindestgröße 2kb beträgt. Er kann dabei größer und kleiner werden. Beim Erweitern wird die Größe des vorherigen Stacks verdoppelt. Der alte Speicher wird dabei in den neuen kopiert und danach freigegeben. m beschreibt eine Verbindung zum derzeitigen OS Thread. sched ist dafür da Zustand zu speichern. Den Staus der Goroutine wird in atomicstatus festgehalten. Runnable, Running und waiting sind die für uns wichtigen Status. Neben diesen gibt es noch einige Weitere, welche nicht weiter beleuchtet werden. Die boolean Variablen activeStackChans und parkingOnChan sind wichtig für die Erweiterung und Verkleinerung des Stacks, damit vorher wichtige Bereiche abgesichert werden können.
Channels in der Laufzeitumgebung
Channels sind als type hchan struct definiert. Wichtig ist hierbei buf, welcher ein Pointer zu dem Array ist, in dem sich die derzeitigen Werte innerhalb des Channels befinden. recvq und sendq sind doubly linked list, welche Listen für die Empfänger und die Absender sind. Der lock wird hier genutzt, um die Operation einer Goroutine auf den Channel zu sichern. Beim Kommunizieren bei Buffered Channels gibt es 3 mögliche Szenarien:
Sender sendet auf nicht vollen Buffer, Empfänger liest auf nicht leeren Buffer
Sender sendet auf vollen Buffer
Empfänger liest auf leeren Buffer
Was in diesen Szenarien im Channel passiert wird nun beschrieben.
Dazu nehmen wir zwei Goroutinen G1 und G2. Vor jeder Aktion einer Goroutine auf einen Channel wird der lock des Channels genommen und danach wieder freigegeben.
Im 1. Szenario sendet G1 in den nicht vollen Channel. Dabei kopiert sie den Wert und schreibt in auf buf vom Channel. Danach liest G2 aus dem Channel. Dabei nimmt sie den Wert aus dem buf, macht eine Kopie und weist die Kopie der Variable zu.
Im 2. Szenario sendet G1 auf einen vollen Buffer. G1 fügt sich dabei der sendq des Channels zu. Der Channel gibt das Signal an den Scheduler, dass G1 jetzt im waiting Status ist. Dann kommt G2 und liest aus dem vollen buf. Hier nimmt G2 den Wert aus dem buf macht eine Kopie und weist die Kopie zu. Dann holt G2 G1 aus der sendq und schreibt den Wert von G1 in den buf. G2 gibt auch das Signal an den Scheduler, dass G1 wieder in den runnable Status gebracht werden kann.
Im 3. Szenario liest G2 aus einem leeren Buffer. G2 fügt sich hierbei der receivq hinzu und der Channel gibt dem Scheduler das Signal, dass G2 im waiting Status ist. G1 schreibt dann in den leeren Channel. Dabei schreibt G1 den Wert direkt in die Variable von G2 und holt diese aus der receivq. G1 gibt außerdem dem Scheduler das Signal G2 in den runnable Status zu bringen.
Das 3. Szenario wird bei unbuffered Channels auf beiden Seiten benutzt. Es wird direkt in die Variable gelesen oder geschrieben. Dieses Verhalten bei unbuffered und buffered Channels ist eine Optimierung, da es länger dauern würde, wenn die Goroutine aus dem wartenden Zustand dies tun würde.
Go Scheduler
Der Go Scheduler ist ein M:N Scheduler. Er weist M Goroutinen auf N OS-Threads zu. Die 3 Hauptbestandteile innerhalb des Schedulers sind G die schon besprochene Goroutine, M der ein OS-Thread innerhalb der Laufzeitumgebung abbildet, sowie P, welches ein Kontext darstellt oder auch einen logischen Prozessor. Die Anzahl dieser p kann mit der Variable GOMAXPROCS festgelegt werden. Standardmäßig ist dies die Anzahl der CPU Kerne. Diese P besitzen eine Local Queue in welcher G fürs Scheduling gebunden werden. Außerdem gibt es zwei Pools für inaktive M und P. Im Scheduler werden OS-Threads(M) an Kontexten(P) zugewiesen, welche selbst die Goroutinen binden. Dort wird dann die gerade laufende Goroutine ausgeführt. Es gibt 3. Szenarien, bei der eine laufende Goroutine in den Wartestatus gelangt und ausgetauscht wird, damit die Auslastung der Threads optimal genutzt wird.
Systemaufruf
Bei einem Systemaufruf ist der dazugehörige Thread ebenfalls blockiert. Der Kontext(P) entfernt deswegen den Thread mit der dazugehörigen Goroutine um zu versuchen einen neuen inaktiven Thread nutzen zu können. Wenn die Goroutine nicht mehr durch den Systemaufruf blockiert ist, versucht der Thread sich an einen freien Kontext zu binden. Falls dies nicht möglich ist, wird die Goroutine der Global Run Queue hinzugefügt
Netzwerkaufruf
Es gibt einen Network Poller, welcher einen eigenen OS-Thread besitzt. Dieser nimmt Goroutinen auf, welche einen Netzwerkaufruf durchführen. Wenn der Aufruf zu Ende ist, führt der Network Poller die Goroutine wieder in die Local Run Queue des vorherigen Kontextes.
Channel Kommunikation
Wie eben schon besprochen wird die Goroutine in dem Channel gespeichert. Wenn diese dann wieder runnable ist, wird sie der Local Run Queue des Kontextes hinzugefügt
Die Kontexte fragen die Global Run Queue periodisch ab und falls sich dort Goroutinen befinden, fügt der Kontext sie in seine Local Run Queue hinzu. Falls die Local Run Queue eines Kontextes leer ist, kann dieser entweder Goroutinen aus der Global Run Queue nehmen oder von anderen Kontexten Goroutinen stehlen. Dabei nimmt er die Hälfte der Goroutinen.
Dies war mein Blog über das Aktor Modell, CSP und deren Implementierungen in Elixir und Go. Ich hoffe, es war interessant zu lesen.
Quellen
Carl Hewitt, Peter Bishop, and Richard Steiger. 1973. A universal modular ACTOR formalism for artificial intelligence.
C. Hewitt, "Actor Model of Computation: Scalable Robust Information Systems," arXiv:1008.1459 [cs.PL], 2015.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
-
Einleitung
Im folgenden Blog werden die beiden theoretischen Modelle zur Nebenläufigkeit Aktor Modell und CSP vorgestellt. Die beiden Programmiersprachen Elixir und Go haben in Anlehnung an diesen Modellen eine eigene Implementierung der Konzepte verwirklicht. Vorgestellt werden hier sowohl die Programmiersprachen selbst, die Syntax zur Nebenläufigkeit als auch die Implementierung in der Laufzeitumgebung, welches das Hauptaugenmerk dieses Blogs ist.
Was ist Concurrency?
Zuerst wird die Frage beantwortet: "Was ist überhaupt Nebenläufigkeit oder Concurrency?". Im Englischen gibt es die Begriffe Concurrency und Parallelism, welche öfters gleichbedeutend genutzt werden, jedoch unterschiedliche Eigenschaften beschreiben. Concurrency ist eine Eigenschaft des Codes. Es beschreibt dabei die Möglichkeit, dass unterschiedliche Blöcke des Codes nebeneinander ausgeführt werden können, ohne dabei zu unterschiedlichen Ergebnissen zu kommen. Parallelism ist hierbei eine Eigenschaft des laufenden Programmes. Es beschreibt, dass Teile des Programmes während der Ausführung gleichzeitig durchgeführt werden. Innerhalb des Studiums trifft man auf die klassischen Modelle, welche Concurrency und Parallelism ermöglichen. Dieses nutzten die Prozesse und Threads des Betriebssystems. In den meisten Programmiersprachen findet man diese beiden Modelle. Die Implementierungen, die in diesem Blog vorgestellt werden, befinden sich eine Abstraktionsebene über den OS-Threads. Diese "Threads" werden jeweils von der Laufzeitumgebung der Programmiersprache gesteuert und versuchen das Arbeiten mit Concurrency im Vergleich zu den herkömmlichen Modellen zu vereinfachen.
Aktor Modell
Das erste theoretische Modell ist das Aktor Modell. Dieses wurde erstmals 1973 von Carl Hewitt, Peter Bishop und Richard Steiger vorgestellt. Es wurde im Rahmen des Planner Projekts ausgearbeitet. Planner ist eine Programmiersprache gewesen für "Automated Planing" im Bereich der künstlichen Intelligenz. Das vorgestellte mathematische Modell hatte als Grundbaustein die Aktoren. Dies waren Recheneinheiten, die sich untereinander Nachrichten senden konnten. Ein Aktor kann auf eine Nachricht unterschiedlich reagieren. Folgende Aktionen kann ein Aktor dabei durchführen:
Damit ein Aktor Nachrichten an andere Aktoren schicken kann, müssen diese miteinander verbunden sein. Ob dies durch Hardware oder Software, wie zum Beispiel Namen von Aktoren realisiert wird, ist offen.
Die Aktoren bearbeiten die Nachrichten nach dem FIFO-Prinzip ab.
Elixir
Die Programmiersprache Elixir enthält eine Implementierung des Aktor Modells. Entwickelt wurde die Programmiersprache von José Valim in 2011. Sie ist ein Open-Source-Projekt, an dem mehrere hundert Personen bereits mitgewirkt haben. Sie ist funktional und nebenläufig. Typisiert ist sie stark und dynamisch. Der Elixir Code kompiliert über den Elixir AST in Beam Code. Beam (Bogumil’s/Björn’s Abstract Machine) ist eine Register-basierte Erlang Virtual Machine. In Elixir kann dabei auch auf Funktionalität aus Erlang zurückgegriffen werden. Elixir versucht das Arbeiten hier deutlich zu vereinfachen. Gerade durch Vereinfachung des Codes sowie einem Build Tool, Mix. Zudem lassen sich Makros einfach definieren, da aus Elixir Code Makros definiert werden können. Das Hauptaugenmerk von Elixir war es, dass Tooling von Erlang zu modernisieren.
Elixir Prozesse
In Elixir und Erlang werden Aktoren Prozesse genannt. In der Abbildung ist ein solcher Prozess zu sehen. Mit dem def keyword können wir eine Funktion definieren, welche bis zum gleich eingerückten end geht. Mit dem receive keyword können wir einen Block definieren, in welchem wir angeben können, auf welche Nachrichten wir reagieren. Die Nachrichten werden dabei mit sogenannten atoms definiert (:ping). Dies sind Konstanten, dessen Wert der eigene Name ist. Dadurch lassen sich die Namen der Nachrichten definieren. An den weiteren Stellen, hinter dem Namen der Nachricht, können weitere Variablen definiert werden. Wir senden hier im Beispiel, wenn wir eine :ping Nachricht bekommen eine :pong Nachricht zurück an den Prozess der übergeben wurde. Danach rufen wir uns rekursiv auf, um auf neue Nachrichten reagieren zu können. Im zweiten Bild starten wir dann einen Prozess, der die server Funktion aufruft mit spawn. Diesem senden wir dann eine Nachricht mit der Hauptprozess als source_alias. Im Hauptprozess definieren wir dann auch ein receive und bekommen dann die :pong Nachricht vom server Prozess und geben diese aus.
Weitere Elixir Aktor Abstraktionen
Im normalen Elixir Gebrauch werden die Prozesse nicht genutzt, sondern höhere Abstraktion die Elixir bietet. Zu Aktor Darstellung wurden die normalen Prozesse genutzt. Hier eine Liste von Abstraktionen die Prozesse nutzen:
Erlang
Erlang wird entwickelt von der Telekommunikationsfirma Ericsson seit dem Jahr 1987. Sie ist wie Elixir funktional, nebenläufig und stark, dynamisch typisiert. Sie wurde vor allem für ein skalierbares zuverlässiges System entwickelt, welches für ein Telekommunikationsnetz nötig ist. Dabei sollen vor allem wenig bis gar keine Downtime erreicht werden und bei Fehlern sollte nicht das ganze System abstürzen. Auch hier wird der Code in Beam Bytecode kompiliert und die Beam führt den Code aus und verwaltet die Prozesse.
Erlang Node
Bevor wir zu den Prozessen in der Runtime kommen, schauen wir uns an, wie ein typisches Elixir Programm beim Starten aussieht. Beim Starten wird eine Erlang Node gestartet, welche in einem Kern eines Prozessors läuft. Diese Node besteht dabei aus mehreren Layern. Im obersten Layer befindet sich dabei der eigene Code der Applikation und der Code der Third Party libraries. Darauf ist die Elixir Umgebung und die Standardbibliothek. Darunter befindet sich OTP(Open Telecom Protocol), welches die Standardbibliothek von Erlang ist. Dann kommt die Beam Virtual Machine und ganz unten dann das ERTS(Erlang Runtime System). Im Bild zu sehen ist, dass für jeden Kern eine Node gestartet werden kann. Die Erlang Nodes können miteinander auf demselben sowie auf anderen Rechner verbunden werden und Aktoren können dann zu Aktoren anderen Nodes Nachrichten schicken.
Erlang Prozesse
Nun werden die Erlang Prozesse vorgestellt und wie sie in der Beam implementiert sind. In der Abbildung sieht man eine Übersicht über die Speicherbausteine eines Prozesses, welche nun genauer erklärt werden. Ein Erlang Prozess ist eine isolierte Einheit, in dem Code ausgeführt wird. Die Mindestgröße liegt bei 326 words (ungefähr 652 byte). Er besitzt einen Stack für Rücksprungadressen, Variablen und
Funktionsargumente, sowie einen Heap für größere Strukturen, wie Listen. Die M-box und m-buf Elemente sind für das Nachrichtensenden und werden gleich genauer erklärt. Der Process Control Block (PCB) ist der einzige Speicher mit einer statischen Größe. Dieser speichert das Verhalten und den derzeitigen Status des Prozesses ab. Das Process Dictionary (PD) ist ein lokaler Key-Value Speicher. Stack, Heap, M-box können dynamisch größer und kleiner werden. Der Garbage Collector gibt Speicher frei, wenn der Speicher voll ist und legt dabei einen neuen größeren Speicher an. Dabei werden die weiterhin genutzten Daten in den neuen Speicherblock kopiert und der alte Speicherbereich dann freigelassen. Ältere Daten werden in einen neuen Speicherblock Old Heap abgespeichert. Dieser wird erst bei einem "Major Collection" des GC freigegeben. Der Stack und der Heap ist ein Speicherblock. Der Stack geht zu den niedrigeren Speicheradressen und der Heap zu den Höheren.
Erlang Nachrichten senden
Jetzt wird gezeigt, wie das Senden von Nachrichten in Erlang funktioniert. Als Beispiel haben wir zwei Prozesse P1 und P2, wobei P1 dem Prozess P2 eine Nachricht sendet. Folgende Schritte werden dabei von P1 ausgeführt:
Der Ort wo der Speicher in P2 allokiert wird, hängt von der jeweiligen Strategie ab. Diese kann eingestellt werden. Als Standard ist "on_heap" gesetzt, die andere Möglichkeit ist "off_heap".
Beim Senden mit der Strategie "on_heap" gibt es zwei Möglichkeiten, wo der Speicher allokiert wird. Falls der Speicher vom Heap von P2 nicht voll ist und P1 den main lock von P2 bekommen kann, wird die Nachricht direkt auf den Heap von P2 geschrieben. Falls dies nicht der Fall ist, wird die Nachricht in einen m-buf geschrieben und die Nachricht wird in die M-box intern verlinkt. Bei dem nächsten GC wird die Nachricht dann in den Heap von P2 gebracht. In m-buf Fragmente können andere Prozesse sicher Nachrichten schreiben.
Bei der Strategie "off_heap" sieht es anders aus. Hier wird immer die Nachricht in ein m-buf geschrieben und die Nachricht wird in die M-box inq verlinkt. Die Nachricht kommt erst auf den Heap von P2, wenn sie von einem anderen Objekt auf dem Heap gebraucht wird.
Erlang Scheduler
Damit die Prozesse effizient ausgeführt werden, gibt es den Scheduler, welcher die Prozesse verwaltet. Dies ist ein preemptive auf cooperative scheduler. Ein Prozess kann nur an bestimmten Punkten die Ausführung entzogen werden. Die Ausführungszeit ist eingeschränkt mit Reductions. Reductions sind nicht genau definiert, jedoch zählt jeder Funktionsaufruf als Reduction. Da Erlang und Elixir keine Schleifen haben und generell es keine längere Zeit gibt, ohne Funktionsaufruf ist dies ein Mittel um die Ausführungszeit des Prozesses zu limitieren. Der Prozess geht im Status dann von running zu runnable. Die Prozesse verlieren zudem die Ausführung, wenn sie in ein receive gehen und keine passende Nachrichten vorhanden ist. Sie gehen dann in den waiting Status. Sie kommen in runnable Status wieder, wenn sie eine Message bekommen oder ein Timeout abgelaufen ist. Jeder Scheduler hat Zwei Queues, eine für die runnable und eine für die im waiting Status stehenden Prozesse. Die Ready Queue(runnable) ist zudem auf 3 Queues verteilt, je nach Priorität. Es werden erst Prozesse aus der Queue mit Priorität Max genommen, dann mit High und dann aus Normal, Low. In der Normal, Low Queue werden den Normal Prozessen einen Counter von 1 und den Low Prozessen einen Counter von 7 zugewiesen. Dieser wird reduziert, wenn ein Prozess ausgeführt werden soll. Ist der Counter auf 0, wird der Prozess ausgeführt andernfalls wird er ans Ende der Queue gesetzt. Falls ein Scheduler keine Prozesse hat, kann er Prozesse anderer Scheduler stehlen. Im SMP Mode kann zudem für jeden OS Thread ein Scheduler genutzt werden.
CSP (Comunicating sequential processes)
Das zweite theoretische Paper handelt von CSP (Comunicating sequential processes). Vorgestellt wurde es von C.A.R. Hoare in 1978. Die Hauptprämisse von ihm war es, das input, output und concurrency primitives einer Programmiersprache seien sollen. Er erwähnte, dass sonst erst nach dem Erstellen einer Programmiersprache diese Konzepte behandelt wurden. Er stellte in seinem Paper eine Beispielprogrammiersprache auf, welche zeigen soll, wie die Konzepte in einer Programmiersprache eingebunden werden können. Dabei löst er mit dieser Programmiersprache bekannte Probleme wie das Philosophenproblem. Die Prozesse in seiner Sprache können mit Kommandos miteinander kommunizieren, wie in der Abbildung zu sehen. Dabei kann mit dem ? Operator aus einem Quellprozess in eine Variable geschrieben werden und mit dem ! Operator einen Ausdruck in einen Prozess gegeben werden. Hierbei müssen die Prozesse sich untereinander mit dem Namen kennen. Er zeigt im Paper selbst alternative Konzepte auf. Eines davon ist die Kommunikation über benannte Ports in denen Variablen gesendet und gelesen werden können. Dieses Konzept ähnelt dem der Programmiersprache Go, welche als nächstes belichtet wird.
Go
Go ist eine Programmiersprache, welche von Mitarbeitern von Google 2009 entwickelt wurde. Sie ist objektorientiert, funktional und nebenläufig.
Die Typisierung ist statisch und stark. Wichtige Themen für das Erstellen von Go war der Development Speed. Die Syntax sollte einfach und prägnant sein(nur 25 Keywords). Der Compiler soll schnell sein und es sollte ein Mittelweg zwischen Sprachen wie C++ und Python gefunden werden. Auch Concurrency war ein wichtiger Teil. Go code kompiliert zu einer binary executeable, welche ein Runtime beinhaltet mit GC und weiteren Funktionalitäten.
Goroutines
Goroutines sind die Lösung für Concurrency in Go. In der Abbildung sieht man ein Beispiel, wie diese genutzt werden. Wir haben hier erst eine Funktion definiert, die ein string bekommt und diesen 5 Mal in 1 Sekunden Abschnitten ausgibt. In unserer main Funktion rufen wir diese Funktion zweimal mit "world" und "hello" auf. Wichtig ist hierbei das "go" keyword, welches dafür sorgt, dass die Funktion in einer Goroutine läuft. Das "go" keyword kann hierbei auch vor einer Funktionsdefinition stehen. Der Output zeigt, dass die Funktionen nicht sequentiell ausgeführt werden, sondern gleichzeitig.
Wenn wir nun zwischen Goroutines kommunizieren möchten, können wir dies mit Channels. Einen Channel können wir mit make(chan int) definieren. Wir können hierbei definieren, welchen Typen wir für den Channel benutzen. In den Channel schreiben wir mit c <- var und lesen mit var <- c. In dem Beispiel berechnen wir die Summe, jedoch mit zwei Goroutinen, welche jeweils die Hälfte des Arrays an Werten bekommen. Diese schreiben die Werte in den Channel und diese Werte werden ausgelesen in die Variablen x und y. Das Lesen und Schreiben blockiert die derzeitige Goroutine solange kein anderer aus dem Channel liest oder sendet je nach Operation.
Dafür gibt es Buffered Channels, diese können mehre Werte aufnehmen je nachdem, wie viele spezifiziert wurden. Das Schreiben, blockiert dadurch erst, wenn der Buffer voll ist oder der Buffer leer ist und gelesen wird.
Das select statement ermöglicht es auf mehrere Channel zu lauschen und falls einer einen Wert hat, wird dieser ausgeführt. Wenn mehrere ausgeführt werden können, wird einer von diesen ausgewählt. Im Beispiel wird dies genutzt, um die Funktion abzubrechen, wenn keine Zahlen mehr gesendet werden.
Goroutines in der Laufzeitumgebung
Goroutines sind in der Laufzeitumgebung als type g struct definiert. In der Abbildung kann man ein paar der wichtigen Attribute einer Goroutine erkennen. Die Goroutine besitzt eines Stack dessen Mindestgröße 2kb beträgt. Er kann dabei größer und kleiner werden. Beim Erweitern wird die Größe des vorherigen Stacks verdoppelt. Der alte Speicher wird dabei in den neuen kopiert und danach freigegeben. m beschreibt eine Verbindung zum derzeitigen OS Thread. sched ist dafür da Zustand zu speichern. Den Staus der Goroutine wird in atomicstatus festgehalten. Runnable, Running und waiting sind die für uns wichtigen Status. Neben diesen gibt es noch einige Weitere, welche nicht weiter beleuchtet werden. Die boolean Variablen activeStackChans und parkingOnChan sind wichtig für die Erweiterung und Verkleinerung des Stacks, damit vorher wichtige Bereiche abgesichert werden können.
Channels in der Laufzeitumgebung
Channels sind als type hchan struct definiert. Wichtig ist hierbei buf, welcher ein Pointer zu dem Array ist, in dem sich die derzeitigen Werte innerhalb des Channels befinden. recvq und sendq sind doubly linked list, welche Listen für die Empfänger und die Absender sind. Der lock wird hier genutzt, um die Operation einer Goroutine auf den Channel zu sichern. Beim Kommunizieren bei Buffered Channels gibt es 3 mögliche Szenarien:
Was in diesen Szenarien im Channel passiert wird nun beschrieben.
Dazu nehmen wir zwei Goroutinen G1 und G2. Vor jeder Aktion einer Goroutine auf einen Channel wird der lock des Channels genommen und danach wieder freigegeben.
Im 1. Szenario sendet G1 in den nicht vollen Channel. Dabei kopiert sie den Wert und schreibt in auf buf vom Channel. Danach liest G2 aus dem Channel. Dabei nimmt sie den Wert aus dem buf, macht eine Kopie und weist die Kopie der Variable zu.
Im 2. Szenario sendet G1 auf einen vollen Buffer. G1 fügt sich dabei der sendq des Channels zu. Der Channel gibt das Signal an den Scheduler, dass G1 jetzt im waiting Status ist. Dann kommt G2 und liest aus dem vollen buf. Hier nimmt G2 den Wert aus dem buf macht eine Kopie und weist die Kopie zu. Dann holt G2 G1 aus der sendq und schreibt den Wert von G1 in den buf. G2 gibt auch das Signal an den Scheduler, dass G1 wieder in den runnable Status gebracht werden kann.
Im 3. Szenario liest G2 aus einem leeren Buffer. G2 fügt sich hierbei der receivq hinzu und der Channel gibt dem Scheduler das Signal, dass G2 im waiting Status ist. G1 schreibt dann in den leeren Channel. Dabei schreibt G1 den Wert direkt in die Variable von G2 und holt diese aus der receivq. G1 gibt außerdem dem Scheduler das Signal G2 in den runnable Status zu bringen.
Das 3. Szenario wird bei unbuffered Channels auf beiden Seiten benutzt. Es wird direkt in die Variable gelesen oder geschrieben. Dieses Verhalten bei unbuffered und buffered Channels ist eine Optimierung, da es länger dauern würde, wenn die Goroutine aus dem wartenden Zustand dies tun würde.
Go Scheduler
Der Go Scheduler ist ein M:N Scheduler. Er weist M Goroutinen auf N OS-Threads zu. Die 3 Hauptbestandteile innerhalb des Schedulers sind G die schon besprochene Goroutine, M der ein OS-Thread innerhalb der Laufzeitumgebung abbildet, sowie P, welches ein Kontext darstellt oder auch einen logischen Prozessor. Die Anzahl dieser p kann mit der Variable GOMAXPROCS festgelegt werden. Standardmäßig ist dies die Anzahl der CPU Kerne. Diese P besitzen eine Local Queue in welcher G fürs Scheduling gebunden werden. Außerdem gibt es zwei Pools für inaktive M und P. Im Scheduler werden OS-Threads(M) an Kontexten(P) zugewiesen, welche selbst die Goroutinen binden. Dort wird dann die gerade laufende Goroutine ausgeführt. Es gibt 3. Szenarien, bei der eine laufende Goroutine in den Wartestatus gelangt und ausgetauscht wird, damit die Auslastung der Threads optimal genutzt wird.
Bei einem Systemaufruf ist der dazugehörige Thread ebenfalls blockiert. Der Kontext(P) entfernt deswegen den Thread mit der dazugehörigen Goroutine um zu versuchen einen neuen inaktiven Thread nutzen zu können. Wenn die Goroutine nicht mehr durch den Systemaufruf blockiert ist, versucht der Thread sich an einen freien Kontext zu binden. Falls dies nicht möglich ist, wird die Goroutine der Global Run Queue hinzugefügt
Es gibt einen Network Poller, welcher einen eigenen OS-Thread besitzt. Dieser nimmt Goroutinen auf, welche einen Netzwerkaufruf durchführen. Wenn der Aufruf zu Ende ist, führt der Network Poller die Goroutine wieder in die Local Run Queue des vorherigen Kontextes.
Wie eben schon besprochen wird die Goroutine in dem Channel gespeichert. Wenn diese dann wieder runnable ist, wird sie der Local Run Queue des Kontextes hinzugefügt
Die Kontexte fragen die Global Run Queue periodisch ab und falls sich dort Goroutinen befinden, fügt der Kontext sie in seine Local Run Queue hinzu. Falls die Local Run Queue eines Kontextes leer ist, kann dieser entweder Goroutinen aus der Global Run Queue nehmen oder von anderen Kontexten Goroutinen stehlen. Dabei nimmt er die Hälfte der Goroutinen.
Dies war mein Blog über das Aktor Modell, CSP und deren Implementierungen in Elixir und Go. Ich hoffe, es war interessant zu lesen.
Quellen
Beta Was this translation helpful? Give feedback.
All reactions