Sofa's blog about design, code everything else.

With the release of Snow Leopard Apple introduced Grand Central Dispatch, a library designed to ease the inherent difficulties in writing concurrent applications. For the non-developers reading this, you may be surprised to know that making an application do more than one thing at a time (reliably) is a difficult problem to solve as the complexity of the application increases. Computer science students are gradually introduced to the concepts of multitasking, and one of the engineering problems often used in teaching is the ‘sleeping barber problem’.

The sleeping barber problem is described well on Wikipedia. It can be summarized with a few statements:

The Waiting Room

We can think of the waiting chairs as a queue of customers, but we need to limit the number of items in the queue to a maximum number.

GCD allows us to use one of the three global concurrent queues which execute tasks concurrently, whereas any queues that we create ourselves are serial queues. We can create a serial queue to represent our chairs, but we need to limit the number of items in the queue to a maximum number, for our purposes we'll have 3 waiting chairs in the shop. To do this we'll use a dispatch semaphore.

Dispatch Semaphores

Semaphores in GCD allow you to manage access of threads to finite resources. They have a key performance advantage over posix semaphores in that they don't call into the kernel if the resource is available, so they're fast. Semaphores allow you to initialize them with a value, which we use to represent the number of chairs in the waiting room. When a customer walks into the shop we call dispatch_semaphore_wait(), which attempts to decrement the semaphore. If the value of the semaphore is greater than zero, then a chair is free and the customer takes a seat. If the semaphore is already at zero then all the chairs are taken, in which case dispatch_semaphore_wait() return value is non-zero and we can turn away the customer.

The key to dispatch semaphores is the timeout value. Passing DISPATCH_TIME_FOREVER will cause any thread to wait until the value of the semaphore moves above zero and and a seat is available. If we did this our customers would be queueing up outside our shop prior to taking a seat in the waiting room. Instead we pass DISPATCH_TIME_NOW so we can see if a chair is immediately available by testing the return value of dispatch_semaphore_wait(). The customer sees that no space is available and walks away.

The Barber

Consider now that we have any number of seats taken by waiting customers. How do we get the barber to do some work? The first thought may be to use another semaphore, a binary one this time, and signal the barber that he has work to do. That's too much work. Instead we create another serial queue, and call this queue the barber. When a customer takes a seat all we have to do is add a new task (shave and a haircut) onto the barber's list of jobs. When a barber begins his next task, we signal the semaphore that a waiting chair has become available.

As the barber is a GCD queue, when there's no work available, libdispatch takes care of managing resources and putting the queue to sleep if necessary.

All in all we've implemented a complete solution to the barbershop problem, without logging what's going on (and depending on your formatting) the bulk is about 18 lines of code (whooping Scala and beating even Clojure):

int main (int argc, const char * argv[]) {
    dispatch_queue_t waitingChairs = dispatch_queue_create("com.madebysofa.waitingChairs", 0);
    dispatch_queue_t barber = dispatch_queue_create("com.madebysofa.barber", 0);    
    dispatch_semaphore_t semaphore = dispatch_semaphore_create((long)3);
    NSInteger index = -1;

    while (YES) {
        index++;
        long success = dispatch_semaphore_wait(semaphore, DISPATCH_TIME_NOW);
        if (success != 0) {
            NSLog(@"Customer turned away %i", index);
            continue;
        }
        dispatch_async(waitingChairs, ^{
            NSLog(@"Customer taking a seat %i", index);
            dispatch_async(barber, ^{
                dispatch_semaphore_signal(semaphore);
                NSLog(@"Shave and a haircut %i", index);
            });
        });        
    }
    dispatch_release(waitingChairs);
    dispatch_release(barber);
    dispatch_release(semaphore);
    return 0;
}

Creative Interpretation

That's all well and good, but we can go a step further. If the customers don't do anything while they're seated, we can again take advantage of the FIFO nature of GCD queues and lose the barber queue altogether. In this case we can simply enqueue a maximum of 3 work units onto our "waiting" queue, and they'll be executed serially anyway. The code then becomes:

int main (int argc, const char * argv[]) {
    dispatch_queue_t waitingChairs = dispatch_queue_create("com.madebysofa.waitingChairs", 0);
    dispatch_semaphore_t semaphore = dispatch_semaphore_create((long)3);
    NSInteger index = -1;
    
    while (YES) {
        index++;
        long success = dispatch_semaphore_wait(semaphore, DISPATCH_TIME_NOW);
        if (success != 0) {
            NSLog(@"Customer turned away %i", index);
            continue;
        }
        dispatch_async(waitingChairs, ^{
            dispatch_semaphore_signal(semaphore);
            NSLog(@"Shave and a haircut %i", index);
        });        
    }

    dispatch_release(waitingChairs);
    dispatch_release(semaphore);
    return 0;
}

You could still create the barber queue and call dispatch_set_target_queue(waitingQueue, barberQueue) which will mean that as an item is dequeued from the waiting queue it gets executed on the barber queue, but there's little point, until we create more waiting rooms that is. By creating more waiting rooms, we can set all their target queues to the barber and we can "funnel" work through the barber queue.

Our original implementation has a key advantage though: while seated the customer can do some work which is guaranteed to complete before the "shave and a haircut" is dispatched to the barber. In our sample code, this "work" is the NSLog(@"Customer taking a seat"), but you can imagine a long calculation taking place in preparation for the haircut.

Final Thoughts

Developers often say, "threading is hard". I disagree. Threading isn't hard, concurrency is hard. Threading is just learning a new set of functions. What Apple have done with GCD is to give us an abstraction for threads, which also makes managing concurrency far easier. Moreso, where people have created functional programming languages like Scala and Clojure to address the concurrency problem, GCD (and blocks) is all just C. There is real power in that simplicity. We can approach problems from a functional standpoint using a procedural language, and more concisely even than I can describe it.