How to Make Things Faster

Chapter 76. Multitasking

Have you ever wondered how a computer with more users than CPUs can serve all of you “at once”? The answer is a scheduling algorithm called preemptive multitasking. It works like this…

Imagine that you and one friend are the only users on a computer with one single-core CPU. Each of you wants to execute a program requiring 2 seconds of CPU time. You make your request at time 0, and she makes hers 1 second later, at time 1, while your program is running:

When you run your program at time 0, the CPU is idle, so it begins executing your program’s instructions right away. Every 1/100th of a second,¹ the CPU sends a scheduler interrupt to the operating system, telling it to stop executing the currently running program and instead run an operating system subroutine called the scheduler. With no other program waiting in the queue, the scheduler simply passes control of the CPU back to your program. Then, 1/100th of a second later, the same thing happens again.

Your program receives CPU service in this manner until the first scheduler interrupt after your friend runs her program at time 1. The scheduler then finds your friend’s program in the run queue and executes a procedure called a context switch, which switches your program to the run queue for waiting, and your friend’s program to the CPU for execution. Your friend proceeds to get 1/100th of a second of ...