|
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.
Submission reference: IN1729
Hey Guys,
Much appreciated for the email on the extension today, I'm sure it will be a great help to many people, unfortunately this has come too late for me as other deadlines have to take precedence at this time, so i will have to leave Task 4 incomplete and take the hit on the marks, many apologies.
That's the problem with granting extensions! Submission dates for all assignments were negotiated centrally, with the aim of avoiding too many happening together.
Anyway, we will accept late submissions of extra work (e.g. a completed Task 4) – though they will not gain full credit for the marks allocated for those additions: the later they arrive, the less credit that can be obtained. If you do this, please mark clearly (with comments) where the additions or changes are from your original submission and mail them to me (phw@kent.ac.uk).
Submission reference: IN1736
For question 4 of last year's exam (2008):
1. For part a, how would you receive the synchronisation signal from every sync channel in parallel before sending a signal to each ack channel to acknowledge the synchronisation without being able to read each sync signal into a dynamically sized array or read each value to a single variable in parallel?
2. Following on from part a, for part b how would you be able to tell when a certain number of channels have been synchronised?
You don't have to read every sync channel in parallel ... but, if you do, you can read into local variables (i.e. you don't have to read into different elements of a dynamically declared and sized global array – nor, illegally, into a shared global variable). For instance:
PROC barrier ([]CHAN BOOL sync?, ack?)
WHILE TRUE
SEQ
PAR i = 0 FOR SIZE snyc? -- gather in the bids to synchronise
BOOL b:
sync[i] ? b
PAR i = 0 FOR SIZE ack? -- all in, so let everyone go
BOOL b:
ack[i] ? b
:
However, both those inner replicated PARs could be SEQs ... think about it, :).
For a partial barrier, where only m (< SIZE sync?) processes engage to trigger their release, we just have to listen out for m bids to synchronise and, then, let those m callers go:
PROC p.barrier (VAL INT m, []CHAN BOOL sync?, ack?)
WHILE TRUE
SEQ
SEQ i = 0 FOR m -- gather in m bids to synchronise
ALT i = 0 FOR SIZE snyc? -- gather one bid (from anyone)
BOOL b:
sync[i] ? b
SEQ i = 0 FOR m -- all in, so let m go
ALT i = 0 FOR SIZE snyc? -- release someone (anyone)
BOOL b:
sync[i] ? b
:
Note that we don't need to keep account of which processes are synchronising – we assume they all do this via the protocol given in the question – i.e.
SEQ
sync[i] ! TRUE -- let barrier know we are ready
ack[i] ! TRUE -- wait for everyone else
With this protocol, only those m processes whose opening syncs have been accepted will be attempting their acks.
Note also that the bid and release loops (m times) must be done in SEQ this time. They cannot be done in PAR, as in the barrier code above.
Keywords: barriers
Referrers: Question 69 (2010)
Submission reference: IN1738
Do we need to worry too much about Test-Rig Design in regards to the exam? Thanks.
You are expected to know all the motivation and mechanisms underlying process-oriented design (i.e. all the occam-pi material covered in the course, except for the slides on mobiles) – and be fluent and comfortable enough in that knowledge to be able to apply them in scenarios not seen before.
So, you do need to understand the principles underlying that Test-Rig (as one example of good application). However, we do not expect you to memorise things by rote learning!
Keywords: exams
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
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
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
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
Submission reference: IN1754
Hi there, I was wondering for the exam, are we likely to be awarded any marks for drawing process network diagrams, to supplement any code we might be asked to write ? Thanks very much.
Unless the question specifically asks for a diagram, there wouldn't be any additional marks for these. However, if a question asks you to write the code for a particular process network, drawing a diagram may be a good place to start — if the code is wrong, but the diagram is right, you would likely get more (though not full) marks than if the diagram was not there [because you essentially know what to do]. This would not apply if the diagram was given in the exam paper, or in an answer to another part of the same question.
Keywords: exams
Submission reference: IN1755
Are we expected to know about graceful termination for this year's exam?
Nope! That paper is for background reading and not directly examinable. Reading it, however, may deepen your understanding of the fundamental issues being learnt.
Keywords: exams
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
Submission reference: IN1758
Are we expected to know about barriers for the exam ? Or is that more advanced material like mobiles? Thanks,
Barriers are in the mobiles.ppt set of slides. Nothing in mobiles.ppt is examinable – it is only for any who are curious to learn more, :).
Keywords: exams
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
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
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
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
|
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. |
