[libdispatch-dev] libdispatch's thread model

[Michael Ash]

On Thu, Jan 28, 2010 at 12:20 PM, Daniel A. Steffen <dsteffen at apple.com> wrote:
>
> On Jan 28, 2010, at 7:07 AM, Mario Schwalbe wrote:
>> 1. Let's assume someone manages to submit n jobs that block each other causing a
>> deadlock on a machine having n processors. The thread pool implementation isn't able
>> to execute any other jobs anymore, so the application can be considered erroneous/dead.
>> The work queue implementation is still able to execute jobs waiting in the queue, so
>> the application (as a whole) can still make some progress, but cannot finish either,
>> because - assuming the results of those blocked jobs are important - it at some point
>> has to wait for their results (dispatch_group_wait()) which will block forever as well.
>>
>> 2. A deadlock requires a cycle in the dependency graph. But jobs submitted that are
>> still waiting in the queue, won't be executed yet, and, hence, won't be able to acquire
>> any resource to prevent other jobs from executing.
>
> not necessarily a cycle, a dependency chain longer than the size of the thread pool is sufficient:
>        sem1 = dispatch_semaphore_create(0);
>        sem2 = dispatch_semaphore_create(0);
>        dispatch_async(q, ^{dispatch_semaphore_wait(sem1);});
>        dispatch_async(q, ^{dispatch_semaphore_wait(sem2); dispatch_signal(sem1);});
>        dispatch_async(q, ^{dispatch_signal(sem2);});
>
> this will deadlock if the pool size is 2 but work correctly with a larger pool (or with the workqueue implementation)

Or to put it another way, every dispatch block has an implicit
dependency on the thread pool itself, so when you add that to the
analysis, this situation *does* have a cycle, because the first two
acquire thread pool resources, and the last two wait on thread pool
resources before they can run.

This is something to watch out for even on the Mac, because the thread
pool maxes out at, I believe, 512 threads. It's tough, but not
impossible, to hit that number inadvertently and have everything seize
up.

Mike