Synchronization Objects
There are four synchronization objects used by operating systems,
Out of these four events are objects mainly used by Windows for synchronization.
Critical Section
A piece of code which involves changing shared resources accessible by threads of the same process is called the critical section. A critical section object can be owned by only one thread at a time, which makes it useful for protecting a shared resource from simultaneous access. If any alteration to the shared resource/s is made by any of the threads and another thread accesses that resource; the thread accessing resource last will get inaccurate results. The thread should be allowed to complete all operations it has to on the shared memory before another thread is brought into the same area through context switching. As an example consider a file-mapping which has been created, now if two threads try to alter it at the same time it would start a race condition. A race condition is reached when there are two or more objects trying to perform a similar action to a resource and these actions aren’t independent of each other.
There can be innumerable such circumstances when an area of code should be used by only one thread and the other threads should not be using that resource until the thread which has entered the critical section is over with it. As soon as the first thread is done, another thread is allowed to enter that section and is given the exclusive access to that resource as the previous thread. When a thread owning a critical section is terminated, the state of the critical section is undefined and an application can be deadlocked waiting for that critical section. Other threads don’t know this critical section has been abandoned.
In case of a uni-processor system this exclusive access of the critical section can be achieved by making sure context-switching doesn’t happen once a thread has entered the critical section. The control remains with the thread executing in the critical section until it is out of it. This can be achieved by a simple condition at the beginning of the critical section. A more complex situation occurs in a SMP system (symmetric multiprocessing; more than one processors sharing the same main memory). A critical section is typically used when a multithreaded program must update multiple related variables without a separate thread making conflicting changes to that data. The limit to critical section is that it is only for threads of the same process. Two threads of the same process can run in parallel in a SMP system. So a critical section helps in synchronizing threads of the same process to make the process work with stable/correct results. If there are two threads, A and B; and A is going to do something depending on the result (alteration in memory) of B; suppose A and B are run in parallel, there would be a 50-50 probability on which one runs first. And this will produce undesired results at least half of the time.
Other synchronization objects like semaphores, mutex and events can also be used to serve the same purpose of synchronizing threads of the same process but the critical section object is slightly faster and more efficient than other mutual-exclusion synchronization mechanisms. As discussed earlier, context-switching can be controlled/monitored to ensure only one thread enters the critical section at a point in time. In such cases the kernel has to be told not to preempt other threads until the thread has completed its critical section operations.
The Windows implementation of critical section works on a CRITICAL_SECTION object. It is very simple to use and there are only a handful of functions used to work with it. These are:
void InitializeCriticalSection (LPCRITICAL_SECTION lpCriticalSection);
void EnterCriticalSection (LPCRITICAL_SECTION lpCriticalSection);
void LeaveCriticalSection (LPCRITICAL_SECTION lpCriticalSection);
void DeleteCriticalSection (LPCRITICAL_SECTION lpCriticalSection);
Their functionality as well is quite obvious from the function names. A CRITICAL_SECITON object is first created; InitializeCriticalSection creates the critical section space in the process’s memory. That’s a reason critical section can only be used by threads of the same process. By EnterCriticalSection a thread gains ownership of this critical section and is released when the function LeaveCriticalSection is executed which introduces another thread into the critical section area which gains ownership in return. A critical section has no handle to use across processes.
Mutex
Mutex stands for mutual exclusion and serves the purpose of thread synchronization. Mutex is the thread synchronization object which allows accessing the resource only one thread at a time. Only when a process goes to the signaled state are the other resources allowed to access. As opposed to critical section, this synchronization tool works across threads of different processes. Mutex objects work on the concept of being owned by a thread working in the critical region of a program. While one thread/process owns a mutex referring to a particular section of code; no other thread can obtain its control until the first thread frees the mutex which can now be owned by any of the threads. While a thread is waiting for ownership of the mutex, it is put to sleep. The order of threads getting the mutex once it’s free depends on the order in which every one of them is awoken.
When a program is started, it creates a mutex for a given resource at the beginning by requesting it from the system and the system returns a unique name or ID for it. After that, any thread needing the resource must use the mutex to lock the resource from other threads while it is using the resource. A mutex signals that it’s ready for some other thread when it has been abandoned. Usually the threads waiting are put into a queue which determines the order threads are awoken. Mutex is allocated in the programs' address spaces. No microkernel data structure is allocated for these objects; they are simply designated by the addresses of the structures. The number of these types of objects that threads can use is thus unlimited. If multiple mutexes are not made on the same section of code, mutual exclusion is successfully achieved. If mutexes are made on the same code, many threads can change the shared memory making mutexes nothing but a waste of time and resources.
One big advantage that mutex has over critical section is that if a thread is terminated while having the ownership of the mutex, the mutex is left in an abandoned state. If any thread seeks ownership of the mutex, an error is returned signaling the mutex is in abandoned state and the memory it was protecting is undefined. If the thread persists and does gain ownership of the mutex, the mutex is treated like a normal mutex removing the abandoned signal. This also helps in SMP systems where there may be a situation where two processors target the same kernel region to use; both want to run an operating system process. Obviously if both are given access to the kernel and run in parallel, the system would crash. For this the whole operating system is put into a big critical region. When a processor wants to run a kernel process, it has to gain control to the mutex or wait for the other processor to free the mutex. But there may be areas which are not so critical in the operating system code too, so the operating system code is divided into small critical regions just like any shared memory regions; which don’t interact with each other and each has its own mutex.
Implementation in Windows is done by creating mutex objects, which are accessible across processes. CreateMutex creates the object and returns a handle. If this handle is NULL, the mutex creation failed. Once the mutex has been created, OpenMutex can be used in any process to make it as if the mutex was local to the process and not in another process. When the thread is over with using the mutex, it uses the function ReleaseMutex to signal to other threads in wait status that it’s free to be accessed.
LPSECURITY_ATTRIBUTES lpsa,
BOOL bInitialOwner,
LPCTSTR lpMutexName)
lpMutexName is the name of the mutex as obvious; bInitialOwner if true, indicates that the thread creating the mutex has the ownership of the mutex as soon as its created.
BOOL ReleaseMutex (HANDLE hMutex)
This function releases the ownership of the mutex.
HANDLE WINAPI OpenMutex( DWORD dwDesiredAccess, BOOL bInheritHandle, LPCTSTR lpName );
As discussed earlier, OpenMutex makes the ‘lpName’ mutex available to the process as if it were defined in its own code area. The dwDesiredAccess hs values that define the way the mutex is needed for access. These are known as access rights, which are a topic in themselves.
Semaphores
Semaphores are synchronization objects which allow a limited number of threads/processes to access the region which is enclosed by semaphore. Since semaphores can have a count associated with them, they are usually made use of when multiple threads cooperatively need to achieve an objective. The simplest kind of semaphore is the "binary semaphore", used to control access to a single resource, which is essentially the same as a mutex. Binary semaphores do not count signaled events, their count will never exceed 1 whatever number of events is signaled to them. Resource semaphores are special binary semaphores suitable for managing resources. The task that acquires a resource semaphore becomes its owner, also called resource owner, since it is the only one capable of manipulating the resource the semaphore is protecting. The owner has its priority increased to that of any task blocking on a wait to the semaphore. Resource semaphores can be recursed, i.e. their task owner is not blocked by nested waits placed on an owned resource. The owner must ensure that it will signal the semaphore, in reversed order, as many times as it waited on it.
The other types of semaphores are the counting semaphores. The value of this semaphore is usually initialized to 1. It is incremented when a thread/process enters the region or uses the resource and is decremented when its’ over with the resource. If the value of the semaphore is 0, it means there are no threads waiting. If a thread tries to decrement it further; it will block itself until another thread comes and increments the semaphore. Here we pay further emphasis to what the value of the semaphore means. As discussed earlier a value of 0 means that there are no threads waiting for access to the region being protected by the semaphore. Positive value of the semaphore variable shows how many thread can enter the critical region. Negative value of a semaphore shows that how many threads are blocked on it. These threads use the WaitForSingleObject function to determine whether the semaphore's current count permits the creation of additional threads in that region or else they’re blocked. Counting semaphores can register up to 0xFFFE threads.
A semaphore is released the operating system tries to satisfy as many waits (i.e., to mark as many threads ready for execution) as possible, though staying within the limit specified upon creation of the semaphore object. This limit helps in keeping count of the maximum number of threads which can be satisfied by this area of code at the same time.
LPSECURITY_ATTRIBUTES lpsa,
LONG lSemInitial,
LONG lSemMax,
LPCTSTR lpSemName)
HANDLE hSemaphore,
LONG cReleaseCount,
LPLONG lpPreviousCount)
lSemMax, which must be 1 or greater, is the maximum value for the semaphore. lSemInitial is the initial value, and the semaphore value is never allowed to go outside this range. A NULL return value in the HANDLE indicates failure.
A semaphore can enter the critical section, and gain ownership of it as well as leave it with all the treatments a thread would have if it wanted to enter the critical section using ReleaseSemaphore.
Events
Events are also synchronization objects which are used to signal to the system that a specific action/result has occurred or become available. When threads want to run critical region code, they are either put into a wait or sent back to be called again asynchronously. In any case the thread would need to know when the resource it wants to access is free for access. This is done by signaling to waiting threads as well as threads running some other code while waiting for this resource that it’s free and can be used by another thread now. As an example consider there is a piece of code which takes control of the COM port and reads data from it. In a SMP system, two threads or even processes may want to gain its access to continue with whatever operation they were intending to perform. If both are given access to the resource, obviously the result would be erroneous and undesired. Each thread would be given independent access one-at-a-time which is done by synchronization objects discussed earlier. Multiple threads are waiting on the resource and are signaled that the COM port is now free and threads wanting to access it now access it and complete their job without unpredictable results.
The operating system kernel supports two types of events corresponding to the user-level auto-reset and manual reset events; namely, synchronization events and notification events. The difference between the two types is similar to the user-level events: signaling a synchronization event would cause only one waiting thread to wake up, while setting a notification event to a signaled state would wake as many threads as there might be waiting. At this stage it may seem that events and semaphores are one and the same thing; but there is a marked difference because of which events are used extensively as compared to semaphores. Semaphores also try to signal to related events it’s now available to more thread/s. As discussed earlier there is a limit to the number of events it can signal, in the case of events there is no limit to the number of threads or any other objects which are signaled when the required resource is free.
In Windows, event is an object with a handle which is created by a function by the name of CreateEvent(…).
HANDLE CreateEvent (NULL, BOOL bManualReset, BOOL bInitialState, LPTSTR lpName);
Signals from the event can be sent using two functions; SetEvent and PulseEvent. The only difference is that SetEvent doesn’t reset the event to a non-signaled state itself and has to be done explicitly whereas the PulseEvent function does. PulseEvent also unblocks all threads waiting on the event. To manually reset the event ResetEvent is used and the event is closed using CloseEvent. Threads can wait on the event using the WaitForSingleObject function as discussed earlier.
Conclusion
A variety of synchronization objects exist, which are distinguished basically for support of the operating system kernel. The actual efficiency of different user-level synchronization objects may appear to be the same; as such schemes may serve as mere synonyms of one general kernel mode construction. On the contrary, some synchronization schemes may support a very specific case, and their performance in other cases of synchronization may degrade. All of these synchronization objects can be used inter-changeably in almost every case. Decision taken on which of these synchronization objects is used should be based on which may be more useful, while writing a well-balanced multithreaded application, and keep in mind the relationships between user- and kernel-based objects, and only apply synchronization objects that have been specifically designed for a particular purpose for the user and get the most out of it in terms of efficiency as well as proper utilization of resources.
