Processes & Scheduling

1. What is a process and how is it different from a program?

A process is a program in execution — an active entity with a program counter, stack, data section, and its own set of resources. A program is passive: a file on disk with a static set of instructions that does nothing until it is loaded.

The process is the dynamic realization of that program — loaded into memory and executing on the CPU. One program can spawn many processes (three Chrome tabs create three processes), and a process has a lifespan from creation to termination, whereas the program persists on disk until it is deleted.

2. What are the five states of a process?

• New — the process is being created.
• Ready — the process is in memory and waiting for CPU allocation.
• Running — the process is currently executing on the CPU.
• Waiting (Blocked) — the process is waiting for I/O, a signal, or an event.
• Terminated — the process has finished, though its PCB still exists until the parent reads its exit status.

A process typically alternates between ready and waiting: it runs, blocks on I/O, becomes ready again, and so on. The transitions are managed by the scheduler.

3. What information is stored in a Process Control Block (PCB)?

The PCB is the data structure the OS keeps for every process to represent it internally. It stores:

• Process ID (PID) — unique numeric identifier.
• Process state — new, ready, running, waiting, or terminated.
• Program counter — address of the next instruction to execute.
• CPU registers — saved during a context switch (accumulators, index registers, stack pointer).
• Scheduling info — priority and queue pointers.
• Memory info — page tables or segment tables.
• I/O status — list of open files and allocated devices.

When a process is suspended, its registers are saved into its PCB; when it resumes, they are loaded back. The PCB is the snapshot that makes context switching possible.

4. What are zombie and orphan processes?

A zombie process has finished executing but still has an entry in the process table because its parent hasn’t called wait() to read its exit status. It consumes a PID but no CPU or memory — it’s just a lingering PCB until the parent cleans it up.

An orphan process’s parent terminated before it did. The kernel re-parents orphans to the init process (PID 1), which adopts them and reaps them when they finish. Both are everyday occurrences — zombies are the bigger interview favorite because they indicate a parent that never calls wait().

5. What is context switching and why is it considered overhead?

Context switching is the CPU saving the current process’s state into its PCB and loading the next process’s state from its PCB. It is what lets multiple processes share the CPU.

It is pure overhead because during the switch the CPU executes zero user code — it saves/loads registers, switches address spaces (which may flush the TLB), and only then resumes useful work. Frequent switches degrade throughput, which is why the scheduling quantum trades off: too small a quantum means too many context switches, each paying that overhead.

6. What are the three types of schedulers?

• Long-term (job) scheduler — decides which processes are loaded from disk into memory, controlling the degree of multiprogramming. Runs infrequently.
• Short-term (CPU) scheduler — picks which ready process gets the CPU next. Runs very frequently, every few milliseconds.
• Medium-term scheduler — swaps processes in and out of memory to disk, used to handle thrashing. Runs occasionally.

The short-term scheduler is the one most people mean by “the scheduler,” and it runs the most often.

7. What are the scheduling criteria used to evaluate algorithms?

The standard metrics:

• Throughput — processes completed per unit time (want it high).
• Turnaround time — total time from submission to completion (want it low).
• Waiting time — total time spent in the ready queue (want it low).
• Response time — time from submission to the first response (critical for interactive systems, want it low).

Different algorithms trade these off. SJF minimizes average waiting time, Round Robin guarantees response time, and FCFS is fair but produces poor average waiting times.

8. What is the FCFS algorithm and what is the convoy effect?

FCFS (First-Come, First-Served) runs processes in arrival order — it is non-preemptive and simple. A short process that arrives behind a long CPU-bound process waits for it to finish.

The convoy effect is the problem: a long CPU-bound process holds the CPU while short I/O-bound processes wait behind it. The I/O devices sit idle, then get flooded all at once when the long process finally finishes. This causes poor resource utilization — CPU and I/O are never busy at the same time.

9. What is SJF/SRTF and why is it optimal?

SJF (Shortest Job First) runs the process with the shortest CPU burst first; it is non-preemptive. SRTF (Shortest Remaining Time First) is the preemptive version — if a new process arrives with a shorter remaining time than the running process, it preempts.

SJF is optimal in the sense that it minimizes average waiting time — provided burst times are known in advance, which they usually aren’t. Its weakness is starvation: long processes may never get the CPU if shorter jobs keep arriving. It also needs burst-time prediction in practice, so real schedulers use approximations.

10. How does Round Robin work and how does the quantum affect it?

Round Robin gives each process a fixed time quantum (typically 10–100 ms), then moves to the next ready process in a circular queue. It is preemptive and guarantees every process gets the CPU regularly, which makes it ideal for time-sharing and interactive systems.

The quantum size is the critical tuning knob. Too large, and it degrades into FCFS with poor response time. Too small, and the system spends more time context switching than executing — overhead destroys throughput. The ideal quantum is just larger than most CPU bursts (roughly the 80th percentile of burst times).

11. What is priority scheduling and how is starvation solved?

Priority scheduling runs higher-priority processes first. Preemption is optional — a higher-priority arriving process can preempt the running one or wait for it.

Starvation is its core problem: low-priority processes may never run if higher-priority ones keep arriving. The standard fix is aging — gradually increase the priority of waiting processes so that eventually every process’s priority rises enough to get the CPU. Priority scheduling also introduces priority inversion (below).

12. What is priority inversion and how is it solved?

Priority inversion happens when a high-priority process is blocked because a low-priority process holds a lock it needs, and the low-priority process can’t run because medium-priority processes keep preempting it. The high-priority process ends up waiting behind work that has lower priority than itself.

It is solved with priority inheritance: temporarily boost the priority of the low-priority lock holder to the priority of the highest waiter, so it gets the CPU, finishes its critical section, and releases the lock. Priority inheritance is used in real-time systems and in Linux mutexes.

13. What is the difference between preemptive and non-preemptive scheduling?

In non-preemptive scheduling, once a process gets the CPU it runs until it voluntarily gives it up — by terminating or blocking on I/O. FCFS and SJF are non-preemptive. The scheduler cannot interrupt a running process, so a high-priority arrival has to wait.

In preemptive scheduling, the scheduler can take the CPU away from the running process — when a higher-priority process arrives, when the time quantum expires, or when a new shorter job appears. SRTF and Round Robin are preemptive. Preemption gives better responsiveness but adds context-switch overhead and requires the scheduler to save and restore state correctly.

14. What is the difference between user-level and kernel-level threads?

User-level threads are managed by a thread library entirely at user level — the kernel doesn’t know they exist. Context switching between them requires no system call, so it is very fast. But if one thread blocks on I/O, the kernel blocks the whole process — all threads stall. They also offer no parallelism: only one user-level thread runs at a time. Green threads in old Java are an example.

Kernel-level threads are managed by the OS kernel. Each thread can block independently, and multiple threads can run in parallel across CPU cores. The cost is that creating and switching them involves system calls, making them slower. POSIX threads (pthreads) on Linux are kernel-level. The modern model maps many user threads to fewer kernel threads (N:M hybrid) for the best of both worlds.

15. What are the multithreading models?

• 1:1 (one-to-one) — each user thread maps to one kernel thread. Linux and Windows use this. Simple, full parallelism, but each thread creation is a kernel call.
• N:1 (many-to-one) — many user threads map to one kernel thread. Fast creation, but one blocking thread blocks all, and no parallelism. Obsolete.
• N:M (many-to-many) — many user threads map to many kernel threads. Most flexible — combines fast creation with true parallelism — but complex to implement.

16. What are the IPC mechanisms and which is fastest?

• Shared memory — the fastest: two processes map the same physical memory into their address spaces and read/write it directly, with no kernel involvement after setup and no copying. The trade-off is that you must add synchronization (mutex or semaphore) to prevent race conditions.
• Message passing — processes send and receive messages through a kernel-managed queue. No shared memory needed and it works across network nodes, but each message goes through the kernel (a copy).
• Pipes — a unidirectional byte stream connecting one process’s output to another’s input. Anonymous pipes work between related processes; named pipes (FIFOs) work between any processes.
• Sockets — network communication, the slowest due to the full network stack.
• Signals — fast, unidirectional notifications/interrupts.

For an interview: shared memory is fastest because there’s no copy, message passing is most general because it works across machines, and pipes are the classic answer for ls | grep.

17. What is a pipe in Linux and how is it created?

A pipe is a unidirectional communication channel. The pipe() system call returns two file descriptors — one for reading and one for writing. Data written to the write end can be read from the read end, in FIFO order.

Anonymous pipes only work between related processes (parent-child, established before the fork). Named pipes (FIFOs) are files in the filesystem, so any processes can use them. Shell pipelines like ls | grep .txt work by connecting ls’s stdout directly to grep’s stdin through a pipe.

18. Why are threads called “lightweight processes”?

Threads share the same address space — code, data, and heap — as their parent process. Creating a thread doesn’t require allocating a new virtual address space, setting up new page tables, or copying file descriptors. It’s just a new stack and register set within the existing process environment.

Context switching between threads is therefore much cheaper than between processes: no TLB flush or address-space switch is needed, just saving/loading registers and the stack pointer. The cost of creating a thread is roughly 10–100x lower than creating a process.

19. What is real-time scheduling? Explain Rate Monotonic (RM) and Earliest Deadline First (EDF).

Real-time scheduling is used where tasks must complete within deadlines. The two classic algorithms are RM and EDF.

Rate Monotonic (RM) — a static priority algorithm. Tasks with shorter periods get higher priority. Priorities are assigned once, based on period, and never change. It’s the optimal static priority scheduling for periodic tasks, but it only guarantees schedulability up to roughly 69% CPU utilization (the Liu–Layland bound) — beyond that, deadlines can be missed even if the CPU looks idle.

Earliest Deadline First (EDF) — a dynamic priority algorithm. At every scheduling decision, the task whose deadline is nearest runs next. Priorities change over time. EDF is optimal: if any schedule can meet all deadlines, EDF can — it can use up to 100% of the CPU.

The interview summary: RM is static-priority and simpler (works up to ~69% load); EDF is dynamic-priority, optimal, and can fill the CPU completely, at the cost of more scheduling overhead. Both are preemptive.

20. What are Multilevel Queue and Multilevel Feedback Queue scheduling?

Multilevel Queue (MLQ) — the ready queue is split into several queues, each with a fixed priority, e.g. system processes, interactive, batch, background. A process is permanently assigned to one queue (by type). Each queue has its own scheduling algorithm (e.g. RR for interactive, FCFS for batch). Lower queues run only when all higher queues are empty. Fixed assignment means a process can never migrate — a CPU-bound process stuck in a low queue stays there even if it becomes interactive.

Multilevel Feedback Queue (MLFQ) — the important one. Processes are allowed to move between queues. A new process enters the highest-priority queue; if it uses up its time slice without finishing, it’s demoted to a lower queue. This naturally differentiates interactive (short-burst) from CPU-bound (long-burst) processes: short jobs finish quickly in the top queue, while long jobs sink to lower queues and run in larger slices. MLFQ is the basis of many real schedulers — it gives low response time to interactive processes and high throughput to batch jobs without knowing burst times in advance.

The difference to remember: MLQ assigns each process to a fixed queue forever; MLFQ lets processes migrate between queues based on their behavior.

21. How many processes are created by n nested fork() calls?

This is a classic placement calculation. If a program calls fork() in a loop n times, each process doubles the count:

• After 1 fork: 2 processes
• After 2 forks: 4
• After 3 forks: 8
• After n forks: 2ⁿ processes, so 2ⁿ − 1 child processes are created (excluding the original parent).

for (int i = 0; i < n; i++)
    fork();
// total processes = 2^n, new processes = 2^n - 1

If the forks are sequential but not in a loop — fork(); fork(); — the same doubling logic applies, so two sequential forks give 4 processes. A common trap: a single if (fork() == 0) { fork(); } gives only 3 processes total, because only the child runs the second fork. Count carefully which processes reach each fork.

22. How do you compute turnaround time and average waiting time for a scheduling algorithm?

These are the standard numerical scheduling questions. Given arrival times and burst times, compute:

• Completion time — when each process finishes.
• Turnaround time (TAT) = completion − arrival.
• Waiting time = turnaround − burst (time spent in the ready queue, not running).

Example (FCFS): processes P1 (burst 5), P2 (burst 3), P3 (burst 8), all arriving at time 0.

Gantt:  | P1 |  P2  |      P3      |
        0    5      8             16

• P1: completion 5, TAT 5, waiting 0
• P2: completion 8, TAT 8, waiting 5
• P3: completion 16, TAT 16, waiting 8

Average TAT = (5 + 8 + 16)/3 = 9.67; average waiting = (0 + 5 + 8)/3 = 4.33.

For Round Robin, add the quantum: each process runs a slice (say 3), then cycles until done. Waiting time = (time the process spent not running before it finished). The method is the same — draw the Gantt chart, then use TAT = completion − arrival, waiting = TAT − burst. SJF minimizes average waiting time; RR trades total turnaround for lower response time.