Process Scheduling in Linux

When multiple processes and threads are running on a Linux system, the kernel must decide which one gets to use the CPU and for how long. This decision-making mechanism, known as process scheduling, ensures fairness, efficiency, and responsiveness in multitasking environments. In this blog, we’ll dive into the basics of process scheduling, explore the Linux scheduler, and provide simple examples to understand the concepts.

What is Process Scheduling?

Process scheduling is the method by which the Linux kernel decides the order in which processes or threads execute. Since the CPU can only execute one task per core at a time, scheduling is crucial for providing the illusion of simultaneous execution (multitasking).

---

Goals of Process Scheduling

1. Fairness: Ensure all processes get CPU time.

2. Efficiency: Keep the CPU busy and maximize system performance.

3. Responsiveness: Minimize latency for interactive processes (e.g., user inputs).

4. Throughput: Maximize the number of tasks completed in a given period.

5. Real-Time Guarantees: Provide strict timing guarantees for real-time tasks.

---

Types of Scheduling in Linux

Linux supports two main categories of scheduling:

1. Preemptive Scheduling

• The currently running process can be interrupted (preempted) if a higher-priority process becomes ready to execute.

• Ensures that important tasks (e.g., real-time or interactive tasks) don’t have to wait for lower-priority tasks to complete.

2. Non-Preemptive Scheduling

• A process runs until it voluntarily relinquishes the CPU (e.g., via I/O operations) or terminates.

• Less common in modern systems due to its inefficiency for multi-user environments.

---

How the Linux Scheduler Works

The Completely Fair Scheduler (CFS) is the default scheduler in Linux. It is designed to provide fairness and scalability for most workloads.

Key Concepts of the CFS

1. Fairness:

   • Each process is allocated a proportion of the CPU based on its priority and weight.

   • The scheduler tries to ensure that all processes get an equal amount of CPU time unless priority dictates otherwise.

2. Time Slices:

   • A time slice is the maximum amount of time a process is allowed to run on the CPU before being preempted.

   • Time slices are dynamically calculated based on process priority and system load.

3. Run Queue:

   • The scheduler maintains a Run Queue, which is a list of all processes in the Runnable state.

   • The queue is organized as a red-black tree (a type of balanced binary tree) to quickly select the process with the smallest runtime.

---

Scheduling Policies

Linux provides several scheduling policies, each designed for specific use cases:

Understanding Priorities

Processes in Linux are assigned priorities that influence their scheduling:

1. Nice Values:

   • Range: -20 (highest priority) to 19 (lowest priority).

   • A lower nice value means the process gets more CPU time.

2. Real-Time Priorities:

• Range: 1 (lowest) to 99 (highest).

• Used only by real-time scheduling policies (SCHED_FIFO and SCHED_RR).

If you feel that the program is taking too much of the resources, you can change the scheduling priority of that process using renice command.

This feature combined with tools like top can help in identifying and changing scheduling priorities of resource intense processes.

Threads in Linux: A Comprehensive Guide