ACM SIGAPP Applied Computing Review · 2015 · 24 citations · 5 references
ComputingComputer EngineeringComputer ScienceParallel AlgorithmsParallel ComputingReal-time SystemsBuffer ManagementCpu SchedulingDeadlock AvoidanceParallel Algorithm DesignParallel Data StructuresBuffer DesignLock-free Data StructuresNetwork RoutingRing Buffer ManagementRing BuffersWait-free AlgorithmsWait-free Data StructuresWait-free Synchronization
The ring buffer is a staple data structure used in many algorithms and applications. It is highly desirable in high-demand use cases such as multimedia, network routing, and trading systems. This work presents a new ring buffer design that is, to the best of our knowledge, the only array-based first-in-first-out ring buffer to provide wait-freedom. Wait-freedom guarantees that each thread completes its operation within a finite number of steps. This property is desirable for real-time and mission critical systems. This work is an extension and refinement of our earlier work. We have improved and expanded algorithm descriptions and pseudo-code, and we have performed all new performance evaluations. In contrast to other concurrent ring buffer designs, our implementation includes new methodology to prevent thread starvation and livelock from occurring.
5
Intel® threading building blocks
Chuck Pheatt · Journal of computing sciences in colleges · 2008 · 127 citations