In Linux

Different classes

Linux considers 3 scheduling classes, each with multiple priority levels:

Priorities range from 0 to 99 for real-time threads and 100 to 139 for the others.

nice system call allows to change the priority of non-real time threads.

SCHED_FIFO

FIFO real-time threads, with priorities.

  • a running thread in this class is preempted only if a higher priority process (of the same class) becomes ready.

  • a running thread can voluntarily give up the processor, executing primitive sched_yield.

  • within the same priority an FCFS discipline is used.

SCHED_RR

Round-robin real-time threads, with priorities.

  • additionally, a running process in this class is preempted if its time quantum ends.

SCHED_OTHER

Non-real-time threads.

  • can only execute if no real-time thread is ready to execute.

  • associated to user processes.

  • the scheduling police changed along kernel versions.

Traditional algorithm

Priorities are based on credits.

Credits of the running process are decremented at every RTC interrupt.

  • the process is preempted when zero credits are reached.

When all ready processes have zero credits, credits for all processes, including those that are blocked, are recalculated.

  • Past history of execution and priorities are combined in the algorithm.

Response time of I/O-bound processes is minimized.

Starvation of processor-bound processes is avoided.

Not adequate for multiple processors and bad if the number of processes is high.

New algorithm

From version 2.6.23, Linux started using a scheduling algorithm for the SCHED OTHER class known as completely fair scheduler (CFS).

Schedule is based on a virtual run time value (vruntime), which records how long a thread has run so far.

  • the virtual run time value is related to the physical run time and the priority of the thread.

  • higher priorities shrinks the physical run time.

The scheduler selects for execution the thread with the smallest virtual run time value.

  • a higher-priority thread that becomes ready to run can preempt a lower-priority thread.

  • thus, I/O-bound threads eventually can preempt CPU-bound ones.

The Linux CFS scheduler provides an efficient algorithm for selecting which thread to run next, based on a red-black tree.

Last updated