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
Corporative Scheduling
- Rather than the Kernel decides when to preempt a Process (进程) and pass the CPU to another process. Process passes control back to kernel for it to perform Process Management
CPU Hogging
Process can hog to CPU forever, modern OS adapts to Preemptive Scheduling instead.
Preemptive Scheduling
- Before Kernel set the Program Counter to the Instruction of a selected Process (进程), the kernel sets the Timer Chip to trigger an Hardware interrupts (外中断) after some period of time(Time Slice)
- The kernel switches the Privilege Level to User Mode and set the program counter to the instruction of a selected process, so the process can start executing
- When the timer chip elapses, it triggers a Hardware interrupts
- The hardware interrupt invokes Trap Interrupt (陷入) which triggers the corresponding Interrupt Handler
- Interrupt handler passes control to Process Scheduler when it completes
- Process Scheduler selects a process to run by restoring the state of the CPU for that process from the process’s Process Control Block (PCB)
- Repeat step 1 to step 6
No CPU Hogging
The hardware interrupt generated by timer chip ensures the kernel obtain control to perform Process Management on a configured interval. The eliminates any process from hogging the CPU forever which may happen in the case of Corporative Scheduling.
Fixed Timeslice Round-Robin Preemptive Scheduling
- Give every Process (进程) the same Time Slice, and the processes are cycled through in order
Laggy Situation
When there is a lot of Process (进程) like
100and the time slice is a fixed10ms, one process needs to wait for1000msbefore it gets to run again.
Dynamic Timeslice Round-Robin Preemptive Scheduling
- Time Slice = Target Latency / the number of Process (进程)
- Used in modern Process Scheduler
Important
Modern process scheduler also take in Process Priority to ensure critical processes get more CPU time and run more often.
Helps to make each process more responsive
Ensures each Process will get to run again before it seems laggy to the user. As long as the Minimum Granularity is ensured and Target Latency is not exceeded.
Process gets to run faster when there is less Process
The Time Slice is a ratio of Target Latency and total Process. Less process means more time for each process.
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.