XML CO538 Anonymous Questions and Answers

This page lists the various questions and answers. To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

We have taken the liberty of making some minor typographical corrections to some of the questions as originally put. Although most of the questions here will have been submitted anonymously, this page also serves to answer some questions of general interest to those on the course.

When asking questions, please do not simply paste in your code and ask what is wrong with it, as these types of question are hard to answer in a public forum (resulting in either no answer, or an answer which will only be of use to the person asking the question). In many cases, a question about code can be formulated in general terms. For example, if you have an `IF' block that results in an `incorrect indentation' error, you might ask, ``what is the correct syntax for an occam `if' statement ?''. Questions of this form are easier to answer, and are meaningful to all.

Questions that are not suitable for these public pages (i.e. those that contain assignment-specific code), should be mailed to your seminar-leader.

Question 121:

There is a question that asks what rule can be followed in order to ensure deadlock avoidance and I can't seem to find anything about deadlock except on the philosophers example. Can you shed some light on this ?

Answer 121:

There are two design rules that guarantee deadlock freedom: client-server and IO-PAR/IO-SEQ. These are in the course notes (discussed in detail in one of the papers). You have not been taught these this year, however, so no need to revise this! But.. it is useful background reading. It's worth noting that the dining philosophers doesn't remove the deadlock by either of these methods. That deadlock is solved by preventing the deadlock condition occuring in the first place, which is slightly less intuitive than client-server or IO-PAR/IO-SEQ, and a lot harder to prove.

Keywords: deadlock , exams

Question 122:

What is actually meant by non-determinism ? Is it the fact the you cannot predict the values of variables and program position ? Due to program flow is un-predictable ?

Answer 122:

Almost.. What you describe is really an artifact of non-determinism. Non-determinism is the inability to predict what event will happen next, even when you do know what events are being offered. A classic example is the difference between `ALT' and `PRI ALT'. For example:

    ALT                          PRI ALT
      c ? x                        c ? x
        P ()                         P ()
      d ? y                        d ? y
        Q ()                         Q ()

In the first (`ALT') example, if we know that the channels `c' and `d' are ready for communication, we cannot tell which guard will be selected by the `ALT'. Hence, that choice is non-deterministic. In the other (`PRI ALT') example, if both channels are ready, we do know what will happen -- it will pick the `c' channel.

`PRI ALT' isn't always determinstic, however. For example:

    PRI ALT
      tim ? AFTER t
        Q ()
      c ? x
        P ()

This too is non-determinstic, since it relies on timing -- the outcome depends on when the code is run. Another way of thinking about a timeout is a parallel-process that waits for a bit then communicates. The above, for example, is equivalent to:

    CHAN BOOL d:
    PAR
      SEQ
        tim ? AFTER t
        c ! TRUE

      PRI ALT
        BOOL any:
        d ? any
          Q ()
        c ? x
          P ()

Unlike the earlier example, where we assumed we knew about the `ready' states of the `c' and `d' channels, we cannot call this example determinstic. The `ready-ness' of `c' depends on timing.

Keywords: non-determinism

Question 123:

How should we answer the question which asks us to explain how a buffered channel of capacity 100 can be implemented without using an ALT. Does this meen that the buffer size is 100 or we have 100 channels. I assumed the latter seeing as it mentioned the ALT but don't really know how to answer it.

Answer 123:

The actual solution is to use a pipeline of (parallel) processes. See the answers to Question 65 (2000) and Question 41 (2002).

Keywords: exams , buffered-channel

Question 124:

In the 2002 exam paper I'm stuck on question 3(b) ... I just have no idea how to tackle the changing of the rate of flow in this question :(

Answer 124:

This is a fairly complex question and needs to be read carefully. Once things are up and running, the `controller.1' process passes values between its `in' and `out' channels at a rate determined by values communicated on `speed'. At the very least, the code for this will require a timer, along with timeout (absolute time of next `tick') and interval (time between `tick's) values, e.g.:

    TIMER tim:
    INT timeout, interval:

The question specifies that `controller.1' should wait for input on `speed' before doing anything:

    BYTE b:
    SEQ
      speed ? b
      WHILE b = 0
        speed ? b          -- wait for a non-zero `speed'

      -- setup interval and timeout
      interval := 255000000 / ((INT b) * max.rate)
      tim ? timeout
      timeout := timeout PLUS interval

After this, `interval' contains the time in micro-seconds between outputs and `timeout' has the absolute time of the first `tick' (that will cause output).

The body of this process will need to be an `ALT' (or `PRI ALT') -- there are two events that require waiting for: a new `speed' signal, or the output timeout. Trying to include the `in' channel in the ALT will complicate things -- that input should be controlled by the timeout. The main body of this process would therefore have the form:

    WHILE TRUE
      PRI ALT
        tim ? AFTER timeout
          ...  handle timeout (input/output)
        speed ? b
          ...  handle new speed

Handling a new communication on `speed' should be similar to the initialisation code, remembering to update the timeout as well. For example:

    --{{{  handle new speed
    SEQ
      WHILE b = 0
        in ? b
      interval := 255000000 / ((INT b) * max.rate)
      tim ? timeout
      timeout := timeout PLUS interval
    --}}}

The arithmetic both here and in the earlier initialisation is taken from the question paper. Handling the timeout is slightly trickier -- if there is no value to be read from `in', the `controller.1' process should repeat the last value it did input. The test for channel-input-ready can be done using a `PRI ALT' with a SKIP guard (polling). To keep the last data-value between iterations of the process, that needs to be declared outside the loop (along with the `TIMER' etc. would be OK) -- and probably a good idea to initialise it too.

The body of the `handle timeout' process could be:

    --{{{  handle timeout
    SEQ
      PRI ALT
        in ? data
          SKIP
        TRUE & SKIP
          error ! 0                 -- signal error
      out ! data

      timeout := timeout PLUS interval
    --}}}

Keywords: exams

Question 125:

Looking at the 2002 question paper and I'm lost by question 4(e) I don't understand what it is asking..

Answer 125:

The question describes the internal structure of the `box' process, then asks you to draw a diagram and write the code for it. Writing the code will be much easier once you have a network-diagram in front of you..

One possible implementation of the `box' process is:

    PROC box ([n]CHAN INT in?, tap.out!, [n]CHAN BOOL tap?)
      [n]CHAN INT c, d:
      PAR i = 0 FOR n
        PAR
          multiplex (in[i]?, c[(i+(n-1)) \ n]?, d[i]!)
          catch (tap[i]?, d[i]?, c[i]!, tap.out[i]!)
    :

Keywords: exams