Note: I originally put this message into the "how can you avoid nested synchronization" thread started by Wayne John; but now decided to start a new thread on this subject
Here we go :
Andrew Monkhouse said (in the thread mentioned above)
While you should always try to avoid nested synchronization, sometimes it is not possible to avoid it totally. As long as you always nest in the same order you should be OK.
I guess we need 1) to determine what objects need to be accessed in a multi-thread safe fashion; 2) and then determine how it can be achieved. That is what I've got so far:
1. For the logical locking (ie record locking) there is a static lockedRecords map that stores key/value pairs where the key is a record number and a value is a client who has locked it
2. For the physical locking (ie file locking) there is a static dbFile object that provides read/write access to the database file (it delegates read/write tasks to the instance of RAF)
3. For the record cache there is static recValidFlags list in which an element position represents a record number and the actual element is a record validity flag (of byte type, either Data.VALID_RECORD or Data. DELETED_RECORD). The actual number of elements in this list represents a total number of records in the file (both deleted and valid).
recValidFlags is initially populated on the start up (when the database file is chosen by the user) and is then maintained by the Data instances.
Collections.synchronizedList(new ArrayList<Byte>()) method is used to create a List instance used for this cache, which makes access to recValidFlags methods multi-thread safe.
The recValidFlags cache is used for a) checking whether the record exist; b) determining in what position to create a new record.
The recValidFlags cache is modified when a) a new record is created ; b) when a record is deleted
Data instances will synchronize on these three static objects ( ie lockedRecords / dbFile / recValidFlags ) in the following manner:
Did you use the synch mechanism that you described in that post? Or did you do some last modifications?
I've modified it - i moved recValidFlags cache into the dbFile. In addition, lockedRecords cache is now used store Record objects , which can be locked / unlocked.
Data#lock(int recNo)
The unlock method extracts Record#recNo, unlocks it and notifies all threads that are on the Record#recNo object's waiting list.
- Did you synch on dbFile when changing database file as well?
- I don't see that it is possible for two threads to read two different records?
I am synchronising on the dbFile whenever it needs to be accessed for reads or writes. Therefore, it is not possible for two threads to read two different records at the same time. While not the most efficient I think it is the simplest solution , which allows for the multi-thread safe access to the database file. What do you think?
In your unlock method, is the first check of recNo in recValidFlags necessary? You have to check after getting the record lock anyway, so the first check one seems like extra work. [ February 06, 2006: Message edited by: B Chen ]
I believe using notifyAll() violates the requirement that a Thread must consume no CPU cycles while waiting for a request. Do a forum search on "notifyAll" for past threads related to this issue.
In your unlock method, is the first check of recNo in recValidFlags necessary? You have to check after getting the record lock anyway, so the first check one seems like extra work.
I think you meant lock method. I think it makes sense to check whether the record exist before starting to work on getting the record lock . Otherwise, we could do all the work (getting the monitor, waiting, getting the monitor again, waiting again, etc) just to discover that the record does not exist.
Kevin wrote:
I believe using notifyAll() violates the requirement that a Thread must consume no CPU cycles...
but notify does not guarantee that a particular thread will ever be notified. So I think it's fairer to allow all waiting threads to get back into the ready state, compete for the monitor and go into waiting state again if required.
but notify does not guarantee that a particular thread will ever be notified. So I think it's fairer to allow all waiting threads to get back into the ready state, compete for the monitor and go into waiting state again if required.
Kind regards.
Alex,
You are correct in that notify() does not guarantee a particular thread will be notified. However, it does guarantee that a thread will be notified, provided that one is waiting for the lock. You shouldn't write code that depends on threads being notified in a certain order.
Again, using notifyAll() will consume extra cpu cycles each time the Thread is woken up, even if it doesn't obtain the lock.
You are correct in that notify() does not guarantee a particular thread will be notified. However, it does guarantee that a thread will be notified, provided that one is waiting for the lock
But what if a waiting thread never gets notified? As far as I understand if we use notify then we're completely dependant on the Thread Scheduler , which will notify a thread but might never notify another thread . However, if we use notifyAll then at least we know that the Thread Scheduler will notify all waiting threads and they will have an equal chance to compete for the monitor and eventually lock the resource. [ February 07, 2006: Message edited by: Alex Sharkoff ]
Whether you call notify() or notifyAll(), only one thread gets the lock. It doesn't matter if they wake up or not, only one thread is going to get it. The only way a thread won't get notified is if the owner of the lock doesn't call notify(). The only way a thread won't get notified is if notify() or notifyAll() is not called at all. It makes no difference which one is called in terms of acquiring the lock.
Whether you call notify() or notifyAll(), only one thread gets the lock. It doesn't matter if they wake up or not, only one thread is going to get it. The only way a thread won't get notified is if the owner of the lock doesn't call notify()
What I am trying to say is that notify() will notify any thread, and there is no guarantee that it will notify a thread that's been waiting for a while. It might even to decide to never notify it. That's what API says for notify:
Wakes up a single thread that is waiting on this object's monitor. If any threads are waiting on this object, one of them is chosen to be awakened. The choice is arbitrary and occurs at the discretion of the implementation.
Imagine, if you've got threads coming in all the time and jumping on the waiting list. If we notify then Thread Scheduler might keep notifying the very last thread that jumped on the waiting list. [ February 07, 2006: Message edited by: Alex Sharkoff ]
Imagine, if you've got threads coming in all the time and jumping on the waiting list. If we notify then Thread Scheduler might keep notifying the very last thread that jumped on the waiting list.
[ February 07, 2006: Message edited by: Alex Sharkoff ]
Well, those are the breaks The Thread scheduler is going to pick who it wants to pick. The exact same scenario can occur using notifyAll(). Just because the threads are "awake", it doens't give them a better shot at the lock.
notifyAll() is used to allow the threads to do something else if they are not chosen for the lock, not to ensure that they get the lock in some "fair" manner.
If you want the Threads to get the lock in first-come, first-serve, you have to build in some kind of queue, the Thread scheduler does not have any concept of what is "fair" in obtaining a lock.
notifyAll(), and signalAll(), wakes up all threads. All of them will, in turn, get the lock. What they do once they get the lock depends on the condition they are waiting for. For example
Two records are locked and two thread waiting for them. If thread-A uses notify, one thread is woken. If thread-C happens to be woken, it will find rec-2 still locked and must continue waiting. Thread-B would have been able to do work based on the change, but was not woken. So notifyAll() must be used to ensure both thread-B and thread-C will wake up and check their condition.
[ February 08, 2006: Message edited by: B Chen ]
[ February 08, 2006: Message edited by: B Chen ] [ February 08, 2006: Message edited by: B Chen ]
I edited my example to indicate rec-2 is already locked by another thread. I didn't include it in the sequence to avoid cluttering it.
The point is that there is only one monitor object, and all threads are waiting on it. But they are waiting for different conditions to be satisified (the logical record locks). Hence notifyAll() must be used to ensure all waiting threads check their condition.
If you want to do better than notifyAll(), you need another locking strategy. One possibility is "hand-over-hand" locking. In this scheme, a separate condition variable is associated with each record lock. Then signal() can be used to wake one thread that is interested in that particular record. Search for forum, or look at Andrew's book for more details.
[ February 08, 2006: Message edited by: B Chen ] [ February 08, 2006: Message edited by: B Chen ]
yes, i've got a lock associated with each record (see pseudocode for Data#lock in one of the replies above). Therefore, only threads waiting for a particular record's lock will be notified when it's unlocked.
What I am trying to say is that with notify() we might run in a situation where a waiting thread is never woken up.
I guess it's up to us to decide on whether to take such risk and comply with the SUN's "no CPU cycles should be consumed" requirement ; or to use notifyAll and be sure that all threads listed on the record's waiting list get woken up. However, the latter option seems to contradict SUN's requirement.
I've tried to sketch it in one of the above replies ( "Imagine, if you've got threads coming ...." ).
The arbitary behaviour mentioned in the API for notify method indicates that not much is guaranteed with this method apart that one thread will be woken up.
I think you are worried about lock starvation in that if a thread is waiting on a lock, the thread scheduler will never give it the lock, correct?
If thats what you're concerned about, then you are indeed at the mercy of the thread scheduler and notify() or notifyAll() will not make a difference. "Starvation" is not an absolute term, the thread scheduler will eventually give control back to the waiting thread, its just a question of how long.
Just because notifyAll() wakes up a thread, it does not give it a better shot at obtaining the lock, it merely gives it the chance to do something else instead of waiting.
As I mentioned before, if you really do not want to be at the mercy of the thread scheduler (which is not a big deal), you need do implement some kind of Priority Queue for your locks.
I am more concerned that with notify() a Thread Scheduler might never notify a thread.
At the same time I agree with you that SUN requires us not to consume CPU cycles, which implies that we should use notify(). In real time situation I'd use notifyAll().
Kind regards.
Post by:autobot
You firghten me terribly. I would like to go home now. Here, take this tiny ad:
a bit of art, as a gift, the permaculture playing cards
![[Logo]](/templates/default/mobile/images/mobile-moose.gif)
