4 ms·
Multiple threads of control aren't necessarily parallelisable. Consider a language runtime for which every thread takes the same global lock on the interpreter,
by HenryR 15y ago
Multiple threads of control aren't necessarily parallelisable. Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Such things happen in the real world.
So you might argue that concurrency is necessary for parallelism, but it's not sufficient.
Concurrency, to me, is about expanding the set of sequentially-equivalent executions of the program which are considered 'correct' according to the operational semantics of the programming language. If you just have one correct sequential execution, then there isn't any concurrency because you would have to execute sequentially to enforce the one correct ordering.
For example, consider this snippet:
1. a = 1
2. b = 2
3. print a to file1
4. print b to file2
For most realistic language semantics there's no dependency between lines 3, and 4, so it's ok to execute in the following orders:
1, 2, 3, 4
1, 3, 2, 4
2, 1, 3, 4
2, 1, 4, 3
and others. There is concurrency there, and if the runtime cannot detect or leverage it quite often the processor will with out-of-order-execution and pipelining.
However, the simpler snippet:
1. a = 2
2. b = a * 2
3. print a + b
Doesn't have any obvious concurrency (ignoring that in this case the compiler could optimise away the assignments and additions into a single statement). 1 must happen before 2, which must happen before 3. There is only one 'correct' sequential execution, and therefore there is no obvious parallelisation achievable.
- javert 15y agoConsider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Well, I disagree that "concurrency" should be defined as "having multiple threads," but if that's how we want to define it... then I think you conflated the definitions half way through. Your final example, you state, has neither concurrency nor parallelism. Actually, by your definition of concurrency, it could be concurrent (put each statement in a separate thread and use locks), though I agree that it can't be parallel; it's inherently sequential.
- ww520 15y agoWhat are your definition of concurrency and parallelism?
- javert 15y agoAt first I didn't have any, but now I've come up with the following: Concurrency occurs when program semantics allow two threads of execution to be executed in a simultaneous or interleaved manner. Parallelism occurs when two program threads actually execute simultaneously.
- HenryR 15y agoThese are tricky waters, but here's what I see as the difference: Two separate threads that can run completely independently without any synchronisation are concurrent because it doesn't matter what order you run them in. Therefore there are many, many 'sequentially equivalent' computations that are correct per the language semantics. From the perspective of the user it can seem like you ran Thread A to completion followed by Thread B, or Thread B then Thread A, or any interleaving of the two. Threads are one way of expressing concurrency. Actors, to pick at random, are another. So I don't believe that threads <=> concurrency, but that threads usually express concurrency unless they have pathological synchronisation behaviour. Which they would have, in your final example - there is no concurrency because there's only a single ordering of events that is correct.
- javert 15y agoI just realized you and I have multiple "threads of conversation" going on at once. (which is OK.) I like your Actors example. Yeah, concurrency can't be defined in terms of "threads" in a specific implementation sense, but only in a more generic sense of "threds of execution," as in "execution contexts".