LCRQ并发排队算法不需要CAS

14→⊥LCRQ并发排队算法不需要CAS 2摘要拉伊德·罗曼诺夫俄罗斯圣彼得堡高等经济学院raid_r@mail.ru尼基塔·科瓦尔JetBrains阿姆斯特丹，荷兰val@ya.ru由迈克尔和斯科特近三十年前[16]，开始-可以说，并发队列是高负载应用程序中最重要的数据结构之一，这要求它们非常快速和可伸缩。实现这些属性是不平凡的。早期的解决方案，如Michael和Scott的经典队列，将元素存储在并发链表中。据说，这种设计是不可扩展的并且存储器效率低。 现代解决方案利用Fetch-and-Add指令来提高算法的可扩展性，并将元素存储在数组中以减少内存压力。其中最著名和快速的算法是LCRQ。其设计的主要缺点是它依赖于原子CAS2指令，这在大多数现代编程语言中是不可用的，例如Java，Kotlin或Go，更不用说某些架构了。本文提出了一种可移植的改进算法LPRQ原始LCRQ设计的简化，消除了所有CAS 2的使用。相反，它只使用标准的Compare-and-Swap和Fetch-and-Add原子指令来执行同步。 我们的实验表明，LPRQ提供了与经典LCRQ算法相同的性能，比不使用CAS 2的现有解决方案的最快速度高出1.6倍。进入构建高效非阻塞数据结构的时代。粗略地说，它们的设计基于一个链表结构，通过Head和Tail指针维护;Enqueue （ .. ） 和 Dequeue （ ） 通 过 原 子 比 较 和 设 置（CAS）指令更新它们。近年来，这种设计有了很大的改进，采用了Fetch-and-Add（FAA）指令来提高算法的可扩展性，并将元素存储在数组中以减少内存压力。该家族中最著名的算法之一是LCRQ[18]，由Morrison和Afek在2013年提出无限数组队列。 LCRQ设计的灵感来自于一种简单的队列算法，该算法使用定位计数器操纵无限数组进行排队（ . ） 和 Dequeue （ ） 操 作。 要 添 加 新 元素 ， 请 执 行Enqueue（..）通过Fetch-and-Add递增Tail计数器，在递增之前获得值t。之后，它将元素存储到保留单元A[t]中并结束。Dequeue（）操作对称地工作，递增其Head计数器并从保留单元A[h]中提取元素。下面的图1显示了插入和提取元素时数据结构的变化。0 1CCS概念：·计算方法学并发算法;共享内存算法。关键词：并发队列，环形缓冲区，无锁尾=0头=0查询（a）...尾=1头=0deq：a尾=1头=11引言数据结构是并发程序设计中最基本、最实用的数据结构之一。 大量的研究已经取得了发展快速和有效的解决方案。提出了第一个无锁算法允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。请求权限请发邮件至sales@acm.org。PPoPP '23，2023年2月25日至3月1日，加拿大魁北克省蒙特利尔市© 2023版权归所有者/作者所有 授权给ACM的出版权。ACM 979-8-4007-0015-6/23/https://doi.org/10.1145/3572848.3577485图1. 无限数组队列结构。由于并发性，可以使用Enqueue（..） 添加Tail和pause，所以Dequeue（）可能会保留一个仍然为空的单元格。为了取得进展，Dequeue（）通过将空单元格的状态移动到一个特殊值并重新启动来破坏它 之后，Enqueue（） 观察到单元被破坏并重新启动;它通过CAS安装元素以进行同步。清单1给出了相应的伪代码。LCRQ设计 Afek和Morrison详细阐述了这个想法，并开发了一种非常有效的LCRQ算法，在引擎盖下使用环形缓冲区，他们称之为CRQ-s（并发环形缓冲区）。粗略地说，CRQ是一个有界队列，关于Enqueue（.）也会失败与无限数组队列类似，Enqueue（..） 递增其尾计数器并处理0 1...0 1...PPoPPRaed Romanov和Nikita Koval15⊥⊤1 Head，Tail： Long// 64位计数器2 A： E[]//E类型元素的无限数组34 funEnque（ite m： E）=while（true）{5t：=尾。FAA（1）6if（A [t]. CAS（null，item））return（七）89 funDeque（）： E=while（true）{10if（Hea d>=Tail l）returnnull//empty？11h：=头部。FAA（1）12if（A[h]==null&&A[h]. CAS（null，））continue13returnA[h]14}清单1. 无限数组队列算法。单元格A[t %R]，其中R是环形缓冲区的大小对称地，Dequeue（）递增Head并处理单元格A[h %R]。 一旦当前的环形缓冲区已满，Enqueue（..）关闭它以进行进一步的插入，并创建一个新的CRQ，构造它们的链表尽管高层次的想法是相似的，但使阵列圆形完全改变了同步在无限数组队列中，每个单元格都可以由ex-tagononeEnqueue（..） 和一个Dequeue（），使它们之间的同步变得简单。 在环形缓冲区结构中，每个R-s Enqueue（.） 和Dequeue（）尝试在大小为R. 这会导致几个潜在的问题，例如将元素添加到队列的中间或无序删除。为了解决竞争问题，LCRQ为每个单元配备了一个64位的历元计数器。直观地说，它确保Dequeue（）仅从其h/R epoch提取元素，而Enqueue（..） 如果相同epoch的共轭Dequeue（）已经处理并跳过了单元格，则永远不会安装该元素。LCRQ不可移植性。LCRQ设计的主要问题是它的可移植性。每个小区都配备了一个历元计数器，LCRQ通过CAS 2自动更新小区状态。虽然这种指令在现代硬件架构中越来越流行，但大多数编程语言，如Java，Kotlin或Go，都没有提供这样的原语，因此无法在其中实现LCRQ。提出了几种方法来消除CAS2的使用。 Ramalhete[22]提出了一个简单的无锁队列，它从不重用环形缓冲区，当到达内部数组的末尾时分配一个新的。 这种设计简化了无限数组队列，并且不使用epoch，只允许一个Encase-Dequeue对处理单元。Yang和Mellor-Crummey[27]扩展了这种方法以提供等待自由。这些工作和我们的实验LCRQ优于这两种解决方案。另一种摆脱CAS2的方法是操作32位值和32位epoch，它们 可 以 打 包 成 单 个 64 位 字 ， 并 由 CAS原 子 地 更 新 。Nikolaev [20]使用这样的队列来构建他的SCQ环形缓冲区算法，维护一个元素数组和该数组中的两个32位索引队列，为Enqueue（..）以及Dequeue（）的占用单元格。 费尔德曼和德切夫[5]用另一种方法处理这个问题，将历元场整合到元素中。除此之外，他们的算法将epoch存储在空单元中，这在大多数具有垃圾收集功能的语言（如Java或C#）中在技术上是不可能的。 与LCRQ相比，这两种解决方案的效率都要低得多。我们的贡献。 本文提出了LPRQ并发排队算法，它是LCRQ的一个可移植的改进，不需要CAS 2。从本质上讲，我们应用两个技术，niques原来的LCRQ设计。首先，我们在Dequeue（）中删除CAS2，使Enqueue（..）操作负责维护历元。然而，它应该只将元素放置在正确的历元中，LCRQ通过CAS 2解决了这个问题。相反，LPRQ通过安装一个线程唯一的令牌，检查epoch并在此之后将令牌替换为元素来“锁定”单元。 从实现方面来说，这个线程唯一的令牌通常是对当前运行的线程的引用（例如，JVM上的线程实例我们用C++实现了LPRQ算法，将其与原始LCRQ解决方案和不需要CAS 2的各种队列进行了比较。 我们的实验表明，我们的LPRQ算法提供了与LCRQ相同的性能，超过了其他最好的解决方案高达1.6倍。2 预赛内存模型和原子操作。 为了简单起见，我们假设一个顺序一致的内存模型。 除了简单的读写操作外，我们还使用了比较和设置（CAS）和获取和添加（FAA）原子操作，这些操作在所有现代编程语言中都可以访问。 在LCRQ算法的讨论中，我们还使用了不可移植的CAS 2指令，它更新两个连续的（不是任意的）内存位置;在x86上也称为cmpxchg16 b。记忆回收 为了简单起见，我们假设环境提供了垃圾收集器。 对于手动内存回收，可以使用诸如Hazard Pointers [15]或Hazard Eras [23]的技术。无效性。原始的LCRQ算法和我们的LPRQ修改假设元素类型E提供了一个特殊的空值，它永远不会插入到队列中。我们用它来指定空的数组单元。在Dequeue（）中返回null表示队列为空。线程令牌。 我们的PRQ算法假设环境提供了线程唯一的令牌，表示为���令牌������������������，可以存储在与元素相同的位置。简而言之，Enqueue（..）在存储元素之前在单元中安装这样的令牌，以确保它在正确的时期执行操作。在实践中，线程标记可以通过保留值的单个位来实现，以将它们与元素区分开来。如果设置了这个位，其他的存储拥有令牌的线程的索引否则LCRQ并发排队算法不需要CAS 2PPoPP16其他位存储该元素。 在某些不允许“位窃取”的平台上，对当前运行线程的引用可以用作线程标记。例如，在一个示例中，可以通过Thread.currentThread（）有效地获取JVM上的java.lang.Thread实例。3LPRQ算法我们首先讨论原始的LCRQ设计，它使用不可移植的CAS2指令。然后，我们分两步消除它的使用。首先，我们在Dequeue（）中删除CAS2，使Enqueue（..）操作负责维护每个小区的时期。接下来，我们在Enqueue（.）中删除CAS2。通过使用线程唯一的令牌来“锁定”单元并安全地执行其余的同步。3.1LCRQ概述LCRQ 背 后 的 关 键 成 分 是 一 个 特 殊 的 环 形 缓 冲 区（CRQ）数据结构，它可以被关闭以供进一步插入。简而言之，CRQ操纵一个预先分配的恒定大小的数组和两个定位计数器，用于Enqueue（..）和Dequeue（）操作。 当CRQ已满时，Enqueue（..）关闭它以防止进一步的插入，并分配一个新的CRQ，构建它们的链表。环形缓冲区顶部的LCRQ 清单2给出了操作环形缓冲区（CRQ-s）的高级LCRQ实现。我们的LPRQ算法利用了相同的设计，用新的PRQ（便携式环形队列）代替了非便携式CRQ环形缓冲区的实现。类似于Michael-Scott队列[16]，链表通过Head和Tail指针指定（第2行）。要插入元素，请执行Enqueue（..）读取最后一个CRQ（第6行）并尝试将元素添加到其中（第7行）。成功后，操作立即结束。否则，当前CRQ已满并关闭，以便进一步插入。 这样，Enqueue（.）分配一个新的CRQ实例，并立即插入元素（第9行）。然后，它尝试以类似于Michael-Scott队列（第10- 15行）的方式将这个新CRQ添加到当前CRQ 如果并发入队（..）已添加新CRQ，则当前操作重新启动。Dequeue（）操作操作Head CRQ并尝试从中提取元素，并在成功时完成（第19 - 21行）。如果提取失败，则当前CRQ为空，而队列可能仍包含非空CRQ。因此，Dequeue（）读取下一个CRQ，如果不存在则返回null（第23行）。否则，并发入队（..）-s可以在我们观察到它为 空 和 读 取 crq 之 间 向 当 前 CRQ 添 加 元 素 。 因此，Dequeue（）尝试再次从当前队列中提取元素（第25行），并在成功时结束（第26行）。否则，当前CRQ为空并关闭，因此Dequeue（）将Head指针更新为下一个CRQ并重新启动（第28行）。高级环形缓冲区设计。 我们将注意力转移到CRQ的实施上。图2显示了环形缓冲区1 classLCRQ E>{2头部，尾部：CRQ34funEnque（ite m： E）=while（true）{5//快速路径：添加到当前CRQ6crq：=尾部7如果（crq. 排队（项目））返回8// slow - path：尾流已满，添加新的CRQ9newTail：= CRQ（）; new Tail. 入队（项目）10if（cr q. Nex t. CAS（null，newTai l））{11尾巴CAS（crq，new Tail）12返回13}else{14尾巴CAS（crq，crq. 下一页）15}16}1718funDeque（）： E=while（true）{19crq：=头部20res：= crq. 脱队21if（res！=null）returnres22//失败，这个队列是空的吗？23if（cr q. Next==null）returnnull24//`crq`是封闭的，但可以存储元素25res：= crq. 脱队26if（res！=null）returnres27//`crq`为空，更新HEAD并重新启动28头CAS（crq，crq. 下一页）29}30}31 classCRQ E>{32Next：CR Q E>=null33//将item加入队列并返回true34//或关闭CRQ并返回false35funEnqueue（ item： E）： Bool36有趣Dequeue（）： E//如果CRQ为空，则37}清单2.高级别LCRQ [18]实现操纵CRQ-s。LPRQ高水平设计是相同的，区别仅在于用清单4中的PRQ替换CRQ。一种基于大小为R的数组A的结构，用于存储配备了Head和Tail定位计数器的元素;它们的值模R指定了下一个元素插入和提取的索引。最初，所有数组单元都是空的，并存储null。环形缓冲区的当前大小等于（Tail-Head），并且永远不会超过R。0 1 2 3 4 5 6 7答：尾=9头=5图2.一个大小为8的环形缓冲区 的例子。Head %R指向下一个要提取的元素，而Tail %R指向下一个要放置元素的单元格要添 加元 素， 请 执行 Enqueue （ ..） 首先 通过 原子Fetch-and-Add指令递增其Tail计数器，在递增之前获得索引t，如果单元格A[t%R]为空，则将元素放置到单元格A[t %R]。对称地，Da B CPPoPPRaed Romanov和Nikita Koval17enq（x）enq（y）（）下一页deq：y（）下一页Dequeue（）通过FAA增加Head并从A[h %R]中提取元素。这种设计让人想起清单1中的无限数组队列。细胞时期。为了进一步讨论，我们需要引入操作指数和操作周期的概念。 当一个操作通过FAA递增Head或Tail时，它返回计数器在递增之前的值i。 我们称这个值i为操作的索引，而i/R是操作周期。Dequeue（）只从共轭的Enqueue（..）中获取元素是至关重要的。相同的操作周期。为了证明这一点，我们考虑了两个大小为R = 2的环形缓冲区的例子，表明提取放在另一个周期上的元素会导致FIFO语义违反。首先，我们考虑图3a所示的执行。螺纹1调用Enqueue（..），它会增加Tail并得到被调度器抢占 执行切换到线程 2，它首先插入 和 。具体地说，在 周 期 0 获得索引1并 放入第1个单元，而在周期1获得索引2并 放入第0个单元。然后，DB2执行两个Dequeue（）-s，以相反的顺序提取DB2和DB 3 问题是： （周期0上的第0个单元格）检索放在更高周期1上的元素;因此，从未来提取它。当Dequeue（）检索放置在较低循环上的元素时，会出现类似的问题;我们在图3b中展示了这样的执行。首先，在循环0上插入“”和“”“ Af-就会被抢占执行切换到 2，它执行两个Dequeue（）-s。（回想一下，Head已经增加了101。）第一个Dequeue（）获取索引1，并从周期0的第一个单元格中提取出索引 第二个操作获得索引2， 从第0个细胞周期1。与前面的示例类似，元素以相反的顺序提取，违反FIFO队列语义。一种确保元素只能在正确的周期上被取用的方法是将每个单元格与一个历元相关联。排队时（..） 将一个元素放入一个单元格中，它还将单元格epoch更新为其操作周期。反过来，Dequeue（）仅在单元格epoch匹配其周期时才提取元素。图4显示了该方案如何修复图3b中的错误表达式。执行开始时，在周期0上添加“”和“” 之后， 1调用Dequeue（），这增加了Head并被抢占。执行切换到2，它执行两个Dequeue（）-s。与前面的示例一样，第一个Dequeue（）获得索引1并提取从第0个周期的第1个细胞中提取。但是，2中的下一个Dequeue（） 不能再检索 ，因为第0个单元格的epoch为0，而操作周期为1。因此，这个Dequeue（）重新启动，发现环形缓冲区为空，并返回null。 在ex-order切换回 1之后，相应的Dequeue（）通过 从第0个单元格中提取完成。联邦航空局局长（1）：0此后，它调用Dequeue（），递增Head和T1deq：xT2deq：y deq：null尾FAA（1）：0T1状态元素时代X y0 0头部=1X0 1头部=2X01 1 1头部=3头部=3T2enq（x）enq（y）deq：ydeq：x尾部=2尾=2尾=2尾部=2状态尾=1头=0X尾=2头=0y x尾=3头部=0X尾=3头=1尾=3头=2图4. 历元有助于保持元素的FIFO顺序。CRQ算法。 我们需要以原子方式更新cell epoch及其状态;否则，Dequeue（）可能会观察到(a) 从未来退出队列会破坏FIFO语义。联邦航空局局长（1）：0T1deq：空T2deq：x元素的不正确的时代，并采取它，打破了FIFO的语义。CRQ通过硬件CAS2指令实现这种原子更新。清单3给出了CRQ伪代码。 单元格数据结构有一个64位的值（行5）和一个64位的SafeAndEpoch（行2）字段;后者包一个特殊的安全标志以及历元。除了头部和尾部计数器，CRQ广告-国家x y x存储Closed标志（第9行）1，表示头=1头=2头部=3队列是否为插入而关闭，以及指向尾部=2尾=2尾=2它们的链表中的下一个CRQ，它被(b) 从过去的队列中退出会破坏FIFO语义。图 3. 这 两 个例 子 表 明 Dequeue （ ） 必 须 只 从 共 轭 的Enqueue（..），周期重合。这里，两个线程访问大小为2的环形缓冲区 。清单2中的LCRQ。Enqueue（..） 和Dequeue（）操作在迭代中进行（参见第13和34行的循环）。 每次迭代开始于对Tail（第14行）或Head（第35行）执行FAA，获得迭代索引及其周期。每1最初，CRQ保留较高的尾位来存储Closed标志。 为了简单起见，我们将它放在一个单独的变量中。enq（v）enq（y）enq（x）LCRQ并发排队算法不需要CAS 2PPoPP18+1 struct单元格E>{34 funDeque（）： E=while（true）{2Safe And Epoch {// 64 bits35h：=头部。FAA（1）3安全：布尔值=true，Epoch：Long = 036循环：=h/R; i：= h %R4}37whilee（true）{//tryupatethecelstate5值：E=null38<安全，epoch>：= A [i]。 安全与时代6 }39value：= A [i]. 值7408 头部：长=0，尾：长=041当{//根据图5进行转换9 关闭d：Boo l=false42epoch= =周期值！=null->{10 A：单元格E>[ R]43//出队转移11 Next：CR Q E>=null //pittCRQ44如果（A [i]. CAS2（<<安全，历元>，值>，1245<，null>））13 funEnque（ite m： E）：Boo l=while（true）{46返回值14t：=尾。FAA（1）47}15if（关闭d）重新打开文件48epoch=cycl evalue e==null->{16循环：=t/R; i：= t %R49//空跃迁17<安全，epoch>：= A [i]。 安全与时代50如果（A [i]. CAS2（<<安全，历元>，值>，18value：= A [i]. 值51<，value>））1952打破20if（value==null //该单元是空的y53}21//并且队列不会被超越54epochcycl evalue e！=null->{22epoch <=周期&& （安全||头部<=（t））55//不安全变迁23//排队转移56如果（A [i]. CAS2（<<安全，历元>，值>，24if（A [i]. CAS2（安全，环保，无污染，57<，valuee>））25<，item>））58打破26返回true59}27}60// else epoch>循环28//队列是否已满？61else->break//deqisovercomen29如果（t -头>=（R）{62}30关闭：=true63}31returnfalse64//队列是否为空？32}65if（Tail= h +1）returnnull33 }66 }清单3.Morrison和Afek的CRQ算法[18]。迭代时，操作读取单元状态（第17- 18行，第38 - 39行图5示出了可能的单元状态转换。考虑Dequeue（）的一个迭代，其索引为，循环为cycle 。如果单元格的历元大于0（第61行），则在计数器递增和读取单元格历元之间，���在这种情况下，此Dequeue（）尝试失败，操作重新启动。 否则，执行以下转变之一：如果单元格包含一个元素，并且epoch与迭代周期匹配 ，则执行出队转换Dequeue（）尝试通过CAS2（第44行）提取元素并增加单元格epoch，成功完成 。 如 果 单 元 格 为 空 ， 则执行空 转 换 ， 防 止Enqueue（..）使元素循环- 是的为此，如果单元格为空，Dequeue（）原子地将单元格epoch增加到1001（第50行）。最后，如果单元格包含元素，但epoch低于100，则执行不安全的转换 为了安全地跳过这个单元格，Dequeue（）必须防止在循环上安装元素 。技巧是重置安全位（第56行），使Enqueue（）只有在Head低于全局单元索引时才有资格安装元素（第22行）。排队转移Cas2XeCDequeuexCAS2过渡CC+1空CAS 2过渡eC+1不安全过渡xCAS 2Xee图5.CRQ中的单元状态转换： 是操作周期， 是转换之前的单元时期。每当执行转换的CAS2失败时，单元更新过程重新开始（第37行处的循环）。 同时，如果Dequeue（）完成了一次迭代而没有提取元素，它会读取Tail来检查队列是否为空（第65行），在这种情况下返回null，如果队列可能有元素，则重新开始。2现在考虑Enqueue（..）的迭代. 在对Tail执行-ing FAA之后，Enqueue（..）检查队列是否关闭（第15行）。在这种情况下，它立即返回false。然后如果2正如Morrison和Afek [18]所提出的，Dequeue（）也可以在返回null之前将Tail提前到当前Head。为了简单起见，我们省略了这种···PPoPPRaed Romanov和Nikita Koval19⊤单元格为空，并排队（..）没有被超越（第20 - 22行），它尝试执行入队转换，成功时返回true。失败时，它检查队列是否可能已满，因此应该关闭（第29行）。 如果是，则Enqueue（..） 将Closed标志更新为true（第30行），防止进一步插入，并返回false。 如果此CRQ有剩余空间，则Enqueue（..）进行下一次迭代。入队转换（第24行）将元素放入单元格，并将epoch提前到迭代周期。值得注意的是，该操作必须验证它没有被更高周期的Dequeue（）超越（第22行）。另外，在设置了安全位的情况下，排队（..）不能依赖于小区时期来确保操作没有被超越。相反，它读取当前Head值并将其与迭代索引进行比较（第22行）。 成功转换后，Enqueue（..） 还将安全位设置为真，从而恢复单元。3.2PRQ算法为了构造我们的PRQ 算法，我们将两个变换应用于CRQ。首先，我们移动循环数并修改转换前提条件，这允许将Dequeue（）中的所有CAS2使用替换为普通的CAS-s。其次，我们提出了一种有效的方法来模拟CAS 2在排队（..），它用它将元素放置在正确的纪元中，并带有一个CAS-序列。与传统的k-CAS算法[8]不同，我们的方法不使用描述符，也不涉及分配或内存间接。删除Dequeue中的CAS2（）。我们对原始CRQ算法进行了以下更改：我们用cycle初始化Head和Tail，因此操作从周期1开始（不像CRQ中的0Enqueue（..）仅当单元时期严格低于操作周期时才有资格放置元素。eeXxCAS不安全过渡CeCAS空跃迁CCx门店脱队过渡CeXCas2排队转移图6.在改进的CRQ算法中的单元状态转换： 是操作周期， 是转换之前的单元时期。图6总结了我们在上面讨论过的改进CRQ算法中的单元状态转换我们在附录A中给出了相应的伪代码。CAS2emulation in Enqueue（..）. 通过上面讨论的更改，只有Enqueue（）需要CAS 2放置其元素并原子地增加epoch（列表3中的第24行）。 我们提供了一种智能的方法来模拟这个CAS 2，如图7所示的三步程序：1. 手 机 预 约 。 要 放 置 元 素 并 增 加 epoch ， 请 执 行Enqueue（..） 首先������������������������通过在单元中安装线程唯一的令牌令牌来“锁定”单元。（关于实现，对当前运行的线程的引用可以用作线程令牌。2. 时代促销。接下来，它将细胞时期增加到操作周期。3. 元素发布。最后，Enqueue（.）替换它的你就不能用元素来表达吗。������������������������关键思想是，当它存储线程令牌时，不允许其他操作更改单元格epoch，因此当Enqueue（..） 用最后一步的元素替换它，保证单元格epoch没有改变。排队时（..）放置元素时，它会将单元格epoch提升到操作周期。成功的，锁细胞推动时代前进发布元件Enqueue（..）-s总是增加细胞时期。当Dequeue（）提取元素时，它保持单元格epoch不变。唯一的例外是空transition，它将epoch提升到操作周期。这些更改有效地将Dequeue（）中的所有CAS2转换为双重比较单交换操作，仅在成功检索时更改Value字段，并在空和不安全转换的情况下更新SafeAndEpoch。我们还需要添加一个元素来通过普通的CAS-s实现它们。直观地说，Dequeue（）应该在更新之前读取单元状态的一致快照。像CRQ一样，它读取SafeAndEpoch，然后是Value（第38 - 39如果是，则已获得正确的单元格快照，因为epoch总是增加，并且仅当Enqueue（..） 增加了细胞时期。 如果还没有获得快照，Dequeue（）会尝试再次获取快照。图7. CAS2 emulation in Enqueue（..） 以正确地放置元件。在这里，螺纹接头在循环1上插入螺纹接头伪代码。 清单4给出了PRQ算法的伪代码。 至于数据结构，它与CRQ的数据结构相同（清单3）;唯一的区别是PRQ使用Head和Tail 代替0（第2行）。TheEnqueue（..） 操作开始于递增其尾计数器，获得索引h（第5行）。然后，它检查单元格是空的还是锁定的，并且操作没有被超越，在这种情况下重新开始（第13- 15行）。否则，它将尝试按照上面描述的三步过程（第18- 29行）放置元素。Dequeue（）操作开始于递增其Head计数器并获得索引h（第41行）。接下来，它对单元格进行快照，获取其epoch、安全标志和单元格值（第4400阿勒1阿勒·X1···LCRQ并发排队算法不需要CAS 2PPoPP20⊤⊤⊤⊤⊤联系我们1 //最初2 头部=R;尾=R34 funEnque（ite m： E）：Boo l=while（true）{5t：=尾。FAA（1）6if（关闭d）重新打开文件78循环：=t/R; i：=t %R910<安全，epoch>：= A [i]。 安全与时代11value：= A [i]. 值1213if（valueisnullor//notoccupiedd14//并且队列不会被超越15时代<周期&& （安全||头部<=（t））1617//使用线程令牌18192021//前进一步22如果（！A [i]. 安全和时代。CAS（<安全，纪元>，23））{24A[i]。值e. CAS（，null）//cleanup��������������� ���������25goto检查溢出26}2728// publish item293031}3233check Overflow：//队列是否已 满？34如果（t -头>=（R）{35关闭：=true36returnfalse37}38}3940 funDeque（）： E=while（true）{41h：=头部。FAA（1）42循环：=h/R; i：= h %R43whilee（true）{//tryupatethecelstate44<安全，epoch>：= A [i]。 安全与时代45value：= A [i]. 值46if（safe，epoch>！<= A [i]。 安全和时代）47continue//inconsistentviewofecel4849当50epoch==cyclevalueisnotnullor->{51//出队转移52A[i]. 值：=null53返回值54}55epoch=cyclevalueisnullor->{56//空跃迁57//解锁单元格585960我爱你61//前进一步62如果（A [i]. 安全和时代。CAS（<安全，纪元>，63<安全，循环>））64打破65}66epochcyclevalueisnottnullor->{67//不安全变迁68如果（A [i]. 安全和时代。CAS（<安全，纪元>，69））70打破71}72// epoch>循环73else->break//deqisovercomen74}75}76//队列是否为空？77if（Tail= h +1）returnnull78}清单4. PRQ算法。黄色突出显示的操作模拟CAS 2。在单元被占用并且历元与迭代周期匹配的情况下执行出队过渡（行50）-它用空值替换存储的元素（行52）并结束（行53）。 由于在单元格被占用时不能更改历元，因此在这里使用普通存储而不是CAS是安全的。当单元格为空或当单元格被锁定并且历元低于操作周期时，应用空转换（行55）。 为此，Dequeue（）首先将线程标记替换为null（第59行），将epoch提前到之后的操作周期（第62行）。如果这些CAS-s中的任何一个失败，则单元更新过程重新启动.如果其历元低于操作周期，则在被占用的单元上执行不安全转换。 与CRQ类似，Dequeue（）重置安全位（第68行）并重新启动。值得注意的是，当Enqueue（..）重新启动时，它还读取Head计数器以验证队列是否已满（第34行），关闭队列（第35行），否则返回false。4 正确性类似于LCRQ，我们的LPRQ算法构造了一个环形缓冲区的链 表 ， 它 遵 循 tantrum 队 列 的 语 义 [18] 。 具体来 说 ，Enqueue（.） 可以不确定地拒绝插入元素并关闭环形缓冲区。关闭后，所有进一步的插入尝试都将失败。为了证明LPRQ的正确性，我们证明了我们的PRQ环形缓冲区是一个线性化的tantrum队列。 由于操作环形缓冲区的高级部分LPRQ（参见清单2）与LCRQ相同，因此我们不对其进行分析。PRQ线性化。 为了证明PRQ是一个可线性化的tantrum队列，我们遵循LCRQ作者[18]的方法。考虑一个操作的执行 <：>、where和return。我们假设一个操作在它的第一个和最后一个事件之间是活动的 。我们表示Dequeue（）/Enqueue（..）执行的最后一次Head.FAA（1）/Tail.FAA（1）调用的结果。操作as().如果（！A [i]. 值CAS（value，CAS������������）������������）goto检查溢出如果（A [i]. 值CAS（������������CAS������������，项目））返回trueif（valueis）&&！A [i]. 值e. CAS（valuee，null））···PPoPPRaed Romanov和Nikita Koval21//（）下一页（）下一页[客户端]（）下一页（）≥//·≥（）下一页≤（）（）≤（）（）首先，我们展示了每个成功的Enqueue（x）调用都与相同索引的Dequeue（）配对，后者返回x。本质上，它保证Dequeue（）-s检索正确epoch的元素，并且成功添加的元素不会消失。引理4.1. 考虑成功的Enqueue（x）操作<：>与= 。如果执行 包含Dequeue（）操作，该操作在返回的Head上执行FAA ，则以下语句是正确的：（1）=，（2）仲裁庭作出裁决后，(3) 如果之前获得了索引，则在尾上执行最后一次FAA时仍然有效。证据 考虑在尾上执行最后一次FAA之后执行，获得索引 。在单元格中安装线程令牌的CAS（第18行），推进epoch的CAS（第22行），以及放置其元素的CAS（第29行）必须成功。如果其中一个CAS-s失败，操作将重新启动，在Tail上执行新的FAA并获得更高的索引。要显示Enqueue（..） 将元素放置在正确的epoch中，我们证明了其他操作不会改变它锁定单元格（第18行）和 用元素替 换 线 程 令 牌 （ 第 29 行 ） 之 间 的 单 元 格epoch。 当另一个人（） 推进epoch（第22行），它首先安装它的线程令牌（第18行），这将阻止元素发布。类似地，当Dequeue（）推进epoch（第62行）时，它首先“解锁”单元（第59行），这也会导致元素发布失败。上面的讨论表明，在某些时候，单元格状态为{SafeAndEpoch：true，i/R>，Value：x}。接下来，我们证明了只有索引为的Dequeue（）可以取���在此Dequeue检索元素之前，删除和其他操作无法更改单元格epoch 由于cell epoch始终是高级的，因此它对于每个已发布的元素都是唯一的。因此，在读取单元状态的一致快照（第44- 47行）之后，Dequeue（）可以观察到仅具有epoch的������ ，因此只有当它的周期与Enqueue（..）’s现在我们证明引理陈述是正确的。根据引理，FAA（1） 在中的某个点 返回。假设“ 。在这种情况下，以下事件之一必须发生在它获得索引 之后和它获得 +1之前：(a)执行空转换（第62行）(b) 执行不安全的转换（第68行）(c)Epoch> i/R（第73行）我们表明，假设这些事件中的任何一个都会导致矛盾。在（a）的情况下，���������将历元提升到。所以���������不能用它的第二个