Classifications of operations free from locks.

Program functions and procedures that are free from locks are in academic terms called "non-blocking", i.e., they are not blocking, provided that the function fulfills certain criteria as among others that there is no possibility for dead-locks. Depending on how the non-blocking functions can guarantee that the functions finish within a certain number of executed program steps, i.e., within a certain time, one can classify the functions as either "wait-free", "lock-free", or "obstruction-free".

Wait-free

In order for a function to be wait-free it is required that it will always finish within a finite number of executed program steps. More concrete, this means that eventual loops in the function must not be repeated more than a certain number of times. In order to completely fulfill the criteria for this property, the function must be able to guarantee this regardless of how many parallel threads that are executing with calls to the function, or if some thread has been interrupted in the middle of an execution of the function (or any other function). Clearly, this property is relatively very hard to achieve.  

Lock-free

In order for a function to be "lock-free" it is demanded that always at least one thread (of all the threads that are executing the function at the moment) are progressing. With progress means that one program step executed in the function is one step further for the function to finish. In order to completely fulfill the criteria for this property, the function must be able to guarantee this regardless of how many threads that are at the moment executing, or not executing, with calls to the function.

Obstruction-free

In order for a function to be "obstruction-free" it is not demanded more than if a thread is the only thread (that is, no parallelism at the moment) that runs the function, the function should progress for every program step that is executed. In order to completely fulfill the criteria for this property, must the function be able to guarantee this regardless of how many parallel threads that have earlier been run with calls to the function. Due to the week criteria, many functions within this group have the possibility to get stuck in a state where no thread are progressing even though program steps are continuously executed - so called "live-lock". In order to be safely used, there must thus be support in the system for detecting and avoiding live-locks.

How do one know that it works

As with all other programs, it is such that the more complicated the program is, it becomes harder to test and examine for faults. In this case with non-blocking programs, it becomes even more complicated as the number of possible combinations of how the program can execute is practically infinite, as between every two lines of code anything else can have been executed. Clearly, a good start is to run a set of test cases and experiments, but this is far enough for being completely sure. Moreover, one wants to make sure that all threads get consistent results from the functions at the same point in real time. Otherwise the function calls may seem ok to each individual thread, but the whole program may anyway behave faulty.

With the term "linearizability" one makes sure that all possible combinations of parallel function calls is possible to order in time, and if only one thread had been running the functions in this order it would have given exactly the same result as the parallel execution. If this holds, then one knows that the functions are behaving atomically. However, to prove this is not easy. One method is to apply formal methods and automatic proof engines, a method that in some cases can take several years of work. Another and faster method, is to construct mathematical oriented proofs that by step-wise reasoning about the program can proof that "linearizability" holds for all possible executions.