原子地交换两个指针的值

Question

我了解到信号量可以充当原子锁，可以执行两个功能：down 和 up。

有什么办法可以原子地交换两个指针的value，避免竞争条件和死锁。

我首先想出了 'solution'，假设两个指针都有：

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
}

但是如果我没记错的话，如果使用相同的指针调用两个 atomic_swap 会导致死锁：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);

在上面的代码中，如果对 atomic_swap 的调用同时到达第一个 down，则下一个 down 将永远阻塞，从而导致死锁。

我能想到的避免死锁的解决方案之一是为它们分配一个'group'，只有同一组中的项目才能安全地执行atomic_swap（没有死锁）：

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

但这当然需要每个项目都携带一个group，并且不相关的项目可能会因为其他调用而等待该组。

理论上使用信号量执行atomic_swap有什么好的方法吗？

Answer 1

您可以使用std::less比较指针以确保所有用户以相同的顺序获取锁：

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
}

原子地交换两个指针的值

Swap the value of two pointers atomically

c++

multithreading

mutex

semaphore

race-condition