Re: Concurrent bidirectional one-to-many map?
Am 10.05.2011 09:34, schrieb Tom Anderson:
On Mon, 9 May 2011, Sebastian wrote:
Am 09.05.2011 19:28, schrieb Tom Anderson:
On Mon, 9 May 2011, Robert Klemme wrote:
On 5/7/2011 2:43 AM, Sebastian wrote:
...
To give an example, I'm trying to solve a problem like this:
Associate tasks with workspaces, where a workspace may hold many
tasks,but a task may be associate with at most one workspace.
...
This could be solved by standard relationship implementations: Make
workspace a member of Task and synchronize accesses on Task. Example:
https://gist.github.com/962538
By using monitors of Task and Workspace we have quite fine granularity
of locking.
Thank you Robert for that instructive example.
I can't modify Task, or Workspace, and I won't do much "passing
around" either, as I'm writing a component that will be called
remotely (over RMI). But I suppose I could create a wrapper object for
each Item/Workspace on the first call and look them up in maps indexed
on the Item/Workspace id. Now I wonder if I just have shifted the
problem to these maps?
...
I don't think you have. The contents of those maps will never change -
you will need to add a new mapping when you first see a new key, but the
mapping will never change (except to be removed), and mappings in the
two maps are independent.
...
For the master maps, though, i'd look at using a ConcurrentMap, which
does not involve locking the whole map. You want to look at the
putIfAbsent method in particular.
...
I hope I got the quoting right, and left enough context for everyone to
follow the discussion.
The maps are independent from each other, but I think not independent
from the rest of the coding.
Let's call the class that uses Robert's TskWp as a datastructure and
manages the two concurrent maps the WorkspaceManager. This class would
need to be able to look up tasks on their ID's and add them to a
workspace. It can use putIfAbsent() and get() to find the Task instance.
It would also need to clear tasks that have workspace==null from the
task map (perhaps after some timeout). In order to prevent concurrency
issues (the removal getting in between the putIfAbsent and the get),
I'd have to hold locks on the map.
It would be a bad thing to assign tasks to a workspace that is
being closed.
I show some code below to illustrate what I mean. Am I correct?
And if I have to hold these locks, how much advantage of an advantage
is left over the original (and much simpler) suggestion by Patricia?,
which was:
[> Am 07.05.2011 15:40, schrieb Patricia Shanahan:
I'd deal with that sort of problem by having a custom data structure
that uses java.util structures in its implementation.
For example, class TaskMapping could have a Map<Task,Workspace> that
maps a task to its workspace, and a Map<Workspace,Set<Task>> that maps a
workspace to the set of tasks it currently holds.
]
You probably will want to use monitors for the WorkspaceWrapper and
TaskWrapper's relationships with each other, though.
tom
Yes, that's exactly what Robert does in his coding.
I don't feel too clever, not being able to wrap my mind around this
concurrency stuff.
-- Sebastian
Here's a bit of the WorkspaceManager code referred to above:
import clj.TskWp.Task;
import clj.TskWp.Workspace;
private ConcurrentMap<String, Task> taskMap =
new ConcurrentHashMap<String, Task>();
private ConcurrentMap<UUID, Workspace> wpMap =
new ConcurrentHashMap<UUID, Workspace>();
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();
public void addTasks( UUID id, String tid ) throws IllegalStateException
{
// have to synchronize externally because of closeWorkspace() ?
readLock.lock(); // <<<<<<<<<<< necessary ?
try {
Workspace wp = wpMap.get( id );
if( wp != null ) {
taskMap.putIfAbsent( tid, new Task( tid ) );
Task t = taskMap.get( tid );
wp.addTask( t );
}
}
finally {
readLock.unlock();
}
};
public void closeWorkspace( UUID id )
{
writeLock.lock(); // <<<<<<<<<<< necessary ?
try {
Workspace wp = wpMap.remove( id );
if( wp != null ) {
wp.removeTasks();
}
// remove unassigned tasks from global map (across workspaces)
for( Task t : taskMap.values() ) {
if( t.getWorkspace() == null ) {
taskMap.remove( t.getId() );
}
}
}
finally {
writeLock.unlock();
}
};