Anyone designing multithreaded applications will agree: the problem of efficient synchronization is among the most difficult tasks of parallel programming. Modern operating systems provide a multitude of synchronization objects, which determine a variety of synchronization methods and schemes.

This article addresses some of the issues of parallel program synchronization and tries to clarify at least a few of them.

Below, several synchronization schemes are discussed; synchronization object behavior is described; internal system implementation of user-visible synchronization objects or functions is also explained where applicable. Hidden timings and latencies are provided; execution thread layout is shown over time, and non-obvious thread time shifts are pointed out.

Readers will also find code examples illustrating important points of the synchronization problem.

All discussions of synchronization objects and algorithms appearing in this article pertain to Microsoft Windows* implementations of such objects and algorithms.

Definitions

Several abbreviations are used throughout the article to denote the following terms:

IPI stands for Inter-Processor Interrupt, an interruption signal sent by one processor to another.

APC, Asynchronous Procedure Call, which is a Microsoft Windows notification scheme enabling the execution of a specified procedure within the context of a specified thread.

Internal Implementation
This article addresses wake-up and signaling schemes which are used to directly control the execution of threads. Schemes of mutual exclusion, which are mostly employed to synchronize resource usage (granting access to a resource to only one thread), are beyond the scope of the article.

Also, in this article we assume that all necessary resources have been already divided between threads; the task is to wake up the thread and load each of them with an appropriate amount of work.

As various mutual exclusion constructions are not within the scope of this article, only two sorts of synchronization objects typically used for signaling are considered: events and semaphores.

From an operating system kernel point of view, all objects involved in synchronization (those whose handles may be specified as arguments of WaitForSingleObject / WaitForMultipleObjects functions) are derived from one basic structure DISPATCHER_HEADER declared in Microsoft Driver Development Kit in the following form:

typedef struct _DISPATCHER_HEADER 
    union 
        struct 
            UCHAR Type;
            UCHAR Absolute;
            UCHAR Size;
            union 
                UCHAR Inserted;
                BOOLEAN DebugActive;
            ;
        ;

        volatile LONG Lock;
    ;
    LONG SignalState;
    LIST_ENTRY WaitListHead;
 DISPATCHER_HEADER;

The most important fields of which are , SignalState, and WaitListHead that let the system differentiate between synchronization objects and organize a list of waiting threads which are to be woken up when the SignalState becomes Signaled.

So event, semaphore, mutex, timer, and thread objects look similar to the kernel.

Read the rest of this tutorial: click download, below.

© 2005 Intel Corp.