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: <lang ada>select
Server.Wake_Up (Parameters);
or delay 5.0;
-- No response, try something else ...
end select;</lang> 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: <lang ada>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;</lang> 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
<lang ada>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;</lang> 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
<lang 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
}</lang>
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.
<lang tcl>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</lang>
See also
- Rendezvous on Wikipedia.
- Rendezvous electronic duo.