On 13/05/2011 12:32, Invisible wrote:

> http://tinyurl.com/64bfdmv
>
> Simon P. J. enumerating the various Haskell technologies for multi-core
> programming: sparks, threads, locks, transactions, parallel arrays...

Darren was asking me about this a while back. Apparently Haskell's 
current STM guarantees the following:

- All committed transactions see a consistent image of the system.
- Deadlock is impossible.
- Livelock is impossible.

That seems to cover just about everything, but in fact there *is* one 
bad thing that can still happen: starvation.

It is impossible for the system to get stuck in a condition where no 
progress is made. (That would be either deadlock or livelock, which are 
guaranteed not to happen.) However, it is perfectly possible for one 
particular transaction to get stuck. There are two ways this can happen:

1. If a transaction waits for a condition which will never be fulfilled, 
it can never complete. (Well, duh!)

2. It is possible for a long-running transaction to be eternally in 
conflict with an endless stream of short transactions, such that the 
short transactions complete successfully causing the long transaction to 
repeatedly restart.

(This is not livelock, since the system is still making progress: All 
the short transactions complete just fine. Only the long transaction 
gets stuck.)

Post a reply to this message