Module 2

Concurrency and Synchronization

Cooperating processes

void main()
T1 B=3*2
{
T1 A IS DEPENDENT ON B

B=3*2
T2 A=B+1
T2
A=B+1

}
THE ORDER OF EXECUTION MATTERS!
Producer Consumer Problem

counter

Producer Consumer

while(true) while(true)
{ {
//produce some data //consume some data
counter++ counter--
} }
How increment and decrements are
implemented

count++ count--
Register1=counter Register2=counter

Register1=Register1+1 Register2=Register2-1

counter=Register1 counter=Register2
 Assume counter=5 now…

Inconsistency : both processes has accessed counter

simultaneously
Race Condition

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
Process Synchronization

Ensure that only one process is allowed to manipulate the

shared data at a time.
The Critical-Section Problem

a system consisting of n processes {P0, P1, ..., Pn−1}

has a segment of code, called a critical section where common

values are changed

when one process is executing in its critical section, no other

process is allowed to execute in its critical section

Each process must request permission to enter its critical

section
D

O
Solutions must satisfy

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.
D

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.

If a process Pi ​requests the critical section, then there

exists a bound on the number of times other processes are
allowed to enter their critical sections before Pi ​is allowed to
enter.
waiting time is
Locks: The Basic Idea

balance = balance + 1; or balance=balance-1

Lock the variable before updating it, and unlock once it is updated
Locks

1. Lock is a variable

2. Lock variable represents the state of the lock at any instant in time

1. Locked/Unlocked

3. exactly one thread can hold the lock at any instant in time
Locking and unlocking

4. Call the routine lock() to acquire a lock

5. If no one holds that lock, the process/thread can enter their CS

6. If any others call the same lock at that time, they will be kept waiting

7. Once the owner of the lock calls unlock()

7.1 if no others waiting, the state of the lock is set to free

7.2 if other processes/threads are waiting, they will be notified

Test and Set Lock (atomic exchange)

[Link]

To attain critical section process access a shared lock

First test the lock to see that it is unlocked

If unlocked , set(aquire) the lock

No one else can access the shared resource when some one has the lock
 P0

P1

Shared resource P2

P4
 P0

P1

Shared resource P2

P4
 Test and Set Instructions

Hardware level single operation that cannot be interrupted

D

O
FALSE
FALSE

FALSE
FALSE

FALSE
FALSE
FALSE

FALSE
FALSE
FALSE

FALSE
FA
L
SE
FALSE
FALSE

FALSE
FA
L
SE
FALSE
FALSE

FALSE
FA
L
SE
FALSE
 T
R
U
E
 E
U
R
T
T
R
U
E
E
 E
U
R
T
T
R
U
E
T
R
U
E
 E
U
R
T
T
R
U
E
T
R
U
E
PERFORMANCE OF SPIN LOCKS

Correctness- spin lock only allows a single thread to enter the critical
section at a time

fairness- unfortunately, spin locks don’t provide any fairness guarantees

PROCESSES MAY SPIN FOREVER

Performance

In single Processor systems- Worst performance

In Multi Processor systems- reasonably well

Compare and Swap

0-> UNLOCKED

1-> LOCKED
0 0 1
0
0==0 TRUE
1
0
D
1
0
0==0 1==0
O 1
P2
P1 0,0,1
1,0,1

1
0
1!=0 TRUE

0!=0 FALSE
Using Queues: Sleeping Instead Of Spinning

Problem with spinning locks

decision on who is next?? No fairness

Solution:

Use a queue to keep track of processes requested for CS in the order they have
requested

threads waiting(spinning ) are put in a queue and allowed to sleep

Park() -> Sleep

Unpark() ->Awake
Thread 1001 acquires the Critical Section (CS).While 1001
is inside CS, thread 1002 arrives and requests the lock.
Step 1: Thread 1001 calls lock(m)

Old value = 0
Guard becomes 1
1001 acquires guard

Since m->flag==0

Set m->flag=1

Final state once lock is acquired Release the guard m->guard-

m->flag=1
m->guard=0 >0
While 1001 is in CS, Thread 1002 calls lock(m)

Acquire the guard

m->guard=1

Test m->flag==0

False

Enqueue the thread 1002

Release the guard

Thread 1001 finishes CS and calls unlock(m)

Acquire the guard

Set m->flag=0

Dequeue the process and deliver the lock

Semaphores

A semaphore is an object with an integer value that we can manipulate

with two routines

sem_wait()

sem_post()
Semaphore Initialization

sem_t s;

sem_init(&s, 0, 1);
Semaphores => initial value of s =1
Types of semaphores

Binary Semaphore

Counting semaphore
Binary Semaphores (Locks)
S=1

sem_wait()

P1
 -1

sem_wait() sem_wait()

P1 P2 Sleep
 0

sem_post()

P1 P2 Wake
Scenario 1-> Only 1 thread accessing the
semaphore
Scenario 2-> Two threads accessing the
semaphore
Counting semaphore

Used for accessing resources that has multiple instances

P0 P1 P2 P4 P5 P6

Multiple instances
S is initialized to the number of resources

S=2
Producer Consumer Problem or Bounder Buffer
Problem

There is a buffer of size n

Each slot is capable of storing 1 unit of data

Two processes producer and consumer

D

Producer should not produce data if the buffer is full

Consumer should not consume data if the buffer is empty

Producer and Consumer should not insert or remove data

simultaneously

[Link]
Solution using semaphores

Three semaphores used

1. mutex(binary semaphore)=>acquire locks

2. Empty(counting semaphore)=> tracks of empty slots in the

buffer=> intial value=number of slots in the buffer

3. Full(counting semaphore)=> tracks of filled slots in the buffer

initial value is 0
Initial mutext = 1 empty=6 full=0
Producer produces some data empty=5 , lock &
put full=1
Producer produces some data empty=4 , lock &
put full=2
Consumer consumes some data empty=5 , lock
& get full=1
Readers-Writers Problem

A database is shared among various concurrent processes

Some process want to read the database and other want to

update

Readers and Writers

Access Scenarions

1. If two readers access the db simultaneously

no problem

2. If one of the process is writer and other is wither

reader/writer creates the synchronization issue

SO WHEN WRITING, A DATABASE SHOULD BE EXCLUSIVE

[Link]
Scenario 1

ATM Counter Phonepe

CheckBalance( Your bank balance CheckBalance()

) $100
Scenario 2

BANK
ATM Counter withdraw()
Your bank balance
Deposit() $100
Solution using semaphores

Two semaphores and one int value

1. Semaphore 1 named as mutex to synchronize readercount

2. Semaphore 2 named as wrt to synchronize readers and

writers

3. Integer variable readercount

 sem_wait(mutex)

sem_wait(wr
sem_wait(wrt) t)
sem_post(mutex)

sem_post(wrt)
sem_wait(mutex)

sem_post(wrt)
sem_post(mutex)
Deadlocks

1. Program → Process

2. Multiple processes exist in memory at the same time.

3. The scheduler selects which process gets the CPU.

1. On a single CPU → concurrency

2. On multiple CPUs → parallelism

4. To achieve better performance, a process is divided into threads.

Deadlocks

5. Threads share: code data & files

6. Shared Data creates Inconsistency

7. To maintain consistency, threads must be synchronized.

Only one thread is allowed inside the critical section.

Others must wait.

Trigger Thinking

1. What if a thread enters the critical section and never releases

the lock?

2. What if a thread holds one lock and waits for another lock
held by someone else?
Each thread holds a resource and waits for another resource
held by another thread

No one can proceed

 THREAD 1

THREAD 2 THREAD 3
Deadlocks

A deadlock in an operating system occurs when two or more

processes get stuck, each waiting for a resource that the other is
holding, preventing further execution. This results in a system
freeze where no process can proceed.

Process 1 ---> Resource A ---> Needs Resource B (Held by P2)

Process 2 ---> Resource B ---> Needs Resource A (Held by P1)
System Model
A process may utilize a resource in only the Release → Printer becomes free

following sequence: Why this order is important

1. Request Prevents resource conflicts

2. Use Helps avoid deadlock

3. Release Enables safe scheduling and sharing

Printer usage:

Request → Process asks for printer

Use → Prints document

Necessary and sufficicent Conditions

Deadlock occurs only if all four conditions hold

simultaneously

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait.
1. Mutual exclusion

At least one resource must be held in a nonsharable mode; that

is, only one process at a time can use the resource.

If another process requests that resource, the requesting

process must be delayed until the resource has been released.

Access one at a time

2. Hold and wait

A process must be holding at least one resource and waiting to

acquire additional resources that are currently being held by
other processes.
3. No preemption

Resources once held by a process is not releasing the same

4 Circular wait

. A set {P0, P1, ..., Pn} of waiting processes must exist such that
P0 is waiting for a resource held by P1, P1 is waiting for a
resource held by P2, ..., Pn−1 is waiting for a resource held by
Pn, and Pn is waiting for a resource held by P0.
Resource-Allocation Graph

Deadlocks can be represented using directed graph called a

system resource-allocation graph

consists of a set of vertices V and a set of edges E.

V represents processes{P1,P2,P3..PN} and resources {R1,R2,..RN}

Where Pi->Ri indicates Pi has requested for the resource Ri

Rj->Pj indicates that Rj is allotted to Pj

 Example
P = {P1, P2, P3}

R = {R1, R2, R3, R4}

◦ E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}

Deadlock detection in allocation graph

If cycle present , there is deadlock, else no dead lock

Methods for Handling Deadlocks
Deadlock Prevention : ensures that deadlock can never occur by
breaking at least one of the four necessary deadlock conditions in
advance.
Simple to implement
Conservative
May cause low resource utilization or starvation

Deadlock Avoidance : Banker’s Algorithm

Deadlock Prevention

Prevent any one of the necessary conditions of dead lock to

prevent the deadlock

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait.
Mutual exclusion

Sharable resources, in contrast, do not require mutually

exclusive access and thus cannot be involved in a deadlock

1. read-only files

2. program code

3. shared libraries

4. read-only database tables

Hold and Wait

1. each process must be allocated all its resources before it

begins execution.

2. 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.
No Preemption

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. In other words, these resources are
implicitly released
No Preemption

if a process requests some resources

1. check whether they are available

1. If not available

1. Check whether they are allocated to some other process that is

waiting for additional resources

1. we preempt the desired resources from the waiting process and

allocate them to the requesting process

2. If the resources are neither available nor held by a waiting

process, the requesting process must wait
Circular Wait

let R = {R1, R2, ..., RN} be the set of resource types

assign to each resource type a unique integer number

F: R → N, where N is the set of natural numbers

F(tape drive) = 1

F(disk drive) = 5

F(printer) = 12
Rule for Requesting Resources

Each process can request resources only in an increasing order

of numbers

a 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)

a process that wants to use the tape drive and printer at the
same time must first request the tape drive and then request
the printer
F(tape drive) = 1 F(disk drive) = 5 F(printer) = 12

If a process needs both tape drive and printer:

Request tape drive (1) then Then request printer (12)

Not allowed - Request printer (12) then Then request tape drive (1)

With strict ordering:

[Link] process can request a lower-numbered resource after holding a

higher-numbered one. Hence, cycles cannot form.
Deadlock Avoidance

Analyze the

Available resources

Allocated resources

Need Resources

Safe state or not

Safe State

if the system can allocate resources to each process in some

order and still avoid a deadlock
Example

Total number of Resource R(Printer)=10

The following processes

Maximum- max resources a process might need

Available resouces =Total-Alloted=10-7=3

Available =3

4
2
3

P2 can complete first because it needs at most (4 - 2) = 2 resources,

which are available.

After P2 completes, it releases its 2 resources.

Available resources = 3 + 2 = 5.
Available =5 P2->

P3 can now complete because it needs at most (5 - 2) = 3, which

are available..

After P3 completes, it releases 2 more resources.

Available resources = 5 + 2 = 7
Available =7 P2->P3

P1 can now complete because it needs at most (7 - 3) = 4, which are

available.

So safe state is the following order P2->P3->P1

Banker's Algorithm

deadlock avoidance algorithm

It ensures that a system never enters an unsafe state by only

granting resource requests if a safe sequence exists.
Key Terms in Banker's Algorithm

Allocated: Number of resources currently allocated to a process.

Maximum Demand: Maximum number of resources a process

may request.

Available: Number of free resources in the system.

Need: Remaining resources required for a process to complete.

Need=Maximum Demand−Allocated
Total resource is 10
Total resource is 10
Consider the following example of a system. Check whether the
system is safe or not using the Bankers Algorithm. Determine its
safe sequence AVAILABLE/
ALLOCATION MAX WORK NEED
PROCES
S A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Step 1 Calculate the need matrix [Max-
Allocation]

ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Step 1 After calculating the need matrix

ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P0
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1

Compare WORK> need of P0 3 3 2 > 7 4 3 True??

Not possible to allocate

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P1
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Compare WORK> need of P1 3 3 2> 1 2 2 True??

possible to allocate

Update WORK to WORK + resources released by P1=> 3 3 2+ 2 0 0

WORK is 5 3 2 Safe Sequence is P1->

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P2
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Compare WORK> need of 5 3 2>6 0 0 True??

Not possible to allocate

WORK is 5 3 2 Safe Sequence is P1->

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P3
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Compare WORK > need of 5 3 2> 0 1 1 True??

possible to allocate

Update WORK to WORK+ resources released by P3=> 5 3 2+ 2 1 1

WORK is 7 4 3 Safe Sequence is P1->P3

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P4
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 7 4 3 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Compare WORK > need of P4 7 4 3> 4 3 1 True??

possible to allocate

Update WORK to WORK+ resources released by P4=> 7 4 3+ 0 0 2

Available is 7 4 5 Safe Sequence is P1->P3->P4

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P0
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 7 4 3 6 0 0
P3 2 1 1 2 2 2 7 4 5 0 1 1
P4 0 0 2 4 3 3 4 3 1
Compare WORK > need of P0 7 4 5> 7 4 3True??

possible to allocate

Update WORK to WORK+ resources released by P0=> 7 4 5+ 0 1 0

WORK is 7 5 5 Safe Sequence is P1->P3->P4->P0

 ALLOCATION MAX WORK NEED
PROCES
A B C A B C A B C A B C
Checking P2
S

P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 7 4 3 6 0 0
P3 2 1 1 2 2 2 7 4 5 0 1 1
P4 0 0 2 4 3 3 7 5 5 4 3 1
Compare WORK> need of P2 7 5 5> 6 0 0True??

possible to allocate

Update WORK to WORK+ resources released by P2=> 7 5 5+ 3 0 2

Available is 10 5 7 Safe Sequence is P1->P3->P4->P0->P2

Consider the following example of a system. Check whether the
system is safe or not using the Bankers Algorithm. Determine its
safe sequence
Safety Algorithm

D
Resource-Request Algorithm

D
Deadlock Detection

1. Single Instance of Each Resource Type

2. Several Instances of a Resource Type

Single Instance of Each Resource Type
Generate a wait for graph and search of cycles

Take the resource allocation graph, remove the resource edges

an edge Pi->Pj indicates

Process Pi is waiting of Pj to
release some resource
Several Instances of a Resource Type

ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 7 4 3 6 0 0
P3 2 1 1 2 2 2 7 4 5 0 1 1
P4 0 0 2 4 3 3 4 3 1
 WORK

T
A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0
1 P0 0 1 0 7 5 3 3 3 2 7 4 3
2 P1 2 0 0 3 2 2 1 2 2
3
P2 3 0 2 9 0 2 6 0 0
4
P3 2 1 1 2 2 2 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0
1 P0 0 1 0 7 5 3 3 3 2 7 4 3
2 P1 2 0 0 3 2 2 1 2 2
3
P2 3 0 2 9 0 2 6 0 0
4
P3 2 1 1 2 2 2 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0 FALSE
1 FALSE P0 0 1 0 7 5 3 3 3 2 7 4 3
2 FALSE P1 2 0 0 3 2 2 1 2 2
3 FALSE
P2 3 0 2 9 0 2 6 0 0
4 FALSE
P3 2 1 1 2 2 2 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0 FALSE
1 FALSE P0 0 1 0 7 5 3 3 3 2 7 4 3
2 FALSE P1 2 0 0 3 2 2 5 3 2 1 2 2
3 FALSE
P2 3 0 2 9 0 2 6 0 0
4 FALSE
P3 2 1 1 2 2 2 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0 FALSE
1 FALSE P0 0 1 0 7 5 3 3 3 2 7 4 3
2 FALSE P1 2 0 0 3 2 2 5 3 2 1 2 2
3 FALSE
P2 3 0 2 9 0 2 7 4 3 6 0 0
4 FALSE
P3 2 1 1 2 2 2 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0 FALSE
1 FALSE P0 0 1 0 7 5 3 3 3 2 7 4 3
2 FALSE P1 2 0 0 3 2 2 5 3 2 1 2 2
3 FALSE
P2 3 0 2 9 0 2 7 4 3 6 0 0
4 FALSE
P3 2 1 1 2 2 2 7 4 5 0 1 1
 WORK

T 3 3 2

A B C

FINISH ALLOCATION MAX WORK NEED

PROCES
S A B C A B C A B C A B C
0 FALSE
1 FALSE P0 0 1 0 7 5 3 3 3 2 7 4 3
2 FALSE P1 2 0 0 3 2 2 5 3 2 1 2 2
3 FALSE
P2 3 0 2 9 0 2 7 4 3 6 0 0
4 FALSE
P3 2 1 1 2 2 2 7 4 5 0 1 1
Recovery from Deadlock

1. Process Termination

A. Abort all deadlocked processes

B. Abort one process at a time until the deadlock cycle is

eliminated.
Abort one process at a time until the deadlock
cycle is eliminated.

Choose the process to incur minimum cost

1. Based on priority

2. How long the process has computed

3. How many and what types of resources the process has used

4. How many more resources the process needs in order to complete

5. How many processes will need to be terminated

Resource Pre-emption

three issues need to be addressed:

1. Selecting a victim

2. Rollback C=A+B … D=C-E

3. Starvation
Dining philosophers Problem