Chapter 6 Flashcards
A cooperating process
is one that can affect or be affected by other processes
executing in the system. Cooperating processes can either directly share a
logical address space (that is, both code and data) or be allowed to share data
only through shared memory or message passing. Concurrent access to shared
data may result in data inconsistency, however. In this chapter, we discuss
various mechanisms to ensure the orderly execution of cooperating processes
that share a logical address space, so that data consistency is maintained.
Bounded buffer
We now return to our consideration of the bounded buffer. As we pointed
out, our original solution allowed at most BUFFER SIZE − 1 items in the buffer
at the same time. Suppose we want to modify the algorithm to remedy this
deficiency. One possibility is to add an integer variable, count, initialized to
0. count is incremented every time we add a new item to the buffer and is
decremented every time we remove one item from the buffer. The code for the
producer process can be modified as follows:
while (true) {
/* produce an item in next produced /
while (count == BUFFER SIZE)
; / do nothing /
buffer[in] = next produced;
in = (in + 1) % BUFFER SIZE;
count++;
}
The code for the consumer process can be modified as follows:
while (true) {
while (count == 0)
; / do nothing /
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
count–;
/ consume the item in next consumed */
}
Although the producer and consumer routines shown above are correct
separately, they may not function correctly when executed concurrently. As
an illustration, suppose that the value of the variable count is currently 5 and
that the producer and consumer processes concurrently execute the statements
“count++” and “count–”. Following the execution of these two statements,
the value of the variable count may be 4, 5, or 6! The only correct result, though,
is count == 5, which is generated correctly if the producer and consumer
execute separately.
We can show that the value of count may be incorrect as follows. Note
that the statement “count++” may be implemented in machine language (on a
typical machine) as follows:
register1 = count
register1 = register1 + 1
count = register1
where register1 is one of the local CPU registers. Similarly, the statement “count-
-” is implemented as follows:
register2 = count
register2 = register2 − 1
count = register2
where again register2 is one of the local CPU registers. Even though register1 and
register2 may be the same physical register, remember that the contents of this
register will be saved and restored by the interrupt handler (Section 1.2.3).
The concurrent execution of “count++” and “count–” is equivalent to a
sequential execution inwhich the lower-level statements presented previously
are interleaved in some arbitrary order (but the order within each high-level
statement is preserved). One such interleaving is the following:
T0: producer execute register1 = count {register1 = 5}
T1: producer execute register1 = register1 +1 {register1 = 6}
T2: consumer execute register2 = count {register2 = 5}
T3: consumer execute register2 = register2 −1 {register2 = 4}
T4: producer execute count = register1 {count = 6}
T5: consumer execute count = register2 {count = 4}
Notice that we have arrived at the incorrect state “count == 4”, indicating that
four buffers are full, when, in fact, five buffers are full. If we reversed the order
of the statements at T4 and T5, we would arrive at the incorrect state “count
== 6”.
We would arrive at this incorrect state because we allowed both processes
to manipulate the variable count concurrently. A situation like this, where
several processes access and manipulate the same data concurrently and the
outcome of the execution depends on the particular order in which the access
takes place, is called a race condition. To guard against the race condition
above, we need to ensure that only one process at a time can be manipulating
the variable count. To make such a guarantee, we require that the processes be
synchronized in some way.
Situations such as the one just described occur frequently in operating
systems as different parts of the system manipulate resources. Furthermore,
as we have emphasized in earlier chapters, the prominence of multicore systems
has brought an increased emphasis on developing multithreaded applications.
In such applications, several threads—which are quite possibly sharing
data—are running in parallel on different processing cores. Clearly, we
want any changes that result from such activities not to interfere with one. another. Because of the importance of this issue, we devote a major portion of
this chapter to process synchronization and coordination among cooperating
processes.
Critical section problem
We begin our consideration of process synchronization by discussing the socalled
critical-section problem. Consider a system consisting of n processes
{P0, P1, …, Pn−1}. Each process has a segment of code, called a critical section,
in which the process may be accessing — and updating — data that is shared
with at least one other process. The important feature of the system is that,
when one process is executing in its critical section, no other process is allowed
to execute in its critical section. That is, no two processes are executing in their
critical sections at the same time. The critical-section problem is to design
a protocol that the processes can use to synchronize their activity so as to
cooperatively share data. Each process must request permission to enter its
critical section. The section of code implementing this request is the entry
section. The critical sectionmay be followed by an exit section. The remaining
code is the remainder section. The general structure of a typical process is
shown in Figure 6.1. The entry section and exit section are enclosed in boxes to
highlight these important segments of code.
A solution to the critical-section problem must satisfy the following three
requirements:
1. Mutual exclusion. If process Pi is executing in its critical section, then no
other processes can be executing in their critical sections.
2. Progress. If no process is executing in its critical section and some processes
wish to enter their critical sections, then only those processes that
are not executing in their remainder sections can participate in deciding
which will enter its critical section next, and this selection cannot be
postponed indefinitely.
3. Bounded waiting. There exists a bound, or limit, on the number of times
that other processes are allowed to enter their critical sections after a
process has made a request to enter its critical section and before that
request is granted.
We assume that each process is executing at a nonzero speed.However,we can
make no assumption concerning the relative speed of the n processes.
At a given point in time, many kernel-mode processes may be active in
the operating system. As a result, the code implementing an operating system
(kernel code) is subject to several possible race conditions. Consider as an
example a kernel data structure that maintains a list of all open files in the
system. This list must be modified when a new file is opened or closed (adding
the file to the list or removing it fromthe list). If two processeswere to open files
simultaneously, the separate updates to this list could result in a race condition.
Another example is illustrated in Figure 6.2. In this situation, two processes,
P0 and P1, are creating child processes using the fork() system call.
Recall from Section 3.3.1 that fork() returns the process identifier of the newly
created process to the parent process. In this example, there is a race condition
on the variable kernel variable next available pid which represents
the value of the next available process identifier. Unless mutual exclusion is
provided, it is possible the same process identifier number could be assigned
to two separate processes.
Other kernel data structures that are prone to possible race conditions
include structures for maintaining memory allocation, for maintaining process
lists, and for interrupt handling. It is up to kernel developers to ensure that the
operating system is free from such race conditions.
The critical-section problem could be solved simply in a single-core environment
if we could prevent interrupts fromoccurring while a shared variable
was being modified. In this way, 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 variable.
Critical section multiprocessing
Unfortunately, this solution is not as feasible in a multiprocessor environment.
Disabling interrupts on a multiprocessor can be time consuming, since
the message is passed to all the processors. 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.
Two general approaches are used to handle critical sections in operating
systems: preemptive kernels and nonpreemptive kernels. A preemptive kernel
allows a process to be preempted while it is running in kernel mode. A
nonpreemptive kernel does not allow a process running in kernel mode to be
preempted; a kernel-mode process will run until it exits kernel mode, blocks,
or voluntarily yields control of the CPU.
Obviously, a nonpreemptive kernel is essentially free from race conditions
on kernel data structures, as only one process is active in the kernel at a time.
We cannot say the same about preemptive kernels, so they must be carefully
designed to ensure that shared kernel data are free from race conditions. Preemptive
kernels are especially difficult to design for SMP architectures, since
in these environments it is possible for two kernel-mode processes to run
simultaneously on different CPU cores.
Why, then, would anyone favor a preemptive kernel over a nonpreemptive
one? A preemptive kernel may be more responsive, since there is less risk
that a kernel-mode process will run for an arbitrarily long period before relinquishing
the processor to waiting processes. (Of course, this risk can also be
minimized by designing kernel code that does not behave in this way.) Furthermore,
a preemptive kernel is more suitable for real-time programming, as
it will allow a real-time process to preempt a process currently running in the
kernel.
Peterson solution
Next,we illustrate a classic software-based solution to the critical-section problem
known as Peterson’s solution. Because of the way modern computer
architectures perform basic machine-language instructions, such as load and
store, there are no guarantees that Peterson’s solution will work correctly
on such architectures. However, we present the solution because it provides a
good algorithmic description of solving the critical-section problem and illustrates
some of the complexities involved in designing software that addresses
the requirements of mutual exclusion, progress, and bounded waiting.
Peterson’s solution is restricted to two processes that alternate execution
between their critical sections and remainder sections. The processes are numbered
P0 and P1. For convenience, when presenting Pi, we use Pj to denote the
other process; that is, j equals 1 − i.
Peterson’s solution requires the two processes to share two data items:
int turn;
boolean flag[2];
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
;
/* critical section /
flag[i] = false;
/remainder section */
}
Figure 6.3 The structure of process Pi in Peterson’s solution.
The variable turn indicates whose turn it is to enter its critical section. That is,
if turn == i, then process Pi is allowed to execute in its critical section. The
flag array is used to indicate if a process is ready to enter its critical section.
For example, if flag[i] is true, Pi is ready to enter its critical section.With an
explanation of these data structures complete, we are now ready to describe
the algorithm shown in Figure 6.3.
To enter the critical section, process Pi first sets flag[i] to be true and
then sets turn to the value j, thereby asserting that if the other process wishes
to enter the critical section, it can do so. If both processes try to enter at the same
time, turn will be set to both i and j at roughly the same time. Only one of
these assignments will last; the other will occur but will be overwritten immediately.
The eventual value of turn determines which of the two processes is
allowed to enter its critical section first.
We now prove that this solution is correct.We need to show that:
1. Mutual exclusion is preserved.
2. The progress requirement is satisfied.
3. The bounded-waiting requirement is met.
To prove property 1, we note that each Pi enters its critical section only
if either flag[j] == false or turn == i. Also note that, if both processes
can be executing in their critical sections at the same time, then flag[0] ==
flag[1] == true. These two observations imply that P0 and P1 could not
have successfully executed their while statements at about the same time,
since the value of turn can be either 0 or 1 but cannot be both. Hence, one of
the processes—say, Pj—must have successfully executed the while statement,
whereas Pi had to execute at least one additional statement (“turn == j”).
However, at that time, flag[j] == true and turn == j, and this condition
will persist as long as Pj is in its critical section; as a result, mutual exclusion is
preserved.
To prove properties 2 and 3,we note that a process Pi can be prevented from
entering the critical section only if it is stuck in the while loop with the condition
flag[j] == true and turn == j; this loop is the only one possible. If Pj is not
ready to enter the critical section, then flag[j] == false, and Pi can enter its
critical section. If Pj has set flag[j] to true and is also executing in its while
statement, then either turn == i or turn == j. If turn == i, then Pi will enter
the critical section. If turn == j, then Pj will enter the critical section. However,
once Pj exits its critical section, it will reset flag[j] to false, allowing Pi to
enter its critical section. If Pj resets flag[j] to true, it must also set turn to i.
Thus, since Pi does not change the value of the variable turn while executing
the while statement, Pi will enter the critical section (progress) after at most
one entry by Pj (bounded waiting).
As mentioned at the beginning of this section, Peterson’s solution is not
guaranteed to work on modern computer architectures for the primary reason
that, to improve system performance, processors and/or compilers may
reorder read and write operations that have no dependencies. For a singlethreaded
application, this reordering is immaterial as far as program correctness
is concerned, as the final values are consistent with what is expected. (This
is similar to balancing a checkbook—the actual order inwhich credit and debit
operations are performed is unimportant, because the final balance will still be
the same.) But for a multithreaded applicationwith shared data, the reordering
of instructions may render inconsistent or unexpected results.
As an example, consider the following data that are shared between two
threads:
boolean flag = false;
int x = 0;
where Thread 1 performs the statements
while (!flag)
;
print x;
and Thread 2 performs
x = 100;
flag = true;
The expected behavior is, of course, that Thread 1 outputs the value 100 for
variable x. However, as there are no data dependencies between the variables
flag and x, it is possible that a processor may reorder the instructions for
Thread 2 so that flag is assigned true before assignment of x = 100. In
this situation, it is possible that Thread 1 would output 0 for variable x. Less
obvious is that the processor may also reorder the statements issued by Thread
1 and load the variable x before loading the value of flag. If this were to occur,
Thread 1would output 0 for variable x even if the instructions issued by Thread
2 were not reordered.
How does this affect Peterson’s solution? Consider what happens if the
assignments of the first two statements that appear in the entry section of
Peterson’s solution in Figure 6.3 are reordered; it is possible that both threads
may be active in their critical sections at the same time, as shown in Figure 6.4.
As you will see in the following sections, the only way to preserve mutual
exclusion is by using proper synchronization tools. Our discussion of these
tools begins with primitive support in hardware and proceeds through
abstract, high-level, software-based APIs available to both kernel developers
and application programmers.
Memory Barriers
In Section 6.3, we saw that a system may reorder instructions, a policy that can
lead to unreliable data states. How a computer architecture determines what
memory guarantees it will provide to an application program is known as its
memory model. In general, a memory model falls into one of two categories:
1. Strongly ordered, where a memory modification on one processor is
immediately visible to all other processors.
2. Weakly ordered, where modifications to memory on one processor may
not be immediately visible to other processors.
Memory models vary by processor type, so kernel developers cannotmake
any assumptions regarding the visibility of modifications to memory on a
shared-memory multiprocessor. To address this issue, computer architectures
provide instructions that can force any changes in memory to be propagated to
all other processors, thereby ensuring that memory modifications are visible to
threads running on other processors. Such instructions are known as memory
barriers or memory fences. When a memory barrier instruction is performed,
the system ensures that all loads and stores are completed before any subsequent
load or store operations are performed. Therefore, even if instructions
were reordered, the memory barrier ensures that the store operations are completed
in memory and visible to other processors before future load or store
operations are performed.
Let’s return to our most recent example, inwhich reordering of instructions
could have resulted in the wrong output, and use a memory barrier to ensure
that we obtain the expected output.
If we add a memory barrier operation to Thread 1
while (!flag)
memory barrier();
print x;
we guarantee that the value of flag is loaded before the value of x.
Similarly, if we place a memory barrier between the assignments performed
by Thread 2
x = 100;
memory barrier();
flag = true;
we ensure that the assignment to x occurs before the assignment to flag.
With respect to Peterson’s solution, we could place a memory barrier
between the first two assignment statements in the entry section to avoid the
reordering of operations shown in Figure 6.4. Note that memory barriers are
considered very low-level operations and are typically only used by kernel
developers when writing specialized code that ensures mutual exclusion.
Hardware Instructions
Many modern computer systems provide special hardware instructions that
allow us either to test and modify the content of aword or to swap the contents
of two words atomically—that is, as one uninterruptible unit. We can use
these special instructions to solve the critical-section problem in a relatively
simple manner. Rather than discussing one specific instruction for one specific
machine, we abstract the main concepts behind these types of instructions by
describing the test and set() and compare and swap() instructions. The test and set() instruction can be defined as shown in Figure 6.5.
The important characteristic of this instruction is that it is executed atomically.
Thus, if two test and set() instructions are executed simultaneously
(each on a different core), they will be executed sequentially in some arbitrary
order. If the machine supports the test and set() 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 6.6.
The compare and swap() instruction (CAS), just like the test and set()
instruction, operates on two words atomically, but uses a different mechanism
that is based on swapping the content of two words.
The CAS instruction operates on three operands and is defined in Figure
6.7. The operand value is set to new value only if the expression (*value
== expected) is true. Regardless, CAS always returns the original value of
the variable value. The important characteristic of this instruction is that it is
executed atomically. Thus, if two CAS instructions are executed simultaneously
(each on a different core), they will be executed sequentially in some arbitrary
order.
Mutual exclusion using CAS can be provided as follows: A global variable
(lock) is declared and is initialized to 0. The first process that invokes
compare and swap() will set lock to 1. It will then enter its critical section, because the original value of lock was equal to the expected value of 0. Subsequent
calls to compare and swap() will not succeed, because lock now is not
equal to the expected value of 0.When a process exits its critical section, it sets
lock back to 0, which allows another process to enter its critical section. The
structure of process Pi is shown in Figure 6.8.
Although this algorithm satisfies the mutual-exclusion requirement, it
does not satisfy the bounded-waiting requirement. In Figure 6.9, we present
another algorithm using the compare and swap() instruction that satisfies all
the critical-section requirements. The common data structures are
boolean waiting[n];
int lock;
The elements in the waiting array are initialized to false, and lock is initialized
to 0. 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 == 0. The value of key can become 0 only if the compare and swap() is
executed. The first process to execute the compare and swap() will find key
== 0; 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 0 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 section. Any process waiting to enter its critical section will
thus do so within n − 1 turns.
Details describing the implementation of the atomic test and set() and
compare and swap() instructions are discussed more fully in books on computer
architecture.
MAKING COMPARE-AND-SWAP ATOMIC
On Intel x86 architectures, the assembly language statement cmpxchg is
used to implement the compare and swap() instruction. To enforce atomic
execution, the lock prefix is used to lock the bus while the destination
operand is being updated. The general form of this instruction appears as:
lock cmpxchg <destination>, <source></source></destination>
Atomic Variables
Typically, the compare and swap() instruction is not used directly to provide
mutual exclusion. Rather, it is used as a basic building block for constructing
other tools that solve the critical-section problem. One such tool is an atomic
variable,which provides atomic operations on basic data types such as integers
and booleans.We know from Section 6.1 that incrementing or decrementing an
integer value may produce a race condition. Atomic variables can be used in
to ensure mutual exclusion in situations where there may be a data race on a
single variable while it is being updated, as when a counter is incremented.
Most systems that support atomic variables provide special atomic data
types as well as functions for accessing and manipulating atomic variables.
These functions are often implemented using compare and swap() operations.
As an example, the following increments the atomic integer sequence:
increment(&sequence);
where the increment() function is implemented using the CAS instruction:
void increment(atomic int *v)
{
int temp;
do {
temp = *v;
}
while (temp != compare and swap(v, temp, temp+1));
}
It is important to note that although atomic variables provide atomic
updates, they do not entirely solve race conditions in all circumstances. For
example, in the bounded-buffer problem described in Section 6.1,we could use
an atomic integer for count. Thiswould ensure that the updates to count were
atomic.However, the producer and consumer processes also have while loops
whose condition depends on the value of count. Consider a situation in which
the buffer is currently empty and two consumers are looping while waiting for
count > 0. If a producer entered one item in the buffer, both consumers could
exit their while loops (as count would no longer be equal to 0) and proceed to
consume, even though the value of count was only set to 1.
Atomic variables are commonly used in operating systems as well as concurrent
applications, although their use is often limited to single updates of
shared data such as counters and sequence generators. In the following sections,
we explore more robust tools that address race conditions in more generalized
situations.
Mutex Locks
The hardware-based solutions to the critical-section problem presented in Section
6.4 are complicated as well as generally inaccessible to application programmers.
Instead, operating-system designers build higher-level software
tools to solve the critical-section problem. The simplest of these tools is the
mutex lock. (In fact, the termmutex is short for mutual exclusion.) We use the
mutex lock to protect critical sections and thus prevent race conditions. That
is, a process must acquire the lock before entering a critical section; it releases
the lock when it exits the critical section. The acquire()function acquires the
lock, and the release() function releases the lock, as illustrated in Figure 6.10.
A mutex lock has a boolean variable available whose value indicates if
the lock is available or not. If the lock is available, a call to acquire() succeeds,
and the lock is then considered unavailable. Aprocess that attempts to acquire
an unavailable lock is blocked until the lock is released.
The definition of acquire() is as follows:
acquire() {
while (!available)
; /* busy wait */
available = false;
}
The definition of release() is as follows:
release() {
available = true;
}
Calls to either acquire() or release() must be performed atomically.
Thus, mutex locks can be implemented using the CAS operation described in
Section 6.4, and we leave the description of this technique as an exercise.
LOCK CONTENTION
Locks are either contended or uncontended. A lock is considered contended
if a thread blocks while trying to acquire the lock. If a lock is available when
a thread attempts to acquire it, the lock is considered uncontended. Contended
locks can experience either high contention (a relatively large number
of threads attempting to acquire the lock) or low contention (a relatively
small number of threads attempting to acquire the lock.) Unsurprisingly,
highly contended locks tend to decrease overall performance of concurrent
applications. Themain disadvantage of the implementation given here is that it requires
busy waiting. While a process is in its critical section, any other process that
tries to enter its critical section must loop continuously in the call to acquire().
This continual looping is clearly a problem in a real multiprogramming system,
where a single CPU core is shared among many processes. Busy waiting also
wastes CPU cycles that some other process might be able to use productively.
(In Section 6.6, we examine a strategy that avoids busy waiting by temporarily
putting the waiting process to sleep and then awakening it once the lock
becomes available.)
The type of mutex lock we have been describing is also called a spinlock
because the process “spins” while waiting for the lock to become available.
(We see the same issue with the code examples illustrating the compare
and swap() instruction.) Spinlocks do have an advantage, however, in
that no context switch is required when a process must wait on a lock, and a
context switch may take considerable time. In certain circumstances on multicore
systems, spinlocks are in fact the preferable choice for locking. If a lock is
to be held for a short duration, one thread can “spin” on one processing core
while another thread performs its critical section on another core. On modern
multicore computing systems, spinlocks are widely used in many operating
systems.
In Chapter 7 we examine how mutex locks can be used to solve classical
synchronization problems.We also discuss how mutex locks and spinlocks are
used in several operating systems, as well as in Pthreads
WHAT IS MEANT BY “SHORT DURATION”?
Spinlocks are often identified as the locking mechanism of choice on multiprocessor
systems when the lock is to be held for a short duration. But what
exactly constitutes a short duration? Given that waiting on a lock requires
two context switches—a context switch to move the thread to the waiting
state and a second context switch to restore the waiting thread once the lock
becomes available—the general rule is to use a spinlock if the lock will be
held for a duration of less than two context switches.
Semaphores
A semaphore S is an integer variable that, apart from initialization, is
accessed only through two standard atomic operations: wait() and signal().
Semaphores were introduced by the Dutch computer scientist Edsger Dijkstra,
and such, the wait() operation was originally termed P (from the Dutch
proberen, “to test”); signal() was originally called V (from verhogen, “to increment”).
The definition of wait() is as follows:
wait(S) {
while (S <= 0)
; // busy wait
S–;
}
The definition of signal() is as follows:
signal(S) {
S++;
}
All modifications to the integer value of the semaphore in the wait() and
signal() operations must be executed atomically. That is, when one process
modifies the semaphore value, no other process can simultaneously modify
that same semaphore value. In addition, in the case of wait(S), the testing of
the integer value of S (S ≤ 0), as well as its possible modification (S–), must
be executed without interruption. We shall see how these operations can be
implemented in Section 6.6.2. First, let’s see how semaphores can be used.
Semaphore Usage
Operating systems often distinguish between counting and binary
semaphores. The value of a counting semaphore can range over an
unrestricted domain. The value of a binary semaphore can range only
between 0 and 1. Thus, binary semaphores behave similarly to mutex locks. In
fact, on systems that do not provide mutex locks, binary semaphores can be
used instead for providing mutual exclusion.
Counting semaphores can be used to control access to a given resource
consisting of a finite number of instances. The semaphore is initialized to the
number of resources available. Each process that wishes to use a resource
performs a wait() operation on the semaphore (thereby decrementing the
count). When a process releases a resource, it performs a signal() operation
(incrementing the count). When the count for the semaphore goes to 0, all
resources are being used. After that, processes that wish to use a resource will
block until the count becomes greater than 0.
We can also use semaphores to solve various synchronization problems.
For example, consider two concurrently running processes: P1 with a statement
S1 and P2 with a statement S2. Suppose we require that S2 be executed only after
S1 has completed. We can implement this scheme readily by letting P1 and P2
share a common semaphore synch, initialized to 0. In process P1, we insert the
statements
S1;
signal(synch);
In process P2, we insert the statements
wait(synch);
S2;
Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked
signal(synch), which is after statement S1 has been executed.
Semaphore Implementation
Recall that the implementation of mutex locks discussed in Section 6.5 suffers
from busy waiting. The definitions of the wait() and signal() semaphore
operations just described present the same problem. To overcome this problem,
we can modify the definition of the wait() and signal() operations
as follows: When a process executes the wait() operation and finds that the
semaphore value is not positive, it must wait. However, rather than engaging
in busy waiting, the process can suspend itself. The suspend operation places
a process into a waiting queue associated with the semaphore, and the state of
the process is switched to the waiting state. Then control is transferred to the
CPU scheduler, which selects another process to execute.
Aprocess that is suspended, waiting on a semaphore S, should be restarted
when some other process executes a signal() operation. The process is
restarted by a wakeup() operation, which changes the process fromthewaiting
state to the ready state. The process is then placed in the ready queue. (The
CPU may or may not be switched from the running process to the newly ready
process, depending on the CPU-scheduling algorithm.)
To implement semaphores under this definition, we define a semaphore as
follows:
typedef struct {
int value;
struct process *list;
} semaphore;
Each semaphore has an integer value and a list of processes list. When
a process must wait on a semaphore, it is added to the list of processes. A
signal() operation removes one process from the list of waiting processes
and awakens that process.
Now, the wait() semaphore operation can be defined as
wait(semaphore *S) {
S->value–;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}
and the signal() semaphore operation can be defined as
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
The sleep() operation suspends the process that invokes it. The wakeup(P)
operation resumes the execution of a suspended process P. These two operations
are provided by the operating system as basic system calls.
Note that in this implementation, semaphore values may be negative,
whereas semaphore values are never negative under the classical definition of
semaphoreswith busywaiting. If a semaphore value is negative, itsmagnitude
is the number of processes waiting on that semaphore. This fact results from
switching the order of the decrement and the test in the implementation of the
wait() operation.
The list of waiting processes can be easily implemented by a link field in
each process control block (PCB). Each semaphore contains an integer value and
a pointer to a list of PCBs. One way to add and remove processes from the list
so as to ensure bounded waiting is to use a FIFO queue, where the semaphore
contains both head and tail pointers to the queue. In general, however, the list
can use any queuing strategy. Correct usage of semaphores does not depend
on a particular queuing strategy for the semaphore lists.
As mentioned, it is critical that semaphore operations be executed atomically.
We must guarantee that no two processes can execute wait() and signal()
operations on the same semaphore at the same time. This is a criticalsection
problem, and in a single-processor environment,we can solve it by simply
inhibiting interrupts during the time the wait() and signal() operations
are executing. This scheme works in a single-processor environment because,
once interrupts are inhibited, instructions from different processes cannot be
interleaved. Only the currently running process executes until interrupts are
reenabled and the scheduler can regain control.
In a multicore environment, interrupts must be disabled on every processing
core. Otherwise, instructions from different processes (running on different
cores) may be interleaved in some arbitrary way. Disabling interrupts
on every core can be a difficult task and can seriously diminish performance.
Therefore, SMP systems must provide alternative techniques—such as compare
and swap() or spinlocks—to ensure that wait() and signal() are performed
atomically.
It is important to admit that we have not completely eliminated busy
waiting with this definition of the wait() and signal() operations. Rather,
we have moved busy waiting from the entry section to the critical sections
of application programs. Furthermore, we have limited busy waiting to the
critical sections of the wait() and signal() operations, and these sections are
short (if properly coded, they should be no more than about ten instructions).
Thus, the critical section is almost never occupied, and busy waiting occurs
rarely, and then for only a short time. An entirely different situation exists
with application programs whose critical sections may be long (minutes or
even hours) or may almost always be occupied. In such cases, busy waiting
is extremely inefficient.
