Process Concepts and States

A program is a passive entity (file on disk); a process is an active entity with a program counter, registers, stack, and resources. The Process Control Block (PCB) stores per-process info: PID, process state, program counter, CPU registers, scheduling info (priority), memory-management info (page/segment tables), accounting info, and I/O status (open files). Memory aid: 'PC RAMS-IO' (PID, Counter, Registers, Accounting, Memory, State, IO). The PCB is saved/restored during a context switch. A process address space has four regions: Text (code), Data (globals), Heap (dynamic, grows up), and Stack (grows down). Remember 'TDHS' bottom-to-top. Context switch overhead is pure scheduling cost; no useful work is done during it.

Two coders attack the same Dynamic Programming problem. One writes a recursive function with a cache; the other fills a 2-D array in nested loops. Both finish with the same time complexity — yet under the hood they made very different trade-offs. Knowing which style to choose, and why, is the heart of GATE-level DP.

Definition: Memoization (top-down DP). Ordinary recursion plus a lookup table (memo[state]). The first time a sub-problem is solved its answer is cached; every later call returns the cached value in O(1). It is lazy — only sub-problems actually reached are computed.

Definition: Tabulation (bottom-up DP). An iterative algorithm that fills a DP table in dependency order, smallest sub-problem first, until the final answer sits at the last cell. It is eager — every entry in the table is computed.

Same Complexity, Different Constants

Both styles share the universal DP shortcut:

Time = (number of distinct states) × (work per transition).

For Fibonacci, the state is a single integer i from 0 to n, so there are n+1 states; each transition does O(1) work, giving O(n) overall. The same formula applies whether you write fib(n) recursively with a cache, or run for i in 0..n: dp[i] = dp[i-1] + dp[i-2].

But constants matter, especially in GATE numerical questions and in interviews.

• Top-down wins when many states are unreachable from the answer state. Classic example: a path-counting problem on a sparse DAG, where only a small subset of (i, j) pairs is ever explored.
• Bottom-up wins when every state is needed anyway, because it avoids function-call overhead and a deep recursion stack.

Stack Depth, Cache Locality and Constant Factors

Recursive memoization carries a hidden tax — the call stack. For an input that requires depth n recursion, the runtime stores n stack frames; on most systems this overflows around n = 10^4 to 10^5. Tabulation has no such limit. A second hidden tax is cache locality: bottom-up loops walk memory sequentially and benefit from CPU prefetching, while a recursive scheme may jump unpredictably through the memo table.

In return, top-down DP is far easier to derive. You write the natural recurrence, slap on @lru_cache, and you are done. That makes it ideal for problems where the recurrence is non-obvious but the state space is small — many game theory, interval and tree DPs fall in this camp.

Space Optimization — A Bottom-Up Super-Power

Once you compute bottom-up, you can often see that row i only depends on row i-1. So instead of storing the full 2-D table, keep just two rows (or even one) and overwrite. This shrinks space from O(n²) to O(n) — sometimes the difference between Accepted and Memory Limit Exceeded. The 0/1 Knapsack, Longest Common Subsequence and Edit Distance all admit this optimization. Top-down DP cannot do this naturally, because recursion calls are unordered.

Worked example — Fibonacci, three ways:

Question: How many states and transitions does fib(n) have, and what does space optimization give you?
Solution:
Step 1: States — one per value of i, so n+1 states.
Step 2: Transition — fib(i) = fib(i-1) + fib(i-2), which is O(1) work.
Step 3: Time = states × work = O(n) × O(1) = O(n).
Step 4: Bottom-up needs an array of size n+1 → O(n) space; with rolling variables a, b, you reduce to O(1) space.
Conclusion: Same O(n) time for every style, but only tabulation gives O(1) space via the two-variable trick.

Why it matters

GATE Computer Science routinely asks: "What is the time/space complexity of the given DP solution?" The correct answer almost always falls out of counting states × transitions. Memoization-vs-tabulation also appears in the Programming and Data Structures section as MCQs about stack overflow, recursion depth and iterative rewrites — and in interviews at every product company that recruits GATE rankers.

Real-world example

Indian Railways uses DP-style algorithms for seat allocation under quotas and fare-table lookups across thousands of stations. Building the fare matrix once at boot (tabulation) is faster than computing fares lazily at every booking request (memoization), because virtually every station pair is queried daily — a textbook case where bottom-up wins.

Common misconception

"Memoization and tabulation are different time complexities." False. Whenever both visit the same set of states, they have the same big-O time. The differences are in constants, space, and which states are computed. Another myth: "Top-down is always slower because of recursion." Not true when many states are pruned — top-down can be asymptotically the same yet do strictly less work in practice.

A context switch saves the current process state into its PCB and loads the next process's state. Triggered by: interrupts, system calls causing blocking, or preemption (timer). Mode switch (user to kernel) is cheaper than a full context switch and does not necessarily change the running process. Example: if a context switch costs 2 ms and a time quantum is 8 ms, then for every 8 ms of useful work, 2 ms is overhead, giving CPU efficiency = 8/(8+2) = 80%. Smaller quanta increase responsiveness but raise context-switch overhead; larger quanta reduce overhead but approach FCFS behaviour. Saving/restoring registers is hardware-assisted on many architectures.

Cover the answer, recall, then check. 11 cards on process concepts and states for GATE OS.

Q1. Name the five states in the general process state model.
A1. New, Ready, Running, Waiting (Blocked), Terminated. Ready and Waiting processes are in memory; only one process per CPU is Running at a time.

Q2. Which state transition is caused by the scheduler (dispatcher)?
A2. Ready → Running (dispatch). The reverse Running → Ready is caused by a timer interrupt / preemption.

Q3. What transition happens on an I/O request, and what on I/O completion?
A3. I/O request: Running → Waiting. I/O completion: Waiting → Ready (never directly to Running).

Q4. What is stored in a Process Control Block (PCB)?
A4. Process state, program counter, CPU registers, PID, scheduling info (priority), memory-management info (page/segment tables), accounting info, and I/O status (open files, allocated devices).

Q5. What is a context switch and is it useful work?
A5. Saving the current process's PCB state and loading another's. It is pure overhead (no useful computation); its cost is a reason to prefer larger RR quanta.

Q6. Define a zombie process.
A6. A process that has terminated but whose PCB entry remains because the parent has not yet read its exit status via wait(). It holds a table slot until reaped.

Q7. Define an orphan process.
A7. A process whose parent terminated before it. It is re-parented (adopted) by init/systemd, which will reap it.

Q8. Difference between a program and a process?
A8. A program is a passive entity (an executable file on disk); a process is an active entity — a program in execution with its own PC, stack, data and heap.

Q9. What are the typical segments of a process's address space?
A9. Text (code), Data (initialised globals), BSS (uninitialised globals), Heap (grows up, dynamic allocation) and Stack (grows down, function frames).

Q10. What does fork() return in parent and child?
A10. In the child it returns 0; in the parent it returns the child's PID (>0); on failure it returns −1. The child is a near-duplicate copy of the parent's address space.

Q11. Ready and Waiting queues — what are they?
A11. The ready queue holds processes waiting for the CPU; each device/event has its own wait (device) queue. Scheduling moves processes between these queues.