What is "non-blocking" concurrency and how is it different than normal concurrency?

1. What is "non-blocking" concurrency and how is it different than normal concurrency using threads? Why don't we use non-blocking concurrency in all the scenarios where concurrency is required? Is there overhead for using non-blocking concurrency?
2. I have heard that non-blocking concurrency is available in Java. Are there any particular scenarios where we should use this feature?
3. Is there a difference or advantage to using one of these methods with a collection? What are the trade-offs?

Example for Q3:

class List   
{  
    private final ArrayList<String> list = new ArrayList<String>();

    void add(String newValue) 
    {
        synchronized (list)
        {
            list.add(newValue);
        }
    }
}  

vs.

private final ArrayList<String> list = Collections.synchronizedList(); 

The questions are more from a learning/understanding point of view. Thanks for attention.

Solution 1:

What is Non-blocking Concurrency and how is it different.

Formal:

In computer science, non-blocking synchronization 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. (wikipedia)

Informal: One of the most advantageous feature of non-blocking vs. blocking is that, threads does not have to be suspended/waken up by the OS. Such overhead can amount to 1ms to a few 10ms, so removing this can be a big performance gain. In java, it also means that you can choose to use non-fair locking, which can have much more system throughput than fair-locking.

I have heard that this is available in Java. Are there any particular scenarios we should use this feature

Yes, from Java5. In fact, in Java you should basically try to meet your needs with java.util.concurrent as much as possible (which happen to use non-blocking concurrency a lot, but you don't have to explicitly worry in most cases). Only if you have no other option, you should use synchronized wrappers (.synchronizedList() etc.) or manual synchronize keyword. That way, you end up most of the time with more maintainable, better performing apps.

Non-blocking concurrency is particularly advantageous when there is a lot of contention. You can't use it when you need blocking (fair-locking, event-driven stuff, queue with maximum length etc.), but if you don't need that, non-blocking concurrency tends to perform better in most conditions.

Is there a difference/advantage of using one of these methods for a collection. What are the trade offs

Both have the same behavior (the byte code should be equal). But I suggest to use Collections.synchronized because it's shorter = smaller room to screw up!

Solution 2:

What is Non-blocking Concurrency and how is it different than Normal Concurrency using Threads.

Non-blocking concurrency is a different way to coordinate access between threads from blocking concurrency. There is a lot of background (theoretical) material out there, but the simplest explanation (as it seems that you're looking for a simple, hands-on answer), is that non-blocking concurrency does not make use of locks.

Why dont we use "non-blocking" Concurrency in all the scenarios where concurrency is required.

We do. I'll show you in a bit. But it is true that there aren't always efficient non-blocking algorithms for every concurrency problem.

are there any overheads for "non-blocking"

Well, there's overhead for any type of sharing information between threads that goes all the way down to how the CPU is structured, especially when you get what we call "contention", i.e. synchronizing more than one thread that are attempting to write to the same memory location at the same time. But in general, non-blocking is faster than blocking (lock-based) concurrency in many cases, especially all the cases where there are well known, simple, lock-free implementation of a given algorithm/data-structure. It is these good solutions that are provided with Java.

I have heard that this is available in Java.

Absolutely. For starters, all the classes in java.util.concurrent.atomic provide lock-free maintenance of shared variables. In addition, all the classes in java.util.concurrent whose names start with ConcurrentLinked or ConcurrentSkipList, provide lock-free implementation of lists, maps and sets.

Are there any particular scenarios we should use this feature.

You would want to use the lock-free queue and deque in all cases where you would otherwise (prior to JDK 1.5) use Collections.synchronizedlist, as they provide better performance under most conditions. i.e., you would use them whenever more than one thread is concurrently modifying the collection, or when one thread is modifying the collection and other threads are attempting to read it. Note that the very popular ConcurrentHashMap does actually use locks internally, but it is more popular than ConcurrentSkipListMap because I think it provides better performance in most scenarios. However, I think that Java 8 would include a lock-free implementation of ConcurrentHashMap.

Is there a difference/advantage of using one of these methods for a collection. What are the trade offs

Well, in this short example, they are exactly the same. Note, however, that when you have concurrent readers and writers, you must synchronize the reads as well as the writes, and Collections.synchronizedList() does that. You might want to try the lock-free ConcurrentLinkedQueue as an alternative. It might give you better performance in some scenarios.

General Note

While concurrency is a very important topic to learn, bear in mind that it is also a very tricky subject, where even very experienced developers often err. What's worse, you might discover concurrency bugs only when your system is under heavy load. So I would always recommend using as many ready-made concurrent classes and libraries as possible rather than rolling out your own.

Solution 3:

1) What is Non-blocking Concurrency and how is it different.

A task (thread) is non-blocking when it doesn't cause other tasks (threads) to wait until the task is finished.

2) I have heard that this is available in Java. Are there any particular scenarios we should use this feature

Java supports at its own multithreading. You can take benefit of it to run multiple tasks concurrently. When well written and implemented, this may speed up the program when running at a machine with multiple logical CPU's. To start, there are java.lang.Runnable and java.lang.Thread as low level concurrency implementations. Then there is high level concurrency in flavor of the java.util.concurrent API.

3) Is there a difference/advantage of using one of these methods for a collection. What are the trade offs

I would use Collections#synchronizedList(), not only because that's more robust and convenient, but also because a Map isn't a List. There's no need to attempt to homegrow one when the API already offers the facility.

That said, there's a Sun tutorial about Concurrency. I recommend you to get yourself through it.