Lesson 4 · Operating Systems

Processes, Threads, and CPU Scheduling

A process is an address space with resources; a thread is a schedulable flow of execution inside it. Processes cannot reach each other's memory, threads share all of theirs — which makes thread communication free and thread bugs shared-memory races.

Process vs Thread

A process is what the OS allocates resources to: a virtual address space, open file descriptors, a working directory, a user identity, and a signal disposition. The kernel tracks it in a process control block (task_struct on Linux) holding its PID, saved registers, state, scheduling parameters, and memory map.

A thread is what the OS schedules. Threads inside one process share code, heap, globals, and file descriptors, but each has its own registers, program counter, stack, and thread-local storage. That split is the whole story: the stack is private because call frames must not be interleaved, and everything else is shared because sharing is the point.

The consequence runs in both directions. Two threads exchange data by writing a variable — no copying, no kernel involvement — but they also corrupt that variable if they write it concurrently without a lock. Two processes cannot corrupt each other at all, and must pay for a pipe, a socket, or an explicit shared-memory mapping to communicate.

Cost differs by roughly an order of magnitude. Creating a thread means a stack and a scheduler entry, a few microseconds; creating a process means a new address space and page tables. Linux blurs this deliberately — fork and pthread_create both call clone, differing only in which resources are flagged as shared, so a thread there is a task that happens to share its memory map.

Process = resource container; thread = unit of scheduling
Private per thread: registers, program counter, stack, TLS
Shared across threads: code, heap, globals, file descriptors
On Linux both are clone with different sharing flags

Types of Threads in OS

The types of threads in OS design differ by who does the scheduling. A kernel-level thread is known to the kernel and scheduled by it, so it can use a core of its own and a blocking call only blocks that thread. A user-level thread is managed entirely by a library the kernel cannot see, which makes creation and switching very cheap — no trap, just a register swap — but means one blocking system call stalls every thread in the process.

Mapping between the two gives the classic models. Many-to-one puts many user threads on one kernel thread: fast switches, no parallelism, and one block stops everything. One-to-one gives each user thread its own kernel thread, which is what Linux, Windows, and modern pthreads do — real parallelism at the cost of a kernel object per thread. Many-to-many multiplexes M user threads onto N kernel threads and is the flexible middle ground that proved hard enough to implement that most systems abandoned it.

The idea came back as language runtimes rather than OS features. Go's goroutines, Java's virtual threads, and async/await in Python and Rust are all many-to-many schedulers in user space, built because a kernel thread per concurrent operation is too heavy at a scale of hundreds of thousands.

One more distinction matters for correctness: a daemon thread does not keep the process alive, so the runtime exits when only daemons remain. Getting that wrong is why a program either exits with work unfinished or refuses to exit at all.

Kernel-level: scheduled by the OS, blocks alone, costs a kernel object
User-level: cheap switches, invisible to the kernel, one block stalls all
One-to-one is what Linux and Windows actually use today
Goroutines and virtual threads revive many-to-many in user space

Process States and the Life Cycle

A process moves through five states. New while the kernel builds its structures; ready when it can run and is only waiting for a core; running when it is on one; waiting (blocked) when it needs an event that has not happened; and terminated once it has exited.

Only three transitions matter. Ready to running is the scheduler dispatching. Running to ready is preemption — the process was still able to run and was moved aside anyway, on a timer interrupt or when something higher-priority woke. Running to waiting is the process blocking itself on I/O or a lock, which is voluntary and does not consume the rest of its slice.

The distinction is what makes I/O-bound and CPU-bound workloads behave so differently. A process that blocks after 2 ms of a 10 ms quantum gives back 8 ms, so schedulers can afford to favour it — it will not monopolise anything. A process that always uses its whole slice gets deprioritised precisely because it never yields.

Termination has a wrinkle. An exited process stays as a zombie — just its exit status and PID — until the parent calls wait. A parent that never reaps leaks PIDs. Conversely, a process whose parent dies first is an orphan and is re-parented to init, which reaps it automatically. An uninterruptible blocked process (state D) is the one that cannot even be killed, because it is mid-way through a device operation the kernel cannot abandon.

New, ready, running, waiting, terminated
Preemption is involuntary; blocking is the process's own choice
I/O-bound processes return their slice, so schedulers favour them
Zombies await reaping; orphans are re-parented to init

Key reference

Terms, operations, and practical uses

Execution units

ProcessAn address space plus resources; the unit the OS allocates to.
ThreadA schedulable flow inside a process; the unit the OS dispatches.
PCBKernel record of PID, saved registers, state, and memory map (task_struct on Linux).
Private per threadRegisters, program counter, stack, and thread-local storage — nothing else.

Process states

ReadyRunnable, waiting only for a core.
RunningCurrently executing on a CPU.
WaitingBlocked on I/O or a lock; gave up its slice voluntarily.
ZombieExited but not yet reaped by its parent's wait call.

Types of schedulers

Long-termAdmission control; sets the degree of multiprogramming.
Short-termPicks the next ready thread every few ms; must be very cheap.
Medium-termSwaps whole processes out under memory pressure.
DispatcherPerforms the switch itself; its cost is dispatch latency.

Scheduling algorithms

FCFSArrival order; suffers the convoy effect behind one long job.
SJF / SRTFOptimal average waiting time, but burst length is unknowable.
Round robinFixed quantum rotation; 10-100 ms keeps switch overhead near 1%.
Multilevel feedbackThreads move between queues, so interactivity is inferred, not declared.

Concurrency

Race conditioncounter++ is load, add, store — interleaving those loses an increment.
MutexExclusive and owned, so it supports priority inheritance.
SemaphoreAn ownerless counter for capacity limits and signalling.
Coffman conditionsMutual exclusion, hold-and-wait, no preemption, circular wait — break one.

Implementation

Protect a shared counter

from threading import Lock, Thread

counter = 0
lock = Lock()

def worker():
    global counter
    for _ in range(3):
        with lock:
            counter += 1

a = Thread(target=worker)
b = Thread(target=worker)
a.start()
b.start()
a.join()
b.join()
print('counter =', counter)

#include <iostream>
#include <mutex>
#include <thread>
using namespace std;
int counter = 0;
mutex counterMutex;
void worker() {
    for (int i = 0; i < 3; ++i) {
        lock_guard<mutex> guard(counterMutex);
        ++counter;
    }
}
int main() {
    thread a(worker), b(worker);
    a.join();
    b.join();
    cout << "counter = " << counter << '\n';
}

class Main {
    static int counter = 0;
    static synchronized void increment() {
        counter++;
    }
    public static void main(String[] args) throws Exception {
        Runnable worker = () -> {
            for (int i = 0; i < 3; i++) increment();
        };
        Thread a = new Thread(worker), b = new Thread(worker);
        a.start();
        b.start();
        a.join();
        b.join();
        System.out.println("counter = " + counter);
    }
}

Watch it run

Step through it

Running on two workers increment three times each

Output

Read all 13 Steps

Start both workers The scheduler may interleave the threads in many ways. The following frames show one valid interleaving; the lock protects every individual increment.
A locks increment 1 A acquires the lock for its first loop iteration. B cannot modify the counter until this increment finishes.
A writes 1 and unlocks A completes one read-modify-write operation, then leaves the with/lock_guard/synchronized section.
B locks increment 1 In this possible schedule, B runs next and acquires the now-free lock.
B writes 2 and unlocks B's protected increment changes 1 to 2 and then releases the lock.
A locks increment 2 A begins its second loop iteration and acquires the lock again; one acquisition does not cover all three iterations.
A writes 3 and unlocks A finishes its second protected increment and releases the lock.
B locks increment 2 B acquires the lock for its second iteration after A has released it.
B writes 4 and unlocks B changes the shared value from 3 to 4 and releases the lock.
A locks increment 3 A obtains exclusive access for its final iteration.
A writes 5 and unlocks A performs its third increment, releases the lock, and has no iterations left.
B locks increment 3 B acquires the lock for the final remaining increment.
B writes 6 and unlocks B changes 5 to 6, releases the lock, and finishes. A different schedule may change the order of these frames, but not the protected final count.

Races, Synchronization, and Deadlock

A race condition is a result that depends on timing the program does not control. counter++ is the canonical case: it compiles to a load, an add, and a store, and two threads interleaving those three steps lose an increment. The tracer on this page walks exactly this, protecting each increment with a lock.

The primitives differ in what they express. A mutex grants exclusive access and has an owner, so it can be checked and can support priority inheritance. A semaphore is a counter with no owner, used for capacity limits and signalling between threads. A condition variable lets a thread sleep until a predicate may have changed, and must always be waited on in a loop because of spurious wakeups. A read-write lock admits many readers or one writer, which pays off only when reads dominate.

The types of deadlock in OS discussions all reduce to one definition: deadlock requires all four Coffman conditions at once — mutual exclusion, hold-and-wait, no preemption, and circular wait. Break any one and deadlock becomes impossible. In practice the lever is circular wait — impose a global lock order and acquire always in that order. The alternatives are trylock with backoff (breaking hold-and-wait) or the Banker's algorithm, which needs resource demands declared up front and is almost never practical.

Two related failures are not deadlock. Livelock is threads actively responding to each other and making no progress — two people stepping aside in a corridor forever. Starvation is one thread never scheduled or never granted a lock while others proceed; priority inversion, where a high-priority thread waits on a lock held by a preempted low-priority one, is the case that stalled Mars Pathfinder and is fixed with priority inheritance.

counter++ is three instructions — that gap is the race
Mutex has an owner; a semaphore is an ownerless counter
Always wait on a condition variable inside a predicate loop
Break circular wait with a global lock order — the practical fix