[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Cost of Choise operators in CSP?



I wonder how Occam does it. Since I did a bit of occam programming
when preparing a benchmark between concurrent languages, I tentatively
remember that you can't choose between output expressions, whereas CML
allow it. This hints to a different philosophy of how programs should
be specified. Allowing choice between output expressions means that
you have to cope with an altogether different fairness issue, where
input and output expressions are considered symmetrically. My advisor,
Frederic Peschanski, has implemented a VM for the pi-calculus that
does just that and is quite fair. I do not know however if it has been
published yet, so I cannot give details.

JA

On Wed, May 19, 2010 at 10:22 AM, Chalmers, Kevin
<K.Chalmers@xxxxxxxxxxxx> wrote:
> I remember reading somewhere about the exact implementation in occam, but can't remember where (someone with a broader knowledge could probably help).
>
> For JCSP, the choice selection goes through two stages. ÂFirst, the Alt iterates through the list of guards (channels, timers, etc.) and checks if any one of these is ready. ÂThis involves gaining exclusive access to each guard in turn, checking its state, and returning true or false based on the readiness of the guard. ÂOnce the enable sequence detects a ready guard, it then must iterate backwards through the list from the ready guard, disabling the guards (again, requiring exclusive access to the guard) in turn. ÂIf it finds that one of these guards has become ready, then that guard is selected instead.
>
> There are a couple of caveats. ÂObviously, there might be a case where no guard is ready. ÂIn this case, the Alt causes the process performing the choice to wait until a guard has become ready. ÂThis is not unexpected, but requires the guard that becomes ready to signal the Alt, requiring exclusive access to the Alt. ÂThis signal may occur during an enabling or disabling sequence also.
>
> The second consideration is the multi-way synchronisation event. ÂThis requires somewhat more complexity in implementation. ÂSee the Integrating and Extending JCSP paper (available from wotug.org or JCSP home) for more information.
>
> Therefore, the cost of performing a select can be as little as 1 (first guard checked is ready) or as much as n (last guard checked is ready or no guards are ready); the individual check requiring gaining a lock on the guard to be checked (and some minor state checking).
>
> A good application to test Alt cost is the StressedAlt test in the JCSP demos (or the equivalent in occam-pi). ÂIt will give you some hard numbers on select time if that is what you are looking for.
>
> Kevin
>
> -----Original Message-----
> From: Mailing_List_Robot [mailto:sympa@xxxxxxxxxx] On Behalf Of Campbell, John
> Sent: 18 May 2010 23:26
> To: Occam Family
> Subject: Cost of Choise operators in CSP?
>
> Hi All
> Can anyone point me at a discussion of the cost of actually implementing the
> choice operator as it functions in CSP?
> Thanks. -jc
>
> Edinburgh Napier University - one of the top 10 universities in the UK for graduate employability (HESA 2009) and proud winners of the Queen's Anniversary Prizes for Higher and Further Education 2009, awarded for innovative housing construction for environmental benefit and quality of life.
>
> This message is intended for the addressee(s) only
> and should not be read, copied or disclosed to anyone else outwith the University without the permission of the sender. It is your responsibility to ensure that this message and any attachments are scanned for viruses or other defects.
> Edinburgh Napier University does not accept liability for any loss or
> damage which may result from this email or any attachment, or for errors or omissions arising after it was sent. Email is not a secure medium. Email entering the University's system is subject to routine monitoring and filtering by the University.
>
> Edinburgh Napier University is a registered Scottish
> charity.
> Registration number SC018373
>
>
>
>