Unit 3

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 51

Unit 3:Inter Process Communication

Reference : Operating System Concepts By Galvin


Modern Operating System By Tanenbaum
https://onlinecourses.nptel.ac.in/noc16_cs10/preview
Contents
• Race Conditions, Critical Section, Co-operating Thread/ Mutual
Exclusion
• Hardware Solution, Strict Alternation, Peterson’s Solution
• The Producer Consumer Problem, Semaphores, Event Counters,
Monitors
• Message Passing and Classical IPC Problems: Reader’s & Writer
Problem, Dinning Philosopher Problem.
Inter Process Communication
• Types of Process: Independent & Cooperating Process
IPC
• What is IPC?
• Videos\Interprocess Communication.mp4
• Advantage of IPC:
• Information sharing
• Modularity
• Computational Speed
• Convenience
• Two Ways:
• Shared Memory
• Message Passing
Scenario
Critical Section:
A situation where several
processes access and manipulate
Program 0 Program 1
the same data

{ Int Counter=5 {
Counter++; Counter--;
} Shared Variable }

1. What will be the out put if these two program executes?


Race Condition
• The outcome depends on the order in which the access take place.

• Prevent Race Condition:


• By Synchronization
• Ensure only once process at a time manipulates the critical data

• No more than one process should execute in critical section at a time.

• Race Condition in Multicore.


Solution for Critical Section Problem
Solution should satisfy the following requirements:
1. Mutual Exclusion:
• No two process may be simultaneously inside their critical region.

2. Progress:
• No process running outside its critical region may block other processes.

3. No starvation(Bounded wait):
• No process should have to wait forever to enter its critical region.
Proposals for achieving Mutual Exclusion
 Disabling Interrupts
 Lock variables
 Strict Alteration
 Peterson’s solution
 TSL instruction
1. Disabling Interrupts
• When Interrupts are disabled, context switch won’t happen.
• Requires privileges:
• User process generally cannot disable interrupts.
• Disadvantage:
• Not suited for multicore systems
• Process has power to disable the interrupt. (If process does not turned it on?)
Process 1 Process 2

{ {
Disable Interrupts() Disable Interrupts()
Critical section Critical section
enable Interrupts() enable Interrupts()
} }
2. Lock Variables
• Shared Lock variable, initially 0.
• When a process wants to enter its critical region, it first tests the lock.
• If the lock is 0, the process sets it to 1 and enters the critical region.

• 0 means, no process is in its critical region.


• 1 means, some process is in its critical region.

• Violate the Mutual Exclusion.


• Suppose process1 reads the lock as 0 and tries to set as 1.Process 2
sets the lock to 1 mean time. (2 processes end up in critical section.)
3. Strict Alternation
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_region; Non-critical_region;
} }

• Initially turn=0.
• Violates Progress
• Busy Waiting: Continuously testing a variable until some value appears.
• Waste CPU cycle
• Spin lock:Lock that uses busy waiting.
4. Peterson’s Solution
Hardware Locks: TSL(Test and Set Lock)

• TSL instruction locks the memory bus to prohibit others from accessing
memory until it is done.
Intel x86 CPUs use XCHG instruction
Sleep and Wakeup
Why Sleep and Wakeup?
•Solution of Busy waiting(Waste CPU Cycle).

•Priority Inversion Problem:


• H= High Priority process, L=Low Priority process.
• H will run whenever it is in ready state.
• L in its critical region, H becomes ready to run. H now begins busy waiting, but since L is
never scheduled while H is running, L never gets the chance to leave its critical region, So
H Loops forever.

•Sleep is system call which blocks the caller, that is, be suspended until
another process wakes it up.
Producer-Consumer Problem(Bounded Buffer
Problem)
• We have a buffer of fixed size.

• A producer can produce an item and can place


in the buffer.

• A consumer can pick items and can consume


them.

• We need to ensure that when a producer is


placing an item in the buffer, then at the same
time consumer should not consume any item.

• In this problem, buffer is the critical section.


Producer-Consumer Problem (Bounded Buffer
Problem)
Missing Wakeup call:
• Buffer is empty.
• Consumer checks value of count which
is 0.
• Before sleep the producer generate item
and increment count by 1 and execute
the wakeup system call.
• Now consumer will execute sleep
system and mean while producer fill up
the buffer and go to sleep.
• Both will sleep forever.

Context Switch
Semaphore
• Semaphore is a variable is used to solve critical section problem and
to achieve process synchronization in the multi processing
environment.
• The two most common kinds of semaphores
• Counting semaphore can take non-negative integer values
• Binary semaphore can take the value 0 & 1. only.
Semaphore
• 2 operations on Semaphores:
• P operation is also called wait, sleep or down operation
• V operation is also called signal, wake-up or up operation.
• Both operations are atomic and semaphore(s) is always initialized to one.
• A critical section is surrounded by both operations to implement
process synchronization.

• Uses of Semaphores:
• Achieve Mutual Exclusion
• Deciding order of execution
• Managing Resource
Semaphore Implementation
Void down(int *s) Void up(int *s)
{ {
while(*s<=0); *s++;
*s--; }
}

• Could now have busy waiting in critical section implementation


Semaphore Implementation with no Busy
waiting
• With each semaphore there is an associated waiting queue
• Each entry in a waiting queue has two data items:
• value (of type integer)
• pointer to next record in the list
• Two operations:
• block – place the process invoking the operation on the appropriate waiting
queue
• wakeup – remove one of processes in the waiting queue and place it in the
ready queue
Semaphore Implementation with no Busy
waiting
wait(semaphore *S) { signal(semaphore *S) {
S->value--; S->value++;
if (S->value < 0) { if (S->value <= 0) {
add this process to remove a process P
S->list; from S->list;
block(); wakeup(P);
} }
} }
Bounded buffer problem
• n buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0
• Semaphore empty initialized to the value n
Producer Consumer using Semaphore
1;
N;
0;

Void producer (void) Void consumer (void)


{ int item; { int item;
While(TRUE){ While(TRUE){
item = produce_item(); down(&full);
down(&empty); down(&mutex);
down(&mutex); item = remove_item();
insert_item(item); up(&mutex);
up(&mutex); up(&empty);
up(&full); consume_item(item);
} }
} }
Structure of producer consumer problem
Producer Consumer
do {
do {
...
/* produce an item in wait(full);
next_produced */ wait(mutex);
...
... /* remove an item from buffer
wait(empty); to next_consumed */
wait(mutex); ...
signal(mutex);
...
signal(empty);
/* add next produced to the
buffer */ ...
/* consume the item in next
... consumed */
signal(mutex); ...
signal(full); } while (true);
} while (true);
Gate Example
• A shared variable x, initialized to zero, is operated by four process w,
x, y, z. Process w and x increment x by one, while process y, z
decrement x by two. Each process before reading perform ‘wait’ on
semaphore ‘s’ and signal on ‘s’ after store. If semaphore ‘s’ initialized
to two, find what is the maximum possible value of x if all process
complete execution?

• Answer: 2
Gate Example
• A counting semaphore was initialized to 10. Then 6 P (wait)
operations and 4V (signal) operations were completed on this
semaphore. The resulting value of the semaphore is
• (a) 0    (b) 8     (c) 10     (d) 12

Ans: option(b)
Gate Example
•  The following program consists of 3 concurrent processes and 3 binary
semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

Process P0 Process P1 Process P2 How many times will process


P0 print '0'?
while (true) wait (S1);
{ Release (S0);
wait (S2);
release (S0);
(a)At least twice
wait (S0); (b)Exactly twice
print (0);
release (S1); (c) Exactly thrice
release (S2); (d) Exactly once
}

Ans: option (a)


Problems with semaphores
• Deadlock – two or more processes are waiting indefinitely for an
event that can be caused by only one of the waiting processes
• Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);
• Starvation – indefinite blocking
Classical IPC Problem: 2.Reader Writer
Problem
 A data set is shared among a
number of concurrent processes
• Readers – only read the data
set; they do not perform any
Reader
updates
• Writers – can both read and
Writer Reader
write Reader
• Problem – allow multiple readers to
read at the same time
• Only one single writer can
access the shared data at the
same time
• Several variations of how readers
and writers are considered – all
involve some form of priorities
Reader Writer Problem Solution
• Writer process:
• Writer requests the entry to critical section.
• If allowed i.e. wait() gives a true value, it enters and performs the write. If not allowed, it
keeps on waiting.
• It exits the critical section.
• Reader process:
• Reader requests the entry to critical section.
• If allowed:
• it increments the count of number of readers inside the critical section. If this reader is
the first reader entering, it locks the wrt semaphore to restrict the entry of writers if any
reader is inside.
• It then, signals mutex as any other reader is allowed to enter while others are already
reading.
• After performing reading, it exits the critical section. When exiting, it checks if no more
reader is inside, it signals the semaphore “wrt” as now, writer can enter the critical
section.
• If not allowed, it keeps on waiting.
Reader Writer Problem Solution using
semaphore
typedef int semaphore;
semaphore mutex = 1; /* controls access to rc */
semaphore wrt = 1; /* controls access to the database write*/
int rc = 0; /* # no of processes reading*/

void writer(void) void reader(void)


{ {
while (TRUE) { while (TRUE) {
down(&mutex);
down(&wrt); rc = rc + 1;
write data base( ); if (rc == 1)
up(&wrt); down(&wrt);
} up(&mutex);
} read data base( );
down(&mutex);
rc = rc −1;
if (rc == 0)
up(&wrt);
up(&mutex);
}
}
Classical IPC Problem: 3.Dining
Philosophers
Develop an Algorithm where no
philosopher starves.

Thinking

OR

Eating
#define N 5 /* #philosophers */
First Try void philosopher(int i) /* i: from 0 to 4 */
{
while (TRUE) {
4 think( ); /* Thinking */
take fork(i); /* take right fork */
take fork((i+1) % N); /* take left fork*/
eat( ); /* Eating*/
put fork((i+1) % N); /* put left fork */
put fork(i); /* put right fork*/
4 0 0 }
3 }
3 Problems
1
2 :
1.What happens if only philosopher 0 and 2 are always
given the priority?
P1, P3 and P4 starves.
2.What happens if all philosophers pick up right forks at a
2 same time?
1
Circular Wait (Deadlock).
#define N 5 /* #philosophers */

Second Try
void philosopher(int i) /* i: from 0 to 4 */
{
while (TRUE) {
think( );
take fork(i); /*Right Fork*/
4 if(available(take fork((i+1) % N)) { /*left fork available*/
take fork((i+1) % N); /*Left Fork*/
eat();
put fork((i+1) % N);
put fork(i);
}
4 0 0 else{ put fork(i);
3 Sleep(Time); /*sleep for some time*/
}
3 }
1
2 }
Problem:
All Philosophers start at the same time , Run
simultaneously and think for the same time.
This could lead to philosophers taking fork and putting it
2 1 down continuously. Deadlock
Solution using #define N 5
semaphore mutex =1 ;
/* #philosophers */

Mutex void philosopher(int i)


{
/* i: from 0 to 4 */

while (TRUE) {
4 think( ); /* Thinking */
wait(mutex);
take fork(i); /* take right fork */
take fork((i+1) % N); /* take left fork*/
eat( ); /* Eating*/
put fork((i+1) % N); /* put left fork */
0 0 put fork(i); /* put right fork*/
4
signal(mutex);
3 }
3
1 }
2
Problem:
 Only one philosopher can eat at a time.

2 1
Solution using Semaphore
A Philosopher can only move to EATING state if neither neighbour is eating.

• All S[ ] semaphore are initialized to 0.


• Philosopher has 3 states: HUNGRY, EATING, THINKING
void philosopher(int i) { void test(i){
while (TRUE) { if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=
think( ); /* Thinking */ EATING) { state[i] = EATING;
take forks(i); /* acquire forks or block */ up(&s[i]);
eat( ); /* Eating*/ }
put forks(i); /* put forks back */ }
}}
void take forks(int i) { void put forks(i){
down(&mutex); /* enter critical region */ down(&mutex); /* enter critical region */
state[i] = HUNGRY; /* philosopher i is hungry */ state[i] = THINKING; /* finished eating */
test(i); /* try to acquire 2 forks */ test(LEFT); /* see if left neighbour can now eat
up(&mutex); /* exit critical region */ */
down(&s[i]); /* block if forks were not acquired */ test(RIGHT); /* see if right neighbour can now eat
} */
up(&mutex); /* exit critical region */
What happens if P3 is eating now and P4 arrives? }
Monitor
• To make it easier to write correct synchronization programs, Brinch
Hansen (1973) and Hoare(1974) proposed a higher-level
synchronization primitive called a monitor.

• A monitor is a collection of procedures, variables, and data structures


that are all grouped together in a special kind of module or package.

• Processes may call the procedures in a monitor whenever they want


to, but they cannot directly access the monitor’s internal data
structures from procedures declared outside the monitor.
Structure of Monitor
monitor example
integer i;
condition c;
procedure producer( );
...
end;
procedure consumer( );
...
end;
end monitor;
Monitors have an important property that
makes them useful for achieving mutual
exclusion:
• only one process can be active in a monitor at any instant.

• when a process calls a monitor procedure, the first few instructions of


the procedure will check to see if any other process is currently active
within the monitor. If so, the calling process will be suspended until
the other process has left the monitor.

• If no other process is using the monitor, the calling process may enter.
Condition variables in Monitor
• We can perform two operations on them, wait and signal.

• When a monitor procedure discovers that it cannot continue (e.g., the


producer finds the buffer full), it does a wait on some condition
variable, say, full. This action causes the calling process to block.

• It also allows another process that had been previously prohibited


from entering the monitor to enter now.
Continue…
• The other process, can wake up its sleeping partner by doing a signal
on the condition variable that its partner is waiting on.

• if a condition variable is signaled with no one waiting on it, the signal


is lost forever. In other words, the wait must come before the signal.
Producer Consumer using Monitor
Message Passing
• This method of interprocess communication uses two primitives, send
and receive.
• send(destination, &message);
• receive(source, &message);

• The former call sends a message to a given destination and the latter
one receives a message from a given source.

• If no message is available, the receiver can block until one


arrives(Blocking). Alternatively, it can return immediately with an
error code(Non Blocking).
Design Issues for Message Passing system
• If the communicating processes are on different machines connected
by a network. For example, messages can be lost by the network.

• What happens if the message is received correctly, but the


acknowledgement back to the sender is lost. The sender will
retransmit the message, so the receiver will get it twice.

• How processes are named, so that the process specified in a send or


receive call is unambiguous.
Continue…
• Authentication is also an issue in message systems: how can the
client tell that it is communicating with the real file server, and not
with an imposter?

• When the sender and receiver are on the same machine. One of
these is performance. Copying messages from one process to another
is always slower than doing a semaphore operation or entering a
monitor.
Producer Consumer using Message Passing
#define N 100 /* number of slots void consumer(void)
in the buffer */ {
void producer(void){ int item, i;
int item; message m;
message m; /* message buffer */ for (i = 0; i < N; i++)
while (TRUE) { send(producer, &m);
item = produce item( ); while (TRUE) {
receive(consumer,&m); receive(producer,&m);
build message(&m, item); item = extract item(&m);
send(consumer,&m); send(producer,&m);
} consume item(item);
} }
Any
Questions

You might also like