Understanding Linux Process States, Scheduling, and Priority: A Deep Dive into the Kernel

1. Introduction

Process state is an integer in task_struct; a running process is in the run queue, while a blocked process waits for I/O or other resources. Process state changes involve moving between different kernel queues, which are essentially data‑structure insert/delete operations.

Understanding kernel linked lists

If a structure contains multiple next and prev pointers, a single task_struct can belong simultaneously to the run queue, a global list, a binary tree, etc.

2. Process states

A Linux process (task) can be in several states, defined in the kernel source:

/* The task state array is a strange "bitmap" of
 * reasons to sleep. Thus "running" is zero, and
 * you can test for combinations of others with
 * simple bit tests.
 */
static const char * const task_state_array[] = {
    "R (running)",   /* 0 */
    "S (sleeping)",  /* 1 */
    "D (disk sleep)",/* 2 */
    "T (stopped)",   /* 4 */
    "t (tracing stop)",/* 8 */
    "X (dead)",      /* 16 */
    "Z (zombie)",    /* 32 */
};

R – Running or Runnable Status description: The process is executing on the CPU or waiting in the run queue. Trigger: Active execution or ready for scheduling. S – Interruptible Sleep Status description: The process is waiting for an event (e.g., I/O) and can be awakened by a signal. Trigger: Calls such as sleep() , read() that block. D – Uninterruptible Sleep Status description: The process is waiting for non‑interruptible operations (e.g., disk I/O) and does not respond to signals. Trigger: Disk I/O or certain kernel operations. T – Stopped Status description: The process has been stopped by a signal such as SIGSTOP , SIGTSTP and awaits SIGCONT . Trigger: Manual pause (Ctrl+Z) or debugging. Z – Zombie Status description: The process has terminated but its exit status has not been collected by the parent via wait() . Trigger: Parent has not called wait() after child exit. t – Tracing stop Status description: The process is stopped by a debugger (e.g., gdb) during tracing. Trigger: Breakpoint or single‑step execution. X – Dead Status description: The child has exited and the parent has not yet reaped it. Trigger: Short‑lived state after exit before removal.

2.1 Viewing process states

Command: ps aux or

ps axj

a: Show processes of all users (requires appropriate permissions). x: Show processes without a controlling terminal (typically daemons). j: Show job‑control information such as PGID, SID, PPID. u: User‑oriented format with detailed resource usage.

2.2 Zombie processes

A zombie appears when a child exits but the parent never calls wait(). The zombie remains in the process table, holding its exit status until the parent reaps it, which can waste kernel resources.

2.3 Orphan processes

When a parent exits, its children become orphans and are adopted by systemd (PID 1). Orphans are not zombies; they continue running under the init process.

3. Process priority

3.1 Concept

Priority determines the order in which the scheduler allocates CPU time.

Lower numeric values mean higher priority.

In Linux, priority is stored in task_struct and can be adjusted via the nice value.

Effective priority = PRI (default) + NI (nice).

3.2 Viewing system processes

Command: ps -al (a = all, l = long format). Important fields: UID: User ID of the process owner. PID: Process identifier. PPID: Parent process identifier. PRI: Base priority (default 80). NI: Nice value that modifies priority.

3.3 Changing priority

Use top (press “r” then enter PID and new nice value) or the commands nice and renice. The kernel system call setpriority() also adjusts priority.

3.4 Competition, independence, parallelism, concurrency

Competition: Multiple processes contend for limited CPU resources.

Independence: Processes run without interfering with each other.

Parallelism: Different CPUs execute multiple processes simultaneously.

Concurrency: A single CPU interleaves execution of multiple processes via context switches.

4. Process switching

A context switch saves the current CPU register state into the process’s task_struct and restores the registers of the next scheduled process.

5. Linux 2.6 O(1) scheduler

Each CPU has a runqueue. Processes are placed into priority‑ordered arrays ( queue[140]) and a bitmap accelerates the search for the highest‑priority non‑empty queue. Active and expired queues are swapped periodically to recycle time slices.