Actor starvation problem

Hi Erik,

> I don't have time to dig in a figure out if my analysis is right (the
> innards of the FJ pools have always left me in a state of confused awe),
> but I think it's at least close. Basically if one task hogs a thread,
> and all the other threads in the pool are busy so they don't do any task
> stealing, then tasks that are directly placed on the dequeue of the
> hogged thread never get executed.

Yes, that's actually what happened. Thanks for hinting at it!

> I'd like to suggest that the Scheduler be modified so that it detects
> this situation and moves the tasks in the hogged thread's dequeue to
> other threads. What I'm picturing would work something like this:
>
> 1. Scan the worker threads and record their current task (use a
> weakreference so we don't get memory leaks!)
> 2. Wait a while
> 3. Scan the worker threads again, if a thread is still on the same
> task and has tasks on its dequeue, distribute the tasks to threads
> that are moving through their dequeues
> 4. If all the threads are stuck, and the pool size is less than the
> max, spawn another worker thread

To solve the problem at hand, I came up with a much simpler solution:
Instead of always putting new tasks into the local dequeue (if
possible), put them into the global dequeue with a chance of, say, 2%.
The rate shouldn't be too high so that work-stealing still has a
positive effect. If it's too low, the actual behavior may not be very
"fair".

This solves the starvation problem in the gears example on
stackoverflow, since the gear actors will sometimes put their next task
into the global queue. When this happens, a different gear is going to
be executed, since the current worker's dequeue is empty causing it to
get a task from the global dequeue.

I added a Boolean `fair` parameter to `ForkJoinScheduler`, which enables
this behavior; it's enabled by default for actors. However, it incurs a
small performance hit: around 10% for chameneos-redux. Fortunately, the
above situation cannot occur with `Reactor`s, since they cannot receive
while holding on to their thread. Therefore, `Reactor` uses a
`ForkJoinScheduler` with `fair` disabled.

The changes are available in trunk (r20950).

> I'm not sure if this is possible without screwing up the locking
> mechanisms in the pool and thus hurting performance. Another option
> could be to have the worker threads descend into task-stealing mode a
> psuedo-random intervals (probably be counting tasks executed) even if
> they have tasks to execute on their own dequeue.

That might be a workable alternative.

Cheers,
Philipp

Hi Erik,

I don't have time to dig in a figure out if my analysis is right (the innards of the FJ pools have always left me in a state of confused awe), but I think it's at least close.  Basically if one task hogs a thread, and all the other threads in the pool are busy so they don't do any task stealing, then tasks that are directly placed on the dequeue of the hogged thread never get executed.

Yes, that's actually what happened. Thanks for hinting at it!

I'd like to suggest that the Scheduler be modified so that it detects this situation and moves the tasks in the hogged thread's dequeue to other threads.  What I'm picturing would work something like this:

  1. Scan the worker threads and record their current task (use a
     weakreference so we don't get memory leaks!)
  2. Wait a while
  3. Scan the worker threads again, if a thread is still on the same
     task and has tasks on its dequeue, distribute the tasks to threads
     that are moving through their dequeues
  4. If all the threads are stuck, and the pool size is less than the
     max, spawn another worker thread

To solve the problem at hand, I came up with a much simpler solution:
Instead of always putting new tasks into the local dequeue (if possible), put them into the global dequeue with a chance of, say, 2%. The rate shouldn't be too high so that work-stealing still has a positive effect. If it's too low, the actual behavior may not be very "fair".

This solves the starvation problem in the gears example on stackoverflow, since the gear actors will sometimes put their next task into the global queue. When this happens, a different gear is going to be executed, since the current worker's dequeue is empty causing it to get a task from the global dequeue.

I added a Boolean `fair` parameter to `ForkJoinScheduler`, which enables this behavior; it's enabled by default for actors. However, it incurs a small performance hit: around 10% for chameneos-redux. Fortunately, the above situation cannot occur with `Reactor`s, since they cannot receive while holding on to their thread. Therefore, `Reactor` uses a `ForkJoinScheduler` with `fair` disabled.

The changes are available in trunk (r20950).

I'm not sure if this is possible without screwing up the locking mechanisms in the pool and thus hurting performance.  Another option could be to have the worker threads descend into task-stealing mode a psuedo-random intervals (probably be counting tasks executed) even if they have tasks to execute on their own dequeue.

That might be a workable alternative.

Cheers,
Philipp

Hi Erik,

I don't have time to dig in a figure out if my analysis is right (the innards of the FJ pools have always left me in a state of confused awe), but I think it's at least close.  Basically if one task hogs a thread, and all the other threads in the pool are busy so they don't do any task stealing, then tasks that are directly placed on the dequeue of the hogged thread never get executed.

Yes, that's actually what happened. Thanks for hinting at it!

I'd like to suggest that the Scheduler be modified so that it detects this situation and moves the tasks in the hogged thread's dequeue to other threads.  What I'm picturing would work something like this:

  1. Scan the worker threads and record their current task (use a
     weakreference so we don't get memory leaks!)
  2. Wait a while
  3. Scan the worker threads again, if a thread is still on the same
     task and has tasks on its dequeue, distribute the tasks to threads
     that are moving through their dequeues
  4. If all the threads are stuck, and the pool size is less than the
     max, spawn another worker thread

To solve the problem at hand, I came up with a much simpler solution:
Instead of always putting new tasks into the local dequeue (if possible), put them into the global dequeue with a chance of, say, 2%. The rate shouldn't be too high so that work-stealing still has a positive effect. If it's too low, the actual behavior may not be very "fair".

This solves the starvation problem in the gears example on stackoverflow, since the gear actors will sometimes put their next task into the global queue. When this happens, a different gear is going to be executed, since the current worker's dequeue is empty causing it to get a task from the global dequeue.

I added a Boolean `fair` parameter to `ForkJoinScheduler`, which enables this behavior; it's enabled by default for actors. However, it incurs a small performance hit: around 10% for chameneos-redux. Fortunately, the above situation cannot occur with `Reactor`s, since they cannot receive while holding on to their thread. Therefore, `Reactor` uses a `ForkJoinScheduler` with `fair` disabled.

The changes are available in trunk (r20950).

I'm not sure if this is possible without screwing up the locking mechanisms in the pool and thus hurting performance.  Another option could be to have the worker threads descend into task-stealing mode a psuedo-random intervals (probably be counting tasks executed) even if they have tasks to execute on their own dequeue.

That might be a workable alternative.

Cheers,
Philipp