Chapter 6: Synchronization
Tools
Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018
Outline
▪ Background
▪ The Critical-Section Problem
▪ Peterson’s Solution
▪ Hardware Support for Synchronization
▪ Mutex Locks
▪ Semaphores
▪ Evaluation
Operating System Concepts – 10th Edition 6.2 Silberschatz, Galvin and Gagne ©2018
Objectives
▪ Describe the critical-section problem and illustrate a race
condition
▪ Illustrate hardware solutions to the critical-section problem
using memory barriers, compare-and-swap operations, and
atomic variables
▪ Demonstrate how mutex locks and semaphores can be used
to solve the critical section problem
▪ Evaluate tools that solve the critical-section problem in Low-,
Moderate-, and high-contention scenarios
Operating System Concepts – 10th Edition 6.3 Silberschatz, Galvin and Gagne ©2018
Background
▪ Interaction can occur through shared data (e.g., threads) or
shared files
▪ Cooperating processes allow information sharing,
computational speedup, modularity, and convenience
▪ Processes can execute concurrently
▪ Concurrent access to shared data may result in data
inconsistency
▪ Maintaining data consistency requires mechanisms to ensure
the orderly execution of cooperating processes
▪ We illustrated in chapter 4 the problem when we considered
the Bounded Buffer problem with use of a counter that is
updated concurrently by the producer and consumer. Which
lead to race condition.
Operating System Concepts – 10th Edition 6.4 Silberschatz, Galvin and Gagne ©2018
Review: Producer-Consumer Problem
▪ The producer-consumer problem is a synchronization problem. There
is a fixed size buffer and the producer produces items and enters them
into the buffer. The consumer removes the items from the buffer and
consumes them. List three examples of deadlocks that are not related to a computersystem environment
▪ A producer should not produce items into the buffer when the
consumer is consuming an item from the buffer and vice versa. So, the
buffer should only be accessed by the producer or consumer at a time.
▪ Now, let us discuss producer-consumer process problems.
Operating System Concepts – 10th Edition 6.5 Silberschatz, Galvin and Gagne ©2018
Review: Producer-Consumer Problem
▪ Step 1 − A producer process produces information that is consumed
by the consumer process. For example, a compiler that produces
assembly code is consumed by an assembler. The assembler can
produce object modules which are consumed by the loader.
▪ Step 2 − It uses the shared memory concept.
▪ Step 3 − If we want to allow producer and consumer processes to run
concurrently, we have to provide a buffer of items which can be filled
by producer and empty the buffer by consumer.
▪ Step 4 − This buffer will reside in a region of memory which is shared
by producer and consumer process.
▪ Step 5 − A producer can produce one item while the consumer is
consuming another item.
▪ Step 6 − The producer and consumer must be synchronised, so that
the consumer does not try to consume an item which is not yet
produced.
Operating System Concepts – 10th Edition 6.6 Silberschatz, Galvin and Gagne ©2018
Race Condition
▪ Processes P0 and P1 are creating child processes using the fork()
system call
▪ Race condition on kernel variable next_available_pid which
represents the next available process identifier (pid)
▪ Unless there is a mechanism to prevent P0 and P1 from accessing the
variable next_available_pid the same pid could be assigned to
two different processes!
Operating System Concepts – 10th Edition 6.7 Silberschatz, Galvin and Gagne ©2018
Critical Section Problem
▪ Consider system of n processes {p0, p1, …
pn-1}
▪ Each process has a critical section segment
of code General structure of
• Process may be changing common process Pi
variables, updating tables, writing file, etc.
• When one process is in critical section,
no other may be in its critical section
▪ Critical section problem is to design
protocol to solve this
▪ Each process must ask permission to enter
critical section in entry section, may follow
critical section with exit section, then
remainder section
Operating System Concepts – 10th Edition 6.8 Silberschatz, Galvin and Gagne ©2018
Critical-Section Problem (Cont.)
Requirements for solution to critical-section problem
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 there exist some processes that wish to enter their
critical section, then the selection of the process that will
enter the critical section next cannot be postponed forever
3. Bounded Waiting - A bound must exist 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
Operating System Concepts – 10th Edition 6.9 Silberschatz, Galvin and Gagne ©2018
Software Solution 1
▪ Two process solution
▪ Assume that the load and store machine-language
instructions are atomic; that is, cannot be interrupted
▪ The two processes share one variable:
• int turn;
▪ The variable turn indicates whose turn it is to enter the
critical section
Algorithm for Process Pi
▪ Initially turn = 1
Operating System Concepts – 10th Edition 6.10 Silberschatz, Galvin and Gagne ©2018
Correctness of the Software Solution
▪ Mutual exclusion is preserved
Pi enters critical section if and only if:
turn = I
and turn cannot be both 0 and 1 at the same time
▪ What about the Progress requirement?
• If Process 1 wants to enter the critical section and Process 2
is not interested in entering the critical section, can Process 1
enter?
Operating System Concepts – 10th Edition 6.11 Silberschatz, Galvin and Gagne ©2018
Software Solution -- Peterson’s Algorithm
▪ Two process solution
▪ Assume that the load and store machine-
language instructions are atomic; that is, cannot be
interrupted
▪ The two processes share two variables:
• int turn;
• boolean flag[2]
▪ The variable turn indicates whose turn it is to enter
the critical section
▪ The flag array is used to indicate if a process is
ready to enter the critical section.
• flag[i] = true implies that process Pi is
ready!
Operating System Concepts – 10th Edition 6.12 Silberschatz, Galvin and Gagne ©2018
Algorithm for Process Pi
while (true){
flag[i] = true;
turn = j;
while (flag[j] && turn = = j)
;
/* critical section */
flag[i] = false;
/* remainder section */
Operating System Concepts – 10th Edition 6.13 Silberschatz, Galvin and Gagne ©2018
Correctness of Peterson’s Solution
▪ Provable that the three CS requirement are met:
1. Mutual exclusion is preserved
Pi enters CS only if:
either flag[j] = false or turn = i
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met
▪ Solution works for 2 process.
▪ What about modifying it to handle 10 processes?
▪ Solution requires busy waiting
• Processes waste CPU cycles to ask if they can enter the critical
section
Operating System Concepts – 10th Edition 6.14 Silberschatz, Galvin and Gagne ©2018
Synchronization Hardware
▪ Many systems provide hardware support for implementing the critical
section code.
▪ Uniprocessors – could disable interrupts
• Currently running code would execute without preemption
Is this practical?
• Generally, too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
▪ There are three forms of hardware support:
• Memory Barriers
• Hardware instructions
• Atomic Variables
▪ Previous solutions are complicated and generally inaccessible to application
programmers
▪ OS designers build software tools to solve critical section problem
▪ Simplest is mutex lock
Operating System Concepts – 10th Edition 6.15 Silberschatz, Galvin and Gagne ©2018
Semaphore
▪ Synchronization tool that provides more sophisticated ways (than Mutex
locks) for processes to synchronize their activities.
▪ Semaphore S – integer variable
▪ Can only be accessed via two indivisible (atomic) operations
• wait() and signal()
Originally called P() and V()
▪ Definition of the wait() operation
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
▪ Definition of the signal() operation
signal(S) {
S++;
}
Operating System Concepts – 10th Edition 6.16 Silberschatz, Galvin and Gagne ©2018
Semaphore (Cont.)
▪ Counting semaphore – integer value can range over an
unrestricted domain
▪ Binary semaphore – integer value can range only between 0
and 1
• Same as a mutex lock
▪ Can implement a counting semaphore S using binary
semaphores
▪ With semaphores we can solve various synchronization
problems
Operating System Concepts – 10th Edition 6.17 Silberschatz, Galvin and Gagne ©2018
Semaphore Implementation
▪ Must guarantee that no two processes can execute the
wait() and signal() on the same semaphore at
the same time
▪ Can be implemented using any of the critical sections
solutions we discussed where the wait and signal
code are placed in the critical section
▪ Could now have busy waiting in critical section
implementation
• But implementation code is short
• Little busy waiting if critical section rarely occupied
▪ Note that for “regular” applications, where the application
may spend lots of time in critical sections this is not a good
solution
Operating System Concepts – 10th Edition 6.18 Silberschatz, Galvin and Gagne ©2018
Implementation with no Busy waiting
▪ With each semaphore there is an associated waiting queue.
▪ Each entry in a waiting queue has two data items:
• Value (of type integer)
• Pointer to next record in the list
▪ Waiting queue
typedef struct { semaphore is a structure that
contains the int value & a
int value;
queue of waiting processes
struct process *list;
} semaphore; struct Semaphore {
int value;
Queue<PCB> queue;
};
Operating System Concepts – 10th Edition 6.19 Silberschatz, Galvin and Gagne ©2018
Implementation of the wait operation
▪ The wait operation:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}
▪ The sleep() suspends the process that
invoked it.
Operating System Concepts – 10th Edition 6.20 Silberschatz, Galvin and Gagne ©2018
Implementation of the signal operation
▪ The signal operation:
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
▪ The wakeup(P) operation resumes the execution of process P
Operating System Concepts – 10th Edition 6.21 Silberschatz, Galvin and Gagne ©2018
Problems with Semaphores
▪ Incorrect use of semaphore operations:
• signal(mutex) …. wait(mutex)
• wait(mutex) … wait(mutex)
• Omitting of wait(mutex) and/or signal(mutex)
▪ These – and others – are examples of what can occur when
semaphores and other synchronization tools are used
incorrectly.
▪ Solution: introduce high-level programming constructs
Operating System Concepts – 10th Edition 6.22 Silberschatz, Galvin and Gagne ©2018
Deadlock
▪ Deadlock – two or more processes are waiting indefinitely for an event
that can be caused by only one of the waiting processes
▪ Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);
▪ Consider if P0 executes wait(S) and P1 wait(Q). When P0 executes
wait(Q), it must wait until P1 executes signal(Q)
▪ However, P1 is waiting until P0 execute signal(S).
▪ Since these signal() operations will never be executed, P0 and P1 are
deadlocked.
Operating System Concepts – 10th Edition 6.23 Silberschatz, Galvin and Gagne ©2018
Other Forms of Deadlock
▪ Starvation – indefinite blocking
• A process may never be removed from the semaphore queue in
which it is suspended
▪ Priority Inversion – Scheduling problem when lower-priority process
holds a lock needed by higher-priority process
▪ Solved via priority-inheritance protocol
Operating System Concepts – 10th Edition 6.24 Silberschatz, Galvin and Gagne ©2018
End of Chapter 6
Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018