Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Dec 3 '12 at 20:57

This question came from our site for professional and enthusiast programmers.

add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
So would I be correct to say that any instruction that is seen by other CPU's could be considered a linearization point? Like a write to shared memory? Thanks for your response –  nfaughnan Dec 3 '12 at 20:51
    
@nfaughnan The other CPUs don't observe the instruction itself, rather its side effects, i.e. memory writes. There can be implicit linearization points issued by the CPU or the OS at certain points. Each CPU architectrue has a list of instructions that are building blocks for linearization points (also known as memory barriers). –  Maxim Yegorushkin Dec 4 '12 at 8:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.