CHAPTER
CONCURRENCY:MUTUAL
EXCLUSION AND
SYNCHRONIZATION
5.1 Principles of Concurrency
A Simple Example
Race Condition
Operating System Concerns
Process Interaction
Requirements for Mutual Exclusion
5.2 Mutual Exclusion: Hardware Support
Interrupt Disabling
Special Machine Instructions
5.3 Semaphores
Mutual Exclusion
The Producer/Consumer Problem
Implementation of Semaphores
5.4 Monitors
Monitor with Signal
Alternate Model of Monitors with Notify and Broadcast
5.5 Message Passing
Synchronization
Addressing
Message Format
Queuing Discipline
Mutual Exclusion
5.6 Readers/Writers Problem
Readers Have Priority
Writers Have Priority
5.7 Summary
5.8 Recommended Reading
5.9 Key Terms, Review Questions, and Problems
205
M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 PM Page 205
The central themes of operating system design are all concerned with the management
of processes and threads:
• Multiprogramming: The management of multiple processes within a
uniprocessor system.
• Multiprocessing: The management of multiple processes within a multiprocessor.
• Distributed processing: The management of multiple processes executing on
multiple, distributed computer systems.The recent proliferation of clusters is a
prime example of this type of system.
Fundamental to all of these areas, and fundamental to OS design, is concurrency.
Concurrency encompasses a host of design issues, including communication among
processes, sharing of and competing for resources (such as memory, files, and I/O ac-
cess), synchronization of the activities of multiple processes, and allocation of
processor time to processes.We shall see that these issues arise not just in multipro-
cessing and distributed processing environments but even in single-processor multi-
programming systems.
Concurrency arises in three different contexts:
• Multiple applications: Multiprogramming was invented to allow processing
time to be dynamically shared among a number of active applications.
• Structured applications: As an extension of the principles of modular design
and structured programming, some applications can be effectively pro-
grammed as a set of concurrent processes.
• Operating system structure: The same structuring advantages apply to systems
programs, and we have seen that operating systems are themselves often im-
plemented as a set of processes or threads.
Because of the importance of this topic, four chapters and an appendix of this
book focus on concurrency-related issues. This chapter and the next deal with con-
currency in multiprogramming and multiprocessing systems. Chapters 16 and 18 ex-
amine concurrency issues related to distributed processing.Although the remainder
of this book covers a number of other important topics in OS design, concurrency
will play a major role in our consideration of all of these other topics.
This chapter begins with an introduction to the concept of concurrency and
the implications of the execution of multiple concurrent processes.
1
We find that the
basic requirement for support of concurrent processes is the ability to enforce mu-
tual exclusion; that is, the ability to exclude all other processes from a course of ac-
tion while one process is granted that ability. Next, we examine some hardware
mechanisms that can support mutual exclusion. Then we look at solutions that do
not involve busy waiting and that can be supported either by the OS or enforced by
language compilers.We examine three approaches: semaphores, monitors, and mes-
sage passing.
1
For simplicity, we generally refer to the concurrent execution of processes. In fact, as we have seen
in the preceding chapter, in some systems the fundamental unit of concurrency is a thread rather than
a process.
206 CHAPTER 5 / CONCURRENCY: MUTUAL EXCLUSION AND SYNCHRONIZATION
M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 PM Page 206
5.1 / PRINCIPLES OF CONCURRENCY 207
Two classic problems in concurrency are used to illustrate the concepts and com-
pare the approaches presented in this chapter. The producer/consumer problem is in-
troduced in Section 5.3 and used as a running example. The chapter closes with the
readers/writers problem.
Our discussion of concurrency continues in Chapter 6, and we defer a discussion
of the concurrency mechanisms of our example systems until the end of that chapter.
Appendix A covers additional topics on concurrency.
Table 5.1 lists some key terms related to concurrency.
5.1 PRINCIPLES OF CONCURRENCY
In a single-processor multiprogramming system, processes are interleaved in time to
yield the appearance of simultaneous execution (Figure 2.12a). Even though actual
parallel processing is not achieved, and even though there is a certain amount of
overhead involved in switching back and forth between processes, interleaved exe-
cution provides major benefits in processing efficiency and in program structuring.
In a multiple-processor system, it is possible not only to interleave the execution of
multiple processes but also to overlap them (Figure 2.12b).
At first glance, it may seem that interleaving and overlapping represent funda-
mentally different modes of execution and present different problems. In fact, both
techniques can be viewed as examples of concurrent processing, and both present
the same problems. In the case of a uniprocessor, the problems stem from a basic
characteristic of multiprogramming systems: The relative speed of execution of
processes cannot be predicted. It depends on the activities of other processes, the
way in which the OS handles interrupts, and the scheduling policies of the OS. The
following difficulties arise:
1. The sharing of global resources is fraught with peril.For example, if two processes
both make use of the same global variable and both perform reads and writes on
that variable, then the order in which the various reads and writes are executed is
critical.An example of this problem is shown in the following subsection.
Table 5.1 Some Key Terms Related to Concurrency
atomic operation A sequence of one or more statements that appears to be indivisible; that is, no other
process can see an intermediate state or interrupt the operation.
critical section A section of code within a process that requires access to shared resources and that must
not be executed while another process is in a corresponding section of code.
deadlock A situation in which two or more processes are unable to proceed because each is waiting
for one of the others to do something.
livelock A situation in which two or more processes continuously change their states in response
to changes in the other process(es) without doing any useful work.
mutual exclusion The requirement that when one process is in a critical section that accesses shared resources,
no other process may be in a critical section that accesses any of those shared resources.
race condition A situation in which multiple threads or processes read and write a shared data item and
the final result depends on the relative timing of their execution.
starvation A situation in which a runnable process is overlooked indefinitely by the scheduler;
although it is able to proceed, it is never chosen.
M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 PM Page 207
208 CHAPTER 5 / CONCURRENCY: MUTUAL EXCLUSION AND SYNCHRONIZATION
2. It is difficult for the OS to manage the allocation of resources optimally. For ex-
ample, process A may request use of, and be granted control of, a particular I/O
channel and then be suspended before using that channel. It may be undesirable
for the OS simply to lock the channel and prevent its use by other processes; in-
deed this may lead to a deadlock condition, as described in Chapter 6.
3. It becomes very difficult to locate a programming error because results are
typically not deterministic and reproducible (e.g., see [LEBL87, CARR89,
SHEN02] for a discussion of this point).
All of the foregoing difficulties present themselves in a multiprocessor system
as well, because here too the relative speed of execution of processes is unpre-
dictable. A multiprocessor system must also deal with problems arising from the si-
multaneous execution of multiple processes. Fundamentally, however, the problems
are the same as those for uniprocessor systems. This should become clear as the dis-
cussion proceeds.
A Simple Example
Consider the following procedure:
void echo()
{
chin = getchar();
chout = chin;
putchar(chout);
}
This procedure shows the essential elements of a program that will provide a char-
acter echo procedure; input is obtained from a keyboard one keystroke at a time.
Each input character is stored in variable chin. It is then transferred to variable
chout and sent to the display. Any program can call this procedure repeatedly to
accept user input and display it on the user’s screen.
Now consider that we have a single-processor multiprogramming system sup-
porting a single user. The user can jump from one application to another, and each
application uses the same keyboard for input and the same screen for output. Be-
cause each application needs to use the procedure echo, it makes sense for it to be
a shared procedure that is loaded into a portion of memory global to all applica-
tions. Thus, only a single copy of the echo procedure is used, saving space.
The sharing of main memory among processes is useful to permit efficient and
close interaction among processes. However, such sharing can lead to problems.
Consider the following sequence:
1. Process P1 invokes the echo procedure and is interrupted immediately after
getchar returns its value and stores it in chin. At this point, the most re-
cently entered character, x, is stored in variable chin.
2. Process P2 is activated and invokes the echo procedure, which runs to conclu-
sion, inputting and then displaying a single character, y, on the screen.
M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 PM Page 208
5.1 / PRINCIPLES OF CONCURRENCY 209
3. Process P1 is resumed. By this time, the value x has been overwritten in chin
and therefore lost. Instead, chin contains y, which is transferred to chout
and displayed.
Thus, the first character is lost and the second character is displayed twice.The
essence of this problem is the shared global variable, chin. Multiple processes have
access to this variable. If one process updates the global variable and then is inter-
rupted, another process may alter the variable before the first process can use its
value. Suppose, however, that we permit only one process at a time to be in that pro-
cedure.Then the foregoing sequence would result in the following:
1. Process P1 invokes the echo procedure and is interrupted immediately after
the conclusion of the input function. At this point, the most recently entered
character, x, is stored in variable chin.
2. Process P2 is activated and invokes the echo procedure. However, because P1 is
still inside the echo procedure,although currently suspended,P2 is blocked from
entering the procedure. Therefore, P2 is suspended awaiting the availability of
the echo procedure.
3. At some later time, process P1 is resumed and completes execution of echo.The
proper character, x, is displayed.
4. When P1 exits echo, this removes the block on P2. When P2 is later resumed,
the echo procedure is successfully invoked.
This example shows that it is necessary to protect shared global variables (and
other shared global resources) and that the only way to do that is to control the code
that accesses the variable. If we impose the discipline that only one process at a time
may enter echo and that once in echo the procedure must run to completion be-
fore it is available for another process, then the type of error just discussed will not
occur. How that discipline may be imposed is a major topic of this chapter.
This problem was stated with the assumption that there was a single-processor,
multiprogramming OS.The example demonstrates that the problems of concurrency
occur even when there is a single processor. In a multiprocessor system, the same
problems of protected shared resources arise, and the same solution works. First,sup-
pose that there is no mechanism for controlling access to the shared global variable:
1. Processes P1 and P2 are both executing, each on a separate processor. Both
processes invoke the echo procedure.
2. The following events occur; events on the same line take place in parallel:
Process P1 Process P2
••
chin = getchar(); •
• chin = getchar();
chout = chin; chout = chin;
putchar(chout); •
• putchar(chout);
••
M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 PM Page 209
