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

Question

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

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

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

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

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

理论上有什么好的方法可以使用信号量执行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
}