1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
/*
* A program to sort concurrently N "random" numbers
* The reduced space and time should be linear in the
* number of processes, and can be reduced when the length of
* the buffer queues is increased.
* In full search it should be exponential.
*/
#define N 7 /* Number of Proc */
#define L 10 /* Size of buffer queues */
#define RANDOM (seed * 3 + 14) % 100 /* Calculate "random" number */
chan q[N] = [L] of {byte};
proctype left(chan out) /* leftmost process, generates random numbers */
{ byte counter, seed;
xs out;
counter = 0; seed = 15;
do
:: out!seed -> /* output value to the right */
counter = counter + 1;
if
:: counter == N -> break
:: counter != N -> skip
fi;
seed = RANDOM /* next "random" number */
od
}
proctype middle(chan inp, out; byte procnum)
{ byte counter, myval, nextval;
xs out;
xr inp;
counter = N - procnum;
inp?myval; /* get first value from the left */
do
:: counter > 0 ->
inp?nextval; /* upon receipt of a new value */
if
:: nextval >= myval -> out!nextval
:: nextval < myval ->
out!myval;
myval=nextval /* send bigger, hold smaller */
fi;
counter = counter - 1
:: counter == 0 -> break
od
}
proctype right(chan inp) /* rightmost channel */
{ byte biggest;
xr inp;
inp?biggest /* accepts only one value, which is the biggest */
}
init {
byte proc=1;
atomic {
run left ( q[0] );
do
:: proc < N ->
run middle ( q[proc-1] , q[proc], proc );
proc = proc+1
:: proc == N -> break
od;
run right ( q[N-1] )
}
}
|
