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

RE: Cost of Choise operators in CSP?

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