The Critical Section Problem
A critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will only have to wait a fixed time to enter it (i.e. bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
By carefully controlling which variables are modified inside and outside the critical section (usually, by accessing important state only from within), concurrent access to that state is prevented. 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. In a related situation, a critical section may be used to ensure a shared resource, for example a printer, can only be accessed by one process at a time.
How critical sections are implemented varies among operating systems.
The simplest method is to prevent any change of processor control inside the critical section. On uni-processor systems, this can be done by disabling interrupts on entry into the critical section, avoiding system calls that can cause a context switch while inside the section and restoring interrupts to their previous state on exit. Any thread of execution entering any critical section anywhere in the system will, with this implementation, prevent any other thread, including an interrupt, from getting the CPU and therefore from entering any other critical section or, indeed, any code whatsoever, until the original thread leaves its critical section.
This brute-force approach can be improved upon by using semaphores. To enter a critical section, a thread must obtain a semaphore, which it releases on leaving the section. Other threads are prevented from entering the critical section at the same time as the original thread, but are free to gain control of the CPU and execute other code, including other critical sections that are protected by different semaphores.
Some confusion exist in the literature about the relationship between different critical sections in the same program. In general, a resource that must be protected from concurrent access may be accessed by several pieces of code. Each piece must be guarded by a common semaphore. Is each piece now a critical section or are all the pieces guarded by the same semaphore in aggregate a single critical section? This confusion is evident in definitions of a critical section such as “… a piece of code that can only be executed by one process or thread at a time”. This only works if all access to a protected resource is contained in one “piece of code”, which requires either the definition of a piece of code or the code itself to be somewhat contrived.
Application Level Critical Sections
Application-level critical sections reside in the memory range of the process and are usually modifiable by the process itself. This is called a user-space object because the program run by the user (as opposed to the kernel) can modify and interact with the object. However the functions called may jump to kernel-space code to register the user-space object with the kernel.
Example Code For Critical Sections with POSIX pthread library
/* Sample C/C++, Unix/Linux */
pthread_mutex_t cs_mutex = PTHREAD_MUTEX_INITIALIZER;
This is the critical section object*/
/* Enter the critical section — other threads are locked out */
pthread_mutex_lock( &cs_mutex );
/* Do some thread-safe processing! */
/*Leave the critical section —
Example Code For Critical Sections with Win32 API
/* Sample C/C++, Win9x/NT/ME/2000/XP, link to kernel32.dll
CRITICAL_SECTION cs; /* This is the critical section object
— once initialized, it cannot be moved in memory */
/* Initialize the critical section — This must be done
before locking */
/* Enter the critical section — other threads are locked
/* Do some thread-safe processing! */
/* Leave the critical section
/* Release system object when all finished — usually at the end of the cleanup code */
Note that on Windows NT (not 9x/ME), the function TryEnterCriticalSection() can be used to attempt to enter the critical section. This function returns immediately so that the thread can do other things if it fails to enter the critical section (usually due to another thread having locked it). Note that the use of a CriticalSection is not the same as a Win32 Mutex, which is an object used for inter-process synchronization. A Win32 CriticalSection is for inter-thread synchronization (and is much faster as far as lock times), however it cannot be shared across processes.
3.1.2 Kernel Level Critical Sections
Typically, critical sections prevent process and thread migration between processors by interrupts. Also, pre-emption of processes and threads is prevent by interrupts.
Critical sections often allow nesting. Nesting allows multiple critical sections to be entered and exited at little cost.
If the scheduler interrupts the current process or thread in a critical section, the scheduler will either allow the process or thread to run to completion of the critical section, or it will schedule the process or thread for another complete quantum. The scheduler will not migrate the process or thread to another processor, and it will not schedule another process or thread to run while the current process or thread is in a critical section.
Similarly, if an interrupt occurs in a critical section, the interrupt’s information is recorded for future processing, and execution is returned to the process or thread in the critical section. Once the critical section is exited, and in some cases the scheduled quantum completes, the pending interrupt will be executed.
Since critical sections may execute only on the processor on which they are entered, synchronization is only required within the executing processor. This allows critical sections to be entered and exited at almost zero cost. No interprocessor synchronization is required, only instruction stream synchronization. Most processors provide the required amount of synchronization by the simple act of interrupting the current execution state.
This allows critical sections in most cases to be nothing more than a per processor count of critical sections entered.
Performance enhancements include executing pending interrupts at the exit of all critical sections and allowing the scheduler to run at the exit of all critical sections. Furthermore, pending interrupts may be transferred to other processors for execution.
Critical sections should not be used as a long-lived locking primitive. They should be short enough that the critical section will be entered, executed, and exited without any interrupts occurring, from neither hardware much less the scheduler.
The first major advance in dealing with the problems of concurrent processes came in
1965 with Dijkstra’s treatise. The fundamental principle is this: two or more processes can cooperate by means of simple signal, such that a process can be forced to stop at a specified place until it has received a specified signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. For signalling, special variables called semaphores are used. To transmit a signal via semaphores, a process executes the primitive signal(s). To receive a signal via semaphore s, a process executes the primitive wait(s); if the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.
To achieve the desired effect, we can view the semaphore as a variable that has an integer value upon which three operations are defined:
- A semaphore may be initialized to a non-negative value
- The wait operation decrements the semaphore value. If the value becomes negative, then the process executing the wait is blocked
- The signal operation increments the semaphore value. If the value is not positive, then a process blocked by wait operation is unblocked.
Other than these three operations, there is no way to inspect or manipulate semaphores.
Semaphores are operated on by a signal operation, which increments the semaphore value and the wait operation, which decreases it. The initial value of semaphore indicates the number of wait operations that can be performed on the semaphore. Thus:
V= I – W + S
where I is the initial value of the semaphore
W is the number of completed wait operations performed on the semaphore
S is the number of signal operations performed on it
V is the current value of the semaphore (which must be greater than or equal to zero).
As V is > 0 then I- W+ S > 0, which gives
Thus, the number of wait operations must be less than or equal to the initial value of the semaphore, plus the number of signal operations. A binary semaphore will have an initial value of 1 (I = 1), thus:
W< S+ 1
In mutual exclusion, waits always occur before signals, as waits happen at the start of a critical piece of code, with a signal at the end of it. The above equation states that no more than one wait may run to completion before a signal has been performed. Thus no more than one process may enter the critical section at a time as required
3.2.1 The Problem with Semaphores
Semaphores work but programmers still need to code carefully to ensure mutual exclusion and that synchronisation operate correctly.
3.2.2 Language Constructs
The problem with semaphores is that they are too low level in nature: they are similar to doing mutual exclusion and synchronisation in assembly language using goto’s. They have no structure. They are also damnably hard to prove correct and near to impossible to test!
What is needed are high-level language constructs that enforce the necessary discipline.
The two main contenders for this job are:
- Critical Regions, and more usefully, Conditional Critical Regions
Monitors are a common high-level synchronization tool which solve some of the problems associated with semaphores.
Monitors are actually a much nicer way of implementing mutual exclusion than semaphores. One of the reasons for this is that the code that implements mutual exclusion is all in one place, the monitor. With semaphores, code can distributed all over the place in the form of wait and signal semaphore function calls.
Additionally, it is next to impossible to setup a monitor incorrectly. On the other hand with semaphores it is quite common to do a wait (B) when you should have done a wait
(C). Simple little mistakes are easy to make with semaphores.
3.3.1 Process Synchronization with Monitors
Process synchronization with monitors is implemented in much the same way as it is implemented with semaphores. However, with monitors you use condition variables rather than semaphores.
For this reason, it is important that you realize the difference between semaphores and condition variables. This is made more difficult because
- both semaphores and condition variables use wait and signal as the valid operations,
- the purpose of both is somewhat similar, and
- they are actually quite different.
The main difference is the operation of signal. With a semaphore the signal operation actually increments the value of the semaphore. So, if there are not any processes blocked on the semaphore, the signal will be “remembered” by the incrementing of the semaphore.
The signal function on a Monitor’s condition variable is different. If there are no processes blocked on the condition variable then the signal function does nothing. The signal is not remembered. In order to remember “empty signals”, you have to use some other form of variables. The good part of this is that using other variables within a monitor is simple because we can be assured that mutual exclusion is being implemented.
In this unit, you learnt some of the methods for synchronizing co-operating processes and how these methods are implemented as well as the advantages and disadvantages of each approach. In the next unit we will discuss some of the classic problems of synchronization.