design question: should the lock manager be synchronized whenever it's used in Data?

[Stewart Grossman]

such as in update(), delete()? i'm trying to figure out if that's necessary. in theory it shouldn't be because those methods shouldn't be called unless the record in question is already locked by the caller, and should be unlocked by the caller when it returns. any opinions?
[ August 10, 2003: Message edited by: Stewart Grossman ]

[Andrew Monkhouse]

Hi Stewart
It sounds like you have answered your own question
Basically it all depends on your usage. It sounds like you are only doing a read only check within the LockManager from within the update and delete methods, so you shouldnt need to synchronize for that.
Regards, Andrew

[Jim Yingst]

i'm trying to figure out if that's necessary. in theory it shouldn't be because those methods shouldn't be called unless the record in question is already locked by the caller, and should be unlocked by the caller when it returns.
Do your instructions require the use of "cookies" when locking? Does your LockManager store cookie info in a HashMap? Are you required to retrieve this info to check the cookie value in order to update() or delete()? Can multiple threads access this HashMap? What happens if one thread reads an old cookie value, rather than the latest value suppied by another thread, because no synchronization was performed while reading? What happens if another thread manages to execute resize() (see source for HashMap) while you're trying to get() an "unchanging" value?
There's a widespread myth that synchronization is only necessary one reads, not writes, and it's usually wrong. If you're accessing mutable data (like a HashMap) from multiple threads, you should synchronize.

[Andrew Monkhouse]

Hi Jim

What happens if one thread reads an old cookie value, rather than the latest value suppied by another thread, because no synchronization was performed while reading?

Does it matter?
In this case, the check should be whether the cookie value in the map is the same as the cookie value being provided for the update / delete. Regardless of whether I get the old or the new value, it will not match the value passed as a parameter in the update / delete.
Now if you had to use the value you read, then you might have to synchronize on the map to ensure that the value that you are using does not change. But in this case, I cannot see any value.

What happens if another thread manages to execute resize() (see source for HashMap) while you're trying to get() an "unchanging" value?

OK - now that argument I will accept. The actual method within the lock manager that retrieves the value for a given key will need to be synchronized. This does not necessarily mean that the whole lock manager will need to be synchronized, nor the use of the lock manager in verifying the record number in update or delete.
You didnt need to go all the way to the code for that comment though - it should come directly from the API:

If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

Regards, Andrew

[Jim Yingst]

[Jim]: What happens if one thread reads an old cookie value, rather than the latest value suppied by another thread, because no synchronization was performed while reading?
[Andrew]: Does it matter?
Sure. Assuming that the assignment requires the use of cookies, and that for an update() or delete() we're supposed to throw a SecurityException if the supplied cookie is not the correct one. That requires that we be able to look up the cookie value currently associated with the record, for validation. Which seems to be what you go on to say, but...
[Andrew]: In this case, the check should be whether the cookie value in the map is the same as the cookie value being provided for the update / delete. Regardless of whether I get the old or the new value, it will not match the value passed as a parameter in the update / delete.
Eh? If we get the most recent value, it should indeed match the value supplied in the update/delete. (Well, assuming that the update() delete was called with the correct (most recent) value of course. That's how we know that we should allow the update/delete rather than throw a SecurityException, right? On the other hand if we get an old cookie value from the map (or a null, indicating this old copy of the map thinks that the record is currently unlocked) then we'll end up throwing a SecurityException even though we're really using the correct cookie value.
[Andrew]: This does not necessarily mean that the whole lock manager will need to be synchronized,
Just the parts that access shared mutable data, as is standard in Java multithreaded applications.
[Andrew]: nor the use of the lock manager in verifying the record number in update or delete.
Ummmm... I'm not sure what this means. When we verify a reord number for update or delete, we do have to look up the cookie in the HashMap, don't we? Are you saying that lookup need not be synchronized?
[Andrew]: You didnt need to go all the way to the code for that comment though - it should come directly from the API:
There's that, too. But somehow this myth has arisen that it's OK to omit synchronization for reads, despite the documentation, and despite clear warnings in the Book of Joshua. So I thought it might be helpful to get people to look at what can happen in the actual code. Though even without something as dynamic as a resize() the previously-discussed memory latency issue is enough to make synchronization a requirement, IMO.

[Andrew Monkhouse]

Hi Jim
I seem to be missing something in your comments. When I get a cookie back from locking a particular record; from (just prior to me receiving the cookie) onwards my cookie should be associated with that record number. I can never get the previous cookie value - once I receive my cookie, then that is the cookie that is associated. I can never get a newer cookie, because noone can lock that record until I release my lock.
The only time the cookie value might change while I am trying to look at it is if I do not own the lock. In that case, I (client A) might read the cookie owned by another client (client B) then by the time I go to use it the cookie may have changed to that owned by a third client (client C). And in this case, I really don't care, since my cookie will not match either client B's or client C's cookies. Either result will cause the comparison to fail, and the exception to be thrown.
So putting a synchronized block around the call to the lockmanager method verifying the cookie should be redundant.

[Andrew]: nor the use of the lock manager in verifying the record number in update or delete.
[Jim]: Ummmm... I'm not sure what this means. When we verify a reord number for update or delete, we do have to look up the cookie in the HashMap, don't we? Are you saying that lookup need not be synchronized?

Correct - we do not need the synchronize the lookup. We do not need to do:

    synchronized (lockManager) {
        lockOwner = lockManager.lookup( recordNumber );
    }

The lockManager.lookup method should be internally synchronized on the collection to ensure that the collection is not changed in the middle of the lookup (but I don't think that was Stewart's question).
I dont think there is any need need to do an external synchronization around that lookup (which I think was Stewart's question).
Regards, Andrew
[ August 11, 2003: Message edited by: Andrew Monkhouse ]

[Jim Yingst]

The following was written before I'd read the last part of Andrew's last comment more carefully. So this may be irrelevant to the actual point of Andrew's comments, or not - but since I already typed it up I'll go ahead and post it, then come back to what I now think is actually the source of our confusion.
Consider this scenario:

Client A locks record 1, gets cookie 123456789.

Client A updates record 1 using 123456789.

Client A unlocks record 1 using 123456789.

Client B locks record 1, gets cookie 987654321.

Client B updates record 1 using 987654321.

Client B unlocks record 1 using 987654321.

Seems reasonably straightforward, no? But - let's say the server is using RMI. RMI makes no guarantees about which thread will serve which requests. A common scenario is that there's a thread pool on the server, and every time an RMI call comes in, it's handled by whatever thread's available. So the RMI spec specifically tells us that "a remote object implementation needs to make sure its implementation is thread-safe." Which generally means you're supposed to synchronize. Despite the claims of certain synchronization-phobic persons who are currently unavailable for comment.
Let's say that the server thread pool has a total of two threads in it at the moment, T1 and T2. (Very high-volume server we have going here.) And let's say that it so happens that steps 1-2 are both served by the same thread, T1. Then let's say that steps 3 and 4 are served by T2, and steps 5 and 6 are served by T1 again. The problem is that when we get to step 5, T1 may access its cached copy of the HashMap data, and think that the cookie that goes with record 1 is 123456789, since that's the last value it knew about, and we haven't forced T1 to refresh its memory (as it would have if we'd synchronized). So even though client B has provided the proper cookie value, 987654321, T1 is looking up the old value, 123456789, and so it will throw a SecurityException even though client B did lock the record and use the proper cookie.
If the server doesn't use RMI, then you have more control over threading issues, and you may be able to explicitly avoid this scenario. But thread pooling is not an uncommon thing on servers; I wouldn't be surprised if someone eventually tried to put in a thread pool later, even if you don't have one initially.
[ August 11, 2003: Message edited by: Jim Yingst ]

[Jim Yingst]

OK, now this is the part that I think is actually where our disagreement comes from:
[Andrew]: The lockManager.lookup method should be internally synchronized on the collection to ensure that the collection is not changed in the middle of the lookup (but I don't think that was Stewart's question).
I dont think there is any need need to do an external synchronization around that lookup (which I think was Stewart's question).
I was assuming Stewart was questioning the need for any synchronization, internal or external; you were evidently assuming that internal synchronization was a given, and so external sync is not necessary. I agree with your assessment, if that is indeed what Stewart meant. Moreover I favor writing classes and methods so that, whenever possible, synchronization is invisible to the people who use a method. If it's possible to solve a problem by synchronizing within a method rather than farcoing others to synchronize externally, that's what I advocate. So in this case, sure, synch the lockManager internally; no more should be needed. There are unfortunately many cases where you really need sync at a higher level in order to prevent another thread from slicing in between method invocations - in these cases, well, put the sync at a higher level, as necessary. And then try again to wrap the whole process in a facade of some sort that agin makes the sync invisible to outside users. If possible.
So, does this mean we're both an the same page again?

[S Bala]

Hi Jim and Andrew,
I feel that syncronizing on the lock and unlock methods is good enough.
I am using a lock store than a lock manager. The access to lock store is via a syncronized method. So no need to worry about it. One has to be very careful with synchronizing LockManager, especially if it is earlybird assignment with the lockCookie . Using nested locks in certain scenarios
can lead to dead locks. My interface needs me to check on the locks in other methods too.
If we use random access file, then I believe it will be manadatory to Syncronize the read method. As the record pointer would change locations.

- Shankar

[Andrew Monkhouse]

Hi Jim,
Yes, I think we are both in agreement now.
Regards, Andrew

[Andrew Monkhouse]

Hi Shankar
I am unsure what you are leaving unsynchronized.
Are you talking about methods in the LockManager - so if for example, you have methods, lock(recordNumber), unlock(recordNumber, cookie), and isLockedBy(recordNumber, cookie), are you suggesting that only the lock and unlock methods are synchronized, and the isLockedBy() method is unsynchronized (even internally)?
Or are you talking about methods in Data, so methods such as update() are unsynchronized?
Or have I missed your suggestion totally?
Regards, Andrew

[S Bala]

Hi Andrew,
I am using something similar to a LockManager. But, I have all my IO methods in my Data class as well as the lock and unlock methods synchronized. So, I have left the methods of the LockManager unsynchronized. I create only one static instance of LockManager in the Data class. If all the access methods (Data Class) to a shared resource (LockManager) are synchronized then we need not synchronize the methods inside the LockManager.
thanks.
-SB

[Andrew Monkhouse]

Hi Shankar

If all the access methods (Data Class) to a shared resource (LockManager) are synchronized then we need not synchronize the methods inside the LockManager.

(my highlighting)
Yes, that sounds reasonable. The only issue is if that pesky junior programmer removes a synchronized statement because they feel that it is not needed. So to stop that you might have to put comments in various places to ensure that people realise that they must not remove the synchronized statements
Regards, Andrew

[S Bala]

Hi Andrew,
I chose to just syncronize the methods of the Data class and leave the LockManager unSynchronized because of possibilities of deadlock (Especially in UrlyBird with lockCookie).
Problems if we Synchronize LockManager in URLYBird 1.1.3 (with lockCookie) ...
Our data access class has methods which need to access the LockManager
as shown below (Nested Lock situation).
- Client thread A doing an Update on Record 10.

public void update(int recNo, String[] data, long lockCookie)

- Client Thread B Doing a delete on Record 10.
The client has to get a lock first.
- Client Z has a Lock for the Record 10.
"Any client thread after attaining a lock, need to read the record to see
if it is a valid record". - if we implement the above statement the problem arises, because the client A is already in a Synchronized method of the DataClass (A DEADLOCK situation).
- SB

[Andrew Monkhouse]

Hi Shankar
As I said, leaving the synchronization at the Data level is OK.
I am not sure where you think deadlock will occur in the scenario you gave. For that scenario:

Client A doing booking: calls synchronized Data.lock() which calls synchronized LockManager.lock() (then on with other tasks)

Client B doing deletion: calls synchronized Data.lock() which calls synchronized LockMananager.lock then enters wait state because lock is in use: other threads can now call methods in Data and in LockManager

Client C doing anything: calls synchronized Data.lock() which calls synchronized LockManager.lock() also enters wait state: other threads can now call methods in Data and LockManager

Client A does modification

Client A calls synchronized Data.unlock() which calls synchronized LockManager.unlock() which unlocks the record and calls notifyAll() to wake up one of the the two sleeping classes.

Where do you see the deadlock ocurring?
Regards, Andrew
[ August 14, 2003: Message edited by: Andrew Monkhouse ]

[Stewart Grossman]

Thanks for the replies. My lock manager is just a plain old HashMap. I'm not creating a new class for it. Frankly, I just don't see the point. It's not necessary. It seems like everyone advocates creating this as a class. Why? I'm not really sure what the consensus answer to my question is. However, I did in fact synchronize all the instances in which I'm using lockMgr.

[Vlad Rabkin]

Hi Stewart,
not really: there are a lot of people who do not have LockManager (I am the one).
Max is also not a fan for LockManager.
So, it is just a design choise to be made.

Vlad

[Max Habibi]

That's true, I'm not. IMO, it's overkill for the scope of the assignment, thought it is fun to write.
M

[Eugene Sun]

Hi all,
I am working on FBN project.
My lock manager is a plain HashSet. It's not really a manager at all actually, it's simply a collection of record number of the records that are currently locked. Let's call it lockedRecords for this email's discussion.
I am not synchronizing the lock() and unlock() at method level. My thread-safe mechanism is done inside both methods where I synchronize the lockedRecords which is a static member field of Data class. I think it's a better idea than synchonizing the entire methods because I still want to give other users to be able to do reads like
getRecordCount()
getFieldInfo()
while I am locking the the records, whereas if synchronizing the methods, the entrie Data object will be blocked.
Any comments on my design decision ?

Thanks,
Eugene

[Andrew Monkhouse]

Hi Stewart
I am another person who did not have a LockManager in my solution.
Max doesnt like my alternative any better than the LockManager solution though
You will find that there are quite a few people in this forum who will happily discuss any idea, regardless of how they personally feel about it.
Regards, Andrew

[Andrew Monkhouse]

Hi Eugene
I also synchronized on my HashSet (yes set, not map) inside my lock and unlock methods rather than synchronizing the entire method.
So I agree with what you described.
Regards, Andrew

[Vlad Rabkin]

Hi Andrew,
by the way,
I have never asked you how did you handle your synchronization for read/write/delete/add methods.
I use separate ReadWriteLock synchronization mechanism to allow concurrent reads (read, find) and exclusive writes(update, add, create).
Have done something like this or you synhronized write/add/create methods also on HashSet and didn't synchronize read/find at all allowing dirty-reads like Max suggests?
Tx,
Vlad

[Andrew Monkhouse]

Hi Vlad,
Yes, I allowed dirty reads. My reading of the instructions (FBNS) implied that they were allowed, so I saved myself that worry.
Regards, Andrew

[Vlad Rabkin]

Hi Andrew,
thanx for your reply.
I argued a lot with Max a lot, but I still didn't understand his point. May be you can explain this:
I use cash the database in a HashMap. To find a record (int[] find(String[]) I have to iterate over the Map. Iterator has fail-fast behaviour, meaning if any write (delete, create, update) occurs at the same time an ConcurrentModificationException will be thrown. Max said it cannot happen because thread make their local copy of the Map. To my opinion they don't because HashMap is not a local variable - it is a member variable of the Data class.
I guess you didn't cash a database, so you didn't have zhe problem.
If you had such design as I do, what do you think about all of this?
Tx,
Vlad

[Andrew Monkhouse]

Hi Vlad,
I didnt have this issue, as I didnt cache my data.
Regards, Andrew

[Jim Yingst]

I use cash the database in a HashMap. To find a record (int[] find(String[]) I have to iterate over the Map. Iterator has fail-fast behaviour, meaning if any write (delete, create, update) occurs at the same time an ConcurrentModificationException will be thrown. Max said it cannot happen because thread make their local copy of the Map. To my opinion they don't because HashMap is not a local variable - it is a member variable of the Data class.
Mmmm, I'd be interested in seeing just what Max said. I'm thinking he might have been suggesting that if you make a copy of the Map, explicitly, then one the copying is done you can iterate through it as slowly as you like, without worrying about changes made to the original map. You'd need to synchronize during the copy process, but not afterwards. In this way you could guarantee that no ConcurrentModificationException would be thrown.
Alternately, if you don't explicitly make a copy of the Map - well, it may or may not happen anyway, thanks to the vagueness of the JVM's memory model. You may even get a sort of partial copying, depending on JIT optimizations - some data regarding the Map may be cached in a local variable, while other data in the same Map must still be looked up in the heap. As a simple example, a HashMap has an array inside - the length of that array could easily be cached locally, since it's going to be re-used many times and is not expected to change while iterating, while the data within the array may remain out on the heap, needing to be looked whenever it's referenced. All sorts of strange things might be going on if you're accessing mutable data from multiple threads, without synchronization. So you may or may not get a ConcurrentModificationException; there's no real guarantee either way. As the API for ConcurrentModificationException says: "Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification."

[Vlad Rabkin]

Hi Andrew,
Thanx, good reason to reconsider if I should cash the database...
Ho Jim,

Mmmm, I'd be interested in seeing just what Max said

Take a look at this page:
https://coderanch.com/t/183593/java-developer-SCJD/certification/NX-Client-crashed-cause-deadlock

[Max]: The way this generally works is this. Your thread, say Thread #1, makes a local copy of the map(for efficiency), and does it's work there(this is Thread Memory, vs. Main Memory).
[Vlad]: The problem is if your database contains many records it will KILL the server:
[Max]: Vlad,
I think you might enjoy reading a bit more about this.
http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html#28458

he might have been suggesting that if you make a copy of the Map

I you have meny record in the database and concurrent requests it will be a memory problem.

You may even get a sort of partial copying

It would be Ok, but I think it is to much complexity.

"Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification."

Ok, but let's say 50% we will get this exception. I don't think it is Ok to allow a client get suddenly such exception.
Tx,
Vlad

[Vlad Rabkin]

Hi Jim,
This is my test:

import java.util.*;
public class ConcurrentDatabase {
  private Map cash = new HashMap();
  public ConcurrentDatabase() {
     this.updateRecord(new Integer(1), "1");
     this.updateRecord(new Integer(2), "2");
     this.updateRecord(new Integer(3), "3");
     this.updateRecord(new Integer(4), "4");
     this.updateRecord(new Integer(5), "5");
     this.updateRecord(new Integer(6), "6");
  }
  public Collection getRecords() {
   Iterator it = cash.keySet().iterator();
   Collection found = new ArrayList();
   while (it.hasNext()) {
    try {
     Thread.sleep(1000);
    } catch (InterruptedException ie) {}
     String record = (String) cash.get(it.next());
     System.out.print(record);
     found.add(record);
   }
   return found;

  }
  public void updateRecord(Integer recNo, String record) {
   synchronized (cash) {
    cash.put(recNo, record);
   }
  }
  public void deleteRecord(Integer recNo) {
   synchronized (cash) {
    cash.remove(recNo);
   }
  }
  public static void main(String[] args) {
   ConcurrentDatabase db = new ConcurrentDatabase();
   Thread find   = new Thread(new TesterRunnable(2, db));
   Thread update = new Thread(new TesterRunnable(1, db));
   Thread delete = new Thread(new TesterRunnable(0, db));
   Thread create = new Thread(new TesterRunnable(3, db));
   find.start();
   update.start();
   create.start();
//   delete.start();
  }
}
  class TesterRunnable implements Runnable {
   private int operation;
   private ConcurrentDatabase db;
   public TesterRunnable(int operation, ConcurrentDatabase conc){
     this.operation = operation;
     this.db = conc;
   }
    public void run() {
     switch (operation) {
      case 0: db.deleteRecord(new Integer(5)); break;
      case 1: db.updateRecord(new Integer(3), "Update"); break;
      case 2: db.getRecords(); break;
      case 3: db.updateRecord(new Integer(10), "Create"); break;
     }
    }
  }  

I have checked it:
A java.util.ConcurrentModificationException will be always thrown.
Vlad

[Jim Yingst]

[Jim]: he might have been suggesting that if you make a copy of the Map
[Vlad]: I you have meny record in the database and concurrent requests it will be a memory problem.
True.
Personally, I keep all records in memory, and I use an ArrayList (index is recNo) rather than a HashMap. To find(), I just loop through the ArrayList, synchonizing each individual access to the List; then after I've retrieved an individual record (and am no longer synced on the List) I sync on that record while I look at it. So there's no need for one long sync of the list; just lots of little ones. If multiple threads are doing this simultaneously, it's no problem. There may be a lot of lock contention if there are a lot of threads, but it's still much faster than reading from the file for every record each time find() is called. And memory may be an issue if the DB file is really big (remember that memory is cheap) - and it's a fixed cost; it doesn't increase with the number of clients, because there's no copying of the list.
Another alternative you may wish to consider - rather than iterating through your HashMap, try doing separate synchronized get()s for each record number. This way, other threads can do find()s at the same time. It's a bit slower than iterating (not sure how much), but it doesn't lock things up while the iteration takes place.
[Jim]: You may even get a sort of partial copying
[Vlad]: It would be Ok, but I think it is to much complexity.
Well, I'm not talking about something we would choose to do; I'm saying that the JVM may do it whether we want to or not.
[spec]: "Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification."
[Vlad]: Ok, but let's say 50% we will get this exception. I don't think it is Ok to allow a client get suddenly such exception.
Agreed. I'm not arguing we should allow it to happen, I was saying what would (or could) happen if we don't take some precaution, such as synchronizing, defensive copying, or something else.
[Vlad]: I have checked it:
A java.util.ConcurrentModificationException will be always thrown.
OK. I don't belive we can really guarantee that it will always be thrown, because of the way the specs are written, but it's usually thrown, sure.

[Vlad Rabkin]

Hi Jim,
Thanx for the reply. I agree with all your statements. That is why I've decided to use cash. Honestly saying we can do almost the with the HashMap, by cheeting on it: I loop over the keys in the Map without using iterator. I tested it today: istead of using Iterator I transfer all keys in a HashMap into the array of Integer and then I loop over this array. It works fine.
I gave a new interesting idea:

To find(), I just loop through the ArrayList, synchonizing each individual access to the List; then after I've retrieved an individual record (and am no longer synced on the List) I sync on that record while I look at it. So there's no need for one long sync of the list; just lots of little ones. If multiple threads are doing this simultaneously, it's no problem.

I assume you hold there only active records (no deleted records). Right?
Why do you synchronize on the record after you have retreived it? To avoid dirty-reads?
As I said to Max in the old discussion I have Read-WriteLock mechanism, which is a small simple class, having 4 ints: activeReaders, waitingReaders, activeWriters, waitingWriters. It allows concurrent reads and exclusive writes. Advantage better performace then just synchronizing reads and writes, disadvatage: nested locks (one lock on the hashmap for lock/unlock method + read/write locks for retrieving the records).
Max gave the idea of dirty-reads by allowing totally un-synchronized reads (read/find). Andrew have made the same thing and have not lost a point for locking! I wonder about this fact, because it is possible that a user see a garbage on the screen (e.g. instead of Sheraton or Holydays Inn: Shedays ). Of course while trying to book a record it can be checked. Still it seems a great idea to boost performance, but a weard solution for real application.
Some people have made read-write locks sync mechaism and other types of synchronization, but all of them have lost scores.
Have been penaltied for your synchronization mechanism?
It looks like you have also many locks:
1) one lock for lock/unlock
2) one lock for get element from the list and add/update element in the list
3) to analyze element from the list (to check if it matches a search criteria)
Could you comment your design decision a bit more in detail (excpecially why not read-write lock or non-synchronized read by allowing dirty read)?

Tx,
Vlad

[Jim Yingst]

[Vlad]: Thanx for the reply. I agree with all your statements. That is why I've decided to use cash. Honestly saying we can do almost the with the HashMap, by cheeting on it: I loop over the keys in the Map without using iterator. I tested it today: istead of using Iterator I transfer all keys in a HashMap into the array of Integer and then I loop over this array. It works fine.
Cool, glad to hear it.
[Jim]: To find(), I just loop through the ArrayList, synchonizing each individual access to the List; then after I've retrieved an individual record (and am no longer synced on the List) I sync on that record while I look at it. So there's no need for one long sync of the list; just lots of little ones. If multiple threads are doing this simultaneously, it's no problem.
[Vlad]: I assume you hold there only active records (no deleted records). Right?
Actually I do have deleted records too; my Record has an isDeleted flag whihc is checked before anything else is done with the record. (For a deleted record, other fields are set to null, freeing most of the other memory that would have been associated with the Record.) This is so that the Record can be used as a monitor when create() is causing a deleted record to be reclaimed. When create() is called, a list of deleted records is consulted, one is picked out, and the Record object associated with that slot is retrieved from the arraylist. I sync on that Record while the rest of create() is taking place, and during that time no other sync locks are held, so other threads are able to access any other parts of the DB without hindrance. I certainly could have set this up diffenently, but it's pretty similar to what I did for update. Most of the sync I do is on those record objects rather than something higher-level, so sync lock contention is pretty minimal.
Why do you synchronize on the record after you have retreived it? To avoid dirty-reads?
Yup. It was easy to prevent, and has a negligible impact on performance in my code, which I've measured. (Again, because the sync is record-level rather than db-level, there's almost no lock contention unless multiple threads are competing for the same record.)
It's not just for reads though - I sync on the Record to do anything with a record, including read. This ensures that the data in the Record is freshly updated, not some cached garbage. So it's necessary for all the other methods too, especially those that deal with cookies - because I need to know that I'm looking at the correct data for an expected cookie value.
As I said to Max in the old discussion I have Read-WriteLock mechanism, which is a small simple class, having 4 ints: activeReaders, waitingReaders, activeWriters, waitingWriters. It allows concurrent reads and exclusive writes. Advantage better performace then just synchronizing reads and writes, disadvatage: nested locks (one lock on the hashmap for lock/unlock method + read/write locks for retrieving the records).
I don't have any nested locks, actually. I did for a little bit back when I added some extra sync on the FileChannel, but I decided this was unnecessary considering the Record sync already prevented concurrent access. Aside from that... I lock on the ArrayList to get the Record. But then I exit the sync block for the ArrayList before I sync on the Record. The wait-notify for the lock() method is done using the Record as monitor; there's no need for any other sync lock at the same time.
Max gave the idea of dirty-reads by allowing totally un-synchronized reads (read/find). Andrew have made the same thing and have not lost a point for locking! I wonder about this fact, because it is possible that a user see a garbage on the screen (e.g. instead of Sheraton or Holydays Inn: Shedays ). Of course while trying to book a record it can be checked. Still it seems a great idea to boost performance, but a weard solution for real application.
Yeah, garbage on the screen is a theoretical possibility that bothers me. However in practice it seems to be a very rare occurrance for most designs. Maybe even impossible, though the FileChannel specs fail to document this adequately. So I can understand why it's viewed as acceptable, and if my own design used more db-level sync, I would probably be more tempted to allow dirty reads myself, to reduce lock contention. Especially on find(). My main objections to dirty reads in the past have been when people didn't think they were possible at all. I think if you know they're possible, and make an informed decision that the risk is accpetable, that's fine. Though personally I haven't felt the need.
Have been penaltied for your synchronization mechanism?
I haven't submitted yet; I'm still playing with the GUI.
It looks like you have also many locks:
1) one lock for lock/unlock
2) one lock for get element from the list and add/update element in the list
3) to analyze element from the list (to check if it matches a search criteria)
Nope, it's
(1) one db-level sync lock to access an element from the ArrayList - this lock is dropped at the end of this step
(2) one record-level sync lock to do anything with a record - this is also dropped at the end of this step.
Basically, sync locks are never nested, and rarely last very long. At most, a Record-level lock lasts long enough to do a write to a file - usually, not even that. And most db-level locks are just long enough to get() a Record from an ArrayList(). I think the longest is for an add(). Still pretty short. In fact I think if I just replaced the ArrayList with a Vector my db-level locking would function the same way. The sync inside Vector doesn't create nested locks; neither does mine.
Note also that Record sync lock != record lock. The former is refers to synchronized code; the latter refers to a state which is controlled by lock() and unlock(). A record lock may (theoretically) be held for a long time, and it requires a Record sync lock to lock() and a Record sync lock to unlock(). (And possibly several more in between for whatever you wanted to do with the locked record.) But each of those Record sync locks is a relatively brief thing; a Record sync lock is not held for the whole time a record is locked.
Could you comment your design decision a bit more in detail (excpecially why not read-write lock or non-synchronized read by allowing dirty read)?
Never saw a need to allow dirty reads. Avoiding them was easy. With everything in memory, find() is extremely fast, lock contention is negligible, and the RMI networking is far slower than anything else in the system, so there was really no reason not to sync the reads as well. The general pattern throughout my code is, if you want to do anything at all with a Record, you sync on that Record (in fact I've been meaning to refactor so the sync is all within the Record class). So it's easier (in terms of consistency) to sync for reads just like any other method, rather than try to explain why they need a special exception to allow dirty reads, when they really don't.

[Vlad Rabkin]

Hi Jim,
It was very clear explanation.
Thank you very much!
Vlad

[Andrew Monkhouse]

Hi Vlad,

Andrew have [allowed dirty reads] and have not lost a point for locking!

I am wondering whether:

I said something that was misconstrued

I said something that I didn't really think through 100%

You are confusing me with someone else

The last is possible - since I did FBNS, I did not get a separate score for locking, it was incorporated into my server score. And I did loose 4 marks for my server (but in what aspect of the server I cannot tell).
Anyway, I did not incorporate read-locks into my design. But at the same time, the situation you were describing where a read could occur half way through a write causing garbled data could not occur in FBNS, since the provided methods getRecord() and modify() were both synchronized.
Regards, Andrew

[Max Habibi]

And since synchronization is not a signature change, I think the path is clear....
M

[Vlad Rabkin]

Hi Andrew,

It seems that I have said something, what irritated you. I apologise for that.
I think I misunderstood you:

[Vlad] Have done something like this or you synhronized write/add/create methods also on HashSet and didn't synchronize read/find at all allowing dirty-reads like Max suggests?

[Andrew]Yes, I allowed dirty reads

That is why I concluded that you allow dirty reads and do not synchronize reads.

[Andrew] Anyway, I did not incorporate read-locks into my design. But at the same time, the situation you were describing where a read could occur half way through a write causing garbled data could not occur in FBNS, since the provided methods getRecord() and modify() were both synchronized.

It sounds to me a bit contradictory:
I don't synchronize reads, but you synchronize getRecord(), which is the same...

Vlad
P.S. Andrew, I am sorry again if have said something incorrect.

[Andrew Monkhouse]

Hi Vlad,

It seems that I have said something, what irritated you.

No way. That post was about midnight last night, but I did not want to leave you with thinking the wrong thing. And it seems all I have done is add more confusion. But no one here has irritated me yet.
Now i understand why you thought i allowed dirty reads - because I said so :roll:
Anyway, what I was trying to get at was that I did not do anything like a read lock. And the write lock did not prevent reads. So when a client asks for a certain record, then I gave them the current values, even if I knew that the data was about to change.
I was trying to differentiate between read locks, and synchronizing methods in the class (which prevents garbled data - what you are calling dirty reads). My definition of dirty reads is slightly different - my meaning is returning any dated data (or data which is known to be about to change) constitutes a dirty read. This was the definition I got from working with databases, where reading data prior to commit / rollback could result in a "dirty read" but not in reading garbled data.
Perhaps I need to update my definition for talking in this forum.
Sorry for any confusion / consternation - it was not intended.
Regards, Andrew

[Vlad Rabkin]

Hi Andrew,
That is what thougth yesterday evening: Synchronizing on read does not mean having a read lock.

I was trying to differentiate between read locks, and synchronizing methods in the class (which prevents garbled data - what you are calling dirty reads). My definition of dirty reads is slightly different - my meaning is returning any dated data (or data which is known to be about to change) constitutes a dirty read. This was the definition I got from working with databases, where reading data prior to commit / rollback could result in a "dirty read" but not in reading garbled data.

I thought also "is returning any dated data (or data which is known to be about to change) constitutes a dirty read" and I am still pretty sure that is a correct definition. It has actually nothing to do with "reading garbled data".
It is just as I asked Max about the problem with "garbled data" if I didn't synchronize on read he has answered me: It Ok, since I anyway have to decide how to handle dirty reads... That is how I changed my vision of "dirty locks". Whatever, I don't want now to irritate Max, by incorrect interpretation of his statements
Anyway, your idea is clear. Thank you very much and sorry again for all these misunderstandings.
Regards,
Vlad
[ August 20, 2003: Message edited by: Vlad Rabkin ]
[ August 20, 2003: Message edited by: Vlad Rabkin ]