After reading http://www.drdobbs.com/lock-free-data-structures/184401865 i got this:
* Normal locking means that the process which holds the lock can hold it arbitrarily long thereby locking out all other processes. Also a live-lock and dead-lock can occur if there is a conflict between processes which try to acquire the same set of resources but cannot acquire all of them at once.
* Wait-free means that no algorithm working with the data structure will be delayed arbitrarily. This is pretty strong. A simple example would be a ring-buffer with a single reader and writer.
* Lock-free means that no process can block the resource for longer than it takes to read/write it. There will always be at least one process that can make progress while the others may have to wait (weaker than wait-free, but stronger than ordinary locked).
Normal processes on most operating systems can be interrupted at any instruction. This would make it impossible to carry out a multiple-instruction sequence to lock-modify-unlock the data structure because it could leave the data structure locked. Does this in turn mean that there must be a "commit" instruction that is uninterruptible?