CPU scheduling: FCFS, SJF and round robin

A CPU scheduling algorithm is the rule that picks which waiting process gets the processor next. Different rules give different waiting times, so the rule changes how fast a computer feels.

Three simple rules explain most of the idea: first come first served, shortest job first and round robin.

The simplest rule is first come first served. The process that arrived first runs until it finishes. Then the next one runs.

Waiting time is easy to read off. A process waits for every burst in front of it. Four processes arrive together and need 6, 8, 7 and 3 time units.

python3 -c "b=[6,8,7,3]; print(sum(sum(b[:i]) for i in range(4)) / 4)"

In shortest job first the scheduler always runs the process with the shortest burst. Short processes no longer queue behind long ones.

Run the same four processes in the order 3, 6, 7, 8. The long ones go last, so fewer processes wait for them.

python3 -c "b=sorted([6,8,7,3]); print(sum(sum(b[:i]) for i in range(4)) / 4)"

In round robin each process gets a turn of at most one time slice, then goes to the back of the queue. Nobody waits long for a first turn.

Here the slice is 4. The average wait is longer than in first come first served. The gain is that every process starts within 12 units, so a user at a keyboard sees an answer soon.

Real systems do not pick one rule. They give each process a share of the processor and let a user ask for less. On Linux the request is called niceness: a higher number means a nicer process, one that lets others go first.

A new shell starts at niceness 0. The nice command prints its own niceness, and -n 5 raises it by five.

nice

nice -n 5 nice