Skip to main content

Concurrent locks for large number of objects

9 replies [Last post]
byhisdeeds
Offline
Joined: 2006-01-06
Points: 0

I'm recursing over about 2000 objects with multiple threads and need to have some locking to prevent two or more threads accessing the same object while it is being processed. I thought of attaching a semaphore to each object and letting the threads acquire it while using the object, which would allow the other threads to block till that object had been processed.

My question is:
1) Is there a better way to handle this case than create 2000+ semaphores
2) Is the memory footprint of the 2000+ semaphores large.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
filip_pas
Offline
Joined: 2003-06-14
Points: 0

Be careful with this approach. It only avoids syncronized methods of the object being called.
Unsynchronized methods can still alter the state of the object u'r synchronizing on. You must make sure that u synchronize the object like posted before using it in every thread running or make sure all methods on obj called by the other threads are synchronized.

byhisdeeds
Offline
Joined: 2006-01-06
Points: 0

> Be careful with this approach. It only avoids
> syncronized methods of the object being called.
I realise this, and for me it is a plus. These 2000+ objects have attachment objects that are being worked on, and I need to synchronize on these attachments while allowing other threads to use the base object during this time.

I thought about the scheme used by hanot but I'm wondering about the cost in performance of looking up the locks in a table.

For now I'm synchronizing on specific objects and running some performance metrics, then I'll try locks and see how that affects things.

Thanks everyone.

sdo
Offline
Joined: 2005-05-23
Points: 0

A couple of points:

First, as I think you've realized (but just in case everyone else hasn't), semaphores cannot be reacquired in the way locks and monitors can be. So for a recursive call (or any other mechanism where the same resource needs to be locked twice in the same thread), you can't use semaphores.

Second, the performance issue in this space isn't around the number of locks -- it's about contention for the locks. It's hard to say without seeing the actual code, but that usually means you're better off with more, finer-grained locking. So don't be afraid to use as many as you can in order to reduce the contention for the objects (that is, in order to hold onto locks for the shortest possible time).

The memory footprint of a few thousand Lock objects won't be negligible, but again depending on the rest of your application (and your heap size), it's unlikely to have a big effect. However, the monitor uses no extra objects, so it will have a slight advantage there.

If you get to the point where the locks are finely-grained and hence the contention for them is small, monitors will be better -- particularly in Mustang, where the acquisition of uncontended locks is particularly optimized. And of course, the contention for the locks also depends on the number of threads you choose to run -- if the threads are CPU bound (which sounds like the case), then you'll need very few to get the best throughput anyway, further reducing the contention for the locks.

hanot
Offline
Joined: 2003-06-18
Points: 0

If you are using lock partitioning you don't need to have a concurrency overcost. In our case locks are preallocated before, in an array. The only overcost we have is the hashCode % array.length to retrieve the entry.
What you can do also is to keep a lock reference in your objects. ( in our case we have millions of objects a the memory cost of the reference is a bit to high ) .

But as i said if you have only 2000 objects , you can allocate a lock per objects , it works fine.

byhisdeeds
Offline
Joined: 2006-01-06
Points: 0

I've settled on pre-allocating a set of locks and keeping a reference to it in the object. I'm doing some testing now to determine the performance of the scheme.

hanot
Offline
Joined: 2003-06-18
Points: 0

We had the same problem on our project. What we did to bypass the problem is a simple lock partitioning.

What we have is a table of lock ( very simple one of N lock preallocated ) , and each object access to its lock by its hashCode % N ( so locks are shared between objects ). All you need to have is a good hashCode on your objects and to have N at least 3 times superior of the number of threads ( obviously higher N is better).

Using monitor was not satisfying because we need to lock all objects in one pass which is not possible with monitors.

But in your case 2000 locks is very acceptable ( N is sized to 5000 in our case ;) ) .

Using this solution you also need to care about lock overlapping to avoid dead lock :
if you need in the same time to lock multiple objects ( object 1 and 2 and from other thread object 2 and 1).

For solving this we had to defined a depth of access and add one dimension to the lock table to have partitioning per depth.

Hope this help.

linuxhippy
Offline
Joined: 2004-01-07
Points: 0

Should not be that bad, but you could also use java monitors for this task.

Lets assume your objects are in an Array-List, you could run the following code from many threads and java cares that only in thread is inseide the synchronized block for one object.

ArrayList list = ....

for(int i=0; i < list.size(); i++)
{
Object obj = list.get(i);

synchronized(obj) //This ensures, that only one thread modifies this object at the same time
{
//modify the object
}
}

byhisdeeds
Offline
Joined: 2006-01-06
Points: 0

I was reading somewhere (I can't remember where) that using monitors via the synchronized statement was not as efficient as the new java.util.concurrent classes under heavy threading load.

Also, as I will be using a recursive method, I figure that I need to have read locks and write locks rather than semaphores. Am I right in thinking this?

I have the following code:

public void sample(Object o)
{
if (o.level == finest)
{
// fill object with data from base data
o.fill(...);
return;
}

for (int i=0; i<4; i++)
{
sample(o.child[i]);
}

// fill object with data from four children
o.fill(...);
}

So I would use write locks around the fill method and read locks around any code to read the contents for the object.

That will mean 2000+ RentrantReadWriteLocks, and I'm not sure how much of an impact that this will have on my code.

alexlamsl
Offline
Joined: 2004-09-02
Points: 0

It might help if you can change your case to one that uses AtomicReference, otherwise I see no harm in using thousands of Locks.

I've been using thousands of synchronized statements with 1000 threads in Mustang Client JRE and it seems to be running smoothly.