Shachar Shemesh wrote:
Hi all,
In principle, a mutex needs to satisfy two conditions:
1. It should never ever ever allow two threads/processes in
simultaneously (exclusion)
2. A blocked process/thread should know that, sooner or later, and
assuming that other threads are occasionally releasing the threads, it
will be allowed in (fairness).
If condition number 1 is not met, we will say that the mutex is
non-exclusive (read - horrendously broken).
If condition number 2 is not met, we will say that the mutex does not
prevent starvation.
I have circumstantial evidence that pthread_mutex_lock on 2.6.18, at
least on a single CPU machine, does not prevent starvation.
Attached is a program that tests this. It creates as many threads as are
specified in the command line. Each thread tries to write its unique
number into the array "results". The current position in the array is
controlled by a var called "position". Updating the variable requires
obtaining a mutex. Here's the thing: since the total amount of positions
in "results" is determined by "TEST_SIZE", and more to the point, is
predetermined, how dominant one thread over the others is solely
controlled by how fair pthread_mutex is with sharing the lock between
the threads.
The results, on my machine, are pretty bad.
I have actually had one run where the results looked like this:
$ ./mutex_fair 6
Thread b7d88bb0 started as thread #0
Thread b7587bb0 started as thread #1
Thread b6d86bb0 started as thread #2
Thread b6585bb0 started as thread #3
Thread b5d84bb0 started as thread #4
Thread b5583bb0 started as thread #5
Results: 4115693 1079530 0 5307675 1 120474
Results: 11383803 1079530 0 14561398 1 120475
Results: 24359183 1079530 0 18432014 1 373438
Results: 35356101 1079530 0 23592369 1 1635686
Results: 37747800 1079530 0 26963875 1 11958452
Results: 52274254 1079530 0 26963875 1 19682340
Joined thread #0
Joined thread #1
Joined thread #2
Joined thread #3
Joined thread #4
Joined thread #5
That's right. Within 100 million mutex acquisitions, not once did thread
number 3 managed to get the mutex, and thread number 5 only got it once.
This was not the only run that was more or less that bad, but these are
not the typical numbers.
Most runs, while not THAT bad, are still far from good. The difference
between the most and the least dominant threads can easily reach a
factor of 40 on a typical run.
Any insight into this will be most welcome.
The Futex mechanism in the kernel, which pthread_mutex_lock is using
(assusming you use an NPTL based system, but I think you are) is known
to have fairness issues with code that does tight loops that do
lock/unlock sequences, at least on SMP systems.
I would try to add a sched_yield() between the unlock and lock in that
while loop of yours.
Cheers,
Gilad
=================================================================
To unsubscribe, send mail to [EMAIL PROTECTED] with
the word "unsubscribe" in the message body, e.g., run the command
echo unsubscribe | mail [EMAIL PROTECTED]
