Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #3954

Re: Concurrent bidirectional one-to-many map?

Show all headers | View raw

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();
   }
};

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-06 22:07 +0200
  Re: Concurrent bidirectional one-to-many map? markspace <-@.> - 2011-05-06 13:45 -0700
    Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-07 11:43 +0200
      Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-07 07:59 -0400
        Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-07 12:49 -0400
          Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-07 21:34 +0200
      Re: Concurrent bidirectional one-to-many map? Patricia Shanahan <pats@acm.org> - 2011-05-07 06:40 -0700
        Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-08 04:51 +0100
          Re: Concurrent bidirectional one-to-many map? Robert Klemme <shortcutter@googlemail.com> - 2011-05-09 06:43 -0700
            Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-09 18:28 +0100
              Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-09 22:57 +0200
                Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-09 18:36 -0400
                Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-10 08:34 +0100
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 10:09 +0200
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 10:51 +0200
                Re: Concurrent bidirectional one-to-many map? Robert Klemme <shortcutter@googlemail.com> - 2011-05-11 04:55 -0700
                Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-11 09:00 -0400
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 20:47 +0200
      Re: Concurrent bidirectional one-to-many map? markspace <-@.> - 2011-05-07 09:35 -0700
      Re: Concurrent bidirectional one-to-many map? Michal Kleczek <kleku75@gmail.com> - 2011-05-09 16:42 +0200
  Re: Concurrent bidirectional one-to-many map? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-07 03:46 -0700

csiph-web