Consistent shared queue without using locks

What is it about?

When it comes to cloud computing or multi-core CPUs, we can’t use the regular data structures, called sequential, we use everyday. Since some processes might do some operation in parallel and the values stored may become inconsistent. Problems like data race could happen which lead us to create shared data structures safe to used by concurrent processes. One way is to use locks on the data structure, whenever some process wants to read or write a value, it is required to have the acquire the lock and when’s its work is finished it should release the lock. One problem with solution is that once some process has the lock, other processes waiting cannot have progress. This solution has some other problems which has led people to show interest in data structures without using locks. There is a more general progress condition defined as lock-freedom which requires after sufficient time at least one process can have progress. In this work we are interested in lock-free algorithms.

Featured Image