Windows System Programming Third Edition [Electronic resources] نسخه متنی

Mutexes

A mutex ("mutual exclusion") object provides functionality beyond that of CRITICAL_SECTIONs. Because mutexes can be named and have handles, they can also be used for interprocess synchronization between threads in separate processes. For example, two processes that share memory by means of memory-mapped files can use mutexes to synchronize access to the shared memory.

Mutex objects are similar to CSs, but, in addition to being process-sharable, mutexes allow time-out values and become signaled when abandoned by a terminating process.^{Chapter 9}.

As always, threads should be careful to release resources they own as soon as possible. A thread can acquire a specific mutex several times; the thread will not block if it already has ownership. Ultimately, it must release the mutex the same number of times. This recursive ownership feature, also available with CSs, can be useful for restricting access to a recursive function or in an application that implements nested transactions.

Windows functions are CreateMutex, ReleaseMutex, and OpenMutex.

HANDLE CreateMutex (
LPSECURITY_ATTRIBUTES lpsa,
BOOL bInitialOwner,
LPCTSTR lpMutexName)

The bInitialOwner flag, if trUE, gives the calling thread immediate ownership of the new mutex. This atomic operation prevents a different thread from gaining mutex ownership before the creating thread does. This flag is overridden if the mutex already exists, as determined by the name.Chapter 5). The assumption always is that one process, such as a server, first performs the Create call to create the named object, and other processes perform the Open call, failing if the named object has not already been created. Alternatively, all processes can use the Create call with the same name if the order is not important.

ReleaseMutex frees a mutex that the calling thread owns. It fails if the thread does not own the mutex.

BOOL ReleaseMutex (HANDLE hMutex)

Abandoned Mutexes

If a thread terminates without releasing a mutex that it owns, the mutex becomes abandoned and the handle is in the signaled state. WaitForSingleObject will return WAIT_ABANDONED_0, and WaitForMultipleObjects will use WAIT_ABANDONED_0 as the base value to indicate that the signaled handle(s) represents abandoned mutex(es).

The fact that abandoned mutex handles are signaled is a useful feature not available with CSs. If an abandoned mutex is detected, there is a possibility of a defect in the thread code because threads should be programmed to release their resources before terminating. It is also possible that the thread was terminated by some other thread.

Mutexes, CRITICAL_SECTIONs, and Deadlocks

Although CSs and mutexes can solve problems such as the one in Figure 8-1, you must use them carefully to avoid deadlocks, in which two threads become blocked waiting for a resource owned by the other thread.

Deadlocks are one of the most common and insidious defects in synchronization, and they frequently occur when two or more mutexes must be locked at the same time. Consider the following problem.

• There are two linked lists, List A and List B, each containing identical structures and maintained by worker threads.

• For one class of list element, correct operation depends on the fact that a given element, X, is either in both lists or in neither. The invariant, stated informally, is: "X is either in both lists or in neither."

• In other situations, an element is allowed to be in one list but not in the other. Motivation: The lists might be employees in Departments A and B, where some employees are allowed to be in both departments.

• Therefore, distinct mutexes (or CRITICAL_SECTIONs) are required for both lists, but both mutexes must be locked when adding or deleting a shared element. Using a single mutex would degrade performance, prohibiting concurrent independent updates to the two lists, because the mutex would be "too large."

Here is a possible implementation of the worker thread functions for adding and deleting shared list elements.

static struct {
/* Invariant: List is a valid list. */
HANDLE guard; /* Mutex handle. */
struct ListStuff;
}  ListA, ListB;
...
DWORD WINAPI AddSharedElement (void *arg)
/* Add a shared element to lists A and B. */
{ /* Invariant: New element is in both or neither list. */
WaitForSingleObject (ListA.guard, INFINITE);
WaitForSingleObject (ListB.guard, INFINITE);
/* Add the element to both lists ... */
ReleaseMutex (ListB.guard);
ReleaseMutex (ListA.guard);
return 0;
}
DWORD WINAPI DeleteSharedElement (void *arg)
/* Delete a shared element to lists A and B. */
{
WaitForSingleObject (ListB.guard, INFINITE);
WaitForSingleObject (ListA.guard, INFINITE);
/* Delete the element from both lists ... */
ReleaseMutex (ListB.guard);
ReleaseMutex (ListA.guard);
return 0;
}

The code looks correct by all the previous guidelines. However, a preemption of the AddSharedElement thread immediately after it locks List A and immediately before it tries to lock List B will deadlock if the DeleteSharedElement thread starts before the add thread resumes. Each thread owns a mutex the other requires, and neither thread can proceed to the ReleaseMutex call that would unblock the other thread.

Notice that deadlocks are really another form of race condition, as one thread races to acquire all its mutexes before the other thread starts to do so.

One way to avoid deadlock is the "try and back off" strategy, whereby a thread calls WaitForSingleObject with a finite time-out value and, when detecting an owned mutex, "backs off" by yielding the processor or sleeping for a brief time before trying again. Designing for deadlock-free systems is even better and more efficient, as described next.

A far simpler method, covered in nearly all OS texts, is to specify a "mutex hierarchy" such that all threads are programmed to assure that they acquire the mutexes in exactly the same order and release them in the opposite order. This hierarchical sequence might be arbitrary or could be natural from the structure of the problem, but, whatever the hierarchy, it must be observed by all threads. In this example, all that is needed is for the delete function to wait for List A and List B in order, and the threads will never deadlock as long as this hierarchical sequence is observed everywhere by all threads.

Another good way to reduce deadlock potential is to put the two mutex handles in an array and use WaitForMultipleObjects with the fWaitAll flag set to trUE so that a thread acquires either both or neither of the mutexes in an atomic operation. This technique is not possible with CRITICAL_SECTIONs.

Review: Mutexes vs. CRITICAL_SECTIONs

As stated several times, mutexes and CRITICAL_SECTIONs are very similar and solve the same set of problems. In particular, both objects can be owned by a single thread, and other threads attempting to gain ownership will block until the object is released. Mutexes do provide greater flexibility, but with a performance penalty. In summary, the differences are as follows.

• Mutexes, when abandoned by a terminated thread, are signaled so that other threads are not blocked forever.

• Mutex waits can time out, whereas you can only poll a CS.

• Mutexes can be named and are sharable by threads in different processes.

• You can use WaitForMultipleObjects with mutexes, which is both a programming convenience and a way to avoid deadlocks if used properly.

• The thread that creates a mutex can specify immediate ownership. With a CS, several threads could race to acquire the CS.

• CSs are usually, but not always, considerably faster than mutexes. There will be more on this in Chapter 9.

Heap Synchronization

A pair of functions for NTHeapLock and HeapUnlockis used to synchronize heap access (Chapter 5). The heap handle is the only argument. These functions are helpful when the HEAP_NO_SERIALIZE flag is used or when it is necessary for a thread to have exclusive access to a heap.