Comment by ww520 | Hacker News Reader

Comment by ww520 | Hacker News Reader

Parent Full thread

Parallelism deals with program running at the same time; by definition, it runs on multiple CPUs. Concurrency deals with the non-deterministic order of running multiple threads of execution. Concurrent threads might or might not run on multiple CPUs. You can have multiple threads running on a single CPU system while the OS schedules one thread after another randomly. You still have concurrency and the order of execution is still non-deterministic, but you don't have parallelism.

Parallelism's goal is to max out the overall throughput. It deals with partitioning data and algorithm to keep all the CPUs busy while minimizing the inter-CPU communication cost. It deals with efficient data transfer, cache coherency, data locality (out of the 10K CPUs, your neighbors can faster serve your subtask's need), and data dependency (which nodes need to go first). Parallel programs can be surprisingly deterministic. Some examples are cracking password (partition the dictionary in N ways and have N CPU hitting them), web crawling (partition the URL address space N way and have N CPU hitting them). Most of the map-reduce stuffs are parallel programs.

Concurrency's main concern is to bring consistency to the non-deterministic nature of multiple threads of execution. Mutex, semaphore, event, monitor, and transactional memory are some mechanisms to bring order to the chaos.

So to simplify, what I'm gathering from this, and other comments, is:

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.

By the way, I still have problems with the use of "non-determinism" here. Contrary to what you say, schedulers do not schedule threads randomly. But looked at from the perspectice of program semantics, that might as well be the case, which is (I think) the reason people keep bringing that up.

The key term to concurrency is the non-deterministic order of execution of multiple threads. Non-deterministic means that you run the program one time, the order of execution is: thread 3, thread 5, thread 1, thread 4, and thread 2. You run it another time, the order can be: thread 1, thread 5, thread 2, thread 4, and thread 3. In another time with 2 CPU: thread 1/5, thread 1/3 (1 overlaps 5 and 3), thread 2, and thread 4. From your perspective, the OS schedules your threads "randomly." It might be due to system load, interrupt, or timing. Doesn't matter. It's just that the order is not guaranteed.

The goal of writing a proper concurrent program is no matter what the order of execution, the computed outcome is the same, due to consistency guarantee coded in.

That's wrong because there's real-time systems out there that run threads in priority order. Are you saying that such a system does not have concurrency?

As you say, from the perspective of the program any scheduling interleaving is possible. The OS can substitute a new scheduling algorithm any time it likes. Otherwise we could know that the possible set of executions is much smaller than the set of all interleavings, and could write our concurrent code based upon that assumption. Then we'd be SOL when anyone tweaked the scheduler.

What do you think about the definitions I gave of the two terms?

BTW, I'm going to pick on you a bit. I don't like it when people oversimplify things in CS. I think it can be confusing to beginners (and, sometimes, non-beginners). I don't like when people say things like "the scheduler can do whatever it wants," "the OS scheduler can change any time," "the scheduler is non-deterministic," etc., because I know those things aren't true. They may help make a point, but it's also introducing a source of potential confusion.

I say this from the perspective of somebody who has actually done some work on OS schedulers. I mean, to me, the OS never substitutes a new scheduling algorithm any time it likes, though an OS hacker may actually change the algorithm. And, as you may know, kernel hackers take advantage of known limitatations in concurrency (i.e., concurrency that will never "actually happen").

I don't see how it confuses people. In CS, the important thing is to specify the contract between subsystems. To your program, a preemptive scheduler's contract is it will run your threads in any order it wants. The point is not whether it's truly random or pseudo random. The point is there is no guarantee of ordering. You better deal with it. You cannot rely on the threads running in certain order. That's non-deterministic. It's a basic notion in concurrency.

Note that I never said the scheduler is non-deterministic. It is the order of your threads' execution that's non-deterministic.

It confuses people because (a) it's not true and (b) it's beside the point.

There are lots of schedulers out there that have a different contract than the one you described ("run threads in any order"). For example, many real-time systems run threads in priority order - you only get preempted if a higher-priority thread wants to run.

I think we are getting off-track here. The non-deterministic nature is about concurrent programs, not about scheduler. Scheduler is just one source causing non-deterministic execution order of threads. There are other non-deterministic causing sources.

Imagine you spin off 10 threads waiting for network requests where one thread per client machine. It cannot be deterministically decided which thread will run first and which will run next. It depends on which client connects to which thread first. That's the non-deterministic nature of the program. Concurrency is the discipline to deal with that problem.

Right, but if you make assumptions about the scheduler, you are tied to that scheduler's implementation, which introduces a significant coupling between OS implementation and language runtime that doesn't win you much and commits you to an implementation that, honestly, can and will change over time.

You wouldn't want to make assumptions about the scheduler if you're programming for a desktop, smartphone, or server, but you have to if you're programming a lot of kinds of embedded systems.

I think your definitions are good, although thread-centric - to be really precise you have to talk a bit about 'steps' in the operational semantics of the program, but it's not helpful usually to do so.

I do think it would have been better if I had said "contexts of execution" wherever I said "thread."

Reply on news.ycombinator.com