1(a) Readers–Writers Problem: Preventing Writer Starvation [6]
Problem
In the reader-priority semaphore solution, a continuous stream of readers may cause writer
starvation, because new readers can enter even when writers are waiting.
Solution Idea (Fair Readers–Writers)
Introduce an additional semaphore (queue) to ensure FIFO ordering, so once a writer is waiting,
new readers cannot bypass it.
Modified Semaphore-Based Solution
Shared Variables
semaphore rw_mutex = 1; // Controls access to shared data
semaphore mutex = 1; // Protects read_count
semaphore queue = 1; // Fairness semaphore
int read_count = 0;
Reader Process
wait(queue);
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
signal(queue);
/* reading */
wait(mutex);
read_count--;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
Writer Process
wait(queue);
wait(rw_mutex);
/* writing */
signal(rw_mutex);
signal(queue);
Why This Works
queue ensures arrival order
New readers cannot overtake a waiting writer
No starvation for either readers or writers
Satisfies mutual exclusion, progress, bounded waiting
1(b) Fork/Join Framework in Java [3]
Handling Large Tasks
The Fork/Join framework recursively divides a large task into smaller independent subtasks
using:
fork() → split task
join() → combine results
This follows a divide-and-conquer strategy.
Work-Stealing Algorithm
Each worker thread maintains a deque
Idle threads steal tasks from busy threads’ queues
Improves load balancing and CPU utilization
Minimizes idle cores on multicore systems
1(c) Counting Semaphore Value [1]
Initial value = 15
7 wait() → 15 − 7 = 8
4 signal() → 8 + 4 = 12
Correct Answer: iv. 12
2(a) CPU Scheduling
Given Processes
Process Burst Priority Arrival
P1 14 2 0
P2 9 2 1
P3 10 1 2
(Lower priority number = higher priority)
(i) SRTF Scheduling
Gantt Chart
0 1 2 11 20 34
| P1 | P2 | P2 | P2 | P2 | P2 | P3 | P1 |
Completion Times
P1 = 34
P2 = 11
P3 = 20
Turnaround Time (TAT)
P1 = 34 − 0 = 34
P2 = 11 − 1 = 10
P3 = 20 − 2 = 18
Waiting Time (WT)
P1 = 34 − 14 = 20
P2 = 10 − 9 = 1
P3 = 18 − 10 = 8
Average WT = (20+1+8)/3 = 9.67 ms
Average TAT = (34+10+18)/3 = 20.67 ms
(ii) Preemptive Priority + Round Robin (q = 3)
Gantt Chart
0 2 5 8 11 14 17 20 23 26 29 32 34
|P1|P3|P3|P3|P2|P1|P2|P1|P2|P1|
Completion Times
P1 = 34
P2 = 29
P3 = 11
Average Waiting Time ≈ 13 ms
Average Turnaround Time ≈ 23 ms
(iii) Comparison
SRTF gives minimum average waiting time
Priority + RR is fairer but causes more context switches
2(b) Context Switching Impact [2]
Impact
High context switching reduces CPU efficiency
CPU spends more time saving/restoring states
Overheads
Register save/restore
Cache invalidation
TLB flush
Scheduler execution time
3(a) Real-Time Scheduling [7.5]
Given
P1: Period = 50, Execution = 25
P2: Period = 70, Execution = 30
CPU Utilization
U=25/50+30/70=0.5+0.43=0.93U
Rate Monotonic (RMS)
For n=2:
Umax=2(2^1/2−1)≈0.828U
Not schedulable by RMS
Earliest Deadline First (EDF)
EDF schedulable if U ≤ 1
Schedulable using EDF
EDF Gantt Chart
0---25(P1)---55(P2)---75(P1)---105(P2)
Pseudo Code (EDF)
while (true) {
select process with earliest deadline;
execute process;
}
3(b) atomic_sub() using compare_and_swap [2.5]
void atomic_sub(int *value, int sub) {
int old;
do {
old = *value;
} while (!compare_and_swap(value, old, old - sub));
}
4(a) Thread Starvation [2.5]
Definition
Thread starvation occurs when a thread waits indefinitely for CPU or resources.
Cause
Poor scheduling (e.g., strict priority scheduling)
No aging mechanism
Continuous arrival of higher-priority thread
4(b) Mutex vs Semaphore [2.5]
Feature Mutex Semaphore
Ownership Yes No
Count Binary Binary / Counting
Usage Critical section Resource management
Example File access Producer-consumer
4(c) POSIX Monitor-like Code [5]
#include <pthread.h>
#include <stdio.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int a = 0, b = 0, x = 0, y = 5;
void* waiting_thread(void* arg) {
pthread_mutex_lock(&mutex);
while (!(a == b || x >= y)) {
pthread_cond_wait(&cond, &mutex);
}
printf("Condition satisfied\n");
pthread_mutex_unlock(&mutex);
return NULL;
}
void* signaling_thread(void* arg) {
pthread_mutex_lock(&mutex);
a = 5;
b = 5;
x = 6;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
return NULL;
}