Goyalayus

CPU Executes Instructions

The first thing is that the CPU executes instructions. Those instructions can come from multiple programs, and the CPU can switch between those programs, meaning it can switch between their instructions. Now, how does it switch? To switch, you need an instruction too, right? We will study this in detail later, but the operating system kernel has the superpower to interrupt execution and switch between programs. This is an abstract explanation for now, but we will return to it in more detail later.

Software Threads and SMT Hardware Threads

Suppose a machine has four cores. Sometimes we say it has eight CPUs. But what does that mean? It has only four physical cores, so how can it have eight CPUs? Each core can have two SMT hardware threads, giving the machine eight logical CPUs.

What are these hardware threads? Suppose a thread is running on one core and it requests a memory load. Loading data can take many clock cycles, so the core's compute resources could otherwise sit idle.

With only software threads, switching between threads is expensive and can take many clock cycles. If a load operation takes only a few cycles, a software context switch may cost more than the time saved. Hardware threads help avoid this overhead. Each core can keep two threads ready at the same time. When thread A requests a memory load and has to wait, the core can immediately switch to thread B, which is another software thread mapped to the core's other SMT hardware thread. From the software's perspective, this switch is almost instantaneous.

What a Thread Stores

Now, a thread has to store several things. For example, it needs a counter that tracks which instruction it is currently executing. This is the program counter (PC). I have not told you what a PC is? Actually, I have told you what a PC is, right? Basically, for a CPU core, it tracks which instruction in memory the CPU is currently executing. After that instruction finishes, we add the instruction's size to its memory address. That gives us the memory address of the next instruction.

Shared Core Resources

What else does the hardware need to store? It needs to remember which instruction it is currently executing. Each hardware thread has its own program counter and private registers for its private values. However, the threads share resources such as the L1 cache, the L2 cache, and the core's execution units.

Processes

What is a process?

A program is just a file, such as an executable file. When you run that program file, the operating system creates a process. There can be multiple processes created from a single program file.

Process Control Block

Each process has a process ID (PID) and its own memory, including stack and heap memory. The operating system keeps track of this information in a process control block (PCB), which is a struct. It contains fields such as:

The process ID (PID)
The location of the stack and heap memory
The saved CPU state
The file descriptor table
Parent-child process information

Saved CPU State

Each process has a saved CPU state. This tells the operating system where the process should continue after it is scheduled again. The saved state includes the program counter, which tells the process where to continue; the CPU registers; the stack pointer; and CPU flags, which represent the current condition of the CPU.

File Descriptors

Each process also has file descriptors. A file descriptor is an integer handle for an open resource. For example, if I have a TCP socket open, the operating system might assign it file descriptor 4. If communication needs to happen through that socket, I can refer to file descriptor 4 in system calls such as read, write, send, or recv.

The file descriptor is not the socket object itself. It is a handle that refers to an object managed by the operating system.

Parent-Child Information

Finally, the process stores parent-child information: which process is its parent and which child processes belong to it.

Process Memory Layout

Every process gets its own virtual memory layout:

Low addresses
┌─────────────────────────────┐
│ Code / text                 │
├─────────────────────────────┤
│ Read-only data              │
├─────────────────────────────┤
│ Initialized global data     │
├─────────────────────────────┤
│ BSS                         │
├─────────────────────────────┤
│ Heap                        │
│       grows upward  ↑       │
│                             │
│          unused space       │
│                             │
│       grows downward ↓      │
│ Stack                       │
└─────────────────────────────┘
High addresses

What Is a Stack Frame?

Consider:

void first() {
    second();
}

void second() {
    third();
}

void third() {
}

While third() is executing, the stack might look like this:

Top of stack

┌──────────────────────────┐
│ third() stack frame      │
├──────────────────────────┤
│ second() stack frame     │
├──────────────────────────┤
│ first() stack frame      │
├──────────────────────────┤
│ main() stack frame       │
└──────────────────────────┘

Stack Pointer

The CPU has a special register called the stack pointer.

It points to the current top of the stack.

Conceptually:

Stack pointer
      ↓
┌───────────────────┐
│ current frame     │
├───────────────────┤
│ previous frame    │
├───────────────────┤
│ older frame       │
└───────────────────┘

When a function call creates a new stack frame, the stack pointer changes.

When the function returns, it changes back.

This is one reason the stack is fast: allocation is often largely just adjusting a pointer.

Process States

A process moves through a set of states during its lifetime:

                         process finishes
New ─────→ Ready ─────→ Running ─────────────→ Terminated
             ↑             │
             │             │ time slice expires
             └─────────────┘ or task yields

             ↑             │
             │             │ waits for I/O,
             │             │ lock, timer, etc.
             │             ↓
             └────────── Blocked
                  event occurs

Example: Output Redirection

Suppose you run:

python script.py > output.txt

The shell roughly performs these steps:

The shell calls fork().
The child process closes or replaces file descriptor 1, which is standard output.
The child makes file descriptor 1 refer to output.txt.
The child calls exec() to load Python.
Python writes to standard output, file descriptor 1.
Those bytes go into output.txt.

How a Process Is Born

There are three important operations to understand: fork(), exec(), and wait().

`fork()`

When a process calls fork(), the operating system creates a child process at that point. The code before the fork() has already run, and both the parent and child continue execution from the instruction after fork().

The child process is initially a copy of the parent, but they are separate processes. They can have the same virtual memory addresses, but those addresses do not refer to the same physical memory.

Copy-on-Write

In the past, the operating system would copy the entire memory of the parent process for the child. Modern systems generally use copy-on-write instead. The parent and child initially share the same physical memory pages. If either process tries to write to a page, the operating system copies only that page for the writing process.

The operating system tracks these pages and performs the copy only when a write occurs.

`wait()`

When the parent process calls wait(), it blocks at that line until one of its child processes finishes. The call returns information about the child process, such as whether it exited successfully and what its exit status was.

There are also non-blocking forms of wait. These return immediately if a child process has not exited yet.

`exec()`

exec() does not create a new process. It replaces the existing process image with the program you provide. For example, a process can call exec() to replace itself with Python. The process keeps its PID, but its code, data, heap, and stack are replaced by those of the new program.

If you print something before calling exec(), that print runs. If exec() succeeds, a print after it does not run because the old program has been replaced.

File Descriptors and `fork()`

File descriptors are inherited across fork(). The parent and child can refer to the same underlying open file description, such as a file or a TCP socket. This is why the child in the output-redirection example can change file descriptor 1 before calling exec(), and the new program automatically writes its standard output to output.txt.

User Mode and Kernel Mode

There are two important privilege modes: user mode and kernel mode.

Applications run in user mode. We do not want arbitrary applications to access the memory of other processes or modify page tables directly, so user-mode code has restricted permissions.

Kernel mode has the highest privileges. The CPU keeps track of the current privilege level while code is executing, and privilege applies to memory access as well as instruction execution. It is more precise to say that an instruction executes while the CPU is in user mode or kernel mode; an instruction itself is not permanently a user-mode or kernel-mode instruction.

What Runs in Kernel Mode?

The kernel is responsible for privileged operations such as:

Process scheduling
Virtual memory management
Device drivers
File systems
Networking
System call handling
Interrupt handling
Permissions and security

System Calls

When you write something like read(fd, buffer, 100), you are not performing only a user-space function call. You are also requesting a system call. A system call is a controlled entry point into the kernel.

The kernel contains the implementation of these privileged operations. It checks whether the file descriptor is valid, whether the memory range is valid, and whether the process has permission to perform the operation. Only then does it carry out the request.

malloc() is not itself a kernel function. It is generally a user-space memory allocator. However, when it needs more memory from the operating system, it uses system calls to request additional memory.

Switching to Kernel Mode

When a program needs to make a system call, the CPU switches from executing user-mode code to executing kernel-mode code. Before making this transition, the CPU preserves enough of the user program's state to resume it later. This includes information such as the program counter, registers, and flags.

The kernel also uses a separate kernel stack instead of the user stack. After checking and handling the system call, the kernel restores the saved user state and returns execution to user mode.

Interrupts, Exceptions, and Traps

An interrupt is an asynchronous event that can cause the CPU to pause the current process. For example, when a process's time slice expires, a timer interrupt can cause the scheduler to switch to another process.

An exception is a synchronous event caused by the instruction currently being executed. An invalid memory access is an example of an exception.

A trap is a deliberate, synchronous transition into the kernel. System calls use this kind of controlled transition, although modern processors provide dedicated system-call instructions as well.

A system call is therefore not the same thing as a timer interrupt. It is a synchronous request made by the process. However, an interrupt can occur while a system call is running, and the process can also be preempted while the kernel is handling it.

Virtual Memory and Page Tables

Now let's look at page tables, which are the mechanism behind virtual memory.

Every process gets its own virtual address space. The program uses virtual addresses, and the CPU's memory-management unit (MMU) translates those addresses into physical addresses using the process's page table.

A page table maps a virtual page to a physical page frame:

Virtual page  ──→  Page table  ──→  Physical page frame

A virtual page and a physical page frame are not required to start at the same address. The page table stores the physical frame corresponding to each virtual page. The offset within the page stays the same during the translation.

This does two important things.

Stable Virtual Addresses

First, virtual memory gives each process a stable address space that is independent of the physical layout of RAM. When an instruction uses a virtual address, the MMU translates it to the appropriate physical address. The operating system can move the data to a different physical page without changing the address that the process uses.

This means that a change in the physical location of the data does not change the process's virtual address mapping unless the operating system deliberately changes the page table.

Process Isolation

Second, page tables prevent processes from looking into or modifying each other's memory. Each process has its own mappings and permissions. User-mode code cannot directly modify page tables or create mappings to arbitrary physical memory; those operations are controlled by the kernel.

Processes and Threads

Every process begins with a main thread.

A process provides resources such as:

A virtual address space
Code and read-only data
Heap memory
Global variables
Open files and file descriptors
Security credentials and permissions

A thread is an execution path inside a process. Multiple threads can execute different functions or different instructions from the same process and the same code.

What Belongs to a Thread?

Each thread needs its own:

Program counter, because different threads can be executing different instructions
CPU registers, which hold the thread's current values
Stack, because each thread can have a different call sequence and different local variables
Scheduling state, such as ready, running, or blocked

Threads do not have their own separate heap or copy of the global variables. Threads in the same process share those resources. If one thread changes a global variable, the other threads can observe that change.

If you want a global variable to have a separate copy for each thread, you use thread-local storage. For example, thread_local is a thread-local storage specifier in C++.

PCB and TCB

We previously discussed the process control block (PCB). The PCB stores process-specific information and resources. Each thread also has a thread control block (TCB), which stores thread-specific information such as its program counter, registers, stack pointer, stack, and scheduling state.

So, it is not quite correct to say that every thread has a PCB. The process has a PCB, and each thread has a TCB associated with that process.

If one thread crashes, the entire process may crash. In that case, the other threads in the same process also stop, although the exact behavior depends on the type of failure and how the program handles it.

Registers and the Memory Hierarchy

Registers provide the fastest storage available to the CPU. A simplified memory hierarchy, from fastest to slowest, is:

CPU registers
L1 cache
L2 cache
L3 cache
RAM
SSD or hard-disk storage

As we move down this hierarchy, storage generally becomes larger and slower.

The compiler mostly decides which values should stay in registers. It performs optimizations such as keeping frequently accessed variables in registers and moving less frequently used values to memory when necessary.

CPU instructions usually operate on values in registers. For example, to add two variables, the CPU generally needs their values in registers. If the values are not already there, the CPU loads them from the cache or memory before performing the operation.

The program counter and stack pointer are also registers associated with the current execution context.

Thread Registers and Context Switching

Why does each thread need its own registers? Suppose two threads are running the same function with different local values. Each thread needs to keep its own values while it executes.

There is another important reason. Suppose a thread is running and an interrupt occurs. The thread may have loaded two values into registers and be about to add them when the interrupt arrives. The CPU must preserve that register state so that the thread can resume later and continue from where it stopped.

The registers are physical hardware inside the CPU; they are not stored in RAM while the thread is actively running. When the operating system switches away from a thread, it saves the thread's architectural register state to memory and restores it when the thread runs again.

With SMT, two hardware threads can be active on the same core. Each hardware thread has its own architectural register state, so the CPU can preserve the state of both threads. The hardware threads share physical execution resources, such as arithmetic units and caches, but the operating system does not need to perform a full kernel context switch every time the core moves between them.

SMT hardware threads can be active at the same time, although they compete for the shared execution resources of the core.

Kernel Threads vs User Threads

There are two broad ways to manage threads: the kernel can manage them, or a user-space runtime can manage them.

Kernel Threads

Kernel threads are threads that are created, maintained, and scheduled by the operating system kernel. The kernel knows about each thread and can schedule, interrupt, block, and resume it independently. This is the model we have been studying so far.

User Threads

User threads are managed by a user-space program or runtime. The kernel does not schedule these threads individually. Instead, it sees only the underlying kernel thread or threads, while the user-space runtime schedules its own threads on top of them.

Goroutines are an example of user-space scheduled units. The Go runtime schedules goroutines onto operating-system threads.

Why Create User Threads?

Switching directly from one kernel thread to another can be expensive. The operating system may need to handle an interrupt, enter the kernel, save the current thread's state, schedule another thread, restore its state, and return to execution.

A user-space runtime can switch between user threads without entering the kernel for every switch. This can make the switch much cheaper. That is the main idea behind user-level threads.

Problems with User Threads

Blocking System Calls

Suppose one kernel thread has three user-level threads scheduled on top of it. If one user-level thread performs a blocking network operation, the kernel blocks the underlying kernel thread.

The other two user-level threads may be ready to run, but they cannot run because the only kernel thread on which they are scheduled is blocked. A runtime can work around this with non-blocking I/O or multiple kernel threads, but the basic one-kernel-thread model has this limitation.

No Direct Kernel Scheduling

The operating system cannot directly see or schedule the individual user-level threads. In a simple user-level threading model, the kernel cannot interrupt one user thread and give another user thread a turn because it sees only the underlying kernel thread.

If a user thread runs for too long without yielding, it can prevent the other user threads from making progress. The user-space runtime can implement cooperative yielding or its own preemption mechanisms, but the kernel does not schedule those user threads directly.

Limited Parallelism

There is one more limitation: user-level threads backed by only one kernel thread cannot execute truly in parallel across multiple CPU cores. The kernel schedules the underlying kernel thread, so only that one kernel thread can run on a core at a time. The user-level threads share its execution time.

To use multiple CPU cores, the runtime must create or use multiple kernel threads and schedule the user-level threads across them. The kernel can then schedule those underlying kernel threads on different cores.

Scheduler

The scheduler should be fair, so every thread gets a fair share of work. It should also maintain throughput, keep latency low, and avoid starvation. Priority is important too: a keyboard click should be handled quickly, while a long-running compiler task can tolerate a second or two of delay.

A thread can be switched in two ways:

Voluntary switch, for example, when a thread starts waiting for data.
Interrupt, which is a hardware mechanism.

On every CPU core, periodic interrupts allow the scheduler to run and choose what to execute next.

We are not going to deep dive into scheduling algorithms here, but one idea we will use is the run queue.

A run queue is the list of runnable threads allowed for a CPU core. The scheduler decides this list.

Why do this per core?

If a single global queue is used with many cores, there is a chance of races, where multiple cores may pick the same thread.

The scheduler is also a load balancer. If one run queue becomes empty and another gets full, it migrates threads across run queues so work is distributed more evenly. Switching threads between run queues is not free, so the scheduler tries to minimize migration overhead.

A thread switch also has cache costs. If a thread is repeatedly touching a data set, that data often stays in cache. When the thread is descheduled and another thread runs, useful cache lines may be evicted, so when the original thread resumes it can suffer cache misses. For compute-heavy workloads, too much preemption can waste more time switching and rewarming cache than doing useful work, so excessive thread switching is usually avoided.

Interrupts, Top Half, and Bottom Half

Suppose a network packet arrives while thread B is waiting. The thread is in a blocked state. A hardware interrupt notifies the kernel that the packet is available, which means the kernel can mark that work as runnable. The scheduler can then decide whether to run B now or later.

Interrupt handling is usually split into two parts:

Top half: runs immediately and handles the urgent work needed to acknowledge and register the event.
Bottom half: runs later for deferred work that can wait, such as the heavier processing.

This split avoids blocking the system on long interrupt work and keeps latency lower.

Direct Memory Access (DMA)\n\nDMA is a very efficient way to move data without burning CPU cycles on byte-by-byte copy work.\n\nSuppose one GB arrives from a device and you need it in RAM. If the CPU handled the entire copy, it would consume a lot of CPU cycles. With DMA, the CPU sets up a transfer and tells the DMA engine to copy the data from device input to RAM.\n\nAfter setup, the transfer proceeds while the CPU can work on other tasks instead of stalling on the copy. So CPU cycles are used more efficiently.\n\n## Wait Queues\n\nWhen a thread requests I/O and blocks, it is put into a wait queue.\n\nWhen the requested data or event arrives, the kernel removes the thread from the wait queue and makes it runnable again.\n\nWait queues are the kernel mechanism for parking blocked threads until an event they are waiting for completes.

Mutex (Locks)

Mutexes are locks on variables that multiple threads can access.

Race conditions happen when multiple threads update the same value at the same time. You might expect +2, but only get +1 if both updates interfere.

Locks make it safer.

But locks can also make things slow. If 100 threads are waiting for a lock held by one thread, it becomes mostly sequential.

Semaphores vs Condition Variables

Semaphores

Semaphores keep a count. Example: 100 threads want a shared DB, but we only have 5 DB connections.

Semaphore count is 5.
At most 5 threads can access the resource.
More than 5 block/wait.

Condition Variables

A condition variable waits on a state predicate.

While a condition is true/false (depending on predicate), thread waits.
When the condition changes, the waiting thread is awakened (for example, by a wake-up signal).

Producer-Consumer with Condition Variables

Consumer:
lock(queue_mutex)
queue empty?
yes
wait()

In a condition-variable wait, two steps need to happen atomically:

Check condition (queue empty?)
Release the lock and go to sleep immediately

If these are not atomic, this can happen: the consumer sees empty, then context-switches, producer inserts data, and consumer goes to sleep. Then the producer may wait on the full condition while consumer is already sleeping. That can deadlock the producer-consumer flow.

Deadlock

Deadlock means:

Two or more threads are permanently waiting for each other.

Nobody can continue.

Classic example: two locks

Suppose:

Lock A Lock B

Two threads:

Thread 1:

lock(A) lock(B) Thread 2:

lock(B) lock(A)

Now the timing:

Thread 1:

gets A

Thread 2:

gets B

Now:

Thread 1: has A waiting for B

Thread 2: has B waiting for A

Result:

Thread 1 waits forever

Thread 2 waits forever

The program is frozen.

Real example: databases

Imagine:

Transaction 1:

locks User table

needs Order table

Transaction 2:

locks Order table

needs User table

Both wait.

Database systems handle this by:

detecting cycles, aborting one transaction, retrying.

We also next small atomic available to us, for example, increment a number. So we don't need to do this, that whole mutex thing. Just do a atomic, atomic increment and it will just directly increment the number instead of, like, locking, then like, running the instruction, then locking altogether.

From CPU Hardware to Concurrency, Threads, Coroutines, and Async I/O: The Hitchhiker's Guide to Concurrency