阅读完这两份文档后你现在可以理解示例中的内容了。这是我们仓库中的一个栈实现示例。在本视频的剩余部分我们假设你已经阅读了 Aaron 的文档和特性文档。现在我们将再次阅读并发栈、队列和链表的实现看看在垃圾回收方面发生了什么。栈实现分析这是一个栈的实现它本质上是一个节点链表。入栈操作在push操作中不需要考虑垃圾回收因为我们没有从链表中移除任何节点也没有释放任何内存。我们只是创建一个新节点然后将其添加到链表的头部。这里仍然有一个关于crossbeam-epoch的有趣方面。你创建了一个Owned指针这基本上是在堆上创建了一个对象但它完全由我自己独占拥有其他线程完全不共享。这就是为什么这种类型被称为Owned。它是一个指向堆的独占指针。我们尝试对头指针执行一个compare_and_set操作。我们将头指针从原始指针替换为新创建的节点。有趣的是这个新创建的指针的所有权被转移给了这个函数。这个函数接收并获得了新指针的所有权。如果这个compare_and_set操作成功那么我们就完成了。如果操作不成功有趣的是你刚刚传入的指针的所有权会被返回。因此为了在下一次循环迭代中使用这个新指针你需要将这个所有权保存到用于保存新指针所有权的变量中。请记住指向堆对象的所有权是在这里通过实际在堆上分配对象而创建的。这个所有权被转移到这里当compare_and_set操作不成功时它会被返回。如果操作成功那么所有权实际上被转移到了共享内存中。因此你不需要再关心这个对象的所有权。出栈操作有趣的事情将发生在pop函数中。在pop函数中你将读取一些指针最后对头指针执行一个compare_and_set操作。你将头指针替换为下一个指针。这有效地从链表中移除或分离了原始头指针。因此我们希望释放这个节点。但正如我们在上一个视频中讨论的我们不能不加考虑地这样做。我们需要“退休”这个节点而不是立即释放它。这里的“延迟销毁”基本上是“退休”的同义词。我们使用Guard来延迟销毁这个节点。这基本上是我们对上一个视频中的示例所做的第二个主要更改。我说过我们需要界定线程访问共享内存的代码范围这个范围由pin函数和此处guard的析构来界定。因此有效地说当你在此处pin这个guard时活动状态开始。活动状态在此guard被释放时结束可能是在这一行guard被丢弃。当guard被丢弃时活动状态自动结束。你可以将这个 API 视为围绕set_active和set_inactive函数的包装器它保证一旦创建了活动状态它必须在之后的某个时间点被停用。这基本上是一个围绕set_active和set_inactive函数的 RAII 类型包装器。这里有趣的是这个retire函数是guard的一个方法。因此这个defer_destroy必须在活动状态内部调用因为它是guard的一个方法而guard只存在于活动状态内部这要归功于这个guard的 RAII 类型 API。所以这里是活动状态。这个guard证明了我们在第 76 行处于活动状态因为我们有一个对guard的引用。这基本上确保了retire函数只在活动状态内部被调用。此外这些compare_and_set和load函数被赋予了一个对guard的引用这也证明了读取全局内存的操作只在活动状态内部执行这个事实由函数被赋予了一个指向guard的指针来保证这证明了我们处于活动状态内部。同样的事情也发生在这个push函数中。我的意思是我们在这里创建了一个guard。在这一点上我们不需要guard因为我们只是在堆中创建一个新节点并且没有访问共享内存。直到这里这个n节点完全由我自己独占拥有所以在创建这个新节点之前我们不需要pin这个guard。在此处pin了guard之后我们可以安全地读取指针因为它们受到基于 epoch 回收实现的有效保护。关于这个store函数有趣的是与load和compare_and_set不同它不接受guard参数因为我们没有主动创建对共享内存的新引用。因此当执行store时我们不需要被赋予一个guard。如果你在这里有一个头指针并且这个头指针有效地用guard的作用域即活动状态的持续时间进行了标注这证明了store函数是在活动状态内部执行的。这就是为什么我们不需要特别要求额外的guard引用参数。到目前为止在较高层次上push和pop函数需要做一些与垃圾回收相关的事情那就是用guard保护代码行guard限定了活动状态的开始和结束。它也是使用guard来限定活动状态的开始和结束。此外我们不是立即释放头指针而是在此时延迟销毁或退休头指针。这些是与没有垃圾回收的朴素栈算法以及带有基于 epoch 回收的朴素栈算法的区别。现在我们可以看到除了解释几种类型外这就是我需要使用这个栈来讨论的所有内容。Stack是一个指向Node的Atomic指针而Node包含一个指向下一个节点的Atomic指针。因此Atomic基本上是一种可以被并发访问的类型。这是可以被多个线程并发访问的指针值。这就是Atomic的目的。它与Owned不同因为Owned是独占指针没有其他人访问这个指针。这就是为什么我们在这一行代码中创建一个新的堆对象。此外还有另一种不同类型的指针即Shared。这个head是load函数的结果这个head的类型必须是Shared。Shared指针基本上是对全局内存的引用。你可以认为这个本地指针Shared是线程本地的。当一个线程从全局内存读取指针时该指针会临时存储在栈中而Shared就是用来保存指向全局内存的指针的。因此有三种类型的指针可以被并发访问的Atomic指向堆对象的独占指针Owned以及临时保存指向全局内存的指针的Shared指针。这个 API 的设计方式使得你很难破坏 epoch 回收的规则。你可以通过阅读我在本视频开头展示的两份文档来看到这一点。队列实现分析现在让我们继续看队列。队列比栈稍微复杂一点。但在垃圾回收方面它们与栈并没有太大不同。入队操作push函数也创建一个Owned指针并立即将其转换为Owned指针。它通过在此处传递guard来访问共享内存。guard作为引用被给出。因此你可以相当确定这个push函数是在活动状态内部执行的。因此你可以安全地将临时指针加载到栈中。作为这个load的结果你可以得到一个Shared指针它临时保存着指向并发内存的指针。这意味着所有对并发内存的访问都是在活动状态内部执行的。到目前为止一切顺利。和往常一样push在分配方面不是很有趣因为push函数不释放任何东西。出队操作另一方面这个pop函数有点不同。它做同样的事情。它被赋予一个guard这证明了这个pop函数是在活动状态内部执行的并且使用这个guard它可以加载并发内存指针以便遍历到下一个指针。首先一切顺利。有趣的是这里也一样。如果你成功更新了头指针你实际上从队列中分离了第一个节点。因此你需要在某个时间点释放它。我们不是立即释放指针而是打算延迟销毁或退休这个指针以等待其他线程完成对同一节点的访问。在调用defer_destroy之后我们读取指针的值并在此处返回值。这基本上就是栈中发生的情况在垃圾回收方面与栈非常相似。你用guard保护函数这证明函数是在活动状态内部执行的。此外你延迟销毁或退休块而不是立即释放它。道理相同。Drop 实现这里有一点有趣的事情。在drop函数中你试图弹出值直到队列为空。这个函数必须在活动状态内部调用。因此我们将给它一个guard但这个guard是一个“不受保护的”guard意味着即使你有一个guard你实际上并不在活动状态内部。但这实际上是正确的实现。乍一看可能看起来是错误的但实际上是正确的因为在队列被释放和drop函数被调用时你可以完全确定只有你知道这个队列。没有其他线程试图访问这个队列因为他们丢失了对这个队列的所有引用。这就是为什么可以调用队列的drop函数。因此你是唯一访问这个队列内部节点的人。因此你根本不需要保护你的访问。这就是为什么我们要调用unprotected而不是pin这个unprotected函数意味着你实际上并不在活动状态内部但我仍然会给你一个guard因为你需要它。但由于这个drop函数的独占性质它仍然是安全的。链表实现分析链表也是一样的。你被赋予一个guard。和往常一样在drop函数中你不需要一个表示活动状态的真正的guard。这里你有很多事情要做。同样的事情发生在迭代开始时你需要通过pin来获取一个guard因为你需要保护你的遍历。在遍历结束时你需要丢弃guard以标记活动状态的结束或活动状态的结束。代码的其余部分也发生同样的事情。对于作业 5你需要实现一些数据结构这些数据结构共同实现了一个并发哈希表。我希望你现在明白如何做到这一点如何在并发哈希表内部保护内存的释放。当你开始访问并发内存时你通过pin创建一个guard。在你完成对共享内存的访问后你丢弃guard这实际上调用了set_inactive函数。只有在这些活动状态内部你才能安全地解引用或引用共享内存。如果你想释放一个节点那么你不是立即释放它而是需要在活动状态内部延迟销毁或退休相关的块。这基本上就是使用基于 epoch 的回收来保护数据结构的较高级别方法。我希望你现在已经很好地理解了如何为并发哈希表做到这一点。https://github.com/OpenDocCN/cs-notes-pt3-zh/raw/master/docs/kaist-cs431-rs-prll-prog/img/c499629267ab2b3e1c0100101e558d91_5.png总结本节课中我们一起学习了crossbeam-epoch库的核心概念和使用方法。我们了解到该库通过Guard、Pin、Owned和Shared等类型强制程序员在安全的边界内进行并发内存访问和回收。关键点包括使用pin()进入活动状态并获取Guard在Guard的作用域内安全地访问共享指针使用defer_destroy或retire来延迟释放内存而不是立即free以及理解Atomic、Owned、Shared三种指针类型的区别和用途。掌握这些模式是使用crossbeam-epoch构建正确、安全的并发数据结构的基础。