Thread scheduling imbalance / starvation

[Alan Bateman]

On 16/04/2023 19:05, Martin Traverso wrote:
> :
>
> From what Ron described above, my understanding is that some threads 
> don't even get a chance to start since the first N threads keep 
> looping with no contention (acquiring and releasing the semaphore) and 
> thereby preventing the second N threads from ever being scheduled.

Yes, it's N threads spinning doing acquire/release on a semaphore with N 
permits. Another N threads (the second batch) have been started but 
haven't executed due to the greedy thread scheduling.

>
> If I add a call to Thread.yield() or Thread.sleep() for 1 ns just 
> *once* before the loop while holding the semaphore, then it works as I 
> would expect. My hypothesis is that that causes the scheduler to pick 
> one of the threads that has been waiting to start to run, which 
> subsequently makes it to the acquire() call and at some point it 
> becomes a contended acquire. The fair semaphore does its job from then on.
>
>     Thread.ofVirtual().start(() -> {
>         semaphore.acquireUninterruptibly();
>         Thread.yield();
>         semaphore.release();
>
>         while (true) {
>             semaphore.acquireUninterruptibly();
>             counter.incrementAndGet();
>             semaphore.release();
>         }
>     });
>

The effect of the Thread.yield here is that the first N threads will 
release the underlying carrier to allow the second batch of N threads to 
execute. The first attempt by threads in the second batch of N thread 
will likely block and be queued until there is an available permit. So 
you end up with 2*N threads competing to acquire permits.

-Alan