STM and fairness

[Roberto Zunino]

Josef Svenningsson wrote:
> What I want to know boils down to
> this: what order are processes run which have been woken up from a
> call to retry?

IIUC, the order of wake up is irrelevant, since *all* the threads will 
re-run the transaction in parallel. So, even if thread 1 is the first to 
wake up, thread 2 might beat it in the race, and complete its 
transaction first.

The execution model should be roughly this one: do not lock anything, 
run every read/write to TVar's in parallel, performing copy-on-write so 
that isolation is preserved. When the transaction ends, commit the data 
written in c-o-w's: lock everything, check that previously read data is 
still the same, and if it is overwrite the master copy of Tvars, unlock 
everything.

I suggest you put some random delay in your fairness tests, maybe using 
unsafeIOtoSTM, so that you can improve starvation ;-)

Also, try running a very slow (much-delayed) transaction againts several 
fast ones. I expect the slow one will never reach completion.

AFAIK, achieving fairness in STM can be quite hard (not unlike other 
mainstream approaches to concurrency, sadly).

Zun.