Locks review....please

[Rajesh So]

Hi,
I just posted a topic and it disappeared !!! . I have written a lock implementation, which did not give errors so far (may be my test program did not find one!!). I request you to spot errors, if any and tell if marks will not be reduced for LOCKS.
I have implemented not checking for clientID for now.
The unlock code would just notifyAll after unlocking.

/*
 * Locks all available records and keeps a list of 'cannot be locked' records and waits.
 * When notified, Locks all available records and keeps a list of 'cannot be locked' records and waits.
 * Cycle repeats till all the given records are locked.
 */
    public synchronized void lock(int record,int clientID) throws IOException {
    int tempRecordCount = getRecordCount();
    int tobeLocked[];
    if (record == -1) {
    tobeLocked = new int[tempRecordCount];
    for(int i=0;i<tempRecordCount;i++) {
    tobeLocked[i] = i;
    }
    } else {
    tobeLocked = new int[1];
    tobeLocked[0] = record;
    }
   while (tobeLocked.length>0) {
   for(int i = 0;i<tobeLocked.length :wink:  {
   if (!locker.containsRecord(tobeLocked[i])) {
   locker.lock(tobeLocked[i],clientID);
System.out.println("Locked " + tobeLocked[i] + " by "
   + Thread.currentThread().getName());
tobeLocked = removeFromArray(tobeLocked,i);
   } else {
   i++;
   }
   }
   if (tobeLocked.length > 0) {
    try {
      System.out.println("Waiting for the release of locks of "
       + printArray(tobeLocked) + " records " 
                         + " by "
                         + Thread.currentThread().getName());
      wait();
    }catch(InterruptedException ie) {
    System.out.println(ie);
    }
    }
   }
   }

Thanks in advance for your review.
Rajesh

[Peter den Haan]

public synchronized void lock(int record,int clientID) throws IOException {

Does this method live in Data? Why did you modify the lock() method signature?

   int tempRecordCount = getRecordCount();

Eliminate this temporary variable -- yes, I know those extra calls to getRecordCount() take a few dozen extra CPU cycles. It also makes your code that little bit harder to understand. Fowler strongly argues against it, and I agree with him (this is typical English understatement for worshipping at his feet).
If you can buy, beg or borrow Fowler's Refactoring, do so. If you can't, consider stealing.

  int tobeLocked[];
   [...]
   tobeLocked = removeFromArray(tobeLocked,i);

Why use an array? You end up with gross inefficiencies (both in execution time and development complexity) like this one... a Set or LinkedList would've done the same job a lot more cleanly. But as a matter of fact it can be argued that you don't want to do this job in the first place. See below.

      for(int i = 0;i<tobeLocked.length   {
         if (!locker.containsRecord(tobeLocked[i])) {
            locker.lock(tobeLocked[i],clientID);

The purpose of your code, apparently is to implement a database lock implementation on top of a record lock implementation ("locker") by progressively locking all records.
I think this is a mistake, although you can perhaps argue that the issues below are all outside the scope of this assignment.

It does not implement the semantics of a "database lock". In particular, with your "database lock" in place a client can successfully acquire record locks on any records that have been added after the lock(-1) started executing.

It is incredibly deadlock-prone. Any client which acquires more than one record lock at a time in any order other than ascending by record number can deadlock if a database lock is in progress.

Your memory consumption is proportional to the number of records in the database, which is rarely a good idea with databases.

Many implement the database lock as a boolean value in their lock manager, or a magic value (often -1) in their lock Map, which is checked whenever a client attempts to acquire a lock. The easiest way to implement it without running into deadlock issues is to wait until there are no more outstanding locks, then impose the database lock.

            }catch(InterruptedException ie) {
               System.out.println(ie);
            }

Decide how you're going to handle interrupts. The possibilities are (broadly):

You don't support interrupts and any attempt to interrupt database server threads is a fault condition. Rethrow InterruptedException wrapped inside a RuntimeException (e.g. a DatabaseInterruptedException extends RuntimeException).

You do passively support interrupts by ignoring them Get rid of the print statement and leave as-is otherwise.

You support interrupts as a way to abort database operations currently underway, for instance to facilitate database shutdown. Rethrow the InterruptedException wrapped inside a DatabaseException or somesuch (e.g. a DatabaseInterruptedException extends DatabaseException).

You completely leave interrupt handling to the calling code. In that case you'd simply allow the interrupt to propagate outside the method.

Don't forget to document your decision.
- Peter
[ January 27, 2003: Message edited by: Peter den Haan ]

[Rajesh So]

Peter, Thank you so much for your time. Please help me understand the following.

Does this method live in Data? Why did you modify the lock() method signature?

It is part of the Data class. I did not get any other idea to identify the person who locks the record. I was told by members of this forum that it is not a bad idea for this way of identifying and changing the method signature.

Eliminate this temporary variable

Yes , done.

Fowler's Refactoring

I came to know of this subject through you and it is interesting. I shall get this book after exam. I have to finish the exam first!!!

Why use an array?

I presumed that using primitive values are easier for the JVM than Integer objects in a List or Set.Easier in terms of execution time. Am I wrong? Shall I use List any way?

The purpose of your code, apparently is to implement a database lock implementation on top of a record lock implementation ("locker") by progressively locking all records.
I think this is a mistake,

Is'nt my code performing this purpose effectively? Please tell me Peter, where I made the mistake.

# your "database lock" in place a client can successfully acquire record locks on any records that have been added after the lock(-1) started executing.

This is true. Shall I keep track of the new records been added, by calling the getRecordCount() every time I do locking? This would cost a few CPU cyles. Is it okay?

# It is incredibly deadlock-prone. Any client which acquires more than one record lock at a time in any order other than ascending by record number can deadlock if a database lock is in progress.

This deadlock would cause tragedies in my marks .I am not able to see any deadlock, becuase one client can lock any number of records, either 1 or complete lock. If it has locked complete, all others have to wait. Please help me understand where I made the possibility of deadlock error.

# Your memory consumption is proportional to the number of records in the database, which is rarely a good idea with databases.

Are you telling this because I am using an array to store all the record numbers? Before proceeding to lock, don't we need to know what records we are locking? Hence I have used arrays. Another advantage of my code is that it can be modified very easily for locking specified number of records. For example a client can lock 4 to 15 records. These are advantages of using arrays. I am not able to see any better ways.

The easiest way to implement it without running into deadlock issues is to wait until there are no more outstanding locks, then impose the database lock.

But Peter, isn't this a hard possibility to wait for everyone to stop locking for a database lock to proceed. This situation may not be in a working situation, because there will be a number of people locking/unlocking records. Our 'Full Databse lock' thread is also one among the competing thread, with equal priority. Is my thinking correct ?

* You don't support interrupts and any attempt to interrupt database server threads is a fault condition. Rethrow InterruptedException wrapped inside a RuntimeException (e.g. a DatabaseInterruptedException extends RuntimeException).

I shall do this as you suggested.

[Peter den Haan]

Originally posted by Rajesh Rajesh:
It is part of the Data class. I did not get any other idea to identify the person who locks the record. I was told by members of this forum that it is not a bad idea for this way of identifying and changing the method signature.

That's one way to solve it, but it's less than ideal. In the past, I've seen plenty who did this and passed. On the other hand, Max mentioned a week or so ago that Sun intends to become stricter. Bottom line is, I'm not sure either way.
There's another line of thought which thinks that (a) locking does not want to go into Data itself, as it is irrelevant in local mode and (b) the best way to identify clients without changing the method signature is to give all of them their own server-side Connection (implements DataInterface) to talk to.

I presumed that using primitive values are easier for the JVM than Integer objects in a List or Set. Easier in terms of execution time.

In principle, yes; but unless I'm mistaken, in your removeFromArray method you are forced to create a new array and copy the old values into the new array. That negates any performance advantage you might've had.
Are you familiar with big-O notation? Your database lock has O(N*N) performance, whereas using a linked list or a set would've given you O(N) performance. In simple terms, when the number of entries in the database grows the current method will quickly start to perform much worse.
But quite apart from that, the instructions tell you to favour simplicity over performance.

Shall I keep track of the new records been added, by calling the getRecordCount() every time I do locking?

That's not enough. Say that you did this, acquired record locks on every single record, and this call returned. It would still be possible to add a record and then acquire a lock on it, despite the fact that a database lock is in place.
That's quite simply not how a database lock is supposed to work IMHO. Having a database lock is not the same as having a record lock on every record in the table.

This deadlock would cause tragedies in my marks.

Don't get me wrong. With the FBN client, there is no danger of deadlock, because no client gets more than one lock at a time. But Data is not an FBN database. A five-minute inspection of the code should convince you that Data is a fully generic, reusable database. You have to code for reuse. Unless the instructions have changed, this is stated in the instructions as well.
As a consequence you cannot simply make assumptions because they happen to hold for the FBN client. You can, of course, decide that the Data database will only support a single lock per client, and document that design decision. That's a perfectly valid decision, even if it's not the one I would make.

Are you telling [that memory usage is proportional to #records] because I am using an array to store all the record numbers?

Yes.

Before proceeding to lock, don't we need to know what records we are locking? Hence I have used arrays. Another advantage of my code is that it can be modified very easily for locking specified number of records. For example a client can lock 4 to 15 records. These are advantages of using arrays.

Before proceeding to lock a record, don't you need to know the bytes you are locking? Well, no, you don't. In the same way, you don't need to know the records you are locking if you just introduce a single flag that indicates whether a database lock is being held (and by whom). Of course, this lock can only be granted when there are no record locks, etc.
I agree that the code can easily be modified to lock 4 to 15 records, but what for?

But Peter, isn't this a hard possibility to wait for everyone to stop locking for a database lock to proceed. This situation may not be in a working situation, because there will be a number of people locking/unlocking records. Our 'Full Databse lock' thread is also one among the competing thread, with equal priority. Is my thinking correct ?

Your thinking is correct, in principle. Yes, what I described basically means that record locks are given priority over database locks. Whether that is acceptable depends on what you think the database lock is for -- the instructions don't tell you, so it is up to you to come up with a theory and implement your design accordingly. I would just want to make the following two points.
1) While in theory, you may have to wait indefinitely for your database lock to be granted, I do not expect any problems in practice. The Data class is not intended for massive loads (it would collapse). Locks are only held for a very short time. In a realistic usage scenario, the average number of locks held at any time will be well below 1.
2) Implementing a database lock that is not susceptible to deadlocks (if you allow multiple record locks per client), or able to detect deadlocks and break them, is much more complicated. The instructions encourage you to favour simplicity over performance -- and in this case, "performance", to me, is the speed at which a database lock is granted.

I shall do this as you suggested [re: interrupt handling]

I outlined four completely different alternatives, and you can probably put up a decent argument for every single one of them. Take your pick. The only point I was trying to make, really, is that this is not a matter of taste or chance but another one of those design decisions that you should consciously make
- Peter
[ January 28, 2003: Message edited by: Peter den Haan ]
[ January 28, 2003: Message edited by: Peter den Haan ]