Rendezvous
You are encouraged to solve this task according to the task description, using any language you may know.
Demonstrate the “rendezvous” communications technique by implementing a printer monitor.
Detailed Description of Programming Task
Rendezvous is a synchronization mechanism based on procedural decomposition. Rendezvous is similar to a procedure call with the difference that the caller and the callee belong to different tasks. The called procedure is usually called an entry point of the corresponding task. A call to an entry point is synchronous, i.e. the caller is blocked until completion. For the caller a call to the entry point is indivisible. Internally it consists of:
- Waiting for the callee ready to accept the rendezvous;
- Engaging the rendezvous (servicing the entry point).
The caller may limit the waiting time to the callee to accept the rendezvous. I.e. a rendezvous request can be aborted if not yet accepted by the callee. When accepted the rendezvous is processed until its completion. During this time the caller and the callee tasks stay synchronized. Which context is used to process the rendezvous depends on the implementation which may wish to minimize context switching.
The callee task may accept several rendezvous requests:
- Rendezvous to the same entry point from different tasks;
- Rendezvous to different entry points.
The callee accepts one rendezvous at a time.
Language mechanism of exceptions (if any) has to be consistent with the rendezvous. In particular when an exception is propagated out of a rendezvous it shall do in both tasks. The exception propagation is synchronous within the rendezvous and asynchronous outside it.
An engaged rendezvous can be requeued by the callee to another entry point of its task or to another task, transparently to the caller.
Differently to messages which are usually asynchronous, rendezvous are synchronous, as it was stated before. Therefore a rendezvous does not require marshaling the parameters and a buffer to keep them. Further, rendezvous can be implemented without context switch. This makes rendezvous a more efficient than messaging.
Rendezvous can be used to implement monitor synchronization objects. A monitor guards a shared resource. All users of the resource request a rendezvous to the monitor in order to get access to the resource. Access is granted by accepting the rendezvous for the time while the rendezvous is serviced.
Language task
Show how rendezvous are supported by the language. If the language does not have rendezvous, provide an implementation of them based on other primitives.
Use case task
Implement a printer monitor. The monitor guards a printer. There are two printers main and reserve. Each has a monitor that accepts a rendezvous Print with a text line to print of the printer. The standard output may serve for printing purpose. Each character of the line is printed separately in order to illustrate that lines are printed indivisibly. Each printer has ink for only 5 lines of text. When the main printer runs out of ink it redirects its requests to the reserve printer. When that runs out of ink too, Out_Of_Ink exception propagates back to the caller. Create two writer tasks which print their plagiarisms on the printer. One does Humpty Dumpty, another Mother Goose.
Ada
Ada has integrated rendezvous support. The caller calls to a rendezvous using the name of the task suffixed by the entry point name and the parameters. An entry point can be called using timed entry call statement which allow limit waiting time:
select
Server.Wake_Up (Parameters);
or delay 5.0;
-- No response, try something else
...
end select;
The task accepts a rendezvous using accept statement. The statement can contain body which implements the rendezvous. When several rendezvous need to be accepted a selective accept statement can be used. For example:
select
accept Wake_Up (Parameters : Work_Item) do
Current_Work_Item := Parameters;
end;
Process (Current_Work_Item);
or accept Shut_Down;
exit; -- Shut down requested
end select;
Entry points in the selective accept can be guarded by Boolean expressions which close the entry point when the expression yield false.
A task may requeue rendezvous request from the body of an accept statement to an entry point of the same or another task if the parameter profile of the entry point is compatible. The requeue statement may contain clause 'with abort which allows the caller to abort the request when it waits for other task to accept it. Without the clause the request is protected from abortion. This might be useful when the first task initiates processing of the request and the side effect of this action need to be removed when processing is completed.
The task
with Ada.Text_IO; use Ada.Text_IO;
procedure Rendezvous is
Out_Of_Ink : exception;
type Printer;
type Printer_Ptr is access all Printer;
task type Printer (ID : Natural; Backup : Printer_Ptr) is
entry Print (Line : String);
end Printer;
task body Printer is
Ink : Natural := 5;
begin
loop
begin
select
accept Print (Line : String) do
if Ink = 0 then
if Backup = null then
raise Out_Of_Ink;
else
requeue Backup.Print with abort;
end if;
else
Put (Integer'Image (ID) & ": ");
for I in Line'Range loop
Put (Line (I));
end loop;
New_Line;
Ink := Ink - 1;
end if;
end Print;
or terminate;
end select;
exception
when Out_Of_Ink =>
null;
end;
end loop;
end Printer;
Reserve : aliased Printer (2, null);
Main : Printer (1, Reserve'Access);
task Humpty_Dumpty;
task Mother_Goose;
task body Humpty_Dumpty is
begin
Main.Print ("Humpty Dumpty sat on a wall.");
Main.Print ("Humpty Dumpty had a great fall.");
Main.Print ("All the king's horses and all the king's men");
Main.Print ("Couldn't put Humpty together again.");
exception
when Out_Of_Ink =>
Put_Line (" Humpty Dumpty out of ink!");
end Humpty_Dumpty;
task body Mother_Goose is
begin
Main.Print ("Old Mother Goose");
Main.Print ("When she wanted to wander,");
Main.Print ("Would ride through the air");
Main.Print ("On a very fine gander.");
Main.Print ("Jack's mother came in,");
Main.Print ("And caught the goose soon,");
Main.Print ("And mounting its back,");
Main.Print ("Flew up to the moon.");
exception
when Out_Of_Ink =>
Put_Line (" Mother Goose out of ink!");
end Mother_Goose;
begin
null;
end Rendezvous;
Sample output:
1: Old Mother Goose
1: Humpty Dumpty sat on a wall.
1: When she wanted to wander,
1: Humpty Dumpty had a great fall.
1: Would ride through the air
2: All the king's horses and all the king's men
2: On a very fine gander.
2: Couldn't put Humpty together again.
2: Jack's mother came in,
2: And caught the goose soon,
Mother Goose out of ink!
AutoHotkey
OnMessage(0x4a, "PrintMonitor")
SetTimer, print2, 400
print1:
print("Old Mother Goose")
print("When she wanted to wander,")
print("Would ride through the air")
print("On a very fine gander.")
print("Jack's mother came in,")
print("And caught the goose soon,")
print("And mounting its back,")
print("Flew up to the moon.")
Return
print2:
SetTimer, print2, Off
print("Humpty Dumpty sat on a wall.")
print("Humpty Dumpty had a great fall.")
print("All the king's horses and all the king's men")
print("Couldn't put Humpty together again.")
Return
print(message)
{
Static StringToSend
StringToSend := message
Gui +LastFound
VarSetCapacity(CopyDataStruct, 12, 0)
NumPut(StrLen(StringToSend) + 1, CopyDataStruct, 4)
NumPut(&StringToSend, CopyDataStruct, 8)
SendMessage, 0x4a, 0, &CopyDataStruct
If ErrorLevel
MsgBox out of ink
Sleep, 200
Return
}
PrintMonitor(wParam, lParam, msg)
{
Static ink = 5
Global printed
Critical
If ink
{
StringAddress := NumGet(lParam + 8)
StringLength := DllCall("lstrlen", UInt, StringAddress)
VarSetCapacity(CopyOfData, StringLength)
DllCall("lstrcpy", "str", CopyOfData, "uint", StringAddress)
printed .= "primaryprinter: " . CopyOfData . "`n"
ToolTip, primary printer`n: %printed%
ink--
}
Else
{
OnMessage(0x4a, "Reserve")
print(CopyOfData)
}
}
Reserve(wParam, lParam, msg)
{
Static ink = 5
Global printed
Critical
If ink
{
StringAddress := NumGet(lParam + 8)
StringLength := DllCall("lstrlen", UInt, StringAddress)
VarSetCapacity(CopyOfData, StringLength)
DllCall("lstrcpy", "str", CopyOfData, "uint", StringAddress)
printed .= "reserveprinter: " . CopyOfData . "`n"
ToolTip, Reserve printer`n: %printed%
ink--
}
Else
Return -1
}
C
Pthreads implementation
This uses POSIX threads to implement a subset of the Ada functionality and primarily focuses on the synchronization aspect. C does not have exceptions, so return values are used to signal errors. Multiple threads can enter a rendezvous at once, and a single thread can accept them. No attempt is made to implement selective accept statements or timeouts (though pthreads does have pthread_cond_timedwait()).
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
/* The language task, implemented with pthreads for POSIX systems. */
/* Each rendezvous_t will be accepted by a single thread, and entered
* by one or more threads. accept_func() only returns an integer and
* is always run within the entering thread's context to simplify
* handling the arguments and return value. This somewhat unlike an
* Ada rendezvous and is a subset of the Ada rendezvous functionality.
* Ada's in and out parameters can be simulated via the void pointer
* passed to accept_func() to update variables owned by both the
* entering and accepting threads, if a suitable struct with pointers
* to those variables is used. */
typedef struct rendezvous {
pthread_mutex_t lock; /* A mutex/lock to use with the CVs. */
pthread_cond_t cv_entering; /* Signaled when a thread enters. */
pthread_cond_t cv_accepting; /* Signaled when accepting thread is ready. */
pthread_cond_t cv_done; /* Signaled when accept_func() finishes. */
int (*accept_func)(void*); /* The function to run when accepted. */
int entering; /* Number of threads trying to enter. */
int accepting; /* True if the accepting thread is ready. */
int done; /* True if accept_func() is done. */
} rendezvous_t;
/* Static initialization for rendezvous_t. */
#define RENDEZVOUS_INITILIZER(accept_function) { \
.lock = PTHREAD_MUTEX_INITIALIZER, \
.cv_entering = PTHREAD_COND_INITIALIZER, \
.cv_accepting = PTHREAD_COND_INITIALIZER, \
.cv_done = PTHREAD_COND_INITIALIZER, \
.accept_func = accept_function, \
.entering = 0, \
.accepting = 0, \
.done = 0, \
}
int enter_rendezvous(rendezvous_t *rv, void* data)
{
/* Arguments are passed in and out of the rendezvous via
* (void*)data, and the accept_func() return value is copied and
* returned to the caller (entering thread). A data struct with
* pointers to variables in both the entering and accepting
* threads can be used to simulate Ada's in and out parameters, if
* needed. */
pthread_mutex_lock(&rv->lock);
rv->entering++;
pthread_cond_signal(&rv->cv_entering);
while (!rv->accepting) {
/* Nothing is accepting yet, keep waiting. pthreads will
* queue all waiting entries. The loop is needed to handle
* both race conditions and spurious wakeups. */
pthread_cond_wait(&rv->cv_accepting, &rv->lock);
}
/* Call accept_func() and copy the return value before leaving
* the mutex. */
int ret = rv->accept_func(data);
/* This signal is needed so that the accepting thread will wait
* for the rendezvous to finish before trying to accept again. */
rv->done = 1;
pthread_cond_signal(&rv->cv_done);
rv->entering--;
rv->accepting = 0;
pthread_mutex_unlock(&rv->lock);
return ret;
}
void accept_rendezvous(rendezvous_t *rv)
{
/* This accept function does not take in or return parameters.
* That is handled on the entry side. This is only for
* synchronization. */
pthread_mutex_lock(&rv->lock);
rv->accepting = 1;
while (!rv->entering) {
/* Nothing to accept yet, keep waiting. */
pthread_cond_wait(&rv->cv_entering, &rv->lock);
}
pthread_cond_signal(&rv->cv_accepting);
while (!rv->done) {
/* Wait for accept_func() to finish. */
pthread_cond_wait(&rv->cv_done, &rv->lock);
}
rv->done = 0;
rv->accepting = 0;
pthread_mutex_unlock(&rv->lock);
}
/* The printer use case task implemented using the above rendezvous
* implementation. Since C doesn't have exceptions, return values are
* used to signal out of ink errors. */
typedef struct printer {
rendezvous_t rv;
struct printer *backup;
int id;
int remaining_lines;
} printer_t;
typedef struct print_args {
struct printer *printer;
const char* line;
} print_args_t;
int print_line(printer_t *printer, const char* line) {
print_args_t args;
args.printer = printer;
args.line = line;
return enter_rendezvous(&printer->rv, &args);
}
int accept_print(void* data) {
/* This is called within the rendezvous, so everything is locked
* and okay to modify. */
print_args_t *args = (print_args_t*)data;
printer_t *printer = args->printer;
const char* line = args->line;
if (printer->remaining_lines) {
/* Print the line, character by character. */
printf("%d: ", printer->id);
while (*line != '\0') {
putchar(*line++);
}
putchar('\n');
printer->remaining_lines--;
return 1;
}
else if (printer->backup) {
/* "Requeue" this rendezvous with the backup printer. */
return print_line(printer->backup, line);
}
else {
/* Out of ink, and no backup available. */
return -1;
}
}
printer_t backup_printer = {
.rv = RENDEZVOUS_INITILIZER(accept_print),
.backup = NULL,
.id = 2,
.remaining_lines = 5,
};
printer_t main_printer = {
.rv = RENDEZVOUS_INITILIZER(accept_print),
.backup = &backup_printer,
.id = 1,
.remaining_lines = 5,
};
void* printer_thread(void* thread_data) {
printer_t *printer = (printer_t*) thread_data;
while (1) {
accept_rendezvous(&printer->rv);
}
}
typedef struct poem {
char* name;
char* lines[];
} poem_t;
poem_t humpty_dumpty = {
.name = "Humpty Dumpty",
.lines = {
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men",
"Couldn't put Humpty together again.",
""
},
};
poem_t mother_goose = {
.name = "Mother Goose",
.lines = {
"Old Mother Goose",
"When she wanted to wander,",
"Would ride through the air",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon.",
""
},
};
void* poem_thread(void* thread_data) {
poem_t *poem = (poem_t*)thread_data;
for (unsigned i = 0; poem->lines[i] != ""; i++) {
int ret = print_line(&main_printer, poem->lines[i]);
if (ret < 0) {
printf(" %s out of ink!\n", poem->name);
exit(1);
}
}
return NULL;
}
int main(void)
{
pthread_t threads[4];
pthread_create(&threads[0], NULL, poem_thread, &humpty_dumpty);
pthread_create(&threads[1], NULL, poem_thread, &mother_goose);
pthread_create(&threads[2], NULL, printer_thread, &main_printer);
pthread_create(&threads[3], NULL, printer_thread, &backup_printer);
pthread_join(threads[0], NULL);
pthread_join(threads[1], NULL);
pthread_cancel(threads[2]);
pthread_cancel(threads[3]);
return 0;
}
OpenMP implementation
Basically just synched threads doing printing: since task didn't ask for service type or resource enumeration, and "message passing is stupid" (c.f. talk), the guarding thread is no more than a glorified mutex, hence completely cut out, leaving the threads directly check ink and do print.
#include <stdio.h>
#include <unistd.h>
#include <omp.h>
typedef struct printer printer;
struct printer { int id, ink; };
printer pnt_main = { 1, 5 };
printer pnt_backup = { 2, 5 };
int print(const char * text, const char **error)
{
#pragma omp critical
{
printer *p = &pnt_main;
if (!p->ink) p = &pnt_backup;
if (!p->ink)
*error = "Out of ink";
else {
*error = 0;
p->ink--;
printf("%d | ", p->id, p->ink);
while (*text != '\0') {
putchar(*(text++));
fflush(stdout);
usleep(30000);
}
putchar('\n');
}
}
return 0 != *error;
}
const char *humpty[] = {
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again."
};
const char *goose[] = {
"Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon."
};
int main()
{
int i, j, len;
const char *msg, **text;
omp_set_num_threads(2);
#pragma omp parallel for private(text, msg, len, j)
for (i = 0; i < 2; i++) {
text = i ? goose : humpty;
len = (i ? sizeof(goose) : sizeof(humpty) ) / sizeof(const char*);
for (j = 0; j < len; j++) {
usleep(100000);
if (print(text[j], &msg)) {
fprintf(stderr, "Error: %s\n", msg);
break;
}
}
}
return 0;
}
C++
#include <condition_variable>
#include <cstdint>
#include <exception>
#include <iostream>
#include <mutex>
#include <string>
#include <thread>
#include <vector>
std::mutex mutex;
std::condition_variable condition_variable;
bool goose_working = true;
bool humpty_working = true;
uint32_t turn = 0;
class out_of_ink_exception : public std::exception { };
class Printer {
public:
Printer(const std::string& name, const uint32_t& client_ink_level)
: name(name), client_ink_level(client_ink_level) { }
bool operator==(const Printer& other) const {
return name == other.name;
}
std::string name;
uint32_t client_ink_level;
};
Printer reserve("Reserve", 5);
Printer primary("Primary", 5);
Printer printer = primary;
void display(const std::string& text) {
if ( printer == primary && printer.client_ink_level == 0 ) {
printer = reserve;
}
if ( printer.client_ink_level > 0 ) {
printer.client_ink_level--;
std::cout << "(" + printer.name + ") " + text << std::endl;
} else {
std::cout << " Printer out of ink" << std::endl;
throw out_of_ink_exception();
}
}
auto messenger =
[](const std::vector<std::string>& message, const uint32_t& my_turn, const uint32_t& turn_count) {
std::unique_lock<std::mutex> lock(mutex);
uint64_t index = 0;
while ( goose_working || humpty_working ) {
condition_variable.wait(lock, [&]() { return turn % turn_count == my_turn; });
if ( index < message.size() ) {
try {
display(message[index++]);
} catch (const out_of_ink_exception& ex) {
goose_working = false;
humpty_working = false;
}
} else {
if ( my_turn == 0 ) {
goose_working = false;
} else {
humpty_working = false;
}
}
turn++;
condition_variable.notify_one();
}
};
int main() {
const std::vector<std::string> goose_text = { "Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon." };
const std::vector<std::string> humpty_text = { "Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again." };
std::thread goose_thread(messenger, goose_text, 0, 2);
std::thread humpty_thread(messenger, humpty_text, 1, 2);
goose_thread.join();
humpty_thread.join();
}
- Output:
(Primary) Old Mother Goose,
(Primary) Humpty Dumpty sat on a wall.
(Primary) When she wanted to wander,
(Primary) Humpty Dumpty had a great fall.
(Primary) Would ride through the air,
(Reserve) All the king's horses and all the king's men,
(Reserve) On a very fine gander.
(Reserve) Couldn't put Humpty together again.
(Reserve) Jack's mother came in,
(Reserve) And caught the goose soon,
Printer out of ink
D
import std.stdio, std.array, std.datetime, std.exception,
std.concurrency, core.thread, core.atomic;
final class OutOfInk: Exception {
this() pure nothrow {
super("Out of ink.");
}
}
struct Printer {
string id;
size_t ink;
void printIt(in string line) {
enforce(ink != 0, new OutOfInk);
writefln("%s: %s", id, line);
ink--;
}
}
/// Treats shared lvalue as if it is thread-local.
ref assumeThreadLocal(T)(ref shared T what) pure nothrow {
return *cast(T*)&what;
}
struct RendezvousPrinter {
Printer[] printers;
void print(const(string)[] lines) shared {
OutOfInk savedException;
// Lightweight mutual exclusion
// using shared atomic bool.
shared static bool mutex;
void lock() {
while (!cas(&mutex, false, true))
Thread.sleep(1.hnsecs);
}
void unlock() nothrow {
assert(mutex.atomicLoad!(MemoryOrder.acq));
mutex.atomicStore!(MemoryOrder.rel)(false);
}
while (!lines.empty) {
if (printers.empty) {
// No more printers to try.
assert(savedException !is null);
throw savedException;
}
try {
{
lock;
scope(exit) unlock;
printers.front.assumeThreadLocal
.printIt(lines.front);
}
lines.popFront;
// Increase the chance of interleaved output.
Thread.sleep(10.msecs);
} catch (OutOfInk exc) {
savedException = exc;
// Switch to the next printer.
lock;
scope(exit) unlock;
printers.assumeThreadLocal.popFront;
}
}
}
}
void humptyDumptyTask(shared ref RendezvousPrinter rendezvous) {
const humptyDumpty = [
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again."];
rendezvous.print(humptyDumpty);
}
void motherGooseTask(shared ref RendezvousPrinter rendezvous) {
const motherGoose = ["Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon."];
rendezvous.print(motherGoose);
}
void main() {
shared rendezvous = RendezvousPrinter
([Printer("main", 5), Printer("reserve", 5)]);
spawn(&humptyDumptyTask, rendezvous);
spawn(&motherGooseTask, rendezvous);
}
- Output:
main: Humpty Dumpty sat on a wall. main: Old Mother Goose, main: When she wanted to wander, main: Humpty Dumpty had a great fall. main: Would ride through the air, reserve: On a very fine gander. reserve: All the king's horses and all the king's men, reserve: Jack's mother came in, reserve: And caught the goose soon, reserve: Couldn't put Humpty together again. rendezvous2.OutOfInk @rendezvous2.d(6): Out of ink. ---------------- 0x0040609F 0x004021FC 0x0040243A 0x00405F47 0x00412D55 0x00433A48 0x77BB1603 in RtlInitializeExceptionChain 0x77BB15D6 in RtlInitializeExceptionChain
Erlang
There is no rendezvous in Erlang. To fulfil the task description I have implemented rendezvous with message passing (which is in Erlang). Doing these printers directly with message passing would have been simpler (in Erlang).
-module( rendezvous ).
-export( [task/0] ).
task() ->
Printer_pid = erlang:spawn( fun() -> printer(1, 5) end ),
Reserve_printer_pid = erlang:spawn( fun() -> printer(2, 5) end ),
Monitor_pid = erlang:spawn( fun() -> printer_monitor(Printer_pid, Reserve_printer_pid) end ),
erlang:spawn( fun() -> print(Monitor_pid, humpty_dumpty()) end ),
erlang:spawn( fun() -> print(Monitor_pid, mother_goose()) end ).
humpty_dumpty() ->
["Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again."].
mother_goose() ->
["Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon."].
print( Pid, Lines ) ->
io:fwrite( "Print ~p started~n", [erlang:self()] ),
print( Pid, Lines, infinity ).
print( _Pid, [], _Timeout ) -> ok;
print( Pid, [Line | T], Timeout ) ->
print_line( Pid, Line, Timeout ),
print_line_done(),
print( Pid, T, Timeout ).
print_line( Pid, Line, Timeout ) ->
Pid ! {print, Line, erlang:self()},
receive
{print, started} -> ok
after Timeout -> erlang:throw( timeout )
end.
print_line_done() ->
receive
{printer, ok} -> ok;
{printer, out_of_ink} -> erlang:throw( out_of_ink )
end.
printer( N, 0 ) ->
receive
{print, _Line, Pid} -> Pid ! {printer, out_of_ink}
end,
printer( N, 0 );
printer( N, Ink ) ->
receive
{print, Line, Pid} ->
Pid ! {printer, ok},
io:fwrite( "~p: ", [N] ),
[io:fwrite("~c", [X]) || X <- Line],
io:nl()
end,
printer( N, Ink - 1 ).
printer_monitor( Printer, Reserve ) ->
{Line, Pid} = printer_monitor_get_line(),
Result = printer_monitor_print_line( Printer, Line ),
printer_monitor_reserve( Result, Reserve, Line, Pid ),
printer_monitor( Printer, Reserve ).
printer_monitor_get_line() ->
receive
{print, Line, Pid} ->
Pid ! {print, started},
{Line, Pid}
end.
printer_monitor_print_line( Printer_pid, Line ) ->
Printer_pid ! {print, Line, erlang:self()},
receive
{printer, Result} -> Result
end.
printer_monitor_reserve( ok, _Reserve_pid, _Line, Pid ) -> Pid ! {printer, ok};
printer_monitor_reserve( out_of_ink, Reserve_pid, Line, Pid ) -> Reserve_pid ! {print, Line, Pid}.
- Output:
The first printouts are there to show the identity of the processes that print. It makes it easier to match the exception to one of them and not to some other process.
53> rendezvous:task().
Print <0.251.0> started
Print <0.252.0> started
1: Humpty Dumpty sat on a wall.
1: Old Mother Goose,
1: Humpty Dumpty had a great fall.
1: When she wanted to wander,
1: All the king's horses and all the king's men,
2: Would ride through the air,
2: Couldn't put Humpty together again.
2: On a very fine gander.
2: Jack's mother came in,
2: And caught the goose soon,
=ERROR REPORT==== 22-Sep-2013::12:09:56 ===
Error in process <0.252.0> with exit value: {{nocatch,out_of_ink},[{rendezvous,print_line_done,0,[{file,"rendezvous.erl"},{line,48}]},{rendezvous,print,3,[{file,"rendezvous.erl"},{line,35}]}]}
F#
The rendezvous mechanism is realized by using F#'s mailbox processors to implement active objects.
It is possible to extract the boilerplate code into a reusable helper class which should be considered when using active objects a lot.
open System
type PrinterCommand = Print of string
// a message is a command and a facility to return an exception
type Message = Message of PrinterCommand * AsyncReplyChannel<Exception option>
// thrown if we have no more ink (and neither has our possible backup printer)
exception OutOfInk
type Printer(id, ?backup:Printer) =
let mutable ink = 5
// the actual printing logic as a private function
let print line =
if ink > 0 then
printf "%d: " id
Seq.iter (printf "%c") line
printf "\n"
ink <- ink - 1
else
match backup with
| Some p -> p.Print line
| None -> raise OutOfInk
// use a MailboxProcessor to process commands asynchronously;
// if an exception occurs, we return it to the calling thread
let agent = MailboxProcessor.Start( fun inbox ->
async {
while true do
let! Message (command, replyChannel) = inbox.Receive()
try
match command with
| Print line -> print line
replyChannel.Reply None
with
| ex -> replyChannel.Reply (Some ex)
})
// public printing method:
// send Print command and propagate exception if one occurs
member x.Print line =
match agent.PostAndReply( fun replyChannel -> Message (Print line, replyChannel) ) with
| None -> ()
| Some ex -> raise ex
open System.Threading
do
let main = new Printer(id=1, backup=new Printer(id=2))
(new Thread(fun () ->
try
main.Print "Humpty Dumpty sat on a wall."
main.Print "Humpty Dumpty had a great fall."
main.Print "All the king's horses and all the king's men"
main.Print "Couldn't put Humpty together again."
with
| OutOfInk -> printfn " Humpty Dumpty out of ink!"
)).Start()
(new Thread(fun () ->
try
main.Print "Old Mother Goose"
main.Print "Would ride through the air"
main.Print "On a very fine gander."
main.Print "Jack's mother came in,"
main.Print "And caught the goose soon,"
main.Print "And mounting its back,"
main.Print "Flew up to the moon."
with
| OutOfInk -> printfn " Mother Goose out of ink!"
)).Start()
Console.ReadLine() |> ignore
Example output:
1: Old Mother Goose
1: Humpty Dumpty sat on a wall.
1: Would ride through the air
1: Humpty Dumpty had a great fall.
1: On a very fine gander.
2: All the king's horses and all the king's men
2: Jack's mother came in,
2: Couldn't put Humpty together again.
2: And caught the goose soon,
2: And mounting its back,
Mother Goose out of ink!
FreeBASIC
Subroutines and flow control structures implementation
Type Printer
tipo As String
ink As Integer
End Type
Sub Printer_New(Byref p As Printer, Byval tipo As String, Byval ink As Integer)
p.tipo = tipo
p.ink = ink
End Sub
Function Printer_ink(Byref p As Printer) As Integer
Return p.ink
End Function
Sub Printer_ink_Set(Byref p As Printer, Byval v As Integer)
p.ink = v
End Sub
Sub Printer_print(Byref p As Printer, Byval text As String)
Print p.tipo & ": ";
For i As Integer = 1 To Len(text)
Print Mid(text, i, 1);
Next
Print
p.ink -= 1
End Sub
Dim Shared As Printer ptrMain, ptrReserve
Printer_New(ptrMain, "Main ", 5)
Printer_New(ptrReserve, "Reserve", 5)
Dim Shared As String*44 hd(3) = {"Humpty Dumpty sat on a wall.", "Humpty Dumpty had a great fall.", "All the king's horses and all the king's men", "Couldn't put Humpty together again."}
Dim Shared As String*26 mg(7) = {"Old Mother Goose", "When she wanted to wander,", "Would ride through the air", "On a very fine gander.", "Jack's mother came in,", "And caught the goose soon,", "And mounting its back,", "Flew up to the moon."}
Function task(Byval nombre As String) As String
Dim As Integer i
Dim As String lines()
If nombre = "Humpty Dumpty" Then
Redim lines(Ubound(hd))
For i = 0 To Ubound(hd) : lines(i) = hd(i)
Next
Else
Redim lines(Ubound(mg))
For i = 0 To Ubound(mg) : lines(i) = mg(i)
Next
End If
For i = 0 To Ubound(lines)
If Printer_ink(ptrMain) > 0 Then
Printer_print(ptrMain, lines(i))
Elseif Printer_ink(ptrReserve) > 0 Then
Printer_print(ptrReserve, lines(i))
Else
Return "ERROR : Reserve printer ran out of ink in " & nombre & " task."
End If
Next
Return ""
End Function
Dim As String rhymes(1) = {"Humpty Dumpty", "Mother Goose"}
Dim As String tasks(1)
For i As Integer = 0 To 1
tasks(i) = task(rhymes(i))
If tasks(i) <> "" Then Print tasks(i): Exit For
Next
Sleep
- Output:
Main : Humpty Dumpty sat on a wall. Main : Humpty Dumpty had a great fall. Main : All the king's horses and all the king's men Main : Couldn't put Humpty together again. Main : Old Mother Goose Reserve: When she wanted to wander, Reserve: Would ride through the air Reserve: On a very fine gander. Reserve: Jack's mother came in, Reserve: And caught the goose soon, ERROR : Reserve printer ran out of ink in Mother Goose task.
Threads implementation
Const MAX_INK As Integer = 5
Type Printer
ID As Integer
Ink As Integer
Backup As Printer Ptr
Mutex As Any Ptr
End Type
Dim Shared Reserve As Printer
Dim Shared Main As Printer
Reserve.ID = 2
Reserve.Ink = MAX_INK
Reserve.Backup = 0
Reserve.Mutex = Mutexcreate()
Main.ID = 1
Main.Ink = MAX_INK
Main.Backup = @Reserve
Main.Mutex = Mutexcreate()
Dim Shared As String*44 humpty(3) = { _
"Humpty Dumpty sat on a wall.", "Humpty Dumpty had a great fall.", _
"All the king's horses and all the king's men", _
"Couldn't put Humpty together again." }
Dim Shared As String*26 goose(7) = {"Old Mother Goose", "When she wanted to wander,", _
"Would ride through the air", "On a very fine gander.", "Jack's mother came in,", _
"And caught the goose soon,", "And mounting its back,", "Flew up to the moon." }
Sub PrintLine(Byref p As Printer, Byval linea As String)
Mutexlock(p.Mutex)
If p.Ink = 0 Then
If p.Backup = 0 Then
Mutexunlock(p.Mutex)
If p.ID = 1 Then
Print " Humpty Dumpty out of ink!"
Elseif p.ID = 2 Then
Print " Mother Goose out of ink!"
End If
Mutexunlock(p.Mutex)
Else
PrintLine(*p.Backup, linea)
End If
Else
Print p.ID; ": "; linea
p.Ink -= 1
End If
Mutexunlock(p.Mutex)
End Sub
Sub HumptyDumpty(Param As Any Ptr)
For i As Integer = 0 To Ubound(humpty)
PrintLine(Main, humpty(i))
Next
End Sub
Sub MotherGoose(Param As Any Ptr)
For i As Integer = 0 To Ubound(goose)
PrintLine(Main, goose(i))
Next
End Sub
' Create threads
Dim HumptyThread As Any Ptr = Threadcreate(@HumptyDumpty, 0)
Dim GooseThread As Any Ptr = Threadcreate(@MotherGoose, 0)
' Wait for threads to finish
Threadwait(HumptyThread)
Sleep
- Output:
1: Humpty Dumpty sat on a wall.
1: Old Mother Goose
1: Humpty Dumpty had a great fall.
1: When she wanted to wander,
1: All the king's horses and all the king's men
2: Would ride through the air
2: Couldn't put Humpty together again.
2: On a very fine gander.
2: Jack's mother came in,
2: And caught the goose soon,
Mother Goose out of ink!
Mother Goose out of ink!
Go
package main
import (
"errors"
"fmt"
"strings"
"sync"
)
var hdText = `Humpty Dumpty sat on a wall.
Humpty Dumpty had a great fall.
All the king's horses and all the king's men,
Couldn't put Humpty together again.`
var mgText = `Old Mother Goose,
When she wanted to wander,
Would ride through the air,
On a very fine gander.
Jack's mother came in,
And caught the goose soon,
And mounting its back,
Flew up to the moon.`
func main() {
reservePrinter := startMonitor(newPrinter(5), nil)
mainPrinter := startMonitor(newPrinter(5), reservePrinter)
var busy sync.WaitGroup
busy.Add(2)
go writer(mainPrinter, "hd", hdText, &busy)
go writer(mainPrinter, "mg", mgText, &busy)
busy.Wait()
}
// printer is a type representing an abstraction of a physical printer.
// It is a type defintion for a function that takes a string to print
// and returns an error value, (hopefully usually nil, meaning no error.)
type printer func(string) error
// newPrinter is a constructor. The parameter is a quantity of ink. It
// returns a printer object encapsulating the ink quantity.
// Note that this is not creating the monitor, only the object serving as
// a physical printer by writing to standard output.
func newPrinter(ink int) printer {
return func(line string) error {
if ink == 0 {
return eOutOfInk
}
for _, c := range line {
fmt.Printf("%c", c)
}
fmt.Println()
ink--
return nil
}
}
var eOutOfInk = errors.New("out of ink")
// For the language task, rSync is a type used to approximate the Ada
// rendezvous mechanism that includes the caller waiting for completion
// of the callee. For this use case, we signal completion with an error
// value as a response. Exceptions are not idiomatic in Go and there is
// no attempt here to model the Ada exception mechanism. Instead, it is
// idomatic in Go to return error values. Sending an error value on a
// channel works well here to signal completion. Go unbuffered channels
// provide synchronous rendezvous, but call and response takes two channels,
// which are bundled together here in a struct. The channel types are chosen
// to mirror the parameter and return types of "type printer" defined above.
// The channel types here, string and error are both "reference types"
// in Go terminology. That is, they are small things containing pointers
// to the actual data. Sending one on a channel does not involve copying,
// or much less marshalling string data.
type rSync struct {
call chan string
response chan error
}
// "rendezvous Print" requested by use case task.
// For the language task though, it is implemented here as a method on
// rSync that sends its argument on rSync.call and returns the result
// received from rSync.response. Each channel operation is synchronous.
// The two operations back to back approximate the Ada rendezvous.
func (r *rSync) print(data string) error {
r.call <- data // blocks until data is accepted on channel
return <-r.response // blocks until response is received
}
// monitor is run as a goroutine. It encapsulates the printer passed to it.
// Print requests are received through the rSync object "entry," named entry
// here to correspond to the Ada concept of an entry point.
func monitor(hardPrint printer, entry, reserve *rSync) {
for {
// The monitor goroutine will block here waiting for a "call"
// to its "entry point."
data := <-entry.call
// Assuming the call came from a goroutine calling rSync.print,
// that goroutine is now blocked, waiting for this one to send
// a response.
// attempt output
switch err := hardPrint(data); {
// consider return value from attempt
case err == nil:
entry.response <- nil // no problems
case err == eOutOfInk && reserve != nil:
// Requeue to "entry point" of reserve printer monitor.
// Caller stays blocked, and now this goroutine blocks until
// it gets a response from the reserve printer monitor.
// It then transparently relays the response to the caller.
entry.response <- reserve.print(data)
default:
entry.response <- err // return failure
}
// The response is away. Loop, and so immediately block again.
}
}
// startMonitor can be seen as an rSync constructor. It also
// of course, starts the monitor for which the rSync serves as entry point.
// Further to the langauge task, note that the channels created here are
// unbuffered. There is no buffer or message box to hold channel data.
// A sender will block waiting for a receiver to accept data synchronously.
func startMonitor(p printer, reservePrinter *rSync) *rSync {
entry := &rSync{make(chan string), make(chan error)}
go monitor(p, entry, reservePrinter)
return entry
}
// Two writer tasks are started as goroutines by main. They run concurrently
// and compete for printers as resources. Note the call to "rendezvous Print"
// as requested in the use case task and compare the syntax,
// Here: printMonitor.print(line);
// Ada solution: Main.Print ("string literal");
func writer(printMonitor *rSync, id, text string, busy *sync.WaitGroup) {
for _, line := range strings.Split(text, "\n") {
if err := printMonitor.print(line); err != nil {
fmt.Printf("**** writer task %q terminated: %v ****\n", id, err)
break
}
}
busy.Done()
}
Output:
Humpty Dumpty sat on a wall. Old Mother Goose, Humpty Dumpty had a great fall. When she wanted to wander, All the king's horses and all the king's men, Would ride through the air, Couldn't put Humpty together again. On a very fine gander. Jack's mother came in, And caught the goose soon, **** writer task "mg" terminated: out of ink ****
Java
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
import java.util.function.Supplier;
public final class Rendezvous {
public static void main(String[] args) throws InterruptedException, ExecutionException {
List<String> motherGooseText = List.of( "Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon." );
List<String> humptyDumptyText = List.of( "Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again." );
Printer reserve = new Printer("Reserve", Optional.empty(), System.out);
Printer main = new Printer("Main", Optional.of(reserve), System.out);
Messenger motherGoose = new Messenger(motherGooseText, main);
Messenger humptyDumpty = new Messenger(humptyDumptyText, main);
while ( CompletableFuture.supplyAsync(motherGoose).get() |
CompletableFuture.supplyAsync(humptyDumpty).get() ) { }
}
}
final class Messenger implements Supplier<Boolean> {
public Messenger(List<String> aMessage, Printer aPrinter) {
message = new ArrayList<String>(aMessage);
iterator = message.iterator();
printer = aPrinter;
}
@Override
public Boolean get() {
if ( iterator.hasNext() ) {
try {
printer.display(iterator.next());
} catch (OutOfInkException exception) {
return false;
}
return true;
}
return false;
}
private List<String> message;
private Iterator<String> iterator;
private Printer printer;
}
final class Printer {
public Printer(String aName, Optional<Printer> aReserve, PrintStream aPrintStream) {
name = aName;
reserve = aReserve;
printStream = aPrintStream;
}
public void display(String message) throws OutOfInkException {
if ( inkLevelForClientUse > 0 ) {
printStream.println("(" + name + ") " + message);
inkLevelForClientUse -= 1;
} else {
if ( reserve.isPresent() ) {
reserve.get().display(message);
} else {
printStream.println(" Printer out of ink");
throw new OutOfInkException();
}
}
}
private String name;
private Optional<Printer> reserve;
private PrintStream printStream;
private int inkLevelForClientUse = 5;
}
final class OutOfInkException extends Exception { }
- Output:
(Main) Old Mother Goose,
(Main) Humpty Dumpty sat on a wall.
(Main) When she wanted to wander,
(Main) Humpty Dumpty had a great fall.
(Main) Would ride through the air,
(Reserve) All the king's horses and all the king's men,
(Reserve) On a very fine gander.
(Reserve) Couldn't put Humpty together again.
(Reserve) Jack's mother came in,
(Reserve) And caught the goose soon,
Printer out of ink
Julia
Julia has coroutines started with the @async macro and Channels, which can be used for interprocess communication, such as passing lines to and errors from a printing routine.
mutable struct Printer
inputpath::Channel{String}
errorpath::Channel{String}
inkremaining::Int32
reserve::Printer
name::String
function Printer(ch1, ch2, ink, name)
this = new()
this.inputpath = ch1
this.errorpath = ch2
this.inkremaining = ink
this.name = name
this.reserve = this
this
end
end
function lineprintertask(printer)
while true
line = take!(printer.inputpath)
linesprinted = 0
if(printer.inkremaining < 1)
if(printer.reserve == printer)
put!(printer.errorpath, "Error: printer $(printer.name) out of ink")
else
put!(printer.reserve.inputpath, line)
end
else
println(line)
printer.inkremaining -= 1
end
end
end
function schedulework(poems)
printerclose(printer) = (close(printer.inputpath); close(printer.errorpath))
reserveprinter = Printer(Channel{String}(1), Channel{String}(10), 5, "Reserve")
mainprinter = Printer(Channel{String}(1), Channel{String}(10), 5, "Main")
mainprinter.reserve = reserveprinter
@async(lineprintertask(mainprinter))
@async(lineprintertask(reserveprinter))
printers = [mainprinter, reserveprinter]
activeprinter = 1
@sync(
for poem in poems
activeprinter = (activeprinter % length(printers)) + 1
@async(
for line in poem
put!(printers[activeprinter].inputpath, line)
end)
end)
for p in printers
while isready(p.errorpath)
println(take!(p.errorpath))
end
printerclose(p)
end
end
const humptydumpty = ["Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again."]
const oldmothergoose = ["Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon."]
schedulework([humptydumpty, oldmothergoose])
- Output:
Humpty Dumpty sat on a wall. Humpty Dumpty had a great fall. Old Mother Goose, All the king's horses and all the king's men, When she wanted to wander, Couldn't put Humpty together again. Would ride through the air, On a very fine gander. Jack's mother came in, And caught the goose soon, Error: printer Reserve out of ink Error: printer Reserve out of ink
Nim
import asyncdispatch, options, strutils
type
Printer = ref object
inkLevel, id: int
backup: Option[Printer]
OutOfInkException = object of IOError
proc print(p: Printer, line: string){.async.} =
if p.inkLevel <= 0:
if p.backup.isNone():
raise newException(OutOfInkException, "out of ink")
else:
await p.backup.get().print(line)
else:
p.inkLevel-=1
stdout.writeLine("$1:$2".format(p.id, line))
await sleepAsync(100)
proc newPrinter(inkLevel, id: int, backup: Option[Printer]): Printer =
new(result)
result.inkLevel = inkLevel
result.id = id
result.backup = backup
proc print(p: Printer, msg: seq[string]){.async.} =
for line in msg:
try:
await p.print(line)
except OutOfInkException as e:
echo("out of ink")
break
const
humptyLines = @[
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again.",
]
gooseLines = @[
"Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon.",
]
proc main(){.async.} =
var
reservePrinter = newPrinter(5, 2, none(Printer))
mainPrinter = newPrinter(5, 1, some(reservePrinter))
await mainPrinter.print(gooseLines) and mainPrinter.print(humptyLines)
waitFor main()
- Output:
1:Old Mother Goose, 1:Humpty Dumpty sat on a wall. 1:When she wanted to wander, 1:Humpty Dumpty had a great fall. 1:Would ride through the air, 2:All the king's horses and all the king's men, 2:On a very fine gander. 2:Couldn't put Humpty together again. 2:Jack's mother came in, 2:And caught the goose soon, out of ink
Oz
Oz does not have a rendezvous mechanism, but the task description lends itself to synchronous active objects. We show how to implement this in Oz and then discuss the differences to the rendezvous model.
First a simple printer class whose definition is completely orthogonal to multithreading issues:
declare
class Printer
attr ink:5
feat id backup
meth init(id:ID backup:Backup<=unit)
self.id = ID
self.backup = Backup
end
meth print(Line)=Msg
if @ink == 0 then
if self.backup == unit then
raise outOfInk end
else
{self.backup Msg}
end
else
{System.printInfo self.id#": "}
for C in Line do
{System.printInfo [C]}
end
{System.printInfo "\n"}
ink := @ink - 1
end
end
endNote how requeuing the task simply becomes delegation to a different object.
Active object are not a predefined abstraction in Oz. But due to Oz' first-class object messages, we can easily define it using ports and streams (many-to-one message passing):
fun {NewActiveSync Class Init}
Obj = {New Class Init}
MsgPort
in
thread MsgStream in
{NewPort ?MsgStream ?MsgPort}
for Msg#Sync in MsgStream do
try
{Obj Msg}
Sync = unit
catch E then
Sync = {Value.failed E}
end
end
end
proc {$ Msg}
Sync = {Port.sendRecv MsgPort Msg}
in
{Wait Sync}
end
endThis functions takes a class and an initialization message and returns a procedure. When called, this procedure will send messages to the new object in a new thread and then wait for the Sync variable to become bound. Exceptions are propagated using failed values.
This works because a unary procedure is syntactically indistinguishable from an object in Oz.
With this new abstraction we can create the two printers and execute both print tasks in their own thread:
Main = {NewActiveSync Printer init(id:1 backup:Reserve)}
Reserve = {NewActiveSync Printer init(id:2)}
in
%% task Humpty Dumpty
thread
try
{Main print("Humpty Dumpty sat on a wall.")}
{Main print("Humpty Dumpty had a great fall.")}
{Main print("All the king's horses and all the king's men")}
{Main print("Couldn't put Humpty together again.")}
catch outOfInk then
{System.showInfo " Humpty Dumpty out of ink!"}
end
end
%% task Mother Goose
thread
try
{Main print("Old Mother Goose")}
{Main print("When she wanted to wander,")}
{Main print("Would ride through the air")}
{Main print("On a very fine gander.")}
{Main print("Jack's mother came in,")}
{Main print("And caught the goose soon,")}
{Main print("And mounting its back,")}
{Main print("Flew up to the moon.")}
catch outOfInk then
{System.showInfo " Mother Goose out of ink!"}
end
endExample output:
1: Humpty Dumpty sat on a wall.
1: Old Mother Goose
1: Humpty Dumpty had a great fall.
1: When she wanted to wander,
1: All the king's horses and all the king's men
2: Would ride through the air
2: Couldn't put Humpty together again.
2: On a very fine gander.
2: Jack's mother came in,
2: And caught the goose soon,
Mother Goose out of ink!
Comparison to Ada
What is called an "entry point" in Ada, is a method in our implementation.
We cannot limit the waiting time. This could be implemented in the NewActiveSync function, but it is not needed in the example task.
The callee task accepts rendezvous requests to the same entry point from multiple caller tasks. Similarly, the active object in Oz is designed to accept messages from different threads. To implement "rendezvous to different entry points", we simply add public methods to the Printer class.
The callee in ADA accepts one rendezvous at a time. The active object in Oz reads one message at a time from the stream.
Messages cannot be requeued in the given implementation. But we can delegate to a different active object which has the same effect, at least for the example given.
Like in the rendezvous mechanism, parameters are not marshalled. This is because sharing immutable data between threads is safe. In contrast to ADA, the parameters are buffered until the printer becomes ready. But with a synchronous communication mechanism, this should not cause problems.
Phix
Phix has no rendezvous mechanism, the following achieves something similar using a simple mutex.
without js -- (threads) constant print_cs = init_cs() enum NAME,INK sequence printers = {{"main",5}, {"reserve",5}} procedure printer(string name, sequence s) try for i=1 to length(s) do enter_cs(print_cs) for p=1 to length(printers) do if printers[p][INK]!=0 then printers[p][INK] -= 1 printf(1,"%s/%s: %s\n",{name,printers[p][NAME],s[i]}) exit elsif p=length(printers) then throw("out of ink") end if end for leave_cs(print_cs) end for exit_thread(0) catch e printf(1,"exception(%s): %s\n",{name,e[E_USER]}) leave_cs(print_cs) exit_thread(1) end try end procedure constant hd = {"Humpty Dumpty sat on a wall.", "Humpty Dumpty had a great fall.", "All the king's horses and all the king's men", "Couldn't put Humpty together again."}, mg = {"Old Mother Goose", "When she wanted to wander,", "Would ride through the air", "On a very fine gander.", "Jack's mother came in,", "And caught the goose soon,", "And mounting its back,", "Flew up to the moon."} sequence hThreads = {create_thread(printer,{"hd",hd}), create_thread(printer,{"mg",mg})} wait_thread(hThreads)
- Output:
hd/main: Humpty Dumpty sat on a wall. mg/main: Old Mother Goose mg/main: When she wanted to wander, hd/main: Humpty Dumpty had a great fall. hd/main: All the king's horses and all the king's men hd/reserve: Couldn't put Humpty together again. mg/reserve: Would ride through the air mg/reserve: On a very fine gander. mg/reserve: Jack's mother came in, mg/reserve: And caught the goose soon, exception(mg): out of ink
PicoLisp
Rendezvous can be implemented in PicoLisp via the following function:
(de rendezvous (Pid . Exe)
(when
(catch '(NIL)
(tell Pid 'setq 'Rendezvous (lit (eval Exe)))
NIL )
(tell Pid 'quit @) ) ) # Raise caught error in callerThe caller invokes it in the callee via the 'tell' interprocess communication, and it uses 'tell' in turn to communicate results (and possible errors) back to the caller.
Use case task:
(de printLine (Str)
(cond
((gt0 *Ink) (prinl *ID ": " Str) (dec '*Ink))
(*Backup (rendezvousPrint @ Str) T)
(T (quit "Out of Ink")) ) )
(de rendezvousPrint (Printer Str)
(let Rendezvous NIL
(tell Printer 'rendezvous *Pid 'printLine Str) # Call entry point
(unless (wait 6000 Rendezvous) # Block max. 1 minute
(quit "Rendezvous timed out") ) ) )
# Start RESERVE printer process
(unless (setq *ReservePrinter (fork))
(setq *ID 2 *Ink 5)
(wait) ) # Run forever
# Start MAIN printer process
(unless (setq *MainPrinter (fork))
(setq *ID 1 *Ink 5 *Backup *ReservePrinter)
(wait) )
# Start Humpty Dumpty process
(unless (fork)
(when
(catch '(NIL)
(for Line
(quote
"Humpty Dumpty sat on a wall."
"Humpty Dumpty had a great fall."
"All the king's horses and all the king's men"
"Couldn't put Humpty together again." )
(rendezvousPrint *MainPrinter Line) ) )
(prinl " Humpty Dumpty: " @ "!") )
(bye) )
# Start Mother Goose process
(unless (fork)
(when
(catch '(NIL)
(for Line
(quote
"Old Mother Goose"
"When she wanted to wander,"
"Would ride through the air"
"On a very fine gander."
"Jack's mother came in,"
"And caught the goose soon,"
"And mounting its back,"
"Flew up to the moon." )
(rendezvousPrint *MainPrinter Line) ) )
(prinl " Mother Goose: " @ "!") )
(bye) )
# Prepare to terminate all processes upon exit
(push '*Bye '(tell 'bye))Output:
1: Old Mother Goose
1: Humpty Dumpty sat on a wall.
1: When she wanted to wander,
1: Humpty Dumpty had a great fall.
1: Would ride through the air
2: All the king's horses and all the king's men
2: On a very fine gander.
2: Jack's mother came in,
2: And caught the goose soon,
2: And mounting its back,
Humpty Dumpty: Out of Ink!
Python
"""An approximation of the rendezvous pattern found in Ada using asyncio."""
from __future__ import annotations
import asyncio
import sys
from typing import Optional
from typing import TextIO
class OutOfInkError(Exception):
"""Exception raised when a printer is out of ink."""
class Printer:
def __init__(self, name: str, backup: Optional[Printer]):
self.name = name
self.backup = backup
self.ink_level: int = 5
self.output_stream: TextIO = sys.stdout
async def print(self, msg):
if self.ink_level <= 0:
if self.backup:
await self.backup.print(msg)
else:
raise OutOfInkError(self.name)
else:
self.ink_level -= 1
self.output_stream.write(f"({self.name}): {msg}\n")
async def main():
reserve = Printer("reserve", None)
main = Printer("main", reserve)
humpty_lines = [
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again.",
]
goose_lines = [
"Old Mother Goose,",
"When she wanted to wander,",
"Would ride through the air,",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon.",
]
async def print_humpty():
for line in humpty_lines:
try:
task = asyncio.Task(main.print(line))
await task
except OutOfInkError:
print("\t Humpty Dumpty out of ink!")
break
async def print_goose():
for line in goose_lines:
try:
task = asyncio.Task(main.print(line))
await task
except OutOfInkError:
print("\t Mother Goose out of ink!")
break
await asyncio.gather(print_goose(), print_humpty())
if __name__ == "__main__":
asyncio.run(main(), debug=True)
- Output:
(main): Old Mother Goose,
(main): Humpty Dumpty sat on a wall.
(main): When she wanted to wander,
(main): Humpty Dumpty had a great fall.
(main): Would ride through the air,
(reserve): All the king's horses and all the king's men,
(reserve): On a very fine gander.
(reserve): Couldn't put Humpty together again.
(reserve): Jack's mother came in,
(reserve): And caught the goose soon,
Mother Goose out of ink!
Racket
#lang racket
;;; Rendezvous primitives implemented in terms of synchronous channels.
(define (send ch msg)
(define handshake (make-channel))
(channel-put ch (list msg handshake))
(channel-get handshake)
(void))
(define (receive ch action)
(match-define (list msg handshake) (channel-get ch))
(action msg)
(channel-put handshake 'done))
;;; A printer receives a line of text, then
;;; - prints it (still ink left)
;;; - sends it to the backup printer (if present)
;;; - raises exception (if no ink and no backup)
(define (printer id ink backup)
(define (on-line-received line)
(cond
[(and (= ink 0) (not backup)) (raise 'out-of-ink)]
[(= ink 0) (send backup line)]
[else (display (~a id ":"))
(for ([c line]) (display c))
(newline)]))
(define ch (make-channel))
(thread
(λ ()
(let loop ()
(receive ch on-line-received)
(set! ink (max 0 (- ink 1)))
(loop))))
ch)
;;; Setup two printers
(define reserve (printer "reserve" 5 #f))
(define main (printer "main" 5 reserve))
;;; Two stories
(define humpty
'("Humpty Dumpty sat on a wall."
"Humpty Dumpty had a great fall."
"All the king's horses and all the king's men,"
"Couldn't put Humpty together again."))
(define goose
'("Old Mother Goose,"
"When she wanted to wander,"
"Would ride through the air,"
"On a very fine gander."
"Jack's mother came in,"
"And caught the goose soon,"
"And mounting its back,"
"Flew up to the moon."))
;;; Print the stories
(for ([l humpty]) (send main l))
(for ([l goose]) (send main l))
Output:
main:Humpty Dumpty sat on a wall.
main:Humpty Dumpty had a great fall.
main:All the king's horses and all the king's men,
main:Couldn't put Humpty together again.
main:Old Mother Goose,
reserve:When she wanted to wander,
reserve:Would ride through the air,
reserve:On a very fine gander.
reserve:Jack's mother came in,
reserve:And caught the goose soon,
uncaught exception: 'out-of-ink
Raku
(formerly Perl 6)
Raku has no built-in support for rendezvous. Simulated using message passing and a lock. May be slightly bogus.
class X::OutOfInk is Exception {
method message() { "Printer out of ink" }
}
class Printer {
has Str $.id;
has Int $.ink = 5;
has Lock $!lock .= new;
has ::?CLASS $.fallback;
method print ($line) {
$!lock.protect: {
if $!ink { say "$!id: $line"; $!ink-- }
elsif $!fallback { $!fallback.print: $line }
else { die X::OutOfInk.new }
}
}
}
my $printer =
Printer.new: id => 'main', fallback =>
Printer.new: id => 'reserve';
sub client ($id, @lines) {
start {
for @lines {
$printer.print: $_;
CATCH {
when X::OutOfInk { note "<$id stops for lack of ink>"; exit }
}
}
note "<$id is done>";
}
}
await
client('Humpty', q:to/END/.lines),
Humpty Dumpty sat on a wall.
Humpty Dumpty had a great fall.
All the king's horses and all the king's men,
Couldn't put Humpty together again.
END
client('Goose', q:to/END/.lines);
Old Mother Goose,
When she wanted to wander,
Would ride through the air,
On a very fine gander.
Jack's mother came in,
And caught the goose soon,
And mounting its back,
Flew up to the moon.
END
- Output:
main: Humpty Dumpty sat on a wall. main: Old Mother Goose, main: Humpty Dumpty had a great fall. main: When she wanted to wander, main: All the king's horses and all the king's men, reserve: Would ride through the air, reserve: Couldn't put Humpty together again. reserve: On a very fine gander. <Humpty is done> reserve: Jack's mother came in, reserve: And caught the goose soon, <Goose stops for lack of ink>
Tcl
Tcl does not have a rendezvous operation, but it does have the ability to send a script to another thread to be evaluated and the results passed back. Combined with coroutines (so that the code is not too ugly), this can make something that works very much like a rendezvous operation.
package require Tcl 8.6
package require Thread
# Really ought to go in a package
eval [set rendezvousEngine {
array set Select {w {} c 0}
# Turns the task into a coroutine, making it easier to write in "Ada style".
# The real thread ids are stored in shared variables.
proc task {id script} {
global rendezvousEngine
set task [list coroutine RTask eval "$script;thread::exit"]
tsv::set tasks $id [thread::create \
"$rendezvousEngine;$task;thread::wait"]
}
# A simple yielding pause.
proc pause t {
after $t [info coroutine]
yield
}
# Wait for a message. Note that this is *not* pretty code and doesn't do
# everything that the Ada rendezvous does.
proc select args {
global Select
set var [namespace which -variable Select](m[incr Select(c)])
set messages {}
foreach {message vars body} $args {
dict set messages $message $body
dict set bindings $message $vars
}
lappend Select(w) [list $var [dict keys $messages]]
try {
set Master ""
while {$Master eq ""} {
set Master [yield]
}
lassign $Master message responder payload
foreach vbl [dict get $bindings $message] value $payload {
upvar 1 $vbl v
set v $value
}
set body [dict get $messages $message]
set code [uplevel 1 [list catch $body ::Select(em) ::Select(op)]]
set opts $Select(op)
if {$code == 1} {
dict append opts -errorinfo \
"\n while processing message\n$message $payload"
}
set $responder [list $code $Select(em) $opts]
} finally {
catch {unset $var}
set Select(w) [lrange $Select(w) 0 end-1]
}
}
# This acts as a receiver for messages, feeding them into the waiting
# [select]. It is incomplete as it should (but doesn't) queue messages that
# can't be received currently.
proc receive {message args} {
global Select
lassign [lindex $Select(w) end] var messages
if {$message ni $messages} {
throw BAD_MESSAGE "don't know message $message"
}
set responder [namespace which -variable Select](r[incr Select(c)])
set $responder ""
RTask [list $message $responder $args]
set response [set $responder]
unset responder
after 1
return $response
}
# This dispatches a message to a task in another thread.
proc send {target message args} {
after 1
set t [tsv::get tasks $target]
if {![thread::send $t [list receive $message {*}$args] response]} {
lassign $response code msg opts
return -options $opts $msg
} else {
return -code error $response
}
}
}]
# The backup printer task.
task BackupPrinter {
set n 5
while {$n >= 0} {
select Print msg {
if {$n > 0} {
incr n -1
puts Backup:$msg
} else {
throw OUT_OF_INK "out of ink"
}
}
}
}
# The main printer task.
task MainPrinter {
set n 5
set Backup BackupPrinter
while 1 {
select Print msg {
try {
if {$n > 0} {
incr n -1
puts Main:$msg
} elseif {$Backup ne ""} {
send $Backup Print $msg
} else {
throw OUT_OF_INK "out of ink"
}
} trap OUT_OF_INK {} {
set Backup ""
throw OUT_OF_INK "out of ink"
}
}
}
}
# Tasks that generate messages to print.
task HumptyDumpty {
pause 100
try {
send MainPrinter Print "Humpty Dumpty sat on a wall."
send MainPrinter Print "Humpty Dumpty had a great fall."
send MainPrinter Print "All the King's horses and all the King's men"
send MainPrinter Print "Couldn't put Humpty together again."
} trap OUT_OF_INK {} {
puts "Humpty Dumpty out of ink!"
}
}
task MotherGoose {
pause 100
try {
send MainPrinter Print "Old Mother Goose"
send MainPrinter Print "When she wanted to wander,"
send MainPrinter Print "Would ride through the air"
send MainPrinter Print "On a very fine gander."
send MainPrinter Print "Jack's mother came in,"
send MainPrinter Print "And caught the goose soon,"
send MainPrinter Print "And mounting its back,"
send MainPrinter Print "Flew up to the moon."
} trap OUT_OF_INK {} {
puts "Mother Goose out of ink!"
}
}
# Wait enough time for the example to run and then finish
after 1000
thread::broadcast thread::exit
Wren
This uses fibers, which are always synchronous in Wren, to simulate the rendezvous mechanism.
class Printer {
construct new(id, ink) {
_id = id
_ink = ink
}
ink { _ink }
ink=(v) { _ink = v }
print(text) {
System.write("%(_id): ")
for (c in text) System.write(c)
System.print()
_ink = _ink - 1
}
}
var ptrMain = Printer.new("Main ", 5)
var ptrReserve = Printer.new("Reserve", 5)
var hd = [
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men",
"Couldn't put Humpty together again."
]
var mg = [
"Old Mother Goose",
"When she wanted to wander,",
"Would ride through the air",
"On a very fine gander.",
"Jack's mother came in,",
"And caught the goose soon,",
"And mounting its back,",
"Flew up to the moon."
]
var task = Fn.new { |name|
var lines = (name == "Humpty Dumpty") ? hd : mg
for (line in lines) {
if (ptrMain.ink > 0) {
ptrMain.print(line)
Fiber.yield()
} else if (ptrReserve.ink > 0) {
ptrReserve.print(line)
Fiber.yield()
} else {
Fiber.abort("ERROR : Reserve printer ran out of ink in %(name) task.")
}
}
}
var rhymes = ["Humpty Dumpty", "Mother Goose"]
var tasks = List.filled(2, null)
for (i in 0..1) {
tasks[i] = Fiber.new(task)
tasks[i].call(rhymes[i])
}
while (true) {
for (i in 0..1) {
if (!tasks[i].isDone) {
var error = tasks[i].try()
if (error) {
System.print(error)
return
}
}
}
if (tasks.all { |task| task.isDone }) return
}
- Output:
Main : Humpty Dumpty sat on a wall. Main : Old Mother Goose Main : Humpty Dumpty had a great fall. Main : When she wanted to wander, Main : All the king's horses and all the king's men Reserve: Would ride through the air Reserve: Couldn't put Humpty together again. Reserve: On a very fine gander. Reserve: Jack's mother came in, Reserve: And caught the goose soon, ERROR : Reserve printer ran out of ink in Mother Goose task.
zkl
It is unfortunate the critical section is so long but there are several intertwined objects that can only be changed as a unit.
class OutOfInk(Exception.IOError){
const TEXT="Out of ink";
text=TEXT; // rename IOError to OutOfInk for this first/mother class
fcn init{ IOError.init(TEXT) } // this renames instances
}
class Printer{
var id, ink;
fcn init(_id,_ink){ id,ink=vm.arglist }
fcn print(line){
if(not ink) throw(OutOfInk);
println("%s: %s".fmt(id,line));
Atomic.sleep((0.0).random(0.01)); // don't let one thread dominate
ink-=1;
}
}
class RendezvousPrinter{ // the choke point between printers and tasks
var printers=Thread.List(); // a thread safe list
fcn init(_printers){ printers.extend(vm.arglist) }
fcn print(line){ // caller waits for print job to finish
var lines=Thread.List(); // fcn local [static] variable, the print queue
lines.write(line); // thread safe, stalls when full
// lines is racy - other threads are modifing it, length is suspect here
while(True){ // this thread can print that threads job
critical{ // creates a [global] mutex, automatically unlocks on exception
if(not printers) throw(OutOfInk); // No more printers to try
if(not lines) break; // only remove jobs in this serialized section
try{
printers[0].print(lines[0]); // can throw
lines.del(0); // successful print, remove job from queue
}catch(OutOfInk){ printers.del(0) } // Switch to the next printer
}
}
}
}fcn printTask(taskNm,rendezvous,lines){
try{ foreach line in (vm.arglist[2,*]){ rendezvous.print(line); } }
catch{ println(taskNm," caught ",__exception); } // and thread quits trying to print
}
fcn humptyDumptyTask(rendezvous){ // a thread
printTask("humptyDumptyTask",rendezvous,
"Humpty Dumpty sat on a wall.",
"Humpty Dumpty had a great fall.",
"All the king's horses and all the king's men,",
"Couldn't put Humpty together again."
)
}
fcn motherGooseTask(rendezvous){ // a thread
printTask("motherGooseTask",rendezvous,
"Old Mother Goose,", "When she wanted to wander,",
"Would ride through the air,", "On a very fine gander.",
"Jack's mother came in,", "And caught the goose soon,",
"And mounting its back,", "Flew up to the moon."
)
}rendezvous:=RendezvousPrinter(Printer("main",5), Printer("reserve",5));
humptyDumptyTask.launch(rendezvous);
motherGooseTask.launch(rendezvous);
Atomic.waitFor(fcn{ (not vm.numThreads) }); // wait for threads to finish- Output:
main: Humpty Dumpty sat on a wall. main: Old Mother Goose, main: Humpty Dumpty had a great fall. main: All the king's horses and all the king's men, main: When she wanted to wander, reserve: Would ride through the air, reserve: On a very fine gander. reserve: Jack's mother came in, reserve: And caught the goose soon, reserve: And mounting its back, motherGooseTask caught OutOfInk(Out of ink) humptyDumptyTask caught OutOfInk(Out of ink)
See also
- Rendezvous on Wikipedia.