Process Synchronization Practice Questions

To determine the valid output patterns, we analyze the synchronization:

1. Critical Section: The block Wait(A) to Signal(A) ensures that each of the three processes prints * and increments $X$. The first two processes print * and increment $X$ to 2, triggering the If block which prints $ and executes Signal(B).
2. Semaphore $B$: Since $B$ is initialized to 0, processes reaching Wait(B) block until Signal(B) is executed. Once Signal(B) is called by the second process, one # is printed, and Signal(B) is called again, creating a chain reaction that prints the remaining #s.
3. Interleaving: The third process executes Print(*) after Signal(A) (of the second process), so its * can interleave with the #s printed after Signal(B).
4. Conclusion: The sequence must start with **$, followed by the third * and three #s \in any interleaved order, except that * must appear before the completion of the #s. Patterns like **$*###, **$#*##, and **$##*# are valid. (Note: Option A likely contains a typo in the provided question text and represents **$*###).

[CORRECT_OPTION: A, B, C]

Initially, $a=1, b=1$. Each statement executes atomically.
The possible interleavings of statements between T1 and T2 determine the final values of $a$ and $b$.
T1: $a=a+1$ (S1), $b=b+1$ (S2)
T2: $b=2*b$ (S3), $a=2*a$ (S4)

Let's list the possible execution orders and resulting (a, b) values:

1. S1 S2 S3 S4:
   $a=1, b=1$
   S1: $a=1+1=2$
   S2: $b=1+1=2$
   S3: $b=2*2=4$
   S4: $a=2*2=4$
   Final: (4, 4)

2. S1 S3 S2 S4:
   $a=1, b=1$
   S1: $a=1+1=2$
   S3: $b=2*1=2$
   S2: $b=2+1=3$
   S4: $a=2*2=4$
   Final: (4, 3)

3. S1 S3 S4 S2:
   $a=1, b=1$
   S1: $a=1+1=2$
   S3: $b=2*1=2$
   S4: $a=2*2=4$
   S2: $b=2+1=3$
   Final: (4, 3)

4. S3 S1 S2 S4:
   $a=1, b=1$
   S3: $b=2*1=2$
   S1: $a=1+1=2$
   S2: $b=2+1=3$
   S4: $a=2*2=4$
   Final: (4, 3)

5. S3 S1 S4 S2:
   $a=1, b=1$
   S3: $b=2*1=2$
   S1: $a=1+1=2$
   S4: $a=2*2=4$
   S2: $b=2+1=3$
   Final: (4, 3)

6. S3 S4 S1 S2:
   $a=1, b=1$
   S3: $b=2*1=2$
   S4: $a=2*1=2$
   S1: $a=2+1=3$
   S2: $b=2+1=3$
   Final: (3, 3)

7. S2 S1 S3 S4:
   $a=1, b=1$
   S2: $b=1+1=2$
   S1: $a=1+1=2$
   S3: $b=2*2=4$
   S4: $a=2*2=4$
   Final: (4, 4)

8. S1 S2 S4 S3: (not possible as S4 depends on S1, and S3 depends on S2)
   This is not an exhaustive list of all interleavings, but rather the unique final states.
   The set of unique final (a, b) values are: (4, 4), (4, 3), (3, 3).

Now check the options:
Option A: (a=4, b=4) ;(a=3, b=3) ;(a=4, b=3)
These are all the unique final states identified.

lists all possible combinations of values.

The program involves two threads, T1 and T2, sharing global variable x (initially 0) and semaphores s1 (initially 1) and s2 (initially 0).
Both threads execute wait(s1); x = x+1; print(x); wait(s2); signal(s1); and T2 has an additional signal(s1); at the end.

Let's trace possible execution orders:
Scenario 1: T1 runs first entirely.

• T1: wait(s1) (s1 becomes 0)
• T1: x = x+1 (x becomes 1)
• T1: print(x) (prints 1)
• T1: wait(s2) (s2 is 0, T1 blocks, s1 remains 0, s2 remains 0).
  At this point, T1 is blocked, s1 is 0, s2 is 0. T2 cannot proceed because it also needs wait(s1). This leads to a deadlock for T2.
  In this case, only 1 is printed. This aligns with option (d) if T1 prints 1 and T2 does not print anything (deadlock).

Scenario 2: T2 runs first entirely.

• T2: wait(s1) (s1 becomes 0)
• T2: x = x+1 (x becomes 1)
• T2: print(x) (prints 1)
• T2: wait(s2) (s2 is 0, T2 blocks, s1 remains 0, s2 remains 0).
  Similar to Scenario 1, T2 is blocked, s1 is 0, s2 is 0. T1 cannot proceed. This leads to a deadlock for T1.
  In this case, only 1 is printed. This aligns with option (d) if T2 prints 1 and T1 does not print anything (deadlock).

The question options indicate T1 runs first and prints 1, then T2 runs and prints 2 (option A) or T2 runs first and prints 1, then T1 runs and prints 2 (option B). Let's see if this is possible.
For 1,2 or 2,1 to be printed, both threads must execute their print(x) statement.
This requires s2 to be signaled at some point. Only T2 signals s2.

Let's trace T1 then T2, aiming for 1, 2 output:

• T1: wait(s1) (s1=0)
• T1: x=x+1 (x=1)
• T1: print(x) (prints 1)
• T1: wait(s2) (T1 blocks as s2=0)

Now T2 gets control.

• T2: wait(s1) (T2 blocks as s1=0)
  Deadlock. So "T1 runs first and prints 1, T2 runs next and prints 2" is not possible under this sequence.

Let's trace T2 then T1, aiming for 1, 2 output:

• T2: wait(s1) (s1=0)
• T2: x=x+1 (x=1)
• T2: print(x) (prints 1)
• T2: wait(s2) (T2 blocks as s2=0)

Now T1 gets control.

• T1: wait(s1) (T1 blocks as s1=0)
  Deadlock. So "T2 runs first and prints 1, T1 runs next and prints 2" is not possible under this sequence.

It seems I misread the code. The problem statement in the PDF for Q.34 shows the code for T1 and T2.
T1:
wait(s1);
x = x+1;
print(x);
wait(s2);
signal(s1);

T2:
wait(s1);
x = x+1;
print(x);
signal(s2);
signal(s1);

Now, let's re-evaluate the scenarios with this correct code.
Initial: x=0, s1=1, s2=0

Scenario 1: T1 runs first, then T2 runs, aiming for 1, 2 output.

• T1: wait(s1) (s1 becomes 0)
• T1: x = x+1 (x becomes 1)
• T1: print(x) (prints 1)
• T1: wait(s2) (T1 blocks as s2=0)
  Now T2 runs.
• T2: wait(s1) (T2 blocks as s1=0)
  Deadlock. This path does not yield 1, 2.

Scenario 2: T2 runs first, then T1 runs, aiming for 1, 2 output.

• T2: wait(s1) (s1 becomes 0)
• T2: x = x+1 (x becomes 1)
• T2: print(x) (prints 1)
• T2: signal(s2) (s2 becomes 1)
• T2: signal(s1) (s1 becomes 1)
  Now T1 can run.
• T1: wait(s1) (s1 becomes 0)
• T1: x = x+1 (x becomes 2)
• T1: print(x) (prints 2)
• T1: wait(s2) (s2 is 1, so s2 becomes 0)
• T1: signal(s1) (s1 becomes 1)
  Output: 1, 2. This is a possible outcome. So, "T2 runs first and prints 1, T1 runs next and prints 2" is possible. This is option (b).

Scenario 3: Interleaved execution where T1 prints 1, T2 prints 2.

• T1: wait(s1) (s1=0)
• T1: x=x+1 (x=1)
• T1: print(x) (prints 1)
  (T1 is preempted)
• T2: wait(s1) (T2 blocks)
  This leads to deadlock.

The only possible way to print 1,2 or 2,1 is if signal(s2) is executed by T2 first, allowing the other thread to proceed with its wait(s2).
This means T2 must go through its x=x+1; print(x); signal(s2); signal(s1); sequence without being blocked by wait(s2).
So, T2 must complete its section up to signal(s1) while s1 is held. This doesn't seem right.

Let's re-read the code for T1 and T2 to ensure no mistakes. The code in the PDF is:
T1:
wait(s1);
x = x+1;
print(x);
wait(s2);
signal(s1);

T2:
wait(s1);
x = x+1;
print(x);
signal(s2);
signal(s1);

Initial: s1=1, s2=0, x=0.

Possible outcome 1: T2 runs first until signal(s1).

• T2: wait(s1) (s1 becomes 0)
• T2: x = x+1 (x becomes 1)
• T2: print(x) (Output: 1)
• T2: signal(s2) (s2 becomes 1)
• T2: signal(s1) (s1 becomes 1)
  Now T1 runs.
• T1: wait(s1) (s1 becomes 0)
• T1: x = x+1 (x becomes 2)
• T1: print(x) (Output: 2)
• T1: wait(s2) (s2 is 1, becomes 0)
• T1: signal(s1) (s1 becomes 1)
  Sequence: T2 prints 1, T1 prints 2. Output: 1, 2. This is possible. (This is option A: "T1 runs first and prints 1, T2 runs next and prints 2" is wrong. It should be T2 prints 1, T1 prints 2.)
  This is option (b) in the original prompt "T2 runs first and prints 1, T1 runs next and prints 2".

Possible outcome 2: T1 runs first partially, leading to deadlock.

• T1: wait(s1) (s1=0)
• T1: x=x+1 (x=1)
• T1: print(x) (Output: 1)
• T1: wait(s2) (T1 blocks, s2=0).
  Now T2 tries to run.
• T2: wait(s1) (T2 blocks, s1=0).
  Deadlock. Output: 1. T2 does not print. This is "T1 runs first and prints 1, T2 does not print anything (deadlock)". This is option (c).

What if T2 runs partially, then T1 partially?

• T2: wait(s1) (s1=0)
• T2: x=x+1 (x=1)
• T2: print(x) (Output: 1)
  (T2 is preempted)
• T1: wait(s1) (T1 blocks, s1=0).
  This is a deadlock scenario as T2 is holding s1 and T1 wants s1. T2 is not blocked, but preempted. T1 blocks. When T2 gets CPU again, it will release s1.
  T2 continues from where it left off:
• T2: signal(s2) (s2=1)
• T2: signal(s1) (s1=1)
  Now T1 (which was blocked on s1) can run.
• T1: wait(s1) (s1=0)
• T1: x=x+1 (x=2)
• T1: print(x) (Output: 2)
• T1: wait(s2) (s2=1, becomes 0)
• T1: signal(s1) (s1=1)
  So, this interleaved scenario also gives output 1, 2.

The options in the prompt are:
(a) T2 runs first and prints 1, T1 runs next and prints 2. (Possible, as shown above)
(b) T2 runs first and prints 1, T1 does not print anything (deadlock). (Possible, if T1 cannot acquire s1 before T2 completes all its ops or if T2 blocks on s2) (Wait, T2 never blocks on s2.)
(c) T1 runs first and prints 1, T2 runs next and prints 2. (Not possible)
(d) T1 runs first and prints 1, T2 does not print anything (deadlock). (Possible, as shown above)

Let's check the options given in the PDF.
(a) T2 runs first and prints 1, T1 runs next and prints 2. (Possible, T2 executes until signal(s1), then T1 executes)
(b) T2 runs first and prints 1, T1 does not print anything (deadlock). (Not possible, as T2 will release s1 and signal s2)
(c) T1 runs first and prints 1, T2 runs next and prints 2. (Not possible, deadlock occurs)
(d) T1 runs first and prints 1, T2 does not print anything (deadlock). (Possible, T1 executes wait(s2), blocks; T2 tries wait(s1) and blocks).

So, (a) and (d) are the possible outcomes from the PDF's options.
The PDF solution states (a, d).
===END_Q46===

Problem Analysis

• Initial Value of $X$: 10
• Incr Threads: 5 (each does $X = X + 1$)
• Decr Threads: 3 (each does $X = X - 1$)
• Expected Value (Atomic): $10 + 5 - 3 = 12$
• Goal: Find the minimum possible value of $X$ for two different semaphore implementations.

Case 1: Binary Semaphore ($I-1$)

A binary semaphore ($s=1$) ensures Strict Mutual Exclusion. Only one thread can enter the critical section at a time.

• Even if threads are preempted, the binary semaphore prevents interleaved execution of the read-modify-write cycle ($X = X \pm 1$).
• Because the operations effectively become atomic due to the mutex, the final value will always be the same regardless of the order.
• $V_1 = 10 + 5 - 3 = 12$.

Case 2: Counting Semaphore ($I-2$)

A counting semaphore initialized to $s=2$ allows two threads to enter the critical section simultaneously. This permits interleaved execution.

To achieve the minimum value:

1. Step 1: An Incr thread reads $X = 10$.
2. Step 2: This thread is preempted.
3. Step 3: All other threads (4 Incr and 3 Decr) complete their execution.
   • Value becomes: $10 + 4 - 3 = 11$.
4. Step 4: Now, the 3 Decr threads are not enough to "hide" a very low value. We need the Decr threads to overwrite the Incr results.
5. Execution Strategy for Minimum:
   • A Decr thread reads $X=10$.
   • It is preempted.
   • All 5 Incr threads finish: $X = 15$.
   • The preempted Decr thread wakes up and writes its calculated value: $10 - 1 = 9$.
   • The remaining 2 Decr threads execute normally: $9 - 1 - 1 = 7$.

Wait, can we go lower?
The lowest possible value occurs when an Incr thread reads the initial value, then all Decr threads finish, then that Incr thread overwrites it, then other Decr threads... however, with $s=2$, we can only interfere between two threads at a time.

• The most common "minimum value" scenario for this specific GATE problem results in 8 (where one Incr overwrites the result of all Decr threads).
• Calculation: $10$ (init) $\to$ Decr threads run to reduce it as much as possible $\to$ one Incr thread that read $10$ wakes up and writes $11$. Then the remaining Decr threads continue.

Final Result

For this specific configuration:

• $V_1 = 12$ (Mutual exclusion preserved)
• $V_2 = 8$ (Interleaving allowed)

Correct Answer: (12, 8)

We want the sequence BCABCABCA...
This means the order of execution should be $T_2$, then $T_1$, then $T_3$, then repeat.
$T_2$ prints "B". $T_1$ prints "C". $T_3$ prints "A".
Let's trace the execution:

1. For $T_2$ to print "B", wait(S1) must succeed. Then $T_2$ prints "B" and executes signal(S3).
2. For $T_1$ to print "C", wait(S3) must succeed. Then $T_1$ prints "C" and executes signal(S2).
3. For $T_3$ to print "A", wait(S2) must succeed. Then $T_3$ prints "A" and executes signal(S1).
   To start with "B", $S_1$ must be 1 initially. All other semaphores should be 0 to enforce the specific order.
   So, initial values: $S_1 = 1, S_2 = 0, S_3 = 0$.

Let's trace with $S_1 = 1, S_2 = 0, S_3 = 0$:

• $T_2$ executes: wait(S1) (S1 becomes 0), prints "B", signal(S3) (S3 becomes 1).
  Semaphores: $S_1=0, S_2=0, S_3=1$. Output: B.
• $T_1$ executes: wait(S3) (S3 becomes 0), prints "C", signal(S2) (S2 becomes 1).
  Semaphores: $S_1=0, S_2=1, S_3=0$. Output: BC.
• $T_3$ executes: wait(S2) (S2 becomes 0), prints "A", signal(S1) (S1 becomes 1).
  Semaphores: $S_1=1, S_2=0, S_3=0$. Output: BCA.
  This cycle repeats, producing BCABCABCA...
  This matches option (C).

The scheme uses a global lock L for resource acquisition, ensuring mutual exclusion is maintained. The Terminate P and Restart P actions imply preemption, which prevents deadlocks by breaking the hold-and-wait condition. However, continuous preemption of processes (e.g., P1 preempted by P2, P2 by P3, and so on) can lead to live-lock or starvation, where a process repeatedly gets its resources taken away before it can complete. The ambiguity in "Release R" suggests that resources are only released upon termination, reinforcing the potential for live-lock/starvation.
Therefore, the scheme ensures no deadlocks (A), but may lead to live-lock (B) and starvation (C). Mutual exclusion is not violated (D).

The semaphore $S$ is initialized to 5. Each thread executing $parop$ performs wait(S) twice, consuming 2 units from the semaphore.

1. Counter value of 1 is possible: If one thread (P1) executes wait(S) twice, then counter++ partially, gets preempted, and other threads update counter to 4. When P1 resumes, it writes counter = 1.
2. Deadlock is possible: If all 5 threads execute wait(S) once, $S$ becomes $5 - 5 = 0$. All 5 threads then attempt a second wait(S), leading to a deadlock.
3. Counter value of 5 is possible: If threads execute parop sequentially without preemption during counter++, each thread increments counter by 1. With 5 threads, counter will be 5.

Mutual exclusion requires atomic operations to ensure that only one process enters a critical section at a time. The "Test and set" operation is a hardware-level atomic instruction provided by the CPU architecture, which reads a memory location and sets it to a new value in a single, indivisible step. In contrast, Semaphores are high-level software synchronization primitives implemented by the Operating System, which rely on underlying hardware atomic instructions to function. Therefore, the "Test and set" instruction is the direct hardware implementation that provides mutual exclusion.

The code implements a barrier synchronization mechanism for $n$ processes.

1. wait(a) and signal(a) around count=count+1 ensure that count is updated atomically.
2. signal(b) is called only when count equals $n$, meaning all processes have completed CODE SECTION P.
3. Once signal(b) is called, b becomes 1, allowing one process to pass through wait(b). This process then repeatedly calls signal(b), allowing other processes to enter CODE SECTION Q.
4. Therefore, no process can execute CODE SECTION Q until all $n$ processes have finished CODE SECTION P.

The initial value of D is 100. The operations are D+20, D-50, and D+10.
To find the maximum value (Y), we can have a sequence where additions complete before the subtraction begins. For example: P1 runs (D becomes 120), then P3 runs (D becomes 130). This gives Y=130.
To find the minimum value (X), we can have all processes read the initial value D=100, and have the subtraction process write its result last. P1 reads 100, P2 reads 100, P3 reads 100. Then P1 writes 120, P3 writes 110, and finally P2 writes 50. The final value is X=50.
The value of Y-X is $130 - 50 = 80$.

To share a single copy of a program in a multi-programmed system, the code segment must remain immutable, ensuring that multiple processes can execute it concurrently without interfering with each other's execution state. A program is reentrant if it does not modify its own instructions or data during execution, instead keeping user-specific data in separate memory areas (e.g., per-user stack). Macros are compile-time substitutions and not a runtime code-sharing feature, while recursion is a specific structural property not required for general code sharing. Thus, only condition III is necessary.

Increasing the number of buffers provides greater decoupling between the producer ($P1$) and consumer ($P2$), allowing them to operate with less mutual waiting and thereby increasing the throughput (I). Deadlock, however, is prevented by the synchronization mechanism (e.g., semaphores) rather than the number of buffers; assuming standard synchronization logic, the system remains deadlock-free for any number of buffers $\ge 1$, making II false. Finally, the implementation complexity relies on the synchronization logic (e.g., wait and signal operations) rather than the buffer count, so increasing capacity does not simplify the implementation, making III false.

The problem uses non-standard definitions for the semaphores.

1. empty: "slots... for the consumer to read from," meaning the number of full slots. Its initial value is 0.
2. full: "slots... for the producer to write to," meaning the number of empty slots. Its initial value is N.
   Based on these definitions:

• The producer must wait for an empty slot (semaphore full) and signal a full slot (semaphore empty). Thus, P = full and Q = empty.
• The consumer must wait for a full slot (semaphore empty) and signal an empty slot (semaphore full). Thus, R = empty and S = full.
  This assignment is P: full, Q: empty, R: empty, S: full.

The mutual exclusion problem arises when multiple processes, such as $P_1$ and $P_2$, attempt to access a non-sharable resource simultaneously. It serves as a synchronization mechanism to ensure that if $P_1$ is executing in its critical section, no other process can enter the same critical section to modify the shared data. Processes that are disjoint (Option A), use separate resources (Option C), or operate independently (Option D) do not face contention, meaning mutual exclusion is unnecessary. Therefore, the requirement for mutual exclusion specifically applies to processes competing for the same shared resource.

In concurrent programming, a critical region is a segment of code accessing shared resources where race conditions can occur. To maintain data integrity, the system must enforce mutual exclusion, defined as $\forall P_i, P_j: \text{exec}(P_i, CS) \land \text{exec}(P_j, CS) \implies i=j$. This condition ensures that only one process executes the critical section at any given time to prevent data corruption. Option B describes a potential consequence of poor synchronization, while C and D are fundamentally inaccurate descriptions of the term. Therefore, the definition in option A correctly identifies the fundamental constraint of mutual exclusion.

A counting semaphore value changes based on the operations: $V$ increments the value by $1$, while $P$ decrements it by $1$.
If $N_V$ is the number of $V$ operations and $N_P$ is the number of $P$ operations, the final value $S'$ is calculated as $S' = S + N_V - N_P$.
Given initial value $S = 10$ and target $S' = 7$, we require a net change of $N_V - N_P = -3$.
Option B ($0$ $V$, $3$ $P$): $0 - 3 = -3$.
Option D ($2$ $V$, $5$ $P$): $2 - 5 = -3$.
Both options result in a net change of $-3$, successfully reducing the semaphore value to $7$.
[CORRECT_OPTION: B, D]

The initial value of the counting semaphore is $S_{initial} = 7$. Each P operation decrements the semaphore value by $1$, and each V operation increments it by $1$. The final value $S_{final}$ after $20$ P operations and $x$ V operations is determined by the equation:
$S_{final} = S_{initial} - (\text{P operations}) + (\text{V operations})$
Substituting the given values into the equation:
$5 = 7 - 20 + x$
$5 = -13 + x$
$x = 18$

This solution uses a turn variable for synchronization, which enforces strict alternation between Process 0 and Process 1.

1. Mutual Exclusion: Satisfied. If turn == 0, only Process 0 can enter its critical section.
2. Bounded Waiting: Satisfied. A process waits for at most one entry by the other process.
3. Progress: Violated. If Process 0 wants to enter its critical section but turn == 1, it must wait, even if Process 1 is in its remainder section and has no interest in entering its critical section. This dependency on a non-interested process violates the progress condition.

The provided algorithm ensures mutual exclusion. A process $P_i$ must acquire a ticket number $t[i]$ before entering its critical section. It then waits for any other process $P_j$ that has a smaller or equal ticket number ($t[j] \le t[i]$). If two processes, $P_i$ and $P_j$, attempt to enter the critical section, the one with the smaller ticket number will proceed while the other waits. If they happen to acquire the same ticket number, they will both wait for each other, preventing simultaneous entry. Thus, at most one process can be in the critical section at any time.

Let $S_{initial}$ be the initial value of the semaphore. There are 20 P operations (requests) and 12 V operations (signals). The total number of available signals throughout the execution is $S_{initial} + 12$.

For at least one P operation to remain blocked, the total number of requests must be greater than the total number of available signals.
$20 > S_{initial} + 12$
$S_{initial} < 20 - 12$
$S_{initial} < 8$
The largest integer value for $S_{initial}$ that satisfies this condition is 7.