Re: [Caml-list] Thread behaviour

["Török Edwin" <edwin+ml-ocaml@etorok.net>]

On 09/30/2013 06:12 PM, Tom Ridge wrote:
> On 30 September 2013 10:18, Xavier Leroy <Xavier.Leroy@inria.fr> wrote:
>> On 2013-09-27 12:10, Tom Ridge wrote:
>>> I have a little program which creates a thread, and then sits in a loop:
>>> [...]
>>> When I run the program I get the output:
>>>
>>> 1
>>> 2
>>>
>>> and the program then sits in the loop.
>>
>> On my machine (OCaml 4.01.0, Ubuntu 12.04 LTS), I sometimes see what
>> you see, and sometimes I see the expected output:
>>
>> 1
>> 2
>> 3
>> hello
>> 4
>>
>> It all depends on the whim of the OS scheduler.  OCaml has no control
>> over it.  And you shoudn't expect any kind of fairness from the OS
>> scheduler, esp. Linux's, which gladly jettisons any pretense of
>> fairness in the hope of getting better throughput.
>>
> 
> Ah! You are saying that the problem (maybe) lies with the Linux scheduler.
> This had never occurred to me. Probably because I assumed the Linux
> phrase "completely fair scheduler" meant something (although
> admittedly, I never tried to find out what).

I think there are two things to consider here:
 * deciding which process(es) to run on the CPU(s), when there are multiple runnable processes/threads (i.e. they are not blocked/sleeping). This is called CFS in Linux, and you can check how well it behaves with top %CPU, /proc/sched_debug, etc.
Although it has some heuristics too, for example related to pipe(2) handling.

 * deciding how to lock a mutex / what thread to wake up when a mutex is released/ condvar is signaled

This is handled first in libpthread (IIRC there is some limited user-space spinning involved), then handed off to the kernel via futex(7).
Depending how its implemented there can be fairness issues, see also 'thundering herd' problem, etc.
AFAIK the kernel uses ticket locks for its spinlocks to get more fairness since quite some time (see http://lwn.net/Articles/267968/ and http://lwn.net/Articles/531254/), but I lost track whether futexes actually use this mechanism or something else. If there is something wrong with the fairness in thread scheduling I'd expect it to be in this part though.

As far as OCaml is concerned one might try to implement something similar to ticket locks in userspace
(or have an array of condition variables and wake up directly the thread we want, and track their execution times?), but it won't be as efficient as if the kernel was (fixed) to do it properly.

Best regards,
--Edwin