Google Interview Question
Software Engineer / DevelopersCountry: United States
Are you sure about your interpretation of "non-blocking threadsafe" being "without aquring a lock"?
In your implementation you are effectively using a spinlock which is still a lock.
That's a good question.
Yes there is a spin lock in the code above. However, if you remove the sleeping part, it becomes polling the CAS variable which is what the wait-free implementations like ConcurrentLinkedQueue do as well. If you look at the code of CLQ you will see there is just the same while loop on CAS variable.
From Wikipedia page on non-blocking algorithms "In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress."
From chapter 7 (spin locks) of The Art of Multiprocessor Programming "Any mutual exclusion protocol poses the question: what do you do if you can- not acquire the lock? There are two alternatives. If you keep trying, the lock is called a spin lock, and repeatedly testing the lock is called spinning, or busy– waiting. The Filter and Bakery algorithms are spin locks. Spinning is sensi- ble when you expect the lock delay to be short. For obvious reasons, spinning makes sense only on multiprocessors. The alternative is to suspend yourself and ask the operating system’s scheduler to schedule another thread on your proces- sor, which is sometimes called blocking. Because switching from one thread to another is expensive, blocking makes sense only if you expect the lock delay to be long."
When writing lock free, it is important to assign ownership of variables. For a Single producer, Single consumer following is guaranteed to be thread safe -
public static class LockFreeQueue<T> {
private T[] buffer; // Bounded buffer.
private final int size; // Max item = size - 1;
private volatile int head; // Dequeue from head. Owned by Consumer.
private volatile int tail; // Enqueue at tail. Owned by producer.
public LockFreeQueue(T[] buffer) {
this.size = buffer.length;
this.buffer = buffer;
this.head = 0;
this.tail = 0;
}
public T dequeue() {
// Check if queue is empty.
if (tail == head) {
return null; // tail can only be incremented
}
// Fetch item. head and buffer location is owned by consumer.
T item = buffer[head % size];
head++; // commit
return item;
}
public boolean enqueue(T obj) {
// Check if queue is full.
if (tail == head + size - 1) {
return false;
}
buffer[tail % size] = obj;
tail++; // commit
return true;
}
}
public void verify() {
final LockFreeQueue<String> queue = new LockFreeQueue<String>(new String[2]);
final int N = 10000000;
System.out.println("Testing ..");
Thread producer = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < N; ++i) {
while(!queue.enqueue("" + i));
}
}
});
Thread consumer = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < N; ++i) {
String item;
while((item = queue.dequeue()) == null);
if (Integer.parseInt(item) != i) {
throw new RuntimeException("FIFO guarantee broken");
}
}
}
});
producer.setDaemon(false);
consumer.setDaemon(false);
producer.start();
consumer.start();
}
Here head is owned by consumer and tail by producer. The cell at tail % size is owned by producer. Other cells with item is owned by consumer.
For precise definitions you can check books like "The Art of Multiprocessor Programming". Otherwise, "Java Concurrency in Practice" provides a pretty good idea in Chapter 15.
"non blocking" roughly means where threads are not blocked waiting to acquire some lock. Just combine that with what thread-safe means, so you have - code where threads do not wait to acquire some lock and still it works correctly with multiple threads.
Here's an attempt to do this using an AtomicBoolean flag to guard the non-threadsafe queue:
- DevGuy January 14, 2014