草庐IT

c# - 尝试编写无锁单链表，删除麻烦

coder 2024-05-21 原文

我正在尝试编写一个无锁单向链表。最终一致性不是问题(有人遍历可能包含不正确项目的列表)。

我认为我正确地添加了项目(循环和 Interlocked.CompareExchange)。

但我不知道如何删除节点(列表中的任何位置)，因为我必须获取上一个项目并将其 Next 字段设置为当前节点 Next 字段。

class Node
{
    Node Next;
    object Value;
}

class SinglyLinkedList
{
    Root _root;

    public void Add(object value)
    {}

    public void Remove(object value)
    {}
}

即

a -> b -> c

到

a -> c

伪代码:

Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
  prev = node;
  node = node.Next;
}
prev.Next = node.Next;

我如何使它成为一个原子操作(即确保 prev.Next = node.Next 被调用而 next 或 prev 之间没有被另一个线程删除)？

我可以改用 ReaderWriterLockSlim，但我发现这个问题很有趣，因为我知道存在无锁链表。

我的顾虑:

如果当前线程在循环和赋值之间挂起，则会发生以下情况:

  • prev 本身可能已被另一个线程删除。
  • node 可能已被另一个线程删除。
  • Node.Next 可能已被删除

最佳答案

是的，添加是一个简单的两步循环，在前一个 .Next 指针上使用 CAS；但是移除很难!

实际上，如果不使用额外的信息和逻辑，您将无法做到这一点。

Harris 通过添加一个标记位创建了这个问题的解决方案，该标记位一旦设置就不允许任何人修改该节点。删除分为两步:首先(CAS)标记已删除的节点以防止任何人更改它(尤其是其 .Next 指针)；第二个 CAS 前一个节点。下一个指针，现在是安全的，因为另一个节点已被标记。

现在的问题是，在 C 中，Harris 使用 .Next 指针的两个最低有效位作为标记。这很聪明，因为对于 4 字节对齐的指针，它们总是未使用(即 00)，并且因为它们适合 32 位指针，它们可以与指针本身原子地进行 CAS，这是该算法的关键。当然这在 C# 中是不可能的，至少在不使用不安全代码的情况下是不可能的。

解决方案变得有点复杂，涉及对包含两个字段(.Next + 标记)的不可变类的额外引用。

我没有对这些想法进行冗长的解释，而是在 Internet 上找到了一些引用资料，它们将详细介绍您需要的所有细节，请参阅:

Lock-free Linked List (Part 1)解释问题；

Lock-free Linked List (Part 2)讲解C方案+自旋锁方案；

Lock-free Linked List (Part 3)解释不可变状态引用；

如果您真的对这个话题很好奇，可以找到包含各种解决方案及其性能分析的学术论文，例如这个:Lock-free linked lists and skip lists

关于c# - 尝试编写无锁单链表，删除麻烦，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16863101/

c#编写codeNextsectionmultithreadinglock-free

有关c# - 尝试编写无锁单链表，删除麻烦的更多相关文章

  1. ruby - ECONNRESET (Whois::ConnectionError) - 尝试在 Ruby 中查询 Whois 时出错 - 2

    我正在用Ruby编写一个简单的程序来检查域列表是否被占用。基本上它循环遍历列表，并使用以下函数进行检查。require'rubygems'require'whois'defcheck_domain(domain)c=Whois::Client.newc.query("google.com").available?end程序不断出错(即使我在google.com中进行硬编码)，并打印以下消息。鉴于该程序非常简单，我已经没有什么想法了-有什么建议吗？/Library/Ruby/Gems/1.8/gems/whois-2.0.2/lib/whois/server/adapters/base.

  2. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  3. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  4. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

    查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

  5. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

    我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

  6. ruby-on-rails - 每次我尝试部署时，我都会得到 - (gcloud.preview.app.deploy) 错误响应 : [4] DEADLINE_EXCEEDED - 2

    我是Google云的新手，我正在尝试对其进行首次部署。我的第一个部署是RubyonRails项目。我基本上是在关注thisguideinthegoogleclouddocumentation.唯一的区别是我使用的是我自己的项目，而不是他们提供的“helloworld”项目。这是我的app.yaml文件runtime:customvm:trueentrypoint:bundleexecrackup-p8080-Eproductionconfig.ruresources:cpu:0.5memory_gb:1.3disk_size_gb:10当我转到我的项目目录并运行gcloudprevie

  7. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  8. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b

  9. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  10. ruby - 如何安全地删除文件？ - 2

    在Ruby中是否有Gem或安全删除文件的方法？我想避免系统上可能不存在的外部程序。“安全删除”指的是覆盖文件内容。 最佳答案 如果您使用的是*nix，一个很好的方法是使用exec/open3/open4调用shred:`shred-fxuz#{filename}`http://www.gnu.org/s/coreutils/manual/html_node/shred-invocation.html检查这个类似的帖子:Writingafileshredderinpythonorruby?

随机推荐