Given sets A, B, C with a parent-child (one to many) relationship between A and B, and B and C.

There are concurrent attempts to modify the data. Each concurrent modification has access to (a1, a2) in (A, A) different from all other modification attempts and a1 != a2. Each concurrent modification may change the parent of B* = children(a1) U children(a2) to a1 or a2. And the children(b1), for any b1 in B*, to any b2 in B*.

Is the following locking strategy correct with this definition? Is there any interleaving order I may have missed that leads to incorrect behaviour?

select (c1, c2) in (C, C), where c1 != c2:
a1 = parent(parent(c1))
a2 = parent(parent(c2))

if try_lock(a1):
    if parent(parent(c1)) is a1:    <-- Reasoning below about this
        if try_lock(a2):
            if (parent(parent(c2)) is a2:
                do a modification on (a1, a2)

My reason on that no locks are needed on items in B or C:

Any attempt at modification of parent(parent(c1)) needs to have a lock on both the pre- and post- modified value. We currently have a lock on 'a1'. Thus no other modification attempt can change parent(parent(c1)) to or from a1. So if we get that parent(parent(c1)) is a1 it cannot be changed to or from that value by another thread since the moment we got the lock on a1.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.