01-os-fundamentals-multithreading.md

01 - OS Fundamentals & Multithreading Deep Dive

To excel in the Juspay Hackathon Part B and System Interviews, you must understand Operating System fundamentals not just as definitions, but how they practically impact the execution of your code on a machine.

1. Process vs. Thread: The Deep Dive

What is a Process?

A process is an instance of a computer program that is being executed. It contains the program code and its activity.

Memory Layout of a Process:

  • Text/Code Segment: Contains the compiled machine code instructions. Read-only.
  • Data Segment: Contains global and static variables.
    • Initialized Data: Variables initialized by the programmer.
    • BSS (Uninitialized Data): Variables initialized to zero by default.
  • Heap: Used for dynamic memory allocation (e.g., malloc in C, new in C++/Java). Grows upwards.
  • Stack: Used for local variables, function parameters, return addresses, and control flow. Grows downwards.

Process Control Block (PCB): The OS maintains a PCB for each process, storing:

  • Process ID (PID)
  • Process State (New, Ready, Running, Waiting, Terminated)
  • Program Counter (address of the next instruction)
  • CPU Registers
  • Memory management info (Page tables)
  • Open file descriptors

What is a Thread?

A thread is the smallest sequence of programmed instructions managed by a scheduler. A process can have multiple threads.

What do Threads Share? Threads within the same process share the Text Segment, Data Segment, Heap, and Open Files. This is why multithreading is powerful: threads can communicate instantly by reading/writing the same variables in the Heap/Data segments (which also causes Race Conditions!).

What is Unique to Each Thread? Each thread has its own Stack, Program Counter, and Registers. The OS maintains a Thread Control Block (TCB) for each thread.

IPC (Inter-Process Communication)

Because processes do not share memory (for security), communicating between them is expensive. IPC mechanisms include:

  • Pipes: Unidirectional data channel.
  • Shared Memory: OS maps a segment of memory into the address space of multiple processes.
  • Message Queues: Linked list of messages stored within the kernel.
  • Sockets: Used for network communication or between processes on the same machine.

2. Context Switching (The Hidden Cost)

Interview Question: What happens when you play a song and code on a single-core PC? Answer: The OS uses rapid Context Switching to create the illusion of simultaneous execution.

What exactly happens during a Context Switch?

  1. The OS interrupts the currently running thread (Thread A).
  2. It saves Thread A's context (Registers, Program Counter) into its TCB/PCB.
  3. The CPU scheduler selects the next thread in the Ready queue (Thread B).
  4. The OS loads Thread B's context from its TCB/PCB into the CPU registers.
  5. Execution resumes at Thread B's Program Counter.

Why is it expensive?

  • CPU Time: The CPU is doing administrative work instead of executing user code.
  • Cache Invalidation: When switching processes, the Translation Lookaside Buffer (TLB) and CPU caches (L1/L2) are often flushed or become filled with irrelevant data. This means the new process will experience "cache misses" and run slowly at first.
  • Note: Switching between threads of the same process is faster because they share the same memory address space (no TLB flush needed).

3. Multicore Processors & Parallelism

Concurrency vs. Parallelism

  • Concurrency (Single Core): The CPU time-slices between tasks. Only one task executes at any exact nanosecond, but progress is made on all of them.
  • Parallelism (Multicore): Multiple tasks execute at the exact same time on different physical cores.

Cache Coherence (MESI Protocol)

In a multicore system, each core has its own private L1/L2 cache, and they share an L3 cache.

  • The Problem: If Core 1 and Core 2 both cache a shared variable X, and Core 1 modifies X, Core 2's cache has "stale" data.
  • The Solution (MESI): Hardware enforces rules to keep caches coherent.
    • Modified: Only this cache has the valid, modified value.
    • Exclusive: Only this cache has the value, it matches main memory.
    • Shared: Multiple caches hold the value, all match main memory.
    • Invalid: The cache line is stale and must be fetched from memory again.

Amdahl's Law

You cannot endlessly throw cores at a problem to make it faster. Amdahl's law states that the maximum speedup of a system is limited by the strictly sequential (non-parallelizable) portion of the code.

  • Formula: Speedup = 1 / ((1 - P) + P/N)
    • P = parallelizable fraction of the code
    • N = number of cores
  • Interview context: If 10% of your tree locking logic requires a global mutex, your maximum speedup is 10x, even with 1000 cores.

4. CPU Scheduling

The OS decides which thread runs next.

  • FCFS (First Come First Serve): Non-preemptive. Can lead to the Convoy Effect (short jobs wait for a long CPU-bound job).
  • SJF (Shortest Job First): Optimal for minimizing average wait time, but impossible to know exact burst time.
  • Round Robin: Each thread gets a time quantum (e.g., 10ms). Preemptive. Excellent for responsiveness.
  • Priority Scheduling: Can lead to Starvation (low priority tasks never run). Fixed via Aging (gradually increasing priority of waiting tasks).