Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

["Berke Durak" <berke.durak@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4169 bytes --]

On Mon, May 19, 2008 at 1:45 PM, Martin Berger <M.Berger@doc.ic.ac.uk>
wrote:

> Jon Harrop wrote:
>
>  Similarly, avoiding threads removes concurrency bugs...
>>>
>>
>  I don't believe you have removed any concurrency bugs. I think you just
>> pushed them around a bit.
>>
>
> I couldn't agree more. If you 'avoid' concurrency by writing your own
> 'sequential' event handling code, you have not removed the concurrency,
> you just face it in a slightly different form, and you have to
> program the event handling code yourself, rather than relying
> on a tried and tested library, i.e. you have an additional
> source of bugs, without removing the problems that are inherent
> in concurrency (e.g. deadlocks, livelocks, fairness ...). There
> are reasons why writing your own concurrency mechanisms might
> be the way to go, but it's a highly non-trivial endeavor.


Let's say that there are two kinds of concurrency bugs : consistency bugs
and
synchronization bugs.

- Consistency bugs arise when two or more threads mutate the same
datastructure concurrently,
leading to inconsistent data.

- Synchronization bugs occur when you have things like starvation (a queue
with waiter never gets filled),
unfairness (some code almost never gets a chance to run), deadlocking (ye
olde deadlock), livelocking
(threads spend time communicating back and forth without making progress),
etc.

Avoiding threads means to me that you're either using Lwt-style monadic
threads, or an event-based
framework (the two being similar).

Avoiding threads almost eliminates consistency bugs.

Code you write is, by default, atomic.  Concurrency must be explicitly
invoked, and
generally shows in the types of functions using concurrency (one of the
situations where monad
creep seems to be a good thing.)

If you take a data structure that was not intended for concurrency, then it
will almost certainly be
concurrency-safe unless it is some kind of structure that can store thunks
and invoke them, and
you store concurrency-producing thunks in them.

Hence, using, say, Lwt, I can have tens of thousands of lightweight threads
that happily mutate
an unprotected, possibly complex datastructure implemented in a
concurrency-agnostic module.
For instance, I can and do use a global reference to a Map module and mutate
it without any lock
of any kind.

Now let me classify synchronization bugs in two sorts :
  - Type A: Logical synchronization bugs due to algorithmic issues
(livelocks, etc.)
  - Type B: Synchronization bugs due to consistency bug avoidance
techniques,

Short of a formal system where concurrency properties are statically proven,
you probably can't
avoid type A bugs, since it's a high-level correctness issue.

Take for instance two mutually-recursive functions calling themselves using
an inter-process mechanism.
If they were supposed to terminate, it's a livelock, otherwise - if they are
some kind of persistent client-server
combination, they are running as usual.  Yet they will be using the same
primitives.

So no one expects logical synchronization bugs to be statically detected.

Type B bugs typically occur when you or someone else peppers code with
locks/unlock pairs (or "synchronized"
attributes, or "perform_under_lock" higher-order function...) and get a
deadlock.

While some type B bugs can be dynamically (and even statically) detected, or
some lock/unlock pairs be
removed by your JIT, others type B bugs will slip thru: even if you maintain
some kind of dependency graph
between locks, as you cannot model a synchronization effect conditioned on
another lock if the unlocking goes
thru a piece of unknown code.

If you avoid threads, type A bugs become much less likely.  Hence you won't
need to wrap almost
every shared datastructure with locks to prevent them, and hence you will
avoid a lot of type B bugs.

In short, with monadic threads, you can safely invoke non-concurrent code
from concurrent code.  (The inverse
can be dangerous - but you usually don't do this anyway since you will end
up optaining an 'a Lwt.t).
This means that locking is almost never needed and hence your code is
safer.  Sequential, yes, but safer.
-- 
Berke Durak

[-- Attachment #2: Type: text/html, Size: 5221 bytes --]