What is a linearization point?

Problem Detail: 

With respect concurrent programming, what is a linearization point?

They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here.

All function calls have a linearization point at some instant between their invocation and their response.

Okay that's fine, they occur somewhere within a function call, but what are they?

All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition.

Occur instantly at their LP's??? I don't understand this.

I also read through this which attempts to prove LP's. I am having trouble finding any solid definitions. Could anyone help?

Asked By : nfaughnan

Answered By : Maxim Egorushkin

Sounds like you are reading The Art of Multiprocessor Programming.

"All function calls have a linearization point at some instant between their invocation and their response"

Okay that's fine, they occur somewhere within a function call, but what are they?

Side effects of the functions. http://en.wikipedia.org/wiki/Side_effect_(computer_science):

A function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

In C/C++ side effects are basically writing to memory that is not on the function stack.

"All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition"

Occur instantly at their LP's??? I don't understand this.

It means that memory writes become visible to other CPUs in the system at that point. Imagine a function of 100 instructions. Instruction 90 is CAS which is a linearization point. Once the instruction has completed the effects of preceding memory writes become visible to other CPUs instantly (release semantics). This happens some time after the function has been called but before it returned (on instruction 90 of 100).

Note, that memory writes may not always be visible to other CPUs in the system if linearization points are not employed.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7132