[concurrency-interest] transferring queued threads

Christian Vest Hansen karmazilla at gmail.com
Mon Apr 6 15:00:07 EDT 2009


Have a lock for each entity; L(A), L(B), L(C) etc. such that each
entity at any given point in time has exactly one lock. These locks
have a universal and immutable ordering to them (like
System.identityHashCode, for instance).

Now, whenever you want to assoc A and B, you start by acquirering L(A)
and L(B) in accord to their universal order. When another thread comes
to assoc B and C, then the first thread will either 1) have gotten
L(B) and so this thread must wait, or 2) get L(B) and then L(C),
causing the first thread to wait on L(B) until this thread is finished
with B and C.

This universal order will prevent lock-ordering dead-locks, while
allowing any thread to reach for any combination of locks.

On Mon, Apr 6, 2009 at 5:55 PM, tom strickland
<mr.tom.strickland at gmail.com> wrote:
> Instances of what? The entities? It seems to me that the problem is that
> [what I need to be queuing on] changes over time. I can't queue on
> individual entities: when A and B are associated, then I would like to queue
> triggers for A and B on the same lock... until they are not associated any
> more.
> Of course, I might have misunderstood your point!
>
> Tom
>
> 2009/4/6 Christian Vest Hansen <karmazilla at gmail.com>
>>
>> Can't you synchronize on the instances individually in the order of
>> their System.identityHashCode?
>
>> On Mon, Apr 6, 2009 at 5:09 PM, tom strickland
>> <mr.tom.strickland at gmail.com> wrote:
>> > I have an interesting locking scenario and I'd appreciate some help
>> > getting
>> > my head around it. I'm sorry if I've made it a little abstract, but
>> > hopefully this will come across clearly.
>> >
>> >
>> > I have some entities (A, B, C, D, E...) that can be associated in pairs.
>> > When 2 entities are associated, only one thread may process them at a
>> > time:
>> > if A and B are associated and a thread has come in for A, then any
>> > threads
>> > coming in for B will be blocked until A's thread has completed. This
>> > seems
>> > to imply a simple lock, shared by A and B, that can be acquired and
>> > released.
>> >
>> > The problem comes when I want to dissociate A and B in order to
>> > associate B
>> > with C. Once B is associated with C, triggers coming in for B should
>> > queue
>> > on a lock shared between B and C, and triggers coming in for A should
>> > use a
>> > separate lock (perhaps the original lock).
>> >
>> > How might this be achieved?
>> > My initial thoughts are that I should use wait... notify and a stored
>> > value
>> > that tells a thread which lock it should be waiting for. At any time, a
>> > running thread can look at this value to see which lock it should
>> > acquire.
>> > If a lock has threads queued up for A and B and we need to split B's
>> > threads
>> > out and queue them on a different lock:
>> >
>> > 1. create a new lock for B
>> > 2. acquire the new lock (in order to prevent races)
>> > 3. change the lock-id field for B to point to the new lock
>> > 4. wake the waiting threads
>> > 5. A woken thread will check whether it has been woken because:
>> >    a. it has acquired the lock - nothing to do here, the lock is
>> > acquired,
>> > proceed as normal.
>> >    b. the lock that it should be waiting for has changed - wait on the
>> > new
>> > lock
>> > 6. do stuff with B and C
>> > 7. release the lock acquired in step 2
>> >
>> >
>> > Does this make sense? I have more questions, mainly about how to
>> > implement
>> > and encapsulate this, but I'd like to start by making sure that I've
>> > understood and explained the problem clearly.
>> >
>> >
>> > Thanks,
>> >
>> > Tom
>> >
>> > _______________________________________________
>> > Concurrency-interest mailing list
>> > Concurrency-interest at cs.oswego.edu
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>> >
>> >
>>
>>
>>
>> --
>> Venlig hilsen / Kind regards,
>> Christian Vest Hansen.
>
>



-- 
Venlig hilsen / Kind regards,
Christian Vest Hansen.



More information about the Concurrency-interest mailing list