没有合适的资源?快使用搜索试试~ 我知道了~
01 ...140最先进的LCRQ并发队列算法不需要CAS20RaedRomanov高等经济学院俄罗斯圣彼得堡 raid_r@mail.ru0Nikita KovalJetBrains阿姆斯特丹,荷兰ndkoval@ya.ru0摘要0并发队列可以说是高负载应用中最重要的数据结构之一,要求其具有极高的速度和可扩展性。要实现这些特性是非常困难的。早期的解决方案,如Michael和Scott的经典队列,将元素存储在并发链表中。据说这种设计不可扩展且内存效率低下。现代的解决方案利用了Fetch-and-Add指令来提高算法的可扩展性,并将元素存储在数组中以减少内存压力。其中最著名且快速的算法之一是LCRQ。其设计的主要缺点是依赖于原子的CAS2指令,在大多数现代编程语言(如Java、Kotlin或Go)以及一些体系结构中不可用。本文介绍了LPRQ算法,这是对原始LCRQ设计的可移植修改,消除了所有CAS2的使用。相比之下,它只使用标准的Compare-and-Swap和Fetch-and-Add原子指令进行同步。我们的实验证明,LPRQ提供了与经典LCRQ算法相同的性能,比不使用CAS2的现有解决方案快1.6倍。0CCS概念:计算方法→并发算法;共享内存算法。0关键词:并发队列,环形缓冲区,无锁01 引言队列是并发编程中最基本和实用的数据结构之一。人们进行了大量研究,以开发快速有效的解决方案。第一个无锁算法是建议的0Michael和Scott在近30年前提出的[16],开启了构建高效非阻塞数据结构的时代。他们的设计基于一个链表结构,通过Head和Tail指针来维护;Enqueue(..)和Dequeue()通过原子的Compare-and-Set(CAS)指令来更新它们。最近,这个设计发生了很大的改变,利用了Fetch-and-Add(FAA)指令来提高算法的可扩展性,并将元素存储在数组中以减少内存压力。这个家族中最著名的算法之一是LCRQ[18],由Morrison和Afek于2013年提出。无限数组队列。LCRQ的设计灵感来自于一个直接的队列算法,该算法通过位置计数器来操作无限数组进行Enqueue(..)和Dequeue()操作。要添加一个新元素,Enqueue(..)通过Fetch-and-Add递增Tail计数器,获得递增之前的值t。之后,它将元素存储到保留的单元格A[t]中并完成。Dequeue()操作对称地工作,递增其Head计数器并从保留的单元格A[h]中提取元素。下图展示了在插入和提取元素时数据结构的变化。0Tail=1 Tail=0 Head=00Tail=1Head=10enq(a) ... deq: a ...0图1. 无限数组队列结构。0由于并发性,Enqueue(..)可能会增加Tail并暂停,因此Dequeue()可能会预留一个仍为空的单元格。为了取得进展,Dequeue()通过将其状态移动到特殊的⊥值来毒化空单元格,并重新开始。之后,Enqueue(..)观察到单元格已被破坏并重新开始;它通过CAS安装元素以进行同步。下面是相应的伪代码。LCRQ设计。Afek和Morrison详细阐述了这个想法,并开发了一种极其高效的LCRQ算法,使用环形缓冲区作为底层,称之为CRQ-s(Concur- rent RingQueues)。粗略地说,CRQ是一个有界队列,对于Enqueue(..)可能失败的条件有宽松的语义。类似于无限数组队列,Enqueue(..)递增其Tail计数器并处理0未经许可,任何个人或课堂使用者均可制作本作品的数字副本或印刷副本,但不得出于盈利或商业优势的考虑制作或分发副本,并且副本应携带本声明和首页面的完整引用。对于除作者之外的其他组成部分,版权所有者必须受到尊重。允许带有信用的摘要。要进行其他复制、重新发布、在服务器上发布或重新分发到列表上,需要事先获得特定的许可和/或费用。请向Permissions@acm.org申请权限。 PPoPP '23,2023年2月25日至3月1日,加拿大蒙特利尔,QC,加拿大©2023版权归所有者/作者所有。出版权由ACM许可。ACM979-8-4007-0015-6/23/02…$15.00 https://doi.org/10.1145/3572848.357748514 }150PPoPP’23, 2023年2月25日至3月1日,加拿大蒙特利尔,Raed Romanov和Nikita Koval01 Head , Tail : Long // 64位计数器 2 A : E [] // 类型为E的无限数组 34 fun Enqueue ( item : E ) = while (true) { 5 t := Tail . FAA( 1 )06 if ( A [ t ]. CAS(null , item )) return07 } 8 9 fun Dequeue () : E = while (true) { 10 if ( Head >=Tail ) return null // 是否为空?011 h := Head . FAA( 1 )012 if ( A [ h ] == null && A [ h ]. CAS(null , ⊥ )) continue013 return A [ h ]0清单1. 无限数组队列算法。0单元格A[t %R],其中R是环形缓冲区的大小。对称地,Dequeue()递增Head并处理单元格A[h %R]。一旦当前环形缓冲区已满,Enqueue(..)关闭它以进行进一步插入,并创建一个新的CRQ,构建它们的链表。尽管高层次的思想是相似的,但将数组变成循环的完全改变了同步机制。在无限数组队列中,每个单元格只能由一个Enqueue(..)和一个Dequeue()处理,使得它们之间的同步变得简单直接。在环形缓冲区结构中,每个R个Enqueue(..)和Dequeue()尝试操作相同的单元格在大小为R的环形缓冲区中。这导致了一些潜在的问题,例如在队列的中间添加元素或无序的删除。为了解决这些竞争条件,LCRQ为每个单元格配备了一个64位的时期计数器。直观地说,它确保Dequeue()只从其h /R时期中提取元素,而如果同一时期的逆Dequeue()已经处理并跳过了该单元格,则Enqueue(..)永远不会安装该元素。LCRQ的不可移植性。LCRQ设计的主要问题是它的可移植性。每个单元格都配备了一个时期计数器,LCRQ通过CAS2原子指令与单元格状态一起更新该计数器。尽管这个指令在现代硬件架构中越来越受欢迎,但大多数编程语言(如Java、Kotlin或Go)不提供这样的原语,因此无法在其中实现LCRQ。已经提出了几种方法来消除CAS2的使用。Ramalhete[22]提出了一个简单的无锁队列,它永远不会重用环形缓冲区,在内部数组末尾时分配一个新的缓冲区。这个设计类似于无限数组队列,不使用时期,只允许一个Enqueue-Dequeue对处理单元格。Yang和Mellor-Crummey[27]扩展了这个方法以提供等待自由。这些工作和我们的实验表明,LCRQ超过了这两个解决方案。摆脱CAS2的另一种方法是操作32位值和32位时期,可以将它们打包成一个64位字,并通过CAS原子地更新。Nikolaev[20]使用这样的队列构建他的SCQ环形缓冲区算法,0维护一个元素数组和两个32位索引队列,这些队列引用了用于Enqueue(..)的空闲单元和用于Dequeue()的占用单元。Feldman和Dechev[5]以另一种方式解决了这个问题,将时代字段集成到元素中。除此之外,他们的算法将时代存储在空单元中,而在具有垃圾收集的大多数语言(如Java或C#)中,这在技术上是不可能的。与LCRQ相比,这两种解决方案都显着低效。我们的贡献。在本文中,我们提出了LPRQ并发队列算法,这是对LCRQ的便携式修改,不需要CAS2。从本质上讲,我们对原始LCRQ设计应用了两种技术。首先,我们在Dequeue()中摆脱了CAS2,使Enqueue(..)操作负责维护时代。然而,它应该将元素仅放在正确的时代中,LCRQ通过CAS2解决了这个问题。相反,LPRQ通过安装线程唯一标识符来“锁定”单元,检查时代,然后将标识符替换为该元素。从实现的角度来看,这个线程唯一标识符通常是对当前运行线程的引用(例如,在JVM上是java.lang.Thread实例)。我们已经在C++中实现了LPRQ算法,并将其与原始LCRQ解决方案和不需要CAS2的各种队列进行了比较。我们的实验表明,我们的LPRQ算法提供与LCRQ相同的性能,超过其他解决方案的最佳性能高达1.6倍。02准备工作内存模型和原子操作。为了简单起见,我们假设具有顺序一致的内存模型。除了普通的读写操作,我们还使用比较并交换(CAS)和加法交换(FAA)等原子操作,这些操作在所有现代编程语言中都是可访问的。在LCRQ算法讨论中,我们还使用了不可移植的CAS2指令,它更新两个连续(而不是任意)的内存位置;在x86上它也被称为cmpxchg16b。内存回收。为了简单起见,我们假设环境提供了垃圾收集器。对于手动内存回收,可以使用诸如Hazard Pointers[15]或Hazard Eras[23]等技术。可为空性。原始的LCRQ算法和我们的LPRQ修改假设元素类型E提供了一个特殊的null值,该值永远不会插入队列。我们用它来指定空数组单元。在Dequeue()中返回null表示队列为空。线程标记。我们的PRQ算法假设环境提供线程唯一标记符,表示为���������,它可以存储在与元素相同的位置上。简而言之,Enqueue(..)在存储元素之前在单元中安装这样的标记符,以确保它在正确的时代中执行操作。在实践中,线程标记可以通过将值的单个位用于区分它们与元素来实现。如果设置了这个位,其他位存储拥有标记符的线程的索引。否则15}16}29}37 }01234567160最先进的LCRQ并发队列算法不需要CAS2 PPoPP'23,2023年2月25日至3月1日,加拿大蒙特利尔0其他位存储元素。在某些不允许“位窃取”的平台上,可以使用对当前运行线程的引用作为线程标记。例如,在JVM上,可以通过Thread.currentThread()有效地获得java.lang.Thread实例。03LPRQ算法我们首先讨论原始的LCRQ设计,它使用不可移植的CAS2指令。然后,我们通过两个步骤消除了它的使用。首先,我们在Dequeue()中摆脱了CAS2,使Enqueue(..)操作负责维护每个单元的时代。接下来,我们通过使用线程唯一标识符来消除Enqueue(..)中的CAS2,以“锁定”单元并安全执行其余的同步操作。03.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队列类似的方式将这个新的CRQ放在当前CRQ之后(第10-15行)。如果并发的Enqueue(..)已经添加了一个新的CRQ,则当前操作重新开始。Dequeue()操作操作HeadCRQ并尝试从中提取一个元素,在成功时完成(第19-21行)。如果提取失败,则当前CRQ为空,而队列可能仍包含非空的CRQ-s。因此,Dequeue()读取下一个CRQ,如果不存在则返回null(第23行)。否则,并发的Enqueue(..)-s可能会在我们观察到它为空并读取crq.Next之间将元素添加到当前CRQ。因此,Dequeue()再次尝试从当前队列中提取元素(第25行),在成功时完成(第26行)。否则,当前CRQ为空且已关闭,所以Dequeue()将Head指针更新为下一个CRQ并重新开始(第28行)。高级环形缓冲设计。我们将注意力转向CRQ的实现。图2显示了环形缓冲01 class LCRQ {2 Head,Tail: CRQ03 4 fun Enqueue(item:E) = while (true) {05 //快速路径:加入当前的CRQ06 crq := tail07 if (crq.Enqueue(item)) return08 //慢速路径:Tail已满,添加新的CRQ09 newTail := CRQ(); newTail.Enqueue(item)010 if (crq.Next.CAS(null,newTail)) {011 Tail.CAS(crq,newTail)012 return013 } else {014 Tail.CAS(crq,crq.Next)017 18 fun Dequeue():E = while (true) {019 crq := Head020 res := crq.Dequeue()021 if (res!= null) return res022 //失败,这个队列是空的吗?023 if (crq.Next == null) return null024 //'crq'已关闭但可能存储元素025 res := crq.Dequeue()026 if (res!= null) return res027 //'crq'为空,更新HEAD并重新开始028 Head.CAS(crq,crq.Next)030 } 31 class CRQ {32 Next:CRQ = null033 //将项目加入队列并返回true034 //或关闭CRQ并返回false035 fun Enqueue(item:E):Bool036 fun Dequeue():E //如果CRQ为空则返回null0第2段。高级LCRQ[18]实现操作CRQ-s。LPRQ的高级设计与之相同,唯一的区别是将CRQ替换为来自列表4的PRQ。0结构,它基于大小为R的数组A来存储带有Head和Tail定位计数器的元素;它们的值对R取模指定了下一个元素插入和提取的索引。最初,所有的数组单元都是空的,存储null。环形缓冲的当前大小等于(Tail-Head),并且永远不会超过R。0d0Tail=9 Head=50a b c0A:0图2. 大小为 � = 8 的环形缓冲区示例。 Head % R指向要提取的下一个元素,而 Tail % R指向要放置元素的下一个单元格。000010111170PPoPP’23,2023年2月25日至3月1日,加拿大蒙特利尔,Raed Romanov和Nikita Koval0enq(x) enq(y) deq: y0y x0deq: x0enq(v) T10T20x0x0Tail0Tail=1 Tail=30Head=20状态0Tail.FAA(1): 00(a) 从未来出队破坏了FIFO语义。0deq: x0deq: null T10T20状态 x y x0Head=2 Tail=2 Tail=0Head=30enq(y)0Head=10Tail=20deq: y0Head.FAA(1): 00(b) 从过去出队破坏了FIFO语义。0图3.这两个示例显示了Dequeue()必须仅从周期相同的共轭Enqueue(..)中获取元素。这里,两个线程访问一个大小为 � = 2的环形缓冲区。0被抢占。执行切换到 � 2,执行两个 Dequeue() 操作。(回想一下 Head 已经被 � 1 增加了)。第一个 Dequeue()操作从第1个单元格获取索引并在周期0中提取�。第二个操作从第0个单元格获取索引并在周期1中提取�。与前一个示例类似,元素以相反的顺序提取,违反了FIFO队列的语义。确保一个元素只能在正确的周期上获取的一种方法是将每个单元格与一个时代(epoch)关联起来。当Enqueue(..)将一个元素放入单元格时,它还将单元格的时代更新为其操作周期。反过来,只有当单元格的时代与其周期匹配时,Dequeue()才会提取元素。图4显示了这种方案如何修复图3b中的错误执行。执行从周期0开始添加 � 和 �。之后,� 1调用Dequeue(),增加Head并被抢占。执行切换到 �2,执行两个 Dequeue() 操作。与前一个示例类似,第一个Dequeue() 从第1个单元格获取索引并在周期0中提取�。然而,� 2 中的下一个 Dequeue() 无法再检索�,因为第0个单元格的时代是0,而操作周期是1。因此,这个Dequeue() 重新开始,发现环形缓冲区为空,并返回null。在执行切换回 � 1 后,相应的 Dequeue()完成,从第0个单元格中提取 �。0图 4. 时代有助于保持元素的FIFO顺序。0CRQ算法。我们需要以原子方式更新单元格时代及其状态;否则,Dequeue()可能会观察到错误时代的元素并提取它,从而破坏FIFO语义。CRQ通过硬件的CAS2指令实现了这种原子更新。列表3呈现了CRQ的伪代码。单元格数据结构有一个64位的Value字段(line 5)和一个64位的SafeAndEpoch字段(line2),后者将特殊的Safe标志与Epoch打包在一起。除了Head和Tail计数器,CRQ还存储了Closed标志(line9),它表示队列是否关闭插入操作,并且还存储了指向下一个CRQ的指针,该指针在列表2中由LCRQ使用。Enqueue(..)和Dequeue()操作以迭代的方式进行(参见第13行和第34行的循环)。每次迭代都通过对Tail(line 14)或Head(line35)进行FAA来开始,获取迭代的索引和其周期。在每次01 最初,CRQ将Tail的更高位保留以存储Closed标志,为了简单起见,我们将其放入单独的变量中。4}27}32}33 }47}53}59}62}63}66 }180最先进的LCRQ并发队列算法不需要CAS201 结构体 Cell < E > { 2 SafeAndEpoch : packed {// 64 位03 Safe : Bool = true , Epoch : Long = 005 Value : E = null06 } 7 8 Head : Long = 0, Tail : Long = 0 9 Closed : Bool = false10 A : Cell < E >[ R ] 11 Next : CRQ < E > = null //指向下一个CRQ的指针 12 13 fun Enqueue ( item : E ) : Bool =while (true) { 14 t := Tail . FAA( 1 )015 如果 Closed 返回 false016 cycle := t / R; i := t % R017 < safe , epoch > := A [ i ]. SafeAndEpoch018 value := A [ i ]. Value019 20 如果 value == null 且 // 单元格为空021 // 并且入队未被超越022 如果 epoch <= cycle 且 ( safe 或者 Head <= t )) {023 // 入队过渡024 如果 ( A [ i ]. CAS2( << safe , epoch > , null > ,025 << true , cycle > , item > ))026 返回 true028 // 队列是否已满?029 if (t - Head >= R) {030 Closed := true031 return false034 fun Dequeue(): E = while (true) { 35 h :=Head.FAA(1)036 周期 := h / R; i := h % R037 while (true) { // 尝试更新单元状态038 < safe, 时代 > := A[i].SafeAndEpoch039 值 := A[i].Value040 41 when { // 根据图5进行转换042 时代 == 周期 && 值 != null -> {043 // 出队转换044 if (A[i].CAS2(<< safe, 时代 >, 值 >,045 << safe, 周期 + 1 >, null >))046 return value048 时代 <= 周期 && 值 == null -> {049 // 空转换050 if (A[i].CAS2(<< safe, 时代 >, 值 >,051 << safe, 周期 + 1 >, 值 >))052 break054 时代 < 周期 && 值 != null -> {055 // 不安全转换056 if (A[i].CAS2(<< safe, 时代 >, 值 >,057 << false , 时代 > , 值 > ))058 break060 // 否则,时代 > 周期061 else -> break // deq被超越了064 // 队列是否为空?065 if (Tail <= h + 1) return null0列表3。Morrison和Afek [18]的CRQ算法。0迭代过程中,操作读取单元状态(第17-18行,38-39行)并执行更新转换、重新启动或完成。图5说明了可能的单元状态转换。考虑带有索引�和周期�的Dequeue()的迭代。如果单元的时代大于�(第61行),则此Dequeue()尝试在计数器递增和读取单元时代之间被超越。在这种情况下,此Dequeue()尝试失败,操作重新启动。否则,执行以下转换之一:0•如果单元包含一个元素且时代与迭代周期�匹配,则执行出队转换。Dequeue()尝试提取元素并通过CAS2(第44行0•如果单元为空,则执行空转换,防止Enqueue(..)在周期�上放置元素。为此,Dequeue()在单元为空时将时代原子0•最后,如果单元包含一个元素,但时代低于�,则执行不安全转换。为了安全地跳过此单元,Dequeue()必须防止在周期�上安装元素。诀窍是重置Safe位(第56行),使Enqueue()只能在Head低于全局单元索引时安装元素(第22行)。0入队转换e0x0c0CAS20出队转换0x0c0CAS20空转换e0CAS20不安全转换0x0e0x0e0CAS20c+10c+10图5。CRQ中的单元状态转换:�是操作周期,�是转换前的单元时代。0无论何时执行转换的CAS2失败,单元更新过程都会重新启动(第37行的循环)。同时,如果Dequeue()在不提取元素的情况下完成迭代,它会读取Tail来检查队列是否为空(第65行),在这种情况下返回null并在队列可能有元素时重新启动。0现在考虑Enqueue(..)的迭代。在对Tail执行FAA之后,Enqueue(..)检查队列是否关闭(第15行)。在这种情况下,它立即返回false。然后,如果0为简单起见,我们省略了Morrison和Afek[18]提出的Dequeue()也可以将Tail提前到当前的Head的优化。001190PPoPP’23,2023年2月25日至3月1日,加拿大蒙特利尔 Raed Romanov和Nikita Koval0如果单元为空且未超越Enqueue(..)(第20-22行),则尝试执行入队转换,并在成功时返回true。失败时,它检查队列是否可能已满,并且应该关闭(第29行)。如果是这样,Enqueue(..)将Closed标志更新为true(第30行),防止进一步插入,并返回false。如果此CRQ还有剩余空间,则Enqueue(..)继续下一次迭代。入队转换(第24行)将元素放入单元并将时代推进到迭代周期。值得注意的是,操作必须验证它在高周期的Dequeue()未被超越(第22行)。此外,如果设置了Safe位,Enqueue(..)不能依赖于单元时代来确保操作未被超越。而是读取当前的Head值并将其与迭代索引进行比较(第22行)。在成功的转换中,Enqueue(..)还将Safe位设置为true,从而恢复单元。03.2PRQ算法为了构建我们的PRQ算法,我们对CRQ应用了两个变换。首先,我们移动周期编号并修改转换的前提条件,从而可以将Dequeue()中的所有CAS2使用替换为普通的CAS。其次,我们提出了一种在Enqueue(..)中模拟CAS2的高效方法,它使用一系列的CAS来将元素放置在正确的时代中。与传统的k-CAS算法[8]不同,我们的方法不使用描述符,也不涉及分配和内存间接访问。消除Dequeue()中的CAS2。我们对原始的CRQ算法进行了以下更改:0• 我们使用�初始化Head和Tail,因此操作从周期1开始(与CRQ中的0不同)。0• 只有当单元时代严格小于操作周期时,Enqueue(..)才有资格放置元素。0•当Enqueue(..)放置元素时,它将单元时代提高到操作周期。因此,成功的Enqueue(..)始终会增加单元时代。0•当Dequeue()提取元素时,它保持单元时代不变。唯一的例外是空转换,它将时代提高到操作周期。0这些改变有效地将Dequeue()中的所有CAS2转换为双比较单交换操作,只在成功检索时更改Value字段,并在空和不安全转换的情况下更新SafeAndEpoch。我们需要添加另一个元素以通过普通CAS实现它们。直观地说,Dequeue()在更新单元之前应该读取一致的快照状态。就像在CRQ中一样,它先读取SafeAndEpoch,然后是Value(第38-39行),还要验证SafeAndEpoch是否已更改。如果是这样,那么正确的单元快照已被获得,因为时代始终增加,并且当Enqueue(..)增加单元时,Safe标志仅重置。如果未获得快照,则Dequeue()尝试再次获取。0入队转换e0x0c0CAS20出队转换0x0c c0存储0空转换e c0CAS0不安全的转换0x0x0CAS0图 6. 修改后的 CRQ 算法中的单元状态转换:� 是操作周期,�是转换之前的单元时期。0图 6 总结了修改后的 CRQ算法中的单元状态转换。我们在附录 A中提供了相应的伪代码。在 Enqueue(..) 中模拟CAS2。通过上述更改,只有 Enqueue() 需要 CAS2来原子地放置其元素并增加时期(清单 3 中的第 24行)。我们提供了一种智能方法,通过图 7中的三步过程模拟这个 CAS2:01. 单元预留。为了放置元素并增加时期,Enqueue(..)首先通过将一个线程唯一的标记 ����������安装到其中来“锁定”单元。(关于实现,当前运行的线程的引用可以用作线程标记。)02. 时期提升。接下来,它将单元的时期增加到操作周期。03. 元素发布。最后,Enqueue(..) 用元素替换其����������。关键思想是当单元存储线程标记时,不允许其他操作更改单元时期,因此当 Enqueue(..)在最后一步将其替换为元素时,可以保证单元时期没有被更改。0x0锁定单元0推进时期0发布元素0图 7. 在 Enqueue(..) 中模拟 CAS2将元素放置正确的过程。这里,线程 � 在周期 1 上插入 �。0伪代码。清单 4 呈现了我们的 PRQ算法的伪代码。至于数据结构,它与 CRQ的数据结构相同(清单 3),唯一的区别是 PRQ 将 Head 和Tail 初始化为�,而不是 0(第 2 行)。Enqueue(..)操作通过增加其 Tail 计数器、获取索引 h(第 5行)开始。然后,它检查单元是否为空或已锁定以及操作是否未被超越,如果是的话就重新开始(第 13 - 15行)。否则,它尝试按照上述三步过程放置元素(第 18 - 29行)。Dequeue() 操作通过增加其 Head 计数器并获取索引h(第 41行)开始。接下来,它快照单元,获取其时期、安全标志和单元值(第 44 - 47 行),然后进行列出的转换之一:26}31}37}38 }3954}65}71}74}75}78 }200现代 LCRQ 并发队列算法不需要 CAS2 PPoPP’23,2023 年 2 月 25 日至 3 月 1 日,加拿大蒙特利尔01 // 初始化 2 Head = R; Tail = R 3 4 fun Enqueue(item: E): Bool= while (true) { 5 t := Tail.FAA(1)06 if (Closed) return false07 8 cycle := t / R; i := t % R09 10 := A[i].SafeAndEpoch011 value := A[i].Value012 13 if (value 是 null 或 � && // 未被占用014 // 并且没有被超越015 epoch < cycle && (safe || Head <= t)) {016 17 // 使用线程标记锁定单元018 if (!A[i].Value.CAS(value, ����������))019 goto checkOverflow020 21 // 推进时期022 if (!A[i].SafeAndEpoch.CAS(,023 )) {024 A[i].Value.CAS(����������, null) // 清理025 goto checkOverflow027 28 // 发布元素029 if (A[i].Value.CAS(����������, item))030 return true032 33 checkOverflow: // 队列是否已满?034 if (t - Head >= R) {035 Closed := true036 return false040 fun Dequeue(): E = while (true) { 41 h :=Head.FAA(1)042 cycle := h / R; i := h % R043 while (true) { // 尝试更新单元状态044 := A[i].SafeAndEpoch045 value := A[i].Value046 if ( != A[i].SafeAndEpoch)047 continue // 单元的不一致视图048 49 when {050 epoch == cycle && value 不是 null 或 � -> {051 // 出队转换052 A[i].Value := null053 return value055 epoch <= cycle && value 是 null 或 � -> {056 // 空转换057 // 解锁单元058 if (value is � &&059 !A[i].Value.CAS(value, null))060 continue061 // 推进时期062 if (A[i].SafeAndEpoch.CAS(,063 )064 break066 epoch < cycle && value 不是 null 或 � -> {067 // 不安全的转换068 如果 A[i].SafeAndEpoch.CAS(,069 ))070 break072 // 时期 > 周期073 else -> break // deq is overtaken076 // 队列是否为空?077 如果 Tail <= h + 1 则返回 null0清单 4. PRQ 算法。黄色突出显示的操作模拟了 CAS2。0• 当单元被占用且时期与迭代周期匹配时(第 50行),执行 Dequeue 转换 ——用 null (第 52 行)替换存储的元素并完成(第 53行)。由于在单元被占用时无法更改时期,所以在这里可以使用普通存储而不是 CAS。0• 空转换在单元为空或已锁定且时期低于操作周期时应用(第 55行)。为此,Dequeue() 首先用 null(第 59行)替换线程标记,然后推进时期到操作周期(第 62行)。如果这些 CAS中的任何一个失败,单元更新过程将重新开始。0•如果一个占用的单元的时期低于操作周期,就会执行不安全的转换。与 CRQ 类似,Dequeue() 会重置 Safe 位(第 68行)并重新开始。0值得注意的是,当 Enqueue(..) 重新开始时,它还会读取 Head计数器以验证队列是否已满(第 34行),在这种情况下关闭队列(第 35 行),否则返回 false。04 正确性 与 LCRQ 类似,我们的 LPRQ算法构建了一个环形缓冲区的链表,其遵循 tantrum队列的语义[18]。具体而言,Enqueue(..)可以非确定性地拒绝插入一个元素并关闭环形缓冲区。一旦关闭,所有进一步的插入尝试都将失败。为了证明 LPRQ的正确性,我们证明了我们的 PRQ环形缓冲区是一个可线性化的 tantrum 队列。由于高层部分LPRQ 操作环形缓冲区(参见清单 2)与 LCRQ的操作是相同的,我们不再分析它。PRQ的线性化。为了证明 PRQ 是一个可线性化的 tantrum队列,我们遵循 LCRQ 作者的方法[18]。考虑一次操作 <��: ���>的执行�,其中��∈{���,���},并返回���。我们假设操作��在�的第一个和最后一个事件之间是活动的。我们将由 Dequeue() / Enqueue(..)操作��执行的最后一个 Head.FAA(1) / Tail.FAA(1)调用的结果表示为�����(��)。210PPoPP’23,2023年2月25日至3月1日,加拿大蒙特利尔 Raed Romanov和Nikita Koval0首先,我们证明每个成功的Enqueue(x)调用与具有相同索引的Dequeue()配对,后者返回x。这实际上保证了Dequeue()检索到正确时期的元素,并且成功添加的元素不会消失。0引理4.1.考虑一个成功的Enqueue(x)操作,其中AAA(AAA) =AAA。如果执行AAA包含一个Dequeue()操作AAA,该操作在Head上执行FAA并返回AAA,则以下陈述正确:0定理4.2.PRQ是一个可线性化的tantrum队列。0证明。考虑AAA在Tail上执行最后的FAA之后的执行,获取索引AAA。在将线程令牌安装在单元格AAA[AAA %AAA](第18行)的CAS,将时期前进(第22行)的CAS以及将其元素AAA(第29行)的CAS之前,必须成功。如果其中一个CAS失败,操作将重新启动,在Tail上执行新的FAA并获得更高的索引。为了显示Enqueue(..)将元素放置在正确的时期中,我们证明其他操作在
下载后可阅读完整内容,剩余1页未读,立即下载
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)