How does CPU scheduling work
There's one seat and many jobs waiting. Who gets called first changes how long everyone waits.
Who should be called first?
There's one counter and many people waiting. Since only one person can be called at a time, someone has to decide who goes first. The person who came first? The one whose business will be done quickly? The one in a hurry?
Deciding the order of calling like this is called scheduling. Jobs line up in front of the CPU too, and someone has to decide which one to handle first.
It's the same problem an emergency room or a bank counter always faces when deciding whom to call first.
One seat, many jobs waiting. Decide the order of calling.
Scheduling means deciding which of the waiting jobs to handle first.
Change the order, and the waiting changes
There are three identical customers: one has a long job, and two have short ones.
The top row calls them in order of arrival. If the long job is at the front, the two short ones behind it wait a long time until it's done. The bottom row calls the short jobs first. The two short ones finish quickly, leaving just the long one.
The customers and jobs are the same, but simply changing the order changed the average time everyone waited.
Put a long job at the front, and everyone behind it has to wait out that whole long stretch, so the average shoots up.
Even with the same three, the average wait changes with the order of calling.
Even with the same amount of work, changing the order changes the average waiting time.
Set the order yourself
Four customers are waiting, each with a job of a different length.
Change the order of calling, and the average time everyone waited appears right below. Put short jobs in front, and the average drops; put long jobs in front, and it rises.
Try different orders and find the one that lowers the average the most.
In fact, always calling the shortest of the remaining jobs first is the way to make the average wait as low as possible.
See how the average wait changes each time you change the order.
Putting short jobs first lowers the average wait, but that isn't always the right answer.
Fast isn't always good
If you keep calling only the short jobs first, the average drops. But a customer with a very long job may keep getting pushed back and wait forever.
So there's another approach: instead of giving everything to one person, give everyone a turn, a little at a time, so no one gets pushed back forever.
But switching often costs you the price of changing places each time. Whether you choose speed or fairness, there's no free choice.
Just as a video call that needs an instant response is treated differently from a big file download that can wait a bit, the balance changes with the situation.
Short jobs first is fast, but long jobs can keep getting pushed back.
Speed that lowers the average and fairness that leaves no one behind have to be traded against each other.
Summing it up on one page
There are just three things to remember.
First, scheduling is deciding the order of calling, because there's one seat and many jobs waiting.
Second, changing the order changes the average wait; putting short jobs first lowers it. Third, there's still no single right answer: speed and fairness have to be traded off, and switching often has its own cost.
However well you set the order, no new time appears out of nowhere. You're only deciding how to divide the waiting, and whom to give how much of it.
Order changes the average, and speed and fairness are traded off.