This week's book giveaway is in the Mac OS forum. We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line! See this thread for details.
I've recently had a telephonic interview and I quite enjoyed it cause it was more like a discussion. The interviewer asked me a question that I tried to answer, but it seems the interviewer was looking for something else which is a very 'easy to see/analyze' thing that I couldn't even think of. Also during the interview, I had no access to any visible piece of code.
We started with different topics and ultimately in one of my answers I mentioned the Observer pattern. So the interviewer started asking me questions about the Observer pattern. In one my answers, I said we could write a modified version of it by making Observable also an interface.
The interviewer immediately asked me a question that I had to really think a lot about. He said what if an observer de-registers at the same time as when the observable changes.
I said clearly there is a race condition here and we need to synchronize the access, so de-registration cannot happen at the same time as the update. He then asked where would this de-registration code be coded. I said it would be declared in the source interface, implemented by the handler class that would maintain listeners for a source, and it would be invoked by the listener. The listener method that would invoke this code would have to be synchronized with the method which the handler invokes when the observable changes.
Then he said there is a very apparent problem here that I have missed.
I thought for two more minutes and then said that the handler probably would also have a collection that would store the listeners for a source. It would have a method that would be invoked by the listeners for de-registration and a method that would update all listeners when the observable changes. So it might be possible that after the observable changes, the handler creates an iterator to update all the listeners but the listener might have invoked the de-registration code after the iterator is created by the handler. So if the synchronization is not correct, the iterator might throw a ConcurrentModificationException.
It seems I still hadn't even touched upon what the interviewer was looking for. And it was just a telephonic round with us having no access to any visible code so it was hard for me to remember how everything functions and to imagine and answer. But what is it I must be missing here? It must be a widely known thing cause he said there is clearly a problem that I hadn't even mentioned.
What is it I may have missed? Was anything I said incorrect?
Trying to guess what someone was thinking is impossible (especially when we don't know the specifics about the conversation). If he didn't share his apprehension then I wouldn't worry about it too much.
My thought when reading your description would be about throughput, I could imagine if multiple notifications came in then they would all be competing with each other for the synchronized lock, and could slow the system down. I might consider using a ReadWriteLock so as to let multiple notifications to happen without collision, but removing a listener (or adding a new one) would be a Write operation and would be isolated from other access.
You could also use the 'snapshot' view of the listener collection, like a CopyOnWrite type of collection, if you suppose adding and removing listeners aren't very frequent.
Yet another approach is to force all notifications and listener registration/de-registration to happen on a single dispatching thread so collisions are impossible. Every registration, deregistration, and notification signal would put a task in a queue, and the dispatcher thread would consume the queue executing all the tasks in the order they entered it. Your observable pattern would then mimic the EDT thread in GUIs with all the associated suggestions to keep processing short or push long processing off to worker threads to prevent notification backup.
But it really all depends on the environment and system, really.
Chan, you second guess is somewhat right. Listener manipulations may be called during listeners notification phase. But this does not require multiple threads:
Steve answer is correct when dealing with multiple threads. But not all solutions solve reenterability problem. However, that solutions (for a thread-safety) may be used alongside some solutions for reenterability.
Some solutions for reenterability problem:
1. Provide a way to run some code after all listeners are notified. For example, register runnable in the event and call them after all listeners are notified.
2. Clone list of listeners each time before the iteration and iterate on clone, not an original list. Swing uses this approach. Look into javax.swing.event.EventListenerList for future details.
3. Hold another queue for "deferred actions". Mark object "unsafe" during change. When listener manipulation is requested in "unsafe" state, register change in the "deferred actions" queue instead. Run all deferred actions after original update is complete. Something like "last chance" solution but more specialized and with completely different API.
4. Use CopyOnWrite collection.
5. Use "event-dispatching" approach and require to perform listener manipulations in it's own transaction. Key point is that no deregistration is allowed in the listener. Listener should put another task in event queue to deregister itelf.
Note that solutions 1-3 are not thread-safe by itself. So you also need to choose some approach to threading problem (one thread for all handlers or proper locking). Solution 4 is good for both problems.
I use different solutions in different situations. Usually I prefer CopyOnWrite collections in Java, "action queues" for general listeners in JS and "last-chance" listeners for special cases like reactive programming (functions over observables).
Joined: Sep 06, 2012
Thanks, Steve and Maxim, for your responses.
Yea, I felt weird also, while answering this question because it all depends on the implementation. We can have a pattern implemented in many ways. A pattern does not state what data structures to use, and it is not a definitive guide about the subset of operations that can be performed on the objects ( it is just a guideline and it knows nothing about our business requirement ) and what degree of parallelism can be obtained. The worst part was I was not left to myself to figure the answer; I had the phone in one hand with a continuous voice sort of disturbing my ability to think ( though yes he was only trying to give me hints and help me arrive at the specific points he was looking for ), and a paper and pencil in the other hand to jot down the points. Clearly the approach didn't work.
I did mention CopyOnWrite collections to him, but it seems he had some other aspect in mind. Perhaps it must be performance or handling of extraneous notification ( I thought the client code would handle 'em well and they shouldn't be an issue worth discussing ), something to do with the event dispatching thread of Swing/graphics APIs. I have no knowledge/experience of Swing and graphics APIs so I wouldn't know about it. If he was expecting an answer related to event dispatching thread, I wouldn't know.
Ok, so based on your responses, it looks like I may not have excluded some very widely known, biggie thing from my answer. I understand though that all of the above are also very significant aspects when we are working on critical projects where inaccuracies can be fatal. With this in my mind, if I come across a related task in future, I will try to think of these points too - at least I know there is more to research on if I'd work on advanced stuff ever.
I understand it feels weird to answer a question which is based on another person's apprehensions and hence I wasn't expecting speedy responses/responses at all. But like always, you've been a magic help. Thanks so much.
subject: Interview Question -What if the listener deregisters at the same time as when the observable changes