• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Bad locking solution !

 
Perceval BRET
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I'm working on B&S v2.1.3 using a cookie lock mechanism.
If you have the same exam requirements as mine and the code hereafter (the first I've thought about), then find another solution !


Sorry for my poor english!


requirements are:

// Locks a record so that it can only be updated or deleted by this client.
// Returned value is a cookie that must be used when the record is unlocked,
// updated, or deleted. If the specified record is already locked by a different
// client, the current thread gives up the CPU and consumes no CPU cycles until
// the record is unlocked.
public long lock(int recNo) throws RecordNotFoundException;


Here is my lock method:

And my unlock method:

This implementation looks like the same as other code I've seen on this forum.

I've made a test to check the lock mecanism behavior in multithreading environment, adding some output messages.
Each thread has the folowing code:

long cookie = lockManager.lock(recNo);
Thread.sleep(time);
lockManager.unlock(recNo, cookie);

launch it with parameters:
Thread-0, record 0, 1000 ms
Thread-1, record 1, 2000 ms
Thread-2, record 1, 1000 ms
Thread-3, record 1, 1000 ms
Thread-4, record 0, 1000 ms

Result output is:

Thread-0 - has locked record 0
Thread-0 - is sleeping 1000 ms
Thread-1 - has locked record 1
Thread-1 - is sleeping 2000 ms
Thread-2 - is waiting for record 1
Thread-3 - is waiting for record 1
Thread-4 - is waiting for record 0
Thread-0 - has unlocked record 0
Thread-2 - wakes up
Thread-2 - is waiting for record 1
Thread-1 - has unlocked record 1
Thread-3 - wakes up
Thread-3 - has locked record 1
Thread-3 - is sleeping 1000 ms
Thread-3 - has unlocked record 1
Thread-4 - wakes up
Thread-4 - has locked record 0
Thread-4 - is sleeping 1000 ms
Thread-4 - has unlocked record 0
Thread-2 - wakes up
Thread-2 - has locked record 1
Thread-2 - is sleeping 1000 ms
Thread-2 - has unlocked record 1


First problem: Thread-2 is awoken by Thread-0 wich has unlocked record 0 but Thread-2 is not waiting for that record... so, it sleeps again. To sum up, Thread-2 has consumed CPU cycles whereas the record 1 has not been unlocked.
Second problem: (consequence to the first one) As Thread-2 sleeps again, no other threads are awoken until a thread unlocks a record and notifies it.

The second problem can be solved replacing notify by notifyAll but the first problem still remains.

Conclusion: This is a bad locking solution.
 
Anton Golovin
Ranch Hand
Posts: 530
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Perceval BRET:
Hi,


First problem: Thread-2 is awoken by Thread-0 wich has unlocked record 0 but Thread-2 is not waiting for that record... so, it sleeps again. To sum up, Thread-2 has consumed CPU cycles whereas the record 1 has not been unlocked.
Second problem: (consequence to the first one) As Thread-2 sleeps again, no other threads are awoken until a thread unlocks a record and notifies it.

The second problem can be solved replacing notify by notifyAll but the first problem still remains.

Conclusion: This is a bad locking solution.


1) True, there is a lot of waking of threads which are waiting for something else. It cannot be helped.

2) The CPU cycles consumed are insignificant when compared to the amount of waiting done. So I think it is the best that can be done for locking.
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Anton Golovin:

1) True, there is a lot of waking of threads which are waiting for something else. It cannot be helped.

2) The CPU cycles consumed are insignificant when compared to the amount of waiting done. So I think it is the best that can be done for locking.


There is an alternate approach, which I have implemented for a real world project many years ago. It involves keeping a queue of users waiting for each resource to become free. When a resource comes free you notify the first user on that resource's queue. The code is very complex and probably burns more CPU than the simple code posted by the OP, especially when the number of users and the contention for locks is low.

I'm using the simple approach for this project, its simple, straight forward and its correctness can be easily demonstrated.
 
Andrew Monkhouse
author and jackaroo
Marshal Commander
Pie
Posts: 12014
220
C++ Firefox Browser IntelliJ IDE Java Mac Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everyone,

It seems that candidates are not being penalised for using notifyAll() even though it does go against the "consume no CPU cycles" requirement.

One or two candidates have met this requirement by having a collection of mutable objects - one for each record. Then the waiting client will wait on the object that corresponds to the record they want. This way they will only be woken when their particular record is released. Note that this does require a mutable object to work - if you use an immutable object (like an Integer) you can cause all sorts of problems.

The FIFO solution suggested by Peter has been used successfully as well - it is possibly the best real world solution, but like Peter I do wonder about the complexity of code which will result.

Regards, Andrew
 
Udham Singh
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Andrew !

I have a question about the second solution. I thought of it too but couldn't think of a way to implement isLocked(). Is there a way in Java for one thread to know if there are other threads waiting on a particular object?

If yes could you please tell me how or point in the right direction.

I've already implemented the first solution (the one that wastes CPU cycles). Hopefully I won't it be penalized too much for it.

Thanks !
 
Andrew Monkhouse
author and jackaroo
Marshal Commander
Pie
Posts: 12014
220
C++ Firefox Browser IntelliJ IDE Java Mac Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Udham,

I have a question about the second solution. I thought of it too but couldn't think of a way to implement isLocked(). Is there a way in Java for one thread to know if there are other threads waiting on a particular object?


You don't need to know if there are other threads waiting for that particular object, just whether it is currently locked or not.

Regards, Andrew
 
Udham Singh
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andrew,

Is there any straight forward way of determining that?
The reason I wanted to check for waiting threads was because they indicate a locked resource. Of course, just because there are no threads waiting doesn't mean the resource is available and thanks for pointing that out to me.

But still, since there is one lock per record how would one know if the lock is availble or not without first acquiring it?

I guess now my question would be is there anything in the language itself (or API) that lets you do that? Or can you think (or know) of a way around this problem i.e. determing if the resourse is locked/unlocked without acquiring the lock.

Thanks
 
Werner Bast
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


And my unlock method:


...

First problem: Thread-2 is awoken by Thread-0 wich has unlocked record 0 but Thread-2 is not waiting for that record... so, it sleeps again. To sum up, Thread-2 has consumed CPU cycles whereas the record 1 has not been unlocked.
Second problem: (consequence to the first one) As Thread-2 sleeps again, no other threads are awoken until a thread unlocks a record and notifies it.

The second problem can be solved replacing notify by notifyAll but the first problem still remains.

Conclusion: This is a bad locking solution.


I saw this pattern in the book "effective java(Joshua Bloch)" and wonder if it can be rewritten by simply adding
an if-block after the wait() like this:


So this is a solution between notify( who wakes one thread ) and
notifyAll( who wakes all threads)

But this is just a simple idea.

Greetings Werner
 
James Turner
Ranch Hand
Posts: 194
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A good point has been made by this post that waiting threads are woken up even if the record lock they are waiting for has not been released. I have a method of doing it by waiting on the lock itself.

Basically, the code is:

public long lock(int recNo) throws RecordNotFoundException {
// Check if lock exists in map of locks.

// If present...
synchronized (recordLock) {
recordLock.wait();
}

// else create your own lock.
}

public void unlock(int recNo, long cookie)
throws RecordNotFoundException, SecurityException {

// Get lock, and remove it from lock map.

// Notify all threads waiting on that particular lock that
// it is now unlocked.
synchronized (recordLock) {
recordLock.notifyAll();
}
}

The thread is waiting on the lock, not the Lock manager, therefore no unnecessary wakes are made as notifyAll only wakes the theads waiting for the specific lock, not any threads waiting for other locks.

This methods does not waist any CPU cycles which is a requirement of the assignment. This appears to work, with my initial tests. I would love to hear any comments on this design. Anything i havn't throught of, any better way of doing it.

I don't think it's very complex and it seems to achieve it's goal.

Looking forward to any comments.

James.
 
Perceval BRET
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a solution I've thought about but there's another thread problem.

Thread-1 -> checks if lock exist (answer: no)
Thread-1 -> creates the lock and does some stuff
Thread-2 -> checks if lock exist (answer: yes)
Thread-2 -> waits for the lock
Thread-1 -> remove the lock from the map
Thread-3 -> checks if lock exist (answer: no)
Thread-3 -> creates the lock and does some stuff
Thread-1 -> notifies the lock has been released
Thread-3 -> remove the lock from the map
Thread-4 -> checks if lock exist (answer: no)
Thread-4 -> creates the lock and does some stuff
...

Thread-2 can wait for long time
 
James Turner
Ranch Hand
Posts: 194
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good point there...

I could amend my unlock method to correct this:

public void unlock(int recNo, long cookie)
throws RecordNotFoundException, SecurityException {

// Get lock

// Remove the lock from the map and notify all
// threads waiting on that particular lock that
// it is now unlocked.
synchronized (recordLock) {
map.remove(recordLock);
recordLock.notifyAll();
}
}


This may help.. it could still have some problems to it.. I will need to think about this more. I think the lock and unlock methods need to be synchronized also..Dead lock is a possibility if we are not careful.

Comments welcome...

James.
 
Linda Andersson
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes this with deadlock is a problem.
If Thread 1 locks record 0 and then gets a RemoteException before it can unlock it. Then all other Threads that tries to lock record 0 will be in a deadlock. Have anyone any idea to how this can be solved?

//Linda
 
Inuka Vincit
Ranch Hand
Posts: 175
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Linda Andersson:
Yes this with deadlock is a problem.
If Thread 1 locks record 0 and then gets a RemoteException before it can unlock it. Then all other Threads that tries to lock record 0 will be in a deadlock. Have anyone any idea to how this can be solved?

//Linda


I am still doing background analysis research for my project but this is the only sollution I can think of other than using some kind of timeout scheme.
link to java RMI FAQ but I think this would make things realy messy

as far as locking, instead of locking using the container data type that holds locked as the locking object, one could use a factory type wrapping object that associates a record with an object instance, in which case you dont wake every single thread that is waiting every time a lock is released. I am still dreaming up my design... ofcourse there maybe be holes in my thinking. This is similar to what Andrew said.., so if you use a scheme like this and then call wait with a timeout time the lock wont be held forever, but then the question is how long should the timeout time be. Accordig to RMI specs should be atleast 10minutes, because if the lock times out before the RMI server does your screwed.

so many things to think about ..

back to analysis.
[ October 06, 2004: Message edited by: Inuka Vincit ]
 
James Turner
Ranch Hand
Posts: 194
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To avoid deadlock problems would it be the case to simply issue a timeout in the wait method?

public long lock(int recNo) throws RecordNotFoundException {
// Check if lock exists in map of locks.

// If present...
synchronized (recordLock) {
recordLock.wait(timout); // Timeout could be anything...1min, 10mins...
}

// else create your own lock.
}

Some thorough testing is required here...

James.
 
Andrew Monkhouse
author and jackaroo
Marshal Commander
Pie
Posts: 12014
220
C++ Firefox Browser IntelliJ IDE Java Mac Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Linda,

Yes this with deadlock is a problem.
If Thread 1 locks record 0 and then gets a RemoteException before it can unlock it. Then all other Threads that tries to lock record 0 will be in a deadlock. Have anyone any idea to how this can be solved?


This is another way of saying that there has been a communications breakdown between the client and server, resulting in an orphaned lock on the server (which implies that the client is calling the lock and unlock methods).

If this happens, then the server will (eventually) be notified that the client is no longer connected. If you wish, you can receive that notification - look at the java.rmi.server.Unreferenced interface for more information. Or (if you are not using lock cookies) you could use the instance of the connection in a WeakMap to have locks automagically cleared after being orphaned (more on that solution in Phil's excellent "WeakHashMap vs WeakReferences" discussion).

Regards, Andrew
 
Andrew Monkhouse
author and jackaroo
Marshal Commander
Pie
Posts: 12014
220
C++ Firefox Browser IntelliJ IDE Java Mac Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi James,

To avoid deadlock problems would it be the case to simply issue a timeout in the wait method?


Do you think you can do that without breaking the instructions? Or without changing the described interface?

Regards, Andrew
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic