I am stuck while solving a counting semaphore problem in Operating system subject.
S is a semaphore initialized to 5.
count = 0 (shared variable)
Assume that the increment operation in line #7 is not atomic.
Now,
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 the 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
what i have understand till now is answer is A and D,because what if all process are executed one by one say(T1->T2->T3->T4->T5) and final value saved will be 5(so A is one of correct options) Now, why D,because what if all process execute line 5 before 6 and will get blocked.
Now, please can any one help me to understand why B is another correct answer. ?
Thanks in advance,
Hope to here from you soon
Any help will be highly appreciated.
CodePudding user response:
Imagine thread 1
gets to line 7 before any other thread, and line 7 is implemented as three instructions:
7_1: load counter, %r0
7_2: add $1, %r0
7_3: store %r0, counter
For some reason (eg. interrupt, preempted), thread 1
stops at instruction 7_2
; so it has loaded the value 0 into register %r0
.
Next, thread's 2..5
all run through this sequence, leaving counter at say 4
.
Thread 1
is rescheduled, increments %r0
to the value 1
and stores it into counter
.