Finalizers etcetera

[Alastair Reid]

> (A mutex lock is required to ensure that the pending queue is not
> traversed more than once, but that is all I think.)

I don't understand how this would work in single-threaded systems (like
I understand NHC to be).

Using mutexes in single-threaded systems results in either no
protection or deadlock.  Which outcome happens depends on what happens
when a thread tries to take a lock it already holds (if it increments
a counter and succeeds, you get no protection; if it blocks the
thread, you get deadlock).

> I understand that there are more tricky issues in concurrency, to do
> with shared access to resources, and scheduling policy.  However I
> am still not sure of all the details, so Alastair's concerns are
> probably well-founded.  I *think* the problem in Hugs is that the
> scheduler is co-operative, so the GC cannot simply place a triggered
> finaliser into a new thread and ignore it. 

I'd say that the problem in Hugs is the same as that in NHC.  That is,
the problem is not that the scheduler is cooperative but that it does
not have a preemptive scheduler.  Not having a preemptive scheduler means:

1) That the code was not written under the additional constraints of
   worrying about atomicity of data structure modifications.

   Here, the code referred to is mostly the C code used to implement
   the Hugs runtime system and large chunks of the standard libraries.

2) That there is no blocking mechanism handy with which to implement
   the mutexes needed to make data structure modifications atomic.

   Here the code referred to is both C code in Hugs and Haskell code
   written by the users of Hugs.

> Is this a fair characterisation Alastair?  

Sort of.

I find it a bit misleading because it seems to suggest that NHC will
not suffer from the same problem because NHC doesn't have a
cooperative scheduler.  If execution of finalizers is not synchronized
with the main IO thread (e.g., by having the Haskell programmer
explicitly call a 'runFinalizersNow' IO function, then finalizers are,
effectively, executed in a preemptive thread and you (and NHC users)
will need to start using many of the programming techniques we know
and hate from writing concurrent programs.

> (1) Why is it a disaster for a finaliser to be delayed for an
> arbitrary amount of time? 

It's a little unclear what you mean by 'arbitrary'.

I'd certainly be unhappy if finalizers never got run before the
program ended because of the massive space leak that could easily
result.  My favourite example of image-trackers based on live video
feeds would tend to die very quickly and tends to take my Linux kernel
with it (640 x 400 x 32 bits at 30 fps exhausts my desktop's 512Mb in
just 17 seconds).

Having an explicit runFinalizersNow function in the IO monad would
provide some control over this but it'd still lead to some
hard-to-resolve space leaks, it'd be ugly and it'd be fragile.

Of course, we can make it easy to fix the space leaks [and people are
bound to try this] by using unsafePerformIO to avoid the use of the IO 
monad.

  runFinalizers' :: a -> a
  runFinalizers' x = unsafePerformIO $ do{ runFinalizersNow; return x }

but this makes it effectively impossible to reason about when the
finalizers run relative to code that they share data structures with.
So, in fixing the space leaks, we introduce race conditions.  The
shared data structures, and hence, the races are in parts of the
Haskell system's runtime system and standard libraries and, more
importantly, in user's code.

We can fix the race conditions by using mutexes but, as outlined
above, use of mutexes in single-threaded systems provides no
protection or causes deadlock.

We can achieve protection and avoid deadlock by providing preemptive
threads - but that is a very high cost to pay.

> As things stand, there is no guarantee on when a finaliser will run
> anyway, just that it will do so before the end of the computation.

It'd be nice to have a portable, easily reasoned about guarantee but,
in the absence of that, we can still learn to avoid using particular
compilers, take care to enable/disable various optimization and
profiling options, etc to get reasonably timely execution of finalizers.

> (2) Why is it a disaster to have an occasional change of scheduling
> policy (from co-operative multi-tasking to pre-emption)?  Does it
> change the semantics of the concurrency model?  Does it lead to a
> possible loss of termination?  Does it disrupt some in-built
> assumptions in the runtime system?

Cooperative multitasking is harder to reason about than
single-threaded systems but it is vastly easier to reason about than
preemptive multi-threaded systems because most of the code is still
atomic.

More importantly though, once you start providing some small form of
premption (i.e., Haskell finalizers whose execution is not
synchronized with execution of C code), you have to finish the job.
That is, you have to provide mutexes (because the only useful
finalizers are those that access shared mutable data structures).
Providing mutexes requires that you are able to save the execution
context (i.e., stack, etc.) of a finalizer, continue executing the
main thread until it releases the mutex, then switch back to executing
the finalizer (because waiting until the main thread terminated or
took another lock would be unacceptable).

How easy would it be to support that in NHC?  I believe it would be hard.

--
Alastair Reid                 alastair at reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/