标签 ‘ wait-free

为什么无等待如此重要

原文地址 ,译文链接,译者:张军,校对:梁海舰

无锁(完全同步)

想象一下,一个无锁算法或数据结构有一个方法,这个方法所有执行过程都需要同步。假设在单线程模式下这个方法每次调用需要10ns,而每增加一个线程调用这个方法,将在同步状态(变量)上产生争用。
很显然,如果只有一个线程,每次调用该方法到返回平均时间都为10ns,我们称之为:每10ns完成的任务数;如果你增加更多的线程,他们将会增加其他线程执行完成的时间,这是因为同一时刻只有一个线程能获得锁;
记住,无锁(Lock-Free)保证一个线程可以执行,但没说是哪一个,并且在当前这个特定的例子中,每次只有一个线程可以执行(完成任务),其他线程不得不从头开始:
阅读全文

无等待是不够的

原文地址译文链接,译者:许巧辉,校对:周可人

无等待是不够的

以目前针对演进条件(progress condition,注:参考[1])的算法和数据结构的分类来看,是不足以区分不同演进条件的能力和每一个演进条件的性能/延迟。

我们提出了一种新的“大O”记号来表示无等待的算法和数据结构。下面是它的工作原理:

一个算法或功能被称为“Wait-Free O(x)“,表示需要最多O(x)操作完成。

阅读全文

非阻塞同步算法实战(三)-LatestResultsProvider

感谢trytocatch投递本文。

前言

阅读本文前,需要读者对happens-before比较熟悉,了解非阻塞同步的一些基本概念。本文主要为happens-before法则的灵活运用,和一些解决问题的小技巧,分析问题的方式。

背景介绍

原始需求为:本人当时在编写一个正则替换工具,里面会动态地显示所有的匹配结果(包括替换预览),文本、正则表达式、参数,这些数据的其中一项发生了变化,结果就应该被更新,为了提供友好的交互体验,数据变化时,应该是发起一个异步请求,由另一个独立的线程来完成运算,完成后通知UI更新结果。由于是动态显示,所以提交会非常频繁。 阅读全文

非阻塞同步算法实战(一)

感谢trytocache投递本文。

前言

本文写给对ConcurrentLinkedQueue的实现和非阻塞同步算法的实现原理有一定了解,但缺少实践经验的朋友,文中包括了实战中的尝试、所走的弯路,经验和教训。

背景介绍

上个月,我被安排独自负责一个聊天系统的服务端,因为一些原因,我没使用现成的开源框架,网络那块直接使用AIO,收数据时,因为只会从channel里过来,所以不需要考虑同步问题;但是发送数据时,因为有聊天消息的转发,所以必需处理这个同步问题。AIO中,是处理完一个注册的操作后,再执行我们定义的方法,此时,如果还有数据需要写,则继续注册写操作,如果没有则不注册;提交数据时,如果当前没有注册写操作,则注册一个,否则仅提交(此时再注册则会报异常)。这样,需要同步的点就是:如何知道当前还有没有数据需要发送(因为其它线程也可以提交数据到此处),和如何知道此次提交时,有没有注册写操作。总之,要完成:有数据要发送时,必需有写操作被注册,并且只能注册一次;没有数据时,不能有写操作被注册。 阅读全文

return top