Question

Consider the following pseudocode, where S is a semaphore intialized to 5 in line#2 an counter is a shared variable intialized 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?

1.

There is a deadlock involving all the threads.

2. The value of counter is 5 after all the threads successfully complete the execution of parop.
3. The value of counter is 1 after all the threads successfully complete the execution of parop.
4. The value of counter is 0 after all the threads successfully complete the execution of parop.

Answer 1

Correct Answer - Option :

Answer: Option 1, Option 2 and Option 3

Explanation:

Increment operation in Line 7 is not atomic means while incrementing the variable process/thread can be preempted.

Increment Generally performed below mentioned 3 steps in assembly language.

load R₁, counter; // load value of counter from memory to register R₁

add R₁,#1;           //add 1 to the content of register R₁.

store R₁, counter;  //Store incremented value in counter (Memory)

Option 1:There is a deadlock involving all the threads.

This Option is Correct.

Now Thread 1 executes till line 5 and preempts; Now S=4,

Thread 2 executes till line 5 and preempts; Now S=3,

Thread 3 executes till line 5 and preempts; Now S=2,

Thread 4 executes till line 5 and preempts; Now S=1,

Thread 0 executes till line 5 and preempts; Now S=0 and if any of threads Resumes; they all will perform unsuccessful down operation and all will be blocked no one to wake up the threads. This is a Deadlock situation.

Option 2:The value of the counter is 5 after all the threads successfully complete the execution of parop.

This Option is Correct.

Option 3:The value of the counter is 1 after all the threads successfully complete the execution of parop.

This Option is Correct.

Thread 1 start execution and line 7, it performs the following

load R1, counter;

add R1,#1; //R₁ contains 1

and now it preempts 

Thread 2 start execution and finishes.

Thread 3 start execution and finishes

Thread 4 start execution and finishes

Thread 5 start execution and finishes.

and Now Thread 1 Resumes.

store R1, counter;  // it overwrite counter as 1;

Option 4:The value of the counter is 0 after all the threads successfully complete the execution of parop.

This is incorrect. Counter =0 not possible after all the threads successfully complete, Minimum value possible is 1.