Unit III

Introduction to Process Synchronization

Process Synchronization is a mechanism in operating systems used to manage the execution of

multiple processes that access shared resources. Its main purpose is to ensure data consistency,
prevent race conditions and avoid deadlocks in a multi-process environment.

On the basis of synchronization, processes are categorized as one of the following two types:
 Independent Process: The execution of one process does not affect the execution of other
processes.
 Cooperative Process: A process that can affect or be affected by other processes executing
in the system.

Process Synchronization is the coordination of multiple cooperating processes in a system to

ensure controlled access to shared resources, thereby preventing race conditions and other
synchronization problems.
Improper Synchronization in Inter Process Communication Environment leads to following
problems:
1. Inconsistency: When two or more processes access shared data at the same time without
proper synchronization. This can lead to conflicting changes, where one process’s update
is overwritten by another, causing the data to become unreliable and incorrect.
2. Loss of Data: Loss of data occurs when multiple processes try to write or modify the
same shared resource without coordination. If one process overwrites the data before
another process finishes, important information can be lost, leading to incomplete or
corrupted data.
3. Deadlock: Lack of proper Synchronization leads to Deadlock which means that two or
more processes get stuck, each waiting for the other to release a resource. Because none of
the processes can continue, the system becomes unresponsive and none of the processes
can complete their tasks.

Role of Synchronization in IPC

1. Preventing Race Conditions: Ensures processes don’t access shared data at the same
time, avoiding inconsistent results.
2. Mutual Exclusion: Allows only one process in the critical section at a time.
3. Process Coordination: Lets processes wait for specific conditions (e.g., producer-
consumer).
4. Deadlock Prevention: Avoids circular waits and indefinite blocking by using proper
resource handling.
5. Safe Communication: Ensures data/messages between processes are sent, received and
processed in order.
6. Fairness: Prevents starvation by giving all processes fair access to resources.
Conditions That Require Process Synchronization

1. Critical Section: A critical section is a code segment that can be accessed by only one
process at a time. The critical section contains shared variables that need to be synchronized to
maintain the consistency of data variables. So the critical section problem means designing a
way for cooperative processes to access shared resources without creating data inconsistencies.

2. Race Condition: A race condition is a situation that may occur inside a critical section. This
happens when the result of multiple process/thread execution in the critical section differs
according to the order in which the threads execute.

3. Pre-emption: Preemption is when the operating system stops a running process to give the
CPU to another process. This allows the system to make sure that important tasks get enough
CPU time. This is important as mainly issues arise when a process has not finished its job on
shared resource and got preempted. The other process might end up reading an inconsistent
value if process synchronization is not done.

Critical Section in Synchronization

A critical section is a part of a program where shared resources (like memory, files, or
variables) are accessed by multiple processes or threads. To avoid problems such as race
conditions and data inconsistency, only one process/thread should execute the critical section
at a time using synchronization techniques. This ensures that operations on shared resources
are performed safely and predictably.
Structure of a Critical Section
1. Entry Section
 The process requests permission to enter the critical section.
 Synchronization tools (e.g., mutex, semaphore) are used to control access.
2. Critical Section: The actual code where shared resources are accessed or modified.
3. Exit Section: The process releases the lock or semaphore, allowing other processes to enter
the critical section.
4. Remainder Section: The rest of the program that does not involve shared resource access.

Critical Section Problem

Shared Resources and Race Conditions
 Shared resources include memory, global variables, files, and databases.
 A race condition occurs when two or more processes attempt to update shared data at the
same time, leading to unexpected results. Example: Two bank transactions modifying the
same account balance simultaneously without synchronization may lead to incorrect final
balance.
Requirements of Critical Section Solutions
1. Mutual Exclusion
 At most one process can be inside the critical section at a time.
 Prevents conflicts by ensuring no two processes update the shared resource
simultaneously.
2. Progress
 If no process is in the critical section, and some processes want to enter, the choice of
who enters next should not be postponed indefinitely.
 Ensures that the system continues to make progress rather than getting stuck.
3. Bounded Waiting
 There must be a limit on how long a process waits before it gets a chance to enter the
critical section.
 Prevents starvation, where one process is repeatedly bypassed while others get to
execute.
Examples of critical sections in real-world applications

Banking System (ATM or Online Banking)

 Critical Section: Updating an account balance during a deposit or withdrawal.
 Issue if not handled: Two simultaneous withdrawals could result in an incorrect final
balance due to race conditions.
Ticket Booking System (Airlines, Movies, Trains)
 Critical Section: Reserving the last available seat.
 Issue if not handled: Two users may be shown the same available seat and both may book
it, leading to overbooking.
Print Spooler in a Networked Printer
 Critical Section: Sending print jobs to the printer queue.
 Issue if not handled: Print jobs may get mixed up or skipped if multiple users send jobs
simultaneously.
File Editing in Shared Documents (e.g., Google Docs, MS Word with shared access)
 Critical Section: Saving or writing to the shared document.
 Issue if not handled: Simultaneous edits could lead to conflicting versions or data loss.

Semaphores in Process Synchronization

In multiprogramming systems, multiple processes may need to access shared resources like
files, printers, or memory. To handle this, operating systems use synchronization mechanisms.
One of the most widely used mechanisms is the Semaphore.
A Semaphore is simply a variable (integer) used to control access to a shared resource by
multiple processes in a concurrent system. It ensures that only the allowed number of processes
can use a resource at a given time.
A semaphore works using two fundamental operations:
1. Wait (P operation / down)
 Decreases the semaphore value.
 If the value becomes negative, the process is blocked until the resource becomes available.
2. Signal (V operation / up)
 Increases the semaphore value.
 If there are waiting processes, one of them gets unblocked.

Types of Semaphores
Semaphores are mainly of two Types:
1. Counting Semaphore
 Used when multiple instances of a resource exist.
 The semaphore value can range over an unrestricted domain (0 to N).
 Example: Managing access to a pool of 5 printers.
2. Binary Semaphore
 Special case of counting semaphore with only two values: 0 and 1.
 Works like a lock: either the resource is free (1) or busy (0).
 Example: Managing access to a single critical section.

Classical IPC Problems

Inter-Process Communication (IPC) allows processes to share data and coordinate tasks.
However, when multiple processes interact, problems such as synchronization errors, resource
conflicts, and deadlocks can occur. These challenges are often studied through classical IPC
problems, which provide models for understanding and solving real-world issues in operating
systems.
The main problems include:
1. Producer-Consumer Problem – managing shared buffers without overflow or underflow.
2. Readers-Writers Problem – balancing concurrent reads and exclusive writes.
3. Dining Philosophers Problem – preventing deadlock and starvation in shared resource
usage.
4. Sleeping Barber Problem – handling synchronization and fairness in service systems.
These problems highlight the need for proper synchronization techniques like semaphores,
mutexes, and monitors.
Producer-Consumer Problem
This problem involves two processes:
 Producer: generates data and adds it to a buffer.
 Consumer: removes data from the buffer for processing.
Challenges:
 Buffer Overflow – producer tries to add when the buffer is full.
 Buffer Underflow – consumer tries to remove when the buffer is empty.
Solution: Use synchronization tools like semaphores or mutexes to ensure controlled access to
the buffer.
Reader-Writer Problem
Here, multiple processes read and write to a shared resource.
 Readers: only read the data.
 Writers: modify the data.
Challenges:
 Allow many readers to access simultaneously.
 Ensure that only one writer writes at a time.
 Prevent readers from reading while a writer is writing.
Solutions:
 Readers Preference – give readers priority, making writers wait.
 Writers Preference – give writers priority, ensuring timely updates.
Dining Philosophers Problem
This problem models philosophers seated around a table, each needing two chopsticks to eat.
Chopsticks are shared between neighbors, creating potential conflicts.
Challenges:
 Deadlock – if all philosophers pick up one chopstick and wait for the other.
 Starvation – some philosophers may never get to eat.
Solution: Use semaphores or monitors to coordinate chopstick use and avoid deadlock.
4. Sleeping Barber Problem
In a barber shop:
 If no customers are present, the barber sleeps.
 If customers arrive and seats are available, they wait.
 If all seats are full, new customers leave.
Challenges:
 Prevent deadlock where no one gets served.
 Ensure fairness so no customer starves waiting too long.
Solution: Semaphores can manage customer queues, chair availability, and barber activity.
Introduction of Deadlock in Operating System
A deadlock is a situation in a computing environment where a set of processes gets
permanently stuck because each process is waiting for a resource held by another process, and
none of them can proceed.
How Does Deadlock Occur in OS?
A process in an operating system typically uses resources in the following sequence:
 Request a resource
 Use the resource
 Release the resource
Deadlock arises when processes hold some resources while waiting for others.
Example:
 Process P1 holds Resource R1 and requests R2.
 Process P2 holds Resource R2 and requests R1.
Neither process can proceed causing a deadlock.
Necessary Conditions for Deadlock in OS
Deadlock can arise if the following four conditions hold simultaneously (Necessary
Conditions)
1. Mutual Exclusion: Only one process can use a resource at any given time i.e. the
resources are non-sharable.
2. Hold and Wait: A process is holding at least one resource at a time and is waiting to
acquire other resources held by some other process.
3. No Preemption: A resource cannot be taken from a process unless the process releases
the resource.
4. Circular Wait: set of processes are waiting for each other in a circular fashion. For
example, imagine four processes P1, P2, P3, and P4 and four resources R1, R2, R3,
 and R4.

4. The above image demonstrates a circular wait deadlock, here's how:

 P1 is holding R1 and waiting for R2 (which is held by P2).
 P2 is holding R2 and waiting for R3 (which is held by P3).
 P3 is holding R3 and waiting for R4 (which is held by P4).
 P4 is holding R4 and waiting for R1 (which is held by P1).
 Handling Deadlocks
Methods of Handling Deadlocks
There are four approaches to dealing with deadlocks.

1. Deadlock Prevention
Deadlock prevention is a strategy used in computer systems to ensure that different processes
can run smoothly without getting stuck waiting for each other forever. Think of it like a traffic
system where cars (processes) must move through intersections (resources) without getting
into a gridlock.
As we have already discussed that deadlock can only happen if all four of the following
conditions are met simultaneously:
 Mutual Exclusion
 Hold and Wait
 No Preemption
 Circular Wait
Eliminate Mutual Exclusion
 Some resources, like a printer, are inherently non-sharable, so this condition is difficult to
break.
 However, sharable resources like read-only files can be accessed by multiple processes at
the same time.
 For non-sharable resources, prevention through this method is not possible.
2. Eliminate Hold and Wait
Hold and wait is a condition in which a process holds one resource while simultaneously
waiting for another resource that is being held by a different process. The process cannot
continue until it gets all the required resources.
There are two ways to eliminate hold and wait:
 By eliminating wait: The process specifies the resources it requires in advance so that it
does not have to wait for allocation after execution starts.
For Example, Process1 declares in advance that it requires both Resource1 and Resource2.
 By eliminating hold: The process has to release all resources it is currently holding
before making a new request.
For Example: Process1 must release Resource2 and Resource3 before requesting
Resource1.
3. Eliminate No Preemption
No preemption means resources can’t be taken away once allocated. To prevent this:
 Processes must release resources voluntarily: A process gives up resources once it
finishes using them.
 Avoid partial allocation: If a process requests resources that are unavailable, it must
release all currently held resources and wait until all required resources are free.
4. Eliminate Circular Wait
Circular wait happens when processes form a cycle, each waiting for a resource held by the
next. To prevent this:
 Impose a strict ordering on resources.
 Assign each resource a unique number.
 Processes can only request resources in increasing order of their numbers.
 This prevents cycles, as no process can go backwards in numbering.
2. Deadlock Avoidance
Deadlock Avoidance is a method where the operating system makes decisions dynamically to
ensure the system never enters an unsafe state, thereby avoiding the possibility of deadlock.
This is usually done using algorithms like the Banker’s Algorithm.
Deadlock avoidance mainly relies on algorithms that check resource allocation before making
decisions. The two common types are:
1. Banker’s Algorithm: Used when multiple instances of resources exist. It simulates
allocation and ensures that the system remains in a safe state before granting resources.
2. Resource Allocation Graph (RAG) Algorithm: Used when each resource has only one
instance. It checks for cycles in the graph to avoid unsafe states.

Deadlock Detection & Recovery

Deadlock Detection: Deadlock detection periodically checks for circular waits and resolves
deadlocks by aborting and restarting processes, releasing their resources. It allows unrestricted
resource access and immediate request fulfillment, enabling online handling. The main
drawback is potential loss due to preemption.
Deadlock Recovery is the process of handling a deadlock after it has occurred. It involves:
1. Process Termination: Aborting one or more deadlocked processes to break the cycle.
2. Resource Preemption: Temporarily taking resources from some processes and
reallocating them to others.
Deadlock Detection
1. If Resources Have a Single Instance
In this case for Deadlock detection, we can run an algorithm to check for the cycle in the
Resource Allocation Graph. The presence of a cycle in the graph is a sufficient condition for
deadlock.
In this diagram, resource 1 and resource 2 have single instances. There is a cycle R1 → P1 →
R2 → P2. So, Deadlock is Confirmed.
2. If There are Multiple Instances of Resources
Detection of the cycle is necessary but not a sufficient condition for deadlock detection, in
this case, the system may or may not be in deadlock varies according to different situations.
For systems with multiple instances of resources, algorithms like Banker's Algorithm can be
adapted to periodically check for deadlocks.
3. Wait-For Graph Algorithm
The Wait-For Graph Algorithm is a deadlock detection algorithm used to detect deadlocks in
a system where resources can have multiple instances. The algorithm works by constructing a
Wait-For Graph, which is a directed graph that represents the dependencies between processes
and resources.
Deadlock Recovery
A traditional operating system such as Windows doesn't deal with deadlock recovery as it is a
time and space-consuming process. Real-time operating systems use Deadlock recovery.

 Killing The Process: Killing all the processes involved in the deadlock. Killing process
one by one. After killing each process check for deadlock again and keep repeating the
process till the system recovers from deadlock. Killing all the processes one by one helps a
system to break circular wait conditions.
 Process Rollback: Rollback deadlocked processes to a previously saved state where the
deadlock condition did not exist. It requires check pointing to periodically save the state of
processes.
 Resource Preemption: Resources are preempted from the processes involved in the
deadlock, and preempted resources are allocated to other processes so that there is a
possibility of recovering the system from the deadlock. In this case, the system goes into
starvation.

 Concurrency Control: Concurrency control mechanisms are used to prevent data

inconsistencies in systems with multiple concurrent processes. These mechanisms ensure
that concurrent processes do not access the same data at the same time, which can lead to
inconsistencies and errors. Deadlocks can occur in concurrent systems when two or more
processes are blocked, waiting for each other to release the resources they need. This can
result in a system-wide stall, where no process can make progress. Concurrency control
mechanisms can help prevent deadlocks by managing access to shared resources and
ensuring that concurrent processes do not interfere with each other.
Deadlock Ignorance
The Deadlock Ignorance strategy simply assumes:
 That deadlocks are so rare that it is not worth the cost of preventing or detecting them.
 If a deadlock does occur, the operating system may take drastic measures such as rebooting
to recover.
 This approach is called the Ostrich Algorithm, because it resembles the ostrich burying its
head in the sand and pretending the problem doesn’t exist.
Why Use Deadlock Ignorance?
1. Rarity of Deadlocks:
 Deadlocks occur very rarely in well-designed programs.
 Other failures (hardware crashes, software bugs, compiler errors) are much more common.
 Engineers prefer to spend effort on frequent problems rather than rare ones.
2. High Overhead of Handling:
 Deadlock prevention/avoidance requires keeping track of resource allocation graphs,
running detection cycles or restricting process behavior.
 These add significant time and space overhead.
 For most users, ignoring deadlock makes the OS faster and simpler.
3. Practical Philosophy:
 For personal computers or single-user systems, rebooting after a rare deadlock is
acceptable.
 For mission-critical systems (e.g., banking, aviation, medical devices), this strategy is not
suitable.