A counting semaphore S is initialized to 20. Then, 7 P operations and 8 V operations are performed on S.
What is the final value of S?
A shared variable x, initialized to seven, 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 two, stores it to memory and then
terminates. Each of the processes Y and Z reads x from memory, decrements by one, 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 processes complete
execution?
In the context of the above question, what is the minimum possible value of x after all processes have
terminated?
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed,
as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.
Method Used by P1 Method Used by P2
while (S1 == S2) ; while (S1 != S2) ;
Critical Section Critical Section
S1 = S2; S2 = not (S1);
Which one of the following statements describes the properties achieved? Why?
(a) Mutual exclusion but not progress
(b) Progress but not mutual exclusion
(c) Neither mutual exclusion nor progress
(d) Both mutual exclusion and progress
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-
and-set instruction as follows:
void enter_CS(X)
{
while test-and-set(X) ;
}
void leave_CS(X)
{
X = 0;
}
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider
the following statements:
I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.
Which of the above statements is TRUE? Why?
The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are
initialized as S0=1, S1=0, S2=1.
Process P0 Process P1 Process P2
while (true) { wait (S1); wait (S2);
wait (S0); Release (S0); release (S0);
print (0);
release (S1);
release (S2);
}
How many times will process P0 print '0'? Explain.
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X,
increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to
implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0
corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
AcquireLock(L){
while (Fetch_And_Add(L,1))
L = 1;
}
ReleaseLock(L){
L = 0;
}
This implementation
(a) fails as L can overflow
(b) fails as L can take on a non-zero value when the lock is actually available
(c) works correctly but may starve some processes
(d) works correctly without starvation
Explain.
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization
construct used by the processes:
/* P1 */ /* P2 */
while (true) { while (true) {
wants1 = true; wants2 = true;
while (wants2 == true); while (wants1==true);
/* Critical /* Critical
Section */ Section */
wants1=false; wants2 = false;
} }
/* Remainder section */ /* Remainder section */
Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following
statements is TRUE about the above construct? Explain.
(a) It does not ensure mutual exclusion.
(b) It does not ensure bounded waiting.
(c) It requires that processes enter the critical section in strict alternation.
(d) It does not prevent deadlocks, but ensures mutual exclusion.
