Consider the two functions and shown below.
incr(){ decr(){
wait(s); wait(s);
X = X+1; X = X-1;
signal(s); signal(s);
} }
There are threads each invoking once, and threads each invoking once, on the same shared variable . The initial value of is
Suppose there are two implementations of the semaphore as follows:
is a binary semaphore initialized to
is a counting semaphore initialized to
Let be the values of at the end of execution of all the threads with implementations respectively.
Which one of the following choices corresponds to the minimum possible values of respectively?
View worked solution
Answer: C
To find the minimum possible values of at the end of execution for both implementations:
Case I-1: Binary Semaphore initialized to
- A binary semaphore initialized to ensures strict mutual exclusion. Only one thread can enter the critical section at any given time.
- Therefore, all increments and decrements will execute sequentially in some order.
- The final value of will always be:
Case I-2: Counting Semaphore initialized to
- Since , up to two threads can enter the critical section concurrently, allowing race conditions.
- To minimize the final value , we can construct a schedule where the effects of the increment threads are overwritten:
- A decrement thread enters the critical section, reads into its local register, and is preempted before writing.
- Since was initially and is now , another thread can enter. All increment threads ( to ) execute sequentially one after another. becomes .
- resumes, decrements its local value of to , and writes back to memory (overwriting the value ).
- The remaining two decrement threads and execute sequentially, reducing from .
- Thus, the minimum possible value is .
Therefore, the minimum values of and are and , respectively.
Free practice · Your answers on this page are not saved.