Re: Losing abstraction

[Richard Beton <richard.beton@xxxxxxxxxx>]

Roy Wilson wrote:

> Speaking of which, has anyone seen and care to comment on the following
> (especially the multiplicity of monitor-style locking strategies discussed)?
>
> http://www.research.ibm.com/journal/sj/391/dimpsey.html

Thanks for pointing this out. It's an interesting article. It highlights, sadly,
the problems of working with conventional monitors on multiprocessor systems.

The article shows graphs (e.g.
http://www.research.ibm.com/journal/sj/391/dimps1.jpg) in which the number of
threads and the number of processors is strongly correlated - more thread than
processors leads to gross inefficiencies.

Two decades ago, the transputer developed a simple scheme for blocking threads
which made use of execution queues. Blocked threads are taken off their
execution queue. Upon reawakening, they get put back on the queue. Since the
processor only spends time doing those processes that are on the execution
queue, blocked threads consume no time. Therefore the number of threads doesn't
matter. These concepts were built into the occam language using channel
communications. Since then, workers in the occam field have developed further
ideas to include general semaphore locks (allowing sharing of channels and other
resources) and other, higher level, paradigms for thread synchronisation. The
impressive efficiencies achieved depend largely on the use of process queues.

The other main benefit of working with higher level abstractions is of course
that they are easier to use. I have experience with the Posix lightweight thread
library and also with occam channels and higher level paradigms. Learning to use
the former is not a task to be undertaken lightly! For the latter, you may
already know occam, but if not you can still make use of the channel approach by
using the JCSP Java library. You just don't get the thread efficiency benefits
because JCSP is built on top of Java monitors.

The article goes on to discuss fairness and thread starvation. Peter Welch et al
discussed this at some length on this mailing list (see also "Wot No Chickens"
http://www.hensa.ac.uk/parallel/groups/wotug/java/discussion/3.html). This
exposes a 'feature' of the Java monitor architecture, namely that wait and
notify operate in a way that can lead to starvation. This differs from C.A.R.
Hoare's original monitor idea. The article seems to suggest that starvation
ain't that bad really. After all, if you have loads of peer worker threads, why
should it matter if some are busier than others? I'll defer to others for a
definite answer to this, but it seems an unsafe assumption that all the threads
are equivalent peers. How a multiprocessor system might become inefficient
becaseu of starvation of some threads is an issue too.

Rick
--
Richard Beton B.Sc. C.Phys. M.Inst.P.
Roke Manor Research Limited (http://www.roke.co.uk/)
--------- Standard Disclaimer about my own views etc etc --------
ICQ: 56840977. Homepage: http://www.beton.freeserve.co.uk/