[concurrency-interest] problem with ReentrantReadWriteLock toimplement atomic function

Kolbjørn Aambø kaa at pax.priv.no
Tue Jun 20 03:57:12 EDT 2006


No there are no OutOfMemory issues as far as I can understand:

The code is made to implement 1:1 relations where accessing values to  
get
keys will happen as efficient as retrieving keys to get their values.

I suspect that the maximum number of locks (65536 recursive write  
locks and 65536 read locks) happen to be the problem here. I'm trying  
to find out how to make  an atomic put function using  
ReentrantReadWriteLock without getting problems with this limitation.

public V put(K key, V value){
	// Tested to be lock robust for upt to 300K Objects 060608
		boolean hasValue = V_K.containsKey(value);
		boolean hasKey = K_V.containsKey(key);
		V value2 = null;
		
		r.lock();
		try {
			hasValue = V_K.containsKey(value);
			hasKey = K_V.containsKey(key);

			if (!hasValue){// No preexisting occurrence of value
				r.unlock();
				w.lock();
				if (hasKey) V_K.remove(K_V.get(key));
				V_K.put(value, key);
				value2 = K_V.put(key, value);
				r.lock(); // Downgrading the lock to read lock
			}
		} finally {
			r.unlock();
		}		
		return value2;
	}// put(..)


The following implementation don't have this limitation and will go  
on working until RAM becomes a problem:
The question is will this implementation work as an atomic put function?

	
	public V put(K key, V value){
	// Tested to be lock robust for up to 300K Objects
		boolean hasValue = V_K.containsKey(value);
		boolean hasKey = K_V.containsKey(key);
		V value2 = null;
		
		r.lock();
		try {
			hasValue = V_K.containsKey(value);
			hasKey = K_V.containsKey(key);
		} finally {
			r.unlock();
		}

		if (!hasValue){// No preexisting occurrence of value
			w.lock();
			try {
				if (hasKey) V_K.remove(K_V.get(key));
				V_K.put(value, key);
				value2 = K_V.put(key, value);
			} finally {
				w.unlock();
			}
		} 		
		return value2;
	}// put(..)
	


	
	







On Jun 19, 2006, at 3:18 PM, David Holmes wrote:

> Brief comment: I think the IllegalMonitorStateException may be  
> masking an
> OutOfMemoryError. If you look at the problematic code it assumes no
> exceptions occur.
>
>   r.unlock();
>   w.lock();
>   if (hasKey) V_K.remove(K_V.get(key));
>   V_K.put(value, key);
>   value2 = K_V.put(key, value);
>   r.lock(); // Downgrading the lock to read lock
>   }
>   } finally {
>     r.unlock();
>   }
>
> Any exception at either put() will cause the finally to unlock the  
> read
> lock, which isn't locked.
>
> David Holmes
>
> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of  
> Kolbjørn
> Aambø
> Sent: Monday, 19 June 2006 6:18 PM
> To: Doug Lea
> Cc: concurrency-interest at cs.oswego.edu
> Subject: [concurrency-interest] problem with ReentrantReadWriteLock
> toimplement atomic function
>
>
> In the code below I try to make an atomic put function. I suspect  
> that my
> implementation that divide the function
> into to try blocks, one for reading and then one for writing will  
> not be
> atomic since there are two try blocks.
>
>
> I have tried to implement the function with one try block first but  
> stumpled
> as seen below. Can you give me some
> advice?
>
>
> Best wishes
>
>
> Kolbjørn Aambø, Oslo
>
>
>
>
>
>
> //
> //  Unique.java
> //  JT1
> //
> //  Created by Kolbjørn Aambø on 2/1/06.
> //  Copyright 2006 __MyCompanyName__. All rights reserved.
> //
> import java.util.concurrent.*;
> import java.util.concurrent.locks.*;
> import java.util.*;
>
>
> public class Unique<K extends Comparable<K>, V extends  
> Comparable<V>> {
> private ConcurrentHashMap<K, V> K_V = new ConcurrentHashMap<K, V>();
> private ConcurrentHashMap<V, K> V_K = new ConcurrentHashMap<V, K>();
> //private Map<V, K> V_K_Text = new TreeMap<V, K>();
> private final ReentrantReadWriteLock rwl = new  
> ReentrantReadWriteLock();
> private final Lock r = rwl.readLock();
>     private final Lock w = rwl.writeLock();
>
>
> public Unique () {}
>
>
> public V put(K key, V value){
> // Tested to be lock robust for upt to 300K Objects 060608
> boolean hasValue = V_K.containsKey(value);
> boolean hasKey = K_V.containsKey(key);
> V value2 = null;
>
>
> r.lock();
> try {
> hasValue = V_K.containsKey(value);
> hasKey = K_V.containsKey(key);
> } finally {
> r.unlock();
> }
>
>
> if (!hasValue){// No preexisting occurrence of value
> w.lock();
> try {
> if (hasKey) V_K.remove(K_V.get(key));
> V_K.put(value, key);
> value2 = K_V.put(key, value);
> } finally {
> w.unlock();
> }
> }
>
>
> /* The code above works (I think) but the code below, that I  
> thought was the
>   the more appropriate  way of doing locking to get atomic  
> functionality
> stops like
>   this at about 65K inserts...:
>
>
> :
> 64000.0/640000.0  10 insert/ms
> 65000.0/650000.0  4 insert/ms
> [LaunchRunner Error] JTally.main(String[]) threw an exception:
> java.lang.IllegalMonitorStateException
> at
> java.util.concurrent.locks.ReentrantReadWriteLock 
> $Sync.tryReleaseShared(Reen
> trantReadWriteLock.java:275)
> at
> java.util.concurrent.locks.AbstractQueuedSynchronizer.releaseShared 
> (Abstract
> QueuedSynchronizer.java:1180)
> at
> java.util.concurrent.locks.ReentrantReadWriteLock$ReadLock.unlock 
> (ReentrantR
> eadWriteLock.java:576)
> at Unique.put(Unique.java:61)
> at Tally.put(Tally.java:116)
> at tryTally.testCombinedUNIQUE13(tryTally.java:41)
> at JTally.main(JTally.java:272)
> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> at
> sun.reflect.NativeMethodAccessorImpl.invoke 
> (NativeMethodAccessorImpl.java:39
> )
> at
> sun.reflect.DelegatingMethodAccessorImpl.invoke 
> (DelegatingMethodAccessorImpl
> .java:25)
> at java.lang.reflect.Method.invoke(Method.java:585)
> at apple.launcher.LaunchRunner.run(LaunchRunner.java:88)
> at apple.launcher.LaunchRunner.callMain(LaunchRunner.java:50)
> at
> apple.launcher.JavaApplicationLauncher.launch 
> (JavaApplicationLauncher.java:5
> 2)
>
>
> JTally has exited with status 0.
>  */
> /*
>
>
> r.lock();
> try {
> hasValue = V_K.containsKey(value);
> hasKey = K_V.containsKey(key);
>
>
> if (!hasValue){// No preexisting occurrence of value
> r.unlock();
> w.lock();
> if (hasKey) V_K.remove(K_V.get(key));
> V_K.put(value, key);
> value2 = K_V.put(key, value);
> r.lock(); // Downgrading the lock to read lock
> }
> } finally {
> r.unlock();
> }
> */
> return value2;
> }// put(..)
>
>
>
>
> public V get(K key){
> return K_V.get(key);
> }
>
>
> public K getKey(V value){
> return V_K.get(value);
> }
>
>
> public boolean containsKey(Object key){
> return K_V.containsKey(key);
> }
>
>
> public boolean containsValue(Object value){
> return V_K.containsKey(value);
> }
>
>
> public boolean contains(Object value){// for compatability with  
> hashtable
> return V_K.containsKey(value);
> }
>
>
> }
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20060620/65398812/attachment-0001.html 


More information about the Concurrency-interest mailing list