Tag: Linux Scheduling

Learn Linux Process Scheduler: how processes are created, scheduled, and managed. Explore CFS, real-time policies, and context switching

Are you curious about how Linux manages multiple programs running simultaneously? If you’ve ever wondered how your system decides which process gets the CPU at a given time, you’re about to discover the fascinating world of the Linux Process Scheduler. In this article, we’ll break it down step by step, explain its importance, and help you understand how Linux keeps everything running smoothly.

What is a Linux Process Scheduler?

The Linux Process Scheduler is the component of the Linux kernel responsible for deciding which process runs at any given moment. Think of it as a traffic controller for your CPU — it ensures that every process gets a fair share of processing power and that critical tasks are prioritized.

Every program or task in Linux is represented as a process, and since CPUs can only execute one instruction at a time per core, the scheduler plays a crucial role in multitasking. Without it, your system could become slow, unresponsive, or chaotic.

Key Functions of the Linux Process Scheduler

The Linux scheduler has several important functions:

1. Process Prioritization: Determines which process should run first based on priority levels.
2. Time Slicing: Allocates a specific time slot to each process to ensure fair CPU usage.
3. Load Balancing: Distributes processes across multiple CPU cores for efficiency.
4. Preemption: Interrupts lower-priority tasks to execute higher-priority tasks immediately.
5. Fairness: Ensures that no process starves and every process gets CPU time.

Types of Linux Process Schedulers

Linux supports different scheduling algorithms to meet varying system needs. Here are the main types:

1. Completely Fair Scheduler (CFS)

• Default scheduler for Linux since kernel 2.6.23.
• Focuses on fair distribution of CPU time to all processes.
• Uses virtual runtime to track and prioritize tasks.

2. Real-Time Scheduler

• Handles time-sensitive tasks with strict deadlines.
• Supports policies like SCHED_FIFO (first-in-first-out) and SCHED_RR (round-robin).
• Essential for embedded systems, robotics, and real-time applications.

3. Deadline Scheduler

• Ensures tasks meet specific timing constraints.
• Primarily used in high-performance and real-time environments.

How Does Scheduling Affect System Performance?

The efficiency of the Linux scheduler directly impacts:

• System responsiveness: Faster response for interactive applications.
• CPU utilization: Ensures no core remains idle unnecessarily.
• Application performance: Critical processes get prioritized without starving others.

By optimizing scheduling policies, Linux can provide both high performance and fairness, balancing user experience and system efficiency.

Here’s a simple C++ example:

#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include <mutex>
#include <unistd.h>
#include <pthread.h>

std::mutex coutMutex;

// Function to simulate a CPU-bound task
void cpuTask(int id, int priority) {
    // Set thread priority (works on Linux)
    sched_param sch;
    sch.sched_priority = priority;
    if(pthread_setschedparam(pthread_self(), SCHED_FIFO, &sch)) {
        std::lock_guard<std::mutex> lock(coutMutex);
        std::cout << "Failed to set thread priority for thread " << id << "\n";
    }

    for(int i = 0; i < 5; ++i) {
        std::lock_guard<std::mutex> lock(coutMutex);
        std::cout << "Thread " << id << " running iteration " << i+1 << "\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(500)); // Simulate work
    }
}

int main() {
    std::vector<std::thread> threads;

    // Create threads with different priorities
    threads.emplace_back(cpuTask, 1, 80); // High priority
    threads.emplace_back(cpuTask, 2, 50); // Medium priority
    threads.emplace_back(cpuTask, 3, 20); // Low priority

    // Join threads
    for(auto &t : threads) {
        t.join();
    }

    std::cout << "All threads completed!" << std::endl;
    return 0;
}

Key Concepts Explained by This Code:

1. Threads simulate processes: In Linux, threads are scheduled like processes by the kernel.
2. Setting thread priority:
   • SCHED_FIFO is a real-time scheduling policy (first-in-first-out).
   • Priority affects which thread gets CPU time first.
3. Fair CPU distribution: Even threads with lower priority eventually get CPU time.
4. Time slicing simulation: sleep_for() shows how CPU time is shared among threads.

How to Run:

1. Save the file as scheduler_demo.cpp.
2. Compile using g++: g++ -pthread scheduler_demo.cpp -o scheduler_demo
3. Run with sudo (required for setting real-time priorities): sudo ./scheduler_demo

Now we break down the C++ code I shared and explain what it does, step by step, in the context of Linux Process Scheduling :

Header Files

#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include <mutex>
#include <unistd.h>
#include <pthread.h>

• iostream → For printing output to console.
• thread → For creating and managing threads (simulating processes).
• chrono → For controlling time delays (sleep_for simulates CPU work).
• vector → To store multiple threads.
• mutex → To safely print from multiple threads without garbled output.
• unistd.h and pthread.h → For POSIX thread scheduling and priority manipulation.

Mutex for Safe Printing

std::mutex coutMutex;

• Since multiple threads run simultaneously, printing directly can overlap.
• coutMutex ensures one thread prints at a time, making output readable.

CPU-Bound Task Function

void cpuTask(int id, int priority) {
    sched_param sch;
    sch.sched_priority = priority;
    if(pthread_setschedparam(pthread_self(), SCHED_FIFO, &sch)) {
        std::lock_guard<std::mutex> lock(coutMutex);
        std::cout << "Failed to set thread priority for thread " << id << "\n";
    }

    for(int i = 0; i < 5; ++i) {
        std::lock_guard<std::mutex> lock(coutMutex);
        std::cout << "Thread " << id << " running iteration " << i+1 << "\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
}

What happens here:

1. Set thread priority:
   • sched_param sch sets the thread priority.
   • pthread_setschedparam assigns it using SCHED_FIFO (first-in-first-out real-time policy).
   • Higher numbers → higher priority.
2. Simulate CPU work:
   • A for loop runs 5 iterations.
   • Each iteration prints which thread is running.
   • sleep_for(500ms) simulates some CPU time being consumed.
3. Safe printing:
   • lock_guard<std::mutex> ensures threads print one by one, preventing mixed output.

Scheduler concept illustrated:

• Threads with higher priority (like 80) are favored by the Linux scheduler.
• Lower priority threads (like 20) may get CPU later, but all threads eventually run, showing fairness.

Main Function

int main() {
    std::vector<std::thread> threads;

    // Create threads with different priorities
    threads.emplace_back(cpuTask, 1, 80); // High priority
    threads.emplace_back(cpuTask, 2, 50); // Medium priority
    threads.emplace_back(cpuTask, 3, 20); // Low priority

    // Join threads
    for(auto &t : threads) {
        t.join();
    }

    std::cout << "All threads completed!" << std::endl;
    return 0;
}

Step-by-step:

1. Create threads with priorities:
   • Thread 1 → High priority (80)
   • Thread 2 → Medium priority (50)
   • Thread 3 → Low priority (20)
2. Join threads:
   • t.join() ensures the main program waits until all threads finish.
3. Final output:
   • After all threads complete their iterations, the program prints: "All threads completed!"

Linux Scheduler Demonstration:

• High priority threads will often run first.
• Medium and low priority threads get CPU in between based on the scheduling policy.
• You can see time-sharing and fairness in action.

How user-space threads “tell” the CPU to run first and what actually happens in Linux.

User Space Can Only Request Priority

In our C++ code:

pthread_setschedparam(pthread_self(), SCHED_FIFO, &sch);

• This requests the kernel to schedule this thread with a given policy and priority.
• It does not guarantee the CPU will run this thread first.
• The kernel’s scheduler still decides when and for how long each thread gets CPU time.

Think of it like: raising your hand in class — you’re asking for attention, but the teacher decides who speaks first.

How Linux Scheduler Handles It

When a thread requests a scheduling policy/priority:

1. The kernel checks the requested policy and priority.
   • Example: SCHED_FIFO threads with higher priority are favored.
   • Example: SCHED_RR threads get CPU in a round-robin fashion among same-priority threads.
2. The scheduler decides which thread runs next based on:
   • Thread priority
   • Current CPU load
   • Fairness (in CFS, lower virtual runtime threads run first)
   • Core affinity (which CPU cores are available)
3. The CPU switches to the selected thread preemptively if needed.
   • Higher-priority threads can interrupt lower-priority ones.

Why Our Code “Feels” Like High-Priority Runs First

• Thread 1 has priority 80 (high), Thread 2 has 50 (medium), Thread 3 has 20 (low).
• When these threads are ready, the kernel usually schedules the higher-priority thread first.
• But the kernel still decides, so timing is not guaranteed.

Note: On Linux, changing real-time priorities usually requires sudo because user-space cannot normally run high-priority real-time threads without permission.

Linux Process Creation and Scheduling Flow

Process Creation (User Request → Kernel)

1. You type a command like: ./myprogram in the shell.
2. The shell calls fork() system call → creates a child process (a duplicate of itself).
   • Inside the kernel, a new task_struct is allocated for the process.
   • task_struct contains process details: PID, scheduling policy, priority, state, etc.
3. The child process then calls execve() → replaces its memory with the new program (myprogram).
   • Loads program code from disk into memory.
   • Initializes stack, heap, registers.
   • Process is now READY to run.

Process States in the Kernel

A process can be in these states:

• NEW → Just created (fork() called).
• READY → Waiting in the runqueue for CPU time.
• RUNNING → Actively executing instructions on a CPU core.
• WAITING / SLEEPING → Waiting for I/O (like reading a file).
• TERMINATED → Finished execution.

The scheduler moves processes between these states.

Scheduler Flow (How CPU Picks a Process)

Linux uses CFS (Completely Fair Scheduler) by default for normal tasks.

High-level flow:

1. Runqueue:
   Each CPU core has a runqueue (a list of runnable processes).
2. Pick Next Task:
   Scheduler picks the process with the lowest virtual runtime (vruntime) → meaning the one that has had the least CPU time recently.
3. Context Switch:
   • Scheduler saves the current process’s state (registers, stack pointer, program counter).
   • Loads the next process’s state.
   • CPU starts executing the new process.
4. Time Slice / Preemption:
   • Each process gets a fair time slice (based on priority/niceness).
   • If time slice expires, the scheduler may preempt it and pick another process.

Special Scheduling Classes

Linux supports multiple schedulers depending on policy:

• CFS (SCHED_NORMAL) → Default fair scheduler.
• Real-Time (SCHED_FIFO, SCHED_RR) → For real-time tasks, strictly priority-based.
• Deadline Scheduler (SCHED_DEADLINE) → For tasks with deadlines.

Detailed Response Flow (Step by Step)

Here’s the entire flow from process creation to CPU execution:

1. User runs program → shell calls fork() → kernel creates new task_struct.
2. Kernel assigns PID → adds process to runqueue of a CPU.
3. Scheduler invoked (either periodically via timer interrupt or when a process yields).
4. Kernel picks next process based on scheduling policy:
   • For CFS: choose lowest vruntime.
   • For RT: choose highest-priority RT task.
5. Context switch occurs: save current process state, load new process state.
6. CPU executes instructions of chosen process.
7. Interrupts & I/O requests may move process back to waiting state.
8. When I/O completes → kernel wakes process → adds back to runqueue.
9. Steps 3–8 repeat until process calls exit().
10. Kernel cleans up process resources (memory, file descriptors, task_struct).

Visualizing

[User runs program] 
       ↓
 fork() + execve()
       ↓
 [Kernel creates task_struct] 
       ↓
 Process added to Runqueue (READY state)
       ↓
[Scheduler picks next process]
       ↓
 Context Switch → Load process state
       ↓
 CPU executes process (RUNNING)
       ↓
 ┌─────────────────────────────────────┐
 |   If timeslice expires → back to READY   |
 |   If I/O requested → go to WAITING       |
 |   If finished → go to TERMINATED         |
 └─────────────────────────────────────┘
       ↓
Repeat for all runnable processes

Scheduling flow through code

User-Space Simulation of Scheduling (C++ Example)

This is not the real scheduler, but it helps you “see” the flow:

#include <iostream>
#include <queue>
#include <thread>
#include <chrono>

struct Process {
    int pid;
    int burstTime;
    int remainingTime;
};

// Simple round-robin scheduler simulation
void roundRobinScheduler(std::queue<Process> &readyQueue, int timeSlice) {
    while (!readyQueue.empty()) {
        Process current = readyQueue.front();
        readyQueue.pop();

        std::cout << "Running process PID " << current.pid << " for ";
        int runTime = std::min(timeSlice, current.remainingTime);
        std::cout << runTime << " ms\n";

        std::this_thread::sleep_for(std::chrono::milliseconds(runTime));
        current.remainingTime -= runTime;

        if (current.remainingTime > 0) {
            std::cout << "Process PID " << current.pid 
                      << " back to READY queue with " 
                      << current.remainingTime << " ms left\n";
            readyQueue.push(current); // back to queue
        } else {
            std::cout << "Process PID " << current.pid << " finished execution!\n";
        }
    }
}

int main() {
    std::queue<Process> readyQueue;

    // Create 3 processes with different burst times
    readyQueue.push({1, 10, 10});
    readyQueue.push({2, 5, 5});
    readyQueue.push({3, 7, 7});

    int timeSlice = 3; // each process gets 3 ms CPU time
    roundRobinScheduler(readyQueue, timeSlice);

    std::cout << "All processes completed!\n";
    return 0;
}

What this shows:

• readyQueue → simulates the kernel’s runqueue.
• roundRobinScheduler → picks processes in FIFO order, runs them for a time slice, then puts them back if not finished.
• Shows transitions: READY → RUNNING → (READY or TERMINATED).
• Output will look like how the kernel “time-slices” processes.

Kernel-Level Pseudo-Code (Real Flow in Linux)

Inside Linux kernel (kernel/sched/core.c), the scheduling flow looks like this (simplified):

// Called whenever scheduler needs to pick next process
schedule() {
    struct task_struct *prev, *next;

    prev = current; // process currently running
    put_prev_task(prev); // save its state

    // Pick the next task from runqueue
    next = pick_next_task(rq);

    if (next != prev) {
        context_switch(prev, next);
    }
}

And the CFS Scheduler (pick_next_task) looks like:

pick_next_task(struct rq *rq) {
    // CFS stores tasks in a red-black tree ordered by vruntime
    // vruntime = "virtual runtime", tracks how much CPU each task used
    struct sched_entity *se = leftmost_entity(rq->cfs.rb_root);
    return task_of(se); // process with least CPU time
}

What this shows:

• schedule() is the heart of Linux scheduling.
• The runqueue (rq) holds all runnable tasks.
• pick_next_task() → chooses the process with lowest vruntime (fair scheduling).
• context_switch() → performs the actual switch: save old process state, load new one.

Flow with Code Context

1. Process created (fork() + execve()) → kernel makes a task_struct.
2. Added to runqueue (enqueue_task).
3. Timer interrupt or event calls schedule().
4. pick_next_task() chooses process (CFS or RT).
5. context_switch() → CPU starts executing new process.
6. When timeslice ends or process blocks → back to READY state.

Mapping C++ Simulation ↔ Linux Kernel Scheduler

Process Creation

C++ Simulation:

readyQueue.push({1, 10, 10});

• You manually create processes (PID, burst time).

Linux Kernel:

fork() + execve()

• Kernel creates a new task_struct.
• Loads program into memory.
• Adds it to CPU’s runqueue.

Ready Queue

C++ Simulation:

std::queue<Process> readyQueue;

• A simple FIFO queue for processes waiting for CPU.

Linux Kernel:

struct rq {
    struct cfs_rq cfs; // Red-black tree of tasks (CFS)
};

• Each CPU has a runqueue (rq).
• Tasks stored in red-black tree, sorted by vruntime (fairness).

Scheduler Decision

C++ Simulation:

Process current = readyQueue.front();
readyQueue.pop();

• Picks the first process in queue.

Linux Kernel:

next = pick_next_task(rq);

• Picks task with smallest vruntime (least CPU so far).
• Ensures fairness.

Process Execution

C++ Simulation:

int runTime = std::min(timeSlice, current.remainingTime);
std::this_thread::sleep_for(std::chrono::milliseconds(runTime));

• Simulates the process “running” for a time slice.

Linux Kernel:

context_switch(prev, next);

• Saves current process registers, stack, PC.
• Loads next process’s state.
• CPU runs the new process until time slice expires or it blocks.

Returning to Ready Queue

C++ Simulation:

if (current.remainingTime > 0) {
    readyQueue.push(current);
}

• If process not finished → back to queue.

Linux Kernel:

enqueue_task(rq, task);

• If process not finished → put back in runqueue with updated vruntime.

Process Exit

C++ Simulation:

std::cout << "Process PID " << current.pid << " finished execution!\n";

• Prints when process completes.

Linux Kernel:

do_exit();
release_task();

• Kernel cleans up memory, closes files, removes task_struct.

Visual Diagram

User Program (C++ Simulation)          Linux Kernel Scheduler (Real)

  Create process manually                fork() + execve()
        │                                       │
   Push into readyQueue                enqueue_task(runqueue)
        │                                       │
  Pop process from queue                pick_next_task()
        │                                       │
 Simulate run (sleep_for)   ←──────→    context_switch()
        │                                       │
 If not finished → push back          enqueue_task(rq, task)
 If finished → print done             do_exit(), cleanup

FAQs About Linux Process Scheduler

You can also Visit other tutorials of Embedded Prep 

• Multithreading in C++
• Multithreading Interview Questions
• Multithreading in Operating System
• Multithreading in Java
• POSIX Threads pthread Beginner’s Guide in C/C++
• Speed Up Code using Multithreading
• Limitations of Multithreading
• Common Issues in Multithreading
• Multithreading Program with One Thread for Addition and One for Multiplication
• Advantage of Multithreading
• Disadvantages of Multithreading
• Applications of Multithreading: How Multithreading Makes Modern Software Faster and Smarter”
• Master CAN Bus Interview Questions 2025
• What Does CAN Stand For in CAN Bus?
• CAN Bus Message Filtering Explained
• CAN Bus Communication Between Nodes With Different Bit Rates
• How Does CAN Bus Handle Message Collisions
• Message Priority Using Identifiers in CAN Protocol