GATE CS Concurrency and Synchronization questions

Consider three processes $\text{P1, P2}$, and $\text{P3}$ running identical code, as shown in the pseudocode below. $\text{A}$ and $\text{B}$ are two binary semaphores initialized to $1$ and $0$, respectively. $\text{X}$ is a shared variable initialized to $0$. Each line in the pseudocode is executed atomically. Pseudocode of P1, P2, and P3 …

​​​​​Consider a multi-threaded program with two threads $\mathrm{T} 1$ and $\mathrm{T} 2$. The threads share two semaphores: $s1$ (initialized to $1$) and $s2$ (initialized to $0$). The threads also share a global variable $\mathrm{x}$ (initialized to $0$). The threads execute the code shown below. //code of T 1 wait (s1); x = x+1; print (x); …

Consider the two functions $\textsf{incr}$ and $\textsf{decr}$ shown below. incr(){ decr(){ wait(s); wait(s); X = X+1; X = X-1; signal(s); signal(s); } } There are $5$ threads each invoking $\textsf{incr}$ once, and $3$ threads each invoking $\textsf{decr}$ once, on the same shared variable $\mathrm{X}$. The initial value of $\mathrm{X}$ is …

Consider the following threads, $\text{T}_{1}, \text{T}_{2},$ and $\text{T}_{3}$ executing on a single processor, synchronized using three binary semaphore variables, $\text{S}_{1}, \text{S}_{2},$ and $\text{S}_{3},$ operated upon using standard $\textsf{wait}()$ and $\textsf{signal}().$ The threads can be context switched in any order and at any …

Consider the following pseudocode, where $\textsf{S}$ is a semaphore initialized to $5$ in line $\#2$ and $\textsf{counter}$ is a shared variable initialized to $0$ in line $\#1$. Assume that the increment operation in line $\#7$ is $\textit{not}$ atomic. 1. int counter = 0; 2. Semaphore S = init(5); 3. void parop(void) 4. { 5. wait(S); 6. …

Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to $1$ and $0$, respectively. Assume that $\text{count}$ is a shared variable initialized to $0$ and not used in CODE SECTION P. $\begin{array}{|c|} \hline \textbf{CODE SECTION P} \\ \hline \end{array}$ wait(a); count=count+1; if (count==n) …

Consider three concurrent processes $P_1, P_2$ and $P_3$ as shown below, which access a shared variable $D$ that has been initialized to $100.$ $$\begin{array}{|c|c|c|} \hline P_1 & P_2 & P_3 \\ \hline : & : & : \\ : & : & : \\ D=D+20 & D=D-50 & D=D+10 \\ : & : & : \\ : & : & : \\ \hline \end{array}$$ …

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is $N$. Three semaphores $empty$, $full$ and $mutex$ are defined with respective initial values of $0, N$ and $1$. Semaphore $empty$ denotes the number of available slots in the buffer, for the consumer to read from. Semaphore $full$ …

A multithreaded program $P$ executes with $x$ number of threads and uses $y$ number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock $l$, then it cannot re-acquire lock $l$ without releasing it. If a thread is unable to acquire a lock, it …

Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{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 != i in …

Consider the following two-process synchronization 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. $$\begin{array}{|l|l|}\hline \text{P1() \{ } & \text{P2()\{} \\ \text{ C = B - 1;} & \text{ D = 2 * B; } \\ \text{ B = 2 * C;} & \text{ B = D - 1;} \\ \text{\}} & \text{\}} \\ \hline \end{array}$$ The number of …

Two processes $X$ and $Y$ need to access a critical section. Consider the following synchronization construct used by both the processes …

Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore n = 0; semaphore s = 1; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(s); semWait(n); removeFromBuffer(); semSignal(s); consume(); } } Which one of the following is …

A certain computation generates two arrays a and b such that $a[i] = f(i)$ for $0 \leq i < n$ and $b[i] = g(a[i])$ for $0 \leq i < n$. Suppose this computation is decomposed into two concurrent processes $X$ and $Y$ such that $X$ computes the array $a$ and $Y$ computes the array $b$. The processes employ two binary semaphores $R$ …

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 …

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 …

The following program consists of $3$ concurrent processes and $3$ binary semaphores. The semaphores are initialized as $S0=1, S1=0$ and $S2=0.$ …

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. …