Concurrency technique for shared objects

摘要: In some embodiments, a Hat Trick deque requires only single DCAS for most pushes and pops. The left right ends do not interfere with each other until there is one or fewer items in the queue, then adjudicates between competing By choosing granularity greater than node, user can amortize costs of adding additional storage over multiple push (and pop) operations that employ added storage. A suitable removal strategy provide similar amortization advantages. technique leaving spare nodes linked structure allows an indefinite number pops at given end to proceed without need invoke memory allocation reclamation so long as difference remains within bounds. Both garbage collection dependent explicit implementations are described.