以原子方式交换两个指针的值

Question

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

有没有办法以value原子方式交换两个指针，避免竞争条件和死锁。

我首先想出了“解决方案”，假设两个指针都有：

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

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将永远阻塞，从而导致死锁。

---

我可以考虑避免死锁的解决方案之一是为它们分配一个“组”，只有同一组中的项目才能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
}