Process scheduling is an essential component of the Linux operating system. It determines how the CPU time is allocated to different processes that are competing for resources. In this tutorial, we will discuss the three main types of process schedulers in Linux: O(n) scheduler, O(1) scheduler, and Completely Fair Scheduler (CFS).
✔ O(n) Scheduler
The O(n) scheduler was the first process scheduler used in the Linux kernel. It is called O(n) because the time complexity of its algorithm is proportional to the number of processes in the system. This means that as the number of processes increases, the time taken by the O(n) scheduler to schedule processes also increases.
The O(n) scheduler works by maintaining a circular linked list of processes, where each process is assigned a priority value. The scheduler traverses the list and selects the highest priority process to run on the CPU. If two or more processes have the same priority, the scheduler uses a round-robin algorithm to allocate CPU time between them.
The O(n) scheduler is not very efficient when the number of processes in the system is large. As a result, it was replaced by the O(1) scheduler in Linux 2.6.
✔ O(1) Scheduler
The O(1) scheduler was introduced in Linux 2.6 and is an improved version of the O(n) scheduler. This algorithm uses a priority-based scheduling approach but has a fixed time complexity of O(1), meaning that scheduling decisions can be made quickly regardless of the number of processes in the system.
The O(1) scheduler works by dividing processes into priority classes and assigning a time slice, or "quantum", to each process based on its priority. Higher priority processes are given shorter quantum times, allowing the scheduler to quickly switch between processes based on their priority.
To configure the O(1) scheduler, you can use the /proc/sys/kernel/sched/ directory to adjust various parameters, such as the length of the quantum and the number of priority levels. For example, to set the quantum length to 100ms, you can run the following command as the root user:
echo 100 > /proc/sys/kernel/sched_latency_ns
✔ Completely Fair Scheduler (CFS):
The Completely Fair Scheduler (CFS) is the current default scheduler in Linux. The CFS is designed to provide fairness and accuracy in CPU allocation by ensuring that each process receives an equal share of the CPU time. The CFS employs a red-black tree data structure to maintain a hierarchy of processes based on their priority and CPU usage.
The CFS measures the CPU usage of each process using a concept called "virtual runtime." The virtual runtime is an estimate of the amount of CPU time that a process has used. When a process is running, its virtual runtime increases at a rate proportional to its priority. The CFS schedules the process with the smallest virtual runtime next, ensuring that each process receives its fair share of the CPU time.
One of the advantages of the CFS is that it provides excellent fairness and accuracy in CPU allocation, making it ideal for systems with multiple users or workloads. Additionally, the CFS can adapt to changes in the workload by adjusting the priority of processes dynamically, ensuring that the system remains responsive even under heavy load.
Example
To illustrate how the different scheduling algorithms work in Linux, let's consider an example. Suppose we have three processes in the system, with the following priority values:
Process A: Priority 1
Process B: Priority 2
Process C: Priority 3
Suppose each process requires one unit of CPU time to complete. In the O(n) scheduler, the scheduler would select the process with the highest priority to run. Therefore, the scheduler would select Process C first, followed by Process B and then Process A. This scheduling algorithm is simple to understand but can lead to starvation of low-priority processes.
In the O(1) scheduler, the scheduler would also select the process with the highest priority to run. However, the O(1) scheduler maintains a runqueue data structure that allows it to locate the highest-priority process quickly. Therefore, the scheduler would select Process C first, followed by Process B and then Process A.
In the CFS, the scheduler would ensure that each process receives an equal share of the CPU time. Therefore, each process would receive 1/3 of the CPU time, regardless of its priority. The CFS would use the virtual runtime to ensure that the process with the smallest virtual runtime is selected next.
Process scheduling is a crucial component of any operating system, including Linux. The scheduler is responsible for allocating CPU resources to different processes, ensuring that each process receives its fair share of the CPU time. Linux employs several different scheduling algorithms, each with its strengths and weaknesses. The O(n) scheduler is simple but can lead to starvation of low-priority processes.
✔ Multicore Vs Multiprocessor System
In summary, a multicore system has multiple cores on a single chip that can share resources and memory, whereas a multiprocessor system has multiple CPUs or chips that can be interconnected via shared or distributed memory or communication networks. Multiprocessor systems offer higher scalability and performance but can be more expensive and less energy-efficient.
Thanks for reading, and happy coding!
Understanding Process Scheduling in Linux -> Understanding Zombie and Orphan Processes in Operating Systems: Causes and Solutions