Process Synchronization

In Today's
Lecture
• Background
• Producer-Consumer
Problem
• Race Condition
• Critical Section Problem
• Solution
Background
• Independent Vs Cooperating Process
o Produces-consumer problem
• Can Share:
o Logical Address Space (Code + Data)
o Data directly through Files or messages
 One solution is shared memory

Buffer

Producer- • Bounded
• Unbounded

Consumer Must be synchronized

Problem Consumer doesn't try to consume unless one is

produced

Counter variable=0

• Counter++
• Counter--
Example

Counter current value=5

Produces -> counter++ and consumer -> counter- - concurrently

Three possibilities:
• 4, 5, 6

Correct result is counter==5

• if execute separately
How actually counter++/-- works
• Machine language
Register1 = counter Register2 = counter
Register1 = register1 + 1 Register2 = register2 - 1
Counter = register1 Counter = register2

T0 Producer execute Register1 = counter Register1 =5

T1 Producer execute Register1 = register1 + 1 Register1 = 6
T2 Consumer execute Register2 = counter Register2 = 5
T3 Consumer execute Register2 = register2 - 1 Register2 = 4
T4 Producer execute Counter = register1 Counter = 6
T5 Consumer execute Counter = register2 Counter = 4
Race Condition

• 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
take place, is called race condition.
The Critical Section

• Critical Section vs Critical Section Problem Consider a system consisting of

processess(P0,P1,…...,Pn)
• Each Process has a segment called:
• Critical Section
o In which the process may be changing common variables, updating a table, writing a
file and so on.
Rule:
o When one process is executing in its critical section, no other process is to be
allowed to execute in its critical section.
 • The critical section problem is used:
o To design a set of protocols which can ensure
The Critical that the Race condition among the processes
Section will never arise.
o To design a protocol that the processes can
Problem use to cooperate
Requirements of
Synchronization mechanisms
• Rules
o Each Process must request
permission to enter its critical
section
o The section of code implementing
this request is the entry
section
The critical section may be followed
by an exit section
o The remaining code is the remainder
section
 Primary
• Mutual Exclusion
• If one process is executing inside critical section then the
other process must not enter in the critical section.
• Progress
• If one process doesn't need to execute into critical section
Requirements of then it should not stop other processes to get into the
critical section (
Synchronization
mechanisms Secondary
• Bounded Waiting
• Predict the waiting time for every process to get into the
critical section. The process must not be endlessly waiting
for getting into the critical section
• Architectural Neutrality
• If our solution is working fine on one architecture then it
should also run on the other ones
 The solution to the critical section problem must satisfy the
following conditions:

Mutual Exclusion

• If process Pi is executing in its critical section, then no other processes

Solution to can be executing in their critical sections

Progress
Critical-Section
Problem • If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then only those
process that are not executing their remainder section can participate
in the decision on which will enter its critical section next.

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.
Peterson’s Solution
• Humble Algorithm
• Software Based Solution
• May not work correctly on modern computer architecture
• Restricted to two process
• Requires two data items to be shared b/w two processes
o Flag
o Turn Used to indicate if a Boolean flag[2]
process is ready to enter its
Int turn critical section

Indicates whose turn it is

To enter its critical section
Learn With Ijaz
 There are three algorithms in the hardware
Hardware approach of solving Process Synchronization
problem:
Based 1. Test and Set
Solution 2. Swap
3. Unlock and Lock
Test and Set Lock
• Hardware Based Solution
Bounded waiting is not ensured
• Shared lock variable
o 0 =Unlock
o 1= Lock
• Initially:
o False/Unlock
• Always returns whatever value is sent to it and sets lock to true
• Before entering into critical section, a process inquires about the lock
• If lock
o Keeps waiting till it becomes free
• If not locked
o It takes lock and execute the critical
section
Learn With Ijaz
Semaphores
• Proposed By Edsger Dijkstra
• Signaling Mechanism Wait() P – Proberen "To Test"
• Simple Integer Variable Signal() V – Verhogen "To Increment"
o Non-negative
o Shared between threads
• Two atomic operations
o Wait
▪ decrements the value of its argument S
o Signal
▪ increments the value of its argument S
 Binary • Value Between 0 and 1
Semaphore • Also known as Mutex Lock

Conting • Value in unrestricted domain

Semaphore • Resources that has multiple instances
A Tricky MCQ asked in PPSC Screening Test

Initial Value of Binary Semaphore is 1 (PPSC Mcq)

Really?

If the semaphore is initialized with 1

• Then the first completed operation must be P

If the semaphore is initialized with 0

• Then the first completed operation must be V
 • Priority Inversion
o L<H
o L<M<H (M is not sharing CS of L and
H)
Priority • Priority Inheritance
Inversion
 • What are SpinLocks?

Assignment
 • Classical problems used to test newly-
Classical proposed synchronization schemes
1. Bounded-Buffer Problem
Problems of 2.Readers and Writers Problem
Synchronization 3.Dining-Philosophers Problem
 • Two processes
o The producer
▪ generate data, put it into the buffer
o The consumer
Bounded- ▪ consuming the data (removing it from the buffer)
• Share a common, fixed-size buffer used as a
Buffer queue
Problem • The problem
o The producer won't try to add data into the
buffer if it's full and consumer won't try to
remove data from an empty buffer.
The Solution

The next time the consumer

The producer is to either go to
removes an item from the buffer,
sleep or discard data if the buffer
it notifies the producer, who
is full.
starts to fill the buffer again.

The next time the producer puts

The consumer can go to sleep if it
data into the buffer, it wakes up
finds the buffer to be empty.
the sleeping consumer.

The solution can be reached by means of inter-

process communication, typically using semaphores.
Readers-Writers Problem

who only read the shared data, and never

Reader change it

who may change the data in addition to or

Writer instead of reading it.

There is no limit to how many readers can access the data simultaneously,
but when a writer accesses the data, it needs exclusive access.
Several variations

• Centered around relative priorities of readers versus writers

The first readers-writers problem

• Gives priority to readers.

• If a reader wants access to the data, and there is not already a
writer accessing it, then access is granted to the reader.
• A solution to this problem can lead to starvation of the writers,
as there could always be more readers coming along to access
the data.

The second readers-writers problem

• Gives priority to the writers.

• When a writer wants access to the data it jumps to the head of
the queue - All waiting readers are blocked, and the writer gets
access to the data as soon as it becomes available.
• In this solution the readers may be starved by a steady stream
of writers.
The Dining-Philosophers Problem
• Allocation of limited resources amongst a group of
processes in a deadlock-free and starvation-free manner
• Consider five philosophers sitting around a table, in
which there are five chopsticks evenly distributed and an
endless bowl of rice in the center, as shown in the
diagram
• There is exactly one chopstick between each pair of
dining philosophers
• These philosophers spend their lives alternating between
two activities: eating and thinking.
• When it is time for a philosopher to eat, it must first
acquire two chopsticks - one from their left and one from
their right.
• When a philosopher thinks, it puts down both chopsticks
in their original locations.
 Each fork can be held by only one philosopher and so a
philosopher can use the fork only if it is not being used
by another philosopher

The After an individual philosopher finishes eating, they

need to put down both forks so that the forks become

Problem available to others

How to design a discipline of behavior (a concurrent

algorithm) such that no philosopher will starve; i.e.,
each can forever continue to alternate between eating
and thinking, assuming that no philosopher can know
when others may want to eat or think