Notes from
Reproducible Testing of
Monitors by Per Brinch Hansen
http://brinch-hansen.net/papers/1978b.pdf
Steps in Testing a Monitor
1. “For each monitor operation the programmer
identifies a set of preconditions that will cause each branch of the operation
to be executed at least once.”
2. “The programmer then constructs a
sequence of monitor calls that will try each operation under each of its
preconditions.”
3. “The programmer now constructs a set
of test processes that will interact exactly as defined above. These processes
are scheduled by means of a clock monitor used for testing only.”
4. “Finally, the test program is
executed and its output is compared with the predicted output.”
Example: a producer process calls a
synchronous buffer monitor with one line as a parameter; a consumer “receives”
a character at a time until it has consumed the entire line. The example code (in Concurrent Pascal is
given below. Remember, all entries to a monitor in Concurrent Pascal are
equivalent to “synchronized” methods in Java. The difference is that the
monitor in Concurrent Pascal has explicit queues, whereas Java must use the
lock of another object to “block” processes.
type
buffer=
monitor
var
contents: line; length: integer; sender, receiver: queue;
procedure entry send(x:line);
begin
if length
> 0 then delay(sender);
contents:=;
length:=80;
if not empty(receiver) then
continue(receiver)
end;
procedure entry receive( var
y: char);
begin
if
length = 0 then delay(receiver);
y:=contents[length];
length := length -1;
if not empty(sender) & (length = 0) then
continue(sender)
end;
begin
length:=0 end
Necessary preconditions that ensure
all statements within the monitor are executed at least once
test cases (send) preconditions
sender is delayed S1: length>0
sender is not delayed S2: length = 0
receiver is continued S3: not empty(receiver)
receiver is not continued S4: empty(receiver)
test cases (receive) preconditions
receiver is delayed R1: length = 0
receiver is not delayed R2: length>0
sender is continued R3: not empty(sender) & length = 1
send is not continued R4:
empty(sender) or
R5:
length<1
A sample test sequence for testing
the buffer monitor
{R1,R4: contents = [],
empty(receiver), empty(sender)}
receive()
{S2, S3: contents=[], not
empty(receiver), empty(sender)}
send(‘ab’)
{contents=’ab’, empty(receiver),
empty(sender)}
receive() continued
{S1,S4: contents = ‘b’,
empty(receiver), empty(sender)}
send(‘cd’)
{R2,R3: contents = ‘b’,
empty(receiver), not empty(sender)}
receive()
{contents =[], empty(receiver),
empty(sender)}
send(‘cd’) continued
{R2,R5: contents = ‘cd’,
empty(receiver), empty)sender)}
receive()
{R4: contents= ‘d’, empty(receiver),
empty(sender)}
receive()
{contents =[], empty(receiver), empty(sender)}
Timing for Testing: Example
T1: receive()
T2: send(‘ab’)
T3: receive() continued
T4: send(’cd’)
T6: send(‘cd’) continued
T7: receive()
T8: receive()
Processes to Test using Test Clock
producer:
process(buf: buffer; clock: testclock);
begin
with
buf, clock do
begin
await(2); send(‘ab’);
await(4); send(‘cd’);
await(6)
end
end
consumer:
process(buf: buffer; clock: testclock;
terminal:
display);
var c: char;
begin
with
buf, clock, terminal do
begin
await(1); receive(c);
await(3); print(c);
await(5); receive(c); print(c);
await(7);
receive(c); print(c);
await(8); receive(c); print(c);
end
end
The Test Clock
1. Maintains an integer that keeps the
clock time.
2. Methods
a. “await(time)” – the clock is called
at this method when it wants to wait a logical amount of “time”;
b. “tick()” –
the clock monitor is called at this method when logical time is advanced. The
logical clock time (kept in the “time” variable of the monitor). “time” is advanced by 1 each time tick is called. If
processes are waiting on the new value of “time”, they are awakened.
3. Clock monitor
type testclock =
monitor
var time:
integer;
sequence:
array[1..steplimit] of queue;
procedure entry await(when: integer);
begin
delay(sequence[when]) end;
procedure entry tick;
begin
time:=
time+1
continue(sequence[time]);
end;
begin
time:=0; end;