Jump to content

Grand Central Dispatch

From Wikipedia, the free encyclopedia

Original author(s)Dave Zarzycki
Developer(s)Apple Inc.
Written inC
Operating systemMac OS X 10.6 (2009) and later, iOS 4.0 and later,[1] watchOS, tvOS, FreeBSD
TypeSystem Utility
LicenseApache 2.0
Websitehttps://apple.github.io/swift-corelibs-libdispatch/

Grand Central Dispatch (GCD or libdispatch) is a technology developed by Apple Inc. to optimize application support for systems with multi-core processors and other symmetric multiprocessing systems.[2] It is an implementation of task parallelism based on the thread pool pattern. The fundamental idea is to move the management of the thread pool out of the hands of the developer, and closer to the operating system. The developer injects "work packages" into the pool oblivious of the pool's architecture. This model improves simplicity, portability and performance.

GCD was first released with Mac OS X 10.6, and is also available with iOS 4 and above. The name "Grand Central Dispatch" is a reference to Grand Central Terminal.[citation needed]

The source code for the library that provides the implementation of GCD's services, libdispatch, was released by Apple under the Apache License on September 10, 2009.[3] It has been ported[4] to FreeBSD 8.1+,[5] MidnightBSD 0.3+,[6] Linux, and Solaris.[7][8] Attempts in 2011 to make libdispatch work on Windows were not merged into upstream.[9][10] Apple has its own port of libdispatch.dll for Windows shipped with Safari and iTunes, but no SDK is provided.

Since around 2017, the original libdispatch repository hosted by Nick Hutchinson[11] was deprecated in favor of a version that is part of the Swift core library created in June 2016. The new version supports more platforms, notably including Windows.

Design

[edit]

GCD works by allowing specific tasks in a program that can be run in parallel to be queued up for execution and, depending on availability of processing resources, scheduling them to execute on any of the available processor cores[12][13] (referred to as "routing" by Apple).[14]

A task can be expressed either as a function or as a "block."[15] Blocks are an extension to the syntax of C, C++, and Objective-C programming languages that encapsulate code and data into a single object in a way similar to a closure.[12] GCD can still be used in environments where blocks are not available.[16]

Grand Central Dispatch still uses threads at the low level but abstracts them away from the programmer, who will not need to be concerned with as many details. Tasks in GCD are lightweight to create and queue; Apple states that 15 instructions are required to queue up a work unit in GCD, while creating a traditional thread could easily require several hundred instructions.[12]

A task in Grand Central Dispatch can be used either to create a work item that is placed in a queue or assign it to an event source. If a task is assigned to an event source, then a work unit is made from the block or function when the event triggers, and the work unit is placed in an appropriate queue. This is described by Apple as more efficient than creating a thread whose sole purpose is to wait on a single event triggering.

Features

[edit]

The dispatch framework declares several data types and functions to create and manipulate them:

  • Dispatch Queues are objects that maintain a queue of tasks, either anonymous code blocks or functions, and execute these tasks in their turn. The library automatically creates several queues with different priority levels that execute several tasks concurrently, selecting the optimal number of tasks to run based on the operating environment. A client to the library may also create any number of serial queues, which execute tasks in the order they are submitted, one at a time.[13] Because a serial queue can only run one task at a time, each task submitted to the queue is critical with regard to the other tasks on the queue, and thus a serial queue can be used instead of a lock on a contended resource.
  • Dispatch Sources are objects that allow the client to register blocks or functions to execute asynchronously upon system events, such as a socket or file descriptor being ready for reading or writing, or a POSIX signal.
  • Dispatch Groups are objects that allow several tasks to be grouped for later joining. Tasks can be added to a queue as a member of a group, and then the client can use the group object to wait until all of the tasks in that group have completed.
  • Dispatch Semaphores are objects that allow a client to permit only a certain number of tasks to execute concurrently.

Libdispatch comes with its own object model, OS Object, that is partially compatible with the Objective-C model. As a result, its objects can be bridged toll-free to ObjC objects.[17]

Examples

[edit]

Two examples that demonstrate the use of Grand Central Dispatch can be found in John Siracusa's Ars Technica Snow Leopard review.[18] Initially, a document-based application has a method called analyzeDocument which may do something like count the number of words and paragraphs in the document. Normally, this would be a quick process, and may be executed in the main thread without the user noticing a delay between pressing a button and the results showing.

- (IBAction)analyzeDocument:(NSButton *)sender {
    NSDictionary *stats = [myDoc analyze];
    [myModel setDict:stats];
    [myStatsView setNeedsDisplay:YES];
}

If the document is large and analysis takes a long time to execute then the main thread will wait for the function to finish. If it takes long enough, the user will notice, and the application may even "beachball". The solution can be seen here:

- (IBAction)analyzeDocument:(NSButton *)sender {
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        NSDictionary *stats = [myDoc analyze];
        dispatch_async(dispatch_get_main_queue(), ^{
            [myModel setDict:stats];
            [myStatsView setNeedsDisplay:YES];
        });
    });
}

Here, the call to [myDoc analyze] is placed inside a Block, which is then placed on one of the global concurrent queues. After it has finished running [myDoc analyze], a new block is placed on the main queue (on which the main thread of the application runs), which updates the GUI (This is necessary because the GUI can only be updated by the main thread). By making these two small changes, the developer has avoided a potential stall of the application as seen by the user, and allowed their application to make better use of hardware resources.

The second example is that of parallelising a for loop:

for (i = 0; i < count; i++) {
      results[i] = do_work(data, i);
}
total = summarize(results, count);

This code runs the do_work function count times, assigning the ith result to the ith element in the array results, and then calls summarize on array once the loop has ended. Unfortunately the work is computed sequentially, where it may not need to be. Assuming that do_work doesn't rely on the results of any of the other calls made to it, there is no reason why these calls cannot be made concurrently. This is how this would be done in GCD:

dispatch_apply(count, dispatch_get_global_queue(0, 0), ^(size_t i){
     results[i] = do_work(data, i);
    });
total = summarize(results, count);

Here, dispatch_apply runs the block passed to it, count times, placing each invocation on a global queue, and passing each block invocation a different number from 0 to count-1. This will allow the OS to spread out the work as it sees fit, choosing the optimal number of threads to run on for the current hardware and system load. dispatch_apply does not return until all the blocks it places on the given queue have completed execution, so that it can be guaranteed that all the work inside the original loop has completed before calling summarize.

Programmers can create their own serial queues for tasks which they know must run serially but which may be executed on a separate thread. A new queue would be created like so:

dispatch_queue_t exampleQueue;
exampleQueue = dispatch_queue_create( "com.example.unique.identifier", NULL );

// exampleQueue may be used here.

dispatch_release( exampleQueue );

Care must be taken to avoid a dispatched block on a queue synchronously placing another block on the same queue as this is guaranteed to deadlock. Such code might do the following:

dispatch_queue_t exampleQueue = dispatch_queue_create( "com.example.unique.identifier", NULL );

dispatch_sync( exampleQueue, ^{
  dispatch_sync( exampleQueue, ^{
    printf( "I am now deadlocked...\n" );
  });
});

dispatch_release( exampleQueue );

Applications

[edit]

GCD is used throughout macOS (beginning with 10.6 Snow Leopard), and Apple has encouraged its adoption by macOS application developers. FreeBSD developer Robert Watson announced the first adaptation of a major open source application, the Apache HTTP Server, to use GCD via the Apache GCD MPM (Multi-Processing Module) on May 11, 2010, in order to illustrate the programming model and how to integrate GCD into existing, large-scale multi-threaded, applications. His announcement observed that the GCD MPM had one third to half the number of lines as other threaded MPMs.[19][20]

Internals

[edit]

GCD is implemented by libdispatch, with support from pthreads non-POSIX extensions developed by Apple. Apple has changed the interface since its inception (in OS X 10.5) through the official launch of GCD (10.6), Mountain Lion (10.8) and Mavericks (10.9). The latest changes involve making the code supporting pthreads, both in user mode and kernel, private (with kernel pthread support reduced to shims only, and the actual workqueue implementation moved to a separate kernel extension).[21]

On other systems, libdispatch implements its own workqueue using the system's own event facilities (epoll, kevent, or Windows NT). On macOS, kevent is used with the kernel workqueue.

See also

[edit]

References

[edit]
  1. ^ "Grand Central Dispatch (GCD) Reference". Apple Inc.
  2. ^ Apple Previews Mac OS X Snow Leopard to Developers Archived March 18, 2012, at the Wayback Machine, June 9, 2008.
  3. ^ "Grand Central Dispatch". apple.github.io.
  4. ^ "GCD libdispatch w/Blocks support working on FreeBSD". Archived from the original on July 27, 2011. Retrieved September 28, 2009.
  5. ^ "FreeBSD Quarterly Status Report". www.freebsd.org.
  6. ^ "libdispatch". Just Journal.
  7. ^ libdispatch mailing list: "Porting status Linux" Archived July 11, 2011, at the Wayback Machine April 10, 2011
  8. ^ libdispatch mailing list: "Porting status Solaris x86/64" Archived October 4, 2011, at the Wayback Machine April 10, 2011
  9. ^ libdispatch mailing list: "libdispatch for Win32" Archived August 20, 2011, at the Wayback Machine April 22, 2011
  10. ^ libdispatch mailing list: "Updates regarding the status of libdispatch on Windows" Archived August 20, 2011, at the Wayback Machine May 5, 2011
  11. ^ Hutchinson, Nicholas (January 10, 2020). "libdispatch". GitHub. Retrieved January 15, 2020.
  12. ^ a b c "Apple Technical Brief on Grand Central Dispatch" (PDF). Archived from the original on September 20, 2009. Retrieved September 12, 2009.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  13. ^ a b Gagne, Abraham Silberschatz, Peter Baer Galvin, Greg (2013). Operating system concepts (9th ed.). Hoboken, N.J.: Wiley. pp. 182–183. ISBN 9781118063330.{{cite book}}: CS1 maint: multiple names: authors list (link)
  14. ^ "WWDC 2008: New in Mac OS X Snow Leopard". Archived from the original on October 17, 2008. Retrieved June 18, 2008.
  15. ^ "Grand Central Dispatch (GCD) Reference". Retrieved September 13, 2009.
  16. ^ "GrandCentralDispatch - FreeBSD Wiki".
  17. ^ Bugaev, Sergey (July 24, 2018). "Mach-O linking and loading tricks". Darling development blog. Retrieved January 15, 2020.
  18. ^ Mac OS X 10.6 Snow Leopard: the Ars Technica review (accessed September 2, 2009)
  19. ^ libdispatch-dev GCD MPM for Apache Archived August 7, 2020, at the Wayback Machine (accessed May 14, 2010)
  20. ^ apache-libdispatch (accessed May 14, 2010)
  21. ^ Levin, Jonathan (February 15, 2014). "GCD Internals: The undocumented side of the Grand Central Dispatcher". Retrieved March 17, 2014.
[edit]