问题标签 [transactional-memory]

背景

在回答一个问题时，我构建并上传了一个 bounded-tchan（我不适合上传jnb 的版本）。如果名称不够，则有界 tchan (BTChan) 是具有最大容量的 STM 通道（如果通道处于容量状态，则写入块）。

最近，我收到了一个请求，要求添加一个像常规 TChan一样的 dup 功能。问题就这样开始了。

BTChan 的外观

下面是 BTChan 的简化（实际上是非功能性的）视图。

每次您写入频道时，您都会nrDups在元组中包含重复次数 ( ) - 这是一个“单个元素计数器”，表示有多少读者获得了该元素。

每个阅读器都会减少它读取的元素的计数器，然后将它的读取指针移动到列表中的下一个元素。如果阅读器将计数器减至零，则 的值count会减少以正确反映通道上的可用容量。

要明确所需的语义：通道容量表示通道中排队的最大元素数。任何给定的元素都会排队，直到每个 dup 的读取器接收到该元素。任何元素都不应为 GCed dup 排队（这是主要问题）。

例如，让容量为 2 的通道 (c1, c2, c3) 有 3 个 dup，其中 2 个项目被写入通道，然后所有项目都从c1和中读出c2。通道仍然是满的（0 剩余容量），因为c3没有消耗它的副本。在任何时候，如果所有对的引用c3都被删除（c3GCed 也是如此），那么容量应该被释放（在这种情况下恢复为 2）。

这是问题所在： 假设我有以下代码

导致 BTChan 看起来像：

注意最后的读取计数"hello"仍然是1？这意味着消息不会被视为消失（即使它会在实际实现中被 GC），并且我们count永远不会递减。因为通道处于容量状态（最多 1 个元素），所以写入器将始终阻塞。

我希望每次dupBTChan调用时都创建一个终结器。当收集到复制（或原始）通道时，该通道上剩余要读取的所有元素将减少每个元素的计数，nrDups变量也将减少。结果，未来的写入将具有正确count的（count不为 GCed 通道未读取的变量保留空间）。

解决方案 1 - 手动资源管理（我想避免的）

由于这个原因，JNB 的 bounded-tchan 实际上有手动资源管理。见cancelBTChan。我要让用户更难出错（并不是说手动管理在许多情况下不是正确的方法）。

解决方案 2 - 通过阻止 TVar 使用异常（GHC 无法按照我的意愿执行此操作）

编辑这个解决方案，解决方案 3 只是一个衍生产品，不起作用！由于错误 5055 (WONTFIX)，GHC 编译器向两个阻塞线程发送异常，即使一个就足够了（理论上可以确定，但对于 GHC GC 不实用）。

如果获取 a 的所有方法BTChan都是 IO，我们可以forkIO使用一个线程来读取/重试给定的唯一的额外（虚拟）TVar 字段BTChan。当所有其他对 TVar 的引用都被删除时，新线程将捕获异常，因此它将知道何时递减nrDups单个元素计数器。这应该可行，但会强制我所有的用户使用 IO 来获取他们BTChan的 s：

编辑：是的，这是一个糟糕的 man 终结器，我没有任何特别的理由避免使用addFinalizer. 那将是相同的解决方案，仍然强制使用 IO afaict。

解决方案 3：比解决方案 2 更简洁的 API，但 GHC 仍然不支持

用户通过调用启动管理器线程initBTChanCollector，它将监视一组这些虚拟 TVar（来自解决方案 2）并进行所需的清理。unsafePerformIO基本上，它将 IO 推入另一个线程，该线程通过全局 ( ed)知道该做什么TVar。事情基本上像解决方案 2 一样工作，但 BTChan 的创建仍然可以是 STM。运行失败initBTChanCollector将导致进程运行时任务列表不断增长（空间泄漏）。

解决方案 4：永远不允许丢弃BTChans

这类似于忽略问题。如果用户从不丢弃重复项BTChan，那么问题就会消失。

解决方案 5 我看到了 ezyang 的回答（完全有效和赞赏），但真的很想保留当前的 ​​API 只是一个 'dup' 函数。

** 解决方案 6** 请告诉我有更好的选择。

编辑：我实现了解决方案 3（完全未经测试的 alpha 版本）并通过将全局本身设为 a 来处理潜在的空间泄漏BTChan- chan 的容量可能应该为 1，因此忘记运行会init很快出现，但这是一个很小的变化。这在 GHCi (7.0.3) 中有效，但这似乎是偶然的。GHC 向两个被阻塞的线程（读取 BTChan 和观察线程的有效线程）抛出异常，所以如果你在另一个线程丢弃它的引用时被阻止读取 BTChan，那么你就会死。

总是被提及的软件事务内存的主要优点之一是可组合性和模块化。可以组合不同的片段以产生更大的组件。在基于锁的程序中，通常情况并非如此。

我正在寻找一个用实际代码说明这一点的简单示例。我更喜欢 Clojure 中的一个例子，但 Haskell 也很好。如果该示例还展示了一些不易编写的基于锁的代码，则可以加分。

我有两个 MVar（以及一个 MVar 和一个 Chan）。我需要从 Chan 中取出东西并处理它们，直到另一个 MVar 不再为空。我的理想解决方案类似于 UNIXselect函数，我传入一个（可能是空的）MVar 列表，线程阻塞直到其中一个已满，然后它返回完整的 MVar。尽我所能尝试，除了用 isEmptyMVar 反复轮询每个 MVar 直到我得到错误之外，我想不出任何办法。这似乎效率低下。

一个不同的想法是使用 throwTo，但它会中断线程中发生的一切，我需要以原子方式完成处理 Chan 的工作。

我输入的最后一个想法是为每个尝试读取其 MVar 的 MVar 创建一个新的 forkIO，然后用它自己的实例填充一个新创建的 MVar。然后原始线程可以在该 MVar 上阻塞。Haskell 线程是否足够便宜，可以运行那么多线程？

我很困惑，因为从阅读 wiki 页面来看，似乎只有一个用于加载和存储的 checkValidate 和提交系统。目的是解决同步问题吗？它是建立在当前硬件之上的软件编程，还是通过 ISA 实现的硬件？每个（硬件/软件）实现之间有什么区别？

谢谢。

我想在 JAVA 中实现 `pi-calculus。对于并发，我使用Deuce STM library。更改 JAVA 语法会很困难，因此我计划使用带注释的变量和通用函数/类。

例如。

所以一个通道将是这个类的一个实例。

我对如何对流程进行建模以允许它们通过这些渠道进行交互感到困惑。

有什么帮助/建议吗？

谢谢你。

在阅读Anandtech 关于“Haswell TSX”（事务性内存屏障）后，我立即想知道 CLR/JVM 是否能够在 C#/Java/Scala/F# 中将这些用于高度并行的应用程序（C# Rx/TPL/TFD）。

作为对 JVM STM 框架的一些分析的一部分，我正在考虑重新设计一个开源库的锁定机制以改用 STM。然后我会运行一些测试来比较性能、编码的易用性等。

显然，性能测试必须支持 STM 的乐观锁定，但可以在以后解决它的语义。

但是，就目前而言，我只对开源库候选者感兴趣。想到的一个是 EhCache，因为它具有内部锁定措施。

还有哪些合适的候选人？

我目前正在使用较新的 Intel Haswell 芯片上可用的 Intel TSX（事务同步扩展），并且我一直在考虑如何正确地在不同线程之间进行信号传递。我尝试使用 pthread 的条件变量，而事务只是不断中止，这是可以理解的。也就是说，如果当前线程在事务中，是否有人知道任何有效的方法来通知另一个线程唤醒？

我目前正试图解决使用 C++ STL 容器的线程安全问题。我最近尝试通过使用 std::mutex 作为成员变量来实现线程安全的 std::vector，然后才意识到虽然我可以通过锁定锁使成员函数成为线程安全的，但我无法使 lib 函数像 std::sort 线程安全，因为它们只获得 begin()/end() 迭代器，这是一般 STL 中容器和算法之间基本分离的结果。

所以我想，如果我不能使用锁，软件事务内存（STM）怎么样？

所以现在我坚持这个：

我编译的是：

使用 g++ 4.8.2，这给了我以下错误：

我有点明白了，因为 push_back 或 sort 或任何未声明 transaction_safe 的东西，但这给我留下了以下问题：

a) 我该如何解决这个错误？

b) 如果我无法修复该错误，那么这些事务块通常用于什么？

c) 如何实现无锁线程安全向量？！

提前致谢！

编辑： 感谢到目前为止的答案，但他们并没有真正抓到我的痒。让我举个例子：假设我有一个全局向量，并且对这个向量的访问应该在多个线程之间共享。所有线程都尝试进行排序插入，因此它们生成一个随机数并尝试以排序方式将此数字插入向量中，因此向量始终保持排序状态（包括 c 的重复项）。为了进行排序插入，他们使用 std::lower_bound 来查找要插入的“索引”，然后使用 vector.insert() 进行插入。

如果我为包含 std::mutex 作为成员的 std::vector 编写包装器，那么我可以编写包装器函数，例如使用 std::lock_guard 锁定互斥锁然后执行实际 std::vector 的插入。插入（）调用。但是 std::lower_bound 并不关心成员互斥锁。这是一个功能，而不是一个错误 afaik。

这使我的线程陷入困境，因为其他线程可以在某人做他的 lower_bound 事情时更改向量。

我能想到的唯一解决方法是：忘记包装器并为向量设置一个全局互斥锁。每当有人想对这个向量做任何事情时，他都需要那个锁。

那就是问题所在。使用此全局互斥锁有哪些替代方法。这就是软件事务内存浮现在脑海中的地方。

那么现在：如何在 STL 容器上使用 STM？（和a），b），c）从上面）。

我想在 Fortran（最好是 gFortran）中使用事务内存。我认为可以通过在 C 函数中使用事务内存并从 Fortran 调用它来解决此问题，但我更愿意直接在 Fortran 中执行此操作（如果可能的话）。

我发现的唯一相关信息是关于Blue Gene 的 IBM 编译器中的实现，但是我没有使用 Blue Gene。