Chapter -3

Concurrency &
Interprocess
Communication
 Outline
Looping
• IPC, Race Conditions, Critical Section, Mutual
Exclusion
• Mutual exclusion with busy waiting
• Disabling interrupts (Hardware approach)
• Shared lock variable (Software approach)
• Strict alteration (Software approach)
• TSL (Test and Set Lock) instruction (Hardware approach)
• Exchange instruction (Hardware approach)
• Dekker’s solution (Software approach)
• Peterson’s solution (Software approach)
• The Producer Consumer Problem
• Semaphores
• Classical IPC Problems
• Monitor
• Pipes and Message Passing
Section - 1
Inter-process communication (IPC)
 Inter-process communication is the mechanism
provided by the operating system that allows
processes to communicate with each other.
 This communication could involve a process letting
another process know that some event has
occurred or transferring of data from one process
to another.
 Processes in a system can be independent or
cooperating.
Inter-process
 Independent process cannot affect or be Communication
affected by the execution of another process.
Process - 1 Process - 2
 Cooperating processes can affect or be
affected by the execution of another process.
 Cooperating processes need inter-process
communication mechanisms.

4
…Inter-process communication (IPC)
 Objectives
 Information sharing: Several processes may need to access the same data (such as
stored in a file.)
 Computation speed-up: A task can often be run faster if it is broken into subtasks and
distributed among different processes.
 Modularity: It may be easier to organize a complex task into separate subtasks, then
have different processes or threads running each subtask.
 Convenience: Different running processes can communicate and work together
efficiently, improving system usability and workflow management.
 Issues of process cooperation
 Data corruption, deadlocks, increased complexity
 Requires processes to synchronize their processing

5
Models for Inter-process communication (IPC)
 Message Passing  Shared Memory
 Process A sends the message to  Process A puts the message into
Kernel and then Kernel sends that Shared Memory and then Process B
message to Process B reads that message from Shared
Memory

6
Race Condition
 The situation where several processes
Print spooler directory example :
access and manipulate shared data
concurrently. The final value of the shared Two processes want to access
data depends upon which process shared memory at the same time.
precisely runs when.
 A race condition is an undesirable
situation that occurs when a device or
system attempts to perform two or more
operations at the same time.
 But, because of the nature of the device
or system, the operations must be done in
the proper sequence to be done
correctly.
 To prevent race conditions, concurrent
processes must be synchronized.
7
Example of Race Condition
• Process A • Process A
next_free_slot = in next_free_slot = in (7)
Write file name at slot Context Switch
(7)
next_free_slot += 1 • Process B
in = next_free_slot (8) next_free_slot = in (7)
Write file name at
slot (7)
Context Switch next_free_slot += 1
in = next_free_slot (8)
• Process B Context Switch
next_free_slot = in
Write file name at slot
• Process A
(8) Write file name at
next_free_slot += 1 slot (7)
in = next_free_slot (9) next_free_slot += 1
in = next_free_slot (8)

8
Critical Section
Critical Section: The part of program
where the shared resource is accessed is
called critical section or critical region.
 When a process executes code that
manipulates/accesses shared data or resource,
we say that the process is in it’s Critical Section
(for that shared data)
 The execution of critical sections must be mutually
exclusive: at any time, only one process is allowed
to execute in its critical section

A enters in critical A leaves critical

Process region region
A B attempt B enters in B leaves
to enter critical critical
Process region region
B
T1 T2 B T3 T4
Blocked
9
CS Problem Dynamics
 The section of code implementing this request is called the Entry Section (ES).
 The critical section (CS) might be followed by a Leave/Exit Section (LS).
 The remaining code is the Non-critical/Remainder Section.
 The critical section problem is to design a protocol that the processes can use
so that their action will not depend on the order in which their execution is
interleaved.
 General structure of process Pi (other is Pj):
do {
entry section
critical section
leave section
remainder section
} while (TRUE);

10
Mutual Exclusion

Mutual Exclusion: Way of making sure

that if one process is using a shared
variable or file; the other process will be
excluded (stopped) from doing the
same thing.

 If process Pi is executing in its critical section,

then no other processes can be executing in
their critical sections

 Suggestions:
 Critical sections better be focused and short.
 Better not get into an infinite loop
 If a process somehow halts/waits in its critical section, it must not interfere with other
processes
11
Solving Critical-Section Problem
Any good solution to the problem must satisfy the following four conditions:
 Mutual Exclusion
 No two processes may be simultaneously inside the same critical section.

 Bounded Waiting
 No process should have to wait forever to enter a critical section.

 Progress
 No process running outside its critical region may block other processes.

 Arbitrary Speed
 No assumption can be made process execution speed or system configuration.

12
Section - 2
Mutual exclusion with busy waiting
 Mechanisms for achieving mutual exclusion with busy waiting
 Disabling interrupts (Hardware approach)
 Shared lock variable (Software approach)
 Strict alteration/ Dekker’s solution (Software approach)
 TSL (Test and Set Lock) instruction (Hardware approach)
 Peterson’s solution (Software approach)

14
Real life example to explain mechanisms for achieving mutual exclusion
with busy waiting

15
Section – 2.1
Disabling interrupts (Hardware approach)
 while (true)
{
< disable interrupts >;
< critical section >;
< enable interrupts >;
< non-critical section >;
} < critical section < non-critical
< disable > < enable section >
interrupts > interrupts >

Process
A

Process
B
T1 T3 T4
17
Problems in Disabling interrupts (Hardware approach)
 Unattractive or unwise to give user processes the power to turn off
interrupts.
 What if one of the process did it (disable interrupt) and never
turned them on (enable interrupt) again? That could be the end of
the system.
 If the system is a multiprocessor, with two or more CPUs, disabling
interrupts affects only the CPU that executed the disable
instruction. The other ones will continue running and can access
the shared memory.

18
Section – 2.2
Shared lock variable (Software approach)
 A shared variable lock having value 0 or 1.
 Before entering into critical region a process checks a shared variable lock’s
value.
 If the value of lock is 0 then set it to 1 before entering the critical section and enters into
critical section and set it to 0 immediately after leaving the critical section.
 If the value of lock is 1 then wait until it becomes 0 by some other process which is in
critical section.

20
Shared lock variable (Software approach)
Problem:
 while (true) • If process-A sees the value of lock variable 0 and
{ while (lock!=0); before it can set it to 1 context switch occurs.
• Now process-B runs and finds value of lock variable 0,
lock=1; so it sets value to 1, enters critical region.
• At some point of time process-A resumes, sets the
critical_section( );
value of lock variable to 1, enters critical region.
lock=0; • Now two processes are in their critical regions
accessing the same shared memory, which violates
non_critical_section( ); the mutual exclusion condition.
}
< critical section < remainder
< set lock to 1 > > < set lock to 0 section
> >

Process
A

Process
B
T1 T3 T4
21
Strict alteration/ Dekker’s solution (Software approach)
 Integer variable 'turn' keeps track of whose turn is to enter the critical section.
 Initially turn=0. Process 0 inspects turn, finds it to be 0, and enters in its critical
section.
 Process 1 also finds it to be 0 and therefore sits in a loop continually testing
'turn' to see when it becomes 1.
 Continuously testing a variable waiting for some event to appear is called the
busy waiting.
 When process 0 exits from critical region it sets turn to 1 and now process 1
can find it to be 1 and enters in to critical region.
 In this way, both the processes get alternate turn to enter in critical region.

22
Strict alteration (Software approach)
Process 0 Process 1
while (TRUE) while (TRUE)
{ {
while (turn != 0) /* loop */ ; while (turn != 1) /* loop */ ;
critical_region(); critical_region();
turn = 1; turn = 0;
non_critical_section(); non_critical_section();
} }

0 0 0 1 0 0
0 enters in critical 0 leaves critical
Process region region
0 1 attempt 1 enters in 1 leaves 1
to enter critical critical attempt
Process region region to enter
1
T1 T2 1 Busy T3 T4 T5 1 Busy
Wait Wait
23
Disadvantages of Strict alteration (Software approach)
 Taking turns is not a good idea when one of the processes is much slower
than the other (e.g. non critical section has thousands of lines of code).
 Consider the following situation for two processes P0 and P1.
 P0 first enters and then leaves its critical region, set turn to 1, enters non critical region.
 P1 enters and finishes its critical region, set turn to 0.
 Now both P0 and P1 in non-critical region.
 P0 finishes non critical region, enters critical region again, and leaves this region, set turn to 1.
 P0 and P1 are now in non-critical region.

0 0 0 1 0 0 1
0 enters in critical 0 leaves critical
Process region region
0 1 attempt 1 enters in 1 leaves
to enter critical critical
Process region region
1
T1 T2 1 Busy T3 T4 T5 T6 T7
Wait
24
Disadvantages of Strict alteration (Software approach)
 P0 finishes non critical region but cannot enter its critical region because turn = 1 and it is
turn of P1 to enter the critical section.
 Hence, P0 will be blocked by a process P1 which is not in critical region. This violates one
of the conditions of mutual exclusion.
 It wastes CPU time, so we should avoid busy waiting as much as we can.

0 0 0 1 0 0 1 0 attempt
0 enters in critical 0 leaves critical to enter
Process region region
0 1 attempt 1 enters in 1 leaves
critical 1 Busy
to enter critical
region Wait
Process region
1
T1 T2 1 Busy T3 T4 T5 T6 T7
Wait
25
TSL (Test and Set Lock) instruction (Hardware approach)
 Algorithm
enter_region: (Before entering its critical region, process calls enter_region)
TSL REGISTER, LOCK |copy lock variable to register AND THEN set lock to 1
CMP REGISTER, #0 |was LOCK variable 0?
JNE enter_region |if it is zero, enter critical region, else busy wait
RET |return to caller: critical region entered

leave_region:(When process wants to leave critical region, process calls leave_region)

MOVE LOCK, #0 |store 0 in lock variable
RET |return to caller

Register 0

Process
0

Process
1
T1 T2 T3 26
TSL (Test and Set Lock) instruction (Hardware approach)
 Test and Set Lock Instruction
 TSL REGISTER, LOCK
 It reads the contents of the memory word lock into register RX and then stores a nonzero
value at the memory address lock.
 The operations of reading the word and storing into it are guaranteed to be indivisible—
no other processor can access the memory word until the instruction is finished.
 The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from
accessing memory until it is done.
Bounded Waiting is not guaranteed in TSL. Some process
might not get a chance for so long.
Register 0 TSL works on a single CPU.

Process
0

Process
1
T1 T2 T3
27
Peterson’s solution (Software approach)
#define FALSE 0
#define TRUE 1
#define N 2 //number of processes
int turn; //whose turn is it? P0 P1 P0 P1
0 1
int interested[N]; //all values initially 0 (FALSE) 0 0 1 0
void enter_region(int process)
{
int other; // number of the other process
other = 1 - process; // the opposite process 1 0
interested[process] = TRUE; // this process is interested 1 0 1 1
turn = process; // set flag 0 1
while(turn == process && interested[other] == TRUE); // wait
}
void leave_region(int process)
{ 0 1
interested[process] = FALSE; // process leaves critical region
}
28
Priority inversion problem
 Priority inversion means the execution of a high priority process/thread is blocked by a lower
priority process/thread.
 Consider a computer with two processes, H having high priority and L having low priority.
 The scheduling rules are such that H runs first then L will run.
 At a certain moment, L is in critical region and H becomes ready to run (e.g. I/O operation
complete).
 H now begins busy waiting and waits until L will exit from critical region.
 But H has highest priority than L so CPU
L
is switched from L to H.
 Now L will never be scheduled (get CPU) until
H is running so L will never get chance to
leave the critical region so H loops forever. H
 This situation is called priority inversion problem.

29
Mutual Exclusion with Busy Waiting
 Disabling Interrupts
 is not appropriate as a general mutual exclusion mechanism for user processes
 Lock Variables
 contains exactly the same fatal flaw that we saw in the spooler directory
 Strict Alternation
 process running outside its critical region blocks other processes.
 Peterson's Solution
 The TSL instruction
 Both Peterson’s solution and the solutions using TSL are correct.
 Limitations:
 Busy Waiting: this approach waste CPU time
 Priority Inversion Problem: a low-priority process blocks a higher-priority one

30
Busy Waiting (Sleep and Wakeup)
 Peterson’s solution and solution using TSL have the limitation of requiring busy
waiting.
 when a processes wants to enter in its critical section, it checks to see if the entry is
allowed.
 If it is not allowed, the process goes into a loop and waits (i.e., start busy waiting) until it is
allowed to enter.
 This approach waste CPU-time.

 But we have interprocess communication primitives (the

pair of sleep & wakeup).
 Sleep: It is a system call that causes the caller to be blocked
(suspended) until some other process wakes it up.
 Wakeup: It is a system call that wakes up the process.
 Syntax: sleep(); wakeup(A);

31
Section - 3
The Producer Consumer Problem
 It is multi-process synchronization
problem.
 Consider Producer-Consumer bounded
buffer problem.
Produc Buffer Consum
 This problem describes two processes er er
producer and consumer, who share
common, fixed size buffer.
 Producer process
 Produce some information and put it into
buffer
 Consumer process
 Consume this information (remove it from the
buffer)

33
What Producer Consumer problem is?
 Buffer is empty
√
 Producer want to produce
X
 Consumer want to consume
 Buffer is full
Produc Buffer Consum
X
 Producer want to produce
er er
√
 Consumer want to consume
 Buffer is partial filled
√
 Producer want to produce
√
 Consumer want to consume

34
Producer Consumer problem using Sleep & Wakeup
#define N 4 count 1
0
int count=0;
item Item 1
void producer (void)
{ int item; Producer Buffer Consumer
1
while (true)
2
{ item=produce_item();
3
if (count==N) sleep(); 4
insert_item(item);
count=count+1;
if(count==1) wakeup(consumer);
}
}
35
Producer Consumer problem using Sleep & Wakeup
void consumer (void) count 1
0
{ int item;
item
while (true)
{ if (count==0) sleep(); Produc Buffer Consum
er 1 Item 1 er
item=remove_item();
2
count=count-1;
3
if(count==N-1) wakeup(producer); 4
consume_item(item);
}
}

36
Problem in Sleep & Wakeup
 Problem with this solution is that it contains a race condition that can lead to a
deadlock. (How???-Lost Wakeup Problem)
#define N 4 Producer void consumer (void) Consumer
int count=0; { int item; Context
coun 1
0 Switching
void producer (void) t while (true)
{ int item; item Item 1 { if (count==0)
while (true) sleep();
Buffer item=remove_item();
{
item=produce_item(); 1 count=count-1;
if (count==N) sleep(); 2 Item 2 if(count==N-1)
insert_item(item); 3 Item 3
Item 4 wakeup(producer);
count=count+1; 4

if(count==1) consume_item(item);
wakeup(consumer); Wakeup }
Signal
} }
} 37
Problem in Sleep & Wakeup
 The consumer has just read the variable count, noticed it's zero and is just about
to move inside the if block.
 Just before calling sleep, the consumer is suspended and the producer is
resumed.
 The producer creates an item, puts it into the buffer, and increases count.
 Because the buffer was empty prior to the last addition, the producer tries to
wake up the consumer.
 Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost (LOST
WEAKUP PROBLEM).
 When the consumer resumes, it goes to sleep and will never be awakened
again. This is because the consumer was only awakened by the producer when
count is equal to 1.
 The producer will loop until the buffer is full, after which it will also go to sleep.
 Finally, both the processes will sleep forever. This solution therefore is
unsatisfactory. 38
Section - 4
Semaphore
 A semaphore is a variable that provides an abstraction for controlling the
access of a shared resource by multiple processes in a parallel programming
environment.
 There are 2 types of semaphores:
 Binary semaphores :-
 Binary semaphores can take only 2 values (0/1).
 Binary semaphores have 2 methods associated with it (up, down / wait, signal).
 They are used to acquire locks.
 Counting semaphores :-
 Counting semaphore can have possible values more than two.

40
Semaphore
 We want functions insert _item and remove_item such that the following hold:
 Mutually exclusive access to buffer: At any time only one process should be executing
(either insert_item or remove_item).
 No buffer overflow: A process executes insert_item only when the buffer is not full (i.e., the
process is blocked if the buffer is full).
 No buffer underflow: A process executes remove_item only when the buffer is not empty
(i.e., the process is blocked if the buffer is empty).
 No busy waiting.
 No producer starvation: A process does not wait forever at insert_item() provided the
buffer repeatedly becomes full.
 No consumer starvation: A process does not wait forever at remove_item() provided the
buffer repeatedly becomes empty.

41
Operations on Semaphore
 Wait(): a process performs a wait operation to tell the semaphore that it wants
exclusive access to the shared resource.
 If the semaphore is empty, then the semaphore enters the full state and allows the
process to continue its execution immediately.
 If the semaphore is full, then the semaphore suspends the process (and remembers that
the process is suspended).
 Signal(): a process performs a signal operation to inform the semaphore that it
is finished using the shared resource.
 If there are processes suspended on the semaphore, the semaphore wakes one of the
up.
 If there are no processes suspended on the semaphore, the semaphore goes into the
empty state.

42
Operations of Binary Semaphores
void wait (semaphore s) void signal(semaphore s)
{ {
if (s==1) if (suspended_queue is empty)
s=0; s=1;
else else
{ {
place the process in suspended queue; remove a process from suspended queue;
block the process; place the process in ready queue;
} }
} }

43
Operations of Counting Semaphores
void wait (semaphore s) void signal(semaphore s)
{ {
s- -; s++;
if (s<0) if (s<=0)
{ {
place the process in suspended queue; remove a process from suspended queue;
block the process; place the process in ready queue;
} }
} }

44
Producer Consumer problem using Semaphore
#define N 4 mutex 1
0
typedef int semaphore;
semaphore mutex=1; empty 3
4
semaphore empty=N;
full 1
0
semaphore full=0;
void producer (void)
item Item 1
{ int item;
while (true)
Produc Buffer Consum
{ item=produce_item(); er er
1
wait(&empty);
2
wait(&mutex);
3
insert_item(item);
4
signal(&mutex);
signal(&full); }
}
45
Producer Consumer problem using Semaphore
void consumer (void) mut 1
0
{ int item; ex
while (true) emp 3
4
{ ty
full 1
0
wait(&full);
wait(&mutex);
item
item=remove_item(item);
signal(&mutex);
Produc Buffer Consum
signal(&empty); er er
1 Item 1
consume_item(item);
2
}
3
}
4

46
Section – 5.1
Readers & Writer Problem
 In the readers and writers problem, many competing processes are wishing to
perform reading and writing operations in a database.
Need to keep
track of read of
P1 P2 P3 P1 P2 P3 more than one
process at a time
Read XRead X Read Read √ Read √ 3 Reader_count
Write Write Write Write Write
X X X X

DATABASE DATABASE

 It is acceptable to have multiple processes reading the database at the same

time, but if one process is updating (writing) the database, no other processes
may have access to the database, not even readers.
48
Readers-Writers Dynamics
 Any number of reader activities and writer activities are running.
 At any time, a reader activity may wish to read data.
 At any time, a writer activity may want to modify the data.
 Any number of readers may access the data simultaneously.
 During the time a writer is writing, no other reader or writer may access the
shared data

49
Readers & Writer Problem
typedef int semaphore;
semaphore mutex=1; //control access to reader count
semaphore db=1; //control access to database
int reader_count=0; //number of processes reading database

50
Readers & Writer Problem
void Reader (void)
{ while (true) {
wait(&mutex); //gain access to reader count
reader_count=reader_count+1; //increment reader counter
if(reader_count==1) //if this is first process to read DB
wait(&db) //prevent writer process to access DB
signal(&mutex) //allow other process to access reader_count
read_database();
wait(&mutex); //gain access to reader count
reader_count=reader_count-1; //decrement reader counter
if(reader_count==0) //if this is last process to read DB
signal(&db) //leave the control of DB, allow writer process
signal(&mutex) //allow other process to access reader_count
use_read_data(); } //use data read from DB (non-critical)
}
51
Readers & Writer Problem
void Writer (void)
{ while (true) {
create_data(); //create data to enter into DB (non-critical)
wait(&db); //gain access to DB
write_db(); //write information to DB
signal(&db); } //release exclusive access to DB
}

52
Section – 5.2
Dinning Philosopher Problem
 In this problem 5 philosophers sitting at a
round table doing 2 things eating and
thinking.
 While eating they are not thinking and while
thinking they are not eating.
 Each philosopher has plates that is total of 5
plates.
 And there is a fork place between each pair
of adjacent philosophers that is total of 5
forks.
 Each philosopher needs 2 forks to eat and
each philosopher can only use the forks on
his immediate left and immediate right.

54
Dinning Philosopher Problem
#define N 5 //no. of philosophers
#define LEFT (i+N-1)%5 //no. of i’s left neighbor
#define RIGHT (i+1)%5 //no. of i’s right neighbor
#define THINKING 0 //Philosopher is thinking
#define HUNGRY 1 //Philosopher is trying to get forks
#define EATING 2 //Philosopher is eating
typedef int semaphore; //semaphore is special kind of int
int state[N]; //array to keep track of everyone’s state
semaphore mutex=1; //mutual exclusion for critical region
semaphore s[N]; //one semaphore per philosopher

55
Dinning Philosopher Problem
void take_forks (int i) //i: philosopher no, from 0 to N-1
void philosopher (int i) //i: philosopher no, from {0 to N-1
wait(&mutex); //enter critical region
state[i]=HUNGRY; //record fact that philosopher i is
{
hungry
while (true) test(i); //try to acquire 2 forks
{ signal(&mutex); //exit critical region
wait(&s[i]); //block if forks were not acquired
think(); //philosopher is thinking }
take_forks(i); //acquire two forks or block
void test (i) //i: philosopher no, from 0 to N-1
{
eat(); //eating spaghetti if (state[i]==HUNGRY && state[LEFT]!=EATING &&
state[RIGHT]!=EATING)
put_forks(i); //put both forks back on table
{ state[i]=EATING;
} signal(&s[i]); }
} }
void put_forks (int i) //i: philosopher no, from 0 to N-1
{ wait(&mutex); //enter critical region
state[i]=THINKING; //philosopher has finished eating
test(LEFT); //see if left neighbor can now eat
test(RIGHT); // see if right neighbor can now eat
signal(&mutex); // exit critical region
}
56
Barbershop Problem
 Consider a barbershop having 3 chairs, 3 barbers, and a waiting area that
can accommodate 4 customers on a sofa and that has standing room for
additional customers. Assume that the barbershop will process 50
customers. The maximum capacity of the barber shop is 20.
 A customer will not enter the shop if it is filled to capacity with other
customers.
 Inside the shop, if the sofa is not filled, the customers takes a seat and if
filled, he stands.
 When a barber is free, the customer has been on the sofa the longest is
served.
 When a sofa seat is free, the customer that has been standing the longest,
takes a seat.

57
…Barbershop Problem
 When a customer haircut is finished, any barber can accept payment, but
there is only one cash register, so payment is accepted for one customer
at a time
 The barbers divide their time among cutting hair, accepting payment and
sleeping in their chair waiting for a customer.

58
…Barbershop Problem
No. Semaphore Wait Signal
c 1. max_capacity customer wait for room to enter shop Exiting customer signals a customer who is waiting
to enter
c 2. sofa customer waits for seat on sofa Customer who now hops into a barber chair
signals a customer who is waiting for sofa

c 3. barber_chair customer waits for empty barber chair barber signals when chair is empty

b 4. cust_ready barber waits until the customer is in customer signals barber that he is ready to cut hair
the chair
c 5. finished[i] customer i waits until his haircut is barber signals when haircut is done
complete
b 6. leave_b_chair barber waits for customers getting up customer signals barber when he gets up from
from chair chair
b(c) 7. payment cashier waits for customers to pay customer signals cashier that he has paid

c 8. recipet customer waits for a receipt for cashier signals that payment has been accepted.
payment
b/b(c) 9. coord wait for a barber to be free to perform signal that a barber is free from the activity
haircut or cashiering
c – customers, b – barber, b(c) – barber cashier

59
…Barbershop Problem
 ‘mutex1’: It protects the ‘count’ (for giving each customer unique number)
 ‘mutex2’: Protects the queue
 Once a customer enters a shop, he gets a unique number.
 enqueue1: A customer places his number on the queue1 with enqueue1
just prior to signaling the barber with the semaphore cust_ready. This is how
barber knows customers number.
 dequeue1: When a barber is ready to cut hair, dequeue1 (b_cust) removes
the top customer from queue1 an places it in the local variable ‘b_cust’.
 The customer executes wait (finished[custno]) to wait on his own
semaphore. When barber finishes haircut he executed signal
(finished[b_cust]) to release the correct customer.

60
…Barbershop Problem
typedefint semaphore;
semaphore max_capacity=20;
semaphore sofa = 4;
semaphorebarber_chair=3, coord=3;
semaphore mutex1=1, mutex2=1;
semaphore cust_ready=0, leave_b_chair=0, payment=0, receipt=0; // binary 0 & 1
semaphore finished[50]= {0}; // 50 cutomers binary semaphores initialized to 0
int count=0;
void customer() leave_barber_chair();
sit_on_sofa();
{ signal(leave_b_chair);
wait(barber_chair);
int custno;//customer number pay();
get_up_from_sofa();
wait(max_capacity); signal(payment);
signal(sofa);
enter_shop(); wait(receipt);
sit_in_barber_chair();
wait(mutex1); exit_shop();
wait(mutex2);
count++; signal(max_capacity);
enqueue1(custno);
custno=count; }
signal(cust_ready);
signal(mutex1);
signal(mutex2);
wait(sofa);
wait(finished[custno]);
61
…Barbershop Problem
void barber() void main()
void cashier()
{ {
{
int_cust; count=0;
while(TRUE)
while(TRUE) parbegin(customer,… 50 times…,
{
{ barber,barber,barber,cashier);
wait(payment);
wait(cust_ready); }
wait(coord);
wait(mutex2);
accept_pay();
dequeue1(b_cust);
signal(coord);
signal(mutex2);
signal(receipt);
wait(coord);
}
cut_hair();
}
signal(coord);
signal(finished[b_cust]);
wait(leave_b_chair);
signal(barber_chair);
}
}
62
Problems with Semaphores
 As an aside, it is worth pointing out that although the readers and writers and
sleeping barber problems do not involve data transfer, they still belong to the
area of IPC because they involve synchronization between multiple
processes.
 Semaphores provide a powerful tool for enforcing mutual exclusion and
coordinate processes.
 But wait(S) and signal(S) are scattered among several processes. Hence,
difficult to understand their effects.
 Usage must be correct in all the processes (correct order, correct variables,
no errors).
 Incorrect use of semaphore operations:
 signal (mutex) …. wait (mutex)
 wait (mutex) … wait (mutex)
 Omitting of wait (mutex) or signal (mutex) (or both)
 One bad (or malicious) process can fail the entire collection of processes.
63
Section – 6
Monitor
 A higher-level synchronization primitive.
 A monitor is a collection of procedures, variables, and data structures that are all grouped
together in a special kind of module or package.
 Semaphores are powerful for enforcing mutual exclusion and for process synchronization.
However, wait and signal operations may be scattered throughout a program and it is not
easy to see overall effect of these operations on the semaphores. Sometimes it may be
difficult to produce a correct program using semaphores.
 The monitor is a programming language construct that provides equivalent functionality as
that of semaphores and easier to control.
 A monitor is an s/w module consisting of one or more procedures, an initialization sequence
and local data. Its chief characteristics are:
1. The local data variables are accessible only by the monitor’s procedure and not by any
external procedure.
2. A process enters the monitor by invoking one of its procedures.
3. Only one process may be executing in the monitor at a time. If any other process invokes
monitor, it is suspended and waits for the monitor to become available.
65
…Monitors
 First two characteristics are similar to those of an object in an OOP language.
 Third characteristic provides mutual exclusion. Thus, a shared data structure
can be protected by placing it in a monitor.
 A monitor supports synchronization by the use of condition variables that are
contained within the monitor and accessible only within the monitor. Two
functions operate on condition variables.
1. cwait(c): Suspend execution of the calling process on condition c. Monitor is now available
for use by another process.
2. csignal (c): Resume execution of some process suspended after a ‘cwait’ on the same
condition. If several such process are there, choose one of them. If there is no such process
do nothing
void cwait(int c) void csignal(int c)
{ {
if monitor_busy then wait; busy = false;
busy = true; monitor is free;
} }
66
Schematic View of a Monitor

67
Possible Monitor Dynamics
 Monitors make the critical data accessible
indirectly and exclusively via a set of
publically available procedures while in
semaphore users are encouraged to
access data by means of the procedures;
they are not forced, like monitors. Thus,
monitors go a step beyond the
semaphores. Semaphores may make the
system vulnerable to the forgetfulness of its
users.
 A process can enter the monitor by
invoking its any procedure; other processes
placed in attempt to enter the monitor,
placed in a queue waiting for monitor’s
availability.
68
…Monitors
 In monitor, the process may temporarily suspend itself on condition x by
issuing cwait(x). It is then placed in a queue of process waiting to reenter the
monitors.
 When a process that is executing in the monitor detects a change in
condition x, it issues csignal(x), which alerts the corresponding condition
queue that the condition has changed. So, the process which has been
waiting longest in the condition queue of x, is now placed in the urgent
queue waiting for availability of monitor. If no, process waiting on condition x,
then the execution of csignal(x) has no effect (it is lost).

69
Producer Consumer Bounded Buffer Problem using Monitor
monitor boundbuffer; //start of monitor Hoare’s Approach

char buffer[N]; // N slots

int nextin,nextout; // buffer pointers
int count; // number of items in buffers
int notfull, notempty; // condition variables
void append(char a) // monitor procedure public
{
if (count == N) //if buffer is full
cwait(notfull); // avoid overflow
buffer[nextin]=a;
nextin=(nextin+1)%N;// next slot in buffer
count++; // An item is added in buffer
csignal(notempty); //resume if consumes waiting
} 70
Producer Consumer problem using Monitor
void take(char a) // monitor procedure public void producer()
{
{
char a;
if (count==0) // if buffer is empty while (TRUE)
{
cwait(notempty); // avoid underflow produce(a);
a = buffer[nextout]; append(a);
//add
nextout = (nextout+1)%N; //next slot in buffer }
count --; // An item is removed from buffer }

csignal(notfull); // resume any waiting producer

} void consumer()
{
{ //initialization char a;
nextin=nextout=count=0; //initially buffer empty while(TRUE)
{
} take(a);
//remove
void main()
consume(a);
{ }
}
pasbegin(producer, consumer);
} 71
…Monitors
 In producer/consumer problem, the shared buffer is declared as belonging to a monitor;
neither produces nor consumes is permitted direct access to it. They must call procedures to
access (append & take). Thus variables are private and procedures are public; so only
procedures are accessible.
 But there are 2 drawbacks of Hoare’s approach:
1. If the process issuing the csignal has not finished with the monitor, then two additional
process switches are required: one to suspend this process and another to resume it when
the monitor becomes available.
2. When ‘csignal’ is issued, a process from the corresponding condition queue must be
activated urgently from the urgent queue and the scheduler must ensure that no other
process enters monitor before activation.
 Lampson and Redell developed an approach to solve these problems: csignal is replaced
cnotify. cnotify(x) causes the process in the x condition queue to be notified but current
process continues to execute and the condition queue process will resume in future when
the monitor is available. Moreover, as there is no guarantee that other process will not enter
the monitor before the waiting process, the waiting process must recheck the condition x.
e.g. The ‘if’ statements in figure are replaced by while loops, so that at least one more time
the condition variable is checked 72
…Monitors
 So, even if before the waiting process if another process enters the monitor
and changes count, then also when waiting process resumes it checks the
condition once again with ‘while’ changing:
while(count==N) while(count==0)
. .
. .
. .
cnotify(not empty); cnotify(notfull);

 With cnotify, no more extra process switches are required.

73
Section – 8
Pipes
 Pipe is a communication medium between two or more related or
interrelated processes usually between parent and child process.
 Communication is achieved by one process write into the pipe and other
process reads from the pipe.
 It performs one-way communication only means we can use a pipe such that
one process write into the pipe, and other process reads from the pipe.
 It opens a pipe, which is an area of main memory that is treated as a “virtual
file”.
 It is bounded buffer means we can send only limited data through pipe.

75
Message Passing
 When processes interact with one another, two fundamental requirements
must be satisfied: synchronization and communication.
 ‘Message Passing’ provides both functions. It is used for uniprocessor,
multiprocessor as well as for distributed system.
 It has a pair of primitives:
Send (destination, message)
Receive(source, message)
 These are mainly 4 design issues:
1. Naming
2. Copying
3. Synchronous and Asynchronous
4. Length
76
Message Passing Design Issues
1. Naming:
a) Direct naming: When each sender sends specific name of recipient and
each receiver names specific source, then it is called ‘Direct naming’.
Send(B, message);receive(A, message)
b) Indirect naming: When message are sent to and received from specialized
repositories, called mailboxes, it is called ‘Indirect naming’. Send (mailbox,
message); receive(mailbox, message).
 E.g. If a printer handler must know the names of all its clients, it uses ‘Direct-
naming’.
 Indirect naming can provide one-to-one, one-to-many, many-to-one and
many-to-many mappings between sending and receiving process. E.g.
Through mailbox, it is possible to provide communication between one
sender-one receiver, one sender - many receivers, many senders - many
receivers, many senders-one receiver and many senders-many receivers.
77
…Message Passing Design Issues
2. Copying:
 Message from sender must be passed to receiver. It is accomplished either by
copying the whole message into the receiver space or by simply passing a
pointer to the message, between two processes. Thus, in message passing,
either value or reference is used to pass a message.
 In distributed system with no common memory, the message is copied into
receiver’s space, while in centralized into receiver’s space, while in
centralized system message is passed by reference.
 UNIX uses hybrid approach: copy-on-write. Initially sharing a single copy of
the message between sender and receiver. However, when either sender or
receiver attempts to modify the shared copy, the OS creates a separate
copy of the message and it is sent into its space.

78
…Message Passing Design Issues
3. Synchronous and Asynchronous Message Exchange:
 The exchange of a message between a sender and receiver can be
synchronous and asynchronous.
 Synchronous: When sender wishes to send a message for which no
outstanding RECEIVE is issued, the sender must be suspended until a willing
receiver accepts the message. So, here at most one message may be
pending at any time. The sender finishes SEND only after the receiver receives
the message.
 Asynchronous : The sender is not suspended even if there is no outstanding
RECEIVE is issued. Sender can continue to execute after sending a message.
This ‘send and forget’ mode of operation tends to increase complexity of
implementation than synchronous mode.

79
…Message Passing Design Issues
 E.g., A process wishing to print something, places the data into a message
and sends it to printer server process. Even if the system’s printer server
process is busy at the moment, the message is queued by the system and
sender continues to execute.
 While in synchronous mode, the sender waits until printer server receivers the
message.
 In unbuffered message systems(no buffer), a problem(for both synchronous
and asynchronous) called ‘Indefinite postponement’ occurs. It happens when
a sent message is never received or when a receiver waits for a message that
is never produced. The solution is on the following slide:

80
…Message Passing Design Issues
 Sender: : Here, the sender sends a
send(mailbox, message); message and then waits for
acknowledgement message
receive(ackmail, ack, time_limit); from the receiver. If the receiver
does not receive the message
:
for some reason, the time limit
 Receiver: : expires and sender does not get
the acknowledgement from
receive(mailbox, message,time_limit); receiver. So, sender takes
appropriate action. Thus, when
if message_received_in_time
receiver does not receive
send(ackmail, ack); message in time limit, this
solution woks.
:

81
…Message Passing Issues
4. Message Length:
 Fixed–size message: Short message waste system buffer’s space, as they are
of fixed size(buffer-fixed size). While a long message is split and sent in
installments, which may cause some (sequencing) problems. However, this
technique is quite simple an efficient.
 Variable-size message: It eliminates the problems of fixed-size buffer, as
buffers are created dynamically, to fit each message . However, allocation
and management of this dynamic memory pool is costly in terms of CPU time.

82
Mutual Exclusion with Message Passing
typedef char *mesg; void main()
const int n =10; // no. of processes {
void P(int i) create_mailbox(mutex); //mailbox-mutex
{ send(mutex, null);
message msg; //message pasbegin(P(1),P(2),…P(n));
while(TRUE); }
{
receive(mutex, msg); //mutex is a mailbox
critical_region();
send(mutex, msg);
noncritical_region();
}
}

83
…Mutual Exclusion with Message Passing
• A process wishing to enter its critical region first attempts to receive a
message. If the mailbox is empty, then process is blocked.
• Once a process acquires the message, it performs its critical region and sends
the message into the mutex(mailbox).
• Now a process wishing to enter, receives the message sent by earlier process;
it makes the mailbox empty again and after performing the critical region, it
sends the message to mailbox.
• Thus, the message is passed from one process to another process to achieve
mutual exclusion.

84
Message Passing Types
 Blocking send, Blocking receive:
• Both the sender and receiver are blocked until the message is delivered called ‘rendezvous’.
It provides tight synchronization.
 Non-blocking send, blocking receive:
• The sender may continue executing; the receiver is blocked until the requested message
arrives. It allows a process to send message to a variety of destination as quickly as possible.
e.g. A server process provides services/ resources to other process; these processes are
blocked until they receive services/resources requested.
 Non-blocking send, Non-blocking receive:
• Neither party is required to wait; they continue executing.

In mutual exclusion assume the use of the non-blocking send, blocking receive.
• A set of processes share a mailbox, mutex which is used by all processes to send and receive.
• The mailbox initially contains a null message.

85
Producer-Consumer Bounded Buffer: Message Passing
typedef char *mesg;
const int capacity = 100; // buffering capacity
int i;

void producer() void consumer()

{ {
message pmsg; //message from producer message cmsg; //message from consumer
while (TRUE) while (TRUE)
{ {
receive(mayproduce, pmsg); receive(mayconsume, cmsg); //receive from mailbox
pmsg = produce(); //produce message consume(cmsg) //consume message
send(mayconsume, pmsg); //send to consume send(mayproduce, null); //send null to mayproduce
} }
} }

86
…Producer-Consumer Bounded Buffer: Message Passing
void main()
{
create_mailbox(mayproduce); // producer-mailbox
create_mailbox(mayconsume); // consumer-mailbox
for(int i =1; i <= capacity; i++)
send(mayproduce, null);// fill mayproduce with null
parbegin(producer, consumer);
}

87
…Producer-Consumer Bounded Buffer: Message Passing
 The producer produces message only when it finds a null in mayproduce
mailbox.
 The message produced by producer is sent to mayconsume mailbox
(messages are queued).
 The consumer executes only when there are messages produced into
mayconsume.
 The message is consumed and null is sent to mayproduce again.
 Whenever produces receives a null message; it adds one to the total
numbers of messages it can produce.
 Initially, ‘capacity’ null messages are sent, so producer can produce
‘capacity’ messages.
 After consuming, the consumer sends a null message and now producer can
produce one more message.
88
Assignment Questions
1. Define following Terms: Mutual Exclusion, Critical Section, Race Condition
2. What is Semaphore? Provide the implementation of Readers-Writers Problem
using Semaphore
3. What is Semaphore? Provide the implementation of Bounded Buffer
Producer Consumer Problem using Semaphore.
4. Solve barbershop problem with monitors.
5. Consider the dining philosophers problem. If we add a 6th chopstick to the
center of the table, have we cured the deadlock problem? If yes, what
condition have we removed? If no, explain why not.
6. What is Critical section Problem and list the requirements to solve it. Write
Peterson’s Solution for the same.
7. Write short note on message passing.
8. Explain monitor with an example.
89
Thank
You