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

[Brian Quinlan]

On Nov 13, 2009, at 4:27 PM, Jeffrey Yasskin wrote:

> 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.

So you have something like this:

def Future.result(self, timeout=None):
   with some_lock:  # would have to think about locking here
     do_work_locally =  (threading.current_thread in  
self._my_executor.threads and
         self._my_executor.free_threads == 0 and
         timeout is None):

That's pretty clever. Some things that I don't like:
1. it might only be applicable to executors using a thread pool so  
people
     shouldn't count on it (but maybe only thread pool executors have  
this
     deadlock problem so it doesn't matter?)
2. it makes the implementation of Future dependent on the executor that
      created it - but maybe that's OK too, Future can be an ABC and
      executor implementations that need customer Futures can subclass  
it

Cheers,
Brian