PROCESS SYNCHRONIZATION and DEADLOCK
Synchronization:
Q1: Below is the code of Producer-Consumer Problem
void Producer(){
do{
//wait until empty > 0
wait(Empty);
wait(mutex);
add()
signal(mutex);
signal(Full);
}while(TRUE);
}
void Consumer(){
do{
//wait until empty > 0
wait(full);
wait(mutex);
consume()
signal(mutex);
signal(empty);
}while(TRUE);
}
1) Can the consumer remove an item from the buffer if full () = 0?
2) Can the producer and consumer acquire the lock simultaneously?
3) What will happen if wait(full) and wait(mutex) are interchanged in Consumer ()?
4) What will happen if signal(mutex) and signal(Full) are interchanged in Producer ()?
Q2: Consider a system with two processes, P1 and P2, that need to enter a critical section. They
use a binary semaphore SSS, initialized to 1, for mutual exclusion. The wait () and signal ()
operations on the semaphore take negligible time. Process P1 executes 5 times per second, and
Process P2 executes 10 times per second. Each time either process enters the critical section, it
spends 20ms in the critical section. What is the maximum time that P2 can be blocked by P1 in
entering the critical section?
Q3: In a variation of the Readers-Writers problem, assume that there are 3 readers and 2 writers.
Each reader takes 2 seconds to read, and each writer takes 4 seconds to write. Writers are given
priority over readers. If at time t=0, a writer starts writing, how long will the next reader have to
wait to start reading, assuming that a writer requests access to the critical section immediately after
the first writer?
Q4: Consider the two functions incr() and decr() shown below.
incr() {
wait(s);
X = X+1;
signal(s);
}
decr() {
wait(s);
X = X-1;
signal(s);
}
There are 5 threads each invoking incr() once, and 3 threads each invoking decr() once, on the
same shared variable X. The initial value of X is 10.
Suppose there are two implementations of the semaphore s, as follows:
I: s is a binary semaphore initialized to 1.
II: s is a counting semaphore initialized to 2.
Let V1, V2 be the values of X at the end of execution of all the threads with implementations I and
II, respectively.
What are the minimum possible values of V1, V2, respectively?
Q5: Consider the following two threads and that update two shared variables and. Assume that
initially. Though context switching between threads can happen at any time, each statement of or
is executed atomically without interruption.
List all the possible combinations of values of a and b after both T1 and T2 finish execution.
Q6: A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y,
Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to
memory and then terminates. Each of the processes Y and Z reads x from memory, decrements by
two, stores it to memory, and then terminates. Each process before reading x invokes the P
operation (i.e. wait) on a counting semaphore S and invokes the V operation (i.e. signal) on the
semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum
possible value of x after all process's complete execution?
Q7: The following two functions P1 and P2 that share a variable B with an initial value of 2 execute
concurrently.
P1() {
C = B – 1;
B = 2 * C;
}
P2() {
D = 2 * B;
B = D - 1;
}
The number of distinct values that B can possibly take after the execution, explain briefly?
Q8:
Consider a non-negative counting semaphore S. the operation P(S) decrements S, and V(S)
increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some
order. What is the largest initial value of S for which at least one P(S) operation will remain
blocked?
Q9. In a bounded buffer problem, there are 5 producer threads and 3 consumer threads. The buffer
size is 10. Producers and consumers interact with the buffer using two semaphores: empty
(initialized to 10) and full (initialized to 0). The time to produce or consume an item is 1 second.
If two producers are producing items simultaneously, how much time will pass before both of them
can place an item in the buffer, assuming the buffer was initially empty?
Q10: In a variation of the Dining Philosophers problem, 5 philosophers are sitting at a table with
5 chopsticks. Each philosopher needs both chopsticks adjacent to them to eat. The time to pick up
a chopstick or put it down is negligible. The time to eat is 10 seconds. A philosopher tries to pick
up both chopsticks simultaneously to avoid deadlock. What is the minimum time required for all
philosophers to eat at least once?
DEADLOCK:
Q1: In the Sleeping Barber problem, there are 3 barber chairs and 7 waiting chairs. If a customer
arrives and all chairs (barber and waiting) are full, they leave. Each haircut takes 20 minutes, and
new customers arrive every 5 minutes. How many customers will be served in 1 hour if the shop
is full initially?
Q2: A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is
shown in the tables below, where P0, P1, P2 are processes and R0, R1, R2 are resource types.
(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?
Q3: Consider a system with 5 processes P1, P2, P3, P4, P5 and 3 resource types R1, R2, R3. The
allocation matrix and request matrix are given below:
Allocation: Request:
Available resources: (1,1,1), (1,1,1), (1,1,1). Detect if the system is in a deadlock state, and if so,
identify the deadlocked processes.
Q4: An operating system uses the Banker’s algorithm for deadlock avoidance when managing
the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table
given below presents the current system state. Here, the Allocation matrix shows the current
number of resources of each type allocated to each process and the Max matrix shows the
maximum number of resources of each type required by each process during its execution.
Allocation
Allocation Max
X Y Z X Y Z
P0 0 0 1 8 4 3
P1 3 2 0 6 2 0
P2 2 1 1 3 3 3
An operating system uses the Banker’s algorithm for deadlock avoidance when managing the
allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given
below presents the current system state. Here, the Allocation matrix shows the current number of
resources of each type allocated to each process and the Max matrix shows the maximum
number of resources of each type required by each process during its execution. Explain which
request will be permitted and why.
Q5: A system has 4 processes P1,P2,P3,P4 and 2 resources RA and RB. The current allocation
and maximum need are as follows:
Allocation Matrix:
Maximum Matrix:
Available Resources: RA=3,RB=2
Determine if the system is in a safe state. If it is safe, find the safe sequence.
Q6: A system has 5 processes and 3 resource types R1,R2,R3 with the following allocation and
maximum matrices:
Allocation:
Maximum:
Available: R1=3,R2=2,R3=2
Determine the total resources in the system and identify if the system is in a deadlock state.
Q7: A system has 4 processes P1, P2, P3, P4 and requires the following maximum resources:
P1: 2 instances of RA, 1 instance of RB
P2: 1 instance of RA, 2nstances of RB
P3: 1 instance of RA, 1 instance of RB
P4: 1 instance of RB
If there are 3 instances of RA and 3 instances of RB, calculate if this system can operate without
deadlock. If not, how many additional resources are needed?
Q8: In a system with 4 processes P1, P2, P3, P4 and 2 resources R1 and R2, the following
information is provided:
Current allocations:
Maximum needs:
Available resources: R1 =1, R2 =1
Identify which processes must be preempted to allow the system to recover from a deadlock state
and explain your reasoning.
