Discussion
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 decr 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, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively.
Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively?
Answer: C
The minimum values are V1 = 12 and V2 = 7.
I-1. A binary semaphore initialised to 1 lets only one thread into the critical section at a time, so every update is applied in full and the result is the same in every run:
\[ V_{1} = 10 + 5 - 3 = 12 \]
I-2. A counting semaphore initialised to 2 lets two threads update X together, so one update can overwrite another (X = X+1 is a read, an add and a write). To make X as small as possible: a decr thread reads X = 10 and pauses inside. Meanwhile the five incr threads pass one by one through the second slot, raising X to 15. The paused decr then writes 9, wiping out all five increments. The other two decr threads run normally: 8, then 7.
No run can end below 7, because the three decrements can lower X by at most 3 from 10. So V2 = 7. 15 and 7 as V1 are impossible under mutual exclusion, and 8 is reachable but is not the minimum.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development