|
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 shared-channel
2012 |
Submission reference: IN2300
For the Life on Mars assessment, are we allowed to changed some of the robot.control channels to SHARED?
Yes. But you will have to work hard on the mars-sim.occ file to let it compile. The channel that gets plugged into your robot.control needs to be declared with its writing-end SHARED. Now, mars-sim.occ caters for multiple robots on mars and provides arrays of opr.req and opr.resp channels back to its (simulated) mission.control process – for your assessment, the number of robots is set to 1. Unfortunately, the occam-pi compiler does not currently allow arrays of channels to be declared with SHARED ends – if you need them, you will need to investigate MOBILE CHAN TYPEs (from "Mobiles" slides 24 onwards, which have not been presented in this module and are not examinable). A simpler solution, however, would be to modify mission.control to a single pair of opr.req / opr.resp channel-ends whose other end (at the robots on mars) is SHARED.
If you do this, you will need to submit your revised mars-sim.occ file (along with mars-main.occ) plus adequate documentation (in both files) explaining your changes and the reason(s) why you made them. This is a lot of work.
Why do you want to make some of the robot.control channels SHARED? I know no good reason. Please read Question 49 (2012), where the questioner was having a technical problem for which a SHARED channel was raised as a possible solution ... but the real problem was some weak software engineering (low cohesion: putting too much functionality into a PROC) and over-engineering (result channels instead of reference parameters to return results). Maybe your problem is similar?
Keywords: mars , shared-channel
Submission reference: IN2295
I have a hazard.monitor process as suggested in the answer to Question 59 (2011) and that seems to be working.
For Task 3 of the mars assessment, I'm trying further parallelism. I have a turn.robot process in parallel with a find.blob, with a cancel channel between them. If find.blob finds the specified blob, it sends a cancel to turn.robot which stops its turn. I have a result process that receives results from both turn.robot (how much it turned) and find.blob (if it found the specified blob and, if so, the blob itself).
However, turn.robot is also used to respond to a turn command and has to send to opr.resp!. My result process also wants to send to opr.resp!. But the opr.resp! parameter given to robot.control is not SHARED, so I cannot run turn.robot, find.blob and result in parallel. If I put result in sequence and after running the other two in parallel, it compiles but, of course, gets stuck as soon as turn.robot and find.blob try to report their results to result which hasn't yet started!
Is there any way out of this impasse, please?
You have two problems.
First, see Question 55 (2011), the paragraph in the answer starting: "From the software engineering principle of cohesion ...". That was talking about a move process, but it applies to turn as well. Task 4 will need lots of turns and you'll want to reuse your turn.robot ... but you won't want it reporting on opr.resp! each time! Do what it says there: remove the opr.resp! parameter from turn.robot and promote your local variable that is accumulating the ticks to a reference parameter. Then, whoever invokes turn.robot will get the ticks it found (when turn.robot finishes) and can report, or not, to opr.resp! as needed. Now, the need for its ticks-reporting channel has gone, so get rid of it.
In general, an initialisation channel that just delivers one value to a process should be replaced with a VAL parameter with that value. Similarly, a reporting channel that delivers only one final report should be replaced by a reference parameter to which the report value is assigned.
[Side-note: check out the answer to Question 58 (2010) for the concept of RESULT parameters. We've not presented them in the course, so they are not examinable. However, they are very simple to understand and use and give added safety (against programming error) and elegance to the recommendation in the second sentence of the preceding paragraph.]
So, get rid also of the reporting channels in find.blob. Replace them by promoting the local variables holding the report values (whether it found a blob with the specified colour and, if so, the blob itself) to reference (or RESULT) parameters. Now, like the changed turn.robot, it has no need to communicate with your result process via a channel and no need, therefore, for that result process to be running in parallel with it.
Now, put result in sequence and after running the other two in parallel, declaring and passing variables for ticks, found-the-blob and blob (as needed by result and the other two). This time, it compiles and result gets the information it needs. Indeed, now that result no longer need to input result data, its code should be trivial enough to write in-line (without a PROC).
Don't forget that, with this modified turn.robot, the code for responding to a turn command (from opr.req?) needs a little extra.
Things should work better now.
You're not there yet though. If a blob is sought that is not in vision range even after a full turn, does your find.blob keep waiting? If so, your response to a find command will never finish – the robot will do a complete turn and nothing else will happen.
Just as your find.blob cancels turn.robot if it finds a blob, so your turn.robot should cancel find.blob if it completes a full turn (plus a couple of seconds to allow for camera processing of the image in its final position). But there's deadlock lurking if they both commit to cancelling each other around the same time – this needs to be avoided. There is a simple solution, but we leave it to you to find.
Keywords: mars , shared-channel
Referrers: Question 50 (2012)
Submission reference: IN2198
I'm having an issue with the idea of CLAIM in the processes. The problem I'm having is that when I try and add CLAIM to the shared channel, I'm getting incorrect indentation. I've tried shifting the indentation but this creates a different error shown below. I've been reading and re-reading the slides, and I can't see where I'm going wrong, nor what is actually correct.
ALT
... (Ed: other guards hidden)
BOOL any:
left ? any
CLAIM report!
report ! fork.up;id
left ? any <<-- incorrect indentation
CLAIM report!
report ! fork.down;id
IF I have the following code, it throws an error that – "must CLAIM 'report?' before using channels":
... (Ed: code hidden)
A CLAIM and its indented code block is a process. The second input line from the left channel is a process. They are listed at the same level of indentation as the response to an ALT guard (the first input line from the left channel). Always, when there are two or more processes to run, we must say whether they are to be run in SEQuence or in PARallel. Here, they need to be in SEQuence. The second CLAIM and its indented code block is also a process and needs to be the third element of that sequence – so it must be at the same level of indentation. Therefore, there is a missing SEQ and the code must be laid out to define what's in that SEQuence:
ALT
... (Ed: other guards hidden)
BOOL any:
left ? any
SEQ
CLAIM report! -- first process of the SEQ
report ! fork.up; id
left ? any -- second process of the SEQ
CLAIM report! -- third process of the SEQ
report ! fork.down; id
If you follow the "USEFUL NOTE" in the answer to Question 37 (2012), the above can be shortened to:
ALT
... (Ed: other guards hidden)
BOOL any:
left ? any
SEQ
CLAIM report ! fork.up; id
left ? any
CLAIM report ! fork.down; id
Re. the last part of your question, I can see nothing wrong with the code you sent ... and neither did the compiler when I tried it. Are you sure you included the right bit of code?
Keywords: q7 , shared-channel
Submission reference: IN2197
I have a shared channel called report which all philosophers and forks will write to. I think I have set this up correctly and it all compiles ... but when I run the program I immediately get:
program failed, state= e, eflags = 00000000
exited with error code: 1
referring to line 108 which is the line in my secure.college process where fork would be writing to its report channel (the last line).
I have not implemented anything further with forks actually writing to the report channel, yet in the fork process it is flagged yellow saying it is currently unused. I have only implemented the reporting for philosophers so far as I wanted to test if that worked before I added forks and security guards.
Here is the code for my almost unchanged reporting.college process.
PROC reporting.college (SHARED CHAN REPORT report!)
... (Ed: code body hidden)
:
How do I go about finding out why this is happening?
As always, the best way to debug code is to read it. However, shared channels are a new concept and I hid the relevant code when editing the question (to allow general viewing) ... so let's talk through what you sent.
Your reporting.college creates (in parallel) all the college processes and plugs all of them into its SHARED report channel-end parameter. However, the college processes cannot be declaring their report channel-end parameters as being SHARED, so they can't directly be plugged in. I can deduce this because, before instancing each college process, reporting.college first CLAIMs the report channel-end. This gives exclusive use of the report channel-end and the college process may now be instanced (exclusive use means the channel-end is no longer shared). Thus, your reporting.college compiles.
But what happens when it runs? Each process in the PAR competes with all other processes in the PAR to CLAIM the report channel-end. One of them wins and the others are blocked (and wait in a queue). However, the winning process then executes its college process in the CLAIM block ... that process never ends ... so the CLAIM is never released. That means no other college process ever starts ... the processes starting them are all queued up trying make their CLAIM. As soon as the winning process tries to communicate with any other college process, it blocks (because that other college process isn't there). So, all college processes are blocked. The display process is blocked, waiting to hear from any college process. Deadlock (apologies for the poor error message from the Transterpreter – the kroc run-time actually reports deadlock).
GENERAL PRINCIPLE: when you share a resource, it's necessary not to grab it until you need it and not to hang on to it afterwards ... and, certainly, not for ever!
FIX: get rid of those CLAIMs on the report channel-end within reporting.college. Now look at the last two sentences in the answer to Question 36 (2012). See also Question 29 (2012) for a similar problem.
USEFUL NOTE: here's some information that's not currently in the "Shared-etc" slides. Slide 10 shows a CLAIM on an output channel and a note that, in the CLAIM body (indented from the CLAIM line), we may use that output channel as many times as you like. However, we often only want to use it once - e.g.
CLAIM report!
report ! hungry
In this case, the code may be written in one line:
CLAIM report ! hungry
which makes the code look less busy and easier to read.
Keywords: q7 , shared-channel
Referrers: Question 38 (2012)
Submission reference: IN2196
I'm trying to implement a variant PROTOCOL called report and part of the design of that protocol is that philosophers, forks and the security guard will need to report on it. But when I try to do this using a similar method to how I did previously with an array of 11 channels in the secure.college process, I get an error:
xxx.occ(99)- parallel outputs on channel `report'
My code surrounding the error reads:
PROC secure.college (CHAN REPORT report!)
... (Ed: code body hidden)
:
Is this because I need to make it a shared channel? If so how do i go about doing this?
Yep. Just declare the report! channel as being SHARED. Otherwise, the normal occam rules against parallel outputs to the same channel apply and the compiler, correctly, complains. Your process header should be ("Shared-etc" slide 7):
PROC secure.college (SHARED CHAN REPORT report!)
Your code body for the above will now compile (with parallel processes outputting to the same, now explicitly shared, channel). At least, it will compile so long as your individual college processes (phil, fork and security) also declare their report! channels as being SHARED. Of course, those college processes will then need to CLAIM their report! before using it ("Shared-etc" slides 8-9).
Keywords: q7 , shared-channel
Referrers: Question 37 (2012)
Submission reference: IN2194
I'm having an issue with setting up my Shared Channel, I have got my protocol REPORT, with the TAGS and INT value to store the philosopher or fork using that channel. I'm struggling with how to pass the ID of the phil or fork to the actual REPORT protocol.
PROTOCOL REPORT
CASE
thinking; INT
... (Ed: rest hidden)
:
PROC fork (CHAN BOOL right?, left?, SHARED CHAN REPORT report!, CHAN INT id?)
... (Ed: code body hidden)
:
PROC secure.college (SHARED CHAN REPORT out!)
SHARED ! CHAN REPORT r:
... (Ed: rest of code body hidden)
:
PROC display (SHARED CHAN REPORT out!, CHAN BYTE screen!)
... (Ed: code body hidden)
:
I keep getting type mismatch for parameter 4 in fork and 6 in philosopher. I've tried a lot of ways to try and get the 'i ' value into the other processes, I want to be able to try and have a look at my display process, but I can't test this until I can actually get it to compile.
Is there a glaring error, or am I approaching this in the completely wrong way.
There is a glaring error – but it's easily fixed.
To give a single value to a process (that will not need updating by some other process as it runs), pass that value as a VAL parameter – not a channel! A process needs a channel input-end to receive information that is not available when it is created and, usually, on more than one occasion.
Parameter 4 in your fork header is declared as a channel. In your secure.college, you instance each fork with the control value, i, as its fourth argument. You can't pass an INT value to a parameter expecting a channel – hence, the "type mismatch" error reported by the compiler. You try to avoid this by actually passing the text "i?" as the fourth argument (maybe hoping that might convert the INT value to a channel delivering that value?). The compiler correctly rejects this.
Inside your fork process, you try to read from that id? channel (the fourth parameter). That will compile, but no process ever sends to it ... so the fork would get stuck at that point.
Solution: change the fourth parameter of fork from a channel to a value:
PROC fork (CHAN BOOL right?, left?, SHARED CHAN REPORT report!, VAL INT id)
Inside its body, just use id when it makes a report. Make similar changes to your philosopher process (not included in your question). Inside secure.college, instance the fourth argument of fork with the PAR replicator i. Done! :)
Not relevant to the above, you included part of your display process in your question – its header is shown in the question. Its first parameter is very wrong (possibly a cut-and-paste mistake?). This is the REPORT channel and it should be for input (not output). Further, it's not SHARED – display is the only process that has to read from it.
Final point: inside your secure.college, you declare another channel carrying the REPORT protocol, also SHARED at the writing-end. Why? The parameter channel, out!, is the one on which reports must be made. You plug the shared writing-end of this new channel, r!, into the report arguments for all college processes – so that is where they will write. Unfortunately, nobody is listening to the other end, r?, so they will all block the first time they try to report, :(. Fix: delete the declaration of channel r and plug out! into the report arguments of the college processes.
Keywords: q7 , shared-channel
Submission reference: IN2182
I'm using a shared channel, and I managed to get one line to output, but then I get "error: 1" which I believe is a deadlock.
SHARED CHAN P.REPORT report:
CLAIM report?
PAR
secure.college (report!) -- some parameters will be needed
display (report?, screen!) -- and a 'display' process ..
This is in the main method. The deadlock is supposedly at display. I assume this means that either that line itself is causing a deadlock or the method it is calling.
PROC display (CHAN P.REPORT report?, CHAN BYTE out!)
... (Ed: some code hidden)
That's the beginning part of my display method. P.REPORT is a protocol that inherits from P.PHIL, P.FORK and P.SEC, which are protocols for the reports from philosophers, forks and security.
I've stared at it for ages and I can't seem to work out what is causing a deadlock.
Any advice? I was thinking perhaps if I made it so its a shared channel at both ends it might work, but I can't seem to work out how to do the solution part mentioned on slide 24 of the shared etc slide. If I do need this (or it is the easier way to fix this) could you give me an example of how i'd implement it.
Eleven processes within the college want to write to your SHARED report channel. Only one process (display) reads from it. Therefore, your report channel needs to be shared only at the writing end. Your declaration shares it at both ends. See "Shared-etc" slide 5 for how to share only the writing end. All college processes given the writing end of the report channel (in their parameter lists) must declare that writing end as SHARED. The display process, which is the sole holder of the reading end, must not declare it to be shared.
CLAIMing a shared channel-end should be done only when it is about to be used and the claim must not linger beyond that use (i.e. the body of the CLAIM must be as short as possible in execution). Your CLAIM on the report channel is made to enclose the whole system, so it lasts forever! Inside a CLAIM block, the code has exclusive use of the channel-end – it is no longer SHARED, so only one process in your secure.college will be able to be connected to it (the compiler won't allow more if you have done this).
So, do not make the CLAIM where you are making it. The college processes will then be allowed to be connected to the report channel writing-end and they must make the claim each time they want to use it. Inside each claim, they can use the channel-end as many times as they like (and no other processes can interrupt this to use it themselves). This may be useful for certain kinds of animation. To begin with though, they will use the channel-end just once within each claim.
Fix these things and see if the deadlock goes away. On your final paragraph: do not make the report channel shared at both ends (only the writing-end is shared) and the problem described in "Shared-etc" slide 24 is not relevant for this system (when a college process uses the report channel, it uses it only briefly to write a single message informing of its state).
Keywords: q7 , shared-channel
Referrers: Question 37 (2012)
2011 |
Submission reference: IN2144
Consider the following top level processes:
PROC main.1 (CHAN BYTE out!)
out.int (1, 0, out!)
:
PROC main.2 (SHARED CHAN BYTE out!)
CLAIM out!
out.int (1, 0, out!)
:
The first prints "1", whereas the second prints nothing. Adding a FLUSH (or newline) "fixes" it.
Why does a SHARED channel introduce this behaviour?
First, I confirm getting the same behaviour that you report (using KRoC under Ubuntu, version 11.04, Linux).
The need to flush characters sent to the screen channel depends on the operating system (if there is one) in which the occam-pi program is running. Both in the KRoC support for occam-pi (compiled code plus multicore scheduler) and in the Transterpreter (interpreter), we have tried to provide the behaviour that is normal for Unix standard output (which is that characters are buffered until either the buffer is full or a special flush character is received).
What happens to characters still in the Unix standard output buffer when a program ends is a grey area. It would be OK simply to discard them, as happens with your main.2 program. It would be OK to flush them out, as happens with your main.1 program. However, we ought to be consistent about this and we will see if we can do that!
Thank you for your question. It is really about the interaction between the occam-pi system and its host operating system. Please be assured that such matters are not part of the syllabus for this module and no questions requiring such knowledge would be asked in the exam on this module.
Keywords: flush , shared-channel
Submission reference: IN2076
I'm currently trying to get me animation processes running in parallel and I'm not sure how to go about this.
I have the display process receiving inputs on a shared channel from the forks, philosophers, and security that is correctly interpreting the input. But anytime I use one of my animation processes it is done in sequence due to the display process not except another input until the animation process has finished, so everything is animated in sequence.
I've tried all that I can think of to fix this. Any advice?
See Question 39 (2011). All the forks, philosophers and the security guard processes must have separate report channels (not a shared one) to separate animation processes that can all operate in parallel. The animation processes then compete with each other to send incremental movement messages over the same shared channel to a display process that handles them.
For example, a philosopher animation process might want to move its philosopher icon from one part of the screen to another by some interesting route (e.g. when its philosopher process reports it is hungry). It animates by a sequence of incremental moves (e.g. erase the icon from its current position, which it has to remember, and re-draw at slightly further on along its route). It can hold its philosopher process till this is complete by using an extended input to receive its messages and doing the animation in the extended rendezvous block (see Shared-etc slide 59). The same effect can be achieved without using the extended input syntax (see Shared-etc slide 61, where the ack channel is not needed in this case if you make the philosopher (or fork or security) send each of its messages twice).
Keywords: q7 , shared-channel , animation
Submission reference: IN2070
I have followed the plan and have a shared channel, but it seems I can't achieve parallel output of the animation when reports only come in sequence...
My security guard's counter always seems to be out of sync with the actual number of philosophers at the table, but I'm unsure why. Any ideas how to achieve this?
For the first problem, you may want to consider adding additional processes to help control the animation. Clearly having all the animation handled by "display" which has a single input channel from everything isn't going to work (as you say, it's serialised). What you would need to do is introduce helper processes which do the legwork of the animation and only communicate step-by-step animation actions to the "display" process. That way lots of things can be animating at once without a problem.
As for the issue about the security guard counter, are you flushing the output after writing the integer to the screen? If not, it may be stale. If that's not the problem, try mailing your code to your seminar leader who should be able to spot the problem quickly.
Keywords: q7 , shared-channel , animation
Referrers: Question 44 (2011)
Submission reference: IN2064
Hi, is is possible to have channels, both shared and normal in a RECORD? I have this:
CHAN TYPE foo
MOBILE RECORD
CHAN INT x?:
CHAN INT y?:
:
but this doesn't compile when used with SHARED CHANs. Is there a way of doing this, or do I just need to pass the SHARED CHANs individually, as it doesn't seem possible to have an array of them either?
Fields of a CHAN TYPE RECORD (informally known as channel bundles) can only be CHANs (with field names that specfify the direction of use) – so the direct answer to your question is: no. However, ...
We only declare variables for the ends of such bundles of channels. The type names of these ends are the type names of the bundles, Bundle type ends with the "!" specifier mean that their channel fields must be used in the opposite directions to those declared in the bundle type (they are the opposite ends of the bundle). Note: it's the the type of the bundle ends that carry the "?" or "!" specifiers – not the variables that hold them (whereas, for standard CHANs, direction specifiers go with the channel variables; we apologise for this inconsistency).
Now, bundle type ends (i.e. either end of the whole bundle) may be SHARED, which should give you what you were after (I hope). Many processes may be given the same end of a shared bundle of channels. To use them, just CLAIM the bundle-end variable and use the individual channels as you like (in the correct directions, of course). See the Mobiles slides 39-43 for examples.
Note: the material on these these channel bundles is not an examinable part of this module.
Re. your question about arrays of shared channels (ordinary ones): sorry, these are not supported – see Question 30 (2010). However, arrays of shared ends of channel bundles are supported, :).
Keywords: shared-channel , chan-type
2010 |
Submission reference: IN1927
Is it possible to declare an array of SHARED channels? "SHARED ! [n]CHAN BOOL lol" gives an error message.
Nope, unfortunately that will not work; you'll need to declare them individually. This will be fixed in a future version of a compiler.
Keywords: q7 , shared-channel
Referrers: Question 34 (2011)
2009 |
Submission reference: IN1841
Hi there, I'm having a strange problem trying to pass my shared channel to where it needs to go.
... code omitted
provides me with this error:
Error-occ21-q7.occ(182)- must CLAIM `reportChan!' before using channels
skroc: Could not compile q7.occ.
skroc exited with error code: 1
and I don't understand why. It's more than happy to let me pass reportChan to philosopher and fork. I can delete the security line and it compiles fine. I can't imagine why it insists on me claiming the channel to pass it to security. At no point in my code am I writing to channel yet anyway! Am pulling my hair out. Help much appreciated! Thanks
There was not enough information in the code fragment you included to answer your question. Also, we cannot reproduce such code fragments (containing too much solution code) in these questions.
However, check that your security guard process declares its reportChan channel as SHARED. Failing that, mail me or your seminar leader your code and repeat your question.
Keywords: q7 , shared-channel
Submission reference: IN1830
Could I clarify that the only use of a shared channel is that you get a free FIFO mechanism for handling requests? As opposed to implementing a FAIR ALT – this doesn't actually exist does it?. Numerous channels per se aren't bad - it's not we are going to run out of channels? Or is it to declutter things?
Thanks,
A shared channel writing-end means that the writing processes are FIFO queued to do their writing on that channel – which is fair. If the other (reading-)end is not shared, than the single reader there will automatically provide a fair service to all writers.
The above is simpler than having a number of classic channels (with non-shared ends) from all the writers to a single reader, with the reader having to be programmed with fair-alting logic to provide a fair service. There are times when we have to do this though – e.g. when the protocols on the channels have to be different (although this can usually be overcome with variant protocols and variant protocol inheritance) or when fair service for some channels has to be balanced with prioritised service for others.
You are right that occam-pi does not support the notion of FAIR ALT as a language mechanism. That would not actually make sense, since the notion of fairness only is relevant when many executions of the ALT take place. The question of fairness for a single ALT does not arise. If fairness were introduced at the language level, it would have to be in terms of a loop that services a set of channels – e.g.
FAIR SERVER i = 0 FOR SIZE in?
in[i] ? x
... deal with x
which would mean something like:
VAL INT n IS SIZE in?:
INITIAL INT favourite IS 0:
WHILE TRUE
PRI ALT i = favourite FOR n
VAL INT i.mod.n IS i\n:
in[i.mod.n] ? x
SEQ
... deal with x
favourite := i.mod.n + 1 -- channel just serviced become least favoured
where we have used classical fair alting logic (see Question 62 (2007)).
FIFO servicing of channel inputs is not the only benefit of shared channels. The reading ends of channel may also be shared, which provides for fair distribution of messages from a single writer. And both ends of a channel may be shared, which provides a fair brokerage service for putting reader and writer processes in touch.
As you say, numerous channels are not necessarily to be avoided. After all, each one only requires one word of storage (to hold a reference to a waiting partner – or nil if no process is waiting). But if you can replace an array of channels with one shared channel, that does tend to simplify the picture and associated logic.
Keywords: q7 , fair-alt , shared-channel
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
Submission reference: IN1643
Hi there, I am having a little bit of a problem in connecting up my shared report channel. I get the error message (type mismatch for parameter 1 in secure.college), but I can't see where I am going wrong. I have declared the channel passed to the secure.college as SHARED and I have a SHARED CHAN within my q7 process that I pass to secure.college. I'd be grateful if you could possibly point me in the right direction. Within q7:
SHARED CHAN P.DISPLAY reporter: secure.college (reporter!)
header of secure.college :
PROC secure.college (SHARED CHAN P.DISPLAY reporter!)
Thanks,
The code you have written in the question looks fine, though in this particular case, the "reporter" channel should only be shared at its output end, i.e. be declared:
SHARED! CHAN P.DISPLAY reporter:
This is on the (usual) understanding that the "display" process reading from the shared channel is the only process doing so. As you're seeing a "type mismatch" error at the point of the procedure call, double-check that the code is as you have it above. Specifically, check that there is not anything else also called "reporter" declared between that shared "reporter" channel and the error-generating call to "secure.college". For example, the following code will generate a similar error:
PROC foo (CHAN BYTE out!)
INT x:
SEQ
x := 42
... some other code
INT out:
SEQ
out := 19
out.string ("Hello, world!*n", 0, out!)
:
In a similar way, also check that the "secure.college" you mention is the only one declared at the top-level. For instance, if you had:
PROC foo (SHARED CHAN BYTE out!)
... stuff
:
PROC bar ()
... stuff
:
PROC foo (CHAN BYTE out!)
... stuff
:
PROC baz ()
SHARED! CHAN BYTE c:
PAR
... some process reading from 'c'
foo (c!)
:
This will also generate a type-mismatch error, since there is another "foo" procedure declared between the one you intend to use (with a shared channel parameter) and the point where it is called (in "baz").
If you can't spot the error yourself, try mailing your seminar leader with the code and asking for help (we're a bit more used to tracking down errors in occam-pi programs quickly!).
Keywords: shared-channel , q7
Submission reference: IN1608
Hi, is it possible to make "screen!" shared? Or is there something we can do that offers the same effect?
If you're using KRoC, then you can directly declare the top-level channels as being SHARED, for instance:
PROC q7 (CHAN BYTE kyb?, SHARED CHAN BYTE scr!, CHAN BYTE err!)
... code
:
Which would give you a shared "scr!" (screen) channel, but unshared "kyb?" (keyboard) and "err!" (error) channels.
The Transterpreter does not yet handle shared top-level channels, but you can get the same effect through the use of a BYTE "id" process running in parallel with your code. For example:
PROC new.q7 (CHAN BYTE kyb?, scr!, err!)
SHARED! CHAN BYTE screen: -- output end shared
PAR
--{{{ byte "id" process
WHILE TRUE
BYTE ch:
SEQ
screen ? ch
scr ! ch
--}}}
--{{{ original q7 instance with shared screen channel
q7 (kyb?, screen!, err!)
--}}}
:
Such a procedure can be added to the end of your existing q7.occ file, and becomes the new top-level process.
Keywords: shared-channel , q7
Referrers: Question 106 (2004)
2007 |
Submission reference: IN1419
I'm just looking over last years exam papers, and a question about fair alting came up.
I didn't think we covered fair alting, at least code wise. I understand what one is, but I havn't seen the code to do so. Was this in the slides, I can't see it?
Fair alting is how a process provides a fair service to multiple client
processes competing for its attention. Writing a process that waits on an ALT
(over input channels from its clients) at the start of its cycle does not guarantee fairness.
Selection between mutliple ready guards in an ALT is arbitrary,
so some clients may be starved of service if they have competitors who always happen to get
chosen. Changing the ALT to a PRI ALT guarantees
unfairness, with guards (clients) lower in priority order always losing out to any
higher up that happen to be ready.
In classical occam, fair alting is a simple technique that uses the guaranteed unfairness of prioritised alting to provide a fair one – we just switch priority ordering each time, giving the guard serviced last time the lowest priority in the next round.
[In occam-pi, however, the need for fair alting has been superceded by the mechanism
of SHARED channel-end (specifically, shared output-ends) and protocol
inheritance. More later.]
To fair alt between just two channels, unroll the server cycle loop once and use
a PRI ALT twice with oppoising priorities:
WHILE running
SEQ
PRI ALT
a ? ...
... deal with the 'a' message
b ? ...
... deal with the 'b' message
PRI ALT
b ? ...
... deal with the 'b' message
a ? ...
... deal with the 'a' message
Now, if a message is pending on the 'b' channel, it will either be taken next
(if the server process is at the second PRI ALT in
its cycle or nothing is pending on the 'a' channel) or it will be taken after
at most one 'a' channel message (if the server is at its first PRI ALT
and something was pending on 'a').
Similarly, any message pending on 'a' will be taken either next or the time after that.
Neither channel can be starved and we can calculate worst case response times by
the server for incoming messages (if we know maximum times for dealing with them).
For example, the fork process in the Dining Philosophers' college can be
modified as above to guarantee no philosopher starves to death because of ever-greedy
colleagues.
[Fair servicing was mentioned several times during the course.
For this (2008) year exam purposes, the trivial solution above is all you need
to have discovered –
though you might as well just read further on to find the fair.fork.0
process that actually applies the above modification.
The rest of this answer – on the fair servicing of arrays of channels, fair
sevicing via a single channel with a shared output-end, and reflections on mutexes
(i.e. "mutually exclusive" locks), counting semaphores and Java monitors –
are for interest only.
Reading and following the examples below, however, will give you more practice
in the ideas of occam-pi concurrency and deepen your understanding –
which always helps with exam preparation, :).]
If there are three channels, this approach is no harder but gets a little tedious:
WHILE running
SEQ
PRI ALT
a ? ...
... deal with the 'a' message
b ? ...
... deal with the 'b' message
c ? ...
... deal with the 'c' message
PRI ALT
b ? ...
... deal with the 'b' message
c ? ...
... deal with the 'c' message
a ? ...
... deal with the 'a' message
PRI ALT
c ? ...
... deal with the 'c' message
a ? ...
... deal with the 'a' message
b ? ...
... deal with the 'b' message
The code is exploding! This can be ameliorated by placing the code responding
to each source of message inside a PROC, so that the above responses
are single line PROC calls. But it's still tedious and gets worse
as the number of guards gets larger!
If the server is servicing an array of channels (rather than a set of individual ones), we can wrap the algorithm up neatly, without any repeated code:
PROC fair.server.0 ([]CHAN SOME.PROTOCOL in?, ...)
... local state variables
SEQ
... initialise local state
INTITIAL BOOL running IS TRUE:
INITIAL INT favourite IS 0:
WHILE running
SEQ
PRI ALT i = favourite FOR SIZE in?
VAL INT actual.i IS i \ (SIZE in?)
... more local variables
in[actual.i] ? ...
... deal with this message
favourite := (favourite + 1) \ (SIZE in?)
:
On its first cycle, 'favourite' is 0 and the channel priority is 0 .. (n-1),
where n is the number of channels (SIZE in?).
The channel with index 'favourite' always has highest priority and that
moves round each cycle. So, in the second cycle, channel priority order
is 1 .. (n-1) 0. Then, 2 .. (n-1) 0 1. Then, 3 .. (n-1) 0 1 2. Each
channel will have highest priority once every n cycles. At worst,
a pending message on any channel will be serviced within n cycles –
and earlier if not all the other channels are pending.
This round-robin prioritisation is not as fair as it could be though. It's possible for channel 7 (say) to have a pending message and for channel 6 to be serviced 7 times in a row before channel 7 is served (e.g. when 'favourite' is 0, channels 0 through 5 have nothing and channel 6 is always ready!).
To fix this, don't round-robin the value of 'favourite'. Instead, as mentioned in the second paragraph of this answer, switch 'favourite' to one after the index serviced last time (which channel becomes least favoured in the next cycle) – a simple modification:
PROC fair.server.1 ([]CHAN SOME.PROTOCOL in?, ...)
... local state variables
SEQ
... initialise local state
INTITIAL BOOL running IS TRUE:
INITIAL INT favourite IS 0:
WHILE running
PRI ALT i = favourite FOR SIZE in?
VAL INT actual.i IS i \ (SIZE in?)
... more local variables
in[actual.i] ? ...
SEQ
... deal with this message
favourite := actual.i + 1
:
Now, once any channel (say index 5) gets serviced, every other channel that is pending will be serviced before channel 5 gets serviced again. Of course, if no other channels are pending, channel 5 can get serviced again immediately should it become ready. Whatever happens, no pending channel will see another channel serviced twice before it gets serviced – and that's fair!
Having said this, a SHARED channel in occam-pi eliminates
the need for these tricks.
Simply let all clients of the server share the output-end of a single
channel to the server.
The server just sees a normal (unshared) channel input-end:
PROC fair.server.2 (CHAN SOME.PROTOCOL in?, ...)
... local state variables
INTITIAL BOOL running IS TRUE:
SEQ
... initialise rest of local state
WHILE running
... more local variables
SEQ
in[actual.i] ? ...
... deal with this message
:
which is a lot simpler! The clients see the SHARED output-end
to this service channel and simply CLAIMs it before use.
Competing clients will be queued and serviced in FIFO order – and that's fair!
The only downside (to fair.server.1 and fair.server.2)
is that all clients must speak the same channel protocol.
However, with protocol inheritance, the service channel can carry the union of
distinct protocols for each client (but all these protocols must carry
a CASE tag):
PROC fair.server.3 (CHAN SOME.PROTOCOL in?, ...)
... local state variables
INTITIAL BOOL running IS TRUE:
SEQ
... initialise rest of local state
WHILE running
... more local variables
in[actual.i] ? CASE
... deal with all message variants
:
Note: the fair alting servers (fair.server.0 and
fair.server.1) may process further messages from its
client (or, indeed, any other client it chooses) in the block of code
labelled: "... deal with this message".
That is not allowed for the shared channel servers
(fair.server.2 and fair.server.3)
since client messages seeking the server's attention all share
the one channel and any further messages from a client will be
queued behind other client's messages – so they are
not available for immediate input.
The effect can be managed, however, by providing a separate channel
on which to receive subsequent messages.
[Note on the above note: an assumption is that clients of the shared channel servers only send one message per CLAIM of its shared writing-end. If they held on to that CLAIM and sent more than one message, all messages sent by that client within that CLAIM block will be grouped together and received in sequence by the shared channel server without being interleaved with messages from other clients. However, for many applications the client must relinquish its CLAIM after sending one message and, then, the problem (and solution) in the above note apply. See the philosopher.0 process below for an example of this.]
An example is the fork process from the Dining
Philosophers system. As suggested earlier, this can be made
to service its competing philosophers fairly by:
PROC fair.fork.0 (CHAN BOOL left?, right?)
WHILE TRUE
BOOL any:
SEQ
PRI ALT
left ? any -- picked up by left phil
left ? any -- put down by left phil
right ? any -- picked up by right phil
right ? any -- put down by right phil
PRI ALT
right ? any -- picked up by right phil
right ? any -- put down by right phil
left ? any -- picked up by left phil
left ? any -- put down by left phil
:
which is neat enough! Doing this with via a shared channel (on which both philosophers try to pick it up) means that we need a separate channel for the release – as opposed to the above, where each philosopher uses the same channel for pick up and release. The code for this server becomes very trivial:
PROC fair.fork.1 (CHAN BOOL pick.up?, put.down?)
WHILE TRUE
BOOL any:
SEQ
pick.up ? any -- get picked up by someone
put.down ? any -- get put down by that same someone
:
Note: this fair.fork.1 process is, in fact, a general
(and fair) mutex, sometimes known as a binary semaphore.
So, the channels pick.up and put.down might
be better renamed, respectively, acquire and
release.
With fair.fork.1, the code for the clients (the philosophers)
is slightly harder.
For one thing, they now need two channels (both shared by other
philosphers) to each fork – instead of one. And they have
to make a CLAIM on those channels before they can
use them. Here it is:
PROC philosopher.0 (SHARED CHAN BOOL pick.up.left!, put.down.left!,
SHARED CHAN BOOL pick.up.right!, put.down.right!,
...)
WHILE TRUE
SEQ
... thinking
... hungry, get past security
PAR
CLAIM pick.up.left! -- pick up
pick.up.left ! any -- forks
CLAIM pick.up.right! -- in
pick.up.right ! any -- parallel
... eating
PAR
CLAIM put.down.left! -- put down
put.down.left ! any -- forks
CLAIM put.down.right! -- in
put.down.right ! any -- parallel
... leaving, let security know
:
[Note: it's because we insist that the philosopher picks up its forks in parallel that it must relinquish its CLAIM on the pick-up channels immediately after using them – it needs to know when both events have happened (so that it can eat) and, for that, both parallel actions (inlcuding the claims) have to terminate.]
A final thought: if we didn't mind programming the philosophers
to pick up their forks serially (and, with the security
guard refusing entry to all five at the same time, this is safe),
we could do things even more simply.
CLAIMing a shared channel-end grabs a mutex
lock implemented by the occam-pi run-time.
We could just use CLAIMs on those shared channel-ends
as pre-requisites for eating and never actually send messages over
the channels at all:
PROC philosopher.1 (SHARED CHAN BOOL pick.up.left!, put.down.left!,
SHARED CHAN BOOL pick.up.right!, put.down.right!,
...)
WHILE TRUE
SEQ
... thinking
... hungry, get past security
CLAIM pick.up.left!
CLAIM pick.up.right!
... eating
... leaving, let security know
:
Making each CLAIM models grabbing the fork –
only one philosopher can succeed at a time.
Exiting the CLAIM block models putting the fork
back – another philosopher may now grab it.
We now don't need any fork processes at all –
just the pick-up/put-down channels, whose receiving ends may
be safely left dangling (since nothing ever gets sent down them!).
The above is, however, slightly clever programming and that can
quickly lead to tears.
Note that making a CLAIM on a SHARED
channel-end and not using it in the claim block is exactly
the semantics Java offers from its monitor concept:
Java: occam-pi:
synchronize (someObject) { CLAIM some.channel!
... stuff ... stuff (don't use some.channel!)
}
However, nested monitor locks – like nested channel claims –
do not always give us what we want.
Hence, from Java 1.5 onwards, Java gives us
a java.util.concurrent.Semaphore class
whose acquire and release methods give more
flexible orderings of use (and, of course, more ways for them to be
mis-used) than monitor locks.
The fair.fork.1 process above (which should be renamed
to mutex) gives us the same flexibility.
For interest, here is a fair counting semaphore process in occam-pi:
--* This is a counting semaphore providing a fair acquisition service.
-- The other ends of the acquire and release channels must be SHARED
-- amongst all user processes. To acquire this semaphore, CLAIM the
-- acquire channel and send TRUE down it. To release, CLAIM the release
-- channel and send TRUE.
--
-- Warning: this semaphore must first be acquired before being released.
-- Releasing a semaphore before acquiring it will lead to deadlock.
-- Forgetting to release an acquired semaphore will also lead to deadlock.
--
-- @param n The number of processes allowed to hold this semaphore
-- at the same time (must be greater than zero).
-- @param acquire The channel to acquire this semaphore.
-- @param release The channel to release this semaphore.
--
PROC semaphore (VAL INT n, CHAN BOOL acquire?, release?)
INITIAL INT count IS n:
WHILE TRUE
BOOL any:
ALT
(count > 0) & acquire ? any
count := count - 1
release ? any
count := count + 1
:
Finally, note that the security guard in the Dining Philosophers'
college can be implemented with the above semaphore,
initialised with a count of 4.
Keywords: fair-alt , shared-channel
Referrers: Question 30 (2009) , Question 45 (2009) , Question 72 (2008) , Question 74 (2008) , Question 68 (2007)
2006 |
Submission reference: IN1059
Does the display process only need to take one array of channels from all of the the process that are reporting to it? If so then I assume this channel will be shared among the philosopher, fork and security procs?
Yep, that's pretty much correct. But your second sentence is inconsistent with your first. Your "this channel" suggests splitting a single channel up amongst the various processes; whereas you talk about an array of channels in the previous sentence.
What you should do is give each of the philosopher, fork and security processes a single channel
from within an array of channels –
see slide 60 from applying.ppt.
As described in the lectures, you can do it with a single channel
– and it's much easier (especially for the display process, which
then only has one channel to deal with).
But that means using a SHARED channel and CLAIM blocks,
as presented in slides 3-26 of shared-etc.ppt.
Note: there is some stuff relating to shared-channels in previous anon Q+A, but these use the old-style which involves SEMAPHOREs and explicit claim and releases (not particularly nice, but these were before the days of mainstream occam-pi).
Keywords: coursework , q7 , shared-channel
Referrers: Question 68 (2006)
2004 |
Could you explain "SHARED" channels again and maybe give an example ? From the class they seem like a cleaver idea but now when it comes to coding them I am a little lost.
[Note: the first part of this answer is now obsolete! The SEMAPHORE data type is no longer supported by the multicore run-time systems for occam-pi. The second part of this answer (using SHARED channel) is the correct way to do things now.]
There are two ways to do shared-channels in occam, and which one you choose will depend on whether you're coding on Linux or Solaris.
KRoC/Linux has built-in support for shared channels, called "anonymous channel types" in the form most useful for Q7. You can find a fairly terse example of these here.
Shared channels on the KRoC installed on raptor must be done manually -- by turning off compiler usage-checks and using "SEMAPHORE"s to provide mutual exclusion.
For comparison and reference, below are two equivalent versions of a simple test program that use shared channels:
#INCLUDE "semaphore.inc" -- NOTE: this version is no longer valid.
#USE "course.module"
PROC hello (SEMAPHORE sem, CHAN BYTE out!, VAL INT id)
SEQ
claim.semaphore (sem)
--{{{ output stuff
out.string ("hello world from ", 0, out!)
out.int (id, 0, out!)
out.string ("*n", 0, out!)
--}}}
release.semaphore (sem)
:
PROC main (CHAN BYTE kyb, scr!, err!)
#PRAGMA SHARED scr
SEMAPHORE sem:
#PRAGMA SHARED sem
SEQ
initialise.semaphore (sem, 1)
PAR i = 0 FOR 10
hello (sem, scr!, i)
:
and (if using KRoC):
#USE "course.module"
PROC hello (SHARED CHAN BYTE out!, VAL INT id)
CLAIM out!
SEQ
--{{{ output stuff
out.string ("hello world from ", 0, out!)
out.int (id, 0, out!)
out.string ("*n", 0, out!)
--}}}
:
PROC main (SHARED CHAN BYTE scr!)
PAR i = 0 FOR 10
hello (scr!, i)
:
but (if using the Transterpreter – see Question 22 (2008)):
#USE "course.lib"
PROC hello (SHARED CHAN BYTE out!, VAL INT id)
CLAIM out!
SEQ
--{{{ output stuff
out.string ("hello world from ", 0, out!)
out.int (id, 0, out!)
out.string ("*n", 0, out!)
--}}}
:
PROC main (CHAN BYTE key?, scr!, err!)
SHARED ! CHAN BYTE screen: -- output end shared
PAR
PAR i = 0 FOR 10
hello (screen!, i)
WHILE TRUE -- byte "id" process
BYTE ch:
SEQ
screen ? ch
scr ! ch
:
Keywords: q7 , shared-channel
2003 |
I've seen that in the dining philosophers animation, when fair ALTing the status reports from the philosophers, forks and security guard, you may have three different case protocols, and have one channel going to the display proc for the philosopher, one for the forks, and one for the security guard. Our seminar leader said that semaphores should be used for the channels where more than one PROC could output at the same time (for philosophers and forks). Is it ok to use `semaphore.inc' in the course library on raptor, or do we need to produce our own implementation?
[Note: this answer is no longer valid! The SEMAPHORE data type is no longer supported by the multicore run-time systems for occam-pi. The correct way to share channels is to use the SHARED channel mechanism that is now part of the language (and mentioned in the last paragraph below).]
If you wish to share channels in this way, yes, using the `semaphore.inc' provided is fine -- and encouraged. If you look at the contents of the file, you'll see that implementing your own is very much non-trivial (although you (CS) know the theory from CO501).
This file defines a `SEMAPHORE' data-type and various PROCs to manipulate the semaphore. Since usage-checking must be disabled on the shared variables, there is a substantially increased risk of program error. Mis-handling of such semaphores can cause anything from deadlock to a serious run-time error (segmentation fault of KRoC). Using lots of channels and ALTing is always a safer bet, but not as efficient or ideal.
The new occam provided in KRoC/Linux has support for SHARED channels at the language level; thus ensuring a basic safe usage (deadlock can still occur through design error, however).
Keywords: shared-channel
|
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. |
