These are rough notes which I took while reading Linux Kernel development by Robert love one can find it here.
Chapter FOUR- Process Scheduling.
– Co-operative: A process voluntarily suspend itself i.e. yield. Unless the process yields, it keeps on running. The scheduler cannot make global decisions regarding how long processes run; processes can monopolize the processor for longer than the user desires.
– Pre-emptive: Act of involuntary suspending a task is called pre-emption.
Whats a Time-slice?
The time a process runs before it is preempted is usually predetermined, and it is called the timeslice of the process. Manag-ing the timeslice enables the scheduler to make global scheduling decisions for the system.
It also prevents any one process from monopolizing the processor. On many modern operating systems, the time-slice is dynamically calculated as a function of process behaviour and configurable system policy.
Too long a time-slice causes the system to have poor interactive performance.
Too short a time-slice causes significant amounts of processor time to be wasted on the overhead of switching processes because a significant percentage of the system’s time is spent switching from one process with a short time-slice to the next.
Key notes: Scheduler decides which process runs, when, and for how long.
Linux kernel history:
– O(1) Scheduler: Introduced a constant-time algorithm for timeslice calculation.
– Rotating Staircase Deadline scheduler: Which introduced the concept of fair scheduling, borrowed from queuing theory, to Linux’s process scheduler.
Policy is the behaviour of the scheduler that determines what runs when.A scheduler’s policy often determines the overall feel of a system and is responsible for optimally utilizing processor time.
– I/O Bound: One who priortizes Input output operations more. Ex: Mouse keyboard input, GUI. Requires a lot of waiting.[LOW LATENCY]
– Code Bound: One who priortizes Code and running processes more than I/O.[HIGH THROUGHPUT]
The scheduler policy in Unix systems tends to explicitly favor I/O-bound processes, thus providing good process response time. Linux, aiming to provide good interactive response and desktop performance, optimizes for process response (low latency), thus favoring I/O-bound processes over processor-bound processors.
As we will see, this is done in a creative manner that does not neglect processor-bound processes. Challenege is to find the right balance b/w two conflicting ways.
I/O-bound processes do not need longer timeslices (although they do like to run often). Whereas processor-bound processes crave long timeslices (to keep their caches hot).
Priority scheduling: The goal is to rank processes based on their worth and need for processor time(Time-slice).
The general idea, which is not exactly implemented on Linux, is that processes with a higher priority run before those with a lower priority, whereas processes with the same priority are scheduled round-robin(one after the next, repeating) The runnable process with timeslice remaining and the highest priority always runs.
Here are all of the problem statements:
– Too long a time-slice causes the system to have poor interactive performance;
– Too short a time-slice causes significant amounts of processor time to be wasted on the overhead of switching processes because a significant percentage of the system’s time is spent switching from one process with a short time-slice to the next.
– The conflicting goals of I/O bound versus processor-bound processes again arise I/O-bound processes do not need longer time-slices (although they do like to run often), whereas processor-bound processes crave long time-slices (to keep their caches hot).
In many operating systems, this observation is taken to heart, and the default time-slice is rather low—for example, 10 milliseconds.
Linux’s CFS scheduler, however, does not directly assign time-slices to processes. Instead, in a novel approach, CFS assigns processes a proportion of the processor. On Linux, therefore, the amount of processor time that a process receives is a function of the load of the system. This assigned proportion is further affected by each process’s nice value.
The nice value acts as a weight, changing the proportion of the processor time each process receives. Processes with higher nice values (a lower priority) receive a deflationary weight, yielding them a smaller proportion of the processor; processes with smaller nice values (a higher priority) receive an inflationary weight, netting them a larger proportion of the processor.
In Linux, under the new CFS(Completely Fair Scheduler), the decision is a function of how much of a proportion of the processor the newly runnable processor has consumed. If it has consumed a smaller proportion of the processor than the currently executing process, it runs immediately, preempting the current process. If not, it is scheduled to run at a later time.
The Linux kernel implements two separate priority ranges:
Nice value: The first is the nice value, a number from –20 to +19 with a default of 0. Larger nice values correspond to a lower priority—you are being “nice” to the other processes on the system. Processes with a lower nice value (higher priority) receive a larger proportion of the system’s processor compared to processes with a higher nice value (lower priority).Nice values are the standard priority range used in all Unix systems, although different Unix systems apply them in different ways, reflective of their individual scheduling algorithms.
In other Unix-based systems, such as Mac OS X, the nice value is a control over the absolute timeslice allotted to a process;
and in Linux, it is a control over the proportion of timeslice;
One can see nice values for various processes running on your Linux system by executing command “ps -el” in the terminal.
Real-time priority value: The second range is the real-time priority.The values are configurable, but by default range from 0 to 99, inclusive. Opposite from nice values, higher real-time priority values correspond to a greater priority.All real-time processes are at a higher priority than normal processes; that is, the real-time priority and nice value are in disjoint value spaces.
Linux implements real-time priorities in accordance with the relevant Unix standards, specifically POSIX. One can see Real Time priority for various processes running on your Linux system by executing command “ps -eo state,uid,pid,ppid,rtprio,time,comm” in the terminal.