Einführung in Linda
Was ist Linda?
Linda ist ein Konzept im Bereich der konkurrenten Programmierung. Linda verwendet zur Kommunikation
- asynchrones und
- broadcast message passing
und unterscheidet sich daher grundlegend von Ada (synchron, Sender kennt Empfänger).
Linda ist also unabhängig von
- Zeit: Zwei Prozesse müssen nicht zur gleichen Zeit existieren um zu kommunizieren.
- Raum: Die Adressierung erfolgt nicht wie zB in Ada über einen Task-Namen sondern benutzt das Blackboard-Prinzip zur Kommunikation.
Linda ist jedoch keine Programmiersprache, sondern besteht aus einigen Funktionen [primitives] die in andere Programmiersprachen eingebettet werden können. Dazu später mehr.
Der Tupelraum [tupel space]
Ein Prozeß, der eine neue Aufgabe erzeugt, die er nicht sofort selbst erledigt, stellt diese auf ein Blackboard. Das ist eine Stelle, auf die auch alle anderen Prozesse zugreifen können, ist also "shared memory".
Dieses Blackboard heißt in Linda "tuple space" (Tupelraum) und ist folgendermaßen aufgebaut:
Wie eine Tabelle ohne festgelegter Spaltenanzahl und Spaltentyp. Das heißt jeder Eintrag, genannt Tupel, in diesem Tupelraum hat eine gewisse Anzahl von Parametern.
Die Stärke (das Geniale) von Linda liegt darin, daß ein Tupel auch formale Elemente [formal elements] enthalten kann. Die Parameter können nicht nur aktuell, sondern auch formell sein. Als Elemente eines Tupels wird also auch eine Typangabe akzeptiert.
Parameter ::= Wert | Typ
Tupel ::= Parameter {, Parameter}
Tupelraum ::= Tupel {, Tupel}
|
Ein Tupel soll so etwas wie eine Aufgabe beschreiben, wobei man den gewünschten ausführenden Prozeß (Prozeßnummer), eine Aufgabenkennung oder den aufrufenden Prozeß mit in das Tupel eintragen kann oder nicht. Es muß nur die Eindeutigkeit gewährleistet sein.
Manipulationen im Tupelraum
Zum Eintragen eines Tupels in den Tupelraum bzw. zum Auslesen eines Tupels aus den Tupelraum gibt es folgende Aufrufe [primitives]:
Output(T) | Trägt das Tupel T in den Tupelraum ein. |
Input(T) | Entfernt ein passendes Tupel aus dem Tupelraum und bindet die formalen Parameter. Falls kein passenden Tupel gefunden wird, wartet es auf ein passendes. |
Read(T) | Wie Input, entfernt aber das Tupel nicht. |
Try_Input(T) | Wie Input, wartet aber nicht, wenn kein passendes Tupel vorhanden ist. |
Try_Read(T) | Wie Read, wartet aber nicht, wenn kein passendes Tupel vorhanden ist. |
Zwei Tupel passen aufeinander [are matching], wenn die aktuellen Parameter übereinstimmen und die formalen Parameter des einen dem Typ des aktuellen Parameters des anderen Tupels entsprechen.
Beispiel:
Output(1, 'A')
Input(I: integer; C: character)
Output stellt das Tupel (1, 'A') in den Tupelraum. Input liest den Tupelraum und findet (1, 'A') als passendes Tupel, denn 1 ist vom Typ integer und 'A' ist vom Typ character. Die formalen Parameter werden gebunden (i:= 1, c:='A'). Das Tupel wird aus dem Tupelraum entfernt.
Anstelle von Input(I: integer, C: character) wäre zB auch folgendes möglich:
Input(I: integer; 'A')
Auch hier würde das Tupel (1, 'A') passen. I: integer würde mit 1 gebunden.
Einfaches Beispiel
Es soll folgende einfache Aufgabe gelöst werden:
Berechne das Produkt aus 2 und 3, bzw. 4 und 5 und drucke die Ergebnisse aus.
Eine "Ada"-ähnliche Lösung könnte etwa so aussehen:
Task 1 |
...
prod1, prod2: natural;
begin
output ('multipliziere', 2, 3);
output ('multipliziere', 4, 5);
input ('Produkt', prod1: natural);
input ('Produkt', prod2: natural);
print ("Ergebnisse: " & prod1 & " " & prod2);
end; |
Task 2 und 3
|
...
input ('multipliziere', a: natural, b: natural);
output ('Produkt', a*b);
end; |
Dies führt zu folgendem Ergebnis:
Ergebnisse: 6 20
bzw.
Ergebnisse: 20 6
Je nachdem, ob Task 2 oder Task 3 als erster auf den Tupelraum zugreift.
Matrix Multiplikation in Linda
Geben seien folgende Matrizen A und B:
1 2 3 1 1 1
A = 4 5 6 und B = 0 2 1
7 8 9 2 1 1
Gesucht ist C = A * B.
Durch folgende Anweisungen werden die Daten der Matrizen in den Tupelraum geschrieben.
Output('A', 1, (1, 2, 3)); -- rows of first matrix
Output('A', 2, (4, 5, 6));
Output('A', 3, (7, 8, 9));
Output('B', 1, (1, 0, 2)); -- columns of second matrix
Output('B', 2, (1, 2, 1));
Output('B', 3, (1, 1, 1));
Output("Next", 1); -- next job counter
Zum Auslesen und zur Anzeige der Daten könnte ein Ada-Programm etwa so aussehen: Das Programm kann parallel zur eigentlichen Multiplikation ausgeführt werden:
for i in 1..3 loop
for j in 1..3 loop
INPUT('C', i: integer, j: integer, C: integer);
print C(i, j);
end loop;
end loop;
Die Arbeit der Matrixmultiplikation wird durch "worker"-Prozesse erledigt. Dabei ist es egal,
ob es mehrere oder nur einen "worker"-Prozeß gibt.
Ein "Worker"-Prozeß könnte wie folgt aussehen:
task body workers is
... -- local data
... -- declarations
begin
loop
INPUT("Next", element); -- get job number
OUTPUT("Next", element + 1); -- put next job number
exit when element > 3 * 3; -- check for termination
i := (element - 1) / 3 + 1; -- compute row number
j := (element - 1) mod 3 + 1; -- compute column number
row_tuple := READ('A', i, v1); -- get row
col_tuple := READ('B', j, v2); -- get coloumn
x := inner_product(v1, v2); -- compute result
OUTPUT('C', i, j, x); -- put result
end loop;
end workers;