Unit IV

Concurrency Control
Interprocess Communication

▪ Processes within a system may be independent or

cooperating
▪ Cooperating process can affect or be affected by other
processes, including sharing data
 Cooperating Processes

▪ Independent process cannot affect or be affected by the execution of

another process
▪ Cooperating process can affect or be affected by the execution of another
process
▪ Advantages of process cooperation
– Information sharing
– Computation speed-up
– Modularity
– Convenience
▪ Cooperating processes need interprocess communication (IPC)
▪ Two models of IPC
– Shared memory
– Message passing
Communications Models
 Interprocess Communication – Shared Memory

▪ An area of memory shared among the processes that wish to communicate

▪ The communication is under the control of the users processes not the
operating system.
▪ Major issues is to provide mechanism that will allow the user processes to
synchronize their actions when they access shared memory.
 Interprocess Communication – Message Passing

▪ Mechanism for processes to communicate and to synchronize their

actions

▪ Message system – processes communicate with each other without

restoring to shared variables

▪ IPC facility provides two operations:

– send(message)
– receive(message)

▪ The message size is either fixed or variable

Race Condition
Here two processes P1 and P2 have count
variable common in them, i.e. count is a
shared variable of both the processes.

But while accessing count variable it may

happen that P1 increments value of count
and at the same time P2 decrements the
value of count.

It leads to ambiguous/incorrect result

It is known as Race Condition.

Critical section : A segment of code that
accesses shared resources (like data variables,
Race Condition : When multiple processes try to
files, or hardware devices) that must not be
modify shared data at the same time, it can lead to
accessed by multiple processes or threads
inconsistent and unpredictable results. This is
simultaneously.
known as a "race condition."
 Critical Section
▪ Critical section : A segment of code that accesses shared
resources (like data variables, files, or hardware devices)
that must not be accessed by multiple processes or
threads simultaneously. Critical section is a part where
shared variables or resources are placed.
▪ Consider system of n processes {p0, p1, … pn-1}
General structure of process Pi
▪ 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

▪ Each process must ask permission to enter critical section

in entry section, may follow critical section with exit
section, then remainder section
 Solution to Critical-Section Problem

Mutexes (Mutual Exclusion Locks):

Mutual exclusion is also known as Mutex.

Mutual exclusion is concurrency control’s property that is installed for the
objective of avoiding race conditions.

•A mutex acts like a lock that only one thread or process can hold at a time.

•Before accessing a shared resource, a thread attempts to acquire the mutex.

•If the mutex is already held, the thread blocks until it becomes available.

•This ensures that only one thread can execute the critical section at any
moment.
 Fundamental Requirements of Mutual Exclusion

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 processes that will enter the critical section next cannot be
postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that
processes are allowed to enter their critical section
 Semaphore

➢ It is a method /tool used to avoid race condition.

➢ It is an integer variable which is used in mutual exclusion manner by
various concurrent co-operative process in order to achieve
synchronization.
➢ There are two types
1. Counting
2. Binary
 Semaphore
shared variable semaphore = 1;
process i ➢ Here in this piece of pseudocode, we have
begin declared a semaphore in line 1, which has the
. value of 1 initially.
. ➢ We then start the execution of a process i which
P(mutex); has some code, and then as you can see, we call a
execute Critical Section function "P" which takes the value
V(mutex); of mutex/semaphore as input and we then
. proceed to the critical section, followed by a
.
function "V" which also takes the value
end;
of mutex/semaphore as input.
➢ Post that, we execute the remainder of the code,
and the process ends.
 Down/Wait Operation in Semaphores
➢ Wait, P , Down and Entry (these all operations have same meaning)
The wait operation, also called the "P" function, sleep, entry ,decrease, or down
operation, is the semaphore operation that controls the entry of a process into a
critical section.
If the value of the mutex/semaphore is positive then we decrease the value of the
semaphore and let the process enter the critical section.
Note that this function is only called before the process enters the critical section,
and not after it.
Example :
P(semaphore) {
if semaphore is greater than 0
then decrement semaphore by 1
}
➢ i.e. when S<=0 => No further process can enter in Critical Section.
➢ when S = 1 => 1 Process can enter in Critical Section.
 UP/Signal Operation in Semaphores
➢ Signal , V , Up, wake-up, increase, Release and Post (these all operations have
same meaning)

➢ As we know, once a process has exited the critical section, we must update the
value of the semaphore so that we can signal the new processes to be able to
access the critical section.

➢ For the updation of the value, once the process has exited the critical section,
since we had decreased the value of the semaphore by 1 in the wait operation,
here we simply increment it.

➢ Note that this function is added only after the process exits the critical
section and cannot be added before the process enters the section.
Example :
V(semaphore){
increment semaphore by 1
}
 Counting Semaphore

Down(Semaphore S) Up (Semaphore S)
{ {
S.Value = S.Value-1; S.Value = S.Value+1;
if (S.Value <= 0) if (S.Value < = 0)
{ {
Put Process (PCB) in suspended Select a Process from (PCB)
list, suspended list,
sleep(); wakeup();
} }
else
return; Wake up means that process can try to
} enter in CS
when S=0 => No further process can enter
in Critical Section.
when S = 1 => 1 Process can enter in Critical
Section.
 Implementation of Binary Semaphore in OS

While implementing of the semaphores we will consider two processes P1 and P2. For
simplicity of the example, we will take 2 processes, however, semaphores are used for a
very large number of processes.

Binary Semaphores:
❑ Initially, the value of the semaphore is 1.
❑ When the process P1 enters the critical section, the value of the semaphore
becomes 0.
❑ If P2 would want to enter the critical section at this time, it wouldn't be able to,
since the value of the semaphore is not greater than 0.
❑ It will have to wait till the semaphore value is greater than 0, and this will happen
only once P1 leaves the critical section and executes the signal operation which
increments the value of the semaphore.
❑ This is how mutual exclusion is achieved using binary semaphore i.e. both processes
cannot access the critical section at the same time.
Binary Semaphores:
❑ Initially, the value of the semaphore is 1.
❑ When the process P1 enters the critical section, the value
of the semaphore becomes 0.
❑ If P2 would want to enter the critical section at this
time, it wouldn't be able to, since the value of the
semaphore is not greater than 0.
❑ It will have to wait till the semaphore value is greater
than 0, and this will happen only once P1 leaves the
critical section and executes the signal operation which
increments the value of the semaphore.
❑ This is how mutual exclusion is achieved using binary
semaphore i.e. both processes cannot access the critical
section at the same time.
 Binary Semaphore Up (Semaphore S)
Down (Semaphore S) {
{ if (Suspended list is empty)
if (S.Value == 1) {
{ S.Value = 1;
S.Value = 0; }
} else
else {
{ select a process from
Block this process and suspended list and wake up();
place in suspended list, sleep(); }
} }
}
P1 P2
Down(s) Down(s)
Example :
Try execution of processes P1 and P2 CS--- CS----
for S=0 and S=1 ➔
Up(s) Up(s)
Classical Problem of Synchronization

❑ Readers-Writers Problem
❑ Producer Consumer Problem
❑ Dining Philosopher Problem
Reader-Writer Problem
 Case 1 : Reader is Reading and Writer is trying
to write it int rc = 1;
int rc = 0; Rc Mutex db Semaphore mutex = 0;
Semaphore mutex = 1; Semaphore db = 0;
Semaphore db = 1; 0 1 1 Void writer(void)
Void Reader(void) 1 0 0 {
{ while(true)
while(true) 1 {
{ down(db);
down(mutex);
rc = rc + 1;
if(rc == 1) then down(db); Tries to block other DB
up(mutex); process by making db=0 up(db);
}
} }
}

DB R1
❑ When writer tries to enter critical
Critical Section section, it must enter in Entry Section .
❑ Entry section code contains down(db) but
db is already zero value so it can’t
Up operation does semaphore from 0 to 1 .But if execute down(db) and writer gets
Semaphore is already 1 then it keeps that value 1. blocked..
Case 2 : Writer is writing and Reader is
trying to read it int rc = 0;
int rc = 0; Rc mutex db Semaphore mutex = 1;
Semaphore mutex = 1; Semaphore db = 0;
Semaphore db = 1; 0 1 1 Void Reader(void)
0 1 0 {
Void writer(void) while(true)
{ 1 0 {
while(true) Blocked down(mutex);
{
down(db); rc = rc +1;
Tries to block other
DB W1 process by making db=0
if (rc ==1 ) then down(db);
up(db);
} up(mutex);
}
}
}
❑ When reader tries to enter critical
section, it must enter in Entry Section .
❑ Entry section code contains down(mutex)
and rc = rc + 1 so value of rc becomes 1.
❑ Next to this it checks if rc == 1 then
down(db) db is already zero value so it
can’t execute down(db) and reader gets
blocked..
 Case 3 : Writer is writing and another writer is trying to write it
int rc = 0;
Semaphore mutex = 1; int rc = 0;
Semaphore db = 1; Rc mutex db Semaphore mutex = 1;
Semaphore db = 0;
Void writer(void) 0 1 1
{ 0 Void writer(void)
while(true) {
{ while(true)
down(db); {
DB W1 Tries to block other down(db);
process by making db=0 DB W1
up(db);
} up(db);
} }
}
❑ When another writer tries to enter
critical section, it must enter in Entry
Section .
❑ Entry section code contains down(db) but
db is already zero value so it can’t
execute down(db) and another
writer(W2) gets blocked..
 Case 4 : Reader is reading and another reader is trying to read it
int rc = 0; Rc Mutex db int rc = 1;
Semaphore mutex = 1; 0 1 1 Semaphore mutex = 1;
Semaphore db = 1; Semaphore db = 0;
Void Reader(void) 1 0 0
Void Reader(void)
{ 1 {
while(true) while(true)
2 0
{ {
down(mutex); 1 down(mutex);
rc = rc + 1; rc = rc + 1;
if(rc == 1) then down(db); Tries to block other
process by making db=0 if(rc == 1) then down(db);
up(mutex); up(mutex);
DB R1 DB R2
} }
} }
 Producer Consumer Problem

❑ Producer-Consumer problem is a classical synchronization problem in the

operating system.
❑ With the presence of more than one process and limited resources in the
system the synchronization problem arises.
❑ If one resource is shared between more than one process at the same time
then it can lead to data inconsistency.
❑ In the producer-consumer problem, the producer produces an item and the
consumer consumes the item produced by the producer.
Producer Consumer Problem

What is Producer?
In operating System Producer is a process which can
produce data/item.
What is consumer?
Consumer is a Process that can consume the
data/item produced by the Producer.

❑ Both Producer and Consumer share a common

memory buffer.
❑ This buffer is a space of a certain size in the
memory of the system which is used for storage.
❑ The producer produces the data into the buffer
and the consumer consumes the data from the
buffer.
What are the Producer-Consumer Problems?

❑ Producer Process should not produce any data when the shared buffer is
full.
❑ Consumer Process should not consume any data when the shared buffer is
empty.
❑ The access to the shared buffer should be mutually exclusive i.e at a time
only one process should be able to access the shared buffer and make
changes to it.
❑ For consistent data synchronization between Producer and Consumer, the
above problem should be resolved.
int count = 0;
Producer
Void Producer(void) Buffer
size n = 8
{ [0…n-1]
int itemP;
while (true) in count item
0 x1
{ 0
1
produce_item(itemP);
2
while(count == n); Buffer overflow
3
Buffer[in] = itemP;
in = (0+1)mod n = 1 mod 8 =1 4
in = (in + 1)mod n;
Load Rp, m[count]; Count gets loaded 5
count = count +1; in Register Rp 6
} INCR Rp; Value of Rp 7
} increments
Store m[count], Rp; Store value of Rp to
memory
 Consumer
Buffer
int count = 0; size n = 8
Void consumer(void) [0…n-1]

{
out count item
int itemC;
0 x1
while (true)
1
{ Empty Buffer 2
while(count == 0); 3
itemC = Buffer(out); 4
out = (out + 1)mod n; Load Rc, m[count]; Count gets loaded 5
count = count -1; in Register Rc
6
Process_item(itemC); DECR Rc; Value of Rc
7
increments
}
Store m[count], Rc; Store value of Rc to
} memory
 Producer Consumer Problem
Case 1 : Best case
Buffer int count = 0;
int count = 0; size n = 8
[0…n-1]
Void consumer(void)
Void Producer(void)
count item
{
{ 0
int itemC;
int itemP; 1
in while (true)
while (true) 2
{
{ 3
while(count == 0);
produce_item(itemP); 4
itemC = Buffer(out); out
while(count == n); 5
6 out = (out + 1)mod n;
Buffer[in] = itemP;
7 count = count -1;
in = (in + 1)mod n;
Process_item(itemC);
count = count +1;
}
}
}
}
 Producer Consumer Problem
Case 2 : Process Synchronization Problem
Problem may occur when interrupt occurs during execution of processes.
It could be like
Load Rp, m[count]; Count gets loaded Load Rc, m[count]; Count gets loaded
in Register Rp in Register Rc
INCR Rp; Value of Rp DECR Rc; Value of Rc
increments increments
Store m[count], Rp; Store value of Rp to Store m[count], Rc; Store value of Rc to
memory memory
❑ Producer executes instructions 1 (Loading Rp) and 2(incrementation of Rp) but
before executing instruction 3 interrupt occurs so Consumer starts execution.

❑ While executing Consumer executes instruction 1(Loading of Rc) and 2

(Decrementation) but again certain interrupt occurs and control goes to Producer.

❑ After some time Producer and Consumer executes Instruction 3.But leads to
ambiguous/incorrect result in count variable.
Producer
Problem
I1 of Producer Consider initially count is 3
I2 of Producer
Interrupt occurs
Load Rp, Count gets Instruction1 I1 Load Rc, Count gets loaded
m[count]; loaded in m[count]; in Register Rc
Consumer Register Rp
Instruction2 I2 DECR Rc; Value of Rc
I1 of Consumer INCR Rp; Value of Rp
increments
I2 of Consumer increments
Instruction3 I3 Store m[count], Rc; Store value of Rc to
Interrupt occurs Store m[count], Store value of Rp
Rp; to memory memory
I3 of Producer
Count=4
Producer
Terminates
I3 of Consumer
Count=2
Consumer
Terminates
 Solution
Assumptions: empty: no of empty slots in the buffer
full : no of filled slots in the buffer

void Consumer()
void Producer()
{
{
while(true)
while(true)
{
{
// consumer consumes an item
// producer produces an item/data
wait(Full);
wait(Empty);
wait(mutex);
wait(mutex);
consume();
add();
signal(mutex);
signal(mutex);
signal(Empty);
signal(Full);
}
}
}
}
 Dining Philosopher Problem

P0
❑Dining Philosophers Problem in OS is a
classical synchronization problem in the
F1 operating system.
F0
P1 ❑ With the presence of more than one
processes and limited resources in the
system the synchronization problem arises.
❑If one resource is shared between more
P4 than one processes at the same time, then it
F2 may lead to data inconsistency.
F4

P2

F3
P3
 Void philosopher(void)
{
while(true)
{
Left fork
When a philosopher thinks, Thinking();
Thinks he does not interact take_fork(i);
with his colleagues
Philosopher take_fork(i+1)mod N right fork
When a philosopher gets
Eats hungry, he tries to pick up the Eat();
two forks that are closest to
him (left & right). put_fork(i);
put_fork((i+1)mod N);
}
}
Void philosopher(void)
Case 1 :Normal Execution
{
P0 first take left fork i.e. F0 and then it
while(true) executes take_fork(i+1)mod N means
(0+1)mod 5 = 1 mod 5 = 1 i.e F1 and executes
{ Eat() instruction and proceed further.
Thinking();
take_fork(i);
take_fork(i+1)modN
Eat();
put_fork(i);
put_fork((i+1)mod N);
}
}
Here, P0,P1,P2,P3,P4 and P5 indicates philosophers so
N=5. F0,F1,F2.F3,F4 and F5 indicates forks.
 Case 2: Ambiguity in Execution
❑ Suppose P0 takes left fork i.e F0 and when P0 tries to get access
of next fork i.e. f1 at that time P1 gets access of F1 and then P1
executes next instruction and get fork F2.
❑ Means P1 gets both necessary forks i.e. F1 and F2 and it gets ready
to execute Eat() instruction.
❑ But P0 will be waiting for F1.
❑ As P1 gets both forks F1 and F2 , it is ready for execution of Eat()
instruction. It finishes its execution and after execution it releases
Here, P0,P1,P2,P3,P4 and P5 fork F1 and F2.Then it P0 will get access of F1 and it will become
indicates philosophers so N=5. ready for the execution.
F0,F1,F2.F3,F4 and F5 ❑ The best solution to implement synchronization is to use
indicates forks. Semaphore.
Void philosopher(void) P0 wants 2 forks so it needs 2 semaphores
Solution
{ P0 takes S0 and S1 (0+1) mod 5 = 1 mod 5 = 1
while(true) P1 takes S1 and S2 (1 + 1) mod 5 = 2 mod 5 = 2
{ P2 takes S2 and S3 (2 + 1) mod 5 = 3 mod 5 = 3
Thinking(); P3 takes S3 and S4 (3 + 1) mod 5 = 4 mod 5 = 4
wait (take_fork(i)); P4 takes S4 and S0 (4 + 1) mod 5 = 5 mod 5 = 0
All semaphores are S0 S1 S2 S3 S4
wait(take_fork(i+1)mod N) initialized with 1 1 1 1 1 1
Eat();
signal(put_fork(i)); Philosopher Required Semaphores
P0 S0 S1
signal(put_fork((i+1)mod N));
P1 S1 S2
}
P2 S2 S3
} P3 S3 S4
Here, P0,P1,P2,P3,P4 and P5 indicates philosophers so P4 S4 S0
N=5. F0,F1,F2.F3,F4 and F5 indicates forks.
 Philosopher Required Semaphores
P0 S0 S1
P1 S1 S2
P2 S2 S3
P3 S3 S4
P4 S4 S0

❑ This is the special case of Dining Philosopher Problem, in which two processes can enter in
Critical section but both should be independent.
❑ In above example P0 and P2 can access critical section at the same time because P0 wants
S0 and S1 and P2 wants S2 and S3 means P0 and P2 requires different forks for
accessing critical section, so they are known as independent.
❑ In the same way P1 and P3 are independent so they can have access of CS at same time.
Questions
1. Write a short note on interprocess communication.
2. What is critical section? Explain race condition with example.
3. Explain in detail Readers-writer classic synchronization problem in
operating system.
4. Explain in detail producer consumer classic synchronization problem in
operating system.
5. Explain in detail Dining philosopher classic synchronization problem in
operating system.
6. What is deadlock? Explain all necessary conditions for deadlock with
suitable example.
7. Explain Banker’s algorithm with suitable example./ Explain Deadlock
avoidance algorithm with suitable example.
8. Write a short note on Deadlock prevention.