Operating Systems: Processes, Scheduling, Concurrency

At 09:59:55 on a weekday morning, the IRCTC Tatkal booking system is nearly idle. Five seconds later, hundreds of thousands of requests land on it in the same instant, all trying to reserve a shrinking pool of berths on the same trains. No server on earth has hundreds of thousands of physical processors, so every single one of those requests is a process (or a thread inside one) that has to be admitted, parked, run for a slice of time, paused, and resumed — over and over, thousands of times a second, on a machine with perhaps a few dozen actual cores. What looks to a user like "the system is slow" is, underneath, a precise engineering problem: which of these competing units of work gets the CPU right now, for how long, and what happens to the ones that don't. That is the entire subject of this chapter — processes, the states they move through, the algorithms that pick a winner, and the new class of bugs that appears the moment two of them touch the same piece of data at the same time.

What Is a Process? (It Is Not a Program)

A program is a static thing — the compiled Tatkal booking binary sitting on a disk, inert, doing nothing. A process is that program in execution: a program counter pointing at the next instruction, a stack of function calls in progress, a heap of allocated memory, a set of CPU register values, and a chunk of address space the operating system has carved out and promised belongs to this execution alone. Run the same booking-server binary twice and you get two processes — same code, but two independent program counters, two independent stacks, two independent memory regions. The OS tracks each one using a data structure called the Process Control Block (PCB), which typically holds:

• a unique process ID (PID)
• the current process state (defined below)
• the saved program counter and CPU register values (only meaningful while the process is not actually running — while it runs, these live in the real hardware registers)
• CPU-scheduling information: priority, how much CPU time it has already consumed
• memory-management information: base/limit registers or page-table pointers
• accounting and I/O status information: open files, pending I/O requests

The PCB matters because it is the entire mechanism that lets one CPU core pretend to run many processes "simultaneously." Every time the OS takes the core away from one process and hands it to another, it is really just swapping out one PCB's worth of saved state for another's.

The Five States a Process Moves Through

A process is never just "running" or "not running." Operating systems track a small state machine with five states, and the transitions between them are exactly what a scheduler manipulates:

• New — the process has been created (the OS has allocated a PID and a PCB) but has not yet been admitted to the pool of processes competing for the CPU.
• Ready — the process is loaded into memory and able to run, but is waiting in a queue for the CPU to become available.
• Running — the process's instructions are actually executing on a CPU core right now. On a single core, exactly one process is ever in this state.
• Waiting (Blocked) — the process cannot make progress until some event completes — most commonly disk or network I/O (a Tatkal booking request that has to wait for a database write to confirm a seat is blocked, not ready).
• Terminated — the process has finished (or been killed) and the OS is reclaiming its PCB and memory.

The transition rules matter as much as the states. New→Ready happens once the OS admits the process. Ready→Running happens when the scheduler dispatches it — hands it a core. Running→Ready is an involuntary demotion: the process still wants to run, but the OS takes the CPU away, either because its time slice ran out or a higher-priority process needs to run. Running→Waiting is voluntary in a different sense — the process itself issued a blocking call (read a file, waited on a network reply) and cannot proceed regardless of CPU availability. Waiting→Ready happens when that event completes: notice it goes back to Ready, not straight to Running — the process still has to win its turn from the scheduler like everyone else.

Context Switching: The Price of Multitasking

Every Ready→Running and Running→Ready transition on a real core involves a context switch: the OS saves the running process's registers and program counter into its PCB, loads the next process's saved registers and program counter from its PCB, and possibly swaps the memory-management state (page tables) if the two processes don't share an address space. The direct cost of this — the actual save/restore of a few dozen registers — is small, typically a few microseconds on modern hardware. The indirect cost is usually larger: the CPU's caches and the translation-lookaside buffer (TLB) were "warm" with the outgoing process's data and instructions, and the incoming process starts with cold caches, so its first several memory accesses are slower until the cache refills. This is precisely why an OS scheduler cannot switch processes for free arbitrarily often — do it too aggressively and the machine spends more time swapping contexts than doing useful work, a pathology called thrashing when it happens with memory paging, and simply "scheduling overhead" when it happens with the CPU scheduler.

CPU Scheduling: Choosing Who Runs Next

When more than one process is Ready, the scheduler needs a policy for choosing which one gets the core. Three classic policies illustrate the trade-offs. Consider four Tatkal-processing tasks arriving in a queue, described by their arrival time and CPU burst (time needed if run start-to-finish without interruption):

First-Come, First-Served (FCFS) runs processes strictly in arrival order, uninterrupted:

P1(0-5)  P2(5-8)  P3(8-16)  P4(16-22)

Completion times are 5, 8, 16, 22. Turnaround time (completion minus arrival) is 5, 7, 14, 19. Waiting time (turnaround minus burst — the time spent Ready but not Running) is 0, 4, 6, 13. Average waiting time = (0+4+6+13)/4 = 5.75.

FCFS's flaw is visible immediately: P2 needs only 3 units of CPU but waits 4 units for the privilege, because it happened to queue up behind the longer P1. Worse, imagine P3 (burst 8) had arrived first — every short job behind it would be stuck waiting nearly 8 units regardless of how brief its own work is. This is the convoy effect.

Shortest Job First, non-preemptive (SJF) instead picks, from whichever processes have already arrived, the one with the smallest remaining burst, and lets it run to completion before choosing again:

P1(0-5)  P2(5-8)  P4(8-14)  P3(14-22)

At t=5 both P2(3) and P3(8) have arrived (P4 hasn't yet); SJF picks P2. At t=8, P3(8) and P4(6) are both available; SJF picks the shorter P4. Completion times: P1=5, P2=8, P4=14, P3=22. Turnaround: 5, 7, 11, 20. Waiting: 0, 4, 5, 12. Average waiting = (0+4+5+12)/4 = 5.25 — better than FCFS. This is not a coincidence: SJF is provably optimal for minimizing average waiting time among non-preemptive algorithms, because any interleaving that runs a longer job before a shorter one that is also available can be improved by swapping them (an exchange argument) — every process still behind the swap waits exactly as long or less.

Round Robin (RR) with time quantum q=2 gives every Ready process a maximum of 2 units of CPU before forcing it to the back of the queue (newly arrived processes join the queue before the just-preempted one re-joins it). Tracing it carefully:

P1(0-2) P2(2-4) P3(4-6) P1(6-8) P4(8-10) P2(10-11)
P3(11-13) P1(13-14) P4(14-16) P3(16-18) P4(18-20) P3(20-22)

P2 finishes at t=11 (it only had 1 unit left on its second turn), P1 finishes at t=14, P4 at t=20, P3 at t=22. Turnaround: P1=14, P2=10, P3=20, P4=17. Waiting: P1=9, P2=7, P3=12, P4=11. Average waiting = (9+7+12+11)/4 = 9.75 — noticeably worse than both FCFS and SJF.

Round Robin looks like the loser here, and by the average-waiting-time metric, it is. But check a different metric: response time, the time from arrival until a process first touches the CPU. Under FCFS, response time equals waiting time for every process except the first, since each only runs once — average response time is the same 5.75. Under RR, P1 first runs at t=0, P2 at t=2 (waited 1), P3 at t=4 (waited 2), P4 at t=8 (waited 5) — average response time = (0+1+2+5)/4 = 2. RR sacrifices average completion-related metrics but gives every process a fast first turn, which is exactly why interactive, time-shared systems (and, not coincidentally, request-handling systems like a booking server that must acknowledge every request promptly even under load) favor round-robin-family schedulers over FCFS or pure SJF: a user submitting a Tatkal request cares far more about getting some response quickly than about a scheduler-optimal total completion time. As a sanity check across all three schedules: total CPU burst is 5+3+8+6=22, and since no schedule ever leaves the CPU idle (P1 is ready at t=0 and there's always a Ready process after that), all three correctly finish their last process at exactly t=22 — a useful invariant to verify any Gantt-chart trace against.

Threads and Concurrency: Sharing an Address Space

A process can contain more than one thread — an independent sequence of execution with its own program counter and stack, but sharing the process's heap, global variables, and open files with every other thread in the same process. This distinction gives four related terms their precise meanings, often blurred in casual speech: multiprogramming is simply keeping several processes in memory so the CPU has something to run whenever one blocks on I/O; multitasking is multiprogramming made interactive, with the OS preempting processes on a short quantum so switching feels instantaneous to a human; multithreading is one process running several threads that share memory (a booking server might run one thread per incoming connection, all reading and writing the same in-memory seat-availability table); multiprocessing is having multiple physical cores actually execute instructions at the same literal instant, which is the only one of the four that is true parallelism rather than time-sliced concurrency.

Threads are attractive because creating one and switching between two threads of the same process is cheaper than doing so for two separate processes — there is no address-space switch, so the TLB and much of the cache stay warm. But sharing memory is a double-edged design: it is also precisely what makes concurrent programming dangerous.

Race Conditions: When Interleaving Breaks Correctness

Suppose the Tatkal server keeps one shared integer, available_seats, currently 1 — the last berth on a train. Two threads, T1 and T2, are each handling a different passenger's booking request and both execute this logic:

if (available_seats > 0) {          // step A: check
    available_seats = available_seats - 1;   // step B: decrement
    confirmBooking();                // step C: confirm
} else {
    rejectBooking();
}

This looks like one atomic action but is really at least three separate CPU-level steps: read available_seats into a register, compare, and (if positive) write back the decremented value. On a single core, the OS can — and routinely does — interrupt a thread between any two instructions to give another thread a turn. Trace one unlucky interleaving:

1. T1 executes step A: reads available_seats into its register — value 1. The check passes. Timer interrupt fires; the OS context-switches to T2 before T1 executes step B.
2. T2 executes step A: reads available_seats — still 1, because T1 never wrote anything back yet. The check passes.
3. T2 executes step B: writes available_seats = 1 - 1 = 0.
4. T2 executes step C: confirmBooking() — passenger 2 is confirmed. Context switch back to T1.
5. T1 resumes exactly where it left off — it already has its stale register value of 1 from step A, so it does not re-read the now-updated shared variable. T1 executes step B: writes available_seats = 1 - 1 = 0 (overwriting T2's write with the same value, coincidentally).
6. T1 executes step C: confirmBooking() — passenger 1 is also confirmed.

Two passengers now hold a confirmed ticket for one seat, and the shared counter reads a plausible-looking 0 — nothing in the final state screams "bug." This is a race condition: a correctness failure that depends on the precise timing of an interleaving, and is often called a lost update, because T2's decrement was logically overwritten by T1 acting on stale data. Note this bug required no second CPU core and no true parallelism at all — a single-core machine with preemptive multitasking is entirely sufficient, because the timer interrupt can land between step A and step B of any thread at any time.

Fixing It: Mutual Exclusion

The fix is to mark steps A and B as a critical section — a sequence that must execute as if atomic with respect to every other thread touching the same shared data — and protect it with a lock (a binary semaphore, commonly called a mutex):

acquire(lock);
if (available_seats > 0) {
    available_seats = available_seats - 1;
    confirmBooking();
} else {
    rejectBooking();
}
release(lock);

acquire(lock) blocks any thread from proceeding past that point while another thread already holds the lock; the OS or runtime guarantees that acquire-and-block is itself implemented atomically (typically using a hardware instruction like compare-and-swap, which the CPU guarantees cannot be interrupted mid-operation). Now if T2 tries to acquire the lock while T1 holds it, T2 is moved to the Waiting state until T1 calls release(lock) — by which point available_seats has already dropped to 0, so T2's check correctly fails and the passenger is rejected. Note confirmBooking() was included inside the critical section here mainly for simplicity of the example; the strict minimal critical section is only steps A and B, since those are the only lines touching the shared variable — confirmBooking() operating purely on thread-local data would not need protection, though in this example it is left inside the lock, which is safe (if slightly more conservative) as well.

The Misconception: "Race Conditions Only Happen With Multiple CPUs"

A student who has just learned that "true parallelism needs multiple cores" often assumes, reasonably but wrongly, that race conditions are exclusively a multi-core phenomenon — that a program running on a single-core, single-threaded-at-a-time machine is automatically safe from them. The Tatkal trace above is the direct counterexample: both threads ran on the same single core, one at a time, never simultaneously in the literal sense, and the bug still occurred. The actual requirement for a race condition is not simultaneous execution — it is an unprotected shared resource accessed by a non-atomic sequence of operations, combined with preemption (or any other source of interleaving) at an inconvenient point in that sequence. A single core with a preemptive scheduler provides exactly that interleaving, because the OS can suspend a thread mid-sequence to run another thread, exactly as multiprogramming requires it to. Multiple cores make races easier to trigger (interleavings can now happen at literally any instruction boundary, more frequently, with less predictable timing) and make an additional class of subtle bugs possible (memory-visibility races, where one core's write hasn't yet become visible to another core's cache) — but they are not a precondition for the bug to exist at all.

Active Recall

Attempt each question before reading its answer.

1. A single compiled binary, tatkal_server, is launched three times on the same machine. Is this one process or three? Justify using the definition of a process.
2. Processes P1(arrival 0, burst 4), P2(arrival 1, burst 2), P3(arrival 2, burst 6) run under FCFS. Compute the average waiting time.
3. Why can SJF cause starvation, and under what arrival pattern would it happen?
4. In the process state diagram, what is the precise difference between what triggers Running→Ready and what triggers Running→Waiting?
5. In the seat-booking pseudocode, which specific line(s) must be inside the critical section, and why is that the minimal set?
6. True or false, with justification: "Setting the Round Robin quantum to 2 ms guarantees every process finishes within 2 ms of arriving."

Worked Answers

1. Three processes. A process is a program in execution, with its own address space, program counter, stack, and PCB. Launching the same binary three times produces three independent executions — three PIDs, three sets of registers and memory — even though all three happen to be running identical code. The program (the file on disk) is one; the processes (the running instances) are three.

2. FCFS runs in arrival order: P1(0–4), P2(4–6), P3(6–12). Completion times: 4, 6, 12. Turnaround: 4−0=4, 6−1=5, 12−2=10. Waiting: 4−4=0, 5−2=3, 10−6=4. Average waiting = (0+3+4)/3 = 7/3 ≈ 2.33.

3. SJF always prefers whatever Ready process currently has the smallest burst, with no regard to how long a process has already been waiting. If short jobs keep arriving continuously — a steady stream of quick Tatkal availability-checks, say — a long job (a heavy fare-calculation batch) sitting in the Ready queue can be repeatedly passed over indefinitely, because there is always something shorter available. This is starvation: the long job is never technically denied the CPU, but it can wait arbitrarily long in principle. Real schedulers mitigate this with aging — gradually raising a waiting process's effective priority the longer it waits.

4. Running→Ready is involuntary preemption: the process still wants and is able to use the CPU, but the OS takes it away — because its time quantum expired or a higher-priority process became Ready. Running→Waiting is self-initiated blocking: the process itself issued a call (disk read, network receive) that cannot complete instantly, so it cannot use the CPU productively even if offered it, and moves itself out of contention until that event completes.

5. Only the check-and-decrement, steps A and B (if (available_seats > 0) and available_seats = available_seats - 1), must be inside the critical section. Those are the only two lines that read then write the shared variable available_seats as a non-atomic sequence — any interleaving between them is what causes the lost-update race. confirmBooking() and rejectBooking() don't need to be inside the lock purely for correctness of the shared counter, since they don't touch available_seats; keeping the lock as narrow as possible (protecting only A and B) reduces how long other threads are blocked, which is good practice, though including a little extra inside the lock is not itself a correctness bug.

6. False. The quantum only bounds how long a process runs per turn once it is Running — it says nothing about how long a process waits in the Ready queue before its turn comes. With four processes ahead of it, each getting a full 2 ms turn, a process could easily wait 8 ms or more before even starting, let alone finishing. The RR trace worked through earlier makes this concrete: with quantum 2, P3 (burst 8) does not complete until t=22, eleven times longer than the quantum itself.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind operating systems: processes, scheduling, concurrency, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.