Semaphores

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

Pseudocode of P1, P2, and P3:

wait(A);
print(*);
X=X+1;

if(X==2)
{
    print($);
    signal(B);
}

signal(A);

wait(B);
print(#);
signal(B);

Assume that any of the three processes can start to
execute first and context switching can happen
between these processes at any arbitrary time and
in any arbitrary order.

Which of the following patterns is/are possible to
be generated as an outcome of the execution of
these three processes?

• (a)**$*###
• (b)**$#*##
• (c)**$##*#
• (d)***$###

Consider a multi-threaded program with two threads
T1 and T2. The threads share two semaphores: s1
(initialized to 1) and s2 (initialized to 0). The threads
also share a global variable x (initialized to 0). The
threads execute the code shown below.

T1:

wait(s1);

x = x + 1;

 print(x);

 wait(s2);

 signal(s1);

T2:

wait(s1);

 x = x + 1;

 print(x);

 signal(s2);

 signal(s1);
Which of the following outcomes is/are possible
when threads T1 and T2 execute concurrently?

• (a)T1 runs first and prints 1, T2 runs next and prints 2
• (b)T2 runs first and prints 1, T1 runs next and prints 2
• (c)T1 runs first and prints 1, T2 does not print anything (deadlock)
• (d)T2 runs first and prints 1, T1 does not print anything (deadlock) OPERATING SYSTEMS

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 decor 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-1: s is a binary semaphore initialized to 1.
I-2: s is a counting semaphore initialized to 2.

Let V1, and V2 be the values of X at the end of the
execution of all the threads with implementations I-
1, and I-2, respectively.

Which one of the following choices corresponds to
the minimum possible values of V1, V2,
respectively?

• (a)15,7
• (b)7,7
• (c)12,7
• (d)12,8

Consider the following threads T1, T2, and T3

executing on a single processor, synchronized using
three binary semaphore variables S1, S2, and
S3,operated upon using standard wait() and signal().
The  threads can be context switched in any order
and at any time.
T1:
 while(true) {
 wait(S3);
 print("C");
 signal(S2);
 }
T2:
 while(true) {
 wait(S1);
 print("B");
 signal(S3);
 }
T3:
 while(true) {
 wait(S2);
 print("A");
 signal(S1);
 }
Which initialization of the semaphores would print
the sequence BCABCABCA...?

• (a)S1 = 1; S2 = 1; S3 = 1
• (b)S1 = 1; S2 = 1; S3 = 0
• (c)S1 = 1; S2 = 0; S3 = 0
• (d)S1 = 0; S2 = 1; S3 = 1 OPERATING SYSTEMS

Consider the following pseudocode, where S is a
semaphore initialized to 5 in line #2 and counter is
a shared variable initialized to 0 in line#1. Assume
that the increment operation in line#7 is not atomic.

1. int counter = 0

2. Semaphore S = init(5);

3. void parop(void)

4. {

5.

wait(S);

6.

 wait(S);

7.

  counter++;

8.
        signal(S);

9.                signal(S);

10.}

If five threads execute the function parop
concurrently, which of the following program
behavior(s) is/are possible?

• (a)The value of counter is 5 after all the threads successfully complete the execution of parop.
• (b)The value of counter is 1 after all the threads successfully complete execution of parop.
• (c)The value of counter is 0 after all the threads successfully complete the execution of parop.
• (d)There is a deadlock involving all the threads.

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 count is a shared
variable initialized to 0 and not used in CODE
SECTION P.

CODE SECTION P

wait (a);
           count = count+1;

if (count==n) signal (b);

signal (a); wait (b); signal (b);

CODE SECTION Q

What does the code achieve?

• (a)It ensures that all processes execute CODE SECTION P mutually exclusively.
• (b)It ensures that at most two processes are in CODE SECTION Q at any time.
• (c)It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
• (d)It ensures that at most n-1 processes are in CODE SECTION P at any time. OPERATING SYSTEMS

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 denotes the
number of available slots in the buffer, for the
producer to write to. The placeholder variables,
denoted by P, Q, R and S, in the code below can be
assigned either empty or full. The valid semaphore
operations are: wait () and signal ().
Producer
Consumer
do{
do {
wait (P);
wait (R);
wait (mutex);
wait mutex);
//Add item to buffer
//Consume item from
buffer
Signal (mutex);
Signal (mutex);
Signal (Q);
Signal (S);
} while (1);
} while (1);

Which one of the following assignments to P, Q, R
and S will yield the correct solution?

• (a)P: full, Q: full, R: empty, S: empty
• (b)P: empty, Q: empty, R: full, S: full
• (c)P: full, Q: empty, R: empty, S: full
• (d)P: empty, Q: full, R: full, S: empty

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

Consider the procedure below for the Producer-
Consumer problem which uses semaphores:

semaphore n = 0;
semaphore s = 1;
void producer() void consumer()
{
    while(true) while(true)
    {
        produce();
        semWait(s) ;
        addToBuffer();
        semSignal(s);
        semSignal(n);
    }
}
void consumer()
{
    while(true)
    {
        semWait(s);
        semWait(n);
        removeFromBuffer();
        semSignal(s);
        consume();
    }
}

OPERATING SYSTEMS

Which one of the following is TRUE?

• (a)The producer will be able to add an item to the buffer, but the consumer can never consume it.
• (b)The consumer will remove no more than one item from the buffer.
• (c)Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
• (d)The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

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
computes the array a and Y computes the array b.
The processes employ two binary semaphores R
and S, both initialized to zero. The array a is shared
by the two processes. The structures of the
processes are shown below.

Process X:
Process Y:
private i;
private i;
for (i= 0; i< n; i + +){
for (i= 0; i< n; i + +){

a[i] = f(i);
EntryY (R, S);
ExitX (R, S);
b[i] = g(a[i]);
}
}

Which one of the following represents the
CORRECT implementations of Exit X and Entry
Y?

• (a)ExitX(R, S) { P(R); V(S); } EntryY(R, S) { P(S); V(R); }
• (b)ExitX(R, S) { V(R); V(S); } EntryY(R, S) { P(R); P(S); }
• (c)ExitX(R, S) { P(S); V(R); } EntryY(R, S) { V(S); P(R); }
• (d)ExitX(R, S) { V(R); P(S); } EntryY(R,S) { V(S); P(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 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

OPERATING SYSTEMS
memory. Semaphore S is initialized to two. What is
the maximum possible value of x after all processes
complete execution?

• (a)-2
• (b)-1
• (c)1
• (d)2

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

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 the process P0 print '0'?

• (a)At least twice
• (b)exactly twice
• (c)exactly thrice
• (d)exactly one

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 wake up process waiting on s;

Assume that Pb and Vb, the wait and signal
operations on binary semaphores, are provided.
Two binary semaphores xb and yb are used to
implement the semaphore operations P(s) and V(s)
as follows:
P(s):
 Pb(xb);
 s = s - 1;
 if (s < 0)
 {
  Vb(xb);
  Pb(yb);
 }
 else Vb(xb);
V(s):
 Pb(xb);
 s = s + 1;
 if (s ≤ 0) Vb(yb);
 Vb(xb);

The initial values of xb and yb are respectively

• (a)0 and 0
• (b)0 and 1
• (c)1 and 0
• (d)1 and 1

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:
void barrier(void) {
1:  P(S);
2:  process_arrived++;
3:  V(S);
4:  while (process_arrived != 3);
5:  P(S);
6:  process_left++;
7:  if (process_left == 3) {
8:      process_arrived = 0;
9:      process_left = 0;
10: }
11: V(S);
}
Variables process_arrived and process_left are
shared and initialized to 0.
Which one of the following is true?

• (a)The barrier implementation is wrong due to the use of binary semaphore S
• (b)The barrier implementation may lead to a deadlock if two barrier invocations are used in immediate succession
• (c)Lines 6 to 10 need not be inside a critical section
• (d)The barrier implementation is correct if there are only two processes instead of three

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:

void barrier(void) {

1:  P(S);

2:  process_arrived++;

3:  V(S);

4:  while (process_arrived != 3);

5:  P(S);

6:  process_left++;

7:  if (process_left == 3) {

8:  process_arrived = 0;

9: process_left = 0;

10: }

11: V(S);

}

The variables process_arrived and process_left are
shared and initialized to zero.

Which one of the following rectifies the problem in
the implementation?

• (a)Lines 6 to 10 are simply replaced by process_arrived--
• (b)At the beginning of the barrier the first process to enter waits until process_arrived becomes zero before proceeding to execute P(S)
• (c)Context switch is disabled at the beginning of the barrier and re-enabled at the end
• (d)The variable process_left is made private instead of shared OPERATING SYSTEMS

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 operation on
semaphores 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)X: P(a) P(b) P(c)Y: P(b) P(c) P(d) Z: P(c) P(d) P(a)
• (b)X: P(b) P(a) P(c) Y: P(b) P(c) P(d) Z: P(a) P(c) P(d)
• (c)X: P(b) P(a) P(c) Y: P(c) P(b) P(d) Z: P(a) P(c) P(d)
• (d)X: P(a) P(b) P(c) Y: P(c) P(b) P(d) Z: P(c) P(d) P(a)