Linux Process Scheduling and Kernel Implementation

This article mainly introduces Linux process scheduling and kernel implementation, in the following order: key data structures of process scheduling -> different scheduling methods -> scheduling triggers and process switching.1. Key Data Structures of Process Management1.1 task_struct task_struct is the structure used by the kernel to describe a process, including scheduling policy, priority, and other information.

struct task_struct {    // 1. Scheduling policy: determines which scheduling class the process belongs to (real-time/fair/idle)    unsigned int policy;          // e.g., SCHED_NORMAL (fair), SCHED_RR (real-time)    // 2. Priority related: static/dynamic/real-time priority    int static_prio;              // Static priority (set by user via nice, 100-139)    int normal_prio;              // Normal priority (calculated from static_prio and policy)    int rt_prio;                  // Real-time priority (0-99, lower value means higher priority)    int prio;                     // Current dynamic priority (may be temporarily elevated due to priority inheritance)    // 3. Scheduling class: points to the scheduling class the process belongs to (e.g., fair_sched_class)    const struct sched_class *sched_class;    // 4. Scheduling entity: encapsulates scheduling information of the process (e.g., vruntime, weight)    struct sched_entity se;       // Entity for fair scheduling (CFS)    struct sched_rt_entity rt;    // Entity for real-time scheduling    // 5. Run queue association: the CPU run queue the process currently belongs to    struct rq *on_rq;             // Non-NULL indicates the process is in the ready queue    // 6. Preemption flag: whether scheduling is needed (set by the kernel, checked by schedule())    unsigned int flags;           // Includes TIF_NEED_RESCHED (needs scheduling)    // ... other fields (memory, files, signals, etc.)};

Priority rules: real-time processes > normal processesReal-time process (rt_prio) lower value means higher priorityNormal priority (static_prio) lower value means higher priorityDynamic priority (prio): defaults to normal_prio, but may be temporarily elevated due topriority inheritance to avoid “priority inversion”.1.2 sched_class Scheduling Class Linux implements encapsulation of different scheduling policies through scheduling classes, which is essentially a structure containing function pointers that define some core operations of scheduling (enqueue, dequeue, etc.).

struct sched_class {    // 1. Scheduling class name (e.g., "fair", "rt")    const char *name;    // 2. Enqueue: adds a process to the ready queue (e.g., after a process wakes up)    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);    // 3. Dequeue: removes a process from the ready queue (e.g., when a process blocks or exits)    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);    // 4. Select the next process to run (core logic of the scheduler)    struct task_struct *(*pick_next_task)(struct rq *rq);    // 5. Prepare for switch: puts the current process back into the ready queue (e.g., when time slice expires)    void (*put_prev_task)(struct rq *rq, struct task_struct *p);    // 6. Check if the current process needs to be preempted    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);    // ... other functions (e.g., task creation, priority modification)};

Scheduling classes are arranged in order of priority from high to low as follows:

1.3 Process States2. Core Scheduling Strategies and Algorithm Implementation2.1 Completely Fair Scheduler (CFS) CFS is the default scheduler in Linux, with the core idea being that if there are N processes, each process gets 1/N of the CPU time. The actual implementation is done by calculating the virtual runtime (vruntime) of the process, prioritizing the scheduling of the process with the smallest vruntime, ensuring that the growth rate of each process’s vruntime matches its weight.The calculation formula is vruntime += actual run time * N / process weight (N represents the number of CPUs in the system),CFS uses a dynamic time slice (the time each process runs), with the length of the time slice determined by the scheduling latency and the process weight.Time slice length = (process weight / total weight) * scheduling latencyScheduling latency refers to the total time for polling all ready processes once.For example:On a single-core CPU with two processes of equal weight, the total weight is 2weight, and the scheduling latency is 6ms.Then the time slice for each process = (weight / 2weight) * 6ms = 3ms.CFS organizes runnable scheduling entities using a red-black tree data structure, with the key being the vruntime of the scheduling process. The leftmost node is the node with the smallest vruntime in the entire tree, which is the next task to be run.When a task is awakened or its state changes, it will be inserted into the red-black tree. When a task is scheduled to run or leaves due to various events, it will be removed from the tree.Why use a red-black tree to manage scheduling tasks instead of a binary search tree? Because a red-black tree maintains the tree’s approximate balance through its own rules during frequent dynamic insertions and deletions, preventing degeneration into a linked list, thus ensuring the time complexity of operations is O(logn). In contrast, a binary search tree can degenerate into a linked list in extreme cases, leading to a time complexity of O(n), making performance unstable.2.2 Real-Time Scheduler (RT) Responsible for scheduling tasks with SCHED_FIFO and SCHED_RR policies. SCHED_FIFO uses first-come, first-served real-time scheduling, with no time slice concept. Once a process acquires the CPU, it will occupy it until it voluntarily relinquishes it or is preempted by a higher priority process. SCHED_RR uses time-slice round-robin scheduling, after running for a time slice (default 100ms), if there are other ready processes of the same priority, it will be placed at the end of the priority list, allowing the next same-priority process to run, while still supporting preemption by higher-priority real-time processes.The real-time scheduler maintains a queue array for each priority and also uses a bitmap to indicate whether the corresponding priority queue is non-empty (each bit represents a binary state of empty or non-empty). The scheduler can quickly find the highest priority non-empty queue by looking up the bitmap, and then take tasks from the head of that queue to run.2.3 Deadline SchedulingEach process must specify three parameters: runtime (CPU time needed per cycle, e.g., 10ms), period (the process’s running cycle, e.g., 100ms means it needs 10ms of CPU time every 100ms), deadline (the deadline, e.g., 10ms before the end of the cycle, which equals 100ms – 10ms).Priority is given to scheduling the process with the earliest deadline to ensure it completes before the deadline.3. Scheduling Triggers and Process SwitchingThe scheduler does not run actively; it needs to be triggered by events to call schedule() (the main scheduling function).3.1 Active Scheduling – Process Actively Yields CPU

3.2 Passive Scheduling – Kernel Forces Scheduling(1) Timer Interrupt The Linux kernel triggers a timer interrupt every 1/HZ seconds (for example, when HZ=1000, it triggers every 1ms), and the timer interrupt handler timer_interrupt calls scheduler_tick().TIF_NEED_RESCHED is a flag indicating that the current process needs to be scheduled.(2) Process Awakening When a process is awakened from sleep, calling wake_up_process():Sets the process state to TASK_RUNNING -> calls enqueue_task() to add the process to the ready queue -> calls check_preempt_curr() (if the awakened process has a higher priority than the currently running process or a smaller vruntime in CFS, sets TIF_NEED_RESCHED).(3) Priority Change When the user modifies the process priority through nice(), renice(), sched_setscheduler(), the kernel calls resched_curr(), setting TIF_NEED_RESCHED.3.3 SchedulingThe main function _schedule() _schedule() is the core function of the scheduler, with the main logic as follows:(1) Get the run queue (rq) of the current CPU and the currently running task (prev).(2) Depending on whether it is active scheduling or passive preemption, update the context switch count (prev->nvcsw or prev->nivcsw).(3) Call the pick_next_task() function to select the next process to run according to the priority order of the scheduling classes (stop > dl > rt > fair > idle).(4) If the selected next task is different from the currently running prev task, call context_switch() to perform the context switch.(5) After the switch is complete, re-enable preemption.3.4 Context Switching (context_switch()) In short, context switching is the process of saving the information of the currently running process and retrieving the information of the next process.Context switching:Page table switching, switching the process’s address space (CR3 register, pointing to the page global directory PGD), ensuring the CPU accesses the memory of the next process.Register switching, saving the current process’s stack pointer, program counter, and other registers to task_struct, restoring the registers of the next process, completing the exchange of CPU ownership.