CSE647: Testing and Verification Homework 4 (ver. 2 Oct, 10:00) Due 9 Oct 2000 Scott Stoller 1. Everyone gave similar answers to hw2, problem 1, but I think none of them are completely correct. I believe you will learn more from thinking about it again than from reading an answer, so please try this problem again. Recall the problem: Consider changing notifyAll to notify in the code for remove(). Is this a good idea? Justify your answer. Big hint: Consider a queue with capacity 1. Construct a scenario in which a thread doing remove and a thread doing insert are simultaneously waiting, and they might end up waiting forever. NOTE: Actually, I had in mind replacing notifyAll with notify in insert AND remove, and this is the basis for my answer below. All reasonable answers to this problem received full credit. Answer: Consider the following scenario. |q|=0 theta1: call remove. wait. theta2: call remove. wait. theta3: call insert. notify theta1. theta1 does not run yet. |q|=1 theta4: call insert. wait. theta1: continue in remove. notify some waiting thread, say, theta2. |q|=0 theta2: continue in remove. wait again. theta2 and theta4 might both wait forever. This is a kind of deadlock. 2. Your answer to hw2, problem 1, affects by your answer to hw2, problem 2, so here is a variant of that problem. Give modified code for Queue.java that performs no unnecessary notifications and does not allow threads to wait forever unnecessarily. Document your modifications either with comments in the code or with a separate explanation. Answer: The basic problem is that a thread running remove might notify a thread waiting in remove rather than one waiting in insert. The simplest way to avoid this is to introduce 2 additional objects; let's call them removewait and insertwait. Threads in remove wait on removewait; threads in insert wait on insertwait. remove contains a call to insertwait.notify; insert contains a call to removewait.notify. If your answer did not work this way, it is a good idea to try to write code that works this way. If you have any questions, please ask.