Multi-Processing
Running processes “in parallel” on a single CPU
Multiple concurrent processes
Lots of processes are
running
simultaneously here.
But CPUs can only
execute one
instruction at a time!
How does that work? Modern CPUs can execute a few
instructions in parallel, but let’s
ignore that for now.
Timesharing
The solution:
● OS kernel switches periodically between processes.
● If switching is fast and occurs often, it creates the
illusion of concurrency!
● This illusion works for both programmers and end users.
Process states
Multi-processing example
Time Media Player (MP) Web browser (WB) Description
1 Running Ready
2 Running Ready
3 Running Ready MP initiates I/O
4 Blocked Running Switch to WB
5 Blocked Running
6 Ready Running I/O finished
7 Ready Running
8 Running Ready Switch to MP
9 Running Ready
10 Ready Running Switch to WB
Multi-processing example
Time Media Player (MP) Web browser (WB) Description
1 Running Ready
2 Running Ready
3 Running Ready MP initiates I/O
4 Blocked Running Switch to WB
5 Blocked Running
6 Ready Running I/O finished
7 Ready Running
8 Running Ready Switch to MP
9 Running Ready
10 Ready Running Switch to WB
Multi-processing example
Time Media Player (MP) Web browser (WB) Description
1 Running Ready
2 Running Ready
3 Running Ready MP initiates I/O
4 Blocked Running Switch to WB
5 Blocked Running
6 Ready Running I/O finished
7 Ready Running
8 Running Ready Switch to MP
9 Running Ready
10 Ready Running Switch to WB
Multi-processing example
Time Media Player (MP) Web browser (WB) Description
1 Running Ready
2 Running Ready
3 Running Ready MP initiates I/O
4 Blocked Running Switch to WB
5 Blocked Running
6 Ready Running I/O finished
7 Ready Running
8 Running Ready Switch to MP
9 Running Ready
10 Ready Running Switch to WB
Multi-processing example
Time Media Player (MP) Web browser (WB) Description
1 Running Ready
2 Running Ready
3 Running Ready MP initiates I/O
4 Blocked Running Switch to WB
5 Blocked Running
6 Ready Running I/O finished
7 Ready Running
8 Running Ready Switch to MP
9 Running Ready
10 Ready Running Switch to WB
Challenges
Performance:
● Switching should not create a huge overhead
Control:
● CPU must stay in control
● Enable fair scheduling (each process gets fair amount of
time)
● Protect against malicious and buggy code
Solution: User vs Kernel mode
CPUs have two different modes of operation.
Kernel mode:
● Code runs with no restrictions, full access to hardware
● The OS runs in kernel mode
● Any interrupt triggers a switch into kernel mode and runs the
interrupt handler (part of the OS)
User mode:
● Only limited subset of instructions is allowed
● E.g. no I/O instructions
● Normal applications run in user mode
System calls
So how can a user program perform I/O?
It calls a library function that’s part of the OS!
This is called a system call.
Usually implemented using a special instruction.
System calls switch from user to kernel mode.
Timers
How can the CPU stop a running process to switch to a
different one? e.g. every microsecond
Use a timer circuit that generates regular interrupts.
Remember: interrupts switch to kernel mode and run the
OS’s interrupt handler.
This interrupts the current process, puts the OS in control and
allows it to switch to a different process.
When to switch?
The OS should switch between processes frequently to
create the illusion of concurrency.
One method for achieving a fair schedule of process
switches is round-robin time-slicing.
We’ll just look at an example.
Round-robin scheduling example
Round-robin scheduling example
Split each process into time-slices
Round-robin scheduling example
Schedule in round-robin fashion
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
Round-robin scheduling example
The shorter the time slice, the fairer the schedule!
But: each switch takes time. OS needs to find the right
compromise.
Summary
● Multi-processing means running several processes
concurrently
● We achieve the illusion of concurrency by repeatedly
switching between processes
● CPU can run in user mode (application) or kernel mode
(OS)
● System calls allow applications to do I/O
● Timer interrupts cause switch to kernel mode
● OS uses (a version of) round-robin scheduling and
time-slicing to achieve fairness between processes
EOF