Vi introducerar SnapQueues - konkurrenta, låsfria köer med en linjäriserbar, låsfri global-state övergångsoperation. Denna övergång kan atomiskt växla mellan godtyckliga SnapQueue-tillstånd, och används av enqueue-, dequeue-, snapshot- och konkateteringsåtgärder. Vi visar att genomförandet av dessa operationer effektivt beror på den ihållande datastrukturen i kärnan av SnapQueue. Denna oföränderliga stöddatastruktur är en utbytbar kärna av SnapQueue och driver dess prestandaegenskaper. Konstruktionen möjliggör resonemang om samtidig drift körtid på ett funktionellt sätt, frånvarande från konvergensöverväganden. Vi presenterar en stöddatastruktur som möjliggör O(1) köoperationer, O(1) ögonblicksbild och O(log n) atomisk samtidig konkatering. Vi visar att SnapQueue enqueue-operationen uppnår upp till 25 % högre prestanda, medan dequeue-operationen har prestanda som är identisk med standardlåsfria samtidiga köer.
FlowPools är baserade på en låsfri kö datastruktur, liknande SnapQueue REF.
SnapQueue: lock-free queue with constant time snapshots
{'venue': 'Scala@PLDI', 'journal': None, 'mag_field_of_study': ['Computer Science']}