如何构建无锁队列?

本文介绍了如何构建无锁队列?的处理方法,对大家解决问题具有一定的参考价值

问题描述

我今天花了很多时间研究无锁队列.我有多个生产者,多个消费者的情况.为了测试,我实现了一个在 Win32 下使用 Interlocked SList 的系统,它使我基于重线程任务的代码的性能提高了一倍.但不幸的是,我希望支持多个平台.在多个平台上互锁本身不是问题,我可以放心地假设我可以毫无问题地互锁.然而,实际的实现让我迷失了.

I've spent today looking into lockless queues. I have a multiple producer, multiple consumer situation. I implemented, for testing, a system using the Interlocked SList thing under Win32 and it doubled the performance of my heavily threaded task based code. Unfortunately, though, I wish to support multiple platforms. Interlocking on multiple platforms itself is not a problem and I can safely assume I can interlock without problems. However the actual implementation loses me.

最大的问题似乎是您需要保证列表推送/弹出将仅使用一个互锁调用.否则,您将留出空间让另一个线程咬入并将事情搞砸.我不确定微软的实现是如何在幕后工作的,我很想知道更多.

The big problem appears to be that you need to guarantee a list push/pop will use only one Interlocked call. Otherwise you are leaving space for another thread to nip in and screw things up. I'm unsure how the microsoft implementation works under-the-hood and would love to know more.

谁能告诉我有用的信息(平台和语言无关紧要)?

Can anyone point me towards useful information (Platform and language are pretty irrelevant)?

此外,我很想知道是否可以实现无锁向量.这对我有很大的用处:)干杯!

Added to that I'd love to know if its possible to implement a lockless vector. That would have huge amounts of use for me :) Cheers!

阅读herb 的DDJ 文章后,我可以看到一个减少的锁定队列,这与我已经拥有的非常相似.但是我注意到最后有一些论文可以使用双重比较和交换(DCAS)操作进行真正的无锁队列.有没有人使用 cmpxchg8b (或 cmpxchg16b )实现队列?

Having read herb's DDJ article I can see a reduced lock queue that is pretty similar to the one I already had. However I notice that there are papers at the end that can do the true lockless queue'ing using a double compare-and-swap (DCAS) operation. Has anyone implemented a queue using cmpxchg8b (or cmpxchg16b for that matter)?

此时我只是在沉思(尚未阅读论文),但您可以使用此系统同时更新头指针和尾指针,从而避免另一个线程在两个原子操作之间跳转的任何问题.但是,您仍然需要获取下一个头指针以针对尾指针进行测试,以查看您是否刚刚修改了尾.当另一个线程准备自己这样做时,如何避免另一个线程更改此信息?这究竟是如何以无锁方式实现的?还是我最好阅读研究论文的不可解读性?;)

I'm just musing at this point (having not read the papers) but you could use this system to update the head and tail pointer simultaneously and thus avoid any issues with another thread jumping inbetween the 2 atomic operations. However you still need to get the next head pointer to test that against the tail pointer to see if yo have just modified the tail. How do you avoid another thread changing this information while the other thread is preparing to do so itself? How exactly is this implemented in a lockless way? Or am i better off reading the undecipherability that is a research paper? ;)

推荐答案

你可能可以用最少的难度实现一个有限大小的队列...我最近在想它并想出了这个设计,但你可能会发现许多其他有趣的想法:(警告:它可能有一些问题!)

You could probably implement a limited-size queue with least difficulty... I was thinking about it lately and came up with this design, but you can probably find many other interesting ideas: (WARNING: it might have some issues!)

  • 队列是一个指向项目的指针数组
  • 您必须管理 2 个指针(头、尾),它们在队列中的工作方式与循环缓冲区相同
  • 如果 head == tail,则没有项目
  • 如果你想enqueue(ptr),Interlocked-Swap tail with NULL (prev_tail 是交换的值)
    • 如果 prev_tail == NULL,再试一次
    • 如果 prev_tail + 1(带环绕)== head,您的队列已满
    • 否则将您的 ptr 放入 *prev_tail 并将 prev_tail+1 分配给 tail (注意缓冲区环绕)
    • the queue is an array of pointers to items
    • you have to manage 2 pointers (head, tail) which work over the queue in the same way as a circular buffer
    • if head == tail, there are no items
    • if you want to enqueue(ptr), Interlocked-Swap tail with NULL (prev_tail is the swapped value)
      • if prev_tail == NULL, try again
      • if prev_tail + 1 (with wraparound) == head, your queue is full
      • otherwise put your ptr in *prev_tail and assign prev_tail+1 to tail (watch out for buffer wrap-around)
      • 如果为真,则返回,因为队列为空
      • 如果是假的
        • *tmp_head 保存为 ptr
        • 做一个 CAS:比较 headtmp_head 交换 headhead+1
        • 如果 CAS 失败 -- 重新启动整个函数
        • 如果成功 -- 返回 ptr
        • if it's true, return because the queue is empty
        • if it's false
          • save *tmp_head as ptr
          • do a CAS: compare head with tmp_head swap head with head+1
          • if CAS failed -- start the whole function over
          • if it succeeded -- return ptr

          head 和 tail CAS 操作都可以等待,但是如果队列没有被争用,你应该第一次成功,没有不必要的锁.

          You can wait on both head and tail CAS operations, but if the queue is not contended, you should succeed the first time, without unnecessary locks.

          无限大小的队列有点"困难;)但是您应该能够创建一个足够大的队列来满足大多数需求.

          Unlimited-size queues are "a bit" harder ;) But you should be able to create a big-enough queue for most needs.

          这篇关于如何构建无锁队列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,WP2

admin_action_{$_REQUEST[‘action’]}

do_action( "admin_action_{$_REQUEST[‘action’]}" )动作钩子::在发送“Action”请求变量时激发。Action Hook: Fires when an ‘action’ request variable is sent.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$_REQUEST['action']引用从GET或POST请求派生的操作。源码(Source)更新版本源码位置使用被使用2.6.0 wp-admin/admin.php:...

日期:2020-09-02 17:44:16 浏览:1127

admin_footer-{$GLOBALS[‘hook_suffix’]}

do_action( "admin_footer-{$GLOBALS[‘hook_suffix’]}", string $hook_suffix )操作挂钩:在默认页脚脚本之后打印脚本或数据。Action Hook: Print scripts or data after the default footer scripts.目录锚点:#说明#参数#源码说明(Description)钩子名的动态部分,$GLOBALS['hook_suffix']引用当前页的全局钩子后缀。参数(Parameters)参数类...

日期:2020-09-02 17:44:20 浏览:1033

customize_save_{$this->id_data[‘base’]}

do_action( "customize_save_{$this->id_data[‘base’]}", WP_Customize_Setting $this )动作钩子::在调用WP_Customize_Setting::save()方法时激发。Action Hook: Fires when the WP_Customize_Setting::save() method is called.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_data...

日期:2020-08-15 15:47:24 浏览:775

customize_value_{$this->id_data[‘base’]}

apply_filters( "customize_value_{$this->id_data[‘base’]}", mixed $default )过滤器::过滤未作为主题模式或选项处理的自定义设置值。Filter Hook: Filter a Customize setting value not handled as a theme_mod or option.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_date['base'],指的是设置...

日期:2020-08-15 15:47:24 浏览:866

get_comment_author_url

过滤钩子:过滤评论作者的URL。Filter Hook: Filters the comment author’s URL.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/comment-template.php:32610...

日期:2020-08-10 23:06:14 浏览:904

network_admin_edit_{$_GET[‘action’]}

do_action( "network_admin_edit_{$_GET[‘action’]}" )操作挂钩:启动请求的处理程序操作。Action Hook: Fires the requested handler action.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$u GET['action']引用请求的操作的名称。源码(Source)更新版本源码位置使用被使用3.1.0 wp-admin/network/edit.php:3600...

日期:2020-08-02 09:56:09 浏览:848

network_sites_updated_message_{$_GET[‘updated’]}

apply_filters( "network_sites_updated_message_{$_GET[‘updated’]}", string $msg )筛选器挂钩:在网络管理中筛选特定的非默认站点更新消息。Filter Hook: Filters a specific, non-default site-updated message in the Network admin.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分$_GET['updated']引用了非默认的...

日期:2020-08-02 09:56:03 浏览:834

pre_wp_is_site_initialized

过滤器::过滤在访问数据库之前是否初始化站点的检查。Filter Hook: Filters the check for whether a site is initialized before the database is accessed.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/ms-site.php:93910...

日期:2020-07-29 10:15:38 浏览:809

WordPress 的SEO 教学:如何在网站中加入关键字(Meta Keywords)与Meta 描述(Meta Description)?

你想在WordPress 中添加关键字和meta 描述吗?关键字和meta 描述使你能够提高网站的SEO。在本文中,我们将向你展示如何在WordPress 中正确添加关键字和meta 描述。为什么要在WordPress 中添加关键字和Meta 描述?关键字和说明让搜寻引擎更了解您的帖子和页面的内容。关键词是人们寻找您发布的内容时,可能会搜索的重要词语或片语。而Meta Description则是对你的页面和文章的简要描述。如果你想要了解更多关于中继标签的资讯,可以参考Google的说明。Meta 关键字和描...

日期:2020-10-03 21:18:25 浏览:1622

谷歌的SEO是什么

SEO (Search Engine Optimization)中文是搜寻引擎最佳化,意思近于「关键字自然排序」、「网站排名优化」。简言之,SEO是以搜索引擎(如Google、Bing)为曝光媒体的行销手法。例如搜寻「wordpress教学」,会看到本站的「WordPress教学:12个课程…」排行Google第一:关键字:wordpress教学、wordpress课程…若搜寻「网站架设」,则会看到另一个网页排名第1:关键字:网站架设、架站…以上两个网页,每月从搜寻引擎导入自然流量,达2万4千:每月「有机搜...

日期:2020-10-30 17:23:57 浏览:1264