Module-3:

Operating Systems
BACSE106

LECTURE 2:
Process Synchronization-Race Condition, Critical Section Problem-Peterson’s
Solution

Course Instructor:-
Dr. [Link],
Professor,
SCOPE, VIT, Vellore.
Syllabus
Module:3 Process Synchronization 9 hours

IPC: Shared memory, message passing - Race condition – Critical

section problem - Peterson's solution – Bakery Algorithm - Hardware
synchronization: Test-and-Set, Swap - Mutex locks - Semaphores –
Classical synchronization problems: Bounded buffer, Readers-Writers,
Dining Philosophers – Monitors.
Introduction to Process Synchronization
• 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 files
or messages
• The former case is achieved through the use of threads, discussed
Background
• We’ve already seen that processes can execute concurrently or in parallel.
• This means that one process may only partially complete execution before
another process is scheduled
• In fact, a process may be interrupted at any point in its instruction stream,
and the processing core may be assigned to execute instructions of another
process
Bounded buffer
• 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 counter, initialized to 0
• counter 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:
• The code for the consumer process can be modified as follows:

• Although the producer and consumer routines shown above are

correct separately, they may not function correctly when executed
concurrently
• Suppose that the value of the variable counter is currently 5 and that
the producer and consumer processes concurrently execute the
statements “counter++” and “counter--”
• Following the execution of these two statements, the value of the
variable counter may be 4, 5, or 6!
• The only correct result, though, is counter == 5, which is generated
correctly if the producer and consumer execute separately
• We can show that the value of counter may be incorrect as follows
• Note that the statement “counter++” may be implemented in
machine language (on a typical machine) as follows:
• where again register2 is one of the local CPU registers
• Even though register1 and register2 may be the same physical register
(an accumulator, say), remember that the contents of this register will
be saved and restored by the interrupt handler
• The concurrent execution of “counter++” and “counter--” is
equivalent to a sequential execution in which 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:
• Notice that we have arrived at the incorrect state “counter == 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 “counter == 6”
• We would arrive at this incorrect state because we allowed both
processes to manipulate the variable counter 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 counter
• 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 growing
importance 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
 The Critical-Section Problem
• We begin our consideration of process synchronization by
discussing the so called 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 changing common variables, updating a
table, writing a file, and so on
• 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 cooperate
• Each process must request permission to enter its critical section
• The section of code implementing this request is the entry section
• The critical section may be followed by an exit section
Critical section problem
• Entry section: Controls entry into critical
section and gets lock on required
resources. Here the process sends a
request to operating system to access the
critical section.
• Critical section: It contains the variables or
files which are globally accessible by all
the processes.
• Exit section: It contains the flag variable
which is enabled by the process after
accessing critical section. This flag reflects
in all other processes.
• Remainder section: It is individual code
and different for all processes.
• The remaining code is the remainder section. The general structure of a
typical process Pi is shown in Figure
• 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
Peterson’s 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:
• 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, this value indicates that Pi is ready to enter
its critical section
• 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).