RFC: termination detection for STM

[Simon Marlow]

Brandon Michael Moore wrote:
> On Wed, Feb 14, 2007 at 10:04:32AM +0000, Simon Marlow wrote:
>> Perhaps I'm missing something, but doesn't GHC already detect the kind of 
>> deadlock you're talking about here?  When a thread is blocked and cannot be 
>> woken up, it is sent the BlockedOnDeadMVar exception.  It's more precise 
>> than the extension you propose, because the GC is used to check which 
>> threads are unreachable and therefore cannot be woken up, so it can detect 
>> mutual-deadlock between two threads in a system that contains other running 
>> threads.
> 
> Perhaps the idea is specifically to detect from the outside when a group of
> threads is deadlocked, maybe like something that can be done with computation
> spaces in Oz, definitely like the way tree spaces work in Aardappel
> ( http://wouter.fov120.com/aardappel/ ).
> 
> Based on your description, it sounds like it wouldn't work very well to have
> a parent thread waiting on a channel, with one of the child threads set up
> to catch BlockedOnDeadMVar and send a message, lest the parent thread be
> considered deadlocked and sent BlockedOnDeadMVar itself.

Yes, that would be a problem.  You can force a thread to stay alive using 
mkStablePtr on the ThreadId, or alternatively the parent thread can catch 
BlockedOnDeadMVar and ignore it.  Neither of these solutions is particularly 
nice, I agree.

> What are the semantics of the exception? It seems like it might be tricky
> to provide any guarantees, if a thread can catch the exception and make the
> MVar live again.

A thread certainly can catch the exception and continue: the fact that the MVar 
was not reachable during GC doesn't mean it has been garbage collected, the GC 
is only being used to detect reachability in this case.  I'm pretty sure you 
could specify precisely what GHC does, but it's not trivial because you'd need 
to build a concept of reachability into the semantics.

Cheers,
	Simon