OPERATING SYSTEM

CHAPTER – 3
PROCESS SYNCHRONISATION

Prof. Sayed faizal

Assistant Professor
Topics to be covered
• IPC, Race Conditions, Critical Section, Mutual Exclusion
• Hardware Solution
• Strict Alternation
• Dekker’s Algorithm
• Peterson’s Solution
• The Producer Consumer Problem
• Semaphores
• Event Counters
• Monitors
• Classical IPC Problems:
• Reader’s & Writer Problem
• Dinning Philosopher Problem
• Pipes and Message Passing
• Barrier and Signal
Inter process communication (IPC)
• Processes in a system can be independent or cooperating.
1. Independent process cannot affect or be affected by the execution of
another process.
2. Cooperating process can affect or be affected by the execution of another
process.

• Cooperating processes need inter process communication

mechanisms.
Inter process communication (IPC)

• Reasons of process cooperation

1.Information sharing
2.Computation speed-up
3.Modularity
4.Convenience

• Issues of process cooperation

• Data corruption, deadlocks, increased complexity
• Requires processes to synchronize their processing
 Models for Inter Process Communication (IPC)
• There are two models for IPC
a.Message Passing (Process A send the message to Kernel and then Kernel send that message to
Process B)
b.Shared Memory (Process A put the message into Shared Memory and then Process B read that
message from Shared Memory)
Race Condition
• Race Condition:
• 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.
Example of Race Condition
• Print spooler directory example : Two processes want to access
shared memory at the same time.
 Example of Race Condition
• Process A • Process A
next_free_slot = in next_free_slot = in (7)
Write file name at slot (7) Context Switch
next_free_slot += 1
• Process B
in = next_free_slot (8)
next_free_slot = in (7) on
di ti
C1o n
Write file name at slot (7)
Context Switch next_free_slot
a c e+=
R
in = next_free_slot (8)
Context Switch
• Process B
next_free_slot = in • Process A
Write file name at slot (8) Write file name at slot (7)
next_free_slot += 1 next_free_slot += 1
in = next_free_slot (9) in = next_free_slot (8)
Basic Definitions

• Race Condition: Situations like this where processes access the same data
concurrently and the outcome of execution depends on the particular order
in which the access takes place is called a race condition. OR

• Situation where two or more processes are reading or writing some shared
data and the final result depends on who runs precisely when.

• Reasons for Race Condition

1. Exact instruction execution order cannot be predicted
2. Resource (file, memory, data etc…) sharing
Basic Definitions
• Inter Process Communication: It is a communication between two or
more processes.
Basic Definitions
• Inter Process Communication: It is a communication between two or
more processes.
 Basic Definitions
• Inter Process Communication: It is a communication between two or
more processes.
Send message

P1 P3

P2
Basic Definitions
• Critical Section:
 Basic Definitions

• Critical Section: The part of program where the shared resource is

accessed is called critical section or critical region.
A enters in critical region A leaves critical region
Process A
B attempt to enter B enters in critical B leaves critical
region region
Process B
T1 T2 B Blocked T3 T4
 Basic Definitions
• 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.
Solving Critical-Section Problem

Any good solution to the problem must satisfy following four conditions:
1. Mutual Exclusion
• No two processes may be simultaneously inside the same critical section.
2. Bounded Waiting
• No process should have to wait forever to enter a critical section.
3. Progress
• No process running outside its critical region may block other processes.
4. Arbitrary Speed
• No assumption can be made about the relative speed of different processes
(though all processes have a non-zero speed).
Mutual exclusion with busy waiting
• Mechanisms for achieving mutual exclusion with busy waiting
1. Disabling interrupts (Hardware approach)
2. Shared lock variable (Software approach)
3. Strict alteration (Software approach)
4. TSL (Test and Set Lock) instruction (Hardware approach)
5. Exchange instruction (Hardware approach)
6. Dekker’s solution (Software approach)
7. Peterson’s solution (Software approach)
 Disabling interrupts
• while (true)
{
< disable interrupts >;
< critical section >;
< enable interrupts >;
< remainder section>; < critical section > < remainder section>
< disable interrupts > < enable interrupts >
}
Process A

Process B
T1 T3 T4
Disabling interrupts
• Problems:
• Unattractive or unwise to give user processes the power to turn off
interrupts.
• What if one of them 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.
Shared lock variable
• 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.
 Shared lock variable
• Algorithm:
• while (true)
{ < set shared variable to 1>;
< critical section >;
< set shared variable
<set lock to 1>
to 0>;
< critical section >
<set lock to 0>
< remainder section>

< remainder section>;

Process A
}
Process B
T1 T3 T4
Shared lock variable
• Problem:
• If process P0 sees the value of lock variable 0 and before it can set it to 1
context switch occurs.
• Now process P1 runs and finds value of lock variable 0, so it sets value to 1,
enters critical region.
• At some point of time P0 resumes, sets the value of lock variable to 1,
enters critical region.
• Now two processes are in their critical regions accessing the same shared
memory, which violates the mutual exclusion condition.
Strict Alteration
• 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.
 Strict Alteration (Algorithm)
Process 0 Process 1
while (TRUE) while (TRUE)
{ {
while (turn != 0) /* loop */ ; while (turn != 1) /* loop */ ;
critical_region(); critical_region();
turn = 1; turn = 0;
noncritical_region(); noncritical_region();
} }

0 0 0 1 0 0
0 enters in critical region 0 leaves critical region
Process 0
1 attempt to enter 1 enters in critical 1 leaves critical 1 attempt to
region region enter
Process 1
T1 T2 1 Busy Wait T3 T4 T5 1 Busy Wait
Strict Alteration (Disadvantages)
• Taking turns is not a good idea when one of the processes is much
slower than the other.
 Strict Alteration (Disadvantages)
 Consider the following situation for two processes P0 and P1.
 P0 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.
0P0 and0 P1 are now 0in non-critical region.
1 0 0 1
0 enters in critical region 0 leaves critical region
Process 0
1 attempt to enter 1 enters in critical 1 leaves critical
region region
Process 1
 Strict Alteration (Disadvantages)
 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 attempt to
enter

0 0 0 1 0 0 1
0 enters in critical region 0 leaves critical region
Process 0
1 attempt to enter 1 enters in critical 1 leaves critical
region region
Process 1
 TSL (Test and Set Lock) Instruction
• Algorithm
enter_region: (Before entering its critical region, process calls enter_region)
TSL REGISTER,LOCK |copy lock variable to register set lock to 1
CMP REGISTER,#0 |was lock variable 0?
JNE enter_region |if it was nonzero, lock was set, so loop
RET |return to caller: critical region entered
Register 0
leave_region: (When process wants to leave critical region, it calls leave_region)
Process A
MOVE LOCK,#0 |store 0 in lock variable
Process BRET
T1 |return to caller T3 T4
The TSL Instruction
• 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.
Exchange Instruction
• Algorithm
enter_region: (Before entering its critical region, process calls enter_region)
MOVE REGISTER,#1 |put 1 in the register
XCHG REGISTER,LOCK |swap content of register & lock variable
CMP REGISTER,#0 |was lock variable 0?
JNE enter_region |if it was nonzero, lock was set, so loop
RET |return to caller: critical region entered
leave_region: (When process wants to leave critical region, it calls leave_region)
MOVE LOCK,#0 |store 0 in lock variable
RET |return to caller
Dekker’s Algorithm
P0 P1

variables
wants_to_enter [2]: array of 2 booleans
P0 P1
turn : integer 0 0
0
wants_to_enter[0] ← false
wants_to_enter[1] ← false
turn ← 0 // or 1
P0:Dekker’s Algorithm
wants_to_enter[0] ← true
P0
0
1
P1
0
P1:
wants_to_enter[1] ← true
while (wants_to_enter[1]) while (wants_to_enter[0])
{if (turn == 1) {if (turn == 0)
{wants_to_enter[0] ← false {wants_to_enter[1] ← false
while (turn == 1) while (turn == 0)
{// busy wait} {// busy wait}
wants_to_enter[0] ← true wants_to_enter[1] ← true
} }
} }
// critical section // critical section
... 1 ...
turn ← 1 P0 P1 turn ← 0
0 0
wants_to_enter[0] ← false wants_to_enter[1] ← false
// remainder section // remainder section
P0:Dekker’s Algorithm
wants_to_enter[0] ← true
P0
10
P1
1
P1:
wants_to_enter[1] ← true
while (wants_to_enter[1]) while (wants_to_enter[0])
{if (turn == 1) 1 {if (turn == 0)
{wants_to_enter[0] ← false 0 1 {wants_to_enter[1] ← false
while (turn == 1) 1 while (turn == 0)
{// busy wait} {// busy wait}
wants_to_enter[0] ← true 1 0 wants_to_enter[1] ← true
} }
} }
// critical section // critical section
... ...
turn ← 1 turn ← 0
wants_to_enter[0] ← false wants_to_enter[1] ← false
// remainder section // remainder section
Peterson’s Solution
#define FALSE 0 P0 P1 P0 P1
0 1
#define TRUE 1 0 0 1 0
#define N 2 //number of processes
int turn; //whose turn is it?
int interested[N]; //all values initially 0 (FALSE)
void enter_region(int process)
{ 1 0
int other; // number of the other process 1 0 1 1
other = 1 - process; // the opposite process
interested[process] = TRUE; // this process is interested 0 1
turn = process; // set flag
while(turn == process && interested[other] == TRUE); // wait
}
void leave_region(int process)
{ 0 1
interested[process] = FALSE; // process leaves critical region
}
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.
Priority inversion problem
• 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 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. This
situation is called priority inversion problem.
Mutual Exclusion with Busy Waiting
1. Disabling Interrupts
• is not appropriate as a general mutual exclusion mechanism for user processes
2. Lock Variables
• contains exactly the same fatal flaw that we saw in the spooler directory
3. Strict Alternation
• process running outside its critical region blocks other processes.
4. Peterson's Solution
5. The TSL/XCHG instruction
• Both Peterson’s solution and the solutions using TSL or XCHG are correct.
• Limitations:
i. Busy Waiting: this approach waste CPU time
ii. Priority Inversion Problem: a low-priority process blocks a higher-priority one
Sleep and Wakeup
• Peterson’s solution and solution using TSL and XCHG 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.
Sleep and Wakeup
 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.
 Both 'sleep' and 'wakeup' system calls have one parameter that represents a
memory address used to match up 'sleeps' and 'wakeups'.
 Producer Consumer
• It is multi-process synchronization
problem
problem.
• It is also known as bounded buffer
Producer Buffer Consumer
problem.
• This problem describes two processes
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)
What Producer Consumer problem is?
• The problem is to make sure that the producer won’t try to add data
(information) into the buffer if it is full and consumer won’t try to
remove data (information) from the an empty buffer.
• Solution for producer:
• Producer either go to sleep or discard data if the buffer is full.
• Once the consumer removes an item from the buffer, it notifies (wakeups)
the producer to put the data into buffer.
• Solution for consumer:
• Consumer can go to sleep if the buffer is empty.
• Once the producer puts data into buffer, it notifies (wakeups) the consumer
to remove (use) data from buffer.
 What Producer
• Buffer is empty
Consumer problem is?
• Producer want to produce √
• Consumer want to consume X
Producer Buffer Consumer
• Buffer is full
• Producer want to produce X
• Consumer want to consume √
• Buffer is partial filled
• Producer want to produce √
• Consumer want to consume √
 Producer Consumer problem using Sleep & Wakeup
#define N 4
int count=0;
count 10
void producer (void)
item Item 1
{ int item;
while (true) {
Producer Buffer Consumer
item=produce_item();
1
if (count==N) sleep();
2
insert_item(item);
3
count=count+1; 4
if(count==1) wakeup(consumer);
}
}
 Producer Consumer
void consumer (void)
problem using Sleep & Wakeup
{ int item;
count 10
while (true)
item
{
if (count==0) sleep();
Producer Buffer Consumer
item=remove_item();
1 Item 1
count=count-1;
2
if(count==N-1)
3
wakeup(producer); 4
consume_item(item);
}
}
Problem in Sleep & Wakeup
• Problem with this solution is that it contains a race condition that can
lead to a deadlock. (How???)
 Problem in Sleep & Wakeup
 The consumer has just read the variable
void consumer (void)
count, noticed it's zero and is just about to
move inside the if block. { int item;
 Just before calling sleep, the consumer is while (true)
Context Switching
suspended and the producer is resumed. {
 The producer creates an item, puts it into if (count==0) sleep();
the buffer, and increases count.
item=remove_item();
 Because the buffer was empty prior to the
last addition, the producer tries to wake up count=count-1;
the consumer. if(count==N-1)
wakeup(producer);
consume_item(item);
}
}
 Problem in Sleep & Wakeup
 Unfortunately the consumer wasn't yet
void consumer (void)
sleeping, and the wakeup call is lost.
 When the consumer resumes, it goes to sleep
{ int item;
and will never be awakened again. This is while (true)
because the consumer is only awakened by the {
producer when count is equal to 1.
if (count==0) sleep();
 The producer will loop until the buffer is full,
after which it will also go to sleep. item=remove_item();
• Finally, both the processes will sleep forever. count=count-1;
This solution therefore is unsatisfactory. if(count==N-1)
wakeup(producer);
consume_item(item);
}
}
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:
1. Binary semaphores :-
• Binary semaphores can take only 2 values (0/1).
• Binary semaphores have 2 methods associated with it (up, down / lock, unlock).
• They are used to acquire locks.
2. Counting semaphores :-
• Counting semaphore can have possible values more than two.
Semaphore (cont…)
• We want functions insert _item and remove_item such that the
following hold:
1. Mutually exclusive access to buffer: At any time only one process should be
executing (either insert_item or remove_item).
2. 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).
3. 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).
Semaphore (cont…)
• We want functions insert _item and remove_item such that the
following hold:
4. No busy waiting.
5. No producer starvation: A process does not wait forever at insert_item()
provided the buffer repeatedly becomes full.
6. No consumer starvation: A process does not wait forever at remove_item()
provided the buffer repeatedly becomes empty.
Semaphores
Two operations on semaphores are defined.
1. Down Operation
• The down operation on a semaphore checks to see if the value is greater than 0.
• If so, it decrements the value and just continues.
• If the value is 0, the process is put to sleep without completing the down for the
moment.
• Checking the value, changing it, and possibly going to sleep, are all done as a single,
indivisible atomic action.
• It is guaranteed that once a semaphore operation has started, no other process can
access the semaphore until the operation has completed or blocked.
Semaphores
Two operations on semaphores are defined.
2. Up Operation
• The up operation increments the value of the semaphore addressed.
• If one or more processes were sleeping on that semaphore, unable to
complete an earlier down operation, one of them is chosen by the system
(e.g., at random) and is allowed to complete its down.
• The operation of incrementing the semaphore and waking up one process is
also indivisible.
• No process ever blocks doing an up, just as no process ever blocks doing a
wakeup in the earlier model.
 Producer Consumer problem using Semaphore
#define N 4
typedef int semaphore; mutex 1
0
semaphore mutex=1;
semaphore empty=N; empty 43
semaphore full=0;
void producer (void) full 0
1
{ int item;
while (true) item Item 1
{
item=produce_item();
down(&empty); Producer Buffer Consumer
down(&mutex); 1
insert_item(item); 2
up(&mutex);
3
up(&full);
4
}
}
 Producer Consumer
void consumer (void)
problem using Semaphore
mutex 0
1
{ int item;
while (true) empty 43
{ full 01
down(&full);
item
down(&mutex);
item=remove_item(item);
Producer Buffer Consumer
up(&mutex);
1 Item 1
up(&empty);
2
consume_item(item); 3
} 4

}
Readers Writer problem
• In the readers and writers problem, many competing processes are
wishing to perform reading and writing operations in a 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 P1
have access
P2
toP3the database, not even
readers.
Read X Read X

Write Write Write

X X

DATABASE
Readers Writer problem
• In the readers and writers problem, many competing processes are
wishing to perform reading and writing operations in a 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 P1
have access
P2
toP3the database, not even
readers.
Read Read √ Read √

Write Write
X X

DATABASE
Readers Writer problem
• In the readers and writers problem, many competing processes are
wishing to perform reading and writing operations in a database.
• It is acceptable to have multiple processes reading the database at
the same time, but if one process is updating (writing) the database,
Need to keep track of read of
no other processes may P1
have access
P2
to the
P3
database,
more thannot evenat a
one process
readers. time

Read Read √ Read √

3 Reader_count

DATABASE
Readers Writer problem using Semaphore

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

 Readers Writer problem using Semaphore
void Reader (void)
{ while (true){
down(&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
down(&db) //prevent writer process to access DB
up(&mutex) //allow other process to access reader_count
read_database();
down(&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
up(&db) //leave the control of DB, allow writer process
up(&mutex) //allow other process to access reader_count
use_read_data();} //use data read from DB (non-critical)
}
Readers Writer problem using Semaphore

void Writer (void)

{ while (true){
create_data(); //create data to enter into DB (non-critical)

down(&db); //gain access to DB

write_db(); //write information to DB

up(&db);} //release exclusive access to DB

}
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.
• 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.
Monitor
• Monitors have an important property 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.
Producer Consumer problem using Monitor

• The solution proposes condition variables, along with 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, 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.
Producer Consumer problem using Monitor

• This other process the consumer, can wake up its sleeping partner by
doing a signal on the condition variable that its partner is waiting on.
• To avoid having two active processes in the monitor at the same time
a signal statement may appear only as the final statement in a
monitor procedure.
• If a signal is done on a condition variable on which several processes
are waiting, only one of them, determined by the system scheduler, is
revived.
Producer Consumer problem using Monitor
monitor ProducerConsumer
condition full, empty;
integer count;

procedure insert (item:integer);

begin
if count=N then wait (full);
insert_item(item);
count=count+1;
if count=1 then signal (empty);
Producer Consumer problem using Monitor

function remove:integer;
begin
if count=0 then wait (empty);
remove=remove_item;
count=count-1;
if count=N-1 then signal (full);
end;
count=0;
end monitor;
Producer Consumer problem using Monitor
procedure producer;
begin
while true do
begin
item=produce_item;
ProducerConsumer.insert(item);
end;
end;

procedure consumer;
begin
while true do
begin
item=ProducerConsumer.remove;
Consume_insert(item);
end;
end;
Mutex
• Mutex is the short form for ‘Mutual Exclusion Object’.
• A Mutex and the binary semaphore are essentially the same.
• Both Mutex and the binary semaphore can take values: 0 or 1.
mutex_lock:
TSL REGISTER,MUTEX |copy Mutex to register and set Mutex to 1
CMP REGISTERS, #0 |was Mutex zero?
JZE ok |if it was zero, Mutex was unlocked, so return
CALL thread_yield |Mutex is busy; schedule another thread
JMP mutex_lock |try again later
ok: RET |return to caller; critical region entered

mutex_unlock:
MOVE MUTEX,#0 |store a 0 in Mutex
RET |return to caller
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.
Pipes
• Accessed by two associated file descriptors:
• fd[0] for reading from pipe
• fd[1] for writing into the pipe
Pipes
#include<unistd.h>
int pipe(int pipedes[2]);

• This system call would create a pipe for one-way communication i.e.,
it creates two descriptors, first one is connected to read from the
pipe and other one is connected to write into the pipe.
• Descriptor pipedes[0] is for reading and pipedes[1] is for writing.
Whatever is written into pipedes[1] can be read from pipedes[0].
• This call would return zero on success and -1 in case of failure.
 Pipes
#include<unistd.h>
#include<fcntl.h> Header files
#include<stdion.h>
char *message = “Hey how are you” /* Message created */
main ()
{
char buffer[1024]; /* Size of buffer is 1024 */
int fd[2]; /* Created array of size 2 for 2 process (file descriptor) */
pipe(fd); /* Created pipe; passed array (fd) in pipe system call */
if (fork() != 0) /* Parent code */
{ write (fd[1], message, strlen (message) + 1); }
else /* Child code */
{ read (fd[0], buffer, 1024);
printf (“Received from Parent %s\n”, buffer); }
}
 Pipes
#include<unistd.h> Parent process #include<unistd.h> Child process
#include<fcntl.h> #include<fcntl.h>
#include<stdion.h> #include<stdion.h> pid = 3000
char *message = “Hey how are you” char *message = “Hey how are you” main ()
main () {
{ char buffer[1024];
char buffer[1024]; int fd[2];
int fd[2]; pipe(fd);
pipe(fd); if (fork != 0) /* Parent code */
if (fork()
3000!= 0) /* Parent code */ { write0(fd[1], message,
{ write (fd[1], message, strlen (message) + 1); }
strlen (message) + 1); } else /* Child code */
else /* Child code */ { read (fd[0], buffer, 1024);
{ read (fd[0], buffer, 1024); printf (“Received from Parent %s\n”,
printf (“Received from Parent %s\n”, buffer); }
buffer); } }
}
Message Passing
• This method will use two primitives
1. Send: It is used to send message.
• Send (destination, &message)
• In above syntax destination is the process to which sender want to send message and
message is what the sender wants to send.
2. Receive: It is used to receive message.
• Receive (source, &message)
• In above syntax source is the process that has send message and message is what the
sender has sent.
Producer Consumer problem using message passing

#define N 100 //number of slots in buffer

void producer (void)

{
int item;
message m; //message buffer

while (true)
{
item=produce_item(); //generate something to put in buffer
receive(consumer, &m); //wait for an empty to arrive
build_message(&m, item); //construct a message to send
Producer Consumer problem using message passing

void consumer (void)

{
int item, i;
message m;
for (i=0; i<N; i++) send (producer, &m);//send N empties
while (true)
{
receive (producer, &m); //get message containing item
item=extract_item(&m); //extract item from message
send (producer, &m); //send back empty reply
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.
Solution to 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

Solution to Dinning Philosopher Problem
void take_forks (int i) //i: philosopher no, from 0 to N-1
{
down(&mutex);//enter critical region
state[i]=HUNGRY; //record fact that philosopher i is hungry
test(i); //try to acquire 2 forks
up(&mutex); //exit critical region
down(&s[i]);//block if forks were not acquired
}

void put_forks (int i) //i: philosopher no, from 0 to N-1

{
down(&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
up(&mutex); //exit critical region
}
Solution to Dinning Philosopher Problem
void test (i) //i: philosopher no, from 0 to N-1
{
if (state[i]==HUNGRY &&
state[LEFT]!=EATING &&
state[RIGHT]!=EATING)
{
state[i]=EATING;
up (&s[i]);
}
}
 Barrier
• In this mechanism some application are
divided into phases and have that rule that
no process may proceed into the next phase
A
until all process completed in this phase and
are ready to proceed to the next phase.

Barrier
• This behaviour is achieved by placing barrier B

at the end of each phase.

• When a process reaches the barrier, it is C

blocked until all processes have reach at the

barrier. D

• There are four processes with a barrier.

Time
 Barrier
• Processes A, B and D are completed and
process C is still not completed so until
process C will complete, process A, B and D
A
will not start in next phase.

Barrier
B

Time
 Barrier
• Once process C completes all the process
start in next phase.
A

Barrier
B

Time
Signal
• Signals are software interrupts sent to a program to indicate that an
important event has occurred.
• When a signal is delivered to a process, the process will stop what
its doing, either handle or ignore the signal.
• Signals are similar to interrupts, the difference being that interrupts
are mediated by the processor and handled by the kernel while
signals are mediated by the kernel (possibly via system calls) and
handled by processes.
• The kernel may pass an interrupt as a signal to the process that
caused it (examples are SIGSEGV, SIGBUS, SIGILL and SIGFPE).
Questions asked in GTU
1. Define following Terms: Mutual Exclusion, Critical Section, Race
Condition
2. What is Semaphore? Give the implementation of Readers-Writers
Problem using Semaphore
3. What is Semaphore? Give the implementation of Bounded Buffer
Producer Consumer Problem using Semaphore.
4. Explain Dining philosopher solution using Semaphore.
5. What Critical section Problem and list the requirements to solve it.
Write Peterson’s Solution for the same.
6. Explain Dining philosopher solution using Monitors.
88