Types of Schedulers & Process Control Block (PCB)

The Story That Explains Schedulers & PCB

A modern computer runs hundreds of processes but has only a few CPU cores. The operating system must decide which process runs, when, and for how long. It also needs a place to remember everything about every process the moment it is paused. Galvin's textbook calls these two ideas the heart of process management.

Foundation — Process States (Quick Recap)

Before understanding schedulers, you need to know the five states a process moves through during its lifetime. Schedulers move processes between these states.

Animated Process State Diagram

Process Control Block (PCB) — What & Why

Every process in the system is represented by a Process Control Block, also called a Task Control Block. Galvin describes it as the data structure that fully identifies a process. When the OS pauses process A to run process B, it saves the entire "state" of A into A's PCB and loads B's state from B's PCB.

Why the PCB Matters

Fields Inside a PCB

Galvin lists the following fields as the minimum information every PCB must carry. Real OSes (Linux task_struct, Windows EPROCESS) extend this significantly.

Animated Anatomy of a PCB

Types of Schedulers — The Three Levels

Operating systems use up to three schedulers, each operating at a different frequency and making a different decision. Galvin classifies them by how often they run and which state transition they control.

Animated — Relative Frequencies of the Three Schedulers

Long-Term Scheduler (Job Scheduler)

Short-Term Scheduler (CPU Scheduler)

The short-term scheduler — also called the CPU scheduler or dispatcher — is invoked every time the CPU becomes free. That happens on every clock interrupt (typically 10 ms), every I/O wait, and every process exit.

Common CPU-Scheduling Algorithms

Animated Round-Robin — Time-Slice In Action

Medium-Term Scheduler (Swapper)

The medium-term scheduler performs swapping: temporarily moving a partially-executed process from main memory to secondary storage, then bringing it back later. This reduces the degree of multiprogramming when memory pressure spikes.

Animated Swap-Out & Swap-In

Animated — All Three Schedulers Working Together

Comparison — All Three Schedulers

Animated — Context Switching With PCB

Practical Example — Modelling a PCB in C

Here is a simplified PCB structure showing what a real kernel writes. This is close to the classical Galvin form.

/* pcb.h - Simplified Process Control Block */
#include <stdint.h>

typedef enum {
    STATE_NEW,
    STATE_READY,
    STATE_RUNNING,
    STATE_WAITING,
    STATE_TERMINATED
} ProcessState;

typedef struct {
    /* --- Identification --- */
    uint32_t pid;                   // unique process ID
    uint32_t ppid;                  // parent PID
    uint32_t uid;                   // owner user ID

    /* --- Process State --- */
    ProcessState state;

    /* --- CPU Context (saved on preemption) --- */
    uint64_t program_counter;
    uint64_t stack_pointer;
    uint64_t registers[16];        // RAX..R15 on x86-64
    uint64_t flags;

    /* --- Scheduling Info --- */
    int      priority;              // 0 = highest
    uint64_t time_slice_remaining;  // for Round Robin
    struct PCB *next_in_queue;    // linked-list pointer

    /* --- Memory Management --- */
    uint64_t base_register;
    uint64_t limit_register;
    void    *page_table;

    /* --- Accounting --- */
    uint64_t cpu_time_used_us;      // microseconds
    uint64_t creation_time;

    /* --- I/O Status --- */
    int      open_files[32];        // file descriptor table
    int      num_open;
} PCB;

Simulating a Round-Robin Short-Term Scheduler

/* Very simplified RR scheduler over a ready-queue of PCBs */
#define QUANTUM_US 10000   // 10 ms time quantum

PCB *ready_head = NULL;    // front of ready queue
PCB *running    = NULL;    // currently on CPU

void enqueue_ready(PCB *p) {
    p->state = STATE_READY;
    p->next_in_queue = NULL;
    if (!ready_head) { ready_head = p; return; }
    PCB *t = ready_head;
    while (t->next_in_queue) t = t->next_in_queue;
    t->next_in_queue = p;
}

void context_switch(PCB *from, PCB *to) {
    // 1. Save current CPU state into 'from' PCB
    if (from) {
        from->program_counter = cpu_get_pc();
        cpu_save_registers(from->registers);
        from->state = STATE_READY;
        enqueue_ready(from);
    }
    // 2. Load 'to' PCB into CPU
    cpu_load_registers(to->registers);
    cpu_set_pc(to->program_counter);
    to->state = STATE_RUNNING;
    to->time_slice_remaining = QUANTUM_US;
    running = to;
}

/* Called on every timer interrupt (every 1 ms, say) */
void timer_tick(uint64_t elapsed_us) {
    if (!running) return;
    running->cpu_time_used_us  += elapsed_us;
    running->time_slice_remaining -= elapsed_us;

    if (running->time_slice_remaining <= 0) {
        // Time-slice expired -> preempt
        PCB *next = ready_head;
        if (next) {
            ready_head = next->next_in_queue;
            context_switch(running, next);
        }
    }
}

Real-World — Linux's task_struct

Linux's PCB is called task_struct and lives in <linux/sched.h>. It has over 100 fields, but the classical Galvin subset is clearly visible.

/* Excerpt from Linux kernel (simplified) */
struct task_struct {
    /* Identification */
    pid_t              pid;
    pid_t              tgid;                // thread group id
    struct task_struct *parent;
    kuid_t             uid;

    /* State & scheduling */
    long               state;               // TASK_RUNNING, TASK_INTERRUPTIBLE...
    int                prio;                // current priority
    int                static_prio;         // nice value based
    struct sched_entity se;                  // CFS scheduling entity
    unsigned int       policy;              // SCHED_NORMAL, SCHED_FIFO...

    /* CPU context — saved in thread_struct */
    struct thread_struct thread;

    /* Memory management */
    struct mm_struct   *mm;

    /* Open files */
    struct files_struct *files;

    /* Accounting */
    u64                utime, stime;       // user/system CPU time
    u64                start_time;
};

Golden Rules