Consider the following proposed solution for the critical section problem. There are n processes: P_{0}...P_{n−1}. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.
Code for P i: do { c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0; for every j 6= i in {0,...,n-1} { while (c[j]); while (t[j] != 0 && t[j]<=t[i]); } Critical Section; t[i]=0; Remainder Section; } while (true);
Which one of the following is TRUE about the above solution?
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. The largest initial value of S for which at least one P(S) operation will remain blocked is ______.
The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.
A variable x is said to be live at a statement S_{i} in a program if the following three conditions hold simultaneously: i. There exists a statement S_{j} that uses x ii. There is a path from S_{i} to S_{j} in the flow graph corresponding to the program iii. The path has no intervening assignment to x including at S_{i} and S_{j}
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a , b and c; process Y executes the P operat ion on semaphore s b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?
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 processes complete execution?
A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i] = g (a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X compu tes the array a and Y computes the array b. T he processes employ two binary semaphores R and S, both initi alized to zero. The array a is shared by the two processes. The structures of the processes are shown below.
Which one of the following represents the CORRECT implementations of ExitX and EntryY?
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
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.
Which one of the following statements describes the properties achieved?
The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
How many times will process P0 print ‘0’?
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 are TRUE?
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows: P(s) : s = s - 1; if s < 0 then wait; V(s) : s = s + 1; if s <= 0 then wakeup a process waiting on s; Assume that P_{b} and V_{b} the wait and signal operations on binary semaphores are provided. Two binary semaphores x_{b} and y_{b} are used to implement the semaphore operations P(s) and V(s) as follows:
P(s) : P_{b} (x_{b}); s = s -1; if (s < 0) { V_{b} (x_{b}); P_{b} (y_{b}); } else V_{b} (x_{b}); V(s) : P_{b} (x_{b}); s = s + 1; if (s <=0) V_{b }(y_{b}); V_{b} (x_{b});
The initial values of x_{b} and y_{b} are respectively
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:
Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?