Process Scheduling

Criteria of a good scheduling algorithm

Real-world schedulers

Linux O(1) scheduler (Linux 2.5, replaced by CFS later)
Linux CFS scheduler (Since Linux 2.6.23) https://www.linuxjournal.com/node/10267

The Linux O(1) Scheduler

Structure overview:

140 priority levels
Each level has two queues of RUNNABLE processes: one for active (time slice > 0) and one for expired tasks (time slice == 0).
after all tasks in the active queue have used their time slices, each task at the other queue are assigned a slice of time.
The two queues are then switched so all the tasks become active again.

O(1) cost

A 140-bit bitmap is used to indicate what levels are non-empty -- It costs a constant number of instructions to select a level.
Always pick the first from the queue.

The problem: interactive tasks vs. batch tasks

At the beginning, CPU has no idea if a process will be interactive or not, so there is no good reason to give any task a higher (or lower) priority, unless specified by the user.
Think what will happen to an interactive task if there are multiple tasks running at the same time, assuming they all have the same priority level.
A hypothetical example of an interactive task: run for 10 ms -> sleep for 100 ms to wait for user input -> run for 10 ms -> sleep.....
Once an interactive task uses up its time share when it's running (in that 10 ms slice), it will be moved to the 2nd queue.
In that extreme case, a user could be typing when the task is "sleeping" in the second queue (with a RUNNABLE state!) so the input cannot be shown on the screen.

O(1) scheduler's solution

Monitoring the behavior of tasks (their average sleep time).
Some "rocket science" is used to determine if a task is interactive or not.
Dynamically increase the priority level of the seemingly interactive tasks.
The scheduler always schedule the highest non-empty level for execution -- note that tasks in SLEEPING mode are temporarily removed from the queues.
So the identified high-priority tasks will always be scheduled, as long as it's not SLEEPING.

However, the "rocket science" is very complicated and error-prone.

A single queue, sorted by the "virtual runtime", maintained in a Red-black tree.

After using some CPU time, a task is pushed to its right as its virtual runtime increases

The task with the minimum runtime is picked up for running.