Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Denny's DVD ReservationsManager - signal()

 
John Stone
Ranch Hand
Posts: 332
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My doubt is regarding signal() used in Denny's DVD ReservationsManager. There is only one Lock and one Condition, on which all threads are waiting. But in release DVD only one thread is signalled - and there is no guarantee which thread it will be.


Here is the basic skeleton of ReservationsManager:


And my doubt is line


If there are more threads waiting, then we can't be sure which thread will be signalled. What if thread waiting for another record is signalled when some thread release record.

Now imagine situation:


Time is going from up to down. And we have 4 thread here, and 2 records (A,B)
+X - this thread successufuly acquired lock on record X
-X - thread can't acquire lock on record X (it is locked by other thread)
*X - lock on record X was released by this thread

- Thread 1 acquires lock on record A
- Thread 2 acquires lock on record B
- Thread 3 is trying to acquire lock on A, but fails and is waiting
- Thread 4 is trying to acquire lock on B, but fails and is waiting
- Thread 1 releases lock on A, signal is notifying one thread, unfortunetaly it is the thread 4, which wakes up and finds, that B is still locked by Thread 2, so it is going again to wait
- Thread 2 releases lock on B, signal is notifying one thread, and again it is thread 4, B is now free, so Thread 4 is able to acquire lock
- Thread 3 is still waiting (but record A is free)

Is there some error in my logic? (As I can't believe there is error in book)
[ June 14, 2007: Message edited by: John Stone ]
 
rinke hoekstra
Ranch Hand
Posts: 152
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good point. I was wondering that too, when I read it last week. Why signal?
 
John Stone
Ranch Hand
Posts: 332
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since there was no replies, I made a test to check signal() used in Denny's DVD ReservationsManager

source code of Denny's DVD can be found on apress homepage:
http://www.apress.com/book/supplementDownload.html?bID=461&sID=3239

source code of my test can be found here:
http://1024labs.org/john.stone/SignalTest.htm
http://1024labs.org/john.stone/SignalTest.java

How did I test it:


I run a few threads, first of them lock record A for one second. This should give enough time to start all 25 threads which then start to fight for record B. One of them wins and block other threads, after 5 seconds all threads trying to lock "B" timeout.

Will be the last thread able to lock on A?

Well see for yourself (ignore all "B" lines, just see what happens to "A")


So, the 25 threads fighting over "B" caused that release notification from thread holding "A" was lost and some wrong thread was notified (which was interested only in "B" record).

I believe "signal()" used in this situation is wrong.
[ June 15, 2007: Message edited by: John Stone ]
 
rinke hoekstra
Ranch Hand
Posts: 152
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi John,

Good testing, thanks (for yourself and for me :-) ).

The outcome of the test is indeed what I would expect on theoretical reasoning.

I wonder what Andrew's comment on this would be.

Rinke
 
Ken Boyd
Ranch Hand
Posts: 329
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Even I had same thinking and prove in testing mine is cookie base URLyBird assignment. Also make sure you don't face race condition when you have signalAll() since it will wake up all waiting thread.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic