Concurrency (并发)
Quote
Concurrency is about dealing with lots of things at once, but parallelism is about doing lots of things at once.
- A way to run multiple Thread or Process (进程) at the same time, instead of running one thread or process after another thread or process is done
- We can achieve concurrency with multiple CPU Core, this is also known as Parallelism (并行性). We can also achieve concurrency with a single CPU core by performing Context Switch
Maximise CPU utilisation + better user experience
CPU is idle when the process and thread are performing non CPU-bounded tasks like reading and writing to IO Device and waiting a result from a remote Server etc. By performing context switch, we can let another process or thread to use CPU to complete its computation. Parallelism allows us to run multiple threads of processes at the same, if we have 4 CPU cores, it means we can have 4 processes/threads consuming the CPU at the same time.
The above describes about how concurrency helps with CPU utilisation. Concurrency also ensures users feel everything is running at the same like browsing the web and playing music at the same time.
Parallelism (并行)
- A subset of Concurrency (并发), Process (进程) and Thread run on their own CPU Core. This is the true processing of multiple tasks at the same time, not an illusion created by quick Context Switch
Data Parallelism
- Divide the data into smaller subsets and distribute them across different CPU cores
Important
This approach yields great performance when the operation on each subset of data is independent of the others, as each subset forms an independent subproblem.
Dividing data into 4 subsets and running them on 4 cores doesn’t yield 4 times the performance due to several factors. Overheads from task distribution, synchronisation. Amdahl’s Law limits speedup based on the proportion of sequential work, while shared memory bandwidth and cache misses can bottleneck performance. Additionally, imbalanced workloads and communication overhead further hinder scalability.
Task Parallelism
- Distribute tasks (or Thread) across multiple CPU cores. Each thread performs a unique operation
Important
Different threads may operate on the same data, in which case Synchronisation (同步) may be needed.
If different threads operate on different data, synchronisation is not needed.
Multi-tasking
- An extension of Multi-programming. The ability for Kernel to execute multiple tasks at the same time by giving each Process (进程) a very small Time Slice, achieving Concurrency (并发). Focusing on improving user experience
- The above animation shows only one CPU, but multi-tasking can also be implemented on multiple CPU Core to achieve Parallelism (并行性)
VS Time-sharing?
In Time-Sharing, we have multi-users instead of multi-tasks. Multi-tasking focuses on the tasks, and the tasks can be from different users. So in that sense, multi-tasking is a superset of time-sharing.
Time-Sharing
- A implementation of Concurrency (并发) and a specific implementation of Multi-tasking when CPU is shared by multiple users at the same time, achieved with quick Context Switch. This allow multiple users to run jobs on the same computer at the same time
- All Time-sharing systems are Multi-programming systems
Info
The first time-sharing machine is invented at MIT in the early 1960s, machines before it are all Batch System.
Multics - Wikipedia was one of the first time-sharing OS which inspires the creation of Unix.