我正在阅读 Read-copy-update (RCU) .对于 SMP，我不确定我是否理解正确。据我所知，RCU 确保更新以原子方式执行。在单链表的例子中，很明显可以在一个操作中完成用新元素交换旧元素，因为它是通过改变指针来完成的。但是如何保证在双向链表的情况下RCU仍然是原子执行的呢？有两个指针指向给定元素(next 和 prev)，因此该元素的每次更改都需要更改这两个指针。 如何确保更改这两个指针将作为原子操作完成？ 在 Linux 中是如何完成的？
最佳答案
我在问自己同样的问题，快速搜索找到了 a reply to a comment , 摘自 an introduction article to RCU作者 Paul McKenney(据我所知，他是 RCU 背后思想的多个并发发明者之一)。
问题:
I'm wondering whether the omission of the backlinks in the examples is a good thing. The omission makes the technique trivial, since publishing only involves one replacing one pointer.
What about the second, back, one? Without support for atomic two-pointer updates, how can both the p->prev->next = q and p->next->prev = q updates be performed without risking clients to see an inconsistent view of the doubly linked list? Or is that not a problem in practice?
Thanks for the article, though. Looking forward to the next installment!
答案:
Glad you liked the article, and thank you for the excellent question! I could give any number of answers, including: In production systems, trivial techniques are a very good thing. Show me an example where it is useful to traverse the ->prev pointers under RCU protection. Given several such examples, we could work out how best to support this. Consistency is grossly overrated. (Not everyone agrees with me on this, though!) Even with atomic two-pointer updates, consider the following sequence of events: (1) task 1 does p=p->next (2) task 2 inserts a new element between the two that task 1 just dealt with (3) task 1 does p=p->prev and fails to end up where it started! Even double-pointer atomic update fails to banish inconsistency! ;-) If you need consistency, use locks. Given the example above, we could support a level of consistency equivalent to the double-pointer atomic update simply by assigning the pointers in sequence -- just remove the prev-pointer poisoning from list_del_rcu(), for example. But doing this would sacrifice the ability to catch those bugs that pointer-poisoning currently catches.
So, there might well come a time when the Linux kernel permits RCU-protected traversal of linked lists in both directions, but we need to see a compelling need for this before implementing it.
所以基本上，Linux 在执行 RCU 时“不允许”在两个方向上向后遍历。如评论中所述，您可以使用一些较新的硬件机制，如 Double Compare And Swap ，但它们并非随处可用，并且如前所述，您仍然会遇到内存一致性问题。
关于c - Linux RCU 和双向链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40360073/
我正在构建一个连接到服务器并等待数据的客户端Ruby库，但也允许用户通过调用方法发送数据。我使用的机制是有一个初始化套接字对的类，如下所示:definitialize@pipe_r,@pipe_w=Socket.pair(:UNIX,:STREAM,0)end我允许开发人员调用以将数据发送到服务器的方法如下所示:defsend(data)@pipe_w.write(data)@pipe_w.flushend然后我在一个单独的线程中有一个循环，我从连接到服务器的socket和@pipe_r中选择:defsocket_loopThread.newdosocket=TCPSocket.new
这是这个问题的延续:OriginalQuestion(SO)这个问题的答案涉及以下一组模型:classUser:friendships#...endclassFriendship'User',:foreign_key=>'friend_id'end如果说，我有一个用户并且我想获得他或她的id是友谊模型上的:user_idFK的所有“友谊”，这很好用。但是，当我运行类似的东西时@user.friendships.friends我希望它返回该用户是友谊中的:user或:friend的所有用户记录-因此，换句话说，返回该用户参与的所有友谊。希望以上内容有意义。我对Rails还是很陌生，希望有
前文，我们实现了认识了链表这一结构，并实现了无头单向非循环链表，接下来我们实现另一种常用的链表结构，带头双向循环链表。如有仍不了解单向链表的，请看这一篇文章(7条消息)【数据结构和算法】认识线性表中的链表，并实现单向链表_小王学代码的博客-CSDN博客目录前言一、带头双向循环链表是什么？二、实现带头双向循环链表1.结构体和要实现函数2.初始化和打印链表3.头插和尾插4.头删和尾删5.查找和返回结点个数6.在pos位置之前插入结点7.删除指定pos结点8.摧毁链表三、完整代码1.DSLinkList.h2.DSLinkList.c3.test.c总结前言带头双向循环链表，是链表中最为复杂的一种结
我需要一个Ruby中的双向哈希表。例如:h={:abc=>123,:xyz=>789,:qaz=>789,:wsx=>[888,999]}h.fetch(:xyz)#=>789h.rfetch(123)#=>abch.rfetch(789)#=>[:xyz,:qaz]h.rfetch(888)#=>:wsxrfetch方法意味着反向获取，这只是我的建议。注意三件事:如果多个键映射到相同的值，则rfetch返回所有键，打包在数组中。如果值是一个数组，则rfetch在数组的元素中查找它的参数。双向哈希意味着fetch和rfetch都应该在恒定时间内执行。Ruby中是否存在这样的结构(包括外
关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。关闭7年前。Improvethisquestion我需要Ruby的双向加密解决方案，例如Blowfish、Rijndael(AES)或其他。然而，问题是我找不到适合它的gem。我希望库支持多种不同的加密算法，这样我就可以比较每种算法的性能，以便在我的应用程序中实现最佳集成。我也希望它是开源的。我遇到了Crypt,但它没有正确安装，而且看起来好像有一段时间没有更新了。EzCrypto也不会安装我还看到了ruby-aes
我在网上查了几个Ruby教程，他们似乎什么都用数组。那么如何在Ruby中实现以下数据结构呢？堆栈队列链表map组 最佳答案 (从评论中移出)好吧，通过限制堆栈或队列方法(push、pop、shift、unshift)，数组可以是堆栈或队列。使用push/pop提供LIFO(后进先出)行为(堆栈)，而使用push/shift或unshift/pop提供FIFO行为(队列)。map是hashes,和一个Set类已经存在。您可以使用类实现链表，但数组将使用标准数组方法提供类似于链表的行为。 关
我是JS的新手，组织数据的概念让我有些困惑，我试图从特定的数组格式中获取数据(因为这是我必须使用的格式)并将其输出为另一种特定的JSON格式。这是给D3sankey模块传递数据https://github.com/d3/d3-plugins/blob/master/sankey/sankey.js我不知道如何将节点的索引添加到链接中，而不是名称。真的，我完全迷失了它!我在这里做了一个fiddle:https://jsfiddle.net/adamdavi3s/kw3jtzx4/下面是所需数据和输出的示例vardata=[{"source":"Agricultural'waste'","
文章目录1.题目描述2.解题思路方法1：方法2：1.题目描述题目链接：力扣21，合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。2.解题思路方法1：首先我们能够想到的就是遍历一遍数组，判断两个结点的大小，将数值小的结点放在前面，数值大的不断尾插在后面。是不是听着挺简单的？具体实现：我们可以创建两个空指针，head用来存放链表的头结点，tail用来遍历两条链表，将两条链表链接起来。当某个链表为空时，我们可以直接返回另一条链表当两个链表都不为空时，我们可以不断比较两条链表的大小，当head和tail为空时，我们将较小的结点同时赋给head
所以我在JS中玩弄链表并提出了以下问题:比方说，我们有一个数组和一个链表，它们都有5000个元素。我们想在索引10处插入新元素。数组方式非常简单。我们在给定索引处插入新元素，并将其余元素向前移动一个索引。所以我尝试用链表来做这件事，并以下面的方式结束它:从NicholasZakas获取链表的实现并添加附加方法addOnPosition(data,index)。最后是代码:functionLinkedList(){this._head=null;this._length=0;}LinkedList.prototype={constructor:LinkedList,add:functio
我对使用datadrivendocuments的当前最佳实践和解决方案感兴趣具有双向AJAX数据绑定(bind)的库。更具体地说，我想知道如何d3最好与支持双向数据绑定(bind)的库集成，例如Angular或Knockout.出现的明显冲突源于以下事实:d3和AJAX库都将数据插入到DOM，这基本上意味着一个必须包装另一个。 最佳答案 关于DOM上的数据您担心插入DOM的数据。这是一些添加的属性:D3js:__data__,__onmouseover.force,__onmouseout.force,__onmousedown
