XML CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

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.

Keyword reference for alternation

Question 107 (2006):

Submission reference: IN1196

Is it possible to put a guard on a variant protocol? TRUE & in ? CASE or TRUE & poison doesn't seem to work.

Answer 107:

Yes, but only if that precondition is part of an ALT. You can't selectively precondition against individual cases – that would require the outputting process to first check the inputting process's ability to handle the particular case, which is not supported. Examples of things which do work are:

  ALT
    cond & in ? CASE
      INT x:
      first; x
        P (x)
      second
        Q ()
    INT x:
    cond2 & in ? CASE first; x
      P (x)

Note: the last guarded process above needs explaining. It could have been written:

    cond2 & in ? CASE
      INT x:
      first; x
        P (x)

It's just that if we only have to deal with one of the variants (e.g. under condition cond2 above), we can write out that variant on the same line as the CASE input. It's just a syntactic shorthand, saving one line of code. It's part of the language, but I don't usually bother with it (and never showed it to you).

Keywords: tagged-protocol , alternation

Question 49 (2004):

In the buffer process (slide 13), by using an ALT instead of a PRI ALT, could the request signal potentially get starved untill the buffer is full? I just thought it would have been better to use a PRI ALT with the request channel so if a request does come in it gets serviced straight away.

Answer 49:

Yes. As you say though, once the buffer is full the request channel is the only one in contention for the ALT, so it would definitely be serviced then.

If you use a PRI ALT, giving priority to the request channel, the reverse starvation will happen. Consider an un-full buffer with some process trying to push things into it competing against an aggressive requester, who always takes his output and comes back for more before the buffer has had time to loop and consider servicing the pusher. In this case, the pusher is starved until the buffer is empty -- at which point, it would definitely be serviced.

So, a PRI ALT is not the answer to providing fair service between competing guards whose pattern of readyness is not known in advance (and may sometimes be always ready). A plain ALT provides an arbitrary service mechanism -- no good if fairness is required. A PRI ALT guarantees un-fairness -- again, no good if fairness is required.

There is a simple solution to this and you are invited to work it out. We do use a PRI ALT, but in a subtle way. With a guaranteed unfair mechanism, we can produce a guaranteed fair one. :)

Keywords: alternation

Question 33 (2003):

This is one of the statements under a PRI ALT in my code:

    BYTE y:
    in ? y
      out ! y

When I compile it tells me that `y' is not declare on the second line. However, I have exactly the same piece of code in another PROC with a `z' instead of a `y' and yet it compiles ok. Any ideas ?

Answer 33:

If that's a guard of a PRI ALT, there's nothing wrong with it. Thus, the error must be elsewhere. Errors above that, but possibly still inside the PRI ALT, might be confusing the compiler when it gets to this point. The first error output by the compiler is generally the most relevant -- others may simply be a cascade effect.

Keywords: alternation , variable-scope

Question 25 (2003):

I have now got a completed version of q4. However, in this monitor process...

    [snip code]

.... it will only reset `I' or `P' if I press the key twice and it pauses it inbetween each key press. How come it is doing this as it is only the `S' case that asks for a second input? Also, typing in N twice causes the program to deadlock, yet I can't think of why. Any suggestions?

Answer 25:

You have an ALT guard of the form:

    in ? y
      BYTE x:
      SEQ
        in ? x
        ...  do something based on `x'

Before getting to the `do something based on `x'' bit, two inputs will happen on "in". Remember that in an ALT, input guards do perform the input before the guarded process runs. The correct guard/process would be something like:

    in ? y
      ...  do something based on `y'

Keywords: q4 , alternation

Question 20 (2002):

Sir, could you explain the process below. Have been trying to figure it.

  PROC pause (CHAN OF BYTE in, interrupt, out)
    WHILE TRUE
      BYTE x :
      PRI ALT
        interrupt ? x
          IF
            x = 'Q'
              black.hole (interrupt)
            TRUE
              interrupt ? x
        in ? x
          out ! x
  :

From my understanding, if data is pending in the interrupt channel, then it checks if it is the 'Q' char. If it is, it goes into a black.hole - otherwise it waits for data to enter though interrupt. So, when does it ever check the second guard?? Thanks.

Answer 20:

(This process is part of the model answer to Q3 on the exercise sheet.)

As you say, if data is pending in the interrupt channel, it inputs it and checks for 'Q'. If it got a 'Q', it goes into an infinite loop that just swallows anything else sent down that interrupt channel - and will never check that second guard (i.e. data will never flow through this device again from in to out, which is what we want).

If the value input from interrupt was not 'Q', it waits for a second character to arrive on interrupt - during which wait it never checks that second guard (i.e. data will not flow from in to out, which is also what we want). If and when it gets that second character on interrupt, it loops around and starts listening again on the in and interrupt channels - now data arriving on in will flow thorugh to out, which is what we want.

Keywords: pause-process , alternation

Question 86 (2000):

In a replicated ALT over an array of channels, how do you include a SKIP process to deal with when none of the channels is sending data? For example:

    forks[f] ? CASE
      upfork
        SEQ
          ...  display an fork in the up position
      downfork
        SEQ
          ...  display an fork in the down position
      -- needs a SKIP if none of the forks positions have changed...

I think my program is deadlocking because it keeps waiting for forks to report when none of them have changed position.

Answer 86:

You should not need such a SKIP guard. The best thing for your display process to do when nothing is being reporting is nothing, which is what will happen if you just listen to all the report channels with a replicated ALT. If your program is deadlocking, it is for another reason - such as your college processes (philosophers, forks and security guard) outputting to parameter channels that are not correctly wired to the input channels of your display process.

If you really need to poll all those report channels (and you don't - honest), you could write something like this:

    WHILE TRUE
      PRI ALT
        ALT p = 0 FOR n.phils
          phils[p] ? CASE
            ...  deal with philosopher reports
        ALT f = 0 FOR n.forks
          forks[f] ? CASE
            ...  deal with fork reports
        INT n.sat.down:
        security ? n.sat.down
          ...  deal with this report from the security guard
        TRUE & SKIP
          ...  no reports available - do something else (like SKIP :-()

Keywords: q7 , alternation

Question 83 (2000):

How can I implement an ALT without it being in a SEQ? I have the following:

    WHILE TRUE
      ...
      PAR
        SEQ
          ...
        SEQ
          ...
        SEQ
          ALT
            over channel 1
              ...
            over channel 2
              ...
      ...

I can think of how to stick the ALT into a loop and yet read over both channels until both actions from the channels are complete.

Answer 83:

I'm afraid I don't understand the questions. An ALT construct can occur anywhere any other occam statement can occur - on its own, as part of a SEQ, as part of a PAR, as part of an IF etc.

Your code fragment above is illegal because there are three processes in the body of the WHILE-loop (the first set of dots, the PAR, and the last set of dots) that are all at the same level of indentation but have no controlling SEQ or PAR.

Should your "can" in your second question have been "can't"? Servicing multiple input channels is one of the basic capabilities of an ALT. Each ALT waits for and services just one input completely. Put it in a loop to service them all continuously.

Keywords: alternation , sequential-execution

Question 65 (2000):

Can you explain "without using ALT constructs" a buffered channel with a max capacity of 100 items? Does the question mean a buffered channel like a ring buffer??

Answer 65:

No - the serial ring buffer process (slides 6-11 through 6-13) requires an ALT. The sought answer is the parallel piepline of id processes (slides 5-7 and 6-17).

Keywords: buffered-channel , alternation

Referrers: Question 123 (2003)

Question 23 (2000):

In the example below, how can I execute the quoted code after any of the two guards is executed? I could put the code with a SEQ in the process part of both guards, but that wouldn't look nice. If I indent the quoted code as in the example below, the compiler complains.

  PROC priAlt (CHAN OF INT inA, inB, outA, outB)
    INT x, z:
    PRI ALT
      inA ? x
        outA ! 1
      inB ? z
        outB ! 2
  " SEQ
      ...  do in all cases"

Answer 23:

This (I think) is what you want but wouldn't look nice:

  PROC priAlt (CHAN OF INT inA, inB, outA, outB)
    INT x, z:
    PRI ALT
      inA ? x
        SEQ
          outA ! 1
          ...  do in all cases
      inB ? z
        SEQ
          outB ! 2
          ...  do in all cases

If so, the common code can be factored out (so that it appears only once) by moving the SEQ outwards:

  PROC priAlt (CHAN OF INT inA, inB, outA, outB)
    INT x, z:
    SEQ
      PRI ALT
        inA ? x
          outA ! 1
        inB ? z
          outB ! 2
      ...  do in all cases

Now, the PRI ALT executes one of its guarded processes (when one or both of them become ready). Then, the do in all cases code gets executed.

Keywords: alternation , sequential-execution