NX:Client crashed cause deadlock in LockManager

[Vlad Rabkin]

Hallo Andrew,
Thanx!
Finally I 've understood your point...!
It is correct I don't use pool. I've decided not to do it because a simple pool would have many drawbacks (major of them is performance). To make it professionally I would have to do 3 separate threads: one for object creation, a second for removal, and second for management etc. So, I've decided not to take a risk.
If I had a pool all your statements were correct!
That is what I said: By using the Hasmap in RemoteObject I have some kind of "client state". Pool should have only stateless objects...

Of course if later a pool will be implemented the current architecture must be reconsidered, but I suppose for the assignement it is Ok.
So, thanx a lot.
Vlad

[Vlad Rabkin]

Hi Max,
Sorry, I've forgotten to thank you for your help.
I 've ordered your book(isn't it your book for jdk 1.4 certification), to get some other information.
Thanx,
Vlad

[Max Habibi]

No problem Vlad: it's good, thoughtful discussion, and that's good for everyone. I'll looking forward to hearing that you passed M
All best,

[Jim Yingst]

[MH]: And if you did share, given your design constraints, then if GUI client #1 has records 4,5,6 locked, and GUI client #2 has records 7,8,9 locked, then how's client two to know supposed to know who has what? I'm missing something.
[VR]: Exactly that is the reason why I currently use additional HashMap in RemoteObject: to keep track on all active locks of the client.
As do I. Except that at this point Max and I are talking about the possiblity of two clients sharing one [/i]connection[/i]. Which is not at all required by the assignment; it's just a potential future enhancement which I have claimed is possible using my design. Probably it's best no to worry too much about this particular point - if it's beneficial to assume that 1 connection == 1 client, I can abandon the connection sharing possibility. (It's not being used now anyway.)
I disagree with Jim that One client can acquire only one lock, and to acqure lock for anothoer record he mus release first one. At the moment it is right, but generally it is bad idea (let's we want in future allow the GUI to book several rooms at the moment?).
In fact, we agree: now, one client can acquire only one lock, but in future enhancements this will probably not be true, and we wish to support these future enhancements. In fact my Data class and networking classes fully support this option - it's just the GUI client that doesn't. And I'm not putting deadlock protection in Data or the networking code, because I believe the proper place for it is in the GUI client. (Or rather, in the facade through which the GUI accesses the rest of the system.) That's the code that would have to change anyway for any future enhancements which would allow multiple locks. So I don't mind leaving out deadlock protection for now, as I feel I've made adequate provision for future enhancements, and to do more would be excess work IMO. I do include some documentation suggestions for how various future enhancements can be accomplished, which in include a warning about deadlock, and a suggestion as to how the client can be coded to always avoid it.

[Vlad Rabkin]

Hi Jim,

Except that at this point Max and I are talking about the possiblity of two clients sharing one [/i]connection[/i].

I understood it. As I said, i don't have any pool of Remote object, nor Singelton remote Object or any other enhanced patterns. So, it is impossible that 2 clients (in my design) will share the same remote object.
I know having some kind of state in Remote object is not perfect, because if I change my design in future and do something like have done this HashMap in RemoteObject will not work. So what, we will find then another solution! An application cannot be 100% expandable for any design changes...

I don't mind leaving out deadlock protection for now

So, does it mean you have decided totally to bypass deadlock handling? If I understand you correctly it is actually also good point, because no dead-lock handling was required by assignement.
The only thing what I disagree - dead-lock preventing is not a busines of client application...
Vlad
I don't quite

[Jim Yingst]

So, does it mean you have decided totally to bypass deadlock handling?
Yes. That is, my DB and network code don't do any deadlock prevention, and my client doesn't do anything that could possibly cause a deadlock.
The only thing what I disagree - dead-lock preventing is not a busines of client application...
Well, I think it needs to be done by something which can uniquely identify clients. The API for DB does not allow anything inside DB to be able to identify a client, IMO. The Connection is still a good place to do it, if we abandon the future possibility of connection sharing by multiple clients. That's OK, as you say, an application cannot be 100% expandable for any design changes. So I think deadlock prevention should be done by either the Connection or something else on the client side. (For myself, I reject the idea of a LockManager as it's been described so far because it seems to circumvent the lock() and unlock() prescribed by the DB API.)
My own preferred solution for deadlock prevention (if I were to implement it) would be to require each client to acquire its locks in a particular order, e.g. according to increasing record number. I believe this is the best way to guard against all the forms of deadlock which I can think of. (Including the 3-way deadlock which defeats Philippe's algorithm, as pointed out by Andrew on the previous page.) It's possible, probably even desireble, to have some server-side code which enforces this. (Can be done in Connection if it's single-client, or if we add some sort fo client ID tracking). However the client code needs to obey this protocol, or the server would keep rejecting its attempts to lock things out of order. So the client must be written to lock things in the correct order; the server may be written to ensure that this order is obeyed by each client. At least, using my preferred deadlock strategy. I'm sure there are other strategies; perhaps there's a better one which I have overlooked.
Note that for a "read" system the server should probably also have things like a timeout, which would help in deadlock situations - but it's too slow for my taste. Or maybe a cancel() method. But that only works once you've detected the deadlock, which is difficult for something like a 3-way deadlock. (Or 4-way, 5-way, etc.) I prefer to make the deadlock impossible in the first place.

[Max Habibi]

Originally posted by Jim Yingst:
So, does it mean you have decided totally to bypass deadlock handling?
Yes. That is, my DB and network code don't do any deadlock prevention, and my client doesn't do anything that could possibly cause a deadlock.
The only thing what I disagree - dead-lock preventing is not a busines of client application...
Well, I think it needs to be done by something which can uniquely identify clients. The API for DB does not allow anything inside DB to be able to identify a client, IMO.

I would suggest that each instance of Data, itself, keep track of the locks it owns. It would coordinate those locks with other clients by using a static* structure(say a Hashmap).

*[i]a static structure is the easiest way: but, for future enhancements, you could easily have the server give a reference to each client connection who is trying to connect to the same db.
all best,
M

[Vlad Rabkin]

Hi Jim,
Hi Max,
First, as i said I agree with the Jim's point that it is out of the scope of this assignement to handle such dead-lock (but just preffered to make it as an extra )
Max - your last idea is Ok, but I have singleton Data: I didn't want to make a pooling, but having no pool we can get a problem with the file connections. I've tested it under standart configuration of Windows 2000: after 2010 connection to file the server crashed with an Exception : Too many files open. I have read that in standard configuration of Solaris 5 max connections for the file per process is 256.
So, I dedicided to use singelton...
Jim, Max, could please take a look on my new topic about java.rmi.Connection.
Vlad,
Thanx

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi Jim,
Hi Max,
First, as i said I agree with the Jim's point that it is out of the scope of this assignement to handle such dead-lock (but just preffered to make it as an extra )
Max - your last idea is Ok, but I have singleton Data: I didn't want to make a pooling, but having no pool we can get a problem with the file connections. I've tested it under standart configuration of Windows 2000: after 2010 connection to file the server crashed with an Exception : Too many files open. I have read that in standard configuration of Solaris 5 max connections for the file per process is 256.
So, I dedicided to use singelton...

Hi Vlad,
Hmm..you have 256 concurrent connections to the file? That is, at the same instant? Seems like overkill: I don't you'd do it this way in a commercial app. Why do it here? Why not make connections are you need them? That is, don't just open up a connection to the file and hang onto it: open up a connection, do your business, and close the door when you're done.

Jim, Max, could please take a look on my new topic about java.rmi.Connection.
Vlad,
Thanx

np,
M
[ July 16, 2003: Message edited by: Max Habibi ]

[Vlad Rabkin]

Hi Max,
With a Singletone I don't have concurrent connections to the file: One Singelton Data have only one connection!
I didn't want to allow multiple instances of Data exactly with the purpose not to have many connections.
If I had Data instances (not one, but per client) I would have to hold file connection (per client).
In order to close each connection I would have to supply a new method to Data : close(), which would close file connection (I decided not to extend Interface provided by Assignement, which doesn't have such method). Second: we cannot rely on client that he coorectly closes connection. So, before Data would be garbage collected we could get a problem.
Normally the best solution is providing close() method + pooling.
To avoid all these problems and complecated enhanced patterns, I use sigle Data object which has single connection to the file.
Access to the Data object I coordinate throught Read-Write Lock Manager (it has nothing to do mith LockManager).
It Works perfect!
Vlad

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi Max,
With a Singletone I don't have concurrent connections to the file: One Singelton Data have only one connection!
I didn't want to allow multiple instances of Data exactly with the purpose not to have many connections.
If I had Data instances (not one, but per client) I would have to hold file connection (per client).

I guess this is the point I was speaking to: as a matter of fact, you wouldn't need to maintain a File connection per client. All you'd have to do is make a connection when you need one: not the entire time. Of course, there's a tradeoff here. You're giving up cycles for memory. Still, it's the way I might do it in a real application.

In order to close each connection I would have to supply a new method to Data : close(), which would close file connection (I decided not to extend Interface provided by Assignment, which doesn't have such method).

Again, not if you did as I described above. of course, I'm just talking about this. Your design is fine, and I'm not suggesting that you change it.

Second: we cannot rely on client that he correctly closes connection. So, before Data would be garbage collected we could get a problem.

Either way, we're depending on the File Connection closing properly. It's just a risk tradeoff: do you want to hold onto the File, knowing that something could go wrong with it in the mean time(and know that only a single client can do anything at any given time, even read), or do you want to keep opening/closing it? It's a tough call.

Normally the best solution is providing close() method + pooling.
To avoid all these problems and complecated enhanced patterns, I use sigle Data object which has single connection to the file.

Seems reasonable.

Access to the Data object I coordinate throught Read-Write Lock Manager (it has nothing to do mith LockManager).
It Works perfect!
Vlad[/qb]

Wait, how many locks do ou have?
M
[ July 16, 2003: Message edited by: Max Habibi ]

[Jim Yingst]

I would suggest that each instance of Data, itself, keep track of the locks it owns. It would coordinate those locks with other clients by using a static* structure(say a Hashmap).
Like Vlad, I'm using a singleton Data instance. Or more properly a multiton, if anyone ever wants to access a different DB file. But there's only one instance of Data per DB file.
As previously discussed, I can track locks from the Connection object, and if we abandon the idea of connection sharing then I can enforce deadlock prevention from there. But I really want the client code to help with this.
Here's a scenario:
Client A has locked record 1, and now wants to lock record 2.
Client B has locked record 2, and now wants to lock record 3.
Client C has locked record 3, and now wants to lock record 1.
How can we prevent deadlock here?
My own solution would be to force client C to give up the lock on record 3 before locking record 1, because it's not allowed (according to me) to lock records out of order. Then client B will get record 3, complete his task and release 2 and 3. Then A will get 2, complete his task, and release 1 and 2. Then C can finally get 1 and 3.
How to implement this from the server? I can write code for Connection (single-clent) that detects that C is trying to lock 1 after already locking 3, and throw an exception. But the client code still needs to be modified to handle the locking correctly; if it just gets an exception, that doesn't help it know how to resolve the problem. The client needs to know to release its lock on 3 before locking 1. I'd prefer to write the client so it always locks in order in the first place.
Another possibility is that when the C's Connection receives the request to lock 1, it could first unlock 3 (without telling the client), then lock 1, then wait to re-lock 3 before returning. Hmmm, that actually might work. It's a little weird because the client thinks it's waiting for 3 when it's really waiting for 1, to be followed by 3, but the point is that the lock() won't return until both 1 and 3 are locked as originally requested. And the client doesn't even need to know about it. Yeah, that has some potential. I'll think some more on it.
It still seems as though a great deal of trouble will be avoided if the clients are written to behave themselves in a nice orderly fashion, rather than depending on Connection (or Data or whatever) to sort out their problems. An ideal solution would have well-behaved clients and a central authority capable of resolving problems if they do occur, IMO.
I still think deadlocks are out of scope for this assignment, but I might handle them anyway, as I'm starting to warm to this solution (letting Connection enforce locking order). I'll give it some more thought - along with possibly letting Data have multiple instances (which may mean I don't even need Connection anymore, if Data now tracks this info. But maybe that's just moving code from one class to another without accomplishing anything.)

[Andrew Monkhouse]

Hi Jim

It still seems as though a great deal of trouble will be avoided if the clients are written to behave themselves in a nice orderly fashion, rather than depending on Connection (or Data or whatever) to sort out their problems.

I must have spent too long working on middleware systems. Typically around 10 - 15% of the code I wrote was handling valid situations, and the other 85 - 90% was handling the invalid data either sent by the clients or received from the back end host. So now I am just too pesimistic, and just dont trust clients to follow the specs I write, or servers to follow the specs that they provide.
Oh well ... that's life.

An ideal solution would have well-behaved clients and a central authority capable of resolving problems if they do occur, IMO.

Agreed.
Regards, Andrew

[Jim Yingst]

Thinking on it some more, the ideal solution is proably to have well-behaved clients, and a server that will detect problems and resolve them by simply disconnecting any client who violates the spec. Cleaning up the problem quietly just encourages them to continue ignoring the spec. We don't need to put up with that sort of thing.

[Andrew Monkhouse]

Hi Jim

a server that will detect problems and resolve them by simply disconnecting any client who violates the spec

It would be nice. But it can cause you extra headaches. Especially when you get in to work one day and find that you have a complaint from a client saying that they got disconnected sometime yesterday and therefore your server is buggy. Now you have your boss screaming at you for putting buggy software into production, and you have to hope to go through your log files for the entire previous day and hope that you have enough information to be able to prove that the client was violating the spec.
Or even worse - the last commercial software I wrote was middleware for my client, and it was their clients who experienced the problems. So by the time the problem got to my attention, the end user would have complained about the buggy software to their sales rep at my client site who would have complained to both my clients and to the sales rep at my company, and I would typically be looking for a problem 2 to 3 days old while the sales reps were complaining to the managers about being unable to sell software because of bad coders.
Which is all a bit theoretical in the current assignment. I'll stop ranting now.
Regards, Andrew

[Philippe Maquet]

Hi Max,
You wrote :

All you'd have to do is make a connection when you need one: not the entire time. Of course, there's a tradeoff here. You're giving up cycles for memory. Still, it's the way I might do it in a real application.

As Vlad, I have only one FileChannel connection opened for the entire time the database is working, and it seems to fit well in my database design.
But reading this comment (and other ones) of yours, I wonder if my design is correct, and it would be great if I could benefit here from your guru-insight.
Let me explain it as briefly as I can :
Like Jim, I use the multiton pattern (one Data instance per database file).
I implemented a cache (to boost performance, but also because my design need it (see below).
The only one FileChannel I have is opened in my open() method. The latter first constructs a MetaData object (which interprets the file header, constructs in turn Field objects used to abstract field access (a field knows its index, its offset, its length) and to help bidirectional conversions between records and array of String field values. Afterwards, open() makes a one-pass read of the whole file to constructs indexes as/if defined, builds a list of deleted records (used later to optimize the createRecord method but also any method wich may throw a RecordNotFoundException), and for any field which is not indexed, builds a sorted list of distinct values (in such a way that any Field, indexed ot not, may be queried its distinct values in order to fill-in a search combobox for example).
All write methods (create/update/delete) build a "write operation object" and put it in a queue. Well, it's a rather complex queue, because I only need to keep the last write operation on a given record, while keeping the order in which those operations were build.
I have one thread dedicated to handle those write operations and perform the actual writes in the database. Except for deletes, it finds record information in the cache (that's why I need one), while the cache-cleaning process (the cache has a parametrable size) makes sure it never cleans a record up if it is implied in a pending write operation.
I see three pros in dealing with writes as I do :

The main one is that I can write a live-backup method in a few lines (after all they intend to move to the web). I just need to tell the WriteThread to stop writing, perform a quick copy of the database, and finally notify the WriterThread that it may go on with its job. In the meantime, all connections are still able to create/update/delete records without blocking.

As I only need to handle the last write operation, previous ones may be bypassed, all benefit to global write-throughput.

The - little - risk of dirty reads is put here at a minimum : as read operations first query the cache where all pending writes reside, when I need a new input from the file, I am pretty sure there will not be a simultaneous write operation on the same record, all that without further synchronizing.

Just one more word about caching : I cache records in their converted form (array of field values) in such a way that I optimize reads twice : if a given record may be read three times from the cache, it's read in the file only one time and converted only one time.
Finally, as locking is concerned, you know already from the previous page that I use a LockManager.
About it, Jim, you wrote :

Including the 3-way deadlock which defeats Philippe's algorithm, as pointed out by Andrew on the previous page.

I don't understand. Andrew pointed two issues out :

A bug, I could correct thanks to him (he pointed it out, I found a solution and corrected it)

The fact that I use currentThread() as the owner. IMO, it's just a limitation I'll document - the DBAccess interface cannot be changed, no solution is perfect, all of them imply tradeoffs - but a limitation which is acceptable : locking/unlocking should be a short-time-state process you may encapsulate on server-side in single methods (try .. finally) which will never spawn multiple threads (nor with RMI neither with sockets, even in the case you allocate connections to threads using a pool).

Jim, your solution of ordering recNos before locking is fine ... till your system use multiple tables. How would you handle it ? My database system being - as yours - multitable by design, I think my solution is simpler to code, easier to explain and finally less error-prone. BTW, it's not a 3-way scheme but a 4-way one : owner-table (the scope of recNos)-recNos-cookie. That's perhaps my best argument : with a LockManager, adding the notion of scope, allowing granting locks accross multiple tables while still preventing deadlocks, was very easy to implement, and I only needed to care with it once. In comparison, you must be aware of your ordering solution each time you need multiple locks, you need a pre-defined tables order too, and you must make sure that all clients respect those requirements.
Max, Jim, everybody, does that whole design make sense ?

Is there any big issue I am missing ?
Thanks a lot in advance,
Cheers,
Phil.

[Philippe Maquet]

Hi everybody,
Just for completeness. In my previous message, I forgot to mention the first main advantage of dealing writes to the file through a WriteThread among the pros I listed : the fact that from the client point of view write operations perform very quicly, without any file I/O blocking.
But it lets me think about a flaw in that design, easy to correct (and I would do).
Typically, there is much more reads than writes in any database system, in such a way that the WriteThread should perform fast enough in such a typical use to make sure that the write queue size remains acceptable. I just put some elasticity in the write process which is good thing. But any elastic band may break (lack of memory).
So I think that I should have some maxWriteQueueSize property to be able to handle huge writes without taking the risk to see the system explode. With that little plus added, write methods would block only when the write queue is full.
Cheers,
Phil.

[Vlad Rabkin]

Hi Max,

Wait, how many locks do ou have?

I have Lock Manager for (lock and unlock methods in Interface).
I have a ReadWriteLock (it is not a lock, it is just a name of Synchronisation pattern).
Nothing should be read while somebody writes and
nothing should be written when sobody read. It is controlled by ReadWriteManager (and has nothing to do a LockManager).
It seems that FileChannel or other classes from java.nio package can provide this functionality, but as I started implementing the assignement I used jdk 1.3.1.
Have I done something wrong?
Vlad

[Vlad Rabkin]

Hi,
I didn't use FileChannel in my assignement, because I as started my assignement I used jdk1.3.1. I used ReadWrite Lock Synchronization.
Now as I've seen in your mails, most of you use FileChannel class from jdk141 (at least I see that Phil does). I just have read description of this class:

File channels are safe for use by multiple concurrent threads. The close method may be invoked at any time, as specified by the Channel interface. Only one operation that involves the channel's position or can change its file's size may be in progress at any given time; attempts to initiate a second such operation while the first is still in progress will block until the first operation completes. Other operations, in particular those that take an explicit position, may proceed concurrently; whether they in fact do so is dependent upon the underlying implementation and is therefore unspecified.

It seems that this read-write lock mechanism makes no sense anymore. Do I understand it correctly?
Thanx,
Vlad

[Max Habibi]

Originally posted by Jim Yingst:
[QB][b]It still seems as though a great deal of trouble will be avoided if the clients are written to behave themselves in a nice orderly fashion, rather than depending on Connection (or Data or whatever) to sort out their problems. An ideal solution would have well-behaved clients and a central authority capable of resolving problems if they do occur, IMO.
I still think deadlocks are out of scope for this assignment, but I might handle them anyway, as I'm starting to warm to this solution (letting Connection enforce locking order). I'll give it some more thought - along with possibly letting Data have multiple instances (which may mean I don't even need Connection anymore, if Data now tracks this info. But maybe that's just moving code from one class to another without accomplishing anything.)
--------------------
QB]

'Morning Jim,
I think you're on the right track here: you do need well behaved clients. IMO, that's the whole point of connection: it's your well behaved client. It's your mediator: it's the guys who behaves 'nicely', regardless of what the GUI client tries to do. So yes, I do think it serves a purpose, and an important one at that. For example, Connection could be the guy who enforces the lock,read,modify,unlock sequence, when all the gui client says is 'do stuff'. This works regardless of whether you're using a singleton Data or multiple Data objects.
ps - any feedback yet on those textpad utils?
M

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi,
I didn't use FileChannel in my assignement, because I as started my assignement I used jdk1.3.1. I used ReadWrite Lock Synchronization.
Now as I've seen in your mails, most of you use FileChannel class from jdk141 (at least I see that Phil does). I just have read description of this class:

It seems that this read-write lock mechanism makes no sense anymore. Do I understand it correctly?
Thanx,
Vlad

You can still use jdk 1.3 file IO, but yes, IMO, FIleChannels are better mechanism. Also, since the whole point of this assignment is to make you a better developer, I say: go ahead and dig into the new technologies.
M

[Max Habibi]

Hi Phil,
You design looks ok, if a little overly complex. Just to stir up the pot a bit. Did you ever consider caching the records as you read them, and going to your cache instead of the File(for reads)?
M

[Philippe Maquet]

Hi Max,

You design looks ok, if a little overly complex. Just to stir up the pot a bit.

Thank you for that so much rewarding opinion.
Now I think that the overall complexity depends on how the code is written (after all, I could explain the whole database stuff in a "few" lines, including locking. Both of them weight 120 points (Locking=80 + Data class=40) in a total of 230 for specific topics (total = 400 - General Considerations = 100 - Documentation = 70) : 52.2% of all specific areas. I tried to spread the db functionality among multiple classes, each of them being responsible for a well-defined area, in such a way that discovering the whole system with a "top-down" approach is easy. Anyway I hope so !

Did you ever consider caching the records as you read them, and going to your cache instead of the File(for reads)?

That's what I do. I thought that it was implicit from what I wrote about caching :

Just one more word about caching : I cache records in their converted form (array of field values) in such a way that I optimize reads twice : if a given record may be read three times from the cache, it's read in the file only one time and converted only one time.

To be more precise, I implemented my cache based on an access-ordered LinkedHashMap.
Except in the open() method where it doesn't make sense, any read from the file goes in the cache.
As removing entries from the cache

takes some time

needs to be "smart" enough to make sure that records implied in a pending write operation are not discarded, which constraint makes the clean-up process even heavier,

I overrode the removeEldestEntry method to :

do the job myself

not everytime the cache size exceeds its limit, but when the excedent is a multiple of an arbitrary acceptable value.

Still OK ?
Cheers,
Phil.

[Vlad Rabkin]

Hi Max,
I have just read your book. Expecially interesting was information about FileChannel.
First, I decided to follow your advice "go ahead and dig into the new technologies" and redesign my architecture and switch to FileChannels.
I have understood 2 major advantages:
1) 2-way connection
2) the thread blocks till the data are written, guarantiing that the block will be correct written in a file.
I don't understand following: does it all mean that read-write operations are thread-safe, so that I don't need Read Write Lock Synchronization mechanism???
I hope you have understood the idea why have been using it, if not I here is this class(again, it has nothing to do with LockManager):

package suncertify.server;
/**
 * The class implements a ReadWriteLock pattern.
 *
 * Waiting writers are preferred over waiting readers when there is contention.
 *
 * Readers are blocked if there are waiting or active Writers,
 * waiting Writers are chosen arbitrary.
 * Writers are blocked if there are active Readers or active Writers.
 *
 * The Lock for reading may be held simultanously by multiple
 * reader threads, so long as there are no Writers.
 * The Lock for writing is exclusive.
 *
 * @author Vlad Rabkin
 * @version 1.0
 **/

public class ReadWriteLock {
  private static ReadWriteLock instance_ = new ReadWriteLock();
  public static ReadWriteLock getInstance() {
return instance_;
}
  private long activeReaders_ = 0;
  private long activeWriters_ = 0;
  private long waitingReaders_ = 0;
  private long waitingWriters_ = 0;
  private ReadWriteLock() {
  }

 /**
  * Tests if reading is allowed in the database.
  * @return Return true if there is no active or waiting writings ahead.
  */
  private boolean allowReader() {
    return activeWriters_ == 0 && waitingWriters_ == 0;
  }
 /**
  * Tests if writing is allowed in the database.
  * @return Return true if there is no active writings or active readings ahead.
  */
  private boolean allowWriter() {
    return activeReaders_ == 0 && activeWriters_ == 0;
  }
 /**
  * Acquires Lock for reading.
  * @throws InterruptedException if another thread has interrupted the current thread.
  */
  public synchronized void acquireReadLock()
   throws InterruptedException {
    ++waitingReaders_;
    while (!allowReader()) {
    // if reading is not allowed, then wait:
    // the current thread gives up the CPU and consumes no CPU cycles until
    // it is waked up.
     try {
      wait();
     } catch(InterruptedException ie) {
  --waitingReaders_; // roll back
      throw ie;
          }
     }
    --waitingReaders_;
    ++activeReaders_;
  }
 /**
  * Releases Lock for reading.
  */
  public synchronized void releaseReadLock() {
  --activeReaders_;
  notifyAll();
  }
 /**
  * Acquires Lock for writing.
  * @throws InterruptedException if another thread has interrupted the current thread.
  */
  public synchronized void acquireWriteLock()
   throws InterruptedException {
    ++waitingWriters_;
     while (!allowWriter()) {
    // if writing is not allowed, then wait:
    // the current thread gives up the CPU and consumes no CPU cycles until
    // it is waked up.
     try {
      wait();
     } catch(InterruptedException ie) {
  --waitingWriters_; // roll back
      throw ie;
          }
     }
    --waitingWriters_;
    ++activeWriters_;
  }
 /**
  * Releases Lock for writing.
  */
  public synchronized void releaseWriteLock() {
  --activeWriters_;
  notifyAll();
  }
  public synchronized String getInfo() {
      return "Readers: " + this.activeReaders_ + " Writers: " + this.activeWriters_;
  }
 }
  

It seems that by using FileChannels, I don't need it anymore...???
Many thanx in advance.

[Max Habibi]

Hi Philippe,
Sorry, I didn't mean to sound so critical: what I meant was this. By increasing the number of locks, you're increasing complexity of the app, and increasing the opportunity for deadlock, regardless of how you're using those locks. I suggest as few locks as possible. It sounds like you have more then you absolutely need.
About your caching. My apologies, I must not have understood you. Effectively speaking then, you read the File once, and never again? Or do you cache records as you read them, so you never have to follow up? If it's the latter( which it sounds like it is), why not do the former?
I'm not really advocating it, mind you: I'm just trying to get a sense of what factors you're weighing.
M
[ July 17, 2003: Message edited by: Max Habibi ]

[Jim Yingst]

[JY]: Including the 3-way deadlock which defeats Philippe's algorithm, as pointed out by Andrew on the previous page.
[Philippe]: I don't understand.
Sorry, Philippe. I see that I hadn't read your followup post closely enough. I retract my comment.
Jim, your solution of ordering recNos before locking is fine ... till your system use multiple tables. How would you handle it ?
Rather easily, at the client level - require all locking to be done in a particular order by table, e.g. alphabetical (using String's natural sort order for the canonical file name), then by record number within a table.
But to do this somewhere on the Server - hm, I hadn't thought about how multiple tables would relate to Connections. Currently a single client connecting to multiple tables would get multiple Connections, one per table. That means each Connection won't have enough info to prevent deadlock if the client is really waiting for locks on other tables to complete before releasing current locks. I'll have to look and see if there's an easy way to modify this, or if I'll just declare it out of scope for my assignment. Thanks.
[Philippe]: My database system being - as yours - multitable by design, I think my solution is simpler to code, easier to explain and finally less error-prone. BTW, it's not a 3-way scheme but a 4-way one : owner-table (the scope of recNos)-recNos-cookie. That's perhaps my best argument : with a LockManager, adding the notion of scope, allowing granting locks accross multiple tables while still preventing deadlocks, was very easy to implement, and I only needed to care with it once. In comparison, you must be aware of your ordering solution each time you need multiple locks, you need a pre-defined tables order too, and you must make sure that all clients respect those requirements.
Well, it would be similarly easy for me I think, if my Connection included all tables from that client. The main problem is, how do you identify a unique client? I had the implession you were tracking threads somehow (Thread.currentThread() probably) - I don't trust this idea at all if you're using RMI (which I am). However it's very possible I've misunderstood your design.
[Max]: IMO, that's the whole point of connection: it's your well behaved client.
Yeah, I think I'll just drop this silly connection-sharing idea; future enhancements will benefit more from having a guarantee that each Connection is associated with a unique client. Dunno if I can enforce such a guarantee, but I'll document it at least. Once I decide how or if I want to deal with the multi-table issue.
[Max]: ps - any feedback yet on those textpad utils?
Sorry, no - been buried in eclipse lately. But come to think of it I've got a couple of quick mini-projects in the next couple days that I could do in TextPad - that'll give me an excuse.

[Vlad Rabkin]

Hi Max,

increasing the number of locks, you're increasing complexity of the app, and increasing the opportunity for deadlock

That is what actually happened today while my last test
So, have to redesign the architechture. It just looks like FileChannel is thread safe and I don't ReadWriteLock (which caused the problem working together with LockManager)

Effectively speaking then, you read the File once, and never again?

Yeap, but I still need to synchronize it:
I should'r pick up any data from the cash, while somybody is writing in the file...
Is my assumption correct that FileChannel is thread safe, so I don't have any read-write synchronization?
Vlad

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi Max,

Yeap, but I still need to synchronize it:
I should'r pick up any data from the cash, while somybody is writing in the file...

Absolutely correct. Some of my private students have done a fairly clever thing, in that their Map has a recordno as a key, and a Record as a value. Thus, for locked, reading, et el, they simply synchronize on the map. One data structure, one lock.

Ori

Is my assumption correct that FileChannel is thread safe, so I don't have any read-write synchronization?
Vlad

Well, it's thread safer. That is, if you don't explicitly move the position by using FileChannel.postion, then your writes are guaranteed to be atomic. Also, if your IO in interrupted, then you'll actually get a InteruptedException. However, if you're sharing FileChannel across various threads, you would need o synchronize it.
That's why I suggest opening your FileChannel as you need them, in the method that uses them. Thus, on startup, load all the records. Then, you simply work with those loaded record, no more IO to read and search. unless you want to, say, modify a record.
To do that, you synchronize on the map, again get a FileChanel in the relevant method, do you business, release the FileChannel, and leave your synchronize block. Thus, you're only ever locking on one thing, and that's the map.
All best,
M

[Vlad Rabkin]

Hi Max,
thanx a lot for explaining FileChannel!
I will use it to write in file. (I have anyway to read the file header with DataInputStream, because it is required by assignement).
I think your idea about opening a FileChannel is great, but a bit weard: I thougt always that openening an closing connection to the file is pretty slow operation. As I correctly understand your idea in your case we don't open connection every time, but just FileChannel to opened connection (FileOuputStream or RandomAccesFile).
I will try to test it.
Thanx again for your advice!
Vlad

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi Max,
thanx a lot for explaining FileChannel!
I will use it to write in file. (I have anyway to read the file header with DataInputStream, because it is required by assignment).
I think your idea about opening a FileChannel is great, but a bit weard:

The story of my life

I thougt always that openening an closing connection to the file is pretty slow operation. As I correctly understand your idea in your case we don't open connection every time, but just FileChannel to opened connection (FileOuputStream or RandomAccesFile).
I will try to test it.
Thanx again for your advice!
Vlad

Yes, in this scenario, you open a connection when you need it, not if you need it. And you're right, opening a connection is slow. However, holding onto a connection that you're not using isn't a great thing either. For me, the tradeoff seems to be on the side of decreasing complexity and risk by decreasing the number of lock. Performance, as you know, is not a consideration in this assignment. That was the tie breaker for me. YMMV.
All best,
M

[Vlad Rabkin]

Hi Max,
That was a good koke about your life!
It sounds at least like your life makes you a lot of fun!
I just thought about following words of you:

Some of my private students have done a fairly clever thing, in that their Map has a recordno as a key, and a Record as a value. Thus, for locked, reading, et el, they simply synchronize on the map

if we just synchronize read and write on the map,
no read will be possible while another read.
(That was actually the idea of RWLock to allow symultanious reads).
May be I understood your ide not corretly?
Vlad

[Max Habibi]

Hi VLad,
No you understood it correctly, I just didn't state it well. you're right, of course, that synchronizing on the Map would force reads to wait. I should have said
"reads..where appropriate"
M

[Vlad Rabkin]

Hi Max,
Well that would make all things pretty simple and stable, but no reads allows while anobody reads at the moment will cause dramatic drawback in performance.
I don't want to develop own application server (as Phil tries ), but do you beleive Sun will accept such solution?
Vlad

[Max Habibi]

I'm suggesting that dirty reads might be ok, depending on the rest of your architecture. Dirty writes are the real danger. Also, you have to remember that you're reads will only take a few microseconds. you won't be forcing a second client to wait very long, even if they do happen to want to read at the same instant. Finally, you have to decide how you want to deal with this issue anyway; even if you decide to do file IO. with the original solution of using a single IO Stream, you're still forcing all the other clients to wait(or not, if you don't care about dirty reads).
M

[Philippe Maquet]

Hi Max,

By increasing the number of locks, you're increasing complexity of the app, and increasing the opportunity for deadlock, regardless of how you're using those locks. I suggest as few locks as possible. It sounds like you have more then you absolutely need

As I didn't talk about locks in my design description (except LockManager), I wonder if you didn't think that Vlad's code excerpt was mine ... I try to block as few as possible (as explained in my previous message, I even don't block on writes !).

About your caching. My apologies, I must not have understood you. Effectively speaking then, you read the File once, and never again? Or do you cache records as you read them, so you never have to follow up? If it's the latter( which it sounds like it is), why not do the former?
I'm not really advocating it, mind you: I'm just trying to get a sense of what factors you're weighing.

I did not understand your question till I read your later message to Vlad :

Thus, on startup, load all the records. Then, you simply work with those loaded record, no more IO to read and search. unless you want to, say, modify a record.

That's what I wanted to avoid, because the feasability of loading (and keeping) all records in memory depends on database size. What is we have 10000 records ? Or 100000 ?
So, on startup I read all records once, not to load them but :

build in-memory indexes (if any)

for other fields, build a TreeSet of distinct values

make an inventory of deleted records

During that startup process, I don't feed my LRU cache. It would slow down the startup process without even improving the performance of the first "real" reads :
If db size is 100000 and the DB admin set the cache size to 1024 (just an example), it's probably better to have get an empty cache after startup than a one filled in with the last 1024 end-of-file records. Right ?
Now I could consider this slight optimization : if the cache size is bigger that the db size, or even if it's size is significant in comparison with the latter (an arbitrary ratio), I could decide to feed the cache at startup. OK.
Or (new idea), accept for my cacheSize property a special value like CACHE_ALL (-1?) and if this value is used, I would :

feed the cache at startup

never clean it up

It should be a good thing for small tables.
Cheers,
Phil.
[ July 17, 2003: Message edited by: Philippe Maquet ]
[ July 17, 2003: Message edited by: Philippe Maquet ]

[Vlad Rabkin]

Hi Phil,

That's what I wanted to avoid, because the feasability of loading (and keeping) all records in memory depends on database size. What is we have 10000 records ? Or 100000 ?

Well, our record size 156 bytes (+4 bytes for Integer ID) I think it is Ok if the server reservers at least 256 MB for the database. It makes 256*1024*1024= 268.435.456 available bytes.
It means we can can hold there about 1.677.721 records... !
For more than that I would buy a database like DB/2 or Oracle
Vlad

[Vlad Rabkin]

Hi Max,
I agree,
Using dirty writes as well as reads, is dangerous.
So, actually what you suggest is Ok. The only problem is find() , which will produce overhead, but I will do what U suggest and test it. At least it is very simple and stable solution.
I have not much experience in synchronizing and threading ( I have been working only with applications servers for last 4 years), but it was a good lesson: USE MINIMUM LOCKS!
Thanx a lot,
Vlad

[Vlad Rabkin]

Hi Max,
I have completely rejected both ideas:
LockManager,
ReadWriteLock.
I have synchronized all read, write, find, lock/unlock and so on on the Map of record (since I have this map anyway - it is my cashed Database).
It works perfect.
I have now only two concerns:
since I synchronized all methods on the map (not to have dirty reads):
- find method (it doesn't read from database , only from cash) can be a bottleneck.
- What is real advance of using FileChannel with this design (all methods are synchronized, so we do not profit from FileChannel synchronization and atomicity of write operation)
I don't really know what Sun excepts from me !?
Could you let me know your opinion:
is it Ok that find() will be synchronized also?
Many thanx,
Vlad

[Tony Collins]

I have the same thoughts Vlad.
If you use File Channels do you have to lock the database at all ?
At what point could you manage a dirty write when using file channels ?
Does it matter if the write to a particular position is not atomic, the record is always going to be at the same position in the file. As a delete doesn't change the size of the file.
Tony
Tony

[Max Habibi]

Originally posted by Vlad Rabkin:
Hi Max,
I have completely rejected both ideas:
LockManager,
ReadWriteLock.
I have synchronized all read, write, find, lock/unlock and so on on the Map of record (since I have this map anyway - it is my cashed Database).
It works perfect.
I have now only two concerns:
since I synchronized all methods on the map (not to have dirty reads):
- find method (it doesn't read from database , only from cash) can be a bottleneck.
- What is real advance of using FileChannel with this design (all methods are synchronized, so we do not profit from FileChannel synchronization and atomicity of write operation)
I don't really know what Sun excepts from me !?
Could you let me know your opinion:
is it Ok that find() will be synchronized also?
Many thanx,
Vlad

Hi Vlad,
I have a question for you: and it's not meant to be leading question, I'd just like to hear your thoughts.
1.Why did you decide to synchronize read and find?
2. In terms of what Sun expects: I think they expect you to adhere to their specs, be able to see the pros and cons of your design/implementation, make a reasonable choices, and defend them. I don't think they're looking for any set answer.
3. The real advantage of FileChannels (here)are guaranteed atomic actions, Interruptible IO, and better performance.
HTH,
M