Module III: Process and Process Synchronization

1. List the different operations performed on

processes. 2M
*Process Creation
*Process termination
2. . Explain the process of the process creation.
8M
Process Creation
A process may create several new processes. The creating
process is called a parent process, and the new processes are
called the children of that process. Each of these new
processes may in turn create other processes.
Every process has a unique process ID.
On typical Solaris systems, the process at the top of the tree
is the ‘sched’ process with PID of 0.
The ‘sched’ process creates several children processes – init,
pageout and fsflush. Pageout and fsflush are responsible for
managing memory and file systems. The init process with a
PID of 1, serves as a parent process for all user processes.
A process will need certain resources (CPU time, memory,
files, I/O devices) to accomplish its task.
When a process creates a subprocess, the subprocess may be
able to obtain its resources in two ways :
• directly from the operating system
• Subprocess may take the resources of the parent process.
The resource can be taken from parent in two ways –

o The parent may have to partition its resources among its

children
o Share the resources among several children.
There are two options for the parent process after creating
the child:
• Wait for the child process to terminate and then continue
execution. The parent makes a wait() system call.
• Run concurrently with the child, continuing to execute
without waiting.
Two possibilities for the address space of the child relative to
the parent:
• The child may be an exact duplicate of the parent, sharing
the same program and data segments in memory. Each will
have their own PCB, including program counter, registers, and
PID. This is the behaviour of the fork system call in UNIX.
• The child process may have a new program loaded into its
address space, with all new code and data segments. This is
the behaviour of the spawn system calls in Windows.

[Link] a C program to fork a separate process

and explain its working with a neat diagram. 10M
In UNIX OS, a child process can be created by fork() system
call. The fork system call, if successful, returns the PID of the
child process to its parents and returns a zero to the child
process.
If failure, it returns -1 to the parent. Process IDs of current
process or its direct parent can be accessed using the getpid(
) and getppid() system calls respectively.
The parent waits for the child process to complete with the
wait() system call. When the child process completes, the
parent process resumes and completes its execution.
In windows the child process is created using the function
createprocess( ). The createprocess( ) returns 1, if the child is
created and returns 0, if the child is not created.
4. Explain the process of the process termination.
8M
Process termination occurs when a process completes its
execution or is forcibly stopped. Upon termination, the
operating system deallocates all resources used by the
process, including memory, open files, and I/O buffers.
Termination can happen in the following ways:
1. Normal Termination
A process terminates normally when it finishes executing its
last statement and calls the exit() system call. It may return an
exit status (usually an integer) to its parent process. For
example:
exit(1);
2. Termination by Parent Process
A parent process can terminate its child process using system
calls such as TerminateProcess() in Windows. This is usually
allowed only if the terminating process is the parent;
otherwise, processes could kill each other arbitrarily.
A parent may terminate a child for several reasons:
• The child exceeds its resource usage.
• The child’s task is no longer required.
• The parent is exiting, and the system does not allow the
child to continue.
3. Cascading Termination
In some systems, if a parent process terminates, all its
children are automatically terminated. This is known as
cascading termination and is managed by the operating
system.
4. Zombie Process
When a process terminates, it becomes a zombie if its parent
has not yet called wait() to collect its exit status. The process
still occupies an entry in the process table until the parent
retrieves the status using:
pid_t pid;
int status;
pid = wait(&status);
Once wait() is called, the process table entry and process ID
are released.
5. Orphan Process
If a parent process terminates before its child and doesn’t call
wait(), the child becomes an orphan process. In UNIX/Linux
systems, orphan processes are adopted by the init process
(PID 1), which periodically calls wait() to clean up their exit
statuses and prevent zombies.
5. Define the zombie process. 2M
A zombie process is a process that has completed execution
but still has an entry in the process table because its parent
has not yet called the wait() system call to retrieve its exit
status.
Although the process has terminated and its resources have
been deallocated, the operating system retains its process ID
and status information so the parent can collect it. Once the
parent calls wait(), the zombie process is completely removed
from the system.
6. Define the orphan process. 2M
An orphan process is a child process whose parent has
terminated before the child finishes execution. Since the
parent is no longer available to call wait(), the operating
system assigns the orphan process to a special parent
process, typically init (PID 1) in UNIX/Linux systems.
The init process periodically calls wait() to collect the exit
status of orphan processes and ensure they do not remain as
zombies.
7. Define cascading termination. 2M
Cascading termination is a process termination mechanism
where if a parent process terminates, all of its child
processes are automatically terminated by the operating
system.
This prevents child processes from continuing to run without
supervision. Cascading termination is typically used in
systems that do not allow orphan processes.

8. List various UNIX system calls used in the life

span of a process. 2M
 fork() – Creates a new child process by duplicating the
parent.
exec() – Replaces the current process image with a new
program.
wait() / waitpid() – Allows a parent to wait for its child to
finish and collect its exit status.
exit() – Terminates the current process and returns an exit
status to the parent.
getpid() – Returns the process ID of the current process.
getppid() – Returns the parent process ID.
kill() – Sends a signal to a process (e.g., to terminate it).

9. List the models for interprocess

communication. 2M
There are two fundamental models of IPC:
1. Shared Memory Model
o A region of memory is shared between cooperating
processes.
o Processes communicate by reading from and
writing to this shared area.
o Fast access as memory operations are direct once
shared memory is established.
2. Message Passing Model
 o Processes communicate by sending and receiving
messages.
o Suitable for exchanging small amounts of data.
o Easier to implement in distributed systems
10. Explain interprocess communication models
with a neat diagram. 10M
Interprocess Communication Models
Processes executing in an operating system can be either
independent or cooperating. A cooperating process is one
that can affect or be affected by other processes. To enable
such cooperation, an Interprocess Communication (IPC)
mechanism is required.
There are two fundamental models of interprocess
communication:

1. Shared Memory Model

• In this model, a region of memory that is shared by
cooperating processes is established.
• Processes exchange information by reading and writing
data to the shared region.
• Once the shared memory is established using system
calls, all accesses are treated as routine memory
accesses, and no further kernel assistance is required.
 • This model can be faster than message passing, as it
avoids the overhead of system calls during
communication.
However, shared memory suffers from cache coherency
issues, especially on systems with several processing cores.
Shared data may migrate among several caches, which can
reduce performance.

2. Message Passing Model

• In this model, communication takes place via messages
exchanged between cooperating processes.
• Message passing is useful for exchanging smaller
amounts of data, and it is also easier to implement in
distributed systems.
• Message-passing systems typically involve kernel
intervention, as they use system calls to send and
receive messages.
While message passing may involve more overhead due to
kernel involvement, recent research shows that it can
provide better performance than shared memory on multi-
core systems.
11. What are bounded and unbounded buffers?
2M
Bounded Buffer:
• A bounded buffer has a fixed size.
• The producer must wait if the buffer is full, and the
consumer must wait if the buffer is empty.
• It has limited capacity, so synchronization between
producer and consumer is necessary to manage when
items are produced or consumed.
Unbounded Buffer:
• An unbounded buffer has no practical limit on the
number of items it can hold.
 • The producer can always produce new items, and the
consumer may need to wait when there are no items to
consume.
• It has infinite capacity, so there is no need to manage
buffer overflow, but the consumer may still need to
synchronize if there are no items to consume.
12. Define race condition. 2M
A race condition occurs when multiple processes or
threads attempt to access and modify shared resources
concurrently, and the result of this access depends on the
timing or order in which the processes execute. Without
proper synchronization, this can lead to inconsistent or
unpredictable behavior, such as incorrect data or corrupted
system states.
13. Define the Critical section. 2M
A critical section is a segment of a process's code where it
accesses or modifies shared resources, such as variables, data
structures, or files. During the execution of a critical section,
no other process or thread should be allowed to access the
same shared resource to prevent race conditions and ensure
data consistency.
In a multi-process or multi-threaded system, the critical
section is the part of the program that must be protected by
synchronization mechanisms (such as locks, semaphores, or
mutual exclusion) to ensure that only one process or thread
can execute within it at a time.
14. List the different requirements to solve the
critical section problem. 2M
To solve the critical-section problem, the solution must
satisfy the following three requirements:
1. Mutual Exclusion: Only one process can be executing in
its critical section at any given time. No two processes
should be allowed to access shared resources
simultaneously.
2. Progress: If no process is executing in its critical section
and some processes wish to enter their critical sections,
the decision about which process will enter next must be
made without indefinite delay. This means that the
system should not block processes indefinitely.
3. Bounded Waiting: There must be a limit on the number
of times other processes are allowed to enter their
critical sections after a process has requested to enter.
This ensures that a process will not have to wait forever
before it can enter its critical section.
15. How critical section is handled in OS? 2M
In an operating system, critical sections are handled using
synchronization mechanisms to ensure that only one process
or thread can execute in its critical section at a time, thereby
preventing race conditions. These mechanisms include:
1. Locks (Mutexes): A lock is used to enforce mutual
exclusion, allowing only one process to enter the critical
section at a time. When a process enters the critical
 section, it acquires the lock, and when it exits, it releases
the lock.
2. Semaphores: A semaphore is a signaling mechanism
used to manage access to shared resources. It can be
binary (like a lock) or can maintain a count to manage
access for multiple processes.
3. Monitors: A higher-level synchronization construct that
combines mutexes and condition variables, allowing
processes to wait for certain conditions while accessing
shared resources.
4. Peterson’s Solution: In simpler or theoretical systems,
algorithms like Peterson’s solution for two processes are
used to ensure mutual exclusion and handle critical
sections without hardware-based locks.
These mechanisms are implemented by the OS to ensure
mutual exclusion, progress, and bounded waiting, making
sure that shared resources are accessed safely by multiple
processes or threads.

16. Explain the software-based solution to the

critical-section problem / Peterson's solution. 5M
Peterson’s Solution is a classic software-based algorithm
designed to solve the critical-section problem for two
processes, ensuring mutual exclusion, progress, and
bounded waiting. It uses two shared variables to coordinate
the access of two processes (P0 and P1) to their critical
sections.
Requirements:
• The solution assumes two processes, P0 and P1, which
alternate between executing their critical sections and
remainder sections.
• The two processes share the following two variables:
o flag[2]: A boolean array where flag[i] indicates
whether process Pi wants to enter its critical
section.
o turn: An integer variable that indicates whose turn
it is to enter the critical section. If turn == i, then it’s
process Pi's turn to enter.
Process Structure in Peterson’s Solution:
Let’s break down the algorithm that governs how each
process (Pi) enters and exits the critical section.
Algorithm for Process Pi:
do {
flag[i] = true; // Indicate that Pi wants to enter the
critical section
turn = j; // Give the turn to the other process Pj
while (flag[j] && turn == j); // Wait while the other process
is in its critical section or it's the other process' turn
// Critical section
 flag[i] = false; // Exit the critical section
// Remainder section
} while (true);
Explanation:
1. Flag Setting (flag[i] = true):
o The process Pi sets flag[i] to true, indicating its
desire to enter the critical section.
2. Setting the Turn (turn = j):
o The process then sets the turn variable to j (the
other process’s index). This means that if both
processes attempt to enter the critical section
simultaneously, the process Pj will be allowed to
enter the critical section first, based on the turn
variable.
3. Waiting in the While Loop (while (flag[j] && turn == j)):
o The process enters the while loop where it waits for
two conditions:
▪ flag[j] == true: This means process Pj wants to
enter the critical section.
▪ turn == j: This means it’s process Pj’s turn to
enter the critical section.
o If either condition is not true (i.e., if Pj is not ready
to enter or it’s Pi’s turn), then Pi proceeds into the
critical section.
4. Entering the Critical Section:
 o Once the process successfully exits the while loop,
it enters the critical section and performs its task
(modifying shared resources).
5. Exiting the Critical Section (flag[i] = false):
o After completing its task in the critical section, Pi
sets flag[i] = false, indicating that it is done and the
other process can enter the critical section.
6. Remainder Section:
o After exiting the critical section, the process
proceeds to the remainder section, where it
performs non-critical tasks.
Proof of Correctness:
Peterson’s solution is correct if it satisfies the three critical
requirements:
1. Mutual Exclusion:
o Mutual exclusion is guaranteed because if both
processes try to enter their critical sections
simultaneously, one process will enter its critical
section first, based on the value of turn. If turn == i,
then Pi will enter; otherwise, Pj will enter first. As a
result, only one process can be in the critical
section at a time.
2. Progress:
o Progress ensures that if no process is in the critical
section, and some process wants to enter, one will
eventually be allowed to enter. If Pj is not trying to
 enter, then flag[j] == false, allowing Pi to enter. If Pj
wants to enter, then either turn == i or turn == j.
Once Pj exits its critical section, Pi can enter.
3. Bounded Waiting:
o Bounded waiting guarantees that a process will not
be stuck waiting forever. If Pi is waiting to enter the
critical section, it can only be blocked by Pj for one
entry cycle (as the process will eventually enter
after Pj exits). Therefore, Pi will enter the critical
section after at most one entry by Pj.
Example:
Let’s walk through a scenario where both P0 and P1 try to
enter the critical section:
1. Initially, P0 sets flag[0] = true and turn = 1, giving P1 the
opportunity to enter the critical section.
2. P0 enters the while loop, where P1 is also trying to
enter. If flag[1] == true and turn == 1, P0 waits until P1
either exits the critical section or changes the value of
turn.
3. Once P1 exits the critical section and sets flag[1] = false,
P0 can enter the critical section.
Limitations:
• Two-process limitation: Peterson's solution is only
suitable for two processes. Extending it to more than
two processes requires more complex synchronization
mechanisms.
 • Atomicity issues on modern hardware: Modern
architectures perform instructions like load and store at
high speed, which may lead to issues such as race
conditions or incorrect behavior in Peterson’s solution.
In practice, atomic hardware instructions (like locks or
atomic compare-and-swap) are used for proper
synchronization.
17. How Synchronization Hardware will help to
handle the critical-section problem. 5M

Synchronization hardware helps in handling the critical-

section problem by providing atomic operations that ensure
mutual exclusion in a reliable and efficient manner. These
hardware instructions allow one process to access shared
resources at a time, preventing race conditions and ensuring
correct program behavior in concurrent systems.
Here’s how:

1. Atomic Operations
Hardware provides atomic (indivisible) instructions like:
• test_and_set()
• compare_and_swap()
These operations are executed without interruption, meaning
no other process can access or modify the shared variable
simultaneously.
2. Mutual Exclusion
These atomic instructions enable only one process to enter
its critical section at a time by controlling access using a
shared lock variable. This ensures mutual exclusion, a core
requirement of solving the critical-section problem.

3. Progress and Efficiency

Unlike software-only solutions, hardware synchronization
avoids the need to disable interrupts (which is inefficient on
multiprocessors), thereby improving system performance
and responsiveness.

4. Basic Lock Mechanism

For example, with test_and_set():
while (test_and_set(&lock)) ; // spin-wait
// critical section
lock = false;
This ensures that only the first process that sets the lock
enters the critical section.

5. Supports Advanced Algorithms

With hardware support, more sophisticated synchronization
algorithms (e.g., bounded waiting with test-and-set and
waiting arrays) can be built, which also satisfy progress and
bounded waiting
18. Explain Peterson's solution and
Synchronization Hardware approach to handle the
critical-section problem. 10M
I. Peterson’s Solution
Peterson’s solution is a software-based algorithm that
ensures mutual exclusion, progress, and bounded waiting
for two processes trying to enter their critical sections.
1. Shared Variables
boolean flag[2]; // flag[i] = true → Process Pi wants to enter
critical section
int turn; // Indicates whose turn it is
2. Structure for Process Pi
do {
flag[i] = true; // Indicate interest
turn = j; // Give other process a chance
while (flag[j] && turn == j); // Wait until it's your turn
// Critical section
flag[i] = false; // Exit section
// Remainder section
} while (true);
3. How It Works
 • Mutual Exclusion: Only one process enters critical
section as it waits for the other’s flag or turn.
• Progress: A process not interested won’t block the other.
• Bounded Waiting: A process gets a fair chance within
one turn.
4. Limitation
• May not work correctly on modern multiprocessor
architectures due to instruction reordering.

II. Synchronization Hardware

This is a hardware-based approach using atomic machine-
level instructions like Test-and-Set and Compare-and-Swap
to manage access to the critical section.
1. Test-and-Set Instruction
boolean test_and_set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
Usage in Mutual Exclusion
do {
while (test_and_set(&lock)); // Wait until lock is false
// Critical section
 lock = false; // Release lock
// Remainder section
} while (true);
2. Compare-and-Swap Instruction
int compare_and_swap(int *value, int expected, int
new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
Usage
• Only the process that sees the expected value gets
access.
• Others retry until they succeed.
3. Advantages
• Ensures mutual exclusion efficiently on multiprocessor
systems.
• Atomic execution prevents race conditions.
4. Limitation
• May cause busy waiting (CPU spinning).
• Does not guarantee bounded waiting in basic form.
 19. Explain the solution to the critical-section
problem using mutex locks. 5M
The critical-section problem arises in concurrent
systems when multiple processes or threads try to
access and modify shared resources simultaneously. This
can lead to race conditions and inconsistent data. To
solve this, we need to ensure mutual exclusion—only
one process can be in the critical section at a time.
Solution Using Mutex Locks:
A mutex lock (short for mutual exclusion lock) is a
software mechanism used to control access to the
critical section. It ensures that only one process can
enter its critical section at a time, thereby preventing
race conditions.

Key Functions:
1. acquire()
This function is called before entering the critical
section. It checks whether the lock is available. If not,
the process waits (spins) until it becomes available.
acquire() {
while (!available)
; // busy wait
available = false;
}
2. release()
This function is called after exiting the critical section. It
makes the lock available to other processes.
release() {
available = true;
}

Execution Structure:
do {
acquire(); // Lock acquired
// critical section
release(); // Lock released
// remainder section
} while (true);

Disadvantage – Busy Waiting (Spinlock):

• When a process cannot acquire the lock, it keeps
checking in a loop (busy waiting).
• This wastes CPU time, especially in single-processor
systems.

Advantage:
• No context switch is needed, which makes mutex locks
efficient for short critical sections.
• Useful in multiprocessor systems, where one process
can spin while another executes.

20. Define spinlock. 2M

A spinlock is a type of lock where a process continuously
checks (or "spins") to see if the lock is available. If the
lock is not available, the process remains in a busy-
waiting loop (spinning) until the lock becomes available,
at which point it acquires the lock and proceeds to the
critical section.
21. How semaphore is used to handle the
critical-section problem. 5M
A semaphore is used to handle the critical-section
problem by providing synchronization between
processes attempting to access shared resources. It
ensures that only one process can access a critical
section at any given time, thus preventing race
conditions. This is done using the wait() and signal()
operations to control the access to shared resources.
Steps to Handle the Critical-Section Problem using
Semaphores:
1. Initialization:
 o A semaphore is initialized to a positive integer
value, representing the number of available
resources or access permissions.
o For mutual exclusion, a binary semaphore (a
semaphore with values 0 or 1) is typically used.
o Example Initialization:
semaphore mutex = 1; // Binary semaphore initialized to
1
2. Entering the Critical Section (Critical Section Control):
o Before entering the critical section, a process must
call the wait() operation on the semaphore.
o wait() decrements the value of the semaphore. If
the value of the semaphore is greater than or equal
to 1, the process proceeds. Otherwise, it is blocked
and added to the semaphore’s waiting queue.
Example:
wait(mutex); // Decrements the semaphore to 0 or
waits if it's 0
3. Executing the Critical Section:
o After successfully entering the critical section (after
wait() succeeds), the process executes its critical
section code, which is the part that accesses or
modifies shared resources.
Example:
// Critical section code (accessing shared resources)
4. Exiting the Critical Section (Critical Section Release):
o After finishing the critical section, the process must
release the semaphore by calling the signal()
operation.
o signal() increments the semaphore value. If any
process is waiting in the semaphore’s queue, one of
them is unblocked and allowed to proceed.
Example:
signal(mutex); // Increments the semaphore, allowing
others to access the critical section
5. Behavior of the Semaphore:
o Binary Semaphore (mutex):
▪ When the semaphore is 1, a process can enter
the critical section.
▪ When the semaphore is 0, the process is
blocked and must wait until it is signaled.
o The use of wait() and signal() ensures that only one
process is allowed in the critical section at a time,
providing mutual exclusion.
Example Code (Critical Section Handling using
Semaphores):
semaphore mutex = 1; // Binary semaphore initialized
to 1

// Process 1
 wait(mutex); // Enter critical section
// Access shared resource
signal(mutex); // Exit critical section

// Process 2
wait(mutex); // Enter critical section
// Access shared resource
signal(mutex); // Exit critical section
Key Points:
1. Mutual Exclusion: The semaphore ensures that only one
process can enter the critical section at a time, thus
enforcing mutual exclusion.
2. Blocking: If the semaphore is unavailable (value 0), the
process is blocked until the semaphore becomes
available again.
3. No Busy Waiting: Unlike a simple spinlock, semaphores
can block a process until the resource becomes
available, avoiding wasteful busy waiting.
4. Signal Mechanism: The signal() operation wakes up a
waiting process once the critical section is freed,
allowing it to acquire the semaphore and enter the
critical section.
Semaphore for Multiple Resources:
 For controlling access to multiple instances of a resource
(e.g., multiple identical printers), a counting semaphore
can be used. The semaphore is initialized to the number
of resources. Each process that wants to use a resource
performs a wait(), and once the process is done, it
performs a signal().
semaphore empty = N; // N is the number of resources
wait(empty); // A resource is acquired
signal(empty); // A resource is released

22. Define deadlock. 2M

A deadlock is a situation in a multi-process system where a
set of processes are blocked because each process is waiting
for a resource that is held by another process in the set. As a
result, none of the processes can proceed or complete their
execution, causing the system to become stuck in a state of
permanent waiting.
23. Define Starvation. 2M
Starvation is a situation in a multi-process system where a
process is perpetually denied access to the resources it needs
to proceed with its execution. This occurs because the
resources are continuously allocated to other processes, and
the process in question is never given a chance to execute.
Starvation usually happens when a scheduling algorithm
prioritizes certain processes over others, leading to indefinite
postponement of the lower-priority processes. This can occur
due to factors like priority inversion or when a resource is
frequently taken by higher-priority tasks.
24. Explain The Bounded-Buffer Problem. 5M
The Bounded-Buffer Problem
The bounded-buffer problem is a classic synchronization
problem that involves managing a shared buffer between a
producer and a consumer process. The buffer has a limited
size, and the challenge lies in ensuring that both processes
can operate concurrently without interfering with each other.
The producer produces items and places them into the buffer,
while the consumer removes items from the buffer. The key
issues are managing access to the buffer to prevent overflows
or underflows, which can occur if the producer adds items
when the buffer is full, or the consumer tries to remove items
when the buffer is empty.
Problem Setup:
• Producer: The producer generates items and places
them into the buffer.
• Consumer: The consumer consumes items from the
buffer.
Shared Resources:
• A shared buffer (with a fixed, bounded size n).
• Semaphore mutex: Provides mutual exclusion for access
to the buffer.
 • Semaphore empty: Counts the number of empty slots in
the buffer (initialized to n).
• Semaphore full: Counts the number of full slots in the
buffer (initialized to 0).
Key Considerations:
1. Producer:
o The producer must wait if the buffer is full (i.e.,
empty is 0).
o The producer can add an item to the buffer when
there's an empty slot.
2. Consumer:
o The consumer must wait if the buffer is empty (i.e.,
full is 0).
o The consumer can remove an item from the buffer
when there is at least one full slot.
Semaphore Initialization:
• mutex = 1 (ensures mutual exclusion for accessing the
buffer).
• empty = n (represents the number of empty slots in the
buffer).
• full = 0 (represents the number of items currently in the
buffer).
Producer Process:
do {
 wait(empty); // Wait for an empty slot in the buffer.
wait(mutex); // Enter critical section (mutual exclusion
for buffer access).
/* Produce an item and place it into the buffer */
signal(mutex); // Exit critical section.
signal(full); // Notify that there is one more full slot in
the buffer.
} while (true);
Consumer Process:
do {
wait(full); // Wait for an item to consume (ensure the
buffer is not empty).
wait(mutex); // Enter critical section (mutual exclusion
for buffer access).
/* Consume an item from the buffer */
signal(mutex); // Exit critical section.
signal(empty); // Notify that there is one more empty
slot in the buffer.
} while (true);
Working of the Solution:
1. Producer:
o The producer first checks if there is space in the
buffer (i.e., if there are empty slots). If the buffer is
full, the producer waits on the empty semaphore.
 o Once space is available, the producer enters the
critical section (using the mutex semaphore) to add
an item to the buffer and then signals that there is
one more item in the buffer by calling signal(full).
2. Consumer:
o The consumer first checks if there is an item to
consume in the buffer (i.e., if there are full slots). If
the buffer is empty, the consumer waits on the full
semaphore.
o Once there is an item, the consumer enters the
critical section (using the mutex semaphore) to
remove an item from the buffer and then signals
that there is one more empty slot by calling
signal(empty).
Key Points:
• The mutex semaphore ensures that only one process
(either producer or consumer) can access the buffer at a
time, avoiding race conditions.
• The empty and full semaphores prevent the producer
from overfilling the buffer and the consumer from
underfilling it (i.e., consuming when there are no items).
25. Explain The Readers–Writers Problem 8M
The Readers–Writers Problem
The Readers-Writers Problem is a classical
synchronization problem in computer science that
deals with managing concurrent access to a
shared resource, typically a database or file, by
multiple processes. Some processes only read the
resource, while others need to write to it. The
challenge lies in ensuring that multiple processes
can read the resource simultaneously, but writes
must be exclusive (i.e., only one process can write
at a time). There are several variations of the
problem, but the most common goal is to ensure
data consistency while also ensuring that
processes can access the shared resource
efficiently.
Types of Processes:
• Readers: Processes that only need to read the
shared resource without modifying it.
• Writers: Processes that need to write to the
shared resource. A writer requires exclusive
access to the resource to avoid
inconsistencies.
Key Constraints:
1. Multiple Readers: Multiple readers can access
the resource simultaneously without causing
 any issues because they don't modify the
data.
2. Exclusive Writer: Only one writer can access
the resource at any given time. If a writer is
writing, no other process (reader or writer)
can access the resource.
3. No Simultaneous Read and Write: A writer
must not be allowed to write to the resource
while a reader is reading it, and vice versa, to
prevent data inconsistency.
4. Fairness: We need to ensure fairness to avoid
starvation, where one process (either a reader
or a writer) could potentially be indefinitely
delayed from accessing the resource.
Basic Variants of the Readers-Writers Problem:
1. First Readers–Writers Problem (No Reader
Starvation):
o A reader should not be kept waiting
unless a writer has already obtained
permission to use the shared object.
 o Key Point: Readers may have to wait for
other readers, but not because a writer is
waiting.
o Priority: Readers are given priority over
writers.
2. Second Readers–Writers Problem (No Writer
Starvation):
o Once a writer is ready, that writer should
get the resource as soon as possible. In
other words, no new readers should start
reading while a writer is waiting.
o Key Point: Writers are given priority over
readers to avoid writer starvation.
3. General Case:
o In more complex scenarios, both
starvation and fairness issues arise, and
more sophisticated synchronization
mechanisms are required to balance
reader and writer needs.
Solution to the First Readers-Writers Problem:
The solution involves using semaphores to control
access to the shared resource. Here's how the
solution is typically implemented:
Data Structures:
• Semaphore rw_mutex: This controls access to
the resource for both readers and writers.
• Semaphore mutex: This is used to ensure
mutual exclusion when updating the reader
count.
• Integer read_count: This keeps track of the
number of readers currently accessing the
shared resource.
Algorithm:
1. Reader Process:
o A reader waits for the mutex semaphore
to enter the critical section to update
read_count.
o If it's the first reader (i.e., read_count ==
1), it acquires the rw_mutex semaphore
to prevent writers from accessing the
resource.
 o After updating the read_count, the reader
reads the resource.
o When finished, it decrements read_count.
If it's the last reader (i.e., read_count ==
0), it releases the rw_mutex semaphore to
allow writers to access the resource.
2. Writer Process:
o A writer waits for the rw_mutex
semaphore, which ensures that no other
writer or reader is accessing the resource
at the same time.
o The writer performs the write operation
on the shared resource.
o After finishing, the writer releases the
rw_mutex semaphore, allowing other
writers or readers to access the resource.
Code for Reader Process (First Readers-Writers
Problem):
do {
wait(mutex); // Enter critical section
(mutual exclusion on read_count)
 read_count++; // Increment read_count
(number of readers)
if (read_count == 1) // If this is the first
reader, lock access for writers
wait(rw_mutex); // Lock the shared
resource for reading
signal(mutex); // Exit critical section

// Reading the shared resource

...

wait(mutex); // Enter critical section

(mutual exclusion on read_count)
read_count--; // Decrement read_count
(number of readers)
if (read_count == 0) // If this is the last
reader, unlock access for writers
signal(rw_mutex); // Release the lock on
the shared resource
signal(mutex); // Exit critical section
} while (true);
Code for Writer Process (First Readers-Writers
Problem):
do {
wait(rw_mutex); // Lock the shared
resource for writing

// Writing to the shared resource

...

signal(rw_mutex); // Release the lock on

the shared resource
} while (true);
Explanation of the Solution:
• The mutex semaphore is used to ensure that
only one reader can update the read_count at
a time. This prevents race conditions.
• The rw_mutex semaphore is used to grant
exclusive access to the shared resource. Only
the first reader acquires the rw_mutex, and
 the last reader releases it. Writers are blocked
from accessing the resource until the
rw_mutex is available.
• Fairness: This solution prioritizes readers, so if
there are multiple readers, they can access
the resource simultaneously, improving
overall throughput.
Starvation Considerations:
• In this solution, readers are prioritized
because they don't modify the shared
resource. However, this can lead to writer
starvation if a continuous stream of readers
arrives.
• Writer starvation could be addressed in the
second variant of the problem (second
readers-writers problem), which ensures that
writers have higher priority when they are
waiting.

26. Explain the dining-philosophers problem /

classic synchronization problem. 8M
The Dining Philosophers Problem (Classic Synchronization
Problem)
The Dining Philosophers Problem is a classical
synchronization problem that demonstrates the challenges of
coordinating multiple processes that need shared resources
while avoiding issues like deadlock and starvation. It is often
used to illustrate the complexities of resource allocation and
concurrency control in systems with multiple processes (or
threads).
Problem Setup:
The problem is set around five philosophers who are sitting
around a circular dining table. Each philosopher alternates
between thinking and eating. To eat, each philosopher needs
two chopsticks. The chopsticks are placed between each pair
of adjacent philosophers. The challenge is to design a
solution that ensures:
• No two philosophers eat at the same time, which would
cause a conflict over chopsticks.
• Philosophers do not starve, meaning that they must be
able to eat eventually even if other philosophers are
constantly eating.
• Deadlock is avoided, meaning that the system should
not end up in a state where no philosopher can eat (due
to a circular wait for resources).
Assumptions:
• There are 5 philosophers (P1, P2, P3, P4, P5).
 • There are 5 chopsticks (C1, C2, C3, C4, C5), placed
between each pair of adjacent philosophers.
• Each philosopher needs to pick up the chopsticks (one at
a time) to eat. After eating, they must put down the
chopsticks.
• A philosopher must pick up the chopsticks in a particular
order: first the one on their left, and then the one on
their right. However, this order can vary in different
solutions.
Key Issues:
1. Deadlock: A situation in which no philosopher can
proceed because each one is waiting for a chopstick held
by another philosopher. This occurs if all philosophers
pick up one chopstick and are waiting for the second
chopstick.
2. Starvation: A philosopher might never be able to eat if
the system always favors other philosophers. This is a
fairness issue that needs to be addressed in the solution.
3. Mutual Exclusion: No two philosophers should eat at
the same time, so they must coordinate their access to
the chopsticks.
The Classical Solution:
The basic approach is to use semaphores to control access to
the shared chopsticks and ensure mutual exclusion. Each
chopstick is modeled as a semaphore that controls access to
the chopstick.
Here's the outline of the solution:
• Semaphores:
o Chopstick[i]: A binary semaphore initialized to 1 for
each chopstick (since only one philosopher can hold
a chopstick at a time).
Philosopher’s Behavior:
Each philosopher follows this cycle:
1. Think for a while.
2. Pick up the left chopstick.
3. Pick up the right chopstick.
4. Eat for a while.
5. Put down the right chopstick.
6. Put down the left chopstick.
7. Repeat.
Pseudocode for Philosopher Process:
do {
think(); // Philosopher is thinking

wait(chopstick[i]); // Pick up left chopstick

wait(chopstick[(i+1) % 5]); // Pick up right chopstick

eat(); // Philosopher eats

 signal(chopstick[i]); // Put down left chopstick
signal(chopstick[(i+1) % 5]); // Put down right chopstick
} while (true);
Problems with the Basic Solution:
While this simple solution avoids some issues, it can lead to
deadlock if all philosophers pick up their left chopstick
simultaneously. For example:
1. All philosophers pick up their left chopstick at the same
time.
2. Each philosopher now waits for the right chopstick, but
all the right chopsticks are already held by their
neighbors, resulting in a deadlock situation.
Deadlock-Free Solutions:
To avoid deadlock, we need to modify the process behavior
to ensure that philosophers do not all pick up their left
chopstick at the same time. Several approaches are
commonly used:
1. Limit the Number of Philosophers Sitting at the Table:
• Solution: At most 4 philosophers can sit at the table at
any given time.
• Explanation: If only 4 philosophers are sitting, one
philosopher will always be left without a chopstick,
preventing the possibility of a deadlock.
 • Drawback: This solution limits the number of
philosophers who can eat simultaneously.
2. Pick up Both Chopsticks in a Critical Section:
• Solution: Philosophers should pick up both chopsticks in
a critical section, ensuring that a philosopher cannot
pick up just one chopstick and leave the other one for
someone else.
• Explanation: This avoids situations where a philosopher
picks up one chopstick but is delayed from picking up
the other chopstick due to contention.
• Drawback: While it can reduce deadlock, it still does not
fully prevent starvation.
3. Asymmetric Solution (Different Pickup Order for Odd and
Even Philosophers):
• Solution: Odd-numbered philosophers pick up the left
chopstick first and then the right chopstick, while even-
numbered philosophers pick up the right chopstick first
and then the left chopstick.
• Explanation: By introducing this asymmetry, we ensure
that not all philosophers are competing for the same
chopsticks at the same time. If one philosopher is
holding the left chopstick, another can hold the right
chopstick, ensuring no deadlock.
• Drawback: This solution works well but may still leave
room for starvation if there is a constant flow of
philosophers trying to eat.
Starvation-Free Solution:
To ensure fairness and avoid starvation, we can adopt the
following strategies:
• Use a priority system to ensure that waiting
philosophers eventually get a chance to eat. This could
be based on a round-robin scheduler or other fairness
mechanisms.
• Another option is to implement a queueing mechanism
where philosophers are given a chance to eat in a well-
defined order, thus preventing one philosopher from
being indefinitely blocked by others.
Final Solution Using Semaphores (Asymmetric Approach):
// Initialize semaphore for each chopstick
semaphore chopstick[5] = {1, 1, 1, 1, 1};

do {
// Pick up the left chopstick
wait(chopstick[i]);
// Pick up the right chopstick
wait(chopstick[(i+1) % 5]);

// Eat
eat();
 // Put down the right chopstick
signal(chopstick[(i+1) % 5]);
// Put down the left chopstick
signal(chopstick[i]);

} while (true);
This solution minimizes the chances of deadlock and ensures
that no philosopher is stuck waiting forever for resources.