为了账号安全,请及时绑定邮箱和手机立即绑定

仅使用本地锁从BST中进行多线程删除

仅使用本地锁从BST中进行多线程删除

拉莫斯之舞 2021-04-07 21:18:30
在用Java编写BST的多线程实现时,我遇到了以下问题。该BST不应使用全局锁定,而应尽可能少地锁定,仅锁定要更改的节点(添加和删除命令)。因此,其他线程只要不尝试更改与您相同的节点,就可以在树中处于活动状态。我找不到一种方法来删除具有2个子节点的节点。普通算法说要找到要删除的节点的顺序后继者,以将其放置在已删除的节点的位置,然后再删除已复制的节点。但这可能会在这两个节点之间的线程中产生问题,并且需要复制的节点,在传输之后,即使该线程在树中,该线程也不会找到所请求的节点。看一下下面的示例:正在执行Tread 1remove(5)。它找到下一个键(6)并将其复制到该节点,然后从副本中删除该节点。但是同时,另一个执行contains(6)命令的线程正在节点8上等待,执行节点号6之后将不再位于其路径中,即使6节点仍在树中,它也会返回错误的结果。删除命令之前的状态示意图(蓝色箭头指示第二个线程在何处。删除命令后的状态示意图(蓝色箭头指示第二个线程在何处。 如何在不锁定整个树的情况下克服此问题?
查看完整描述

4 回答

?
哈士奇WWW

TA贡献1799条经验 获得超6个赞

我使用的解决方案是为BST提供一个版本号,并且每次remove有两个子节点的节点需要a时,我都会在删除重复的节点之前增加版本号。

然后,每个操作在开始之前都会检查版本号,如果我得到一个表明未找到密钥的结果,我会检查版本号是否仍然相同,如果不相同,请重试该操作。

这表示:

  • 对于removecontains-如果操作失败(这意味着,关键是没有找到)和版本改变了,再试一次。

  • 对于insert-我检查版本号,而不是在操作结束时检查,而是在我处于一片叶子时以及在创建和添加新节点之前检查版本号。如果要添加一个新节点,这意味着我没有找到带有该键的节点,我想确保在更改键并创建新叶子之前,键确实不在树中,以防止出现以下情况:一个双键将被添加到树中,然后我需要通过删除节点来重做此操作。


查看完整回答
反对 回复 2021-04-14
  • 4 回答
  • 0 关注
  • 119 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信