CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 3 of 8 · 3 min read

Processes and scheduling

Think of a kitchen: a recipe is a program, a cook working from it is a process, and several cooks sharing one counter and one pot are threads. The analogy stops in one place: cooks can talk to each other freely, and threads of one process share memory with no checks at all, which is the cause of races.

In plain words: Model answers to five classic questions:

  1. Process or thread? A process is a running program with its own address space and resources. A thread is a flow of execution inside a process that shares the address space, open files and heap with the other threads, and has its own stack and registers. Threads switch faster and share data directly, and a bug in one can corrupt all (Levels 1 and 2).
  2. What happens on fork? The kernel makes a copy of the process: a new process ID, a copy of the page tables with pages shared copy-on-write, and the same open files. The child returns 0 and the parent returns the child's ID (Level 1).
  3. What happens on a system call? The program runs a special instruction, the processor switches to kernel mode and jumps to a fixed entry point, the kernel checks the arguments and does the work, then returns to user mode. A trace shows them (page 3 measured 34 calls for a program that prints one line) and a call costs about 100 ns in the best case (page 3).
  4. What is a zombie? A process that has ended but whose parent has not yet read its exit status with wait. It holds only its process-table entry (Level 1).
  5. FCFS, SJF or round robin? FCFS is simple and long jobs delay short ones (the convoy effect). Shortest-job-first gives the lowest average waiting time but needs the burst lengths and may starve long jobs. Round robin gives each process a time slice and so a good response time, at the cost of more switches (Level 3).

A worked example. Three processes arrive at time 0 with bursts of 10, 5 and 8 ms. Compare FCFS with round robin of quantum 4 ms.

Policy Finish times (P1, P2, P3) Average turnaround Average waiting Average first response
FCFS 10, 15, 23 16.0 ms 8.33 ms 8.33 ms
Round robin, q = 4 23, 17, 21 20.33 ms 12.67 ms 4.0 ms

The round-robin timeline is P1 0-4, P2 4-8, P3 8-12, P1 12-16, P2 16-17, P3 17-21, P1 21-23. Turnaround is the finish time (all arrive at 0). Waiting is turnaround minus burst: 13, 12 and 13 ms. Round robin is worse on turnaround and waiting (20.33 against 16.0) and better on response: the first run begins at 0, 4 and 8 ms, an average of 4.0 ms against 8.33 ms for FCFS.

The key lines. There is no best policy. The right answer names the metric: throughput and waiting favour short-job-first, response time favours round robin.

Turnaround time

The turnaround time of a process is the time from its arrival to its completion. The waiting time is the turnaround time minus the time it spent running, and the response time is the time from arrival to its first run.

Example: P1 arrives at 0 and finishes at 23 in the round-robin case, so its turnaround is 23 ms.

Check yourself: 1. What do threads of one process share, and what do they not? 2. Why can round robin have a worse average turnaround than FCFS? 3. What does a zombie hold?