Why no mention of GCD here? GCD is very, very good at synchronizing access to shared resources.

The most Cocoa-compatible way of handling background execution of expensive procedures is always going to be best executed, quickest, using Grand Central Dispatch.

For example:

    @interface Foo ()
    @property (nonatomic) dispatch_queue_t backgroundQueue;
    @end
    
    @implementation Foo

    - (BOOL) veryExpensiveMethod:(id)arg completion:(void (^)())completion {
        dispatch_async(self.backgroundQueue, ^{
            if (_counter++ > N) {
                _counter--;
                return NO;
            }
            // Critical section
            _counter--;
            return YES;
            dispatch_async(dispatch_get_main_queue(), completion);
        };

That will ensure every call to -veryExpensiveMethod is run in sequence, and won't require waiting on your end.

These problems have been solved, better.