Question

Instructions: Write your answers in MS Word and submit your homework as a PDF via email by the deadline. 1. Briefly describe what the producer/consumer problem is and how it can be solved using semaphores. const int n-50 int tally void total () int count; for (count 1 count<- n count++) tally++ void main () tally O parbegin (total , total write (tally) 2. Consider the above program. What are two possible final values of the shared variable tally? Assume that the two processes run concurrently and they can execute at any relative speed only one program is allowed to access this function at a time. In the space below, write a pseudocode algorithm for a program that uses the exchange instruction for mutual exclusion to call the processO function.

Answer 1

1. The producer consumer problem is one in which there are two threads using a bounded queue in the following fashion: Producer pushes an item onto the queue unless it is full, consumer pops an item unless it is empty. If the queue is full, producer thread goes to sleep until something has been popped. Similarly, consumer goes to sleep on empty queue until something gets pushed.

Consider the following scenario: consumer checks the queue and finds it empty, but gets interrupted before it can go to sleep by the producer thread being scheduled. This will send the signal that something has been pushed onto the queue. But, the consumer thread has not yet gone to sleep, hence it doesn't wake up. But when it does get scheduled again, it continues from the last point of execution, which was going to sleep, hence it goes to sleep. Now, nothing is being consumed and the producer will simply keep pushing till the queue becomes full, and then it will also go to sleep. This is a deadlock.

This can be solved by using a semaphore in the following way: The consumer thread locks the semaphore before reading the queue and unlocks it after finishing its processing. Similarly for the producer thread. This way, they can never in the deadlock situation as described above.

2. Tally is initialized to 0, and both threads will try to increase it 50 times. If no race conditions occur, then both will increase it by 50, and the final will be 100.

But, say thread A has read the variable and calculated what value to write, but it gets interrupted by thread B. Thread B still reads the old value, increases it by 1 and writes it. A is now scheduled, but had already calculated what to write, and does so. Thus, effectively, tally is only increased by 1, although both the threads went through one loop. This could happen all 50 times, hence the tally at the end might just be 50.

Hence, two values are 100 and 50.

Comment in case of any doubts.