Synchronization Hardware semaphores
have just described one software-based solution to the critical-section
problem. However, as mentioned, software-based solutions such as Peterson's are
not guaranteed to work on modern computer architectures.
- Instead, we can
generally state that any solution to the critical-section problem requires a simple
- Race conditions are
prevented by requiring that critical regions be protected by locks.
- That is, a process must
acquire a lock before entering a critical section; it releases the lock when it
exits the critical section. This is illustrated in Figure 2.27.
Figure 2.27 Solution to the critical-section problem using locks.
- In the following discussions, we explore several more solutions to the critical-section problem using techniques ranging from hardware to software based APIs available to application programmers.
- All these solutions are based on the premise of locking; however, as we shall see, the designs of such locks can be quite sophisticated.
Figure 2.28 The definition of the TestAndSet () instruction.
Figure 2.29 Mutual-exclusion
implementation with TestAndSet ().
- We start by presenting
some simple hardware instructions that are available on many systems and
showing how they can be used effectively in solving the critical-section
- Hardware features can
make any programming task easier and improve system efficiency.
- The critical-section
problem could be solved simply in a uniprocessor environment if we could
prevent interrupts from occurring while a shared variable was being modified.
- In this manner, we
could be sure that the current sequence of instructions would be allowed to
execute in order without preemption.
- No other instructions
would be run, so no unexpected modifications could be made to the shared
- This is often the
approach taken by nonpreemptive kernels. Unfortunately, this solution is not as
feasible in a multiprocessor environment.
- Disabling interrupts on
a multiprocessor can be time consuming, as the message is passed to all the
- This message passing
delays entry into each critical section, and system efficiency decreases.
- Also consider the
effect on a system's clock if the clock is kept updated by interrupts.
- Many modern computer systems therefore
provide special hardware instructions that allow us either to test and modify
the content of a word or to swap the contents of two words atomically - that is, as one uninterruptible unit.
Figure 2.30 The definition of the Swap
Figure 2.31 Mutual-exclusion implementation with the Swap() instruction.
- We can use these
special instructions to solve the critical-section problem in a relatively
- Rather than discussing
one specific instruction for one specific machine, we abstract the main
concepts behind these types of instructions by describing the TestAndSet () and
- The TestAndSet ()
instruction can be defined as shown in Figure 2.28. The important
characteristic of this instruction is that it is executed atomically.
- Thus, if two TestAndSet
() instructions are executed simultaneously (each on a different CPU), they
will be executed sequentially in some arbitrary order.
- If the machine supports
the TestAndSet () instruction, then we can implement mutual exclusion by
declaring a Boolean variable lock, initialized to false. The structure of
process Pi is shown in Figure 2.29.
- The Swap() instruction, in contrast to the
TestAndSet () instruction, operates on the contents of two words; it is defined
as shown in Figure 2.30
Figure 2.32 Bounded-waiting mutual exclusion with TestAndSet ().
the TestAndSet () instruction, it is executed atomically. If the machine
supports the Swap() instruction, then mutual exclusion can be provided as
- A global Boolean
variable lock is declared and is initialized to false. In addition, each
process has a local Boolean variable key. The structure of process P; is
shown in Figure 2.31.
- Although these
algorithms satisfy the mutual-exclusion requirement, they do not satisfy the
- In Figure 2.32, we
present another algorithm using the TestAndSet () instruction that satisfies
all the critical-section requirements. The common data structures are
data structures are initialized to false. To prove that the mutual exclusion
requirement is met, we note that process Pi can enter its critical
section only if either waiting [i] == false or key == false. The value of key
can become false only if the TestAndSet () is executed.
- The first process to
execute the TestAndSet () will find key== false; all others must wait.
- The variable waiting
[i] can become false only if another process leaves its critical section; only
one waiting [i] is set to false, maintaining the mutual-exclusion requirement.
- To prove that the
progress requirement is met, we note that the arguments presented for mutual
exclusion also apply here, since a process exiting the critical section either
sets lock to false or sets waiting[j] to false.
- Both allow a process
that is waiting to enter its critical section to proceed.
- To prove that the
bounded-waiting requirement is met, we note that, when a process leaves its
critical section, it scans the array waiting in the cyclic ordering (i + 1, i
+ 2, ... , n-1, 0, ... , i-1).
- It designates the first
process in this ordering that is in the entry section (waiting[j] ==true) as
the next one to
- enter the critical
- Any process waiting to
enter its critical section will thus do so within n - 1 turns.
- Unfortunately for
hardware designers, implementing atomic TestAndSet() instructions on
multiprocessors is not a trivial task.
- The Operating System Concepts by Silberschatz, Galvin, Gagne, 8th Edition
- MODERN OPERATING SYSTEMS by Andrew S. Tanenbaum, Second Edition