Locking without blocking

摘要: Nonblocking algorithms for concurrent data structures guarantee that a structure is always accessible. This in contrast to blocking which slow or halted process can render part all of the inaccessible other processes.This paper proposes technique convert most existing lock-based into nonblocking with same functionality. Our instruction-by-instruction transformation be applied any algorithm having following properties:•Interprocess synchronization established solely through use locks.•There no possiblity deadlock (e.g. because well-ordering among lock requests).In previous work, our requires only constant amount overhead per operation and, absence failures, it incurs penalty concurrency was available original structure.The techniques this may obviate need wholesale reinvention algorithms.