> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/linux-internals/03-process-management-and-scheduling-x86-x86_64-+.md).
# 03 - Process Management & Scheduling (x86/x86\_64)+
> Processes/threads, the `task_struct`, fork/exec, context switching at the register level, and how the scheduler picks who runs next.
***
### 1. What a process actually is to the kernel
Every process (and every thread - Linux doesn't really distinguish them internally) is represented by one struct: **`task_struct`** (`include/linux/sched.h`). It's large (hundreds of fields); conceptually:
```
struct task_struct {
pid_t pid, tgid; // process id, thread-group id
struct mm_struct *mm; // memory map (NULL for kernel threads)
struct files_struct *files; // open file descriptor table
struct fs_struct *fs; // cwd, root dir
struct task_struct *parent;
struct list_head children;
struct sched_entity se; // scheduler bookkeeping (CFS)
struct thread_struct thread; // saved CPU register state when not running
struct cred *cred; // uid/gid/capabilities
unsigned long state; // RUNNING, INTERRUPTIBLE, ZOMBIE, ...
struct signal_struct *signal;
...
};
```
Linux threads = tasks that **share** `mm`, `files`, `fs` with their thread group leader, but each get their own `task_struct`, own kernel stack, own register state. This is why `clone()` (the real primitive under both `fork()` and `pthread_create()`) takes a huge set of flags (`CLONE_VM`, `CLONE_FILES`, `CLONE_FS`, `CLONE_THREAD`...) - a "thread" is just a `clone()` call that shares almost everything, and a "process" is a `clone()`/`fork()` that shares almost nothing.
Every `task_struct` also has its own **kernel stack** (a small, fixed-size stack - typically 16KB on x86\_64, `THREAD_SIZE`) used only while that task is executing kernel code. This is a classic kernel exploitation target: stack-based buffer overflows in kernel stacks are more dangerous than userspace ones because the stack is tiny and sits right next to critical data (`thread_info`, and historically adjacent to other allocations).
***
## 2. Process states
#### 1. Birth: `fork()` to `RUNNABLE`
When a program calls `fork()`, a brand-new process is created.
* It starts in the `RUNNABLE` (`TASK_RUNNING`) state.
* What it means: The process is fully ready to execute, but it is sitting in a waiting room (the run queue) until the CPU scheduler has a free slot to run it.
### 2. Execution: `RUNNABLE` $\leftrightarrow$ `RUNNING`
Once the CPU scheduler selects the process from the queue, it moves to the `RUNNING` state.
* What it means: The CPU is actively executing the process's instructions.
* The Loop Back: A process rarely finishes its entire job in one go. If its time slice expires or a higher-priority task arrives, it gets preempted and is pushed right back into the `RUNNABLE` queue to wait for its next turn.
### 3. Waiting: `RUNNING` $\rightarrow$ `SLEEPING` $\rightarrow$ `RUNNABLE`
If a running process needs to read data from a hard drive, wait for a network packet, or acquire a locked resource, it cannot keep using the CPU. It voluntarily blocks.
* It moves into the `SLEEPING` state.
* There are two types of sleep mentioned here:
* Interruptible: The process can be woken up early if it receives a system signal (like you pressing `Ctrl+C`).
* Uninterruptible: The process is waiting for hardware directly (like disk I/O) and absolutely cannot be interrupted until the hardware responds.
* The Wake-up: Once the hardware event finishes or the lock opens, the process moves back to the `RUNNABLE` queue to wait for its turn on the CPU again.
### 4. Death: `exit()` to `ZOMBIE`
When a process finishes its work, it calls `exit()`. However, it does not disappear instantly.
* It enters the `ZOMBIE` state.
* What it means: The process is dead. All of its memory space and open files are cleared out. However, its `task_struct` (the passport/dossier) is kept alive in the kernel's process table. This is done so the parent process can read its final exit code to see if it finished successfully or crashed.
### 5. Final Clean up: `reaped`
The zombie process stays in limbo until its parent process acknowledges its death by calling `wait()`.
* What it means: The parent reads the exit status.
* Once this happens, the process is finally reaped. The kernel completely deletes the remaining `task_struct` and frees that memory back to the system.
Would you like to explore what happens if a parent process dies before its child becomes a zombie (orphan processes), or look into how to spot zombie processes using command-line tools?
```
BIRTH:::
┌───────────────┐
fork() ───►│ RUNNABLE │◄──── scheduler picks it
│ (TASK_RUNNING)│
└──────┬────────┘
│ runs on CPU
┌───────▼────────┐
│ RUNNING │
└───┬────────┬───┘
blocks on I/O │ │ preempted / time slice ends
or a lock │ │ (back to Runnable queue)
┌───▼────┐ │
│SLEEPING│ │
│(INTERRU│ │
│PTIBLE/ │ │
│UNINTERR│ │
│UPTIBLE)│ │
└───┬────┘ │
event occurs │ │
(I/O done, │ │
signal, etc) │ │
┌───▼────────▼───┐
│ RUNNABLE │
└────────────────┘
exit() ──► ┌────────────┐ parent calls wait() ┌─────────┐
│ ZOMBIE │──────────────────────►│ reaped │
│(exited, wait│ (task_struct finally │ (freed) │
│ for parent) │ freed) │ │
└────────────┘ └─────────┘
```
***
### 3. `fork()` / `exec()` in detail
Classic Unix pattern for "run a new program": **fork then exec**.
```
Parent process Child process
─────────────── ──────────────
fork() ───────────────────────────► (new task_struct created,
COPY of parent's mm - but see
COW below; copies fd table,
signal handlers, etc.)
returns child's PID returns 0
│ │
│ ▼
│ execve("/bin/ls", argv, envp)
│ │
│ ┌───▼─────────────────────────┐
│ │ kernel: │
│ │ - opens & validates ELF │
│ │ - flushes old address space │
│ │ - maps new ELF segments, │
│ │ interpreter (ld.so), stack│
│ │ - sets up auxv, argv, envp │
│ │ on new stack │
│ │ - jumps to ELF entry point │
│ └──────────────────────────────┘
│ (child is now running ls,
│ completely new memory image)
wait(&status) ◄────────────────────── eventually exit()
```
**Copy-on-Write (COW)**: `fork()` does NOT actually copy all of the parent's memory pages immediately - that would be enormously wasteful for a fork()-then-immediately-exec() pattern (the overwhelmingly common case). Instead:
1. Child gets its own page tables, but entries point to the **same physical pages** as the parent.
2. Both parent's and child's PTEs for these shared pages are marked **read-only**, even if they were writable before.
3. If either process writes to such a page, the CPU raises a **page fault**; the kernel's fault handler sees it's a COW page, allocates a fresh physical page, copies the data, and updates that process's PTE to point to the new page (now genuinely writable, refcount on the old page drops).
This COW mechanism (reference-counted physical pages, lazy duplication) is foundational - you'll see the same pattern in `mmap(MAP_PRIVATE)`, and COW-related race conditions have produced real kernel exploits (e.g. **Dirty COW**, CVE-2016-5195 - a race between GUP (`get_user_pages`) and COW page fault handling that let unprivileged users write to read-only files).
```mermaid
flowchart LR
subgraph BEFORE["BEFORE WRITE: Sharing"]
direction TB
P1[👨 Parent PTE Points to Page X 🔒 READ-ONLY]
C1[👶 Child PTE Points to Page X 🔒 READ-ONLY]
PX[📄 PHYSICAL PAGE X Shared by both]
P1 --> PX
C1 --> PX
end
BEFORE --> WRITE[✍️ Child tries to write]
WRITE --> FAULT[💥 PAGE FAULT CPU raises exception]
FAULT --> KERNEL[🔧 Kernel's fault handler runs]
KERNEL --> ALLOC[📝 Allocate new physical page Y]
ALLOC --> COPYDATA[📋 Copy data from Page X to Page Y]
COPYDATA --> UPDATE[✏️ Update Child's PTE to point to Page Y 🔓 READ-WRITE]
UPDATE --> RESULT[✅ Write succeeds on Page Y Parent still has Page X]
subgraph AFTER["AFTER WRITE: Separate"]
direction TB
P2[👨 Parent PTE Points to Page X 🔓 READ-WRITE]
C2[👶 Child PTE Points to Page Y 🔓 READ-WRITE]
PX2[📄 PHYSICAL PAGE X Parent only]
PY2[📄 PHYSICAL PAGE Y Child only]
P2 --> PX2
C2 --> PY2
end
RESULT --> AFTER
classDef before fill:#e3f2fd,stroke:#1565c0
classDef action fill:#fff3e0,stroke:#e65100
classDef after fill:#e8f5e9,stroke:#2e7d32
classDef kernel fill:#f3e5f5,stroke:#4a148c
class BEFORE before
class WRITE,FAULT action
class KERNEL,ALLOC,COPYDATA,UPDATE kernel
class AFTER after
```
***
### 4. Context switching (the register-level mechanics)
A context switch is the kernel saving one task's full CPU state and restoring another's. On x86\_64, roughly:
```
Task A running Task B about to run
─────────────── ────────────────────
Timer interrupt / syscall / blocking
call fires → traps into kernel
│
▼
save Task A's general-purpose registers
(rax, rbx, ..., r15, rip, rflags) into
Task A's kernel stack / thread_struct
│
▼
scheduler picks Task B (see CFS below)
│
▼
switch_mm(): if different process,
load Task B's page tables:
mov cr3,
(this flushes the TLB unless PCID used)
│
▼
switch_to() macro: swap stack pointer
to Task B's kernel stack, restore
Task B's saved registers
│
▼
return-from-interrupt (iretq) or
sysretq → CPU resumes Task B exactly
where it left off, now in Task B's
address space
```
Two costs worth internalizing: (1) reloading `cr3` invalidates the TLB (unless PCID/ASID tagging is used to avoid this - modern kernels do use PCIDs for exactly this reason), and (2) **KPTI** (Kernel Page Table Isolation, the Meltdown mitigation) makes syscalls/interrupts *even more* expensive because it forces nearly a full page-table switch on every kernel/user transition, not just on process switches - because under KPTI the user page tables intentionally do NOT map most of the kernel at all.
```mermaid
flowchart TD
%% ===== TITLE =====
subgraph TITLE["🔄 CONTEXT SWITCHING — What It Is"]
T1["📌 The kernel saves one task's CPU state and restores another task's state"]
end
%% ===== TRIGGER =====
TRIGGER["⚡ What triggers a context switch?"]
TRIGGER --> T1A["⏰ Timer interrupt (time slice expired)"]
TRIGGER --> T1B["📞 System call (process asks kernel for service)"]
TRIGGER --> T1C["⏳ Blocking operation (process waiting for I/O or lock)"]
T1A --> TRAP
T1B --> TRAP
T1C --> TRAP
TRAP["🛑 CPU traps into kernel mode"]
%% ===== PHASE 1: SAVE =====
TRAP --> SAVE["💾 PHASE 1: SAVE Task A's state"]
SAVE --> SAVE1["1. Save general-purpose registers rax, rbx, rcx, rdx, rsi, rdi, rbp rsp, r8, r9, r10, r11, r12, r13, r14, r15"]
SAVE --> SAVE2["2. Save instruction pointer rip = next instruction to execute"]
SAVE --> SAVE3["3. Save flags register rflags = status flags (zero, carry, etc.)"]
SAVE --> SAVE4["4. Save stack pointer rsp = current stack location"]
SAVE --> SAVE5["5. Segment registers cs, ds, es, fs, gs (legacy x86)"]
SAVE1 --> STORE
SAVE2 --> STORE
SAVE3 --> STORE
SAVE4 --> STORE
SAVE5 --> STORE
STORE["📂 Store saved state in Task A's kernel stack and thread_struct"]
%% ===== PHASE 2: SCHEDULE =====
STORE --> SCHED["📋 PHASE 2: Scheduler picks next task"]
SCHED --> SCHED1["Scheduler uses CFS (Completely Fair Scheduler)"]
SCHED1 --> SCHED2["Picks Task B based on vruntime/priority"]
%% ===== PHASE 3: SWITCH MEMORY =====
SCHED --> SWITCHMM["🗺️ PHASE 3: switch_mm() — Switch address spaces"]
SWITCHMM --> MM1["Is Task B in the same process as Task A?"]
MM1 --> |✅ Same process (e.g., threads)| MMNO["No CR3 change Same address space"]
MM1 --> |❌ Different process| MMYES["Load Task B's page tables"]
MMYES --> CR3["mov cr3, <Task B's PGD physical address>"]
CR3 --> TLB["💥 This invalidates the TLB (Translation Lookaside Buffer)"]
TLB --> PCID{"Does CPU support PCID?"}
PCID --> |✅ Yes (modern)| PCIDYES["PCID tags TLB entries AVOIDS full TLB flush"]
PCID --> |❌ No (old)| PCIDNO["❌ Full TLB flush — expensive!"]
PCIDYES --> KPTI
PCIDNO --> KPTI
%% ===== PHASE 4: KPTI =====
KPTI["🛡️ KPTI — Kernel Page Table Isolation"]
KPTI --> KPTI1["Meltdown mitigation"]
KPTI --> KPTI2["User page tables don't map most of kernel"]
KPTI --> KPTI3["⚠️ Every kernel/user transition forces page table switch"]
KPTI --> KPTI4["📉 Makes syscalls/interrupts MORE expensive"]
%% ===== PHASE 5: SWITCH STACK =====
KPTI --> SWITCHSTACK["🔀 PHASE 4: switch_to() — Switch stack"]
SWITCHSTACK --> SS1["Swap stack pointers"]
SS1 --> SS2["Task A's kernel stack → Task B's kernel stack"]
SS2 --> SS3["Update task_struct to point to current task"]
%% ===== PHASE 6: RESTORE =====
SS3 --> RESTORE["📤 PHASE 5: Restore Task B's saved state"]
RESTORE --> RESTORE1["1. Restore general-purpose registers"]
RESTORE --> RESTORE2["2. Restore instruction pointer (rip)"]
RESTORE --> RESTORE3["3. Restore flags (rflags)"]
RESTORE --> RESTORE4["4. Restore stack pointer (rsp)"]
RESTORE1 --> RTN
RESTORE2 --> RTN
RESTORE3 --> RTN
RESTORE4 --> RTN
%% ===== RETURN =====
RTN["🚀 Return from interrupt"]
RTN --> RTN1["iretq or sysretq instruction"]
RTN1 --> RESUMEB["✅ CPU resumes Task B EXACTLY where it left off"]
RESUMEB --> RESULT["🎯 Task B is now running in Task B's address space"]
%% ===== COSTS =====
subgraph COSTS["💸 Two Major Costs"]
C1["1️⃣ CR3 reload = TLB invalidated (unless PCID/ASID used)"]
C2["2️⃣ KPTI = extra page table switch on EVERY kernel/user transition"]
end
CR3 -.-> C1
KPTI -.-> C2
%% ===== STYLING =====
classDef trigger fill:#fff3e0,stroke:#e65100
classDef save fill:#e3f2fd,stroke:#1565c0
classDef schedule fill:#e8f5e9,stroke:#2e7d32
classDef memory fill:#f3e5f5,stroke:#4a148c
classDef restore fill:#fce4ec,stroke:#b71c1c
classDef result fill:#c8e6c9,stroke:#1b5e20
classDef cost fill:#ffebee,stroke:#c62828
classDef title fill:#fff9c4,stroke:#f9a825
class TRIGGER,T1A,T1B,T1C,TRAP trigger
class SAVE,SAVE1,SAVE2,SAVE3,SAVE4,SAVE5,STORE save
class SCHED,SCHED1,SCHED2 schedule
class SWITCHMM,MM1,MMYES,MMNO,CR3,TLB,PCID,PCIDYES,PCIDNO,KPTI,KPTI1,KPTI2,KPTI3,KPTI4 memory
class SWITCHSTACK,SS1,SS2,SS3 restore
class RESTORE,RESTORE1,RESTORE2,RESTORE3,RESTORE4,RTN,RTN1,RESUMEB,RESULT result
class C1,C2 cost
class TITLE,T1 title
```
***
### 🎯 SIMPLIFIED SEQUENCE DIAGRAM
```mermaid
sequenceDiagram
participant TA as 🔵 Task A (running)
participant CPU as 💻 CPU
participant K as 🧠 Kernel
participant S as 📋 Scheduler
participant TB as 🟢 Task B (about to run)
Note over TA: Task A executing normally
CPU->>CPU: ⏰ Timer interrupt fires
CPU->>K: 🔒 Trap into kernel mode
Note over K: 💾 SAVE TASK A STATE
K->>K: Save all registers to Task A's kernel stack (rax, rbx, rcx, rdx, rsi, rdi, rbp rsp, rip, rflags, r8-r15)
K->>S: "Which task should run next?"
S->>S: 📋 CFS picks Task B (lowest vruntime)
S->>K: "Run Task B"
Note over K: 🗺️ SWITCH ADDRESS SPACE
alt Different process
K->>CPU: mov cr3, Task B's PGD
CPU->>CPU: 💥 TLB flush (or PCID tagging)
else Same process (threads)
K->>K: ✅ No CR3 change needed
end
Note over K: 🛡️ KPTI CHECK (Meltdown mitigation)
K->>CPU: Switch to kernel page tables then back to user page tables
Note over K: 🔀 SWITCH STACK
K->>K: rsp = Task B's kernel stack
K->>K: current = Task B's task_struct
Note over K: 📤 RESTORE TASK B STATE
K->>K: Restore all registers from Task B's kernel stack
CPU->>CPU: iretq / sysretq
CPU->>TB: ✅ Resume Task B from where it left off
Note over TB: Task B now executing!
```
***
### 🔬 REGISTER SAVE/RESTORE — DETAILED
```mermaid
flowchart LR
subgraph BEFORE["⏳ BEFORE: Task A running"]
A_CPU["💻 CPU Registers contain Task A's state"]
A_STACK["📂 Task A's kernel stack"]
end
BEFORE --> INTERRUPT["⚡ Interrupt"]
INTERRUPT --> SAVE_DETAIL["💾 SAVE OPERATION"]
SAVE_DETAIL --> REGS["📝 Save these registers:"]
REGS --> GPR["General Purpose: rax, rbx, rcx, rdx, rsi, rdi, rbp r8, r9, r10, r11, r12, r13, r14, r15"]
REGS --> IP["Instruction Pointer: rip"]
REGS --> FLAGS["Status Flags: rflags"]
REGS --> STACK["Stack Pointer: rsp"]
REGS --> SEG["Segment Registers: cs, ds, es, fs, gs"]
GPR --> PUSH
IP --> PUSH
FLAGS --> PUSH
STACK --> PUSH
SEG --> PUSH
PUSH["📥 PUSH all onto Task A's kernel stack"]
PUSH --> SAVED["✅ Task A state saved"]
SAVED --> SWITCH_DETAIL["🔀 SCHEDULER RUNS"]
SWITCH_DETAIL --> PICK["📋 Picks Task B"]
PICK --> RESTORE_DETAIL["📤 RESTORE OPERATION"]
RESTORE_DETAIL --> POP["📤 POP from Task B's kernel stack"]
POP --> POPGPR["Restore General Purpose registers"]
POP --> POPIP["Restore rip"]
POP --> POPFLAGS["Restore rflags"]
POP --> POPSTACK["Restore rsp"]
POPGPR --> DONE
POPIP --> DONE
POPFLAGS --> DONE
POPSTACK --> DONE
DONE["✅ Task B restored"]
DONE --> RESUMEB["🚀 Resume Task B"]
classDef before fill:#e3f2fd,stroke:#1565c0
classDef save fill:#fff3e0,stroke:#e65100
classDef restore fill:#e8f5e9,stroke:#2e7d32
classDef result fill:#c8e6c9,stroke:#1b5e20
class BEFORE,A_CPU,A_STACK,INTERRUPT before
class SAVE_DETAIL,REGS,GPR,IP,FLAGS,STACK,SEG,PUSH,SAVED save
class SWITCH_DETAIL,PICK restore
class RESTORE_DETAIL,POP,POPGPR,POPIP,POPFLAGS,POPSTACK,DONE,RESUMEB result
```
***
### 🗺️ ADDRESS SPACE SWITCH — THE CR3 DETAIL
```mermaid
flowchart TD
subgraph BEFORE["Task A running"]
A_PT["Task A's Page Tables (PGD at physical address 0x1234)"]
A_DATA["Task A's Data"]
CPU_CR3["CPU CR3 = 0x1234"]
CPU_CR3 --> A_PT
A_PT --> A_DATA
end
BEFORE --> SWITCH["🔀 switch_mm() called"]
SWITCH --> SAME{"Same process?"}
SAME --> |✅ Yes (threads)| SKIP["⏭️ Skip CR3 change Same address space"]
SAME --> |❌ No| CHANGE["🔄 Load Task B's page tables"]
CHANGE --> CR3["mov cr3, Task B's PGD (physical address 0x5678)"]
CR3 --> TLB["💥 TLB invalidated!"]
TLB --> PCID{"PCID supported?"}
PCID --> |✅ Yes| PCIDSAVE["PCID tags TLB entries Avoids full flush"]
PCID --> |❌ No| FULLFLUSH["❌ Full TLB flush (Very expensive!)"]
PCIDSAVE --> B
FULLFLUSH --> B
subgraph AFTER["🟢 Task B running"]
B_PT["Task B's Page Tables (PGD at physical address 0x5678)"]
B_DATA["Task B's Data"]
CPU_CR3_B["CPU CR3 = 0x5678"]
CPU_CR3_B --> B_PT
B_PT --> B_DATA
end
AFTER --> KPTI["🛡️ KPTI also adds overhead"]
KPTI --> KPTI1["User page tables map almost no kernel"]
KPTI --> KPTI2["Must switch page tables on every syscall/interrupt"]
classDef before fill:#e3f2fd,stroke:#1565c0
classDef switch fill:#fff3e0,stroke:#e65100
classDef after fill:#e8f5e9,stroke:#2e7d32
classDef kpti fill:#ffebee,stroke:#c62828
class BEFORE,A_PT,A_DATA,CPU_CR3 before
class SWITCH,SAME,SKIP,CHANGE,CR3,TLB,PCID,PCIDSAVE,FULLFLUSH switch
class AFTER,B_PT,B_DATA,CPU_CR3_B after
class KPTI,KPTI1,KPTI2 kpti
```
***
### 📋 EXPLANATION OF EVERY TERM
| **Term** | **Meaning** | **Why It Matters** |
| -------------------------------------- | -------------------------------------------------------------------- | ----------------------------------------------------------------------- |
| **Context Switch** | Saving one process's CPU state and restoring another's | Enables multitasking; every process gets CPU time |
| **Timer Interrupt** | Hardware interrupt fired by CPU timer; usually every 1-10ms | Forces the kernel to decide if current process should continue |
| **System Call** | Process asks kernel for service (open, read, write, etc.) | Triggers context switch to kernel mode |
| **Blocking Operation** | Process waits for I/O, lock, or event | Process can't continue, so kernel switches to another |
| **Trap** | CPU transfers control to kernel in response to interrupt/syscall | The mechanism that enters kernel mode |
| **Kernel Mode** | Privileged CPU mode where all instructions are allowed | OS runs here; can access hardware directly |
| **User Mode** | Unprivileged CPU mode where applications run | Restricted; can't access hardware or kernel memory directly |
| **Register** | Ultra-fast memory inside CPU; holds data/addresses | Everything the CPU works on lives in registers |
| **rip** | Instruction Pointer; holds address of next instruction | Changing this changes what code runs |
| **rflags** | Flags register; contains status bits (zero, carry, etc.) | Used for condition checking and control flow |
| **rsp** | Stack Pointer; points to current top of stack | Critical for function calls and local variables |
| **task\_struct** | Kernel data structure containing all info about a process | The kernel's "process ID card" |
| **thread\_struct** | Kernel data structure containing CPU state for a thread | Stores registers when thread isn't running |
| **Kernel Stack** | Each process/thread has its own stack in kernel memory | Used when process enters kernel mode |
| **Scheduler** | Kernel component that decides which process runs next | The "traffic cop" of the CPU |
| **CFS (Completely Fair Scheduler)** | Linux's default scheduler; uses vruntime to be fair | Modern, efficient, scales to many cores |
| **vruntime** | Virtual runtime; tracks how much CPU time a process has used | Lower vruntime = more CPU needed = gets scheduled sooner |
| **switch\_mm()** | Kernel function that switches address spaces | Called during context switch to different process |
| **CR3** | Control Register 3; holds physical address of page table root | Loading new value switches address space |
| **PGD (Page Global Directory)** | Top-level page table; root of the page table hierarchy | CR3 points to PGD physical address |
| **TLB (Translation Lookaside Buffer)** | Cache inside CPU that stores recent virtual→physical translations | Makes memory access faster; invalidating it is expensive |
| **PCID (Process Context ID)** | CPU feature that tags TLB entries with process ID | Prevents TLB flush on every context switch; huge performance win |
| **ASID (Address Space ID)** | ARM equivalent of PCID | Same concept; tags TLB entries |
| **KPTI (Kernel Page Table Isolation)** | Security mitigation for Meltdown; separates kernel/user page tables | Forces page table switch on every kernel/user transition; adds overhead |
| **Meltdown** | CPU vulnerability that allowed reading kernel memory from user space | KPTI was the main mitigation; still affects performance |
| **iretq** | Interrupt Return instruction for 64-bit x86 | Returns from interrupt; restores CPU state |
| **sysretq** | System Return instruction for 64-bit x86 | Returns from system call; optimized path |
| **switch\_to()** | Kernel macro that actually performs the register switch | Low-level assembly that swaps CPU state |
| **Current** | Pointer to current task's task\_struct | The kernel's way of knowing which process is running |
***
### 💸 COSTS OF CONTEXT SWITCH — VISUAL
```mermaid
flowchart TD
subgraph COSTS["💰 Context Switch Costs"]
C1["1️⃣ Save/restore registers ~100-200 registers"]
C2["2️⃣ Switch memory address space CR3 reload"]
C3["3️⃣ TLB flush (unless PCID)"]
C4["4️⃣ Cache misses Task A's data no longer hot"]
C5["5️⃣ KPTI overhead Extra page table switch"]
C6["6️⃣ Branch prediction cold CPU needs to relearn patterns"]
end
C1 --> TOTAL
C2 --> TOTAL
C3 --> TOTAL
C4 --> TOTAL
C5 --> TOTAL
C6 --> TOTAL
TOTAL["📊 Total cost: ~1-10 microseconds (could be thousands of instructions!)"]
TOTAL --> IMPACT["⚠️ Impact: More context switches = worse performance Why: interrupts, syscalls, process count matter!"]
classDef costs fill:#ffebee,stroke:#c62828
classDef result fill:#fff9c4,stroke:#f9a825
class C1,C2,C3,C4,C5,C6,TOTAL costs
class IMPACT result
```
***
### 🔗 WHY THIS MATTERS FOR EXPLOITS
```mermaid
flowchart TD
subgraph SECURITY["🔒 Security Implications"]
S1["1️⃣ KPTI = Meltdown mitigation Forces page table switch every time"]
S2["2️⃣ PCID = Performance optimization Can leak information via timing?"]
S3["3️⃣ Meltdown = Read kernel memory via speculative execution"]
S4["4️⃣ Spectre = Use branch prediction to leak data across processes"]
end
S1 --> S5["All about managing WHAT the CPU can see"]
S2 --> S5
S3 --> S5
S4 --> S5
S5 --> S6["🔴 Side-channel attacks: Measure timing differences to extract secrets!"]
classDef sec fill:#ffcdd2,stroke:#c62828
classDef result fill:#fff3e0,stroke:#e65100
class S1,S2,S3,S4,S5 sec
class S6 result
```
***
### 💡 KEY TAKEAWAYS
1. **Context switching = saving one process's state and restoring another's**
2. **Triggered by**: timer interrupts, syscalls, blocking operations
3. **Saves all registers**: rip, rflags, rsp, and all general-purpose registers
4. **CR3 reload = address space switch** = TLB flush (expensive!)
5. **PCID** helps avoid full TLB flush (modern CPUs)
6. **KPTI** (Meltdown mitigation) adds extra overhead on every syscall
7. **Costs**: 1-10 microseconds; many instructions; cache misses
***
### 📊 QUICK REFERENCE CARD
| **Component** | **What It Does** | **When** |
| ------------------- | ----------------------------- | ------------------------- |
| **Timer interrupt** | Triggers scheduler to check | Every 1-10ms |
| **Save registers** | Stores current process state | Interrupt entry |
| **Schedule()** | Picks next process to run | After saving state |
| **switch\_mm()** | Switches address space | Different process |
| **CR3 reload** | Changes page tables | Address space switch |
| **TLB flush** | Invalidates translation cache | CR3 reload (without PCID) |
| **switch\_to()** | Switches stack, restores | Register restore |
| **iretq/sysretq** | Returns to user mode | Resume process |
***
### 5. The scheduler: CFS (Completely Fair Scheduler) and beyond
Default scheduling class for normal tasks: **CFS**. Core idea: give every runnable task a fair share of CPU time, tracked via a **virtual runtime** (`vruntime`) - time actually spent on CPU, weighted by priority (`nice` value). CFS always picks the runnable task with the *smallest* `vruntime` (i.e., the one that has been "cheated" out of CPU time the most), using a **red-black tree** keyed by vruntime for O(log n) selection.
```
Run queue (rq), one per CPU, keyed by vruntime (rbtree):
vruntime=10 vruntime=15 vruntime=22
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Task C │◄run next│ Task A │ │ Task B │
└─────────┘ └─────────┘ └─────────┘
(leftmost node = next to run)
```
As of recent kernels (6.6+), CFS has been replaced by default with **EEVDF** (Earliest Eligible Virtual Deadline First) - same spirit (fairness via virtual time), different algorithm for choosing deadlines, better latency guarantees. Conceptually similar enough that the CFS mental model still transfers.
Scheduling classes, in priority order (a higher class always preempts a lower one):
```
1. stop_sched_class - highest priority, used internally (CPU hotplug etc)
2. deadline (SCHED_DEADLINE) - EDF/CBS for hard real-time
3. rt (SCHED_FIFO/SCHED_RR) - real-time, fixed priority 1-99
4. fair (SCHED_NORMAL/CFS/EEVDF) - everything normal
5. idle - runs only when nothing else can
```
**Multi-core**: each CPU has its own run queue. Load balancing periodically migrates tasks between CPUs to keep them even; `sched_setaffinity()` lets you pin a task to specific CPUs (relevant when you want deterministic single-core reproduction of a race-condition PoC).
***
### 6. Interrupts, softirqs, and why it matters for exploitation
Hardware interrupts (from a NIC, disk, timer) trigger the CPU to jump via the **IDT** to a kernel handler, interrupting whatever task was running - completely independent of the scheduler's normal flow. Because interrupt handlers must be fast, heavy work is deferred to **softirqs** / **tasklets** / **workqueues**, run later in a safer context.
```
Hardware IRQ fires
│
▼
top half (IRQ handler): minimal work, e.g. "packet arrived,
copy pointer, ack the device"
│
▼
bottom half (softirq/tasklet/workqueue): the actual heavy
processing, e.g. protocol parsing in NET_RX_SOFTIRQ,
run with interrupts enabled, can be preempted
```
This split matters for **race condition bugs** - a huge class of kernel vulnerabilities come from code that assumed it couldn't be interrupted or run concurrently with a softirq/another CPU, but actually could (classic TOCTOU / missing-lock bugs found by tools like Syzkaller + KCSAN).
***
### 7. Practical commands to build intuition
```
ps -eLf # every thread, with PID/TID
cat /proc//status # State, VmRSS, Threads, etc.
cat /proc//stat # raw scheduler-relevant fields
chrt -p # see scheduling policy/priority
taskset -pc 0-3 # set CPU affinity
strace -f -e trace=clone,execve,fork # watch process creation live
```
***
### 8. Key Terms Defined
* **`task_struct`**: the kernel structure representing one process or thread - PID, memory map, open files, credentials, scheduling info, saved register state.
* **Kernel stack**: a small, fixed-size stack (typically 16KB on x86\_64) per task, used only while that task is executing kernel code.
* **`clone()`**: the underlying syscall behind both `fork()` and `pthread_create()`; flags control what's shared (memory, file descriptors, filesystem context) between parent and child.
* **Thread group**: a set of tasks (threads) that share `mm`, `files`, and `fs` but each have their own `task_struct`, kernel stack, and registers.
* **`TASK_RUNNING`**: a process state meaning runnable - either currently executing or waiting in a run queue for CPU time.
* **`TASK_INTERRUPTIBLE`**: a sleeping state that can be woken early by a signal.
* **`TASK_UNINTERRUPTIBLE` ("D state")**: a sleeping state (usually waiting on disk I/O) that cannot be interrupted by a signal, not even `SIGKILL`.
* **Zombie process**: an exited process whose `task_struct` still exists because its parent hasn't yet called `wait()` to collect its exit status.
* **Copy-on-Write (COW)**: an optimization where `fork()` shares physical pages between parent and child (marked read-only) and only duplicates a page when either side actually writes to it, triggering a page fault.
* **`execve()`**: the syscall that replaces a process's entire memory image with a new program, without creating a new process.
* **Context switch**: the kernel saving one task's full CPU register state and restoring another's so it can run.
* **`switch_to()` / `switch_mm()`**: the low-level kernel mechanisms that perform a context switch, including reloading `CR3` (page table base) when switching to a different process.
* **`vruntime`**: a per-task "virtual runtime" value CFS uses to track how much CPU time a task has effectively received, weighted by priority.
* **CFS (Completely Fair Scheduler)**: the traditional default Linux scheduler for normal tasks, picking the runnable task with the lowest `vruntime` via a red-black tree.
* **EEVDF (Earliest Eligible Virtual Deadline First)**: the scheduler that replaced CFS by default in recent kernels (6.6+), same fairness goal, deadline-based selection.
* **`nice` value**: a user-settable priority hint (-20 to 19) that weights how fast a task's `vruntime` accumulates.
* **Scheduling class**: a priority tier of scheduling policy - `deadline`, `rt` (real-time), `fair` (normal), and `idle`, in descending priority.
* **Top half / bottom half**: the split of interrupt handling into a fast, minimal handler (top half) and deferred heavier processing (bottom half: softirq, tasklet, or workqueue).
* **Softirq**: a deferred, high-priority form of bottom-half interrupt processing that can run on any CPU, used heavily by the network stack.
* **Race condition**: a bug where correctness depends on the relative timing of concurrent operations (across CPUs, or between a process and an interrupt/softirq) that the code didn't properly synchronize against.
Next: **04-memory-management.md** - virtual memory, x86\_64 4/5-level paging, the MMU, SLUB allocator, KASLR/KPTI/SMEP/SMAP in depth - the file most directly relevant to memory-corruption exploit development.
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://alham-rizvi.gitbook.io/alhamrizvi/linux-internals/03-process-management-and-scheduling-x86-x86_64-+.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.