Linux 2.6 process schedulering in brief

Process scheduler is a very important task for OS kernel. It decides which process/thread will be put into running by CPU. It is also important for System Admin to understand how process/thread is scheduled.

This blog will cover how Linux 2.6 does the process schedule. Be in mind, the information is from internet and books, it is not from reading the source code. And also it just covers the basic procedure not the detailed information.

Scheduler algorithm: (CFS)

CFS is based on the idea to pick up the least runtime process from all processes. The scheduler stores the records about the planned tasks in a red-black tree, using the spent processor time (weighted by other facts such as nice value)as a key. This allows it to pick efficiently the process that has used the least amount of time

Process runtime audit:

The task_struct has a variable called se (sched_entity) to record the schedule related information. Then the se has a field called vruntime, it records the weighted/standardized run time for the process.

OS kernel will call update_curr() periodically to recalculate the vrumtime for all the processes.

It will update the process/thread’s vrumtime.

Process selection by rbtree:

It is very simple for OS to choose the next suitable task, it is just to pick up the most left leave of the special data structure called rbtree (a self-balanced tree). In the rbtree, the runable processes are organized by rbtree.

When a process is created or wakeup from blocked status, the process will be added to rbtree.

When a process is blocked or finished, it will be removed from the rbtree.

Rbtree hava some color procedure. It is the self-balance process.

Process status switching

We need to understand the process status switching diagram

Note: 

uninterruptable: ignore the singles to the process (eg during process creation stage)

Interruptable: can accept the signal and response it.

When the process is blocked (typically waiting for IO, network resource) it will go to sleeping status.

When the resource is ready, it will be waked up.

From running (wait) to running (on) is called content_switch. It will do new virtual memory mapping and registers/stacks switch.