Here is a sketch of solutions to the exam of 24 Aug 2015.





Q1.  a)  The scenario is p1, p2, q1, q2, p1.     (n=1 at the end).





b)  Then p1, p2, q1, p1, q2, p2, p1 terminates with n=0 at the end.



c)   The scenario (p1, p2, p1, p2, q1)*  looping.  Then n becomes 1,
then 0, and q1 only tests it when n=0.  This is fair, because both p and
q execute infinitely often.









Q2.   a)   Here is a sketch of a solution.

            What happens at the bottom of the shaft is abbreviated.







protected object C

    integer array[1..3] free := [2,2,2];

        // array showing free places in each lift (numbered 1 through 3)

    integer sumfree := 6;

        // int variable showing total of free places (in any lift)

    integer fun index;

        // index is a function returning 0 if sumfree=0,



    entry miner_top when sumfree > 0

        sumfree--;

        i:= index;       //find free lift i;

        free(i)--;

        print("on" i)



    entry lift_arrive (i)

        free(i)=2;

        sumfree++ ++



    entry lift_depart (i) when free(i)=0

            // go down, then:

        print("off" i)

        print("off" i)



proc lift(i)

    loop

        lift_depart(i);

        lift_arrive(i)





proc miner;

    miner_top





Q2 b)   There are several solutions possible.  For example, sumfree can
be mimicked by a signal for sumfree ++, and by a wait for sumfree --.
The array free can be guarded by one semaphore, while three others
record whether free(i)=0.  Call index only when you have exclusive
access to sumfree; release this only after miner_top.







Q3.  The table is



s1=(p2, q2, 0)      (p3, q2, 2)=s2      (p2, q3, 5)=s3



s2=(p3, q2, 2)      (p5, q2, 2)=s4      (p3, q3, 7)=s5



s3=(p2, q3, 5)      (p3, q3, 3)=s6      (p2, q5, 5)=s7



s4=(p5, q2, 2)      (p2, q2, 0)=s1      (p5, q3, 7)=s8



s5=(p3, q3, 7)      (p5, q3, 7)=s8      no move



s6=(p3, q3, 3)      no move             (p3, q5, 3)=s9



s7=(p2, q5, 5)     (p3, q5, 3)=s9    (p2, q2, 4)=s10



s8=(p5, q3, 7)    (p2, q3, 5)=s3    no move



s9=(p3, q5, 3)    no move             (p3, q2, 2)=s2



s10=(p2, q2, 4)  (p3, q2, 2)=s2      (p2, q3, 5)=s3





Q 3 b)  There is no state (p5, q5, sn) in the table.   Remember that p5
and q5 are in the critical section; the process only leaves that after
executing p5 or q5.



Q3 c)  There is no state where neither p nor q can move.





Q4  a)  To get to p3 and q3, we have either



                      p2 and q3 followed by doing p2.    q3 implies S=5
or S=7.  Then p2 makes S=3.



                                                          or



                      p3 and q2 followed by doing q2.    p3 implies S=2
or S=3.  In either case, q2 makes S=7.



Q4 b)   If p3 and q5, we may assume S=3.  Then p3 has to wait until q5
runs and makes S=2.



Q4 c)  Suppose p3, q1.   So S=2, given.  If q1 loops, it cannot reset
S.   (Remember that protocol variables are only to be accessed in pre-
or post-protocols).    So p3 will move on to p5.   We need to assume
fairness, otherwise q could hog all the CPU time.







Q5.  a)  Assign a channel to each node, and a process to each arc.
The channels are of type unit (they transmit beeps), but they can be
declared to be of type int, bool, ....  We won't use the value.





For the arc (i, j) we have a process



process P(i,j)            //where i and j are channels of unit

unit dummy;



i => dummy;         // read from channel i

loop forever

    j <= dummy;     // write to channel j





We also need



process Start (k)    //where k is a channel of unit

loop forever

        k <= dummy;     // write to channel k



and



process End (l)    //where l is a channel of unit

l <= dummy;     // read from channel l

print ("ok")



So to check if there is a path from k to l, Start floods k with beeps.
All arcs from k will relay this fllod on to their end nodes.  Flood the
whole graph until a beep reaches l.  Then we know there is a path.



Q5 b)  The arcs don't synchronise with each other, so the channels can
be synchronous or asynchronous.



Q5 c)  For this, the channels are of type int.  Start floods 0 onto k.
Each arc (i,j) receives dummy and sends dummy+1.   The end node gets a
number giving the length of the path that reached it.







Q6.  a)



process S(k, l)



int x;



loop

    read(k, x);

    if x = l

    then

        print("ok");

        break

    else

        k := x

end loop



This will start at x  (=k to start with) and look for an arc leading
away.  If it finds l, great, otherwise just keep going till there are no
arcs left  (hang).



If there is a path k to l, some run of S will find it (by fairness
assumption).



Q6 b)  This is simply part a except that instead of running S
repeatedly, we run all the repetitions in parallel.


Q6 is almost not about Linda, but about general ideas of parallel search.