To answer that, I need to basically explain the difference between lock-free and locking data structures. If we consider a locking data structure, say a binary

To answer that, I need to basically explain the difference between lock-free and locking data structures. If we consider a locking data structure, say a binary tree using a mutex to serialise access, we see a couple of things; 1. when a thread holds the mutex, no other thread can get any work done 2. if a thread holding the mutex is idled by the operating system, every other thread cannot get any work done on the tree until that thread is finally swapped back in 3. if a thread is holding the mutex when an interrupt occurs, the interrupt handler cannot use the tree, because the tree may be in an invalid state - the mutex holding thread could be right in the middle of adjusting a bunch of pointers The fact that thread can be prevented from working by other threads is what is meant by saying it is a locking dats structure. Lock-free data structures are implemented such that, broadly speaking (there are nuances in this which are not necessary here), all threads can continue with their work, regardless of how many other threads are using the data structure or whether or not they've been idled by the operating system. In short, a lock-free data structure is written in such a way that all possible operations, and any number of them in any order can happen at ANY time, i.e. between the execution of one instruction and the next, and the data structure remains valid at all time. It is this which makes the data structure process, thread and interrupt safe. Typically, lock-free data strutures achieve this though the use atomic operations and careful design. (Superior designs also distribute memory accesses away from just one or a few pointers, an improvement which is necessary but insufficient for scalability).