Swap the value of two pointers atomically

Question

I've learnt that semaphore can act as an atomic lock that can perform two function: down and up.

Is there any way, to swap the value of two pointers atomically, avoiding race condition and deadlock.

I first came up with the 'solution', suppose both pointers has :

Item a = { value = "A", lock = Semaphore(1) }
Item b = { value = "B", lock = Semaphore(1) }

void atomic_swap(Item* a, Item* b) {
    a->lock.down(); // acquire
    b->lock.down(); // acquire
    
    non_atomic_swap(&a.value, &b.value);

    b->lock.up(); // release
    a->lock.up(); // release
}

But if I am not wrong, it will result to deadlock if two atomic_swap is called using same pointers: eg.

Item a = ...;
Item b = ...;
thread_start(atomic_swap, {&a, &b}); // start a thread running atomic_swap(&a, &b);
thread_start(atomic_swap, {&b, &a}); // start a thread running atomic_swap(&b, &a);

On the code above, if both call to atomic_swap arrive the first down simultaneously, the next down will block forever, which results to deadlock.

---

One of the solution I can think about to avoid deadlock is assign a 'group' to them, only item in the same group can perform atomic_swap safely (without deadlock):

Group g = { lock = Semaphore(1) };
Item a = { value = "A", group = g };
Item b = { value = "B", group = g };

void atomic_swap(Item* a, Item* b) {
    // assume a->group == b->group

    a->group.down() // b->group.down()
    non_atomic_swap(&a.value, &b.value);
    a->group.up(); // b->group.up();
}

But this of course require every item to carry a group, and unrelated items might wait for the group because of other calls.

Is there any good way to perform the atomic_swap theoretically using semaphore?

Answer 1

You can use std::less to compare the pointers to ensure that all users acquire the locks in the same order:

void atomic_swap(Item* a, Item* b) {
    std::less<Item *> cmp;

    if (cmp(a, b)) {
        a->lock.down();
        b->lock.down();
    } else {
        b->lock.down();
        a->lock.down(); }
    
    non_atomic_swap(&a->value, &b->value);

    b->lock.up(); // release
    a->lock.up(); // release
}