question about concurrency implementation

Phil Trinder
Thu, 21 Mar 2002 09:19:44 +0000 (GMT Standard Time)


Alastair Reid wrote:

> > Just to be sure we agree on terminology: some people like to
> > distinguish between "parallelism" and "concurrency".
> > 
> > Parallelism is a way of going faster but doesn't change your
> > programming model.  Implemented correctly, a parallel implementation
> > yields the same results as a sequential implementation - it just runs
> > faster.  (This is ignoring the effects of interaction with the outside
> > world, of course - since that can also affect determinism.)  Parallel
> > Haskell adds "par" and friends (operations which have no effect on the
> > semantics of your program).
> > 
> > Concurrency changes your programming model.  A concurrent program is
> > allowed to give different results and interesting interactions
> > (including race conditions) between threads.  A concurrent program may
> > run on a single processor.  Concurrent Haskell adds forkIO,
> > killThread, MVars, etc (operations which affect not just the semantics
> > of your program but also the way the semantics are defined).

We distinguish between parallel, concurrent and distributed depending on the 
number of processors and whether threads are *stateful*, i.e. access stateful 
objects like Mvars or Files, or *stateless*. That is:

Sequential, e.g. Haskell 98:  
  1 PE, 1 Stateful thread,  0 stateless threads
Concurrent, e.g. Concurrent Haskell: 
  1 PE, N Stateful thread,  0 stateless threads
Parallel, e.g. GpH: 
  N PEs, 1 Stateful thread, N stateless threads
Distributed, e.g. GdH: 
  N PEs, N Stateful thread, N stateless threads

In fact these languages form an inclusion hierarchy, e.g. GdH is a superset of 
both GpH and Concurrent Haskell:

                 /   \
               GpH  Conc. Haskell
                 \   /
               Haskell 98

Dean Herington wrote:
> I've asked these questions in order to convince myself that multiple
> threads can (and will) cooperate in lazily evaluating a value they share,
> without need for any special programming.  In particular, I plan to have
> multiple threads share values whose computations involve uses of
> `unsafePerformIO` (the safety of which my application's usage pattern
> guarantees).

The key issue is whether the 'values' are stateful (e.g. Mvars or Files) or 
stateless (e.g. a shared Haskell variable). Sharing stateless objects between 
parallel, concurrent, or distributed threads preserves sequential semantics, 
but sharing stateful objects can introduce non-determinism, unless you have 
additional properties.

Phil Trinder
Department of Computing and Electrical Engineering
Heriot Watt University
Edinburgh, EH14 4AS

Teleph: +44 (0)131 451 3435
Depart: +44 (0)131 451 3328
Fasmly: +44 (0)131 451 3327