Unit 3

Process Synchronization: Background - The Critical Section problem - Peterson’s solution -

Synchronization hardware - Mutex Locks - Semaphores - Classic problems of synchronization –
Monitors, Deadlocks: System model - Deadlock characterization - Methods for handling
deadlocks: Deadlock prevention, Deadlock avoidance, Deadlock detection, Recovery from
deadlock.
Process Synchronization: Background
• Processes can execute concurrently or in parallel.
• Concurrent or parallel execution can contribute to issues
involving the integrity of data shared by several processes.
• Maintaining data consistency requires mechanisms to ensure
the orderly execution of cooperating processes.
• A situation where several processes access and manipulate the
same data concurrently and the outcome of the execution
depends on the order in which the access takes place, is called a
race condition.
 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!
The Critical-Section Problem
• Consider system of n processes {p0, p1, … pn-1}
• Each process has critical section segment of code
• Process may be changing common variables, updating table, writing file,
etc.
• When one process 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
General structure of process Pi
• The critical-section problem is to design a protocol that the processes can
use to cooperate
Requirements 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 indefinitely
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
• Assume that each process executes at a nonzero speed
• No assumption concerning relative speed of the n processes
Peterson’s solution
• Classic software-based solution to the critical-section problem known as
Peterson’s solution.
• The solution because it provides a good algorithmic description of solving
the critical-section problem
• Illustrates 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.
• When presenting Pi , we use Pj to denote the other process; that is, j equals
1 − i.
Peterson’s Solution (Cont..)
• Peterson’s solution requires the two processes to share two data
items:
int turn;
boolean flag[2];
• The variable turn tindicates whose turn it is to enter its critical
section. If turn = i, then process Pi is allowed to execute in its
critical section.
• flag array is used to indicate if a process is ready to enter its
critical section. If flag[i] is true, this value indicates that Pi is
ready to enter its critical section.
Structure of Processes in Peterson’s Solution
Proving Peterson’s Solution is correct
1. Mutual exclusion is preserved.
• Pi enters its critical section only if either flag[j] = false or turn = i. If both processes
can be executing in their critical sections at the same time, then flag[0] = flag[1] =
true which is not possible.
2. The progress requirement is satisfied.
3. The bounded-waiting requirement is met.
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).
Synchronization hardware
• The critical-section problem addressed using techniques ranging from
hardware to software-based APIs available to both kernel developers and
application programmers.
• All these solutions are based on the premise of locking —that is, protecting
critical regions through the use of locks.
• Special hardware instructions that allow us to either test-and-modify the
content of a word, or to swap the contents of two words atomically
(uninterruptedly.)
• Test-and-Set instruction
• Compare-and-Swap instruction
 test_and_set() instruction
Executed Atomically - that is, as one uninterruptible Unit.
compare and swap Executed Atomically - that is, as one uninterruptible
Unit.
Solving Bounded Waiting
Mutual Exclusion and Progress
boolean waiting[n];
boolean lock;These 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.
• To prove that the progress requirement is met, a process exiting the critical
section either sets lock to false or sets waiting[j] to false.
Bounded Waiting - Proof
• To prove that the bounded-waiting requirement ismet,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.
Mutex Locks
• The simplest of these tools is the mutex lock. (In fact, the term mutex is short
for mutual exclusion.) We use the mutex lock to protect critical regions and
thus prevent race conditions.
• 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.
• A mutex lock has a boolean variable available whose value indicates if the
lock is available or not.
Solution to the critical-section problem using
mutex locks
Spinlock
• The main 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().
• In fact, this type of mutex lock is also called a spinlock because the process
“spins” while waiting for the lock to become available.
• 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.
• Thus, when locks are expected to be held for short times, spinlocks are
useful.
Semaphores
Semaphore Definition
• All modifications to the integer value of the semaphore in the wait() and signal() operations
must be executed indivisibly.
• That is, when one process modifies the semaphore value, no other process can simultaneously
modify that same semaphore value

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.
Semaphore Usage
• 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.
• 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
• When a process releases a resource, it performs a signal() operation
To solve
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.

Solution : 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

Process P1
S1;
signal(synch);

Process P2
wait (synch);
S2;
Semaphore Implementation to prevent busy
waiting
• 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 block itself.
• The block operation places a process into a waiting queue associated with the
semaphore, and the state of the process is switched to the waiting state;
• A process that is blocked, 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
from the waiting state to the ready state.
Semaphore Definition of wait and signal

The wakeup(P) operation resumes the execution of a blocked process P

Semaphore Implementation (Cont..)
• The block() operation and wakeup(P) are provided by the operating
system as basic system calls.
• We have moved busy waiting from the entry section to the critical sections
of application programs.
• Have not completely eliminated busy waiting with this definition of the
wait() and signal() operations.
Deadlock and starvation
• The implementation of a semaphore with a waiting queue may result in a situation where two or
more processes are waiting indefinitely for an event that can be caused only by one of the waiting
processes.

When P0
executes wait(Q),
P1 executes it must wait until
wait(S), it P1 executes
must wait signal(Q).
until P0
executes
signal(S).

Since these signal() operations cannot be executed, P0 and P1 are deadlocked.

Priority Inversion
• Three processes—L, M, and H—whose priorities follow the order L < M <
H. Assume that process H requires resource R, which is currently being
accessed by process L. M becomes runnable, thereby preempting process
L. lower priority process M has affected how long process H must wait for
L to relinquish resource R.

• Solution:
All processes that are accessing resources needed by a higher-priority
process inherit the higher priority until they are finished with the resources.
When they are finished, their priorities revert to their original values.
Classic problems of synchronization
• Producer Consumer Problem
• The Readers–Writers Problem
• Dining Philosopher Problem
Producer Consumer Problem

We can interpret this code as the producer producing full buffers for the consumer or as the consumer
producing empty buffers for the producer.
The Readers–Writers Problem
• Suppose that a database is to be shared among several concurrent
processes.
• Some of these processes may want only to read the database,
whereas others may want to update (that is, to read and write) the
database.
• We distinguish between these two types of processes by referring
to the former as readers and to the latter as writers.
• The writers should have exclusive access to the shared database
while writing to the database.
Readers and Writers
• first readers–writers problem, requires that no reader be kept waiting
unless a writer has already obtained permission to use the shared object.
no reader should wait for other readers to finish simply because a writer is
waiting
• Second once a writer is ready, that writer perform its write as soon as
possible. In other words, if a writer is waiting to access the object, no new
readers may start reading.
Solution to Readers and Writers Problem

rw_mutex is common to both reader and writer

 Dining Philosoper’s Problem
• Consider five philosophers who spend their lives
thinking and eating
• When a hungry philosopher has both her chopsticks at
the same time, she eats without releasing the
chopsticks.
• A philosopher may pick up only one chopstick at a
time.
• From time to time, a philosopher gets hungry and tries
to pick up the two chopsticks that are closest to them.
• It is a simple representation of the needto allocate
several resources among several processes in a
deadlock-free and starvation-free manner.
 Solution by Semaphore
• One simple solution is to represent each chopstick with a semaphore.
• A philosopher tries to grab a chopstick by executing a wait() operation on that semaphore.
• She releases her chopsticks by executing the signal() operation on the appropriate semaphores.
semaphore chopstick[5];
Remedies to Deadlock

1. Allow at most four philosophers to be sitting simultaneously at the table.

2. Allow a philosopher to pick up her chopsticks only if both chopsticks are
available (to do this, she must pick them up in a critical section).
3. Use an asymmetric solution—that is, an odd-numbered philosopher picks
up first her left chopstick and then her right chopstick, whereas an even
numbered philosopher picks up her right chopstick and then her left
chopstick.
 Monitors
• Researchers have developed high-level
language constructs. In this section, we
describe one fundamental high-level
synchronization construct—the monitor type.

• Monitor type is an ADT that includes a set of

programmer defined operations that are
provided with mutual exclusion within the
monitor.

• Function defined within a monitor can access

only those variables declared locally within the
monitor.
• The monitor construct ensures that only one
process at a time is active within the monitor.

• Programmer does not need to code this

synchronization constraint explicitly.
Monitors (Cont..)
• Programmer who needs to write a tailor-made synchronization scheme
can define one or more variables of type condition: condition x, y;
• The only operations that can be invoked on a condition variable are wait()
and signal().
• The process invoking x.wait() operation is suspended until another
process invokes x.signal(); The x.signal() operation resumes exactly one
suspended process.
• If no process is suspended, then the signal() operation has no effect; that is,
the state of x is the same as if the operation had never been executed
whereas signal() operation associated with semaphores, which always
affects the state of the semaphore
 Monitors (Cont..)
• When the x.signal() operation is invoked by a process P, there exists a
suspended process Q associated with condition x.
Adopting methods in monitor
• P was already executing in the monitor, the signal-and continue method
seems more reasonable.
• On the other, if we allow thread P to continue, then by the time Q is
resumed, the logical condition for which Q was waiting may no longer
hold.
Solution :
• When thread P executes the signal operation, it immediately leaves the
monitor. Hence, Q is immediately resumed.
Dining-Philosophers Solution Using Monitors
• This solution imposes the restriction that a philosopher may pick up her
chopsticks only if both chopsticks are available.

Condition to delay when philosopher is hungry but unable to get the chopsticks
Deadlock
• A process requests resources; if the resources are not available at that time,
the process enters a waiting state.
• Sometimes, a waiting process is never again able to change state, because
the resources it has requested are held by other waiting processes. This
situation is called a deadlock.
Deadlock – No progress
System Model
Under the normal mode of operation, a process may utilize a resource in
only the following sequence:
1. Request. The process requests the resource. If the request cannot be
granted immediately (for example, if the resource is being used by
another process), then the requesting process must wait until it can
acquire the resource.
2. Use. The process can operate on the resource (for example, if the resource
is a printer, the process can print on the printer).
3. Release. The process releases the resource.
Necessary Conditions for Deadlock

All four conditions must hold for a deadlock to occur.

Mutual Exclusion - Non Sharing Resource

When Resources are

shareable – no deadlock
2. No Preemption
Preemption
Resource Allocation Graph (RAG)
• Deadlocks can be described more precisely in terms of a directed
graph called a system resource-allocation graph.
• This graph consists of a set of vertices V and a set of edges E.
• The set of vertices V is partitioned into two different types of nodes:
P = { P1, P2, ..., Pn }the set consisting of all the active processes in
the system, and R ={ R1, R2, ..., Rm} the set consisting of all resource
types in the system
Resource Allocation Graph
• A directed edge from process Pi to resource type Rj is denoted by Pi → Rj ;
it signifies that process Pi has requested an instance of resource type Rj and
is currently waiting for that resource.
• A directed edge from resource type Rj to process Pi is denoted by Rj → Pi; it
signifies that an instance of resource type Rj has been allocated to process
Pi .

Rj Pi

Request Edge
Assignment Edge

Pi Rj
 A simple RAG
The sets P, R, and E:
P = { P1, P2, P3 }
R = {R1, R2, R3, R4 }
E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3 }
• Resource instances:
✓ One instance of resource type R1
✓ Two instances of resource type R2
✓ One instance of resource type R3
✓ Three instances of resource type R4
• Process states:
✓ Process P1 is holding an instance of resource type R2 and is
waiting for an instance of resource type R1.
✓ Process P2 is holding an instance of R1 and an instance of R2
and is waiting for an instance of R3.
✓ Process P3 is holding an instance of R3.
Conditions for Deadlock
• Given the definition of a resource-allocation graph, it can be shown that, if the
graph contains no cycles, then no process in the system is deadlocked.
• If the graph does contain a cycle, then a deadlock may exist.
• If each resource type has exactly one instance, then a cycle implies that a
deadlock has occurred.
• If the cycle involves only a set of resource types, each of which has only a single
instance, then a deadlock has occurred. Each process involved in the cycle is
deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient
condition for the existence of deadlock.
• If each resource type has several instances, then a cycle does not necessarily
imply that a deadlock has occurred. In this case, a cycle in the graph is a
necessary but not a sufficient condition for the existence of deadlock.
 RAG cyclic with deadlock
Two minimal cycles exist in this RAG

• Processes P1, P2, and P3 are deadlocked.

• Process P2 is waiting for the resource R3, which is held by
process P3.
• Process P3 is waiting for either process P1 or process P2 to
release resource R2.
• Process P1 is waiting for process P2 to release resource R1.
 RAG cyclic without Deadlock
• Process P4 may release its instance of resource
type R2. Then resource can be allocated to P3,
breaking the cycle.
• In summary, if a resource-allocation graph
does not have a cycle, then the system is not
in a deadlocked state.
• If there is a cycle, then the system may or
may not be in a deadlocked state. This
observation is important when we deal with
the deadlock problem.
Methods for Handling Deadlocks
1. We can use a protocol to prevent or avoid deadlocks, ensuring
that the system will never enter a deadlocked state.
2. We can allow the system to enter a deadlocked state, detect it,
and recover.
3. We can ignore the problem altogether and pretend that deadlocks
never occur in the system.
Deadlock Prevention
Deadlock prevention provides a set of methods to ensure that at least one of
the necessary conditions for deadlock cannot hold.
1.Mutual Exclusion
• Sharable resources, do not require mutually exclusive access and thus cannot
be involved in a deadlock. Only non-sharable resources require mutual
exclusion.
• Read-only files are a good example of a sharable resource.
• If several processes attempt to open a read-only file at the same time, they can
be granted simultaneous access to the file.
• We cannot prevent deadlocks by denying the mutual-exclusion condition,
because some resources like mutex are intrinsically nonsharable.
2. No Preemption
Resource Preempted for process which cannot be instantly
allocated
• If a process is holding some resources and requests another resource that
cannot be immediately allocated to it (that is, the process must wait), then
all resources the process is currently holding are preempted.
• The preempted resources are added to the list of resources for which the
process is waiting.
• The process will be restarted only when it can regain its old resources, as
well as the new ones that it is requesting.
 No Preemption(Cont..)
Allocate to requesting process from waiting process
• If a process requests some resources, we first check whether they are available.
• If they are, we allocate them. If they are not, we check whether they are allocated
to some other process that is waiting for additional resources.
• Preempt the desired resources from the waiting process and allocate them to
the requesting process.
• If the resources are neither available nor held by a waiting process, the
requesting process must wait.
• A process can be restarted only when it is allocated the new resources it is
requesting and recovers any resources that were preempted while it was
waiting.
3. Hold and Wait
I. Allocate all the resources to the process before it begins
execution.

II. A process may request some resources and use them. Before it
can request any additional resources, it must release all the
resources that it is currently allocated.
Problem with first protocol
We consider a process that copies data from pen drive to a file on disk, sorts
the file, and then prints the results to a printer

• If all resources must be requested at the beginning of the process, then the
process must initially request the pen drive, disk file, and printer. It will
hold the printer for its entire execution, even though it needs the printer
only at the end.
• Problem is resource utilization may be low, since resources may be
allocated but unused for a long period.
Problem with second protocol
The second protocol allows the process to request initially only the pen
drive and disk file.

• Process copies from the pen drive to the disk and then releases both the
pen drive and the disk file. The process must then request the disk file and
the printer.
• After copying the disk file to the printer, it releases these two resources
and terminates.
• Problem is starvation is possible. A process that needs several popular
resources may have to wait indefinitely, because at least one of the
resources that it needs will be always allocated to some other process.
4. Circular Wait
• One way to ensure that this condition never holds is to impose a total
ordering of all resource types and to require that each process requests
resources in an increasing order of enumeration.
• Process can initially request any number of instances of a resource type
say, Ri. After that, the process can request instances of resource type Rj if
and only if F(Rj ) > F(Ri ).
• Then process requesting an instance of resource type Rj must have
released any resources Ri such that F(Ri ) ≥ F(Rj ).
• If several instances of the same resource type are needed, a single request
for all of them must be issued.
• If these two protocols are used, then the circular-wait condition cannot
hold.
Deadlock Avoidance
• Possible side effects of preventing deadlocks by this method, however, are
low device utilization and reduced system throughput.
• An alternative method for avoiding deadlocks is to require additional
information about how resources are to be requested.
• A deadlock-avoidance algorithm dynamically examines the resource-
allocation state to ensure that a circular-wait condition can never exist.
• The resource allocation state is defined by the number of available and
allocated resources and the maximum demands of the processes.
Safe , Unsafe states
• A state is safe if the system can allocate resources to each process (up to its
maximum) in some order and still avoid a deadlock. More formally, a
system is in a safe state only if there exists a safe sequence.
• When Pi terminates, Pi+1 can obtain its needed resources, and so on. If no
such sequence exists, then the system state is said to be unsafe.
Banker’s Algorithm
• Deadlock avoidance Algorithm
• The name was chosen because the algorithm could be used in a
banking system to ensure that the bank never allocated its available
cash in such a way that it could no longer satisfy the needs of all its
customers.
• When a new process enters the system, it must declare the maximum
number of instances of each resource type that it may need.
• This number may not exceed the total number of resources in the
system.
• When a user requests a set of resources, the system must determine
whether the allocation of these resources will leave the system in a
safe state.
Data Structures in Banker’s Algorithm
 Deadlock Detection
• If a system does not employ either a deadlock-prevention or a deadlock
avoidance algorithm, then a deadlock situation may occur.
In this environment, the system may provide:
1. An algorithm that examines the state of the system to determine whether a deadlock
has occurred
2. An algorithm to recover from the deadlock
Deadlock Detection – Wait for Graph
• We obtain this graph from the resource-allocation graph by removing the
resource nodes and collapsing the appropriate edges.
• An edge Pi → Pj exists in a wait-for graph if and only if the RAG contains
two edges Pi → Rq and Rq → Pj for some resource Rq
Wait for Graph
• A deadlock exists in the system if and only if the wait-for graph
contains a cycle.
• To detect deadlocks, the system needs to maintain the wait for
graph and periodically invoke an algorithm that searches for a
cycle in the graph.
• Can be used for resources have only a single instance.
Recovery from Deadlock
Process Termination
Resource Preemption

These are the factors to be considered for recovery of deadlock

through resource preemption
1. Selection of Victim to be preempted
2. Rollback
3. Starvation
Selection of Victim
Rollback
Starvation