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
