PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
CRITICAL SECTION PROBLEM
✓Consider a system consisting of n processes {P0 , P1, P2, …, Pn-1}
✓Each process has a segment of code, called a critical section, in which
the process may be accessing – and updating – data that is shared
with at least one other process.
✓The important feature of the system is that, when one processs is
executing in its critical section, no other process is allowed to execute
in its critical section.
✓That is, no two processes is allowed to execute in its critical sections at the
same time. The critical-section problem is to design a protocol that the
processes can use to synchronize their activity so as to cooperatively shared
data.
✓Each process must request permission to enter its critical section. The section
of code implementing this request is the entry section. The critical section may
be followed by an exit section. The remaining code is the remainder section.
Figure General structure of a typical process
A SOLUTION TO THE CRITICAL SECTION PROBLEM
➢Must satisfy the following three requirements :
1. Mutual exclusion : If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections.
2. Progress : If no process is executing in its critical section and some processes wish to
enter their critical sections, then only those processes that are not executing in their
remainder sections can participate in deciding which will enter its critical section next,
and this selection cannot be postponed indefinitely
3. Bounded waiting : There exists a bound, or limit, on the number of times that other
processes are allowed to enter their critical sections after a process has made a
request to enter its critical section and before that request is granted.
PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
MUTEX IN OPERATING SYSTEM
✓Mutex lock in OS is essentially a variable that is binary nature that’s provides
code wise functionality for mutual exclusion. At times, there maybe multiple
threads that may be trying to access same resource like memory or I/O etc. to
make sure that there is no overriding. Mutex provides a locking mechanism.
✓Only one thread at a time can take the ownership of a mutex and apply the
lock. Once it done utilizing the resource and it may release the mutex lock.
MUTEX HIGHLIGHTS
➢Mutex is very different from Semaphores
1. Mutex is binary in nature
2. Operations like Lock and Release are possible
3. Mutex is for Threads, while Semaphores are for processes
4. Mutex works in user-space and Semaphore for Kernel
5. Mutex provides Locking mechanism
6. A thread may require more than one mutex
7. Binary semaphore and mutex are different
PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
SEMAPHORE
SEMAPHORE USES SIGNALLING MECHANISM TO ALLOW ACCESS TO
SHARED RESOURCES NAMEDLY BY TWO –
1. WAIT
2. SIGNAL
THERE ARE TWO TYPES OF SEMAPHORES :
1. BINARY SEMAPHORE – ONLY TRUE/FALSE OR 1/0 VALUES
2. COUNTING SEMAPHORES – NON-NEGATIVE VALUE
SEMAPHORE IMPLEMENTATION
Semaphore can have two different operations which are wait and
signal. In some books wait signals are also denoted by P(s) and signal
by V(s). Where s is a common semaphore.
Wait p(s) or wait(s) : Wait decrements the value of semaphore by 1
Signal v(s) or signal(s) : Signal increments the value of semaphore by 1
SEMAPHORE
1. Semaphore can only have non-negative values
2. Before that start of the program, it is always initialized to
✓n in Counting semaphore (where n is the number of processes
allowed to enter critical section simultaneously)
✓1 in the case of a binary semaphore.
SIGNAL OPERATIONS
✓Signal operation is simple
✓It increments the value of semaphore by 1 as shown below
Signal(s) {
s++;
}
WAIT OPERATIONS
✓Wait operation decrements the value of semaphore s if s is a positive
number
✓Else if s is 0 or negative then code gets stuck at while loop as it keeps
implementing infinitively
✓The semi-colon after while forces while loop definitely if s is 0 or negative
✓Thus the code doesn’t move ahead in hopes that the value of s will
increase because of some other signal operation elsewhere
WAIT OPERATIONS
Code Logic for Incrementing – Decrementing value of semaphore
wait(s) {
while(s <= 0) ;
s--;
}
➢Actual working for both functions together to achieve access of critical
section
// some code
wait(s);
// critical section code
signal(s);
// remainder code
The eventual goal is to protect the critical section code using wait and
signal operations.
To visualize the whole operation on how the semaphore system works
with the example below :
➢ FOR COUNTING SEMAPHORE
WE INITIALIZE THE VALUE OF SEMAPHORE AS THE NUMBER OF
CONCURRENT ACCESS OF CRITICAL SECTIONS WE WANT TO ALLOW
PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
READERS – WRITERS PROBLEM IN OS
✓If a database or file is to be shared among several concurrent process,
there can be broadly 2 types of users –
➢Readers – Readers are those processes/users which only read the data
➢Writers – Writers are those processes which also write, that is, they
change the data
It is allowed for 2 or more readers to access shared data, simultaneously as
they are not making any change and even after the reading the file format
remains the same
READERS – WRITERS PROBLEM IN OS
But if one Writer (say W1) is editing or writing the file then it should locked
and no other writer (say W2) can make any changes until W1 has finished
writing the file.
Writers are given to be exclusive access to shared database while writing to
database. This is called Reader’s writer problem.
HIGHLIGHTS
✓If Writer W1 has begun writing process then
• No additional writer can perform write function
• No Reader is allowed to read
✓If 1 or more Readers are reading then
• Other Readers may read as well
• No Writer may perform write function until all Readers have finished
reading
EXPLANATIONS
✓In simple terms understand this as unlimited number of Readers can
read simultaneously. Only one Writer can write at a time.
✓When a Writer is writing no other Writer can write to the file. A
Writer can not write when there are one or more than one reader
reading. That is Writer can only write when there is no Readers or
no Writers accessing the resource.
READERS – WRITERS PROBLEM
READERS – WRITERS PROBLEM
READERS – WRITERS PROBLEM
SOLUTION
➢Variables used –
1. Mutex – mutex (used for mutual exclusion, when read count is
changed)
✓Initialized as 1
2. Semaphore – wrt (used by both readers and writers)
✓Initialized as 1
✓readers_count – Counter of number of people reading the file
✓Initialized as 0
FUNCTIONS
THERE ARE TWO FUNCTIONS
1. wait( ) – performs as --, which basically decrements value of
semaphore
2. signal( ) – performs as ++, which basically increments value of
semaphore
HOW DOES WAIT AND SIGNAL WORK
✓How atomic operations wait and signal work
✓Wait and Signal Implementing
WRITER PROBLEM
WRITER SECTION
1. Writer wants the access to critical section i.e wants to perform the writing
2. First wait(wrt) value is checked
1. If returns true then gets access
1. Does the write process
2. Performs signal(wrt) and increments value
2. If returns false then
1. Does not get write access
READER PROBLEM
READER SECTION
WRITER
✓Mutex Semaphore ensure mutual exclusion when read count is
updated
✓read_count : tracks how many processes are currently reading the
object
✓mutex : Functions as a mutual exclusion semaphore for writers. Also
used by first or last reader that enters or exits the critical section
WRITER
✓If Writer is in critical section and n Readers are waiting, 1 Reader is
queued as mutex. And n-1 Readers are queued or mutex
✓When signal(mutex) is excuted, then one of 2 thing can happen : Either
waiting Readers execute or 1 single writing process is executed. This is
needed by scheduler.
THE SOLUTION TO READER – WRITER PROBLEM
Can be generalized to provide Reader-Writer lock on some system. To
acquire a Reader-Writer lock, one must specify the mode of lock –
either read or write access.
If a process wanting to only read shared data, request reader-writer
lock in read mode. A process waiting to only write on shared data must
request the lock in write mode.
PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
BOUNDED BUFFER PROBLEM IN OS
There are three entities storage
buffer slots, consumer and producer.
The producer tries to store data in the
storage slots while the consumer tries
to remove the data from the buffer
storage.
PROBLEM
The Bounded Buffer problem uses Semaphore.
BOUNDED BUFFER SIGNAL AND WAIT
We need to make that the acces to data buffer is only
either to producer or consumer, i.e when producer is
placing the item in the buffer the consumer should not
consume.
We do that via three entities –
✓ Mutex – used to lock and release critical section
✓ Empty – keeps tab on number empty slots in the
buffer at any given time
• Initialized as n as all slots are empty
✓ Full – keeps tab on number of entities in buffer at any
time.
• Initialized as 0
PRODUCER PROBLEM SOLUTION CONSUMER PROBLEM SOLUTION
PROCESS SYNCHRONIZATION
1. Critical Section Problem ?
2. Mutex Lock ?
3. Semaphore ?
4. Bounded Buffering Problem
5. Reader – Writer Problem
6. Dining Philosopher Problem
DINING PHILOSOPHERS PROBLEM IN OS
Dining philosophers essentially is a process
synchronization example and helps understand how
we can simultaneously utilize common resources of
multiple process together
Entities – Noodles/Rice, Chopticks, Philosophers
Problem Statement
Imagine five philosophers sitting around a circular table
and have a bowl of rice or noodles in the middle and
there are five chopsticks on the table.
At any given instance, a philosopher will do –
✓ Thinking
✓ Eating
✓ Whenever the philosopher want to eat. He
obviously will use two chopticks together.
• So to eat both chopticks on the right and
left must be free
✓ Whenever he is thinking
• He must put down both the chopsticks
back at the table
RULES AND SOLUTION
If a philosopher decides to eat
✓ He first will wait for the chopsticks on his left to be free
✓ If the left chopstick is already free he will pick that up
✓ Then he will wait for the chopstick on his right
✓ And once the right chopstick is also free he will pick that up too and do the
eating
ALGORITHM • Some of the ways to avoid deadlock are as
follows :
• Four Philosopher : there should be at most four
philosophers on the table. In this way one
chopstick will be extra if all decide to eat
together. This one chopstick then can be used by
one of our philosopher and he will finish his
eating and then two chopsticks are available
then 1 more can eat and son …
• Coordination : Only and only if both
chopsticks are available at the same time • Even Odd : Solving with even and odd techniques,
for a philosopher then only he should pick even philosopher must pick his right and off must
them up pick his left.
