Synchronization

Threads within a single process share all resources owned by the process. This implies that threads must coordinate access to these resources by implementing serialization and mutual exclusion policies.

The synchronization functions provided by CMS allow sets of threads to implement coordination and mutual exclusion policies. They are primitives upon which more elaborate and special purpose synchronization mechanisms can be built by programming languages and applications. These primitives are designed to be highly efficient in a parallel execution environment.

The synchronization primitives are based on the following definitions:

Critical Section

A block of code that manipulates a shared resource, such as a data structure or device.

Mutex

A variable with an associated wait queue used to protect a critical section. The typical use of a mutex is as follows:

   MutexAcquire(mutex_handle)

      /* access the critical section */

   MutexRelease(mutex_handle)

If more than one thread simultaneously tries to acquire the mutex, only one such thread acquires the mutex. The other threads are queued, waiting to acquire the mutex, and are given the mutex one at a time as the previous holder of the mutex releases it. The order in which these threads acquire the mutex is defined by the order in which they execute the MutexAcquire function.

Condition Variable

A variable representing a state for a mutex-protected shared resource. This state, or condition, can be waited on and signaled as being true.

CMS maintains the condition variable and its associated wait queue. However, it does not determine if the condition is true or false. It is the responsibility of the application to wait on the condition variable when necessary and signal it when the condition is true.

For example, if a stack of length 10 is a shared resource, a condition variable might represent whether there are less than 10 elements in the stack. An element can be pushed onto the stack if it currently contains less than 10 elements.

To use a condition variable, a thread evaluates the condition represented by the condition variable while holding its associated mutex. If the condition is false, the CondVarWait function is issued. When the thread returns from this function, it once again holds the mutex and the condition is true. The other side of the condition variable interface is the CondVarSignal function. It is used by a thread that has changed the state of the shared resource to make the condition true for one thread that may be waiting.

Semaphore

A variable used to perform wait and post operations between threads. It is an integer variable S with an associated wait queue upon which only the following two primary atomic (that is, noninterruptable) operations may be performed:

   P(S): S := S - 1;
         If (S < 0) then
            Add the thread to the wait queue for S;
         Endif

   V(S): S := S + 1;
         If (S ≤ 0) then
            Unblock a thread on wait queue for S;
         Endif

Note here that S may be interpreted as follows: if S ≥ 0, the number of P(S) operations that are allowed before blocking occurs; if S < 0, the number of blocked threads waiting on S.

The P(S) and V(S) operations are renamed to the more meaningful function names SemWait and SemSignal, respectively. These functions implement general counting semaphores.

Along with the primary semaphore operations defined above, a SemReInit function is included. This function reinitializes the semaphore's value and unblocks all the threads waiting on a semaphore.

There is no notion of establishing ownership of a semaphore as is the case with a mutex. A semaphore should be used to wait for a condition to occur and resume execution when the condition occurs.

The central operational differences between a mutex and a semaphore are the preconditions placed on the operations defined on them. A given thread can signal a semaphore without having previously waited on it, but a given thread cannot release a mutex without having previously acquired it. See CMS Multitasking Function Descriptions for a more formal definition of these functions.

Because mutexes and condition variables provide more discipline, semaphores should be used only when these more structured mechanisms cannot be applied. See Synchronization Examples for examples on the use of mutexes and semaphores.

Event services can alert other threads of important situations, such as the end of a computation phase or an error condition. Signaling, testing, and waiting for events can also be used in place of semaphores; however, semaphore operations are more efficient for such situations.

When a program creates a mutex or semaphore, it assigns it a scope. This scope determines the visibility of the mutex or semaphore relative to other threads in the session. Process-level scope means that the mutex or semaphore is accessible only to the threads in the creating process. Session-level scope means that any thread in any process in the session can access the mutex or semaphore. A condition variable has visibility equal to the visibility of the mutex with which it is associated.

Mutexes, semaphores, and condition variables are assigned handles when they are created. A handle is simply a token used in subsequent function calls to identify the object. The scope of a handle is equal to the scope of the object with which it is associated; in other words, the handle may be used to identify the object wherever the object is known. The scope of the handle is a useful concept. For example, the handle of a mutex can be stored in the data structure it is used to protect and thus be accessible to all threads that use the data structure.

CMS supports up to 32,768 session-scope semaphores, mutexes, and condition variables, altogether. Also, for each process, CMS supports up to 32,768 process-scope semaphores, mutexes, and condition variables, altogether.