STM and fairness

[Josef Svenningsson]

On Fri, Feb 29, 2008 at 4:27 PM, Roberto Zunino <zunino at di.unipi.it> wrote:
> 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.
>
That's not quite right since there is no true parallelism here. I'm
running on a single core (which I suppose I could have mentioned) and
so it is up the scheduler to make sure that processes get a fair
chance at doing their business, i.e. achieving fairness. The point I
was trying to make is that the scheduler isn't doing a very good job
in this case.

>  I suggest you put some random delay in your fairness tests, maybe using
>  unsafeIOtoSTM, so that you can improve starvation ;-)
>
I'd rather fix the scheduler.

>  Also, try running a very slow (much-delayed) transaction againts several
>  fast ones. I expect the slow one will never reach completion.
>
Indeed. This is a well known problem with STM but afaict orthogonal to
the problem I'm talking about.

>  AFAIK, achieving fairness in STM can be quite hard (not unlike other
>  mainstream approaches to concurrency, sadly).
>
Yes. Still, in the particular situation I showed I think we can do a
better job than what is currently being done.

Cheers,

Josef