Operating Systems
Question Bank Solutions
Module 3: Process Synchronization
Prepared By
Raj Odedara
Question Bank Coverage: Questions 39 – 47
Academic Reference Notes
Designed for Exam Preparation and Concept Clarity
Module 3: Process Synchronization Operating Systems
Table of Contents
Q39. Inter-Process Communication (IPC) mechanisms. 2
Q40. Race condition and examples. 3
Q41. Bounded buffer problem. 3
Q42. Producer-consumer problem. 5
Q43. wait() and signal() atomicity. 6
Q44. Critical section problems and 3 requirements. 7
Q45. Peterson’s solution for the Critical section. 8
Q46. Software and hardware solutions of CS problem. 9
Q47. wait() and signal() using TestAndSet(). 10
Page 1
Module 3: Process Synchronization Operating Systems
Q39. Explain Inter-Process Communication (IPC)
mechanisms with suitable examples.
Inter-Process Communication (IPC)
IPC is a mechanism that allows processes to communicate with each other and syn-
chronize their actions. The communication can be seen as a method of cooperation
between processes.
There are two primary models of IPC: Shared Memory and Message Passing.
1. Shared Memory System In this model, cooperating processes establish a region
of memory that is shared between them. Processes can then exchange information by
reading and writing data to this shared region.
• Pros: Maximum speed and convenience of communication, as it is done at memory
speeds.
• Cons: Requires careful synchronization (like Semaphores or Mutexes) to ensure
processes do not write to the same location simultaneously.
• Example: POSIX Shared Memory (shmget, shmat).
2. Message Passing System In this model, communication takes place by means of
messages exchanged between the cooperating processes without using shared variables.
It uses two basic operations: send(message) and receive(message).
• Pros: Easier to implement in distributed systems (across networks). No conflict
over shared memory.
• Cons: Slower due to system call overhead and data copying.
• Example: Pipes, FIFOs, Message Queues, Sockets.
Shared Memory Message Passing
Process A Process B Process A Process B
send() receive()
Shared Memory OS Kernel (Msg Queue)
Page 2
Module 3: Process Synchronization Operating Systems
Q40. What is race condition? Explain with suitable
examples.
Race Condition
A Race Condition is a situation where several processes access and manipulate
the same shared data concurrently, and the final outcome of the execution depends
on the particular order (or interleaving) in which the access takes place.
To guard against race conditions, we need to ensure that only one process at a time can
manipulate the shared data (Mutual Exclusion).
Example of a Race Condition: Consider a shared variable counter initialized to 5.
• Process P1 executes: counter++ (Producer)
• Process P2 executes: counter-- (Consumer)
At the assembly level, these operations are not atomic. They translate to:
Process P1 (counter++) Process P2 (counter–)
R1 = counter R2 = counter
R1 = R1 + 1 R2 = R2 − 1
counter = R1 counter = R2
Interleaved Execution causing an error:
1. P1 reads counter into R1 (R1 = 5)
2. P1 increments R1 (R1 = 6). Context switch occurs!
3. P2 reads counter into R2 (R2 = 5, since P1 hasn’t saved yet)
4. P2 decrements R2 (R2 = 4)
5. P2 writes R2 back to counter (counter = 4). Context switch occurs!
6. P1 writes R1 back to counter (counter = 6).
Result: The final value is 6 (or 4, depending on who writes last), but the correct value
should be 5 (since we incremented and decremented once). This data inconsistency is the
result of a race condition.
Q41. What is the bounded buffer problem?
Bounded Buffer Problem
The Bounded Buffer problem is a classic IPC synchronization problem. It
involves a buffer of fixed size (say, N slots) that is shared between two types of
processes: Producers and Consumers.
Page 3
Module 3: Process Synchronization Operating Systems
Rules and Constraints:
1. The Producer generates items and places them into the buffer.
2. The Consumer removes items from the buffer and consumes them.
3. Constraint 1: The Producer must not try to add data into the buffer if it is full.
If full, it must wait.
4. Constraint 2: The Consumer must not try to remove data from an empty buffer.
If empty, it must wait.
5. Constraint 3: Both producer and consumer cannot access the buffer simultane-
ously (Mutual Exclusion must be guaranteed).
Page 4
Module 3: Process Synchronization Operating Systems
Q42. What is the producer-consumer problem? Ex-
plain with suitable programs and examples.
The Producer-Consumer problem is identical to the bounded buffer problem. It
demonstrates the need for synchronization when processes share a common resource (the
buffer). We solve this using three semaphores:
• mutex: Binary semaphore initialized to 1 (Ensures mutual exclusion).
• empty: Counting semaphore initialized to N (Counts empty slots).
• full: Counting semaphore initialized to 0 (Counts filled slots).
Producer Process
while (true) // Produce an item item = producei tem();
wait(empty); // Wait if buffer is full (empty slots == 0)
wait(mutex); // Acquire lock for critical section
// CRITICAL SECTION buffer[in] = item; in = (in + 1)
signal(mutex); // Release lock signal(full); // Increment number of
full slots
Consumer Process
while (true) wait(full); // Wait if buffer is empty (full slots ==
0) wait(mutex); // Acquire lock for critical section
// CRITICAL SECTION item = buffer[out]; out = (out + 1)
signal(mutex); // Release lock signal(empty); // Increment number of
empty slots
// Consume the item consumei tem(item);
Explanation: If the buffer is full, empty is 0. The Producer calls wait(empty) and gets
blocked. Once the Consumer consumes an item, it calls signal(empty), which wakes up
the Producer. The mutex ensures that ‘in‘ and ‘out‘ pointers are updated atomically.
Page 5
Module 3: Process Synchronization Operating Systems
Q43. Show that, if the wait() and signal() semaphore
operations are not executed automatically, then mu-
tual exclusion may be violated.
The standard definitions of wait(S) and signal(S) for a semaphore S are:
wait(S)
signal(S)
wait(S) while (S <= 0) ; //
signal(S) S++;
busy wait S--;
If these operations are not executed atomically (indivisibly), race conditions can occur
on the semaphore variable S itself.
Proof of Violation: Suppose Semaphore S = 1 (Mutex). Processes P1 and P2 both
want to enter their critical sections and simultaneously execute wait(S).
1. P1 evaluates (S <= 0) → False. P1 is about to execute S--. 2. Context switch to P2.
3. P2 evaluates (S <= 0) → False (since S is still 1). 4. P2 executes S-- → S becomes
0. 5. P2 enters the Critical Section. 6. Context switch back to P1. 7. P1 resumes and
executes its S-- → S becomes -1. 8. P1 enters the Critical Section.
Conclusion: Both P1 and P2 are now in the Critical Section at the same time. Mutual
Exclusion is violated. Therefore, it is absolutely mandatory that wait() and signal()
are implemented as atomic hardware instructions or protected by spinlocks.
Page 6
Module 3: Process Synchronization Operating Systems
Q44. Explain critical section problems in detail. Give
the three requirements that should be satisfied.
Critical Section
A Critical Section is a segment of code in a process where the process may be
modifying shared variables, updating a table, writing to a file, etc. The most
important feature is that when one process is executing in its critical section, no
other process is allowed to execute in its critical section.
Structure of a Typical Process:
Process Pi
do // ENTRY SECTION: Requests permission to enter CS
// CRITICAL SECTION (CS): Modifies shared data
// EXIT SECTION: Notifies others that CS is vacant
// REMAINDER SECTION: Non-shared code while (true);
Three Requirements for a Valid Solution: A valid 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. This selection cannot be postponed indefinitely (no deadlock).
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 (no starvation).
Page 7
Module 3: Process Synchronization Operating Systems
Q45. Explain Peterson’s solution for the Critical sec-
tion. Also Justify how it satisfies the three require-
ments.
Peterson’s Solution is a classic software-based solution to the critical section problem
restricted to exactly two processes (P0 and P1 ). It relies on two shared data items:
• int turn; (Indicates whose turn it is to enter the CS).
• boolean flag[2]; (Indicates if a process is ready to enter the CS).
Structure of Process Pi (where j
do flag[i] = true; // Pi announces it wants to enter turn = j; //
Pi politely offers the turn to Pj
while (flag[j] turn == j); // ENTRY SECTION (Busy wait)
// CRITICAL SECTION
flag[i] = false; // EXIT SECTION
// REMAINDER SECTION while (true);
Justification of the Three Requirements:
1. Mutual Exclusion: P0 and P1 can only be in the CS simultaneously if both bypass
the while loop. This requires flag[0] = flag[1] = true AND both turn == 0
and turn == 1. Since the variable turn can only hold one value at a time, only
one process escapes the while loop. ME is preserved.
2. Progress: If P1 is not interested (flag[1] = false), the while loop condition
for P0 (flag[1] && turn == 1) becomes false immediately. Thus, P0 can enter
without delay. A process operating outside its CS does not block another process.
3. Bounded Waiting: Suppose P0 is waiting to enter, so flag[0] = true and turn
= 1. If P1 is in the CS and then exits, it sets flag[1] = false, allowing P0 to
enter. If P1 tries to re-enter immediately, it sets flag[1] = true and sets turn
= 0. Now P1 must wait, and P0 enters. Thus, P1 can enter the CS at most once
while P0 is waiting.
Page 8
Module 3: Process Synchronization Operating Systems
Q46. What is the critical-section problem? List soft-
ware and hardware solutions and describe any of it.
The Critical Section Problem is the problem of designing a protocol that processes
can use to cooperate and ensure that only one process accesses shared data at a time.
Software Solutions:
• Dekker’s Algorithm
• Peterson’s Solution (Works for 2 processes)
• Lamport’s Bakery Algorithm (Works for N processes)
Hardware Solutions (Synchronization Hardware):
• TestAndSet Instruction
• CompareAndSwap Instruction
• Mutex Locks / Semaphores (OS-level abstractions using hardware)
Description of Hardware Solution: TestAndSet Instruction Many modern com-
puter systems provide special hardware instructions that allow us either to test and
modify the content of a word or to swap the contents of two words atomically (uninter-
ruptibly).
Definition of TestAndSet (Atomic Hardware Level)
boolean TestAndSet(boolean *target) boolean rv = *target; *target =
true; return rv;
Using TestAndSet for Mutual Exclusion: We declare a shared boolean variable
lock, initialized to false.
Process Pi using TestAndSet
do // If lock is false, TestAndSet returns false and sets lock to
true. // The loop breaks and Pi enters CS. // If lock is true, it
returns true and loops infinitely (spins). while (TestAndSet(lock))
; /* do nothing */
// CRITICAL SECTION
lock = false; // Release the lock
// REMAINDER SECTION while (true);
Page 9
Module 3: Process Synchronization Operating Systems
Q47. Show how to implement the wait() and sig-
nal() semaphore operations in a multiprocessor en-
vironment using the TestAndSet() instruction.
In a multiprocessor environment, we cannot simply disable interrupts to ensure atomicity
of wait() and signal(), as disabling interrupts across all processors is highly inefficient.
Instead, we use a hardware spinlock like TestAndSet to protect the semaphore’s internal
state.
We define a Semaphore as a struct:
Semaphore Structure
typedef struct int value; struct process *list; // Wait queue
boolean lock; // Hardware spinlock semaphore;
The lock is initialized to false. We use TestAndSet to ensure only one process at a
time can modify the value and the list.
Implementation of wait():
wait() Implementation
wait(semaphore *S) // Acquire the spinlock while
(TestAndSet(S->lock)) ; /* busy wait */
S->value--; if (S->value < 0) // Add this process to S->list //
Release the spinlock BEFORE blocking S->lock = false; block(); //
Suspend the process else S->lock = false; // Release the spinlock
Implementation of signal():
signal() Implementation
signal(semaphore *S) // Acquire the spinlock while
(TestAndSet(S->lock)) ; /* busy wait */
S->value++; if (S->value <= 0) // Remove a process P from S->list
wakeup(P); // Move P to ready queue
S->lock = false; // Release the spinlock
Why is this better?
We still have busy waiting (the while loop), but this busy waiting is strictly limited
to the short time it takes to increment/decrement the value and manipulate the
queue pointers. We do not busy-wait for the entire duration of the Critical Section.
Page 10