[stdlib-sig] futures - a new package for asynchronous execution

[Jeffrey Yasskin]

On Thu, Nov 12, 2009 at 9:19 PM, Brian Quinlan <brian at sweetapp.com> wrote:
> On Nov 8, 2009, at 6:37 AM, Jeffrey Yasskin wrote:
>>
>> --- More general points ---
>>
>> ** Java's Futures made a mistake in not supporting work stealing, and
>> this has caused deadlocks at Google. Specifically, in a bounded-size
>> thread or process pool, when a task in the pool can wait for work
>> running in the same pool, you can fill up the pool with tasks that are
>> waiting for tasks that haven't started running yet. To avoid this,
>> Future.get() should be able to steal the task it's waiting on out of
>> the pool's queue and run it immediately.
>
> Hey Jeff,
>
> I understand the deadlock possibilities of the executor model, could you
> explain your proposal would work?
>
> Would it be some sort of flag on the Future.get method e.g.
> Future.get(timeout=None, immediate_execution=False)?

I don't think a flag is the way to go at first glance, although there
could be upsides I haven't thought of. Here's what I had in mind:

After I call "fut = executor.submit(task)", the task can be in 3
states: queued, running, and finished. The simplest deadlock happens
in a 1-thread pool when the running thread calls fut.result(), and the
task is queued on the same pool. So instead of just waiting for the
task to finish running, the current thread atomically(checks what
state it's in, and if it's queued, marks it as stolen instead) and
calls it in the current thread. When a stolen task gets to the front
of its queue and starts running, it just acts like a no-op.

This can't introduce any new lock-order deadlocks, but it can be
observable if the task looks at thread-local variables.