lock free CAS confusion

Hey guys,
I am reading these so called non-blocking techniques, but i have few doubts :

1) lock-free operation are performed using atomic operation, now what are these atomic operation ? i mean at certain level they also need to have a lock right ? so Does this lock-free approach provides us locking at finer granularity only ?
2) they say non-blocking list, Now what a non-blocking list should be : if more than one threads comes at the same insertion, only one is going to get succeed, another one will do some other work right ?, but if other thread has no choice except inserting a node then how come it is non-blocking ? won't it will get blocked until previous one is done ??
3) In java, how do they atomic operation ? doesn't they do something like synchronized boolean ..... so how it is lock-free since they are acquiring lock i.e. synchronized section ? 4) CAS is usually used to implement atomic operation. So doesn't cas allow only one operation to happen on the same object , and stops ( block ) others those want to operate on the same object ? Sorry for so many doubts... please clarify...

EDIT what happens when i have a structure to update ? does it also supported by hardware ? No right, So doesn't language would be acquiring locks at some level to make these structure operation atomic ?
About JAVA : there are AtomicReference and AtomicReferenceFieldUpdater class which provides updation to a object ( structure or any kind of object) , so can we compare them in terms of performance i mean speed ? Both in tern uses Unsafe class which uses Native class .

Solution

Here is a simple lock free method in AtomicInteger

public final int getAndIncrement() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return current;
    }
}

You can see that it gets the value, increments it and does a compareAndSwap. If the compareAndSwap doesn't find the expect value, it means another thread has changed the value. So it tries again, and again, until all other threads trying to change the value have done so. This is lock free as no lock is used, but not blocking free as it may have to try again (which is rare) more than once (very rare)

1) lock-free operation are performed using atomic operation, now what are these atomic operation ? i mean at certain level they also need to have a lock right ? so Does this lock-free approach provides us locking at finer granularity only ?

However locks are implemented using more primitive operations. Otherwise you would need a lock to implement a lock adnauseum. The lock free approach uses atomic operations which avoid a full blown lock.

2) they say non-blocking list, Now what a non-blocking list should be : if more than one threads comes at the same insertion, only one is going to get succeed, another one will do some other work right ?,

If its thread safe they should both succeed, one at a time.

but if other thread has no choice except inserting a node then how come it is non-blocking ?

The term is "concurrent". It still has to wait for the other thread to finish, it uses a lock-free approach to do this.

won't it will get blocked until previous one is done ??

yes.

3) In java, how do they atomic operation ?

There is a call native method which performs the atomic operations. You can see this by reading the code. ;) From look at the native code generated, these native method are turned into machine code instructions for performance (rather than being a true method call)

doesn't they do something like synchronized boolean ..... so how it is lock-free since they are acquiring lock i.e. synchronized section ?

No, if you read the code, you would see that it doesn't.

4) CAS is usually used to implement atomic operation. So doesn't cas allow only one operation to happen on the same object ,

No.

and stops ( block ) others those want to operate on the same object ?

No.

Again, if you look at how it is used it may make more sense.