问题标签 [stm]

我一直在使用 Haskell 的 STM 库，我真的很喜欢编写事务的能力和 STM 的一般“你不能得到这个错误”的性质。

有充分的理由，STM 不允许事务中的 IO 操作。无法重试 IO 操作。（在此处插入发射导弹参考）。另一方面，数据库事务确实有一些非常相似的原子性保证。有没有一种可接受的方式将两者结合使用？

有以下版本的读写器问题：多个读写器，2 个或多个读者可以同时读取，如果一个作者在写，没有人可以读写，最好是所有作者都有平等的写作机会（对于例如在 100 轮中，5 位作者每人应该写大约 20 次）。使用 STM 在 Clojure 中实现此功能的正确方法是什么？我不是在寻找一个完整的代码，只是一些一般的方向。

check库中的Contol.Concurent.STM函数有 typeBool -> STM a并返回undefined成功而不是type有充分的理由Bool -> STM ()吗？它的实现方式类型检查器将编译一个以 结尾的 do 块，check foo仅在运行时以*** Exception: Prelude.undefined.

我一直在对 STM（软件事务内存）实现进行一些研究，特别是关于利用锁且不依赖于垃圾收集器的存在的算法，以保持与 C/C++ 等非托管语言的兼容性。我已经阅读了 Herlihy 和 Shavit 的“多处理器编程艺术”中的 STM 章节，并阅读了 Shavit 的几篇描述他的“事务锁定”和“事务锁定 II”的论文STM 实现。他们的基本方法是利用存储全局版本时钟和锁的值的哈希表来确定内存位置是否已被另一个线程的写入触及。据我了解该算法，当执行写入事务时，版本时钟被读取并存储在线程本地内存中，并且还在线程本地内存中创建读取集和写入集。然后执行以下步骤：

1. 读取的任何地址的值都存储在读取集中。这意味着事务检查正在读取的任何位置是否未锁定，并且它们等于或小于本地存储的版本时钟值。
2. 写入的任何地址的值与要写入这些位置的值一起存储在写入集中。
3. 一旦整个写入事务完成（这可能包括读取和写入多个位置），事务就会尝试使用哈希表中的锁锁定要写入的每个地址，该锁针对地址进行哈希处理' 价值。
4. 当所有的写集地址都被锁定时，全局版本时钟原子地递增并且新的递增值被本地存储。
5. 写入事务再次检查以确保读取集中的值没有用新的版本号更新或没有被另一个线程锁定。
6. write-transaction 使用它在步骤 #4 中存储的新值更新该内存位置的 version-stamp，并将 write-set 中的值提交到内存
7. 内存位置上的锁被释放

如果上述检查步骤中的任何一个失败（即步骤#1、#3 和#5），则写入事务被中止。

读取事务的过程要简单得多。根据 Shavit 的论文，我们简单地

1. 读取并在本地存储全局版本时钟值
2. 检查以确保内存位置的时钟值不大于当前存储的全局版本时钟值，并确保内存位置当前未锁定
3. 执行读取操作
4. 重复步骤 #2 进行验证

如果第 2 步或第 4 步失败，则中止读取事务。

不过，我似乎无法解决的问题是，当您尝试读取位于堆中的对象内的内存位置并且另一个线程调用delete指向该对象的指针时会发生什么？在 Shavit 的论文中，他们详细解释了如何不能对已回收或释放的内存位置进行写入，但似乎在读取事务内部，没有什么可以阻止可能的时序场景允许您从已被另一个线程释放的对象内部的内存位置读取。例如，考虑以下代码：

Thread A在原子读取事务中执行以下操作：linked_list_node* next_node = node->next;

Thread B执行以下操作：delete node;

由于next_node是线程局部变量，因此它不是事务对象。为它分配虽然的值所需的取消引用操作node->next实际上需要两次单独的读取。在这些读取之间，delete可以调用 on node，以便从成员next读取实际上是从已释放的内存段读取。node由于读取是乐观的，因此in指向的内存的释放Thread B不会被检测到 in Thread A。这不会导致可能的崩溃或分段错误吗？如果是这样，如果不锁定内存位置以供读取，如何避免这种情况（教科书和论文都表示这是不必要的）？

什么时候应该更喜欢 AkkaTransactionalMap而不是常规的不可变映射，SynchronizedMap反之亦然？（或者我在这里比较苹果和橙子？）

我在Data.Unique中注意到了这个成语：

是否保证只运行一次？

我是函数式编程和 Clojure 的新手，所以我不太确定在大学里为项目做什么。该项目应展示 Clojure STM 在银行交易中的优势（将资金从账户 A 转移到账户 B）。所以我打算这样进行：

1. 定义初始数据，如 Refs 矩阵或更好的东西
2. 生成随机操作来执行：[ random-account-source-id(0, N_MAX) , random-account-destination-id(0, N_MAX), random-money (0, 1000) ]
3. 将事务插入数据结构
4. 对于矩阵中的所有插入，将资金从源 ID 同步转移到目的地 ID，例如： /li>

那么，我不确定这一点，也许：

原来的问题

我是 STM 的新手。我想在 Haskell 中做的一件事涉及一大块数据，以及大量轻量级线程读取和写入所述大块数据的一小部分。读取和写入的位置基本上可以认为是随机的和小的。STM 似乎很适合这个，但我对如何解决这个问题有一些疑问。我看到了几种可能的方法，每种方法都有一些缺点，有些看起来很愚蠢。对这些或其他替代方案的一些评论将不胜感激。

为简单起见，我们假设大数据是 a Data.Vector a，其中元素本身很小。

1. 整条数据为一个TVar (Vector a)。我想这会导致大量数据的大量复制，因为 STM 会认为每个单独的写入都可能影响整个共享数据。当然，STM 识别出读取和写入非常本地化，并且不需要跨大数据的一致性的地方没有魔法？

2. 大量的TVar as，基本上每个元素一个，提供完全本地化的 STM，但基本上复制了整个Vector a. 这似乎很愚蠢。

3. 通过对数据进行分段，在 1 和 2 之间进行折衷，以便我有合理数量的TVar (Vector a)s 对应于数据的子向量。我觉得这个解决方案过于依赖启发式方法，比如分段应该有多大。

4. 消息传递。不是每个工作人员都使用 STM 读取和写入数据，而是每个工作人员都通过一些STM 机制（例如TChan. 一个特殊的线程接收这些消息，通过另一个线程传递请求的数据TChan，或者获取接收到的数据并将其写入共享数据结构。这个解决方案似乎没有困扰解决方案 1-3 的问题，但在我看来，它基本上放弃了使用 STM 的细节来保持数据一致。相反，它只是消息传递。当然，消息传递部分是用 STM 实现的，但我真正的问题是通过消息传递解决的。STM 看起来太棒了，消息传递太……嗯。

我是否正确地考虑了这一点？有人有任何提示或其他建议吗？

请记住，我没有使用 STM 的经验，也没有尝试过上述解决方案。我会从扶手椅上站起来，但有时在尝试任何事情之前考虑这些事情可能会很好。

附录：第五种方法来自 Nathan Howell，并使用TArray. 这听起来像我想要的，但文档说：

它目前以 Array ix (TVar e) 的形式实现，但将来可能会被更高效的实现所取代（但接口将保持不变）。

我认为这意味着这TArray只是我穿着更好衣服的方法 2。暗示“更有效”实现的文档很有趣，因为它暗示实际上存在更好的方法。

跟进 Vagif Verdi 的回答

Vagif Verdi 的回答很有趣，所以我做了一个小实验来尝试一下。我现在没有时间精简代码，因此对此感兴趣的人将不得不忍受我的代码，而不仅仅是包含基本要素。我决定使用 10^8Int的可变向量作为“大共享数据”，并让多个读取器/写入器对应于网络套接字上的线程。

请注意，代码甚至不读取或写入共享数据块。它就在那里，每个线程都有一个TVar。

那么会发生什么？我运行该程序，它立即占用了大约 780 MB 的 RAM，这是意料之中的（这大约是 10^8 Ints 所需要的）。现在，如果我使用 netcat 连接几个客户端并编写一些文本，程序只是应该打印出来，甚至不写入共享数据，那么进程的 CPU 使用率会在一秒以上的时间内飙升至 100% ！在显示文本之前有明显的延迟。从好的方面来说，内存使用量保持不变（根据 Vagif Verdi 的回答）。如果我删除向量和TVar，即取出所有 STM 和共享数据，一切都非常快速且响应迅速，并且每当客户端写入内容时都没有明显的 CPU 使用率。

因此，虽然很高兴看到共享数据实际上没有重复（尽管我想我应该实际写入共享数据以完全验证这一点），但维护一致状态会带来非常严重的性能损失。对我来说，我的问题仍然存在：如何在保持 STM 优点的同时正确解决这个问题？

感谢 Vagif Verdi 提出了一些非常有趣的观点。

在 Snap 源Snap.Internal.Http.Server.TimeoutManager

为什么会有 _morePlease 字段？
做什么_ <- tryPutMVar morePlease ()？

在一个网络应用程序中，我试图从一个有限的 id 池中生成一个唯一的线程安全 id。我面临的问题是在读取和写入另一个线程之间可能已经改变了数据结构；这就是为什么我不得不求助于compare-and-set!.

有没有一种更简单的方法来同步读取和写入，而不必“手动”执行 STM，也不会滥用字段sid-pool作为返回值swap!？