# 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 past-exams

## 2008

### Question 75 (2008):

Submission reference: IN1764

Hi there, for the 2008 exam, question 1b would the following be an acceptable answer?

```  PROC min.max (VAL []REAL32 x, REAL32 min, max)
SEQ i = 0 FOR SIZE x
IF
((x[i] < (x[i+1]\4))
min := x[i]
max := x[i +1]
((x[i] > (x[i+1]\4))
min := x[i+1]
max := x[i]
:
```

Not quite; what you have there looks more like a sorting algorithm. The correct answer is fairly straightforward (once you know how!). If you assume that the first value in the given array is the largest and smallest to start with, you then just need to search through the remaining elements and test them against the largest/smallest you already have. For instance:

```  PROC min.max (VAL []REAL32 x, REAL32 min, max)
SEQ
min := x[0]
max := x[0]
SEQ i = 1 FOR (SIZE x) - 1
IF
x[i] < min
min := x[i]
x[i] > max
max := x[i]
TRUE
SKIP
:
```

Keywords: past-exams

### Question 74 (2008):

Submission reference: IN1763

I'm a little unsure about question 2b from the 2008 exam paper. It asks for a plex process to muliplex fairly two input channels into one output channel. Would it be safe to assume the input channels are from an array and so write the process something like this :

```  PROC plex ([]CHAN INT in?, CHAN INT out!)
WHILE TRUE
ALT i = 0 FOR 2
INT x:
in[i] ? x
out ! x
:
```

The process is fair as it loops round, inputting from each of the two channels in turn.

Or would a better answer be to use a PRI ALT and use its guaranteed un-fairness as a way of guaranteeing fairness?

The code you have there is not fair. It relies on the implementation of ALT being fair, which may not be the case. ALT makes an arbitrary decision, which may be random or fair ... but may not be either. With current implementations, an ALT is neither random nor fair.

Your code is, therefore, not fair. Neither does it "loop around, inputting from each of the two channels in turn". Expanding out your replicated ALT, your code is equivalent to:

```  PROC plex ([]CHAN INT in?, CHAN INT out!)
WHILE TRUE
ALT
INT x:
in[0] ? x
out ! x
INT x:
in[1] ? x
out ! x
```

which, of course, is exactly the same as:

```  PROC plex ([]CHAN INT in?, CHAN INT out!)
WHILE TRUE
ALT
INT x:
in[1] ? x
out ! x
INT x:
in[0] ? x
out ! x
```

A suitable solution to the two-channel case (and others) does use the guaranteed unfairness of the PRI ALT to construct a fair solution. This can be found in the answer to Question 62 (2007).

Keywords: past-exams , fair-alt

### Question 73 (2008):

Submission reference: IN1760

Could you provide the code for the box process in exam 08? I'm not sure whether the 'ring' channel should be a single array of channels or two separate ones.

You can do it with either; two separate arrays of channels would probably be easier to code though. Something like:

```  PROC box ([n]CHAN INT in?, [n]CHAN BOOL tap?, [n]CHAN INT tap.out!)
[n]CHAN INT ring.0, ring.1:
PAR
...  network of 'catch' and 'plex' processes.
:
```

Keywords: past-exams

### Question 72 (2008):

Submission reference: IN1759

Hello there, I noticed in the 2007 exam paper there was a question on fair servicing / starvation-free processes. Would we need to use the notion of shared channels for a question like this or would you accept answers using a fair-alt ?

If you're referring to question 1(f), then this is really asking about the fair-alt. The question states "servicing of input channels", which suggests something about the insides of a process whose interface is already defined (multiple channels). So a shared-channel would not be a good answer, unless you can explain (correctly) how shared channels handle fairness. I don't think we've taught you how that works though! [Added later: yes, we have! See Question 62 (2007), about half-way through the answer.]

Keywords: past-exams , shared-channel , fair-alt

### Question 70 (2008):

Submission reference: IN1757

Hi. For question 1(c) of the 2006 past paper, where it asks you to draw a network diagram, do channels have to be drawn in order around a process shape (clockwise or anti-clockwise) to correspond to the order they appear in the PROC declaration? Would marks be deducted if the channels were not drawn in order?

Also, will we be getting our assessment marks back before the exam? Thanks.

Generally speaking, no, channels do not have to be drawn in any particular order, but as a default, from left-to-right would be sensible (clockwise or anti-clockwise). However, all similar occurences of any particular process should have their channels connected in the same way. The question in this case just states "Invent suitable icons for drawing the inner processes.", so whatever works best probably. Labeling the channels in the diagram ("a", "b", "c", "d") would aid clarity.

Regarding assessment marks, apologies for the delays. Depending on which group you're in, you may have had these back already; else efforts will be made to get them back before Tuesday's exam.

Keywords: past-exams

### Question 67 (2008):

Submission reference: IN1752

For the 2006 exam, question 2(d), is the following correct (assuming each process works correctly)?:

```  PROC beer.network()
[]CHAN BOOL req, resp:
[]CHAN BATCH batch:

PAR i = 0 FOR 100
PAR j = 0 FOR 3
bar (batch[i]?, req[i]?, resp[i]!)
student (i, req[i]!, resp[i]?)
bartender (j, batch[j]!)
:
```

Not quite — the code you have above (which won't compile just yet) is attempting to create 300 instances of each process. In essence, nested PARs like this create multi-dimensional structures of processes (e.g. the 2D grid in a game-of-life simulation). The solution for this question is simpler, and just involves expressing the diagram of the simulation in code. This should (must) have the structure:

```  PAR
...  single bar process
...  3 bartender processes
...  100 student processes
```

When filled in, with appropriate channel-declarations, something like this:

```  VAL INT N.STUDENT IS 100:
VAL INT N.BARTEND IS 3:

[N.STUDENT]CHAN BOOL req, resp:
[N.BARTEND]CHAN BATCH batch:
PAR
bar (batch?, req?, resp!)
PAR i = 0 FOR N.STUDENT
student (i, req[i]!, resp[i]?)
PAR i = 0 FOR N.BARTEND
bartender (j, batch[j]!)
```

In the above, the "bar" process takes whole arrays of channels. The code you give in your question is attempting to pass individual channels to multiple "bar" instances. The "VAL INT" constants are not strictly necessary, but are nice for clarity.

Keywords: past-exams

### Question 66 (2008):

Submission reference: IN1751

for question 2(b) of the 2006 paper, what would be a suitable protocol for a batch? I was thinking about an array protocol, but don't we just need to output a size (INT)?

Yes, an INT is sufficient. You can write this as:

```  PROTOCOL BATCH IS INT:           -- specifies how many pints.
```

Keywords: past-exams

### Question 65 (2008):

Submission reference: IN1750

Hi, I have been solving the 2006 past exam paper. I came across the "bar simulation" question (no. 2). Writing the code wasn't a problem because a good description of the system including the network diagram is given, plus hints on which constructs to actually use).

Then I came across part (e): "Is there any danger of deadlock, livelock or process starvation in this system? Does your answer depend on any of the timing values given above?".

I know that the client-server structure of the students->bar and bar->student relationship is never meant to deadlock. However, when you stick the bartenders at the back of the bar (as shown on the diagram)?.....I wasn't sure anymore. So I quickly implemented the system, and guess what? I do get deadlocks! and it does depend on the timing!

However I can't give precise technical reasons to why the deadlock happens. During the course we were only told about cyclic deadlocks and their solutions (i.e. using buffers). What other types of deadlocks are there which we need to be aware of before the exam?? Many thanks :)

As you almost point out, the "bar" process is a pure server, in that it never initiates communication with another process (it just services requests from the others). As such, it should not deadlock; if your implementation does deadlock, then there is probably an error somewhere. Similarly, the system should not livelock either. Furthermore, given the constraints in the question that specify priority and fair-servicing, there should not be any process starvation either.

Regarding other types of deadlock, apart from cycles of communication, you can get deadlock by not accepting a communication. For instance, the following code immediately deadlocks:

```  CHAN INT c:
c ! 42
```

because there is no inputting process on the channel "c", the output process above can never complete (and is therefore deadlocked). Once this process has deadlocked, any other part of the system that attempts to communicate with it will also deadlock. Although you wouldn't normally write something like the above, it can happen if the pre-conditions in an "ALT" or "PRI ALT" prevent communication with the alting process. This would be a good place to start looking for errors.

Keywords: past-exams

### Question 64 (2008):

Submission reference: IN1753

For the 2006 question 4c, are we supposed to implement the code for retina?

No, you just have to write the code for the network diagram that you drew in part (a), i.e. a "PAR" instantiating the various sub-processes, including "retina". There isn't enough information given in the question to implement "retina" itself.

Keywords: past-exams

## 2004

### Question 130 (2004):

Just a question about the past exam papers, was there no C or occam module (under a different title) before 2001 ?