Clarifications on dispatch_queue, reentrancy and d

问题:

I need a clarifications on how dispatch_queues is related to reentrancy and deadlocks.

Reading this blog post Thread Safety Basics on iOS/OS X, I encountered this sentence:

All dispatch queues are non-reentrant, meaning you will deadlock if you attempt to dispatch_sync on the current queue.

So, what is the relationship between reentrancy and deadlock? Why, if a dispatch_queue is non-reentrant, does a deadlock arise when you are using dispatch_sync call?

In my understanding, you can have a deadlock using dispatch_sync only if the thread you are running on is the same thread where the block is dispatch into.

A simple example is the following. If I run the code in the main thread, since the dispatch_get_main_queue() will grab the main thread as well and I will end in a deadlock.

dispatch_sync(dispatch_get_main_queue(), ^{

    NSLog(@"Deadlock!!!");

});

Any clarifications?

回答1:

All dispatch queues are non-reentrant, meaning you will deadlock if you attempt to dispatch_sync on the current queue.

So, what is the relationship between reentrancy and deadlock? Why, if a dispatch_queue is non-reentrant, does a deadlock arise when you are using dispatch_sync call?

Without having read that article, I imagine that statement was in reference to serial queues, because it's otherwise false.

Now, let's consider a simplified conceptual view of how dispatch queues work (in some made-up pseudo-language). We also assume a serial queue, and don't consider target queues.

Dispatch Queue

When you create a dispatch queue, basically you get a FIFO queue, a simple data structure where you can push objects on the end, and take objects off the front.

You also get some complex mechanisms to manage thread pools and do synchronization, but most of that is for performance. Let's simply assume that you also get a thread that just runs an infinite loop, processing messages from the queue.

void processQueue(queue) {
    for (;;) {
        waitUntilQueueIsNotEmptyInAThreadSaveManner(queue)
        block = removeFirstObject(queue);
        block();
    }
}

dispatch_async

Taking the same simplistic view of dispatch_async yields something like this...

void dispatch_async(queue, block) {
    appendToEndInAThreadSafeManner(queue, block);
}

All it is really doing is taking the block, and adding it to the queue. This is why it returns immediately, it just adds the block onto the end of the data structure. At some point, that other thread will pull this block off the queue, and execute it.

Note, that this is where the FIFO guarantee comes into play. The thread pulling blocks off the queue and executing them always takes them in the order that they were placed on the queue. It then waits until that block has fully executed before getting the next block off the queue

dispatch_sync

Now, another simplistic view of dispatch_sync. In this case, the API guarantees that it will wait until the block has run to completion before it returns. In particular, calling this function does not violate the FIFO guarantee.

void dispatch_sync(queue, block) {
    bool done = false;
    dispatch_async(queue, { block(); done = true; });
    while (!done) { }
}

Now, this is actually done with semaphores so there is no cpu loops and boolean flag, and it doesn't use a separate block, but we are trying to keep it simple. You should get the idea.

The block is placed on the queue, and then the function waits until it knows for sure that "the other thread" has run the block to completion.

Reentrancy

Now, we can get a reentrant call in a number of different ways. Let's consider the most obvious.

block1 = {
    dispatch_sync(queue, block2);
}
dispatch_sync(queue, block1);

This will place block1 on the queue, and wait for it to run. Eventually the thread processing the queue will pop block1 off, and start executing it. When block1 executes, it will put block2 on the queue, and then wait for it to finish executing.

This is one meaning of reentrancy: when you re-enter a call to dispatch_sync from another call to dispatch_sync

Deadlock from reentering dispatch_sync

However, block1 is now running inside the queue's for loop. That code is executing block1, and will not process anything more from the queue until block1 completes.

Block1, though, has placed block2 on the queue, and is waiting for it to complete. Block2 has indeed been placed on the queue, but it will never be executed. Block1 is "waiting" for block2 to complete, but block2 is sitting on a queue, and the code that pulls it off the queue and executes it will not run until block1 completes.

Deadlock from NOT reentering dispatch_sync

Now, what if we change the code to this...

block1 = {
    dispatch_sync(queue, block2);
}
dispatch_async(queue, block1);

We are not technically reentering dispatch_sync. However, we still have the same scenario, it's just that the thread that kicked off block1 is not waiting for it to finish.

We are still running block1, waiting for block2 to finish, but the thread that will run block2 must finish with block1 first. This will never happen because the code to process block1 is waiting for block2 to be taken off the queue and executed.

Thus reentrancy for dispatch queues is not technically reentering the same function, but reentering the same queue processing.

Deadlocks from NOT reentering the queue at all

In it's most simple case (and most common), let's assume [self foo] gets called on the main thread, as is common for UI callbacks.

-(void) foo {
    dispatch_sync(dispatch_get_main_queue(), ^{
        // Never gets here
    });
}

This doesn't "reenter" the dispatch queue API, but it has the same effect. We are running on the main thread. The main thread is where the blocks are taken off the main queue and processed. The main thread is currently executing foo and a block is placed on the main-queue, and foo then waits for that block to be executed. However, it can only be taken off the queue and executed after the main thread gets done with its current work.

This will never happen because the main thread will not progress until `foo completes, but it will never complete until that block it is waiting for runs... which will not happen.

In my understanding, you can have a deadlock using dispatch_sync only if the thread you are running on is the same thread where the block is dispatch into.

As the aforementioned example illustrates, that's not the case.

Furthermore, there are other scenarios that are similar, but not so obvious, especially when the sync access is hidden in layers of method calls.

Avoiding deadlocks

The only sure way to avoid deadlocks is to never call dispatch_sync (that's not exactly true, but it's close enough). This is especially true if you expose your queue to users.

If you use a self-contained queue, and control its use and target queues, you can maintain some control when using dispatch_sync.

There are, indeed, some valid uses of dispatch_sync on a serial queue, but most are probably unwise, and should only be done when you know for certain that you will not be 'sync' accessing the same or another resource (the latter is known as deadly embrace).

EDIT

Jody, Thanks a lot for your answer. I really understood all of your stuff. I would like to put more points...but right now I cannot.