7

我一直在关注一些无锁代码的正确性，我非常感谢我能得到的任何输入。我的问题是关于如何在 C++11 的内存模型中使用获取和释放语义来实现一些所需的线程间同步。在我的问题之前，一些背景......

在MVCC中，写入者可以安装对象的新版本，而不会影响旧对象版本的读取者。但是，如果当具有较高时间戳的读取器已经获得对旧版本的引用时，写入器安装了对象的新版本，则写入器事务将不得不回滚并重试。这是为了保持可序列化的快照隔离（所以就好像所有成功的事务都按时间戳顺序一个接一个地执行）。读者永远不必因为写入而重试，但如果他们的活动将“从下面拉出地毯”具有更高编号的时间戳的读者，他们可能不得不回滚并重试。为了实现这个约束，一个读时间戳用来。这个想法是读取器在获取引用之前将对象的读取时间戳更新为自己的时间戳，写入器将检查读取时间戳以查看是否可以继续使用该对象的新版本。

假设有两个事务：T1（写入者）和 T2（读取者）在不同的线程中运行。

T1（作者）这样做：

void
DataStore::update(CachedObject* oldObject, CachedObject* newObject)
{
    .
    .
    .
    COcontainer* container = oldObject->parent();
    tid_t newTID = newObject->revision();
    container->setObject(newObject);
    tid_t* rrp = &container->readRevision;
    tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
    while (true)
    {
        if (rr > newTID) throw TransactionRetryEx();
        if (__atomic_compare_exchange_n(
            rrp,
            &rr,
            rr,
            false,
            __ATOMIC_RELEASE,
            __ATOMIC_RELAXED)
        {
            break;
        }
    }
}

T2（读者）这样做：

CachedObject*
Transaction::onRead(CachedObject* object)
{
    tid_t tid = Transaction::mine()->tid();
    COcontainer* container = object->parent();
    tid_t* rrp = &container->readRevision;
    tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
    while (rr < tid)
    {
        if (__atomic_compare_exchange_n(
            rrp,
            &rr,
            tid,
            false,
            __ATOMIC_ACQUIRE,
            __ATOMIC_ACQUIRE))
        {
            break;
        }
    }
    // follow the chain of objects to find the newest one this transaction can use
    object = object->newest();
    // caller can use object now
    return object;
}

这是我担心的情况的简单总结：

     A    B    C
<----*----*----*---->
   timestamp order

A: old object's timestamp
B: new object's timestamp (T1's timestamp)
C: "future" reader's timestamp (T2's timestamp)

* If T2@C reads object@A, T1@B must be rolled back.

如果 T1 在 T2 开始之前完全执行（并且 T1 的效果对 T2 完全可见），那么就没有问题。T2 将获取对 T1 安装的对象版本的引用，它可以使用它，因为 T1 的时间戳小于 T2 的。（事务可以“从过去”读取对象，但不能“窥探未来”）。

如果 T2 在 T1 开始之前完全执行（并且 T2 的效果对 T1 完全可见），那么就没有问题。T1 将看到“来自未来”的事务可能读取了对象的旧版本。因此，T1 将被回滚并创建一个新事务来重试工作的性能。

问题（当然）是在 T1 和 T2 同时运行时保证正确的行为。只使用互斥锁来消除竞争条件非常简单，但如果我确信没有其他方法，我只会接受带锁的解决方案。我很确定应该可以使用 C++11 的获取和释放内存模型来做到这一点。我可以接受一些复杂性，只要我对代码正确感到满意。我真的希望读者尽可能快地运行，这是 MVCC 的主要卖点。

问题：

1.throw TransactionRetryEx()看上面的（部分）代码，你认为是否存在竞争条件，以至于在 T2 继续使用旧版本的对象的情况下，T1 可能无法回滚（通过）？

2.如果代码错误，请解释原因，并提供纠正错误的一般指导。

3.即使代码看起来正确，你能看到它如何更高效吗？

我的理由DataStore::update()是，如果调用__atomic_compare_exchange_n()成功，则意味着“冲突”读取器线程尚未更新读取时间戳，因此它也没有遍历对象版本链以找到新的可访问版本刚刚安装。

我正要买《事务信息系统：理论、算法和并发控制与恢复的实践》这本书，但我想我也会打扰你：我想我应该早点买这本书，但我我也相当确定我不会学到任何会使我的大部分工作无效的东西。

我希望我已经提供了足够的信息以使答案成为可能。如果我收到建设性的批评，我会很乐意编辑我的问题以使其更清楚。如果已经提出并回答了这个问题（或类似的问题），那就太好了。

谢谢！

4

1 回答 1

1

这很复杂，我还不能对 1. 和 2. 说什么，但是关于 3 我注意到了一些事情：

当 __atomic_compare_exchange_n 返回 false 时，*rrp 的当前值被写入 rr，因此循环中的 __atomic_load()s 都是冗余的（在 T2 中只需将其丢弃，在 T1 中像在 T2 中一样在循环之前执行一次）。

作为一般评论，在算法中的其他所有内容完成之前，可能没有必要考虑获取/释放；然后您可以检查“无处不在”需要多强的内存屏障。

于 2012-09-23T11:55:24.883 回答