Logical/File Locking and nested synchronisation

[Alex Sharkoff]

Hi all,

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:

Data#read(int recNo)

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synchronization in [I]recValidFlags[/I]


GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

  VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synch in [I]recValidFlags[/I] - [B]nested synchronisation[/B]

  READ Record from [I]dbFile[/I]

RELEASE [I]dbFile[/I] Monitor // end of synchronizing block

Data#create(String[] record)

VALIDATE record


GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

  VERIFY Record IS NOT Duplicate (read record by record and compare with given record)

  USE [I]recValidFlags[/I] to DETERMINE Record position  // internal synch in [I]recValidFlags[/I] - [B]nested synchronisation[/B]

  WRITE Record into [I]dbFile[/I]

  GET Monitor on [I]recValidFlags[/I] // synch on [I]recValidFlags[/I] - [B]nested synchronisation[/B]

    MODIFY [I]recValidFlags[/I] with new Record validity flag // ([I]recValidFlags#remove[/I] and then [I]recValidFlags#add[/I])

  RELEASE [I]recValidFlags[/I] Monitor // end of synch block on [I]recValidFlags[/I]

RELEASE [I]dbFile[/I] Monitor // end of synch block [I]dbFile[/I]

Data#lock(int recNo)

VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synchronization in [I]recValidFlags[/I]


GET Monitor on [I]lockedRecords[/I] // synchronizing on [I]lockedRecords[/I]

  WHILE Record IS in [I]lockedRecords[/I] -> WAIT

  VERIFY Record EXISTS in [I]recValidFlags[/I] // internal synch in [I]recValidFlags[/I] - [B]nested synchronisation[/B]

  PUT Record into [I]lockedRecords[/I]

RELEASE [I]lockedRecords[/I] Monitor // end of synchronizing block

Data#delete(int recNo)

VERIFY Record IS Locked in [I]lockedRecords[/I]  by the client who has called [I]delete[/I]

// no need to perform any further record validation as the record is locked 
// by the client who's called the delete and therefore this record cannot 
// be modified by anyone else until this client unlocks the record 
// (the client will probably do it after the delete operation)

GET Monitor on [I]dbFile[/I] // synchronizing on [I]dbFile[/I]

  UPDATE Record with deleted flag in [I]dbFile[/I]

  GET Monitor on [I]recValidFlags[/I] // synch on [I]recValidFlags[/I] - [B]nested synchronisation[/B]

    MODIFY [I]recValidFlags[/I] with the Record's deleted flag // ([I]recValidFlags#remove[/I] and then [I]recValidFlags#add[/I])

  RELEASE [I]recValidFlags[/I] Monitor // end of synch block on [I]recValidFlags[/I]

RELEASE [I]dbFile[/I] Monitor // end of synch block [I]dbFile[/I]

All comments are welcome.


[ December 20, 2005: Message edited by: Alex Sharkoff ]

[Alex Sharkoff]

Hi all,


Seems like nobody wants to comment on it. Must be that good

[Henrik Strand]

Hi Alex!

A couple of questions:

- Are you finished with the SCJD cert? If so, what was your locking score (if I may ask )?

- Did you use the synch mechanism that you described in that post? Or did you do some last modifications?

- 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? Is that ok, or am I missing something?

Regards,
Henrik Strand

[Alex Sharkoff]

Hi Henrik,

sorry i could not reply earlier

Are you finished with the SCJD cert?

I wish still going bit by bit

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)

 
GET  [I]dbFile[/I] Monitor
  VERIFY that recNo EXISTS in [I]recValidFlags[i]
RELEASE[i]dbFile[/I] Monitor 


GET [I]lockedRecords[/I] Monitor
  EXTRACT Record#recNo object from [I]lockedRecords[/I] (or create Record#recNo if it does not exist and place into [I]lockedRecords[/I])
RELEASE [I]lockedRecords[/I] Monitor

  
GET [I]Record#recNo[/I] Monitor
 
  WHILE Record#recNo IS Locked -> RELEASE [I]Record#recNo[/I] Monitor and WAIT 

  GET  [I]dbFile[/I] Monitor    - [B]nested synchronisation[/B] 
    VERIFY that recNo EXISTS in [I]recValidFlags[i] 
  RELEASE[i]dbFile[/I] Monitor   

  LOCK  Record#recNo

RELEASE [I]Record#recNo[/I] Monitor // end of synchronizing block
 

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?


Kind regards,

[B Chen]

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 ]

[Kevin Conaway]

Alex,

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.

Kevin

[Alex Sharkoff]

B Chen wrote:

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.


Kind regards.

[Kevin Conaway]

Originally posted by Alex Sharkoff:


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.

Kevin

[Alex Sharkoff]

Kevin wrote:

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 ]

[Kevin Conaway]

Alex,

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.

Kevin

[Alex Sharkoff]

Kevin,

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 ]

[Kevin Conaway]

Originally posted by Alex Sharkoff:
Kevin,



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.

Kevin

[B Chen]

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

rec-2 locked by another thread already...
 
          Thread-A         Thread-B            Thread-C
          --------------   ------------------  ---------------------
          lock rec-1
                           waiting for rec-1   waiting for rec-2
          unlock rec-1
          notify
                                               checks, rec-2 still locked
                                               waiting for rec-2

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 ]

[Kevin Conaway]

B Chen,

In your example, Thread C would not have to wait for "rec-2" because no other Thread has locked it.

Threads A and B are waiting on a different object than Thread C

Kevin
[ February 08, 2006: Message edited by: Kevin Conaway ]

[B Chen]

Kevin,

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 ]

[Kevin Conaway]

Alex / B Chen,

I assumed he was using "hand over hand" locking where there is a lock associated with each record.

Sorry for the confusion.

Kevin

[Alex Sharkoff]

Hi B Chen and Kevin,

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.


Kind regards.

[Kevin Conaway]

Alex,

Can you sketch out such a situation please?

Thanks,

Kevin

[Alex Sharkoff]

Kevin,

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.


Kind regards.

[Kevin Conaway]

Alex,

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.

Kevin

[Alex Sharkoff]

Hi Kevin,

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.