thread scheduling at mutex unlock

[Alfred Perlstein]

[[ -stable removed, additional cc' to interested parties ]]

Guys,

Andriy's issue appears to actually be severe.

The main issue is that we have a starvation situation for heavily
contended mutexes.

If I am reading the test case, any heavily contented mutex will
exhibit this problem.

You do NOT need a sleep(3) call to provoke it, you just need the
following scenario:

thread A:
10:
  gets mutex
  does heavy processing (N (99%) of its time)
  releases mutex
  does something else (M (1%) of the time)
  goto 10;

thread B...:
  tries to get mutex...
  do not care.


The way that scheduling works means that you can do a back of a
napkin calculation to figure out that this sort of situation will
certainly starve threads without some support from the underlying
locking mechanism to fix it.

Let's say that that "thread A" spends N (99%) of it's time doing
"heavy processing" then that means that only M (1%) of the time the
scheduler will preempt it at the correct time so that it is not
holding the lock.

Clearly this will lead to starvation where "thread A" has a
99% chance per-quantum of being left holding the lock when it
is preempted.

I think it's time that people look into the so-called "working"
implementations (linux/solaris) for ways to handle this sort of
thing.

. <- that's a period.

-Alfred