假设我们有资源 A、B、C 及其依赖非循环:
B->A
C->A
意味着 B 强烈依赖于 A,C 强烈依赖于 A。例如:B,C 是 A 的预计算资源。因此,如果 A 更新,B,C 也应该更新。但是如果 B 更新了——除了 B 什么都没有改变。
对于问题:考虑到可以访问图的每个节点以进行Read 或Write 或Read/Upgrade to Write以多线程方式,应该如何管理此类图中的锁?这个问题有泛化吗?
更新
抱歉,问题不明确。这里还有一件非常重要的事情: 例如,如果 A 更改并强制更新 B、C,这意味着 B 及其依赖项更新的那一刻 - 它将释放写锁。
最佳答案
您的问题是事务 - 锁定 - 并发 - 冲突解决的混合体。因此,关系数据库中使用的模型可能会满足您的目的。
为concurrency control定义了很多方法.
在您的情况下,某些可能适用,具体取决于您的算法需要多乐观或悲观、读取或写入的次数以及每个事务的数据量是多少。
我能想到两种对您的情况有帮助的方法:
<强>1。 Strict Two-Phase Locking (SSPL or S2PL)
一个事务开始,A
、B
、C
锁正在获取中,并一直保持到事务结束。因为多个锁一直保留到事务结束,在获取锁时可能会遇到死锁情况。锁可以在交易期间更改。
这种方法是可序列化的,这意味着所有事件都按顺序发生,并且在事务保持期间任何其他方都不能进行任何更改。
这种方法是悲观的,锁可能会持有很长时间,因此会消耗资源和时间。
<强>2。 Multiversion
与其锁定 A
、B
、C
,不如维护版本号并为每个版本创建快照。所有更改都将对快照进行。最后,所有快照将替换以前的版本。如果 A
、B
和 C
的任何版本发生更改,则会发生错误情况并丢弃更改。
这种方法不放置读锁或写锁,这意味着速度会很快。但在发生冲突的情况下,如果任何版本在此期间发生更改,则数据将被丢弃。
这是乐观的,但可能会花费更多的资源来支持速度。
在数据库系统中还有“事务日志”的概念。这意味着任何正在完成或未决的交易都将出现在“交易日志”中。因此,在上述任何方法中完成的每个操作都首先对事务日志进行。日志中的操作将在适当的时候在主存储中具体化。如果出现故障,将分析日志,将已完成的事务具体化到主存储,并丢弃待处理的事务。
这也用于 "log shipping"为了将日志发送到其他服务器以进行复制。
已知实现
有多个内存数据库可以避免在实现您自己的解决方案时出现一些麻烦。
H2还提供可以匹配您的用例的可序列化隔离级别。
go-memdb提供多版本并发。这个使用 immutable radix tree algorithm ,因此,如果您正在寻找构建自己的解决方案,也可以查看此内容以了解详细信息。
更多的定义here .
关于multithreading - 是否有一些用于 R/W 锁图的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43932380/