Task scheduling is the core part of an operation system. It is extremely important but need not to be very complicated. In many cases, simple scheduling policy can improve the system efficiency. Personally speaking, there is not the best scheduling policy but the most suitable scheduling policy.

Timer

The Scheduler and timer are two indivisible concepts in operation system. In Linux 0.11, in the initiation step, the system will set an timer which will time out in every 10ms. Every 10ms, the system will execute the ISP, and execute all the functions registered by different processes. Minus the time slices (counter, the default value of counter is the process’s priority) by 1.

Scheduler

Before the real task scheduling in Linux 0.11, the system will deal with all the alarms. For the process which has set an alarm and the alarm is time out, the kernel will send an alarm message to the processes and based on the current status of the processes, wake up the processes (set them into Ready status). Find the process with the biggest counter in Ready status, then jump to this process. If the biggest counter is 0, update all the counters. The policy is $counter = counter/2 + priority$ and after the update, find the process with the biggest counter in Ready status.

The task state transition diagram is shown below.