Process Synchronization:

Synchronization:
The critical section problem;
Peterson’s solution;
Synchronization hardware;
Semaphores;
Classical problems
of synchronization
 Race condition

● Race Condition: A situation where several processes access and

manipulate the same data concurrently and the outcome of the
execution depends on the particular order in which the access takes
place is called a Race Condition.

● Concurrent access: Multiple processes try to read and write to the

same data at the same time.
● Unpredictable outcome: The final result depends on the specific,
unpredictable order in which the processes complete their operations.
● Example: Imagine two people trying to withdraw money from the
same bank account at the same time. If the first person's balance is
checked and updated, but before their change is saved, the second
person's withdrawal is also processed, the final balance could be
incorrect because it doesn't account for the first person's transaction.
● Critical section problems
● Critical section : is a code segment that can be accessed by only one
process at a time.
Consider a system consisting of n processes {Po, P1 , ... ,Pn-1}.
Each process has a segment of code, called a critical section in which
the process may be changing common variables, updating a table,
writing a file, and soon.
when one process is executing in its critical section, no other process
is to be allowed to execute in its critical section.
● The general structure of a typical process

Entry section

Critical section

Exit section
 Requirements/Conditions for Solving Critical Section
Problem

● [Link] 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.
Define critical section ? What are the requirements or
conditions for the solution to critical section problems.
Briefly explain Peterson's Solution.
 Peterson's Solution

● Peterson's solution is a classic algorithm for solving the critical section

problem for two processes.
● It uses shared variables to coordinate access.
● Shared Variables
int turn;
boolean flag[2];
● A classic algorithm for 2 processes to solve the critical section problem
we have two processes, P0 and P1.
P0
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);// Critical Section
flag[0] = false;

P1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);// Critical Section

flag[1] = false ;
● Synchronization Hardware : Specialized hardware instructions that
help solve synchronization problems.
Examples:
1. Test-and-Set: Atomically tests and sets a value.
2. Compare-and-Swap: Compares and swaps values if equal.
3. Fetch-and-Add: Atomically increments a value.
These instructions help implement locks and other synchronization
primitives efficiently.
1. Test-and-Set: Checks if a value is 0, sets it to 1 if so. Returns old
value.
2. Compare-and-Swap: If value == expected, sets it to new. Returns old
value.
3. Fetch-and-Add: Returns current value and adds a number to it. All
atomically
 Semaphores

● Variable that controls access to shared resources

● Types :
Binary semaphore : 0 & 1
Counting semaphore : any non-negative integer
Operations :
wait(s)
signal(s)
Classical Problems
1. Bounded Buffer:
2. Dining Philosophers:
3 Readers-Writers:
● The hardware solution to the critical section problem is complicated
for application programmers to use
To overcome this difficulty we use synchronization tool called
semaphore.
● Semaphore S – integer variable apart from initialization it can be
accessed and modified only by two operations wait() and signal()
● What are semaphores? List any 3 application of semaphores
● Semaphore is an integer variable, is used in mutual exclusive manner
by various concurrent cooperative processes in order to achieve
synchronization.
● Apart from semaphores initialization it can be accessed and modified
only by two operations
● wait() and signal().

Application of Semaphore
1. Semaphore is used to solve critical section problem
2. Semaphore is used to decide the order of execution among the
processes.(synchronization)
3. Resource management
Definition of wait() and signal()
wait (S)
{
while (S <= 0); // no-op
S--;
}
signal (S)
{
S++;
}
 TYPES OF SEMAPHORES
● Explain binary and counting semaphores with examples.
1. Counting semaphore
2. Binary semaphore

● Explain the usage of semaphores. Counting Semaphore

● Explain how semaphore is used to handle resource management.
● Handling Resource management
● It is mainly used in resource management. The value of a counting
semaphore can range over an unrestricted domain. Counting
semaphores can be used to control access to a given resource
consisting of finite number of instances.
● The semaphore is initialized to the number of resources available.
Each process that wishes to use a resource performs a wait()
operation on the semaphore (thereby decrementing the count).
● When a process releases a resource, it performs a signal() operation
(incrementing the count). When the count for the semaphore goes to
0, all resources are being used. After that, processes that wish to use a
resource will block until the count becomes greater than 0.
● Binary Semaphore
The value of a semaphore can range only between 0 and 1.
On some systems, binary semaphores are known as mutex locks, as
they are locks that provide mutual-exclusion.

● Solving Critical-section Problem using Binary Semaphores.

(OR)
Explain how semaphore is used to solve critical section problem
Binary semaphores can be used to solve the critical-section problem
for multiple processes.
Mutual-exclusion implementation with semaphores
● The ‘n’ processes share semaphore Mutex which is initialized to 1
● Explanation: Whichever the process interested to enter critical section,
say P1 must execute the wait (mutex) at its entry section.
● Mutex is decremented by 1, if its value is > 0 and process P1 enters
into CS. Now the Mutex value = 0. When P1 is inside the CS, if P2
attempts to enter CS by executing wait (mutex).
● Since the mutex value is 0, the while (mutex<=0) statement results in
true and blocks process P1 in entry section. Thus the mutual exclusion
property is ensured.
● Explain how semaphore is used to solve synchronization problem
● Semaphores can also be used to solve synchronization problems.
● For example, consider 2 concurrently running-processes: P1 with a
statement S1 and P2 with a statement S2. Suppose we require that S2
be executed only after S1 has completed. We can implement this
scheme readily by letting P1 and P2 to share a common semaphore
synch initialized to 0, and by inserting the following statements in
process P1
S1:
signal(synch)
and the following statements in process P2
wait(synch) S2;
Since synch is initialized to 0, P2 will execute S2 only after P1 has
invoked signal (synch),
which is after statement S1 has been executed.
● What are the advantages of semaphore?
1. Semaphores allow only one process into the critical section.
2. Semaphores follow mutual exclusion principle strictly.
3. Semaphores are much more efficient than some other methods of
synchronization

● Disadvantage of semaphore is Busy waiting.

● What is busy waiting in critical section concept? OR
What is spinlock?
While a process is in its critical-section, any other process that tries to
enter its critical- section must loop continuously in the entry-code, and
this situation in critical section problem is called busy waiting.
Busy waiting wastes CPU cycles that some other process might be
able to use productively. This type of semaphore is also called a
spinlock (because the process "spins" while waiting for the lock).
● Explain implementation of semaphore
To overcome busy waiting, we can modify the definition of the wait()
and signal() as follows: When a process executes the wait() and finds
that the semaphore-value is not positive, it must wait. However, rather
than engaging in busy waiting, the process can blockitself.
A process that is blocked (waiting on a semaphore S) should be
restarted when someother process executes a signal(). The process
is restarted by awakeup().

● Assume 2 simple operations:

1) block() suspends the process that invokes it.
2) wakeup(P) resumes the execution of a blocked process P. We
define a semaphore as follows:
typedef struct
{
int value ;
Struct process *list;
}
semaphore ;
● Implementation of wait( )
wait (S)
{
value--;
if (value <0)
{
add this process to waiting queue
block();
}
}
● Implementation of signal( )

signal(S)
{
value++;
if (value <=0)
{
Remove a process P from the waiting queue
wakeup(P);
}
}
 BOUNDED-BUFFER PROBLEM

● Give a solution to the bounded buffer problem using semaphores.

Write the structure of producer and consumer processes

● The bounded-buffer problem is related to the producer consumer

problem. There is a pool of n buffers, each capable of holding one

item .
● Shared data :
int n;
semaphore mutex =1;
semaphore empty = n;
semaphore null = 0;
● The mutex semaphores provide mutual exclusion for access to the
buffer pool and is initialized to the value 1

● empty and full semaphores are used to count the number of empty
and full items in buffer respectively.

● Initially empty = n; full=0

● The symmetry between the producer and the consumer is ensured by

the producer producing full items in buffers for the consumer and the
consumer produces empty buffers for the producer.
● The structure of the producer process
while (true)
{
// produce an item wait (empty);
wait (mutex);
// add the item to the buffer signal (mutex);
signal (full);
}
● The structure of the consumer process
while (true)
{
wait (full); wait (mutex);
// remove an item from buffer signal (mutex);
signal (empty);
// consume the removed item
}
 READERS WRITERS PROBLEM

● In cooperative process a data set is shared among a number of

concurrent processes. In readers arbiters problem:

● Readers are the processes which want to only read the database (DB).

● Writers are the processes which want to update (i.e. to read & write)
the DB.

● The actual problem in Readers Writers problem is, if 2 readers can

access the shared-DB simultaneously without any problems. However,
if a writer & other process (either a reader or a writer) access the
shared-DB simultaneously, problems may arise.
● Shared data
semaphore mutex , wrt ;
int readcount ;

Where,
mutex is used to ensure mutual-exclusion when the variable readcount
is updated.
wrt is common to both reader and writer processes.
wrt is used as a mutual-exclusion semaphore for the writers. Also wrt
is used by the first/last reader that enters/exits the critical-section.
readcount counts the number of processes currently reading the
object.
● Initialization
mutex = 1, wrt = 1, readcount = 0

● The structure of a writer process

while (true)
{
wait (wrt) ;
// writing is performed
signal (wrt) ;
}
● The structure of a reader process
while (true)
{
wait (mutex) ;
readcount ++ ;
if (readcount == 1) then wait (wrt) ; signal (mutex)
// reading is performed
wait (mutex) ;
readcount - - ;
if (readcount == 0) then signal (wrt) ; signal (mutex) ;
}
 THE DINING-PHILOSOPHERS PROBLEM

● Problem objective: To allocate several resources among several

processes in a deadlock-free & starvation-free manner.
● Solution using semaphore:
Represent each chopstick with a semaphore; chopstick[5]
A philosopher tries to grab a chopstick by executing a wait( ) on the
semaphore.
The philosopher releases her chopsticks by executing the signal( ) on
the semaphores.
This solution guarantees that no two neighbors are eating
simultaneously.
 Shared-data:
semaphore chopstick[5];
Initialization
chopstick[5]={1,1,1,1,1}
● The structure of Dining- Philosopher i with semaphore solution:
do
{
wait (chopstick[i] );
wait (chopstick[ (i + 1) % 5] );
// eat
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
}
while (TRUE);
● Disadvantage of Dining Philosopher problem with semaphore:
Deadlock may occur if all 5 philosophers become hungry
simultaneously and grab their left chopstick.
When each philosopher tries to grab her right chopstick, she will be
delayed forever.
Three possible remedies to the deadlock problem:
● 1) Allow at most 4 philosophers to be sitting simultaneously at the
table.
● 2) Allow a philosopher to pick up her chopsticks only if both
chopsticks are available.
● 3) Use an asymmetric solution; i.e. an odd philosopher picks up first
her left chopstick and then her right chopstick, whereas an even
philosopher picks up her right chopstick and then her left chopstick.
Define semaphore develop a c program to simulate
producer consumer problem using semaphore.
 Deadlocks

● A deadlock is a situation where two or more processes are blocked

indefinitely, each waiting for the other to release a resource.

● Conditions for Deadlock

1. Mutual Exclusion: Resources are non-shareable.
[Link] and Wait: Processes hold resources while waiting for others.
3. No Preemption: Resources can't be forcely taken away.
4. Circular Wait: Processes wait for each other in a cycle.
● Preventing Deadlock
1. Avoid Mutual Exclusion: Make resources shareable if possible.
2. Request all resources at once: Avoid holding some resources while
waiting for others.
3. Allow Preemption: Take resources away if needed.
4. Order resources: Ensure processes request resources in a specific
order to avoid circular wait.