Process States & Context Switch

A process has a life cycle

A process is a program in execution. From the moment it is created until it disappears, it is always in exactly one state:

State	Meaning
New	The OS is creating the process (allocating its PCB and memory).
Ready	It has everything it needs except the CPU. It sits in the ready queue.
Running	Its instructions are executing on a CPU right now. With one CPU, only one process is Running.
Waiting (blocked)	It cannot continue until an event happens, usually I/O completion.
Terminated	It has finished. The OS frees its resources.

A process moves between states along six arrows. Each has a cause:

Transition	Cause
New → Ready	Admit: the OS accepts the process.
Ready → Running	Dispatch: the scheduler picks it and the dispatcher gives it the CPU.
Running → Ready	Timeout (preemption): its time quantum ran out, or a higher-priority process arrived.
Running → Waiting	I/O or event wait: it asks for something that will take a while.
Waiting → Ready	I/O done: the event it waited for has happened.
Running → Terminated	Exit.

There is no Waiting → Running arrow and no Ready → Waiting arrow. A process can only block itself, and only while it is running. And after waiting it always has to queue again.

Reading the 3D lifecycle model

The model runs three processes under round-robin scheduling with a selectable quantum. Each process has CPU bursts and I/O bursts: P1 needs CPU 4, I/O 3, CPU 2; P2 needs CPU 5; P3 needs CPU 2, I/O 2, CPU 3. The tag above each sphere shows its current burst.

With q = 3 the trace starts like this:

Time	Event
0	P1, P2, P3 admitted; P1 dispatched
3	P1 times out (still has 1 CPU unit left); P2 dispatched
6	P2 times out; P3 dispatched
8	P3 finishes its CPU burst and starts I/O (Waiting); P1 dispatched
9	P1 finishes its burst and starts I/O; P2 dispatched
10	P3’s I/O finishes, so it is Ready again
11	P2 exits; P3 dispatched
12	P1’s I/O finishes
14	P3 exits; P1 dispatched
16	P1 exits

Notice two things. First, P1 and P3 spend time Waiting while P2 and the others use the CPU: I/O overlaps with computation, which is the whole point of multiprogramming. Second, the number of dispatches (7 here) depends on the quantum: q = 2 gives 9 and q = 4 gives 6.

Tie-breaking

If a process’s quantum ends in the same time unit that another process’s I/O finishes, books disagree about who joins the ready queue first. This model puts the I/O completion first (like a new arrival) and the preempted process after it. A different convention gives a slightly different trace, so in an exam always use the rule your question states.

The process control block (PCB)

To manage a process the OS keeps a record in kernel memory, the PCB (called the task struct in Linux). It holds:

• the process state and process ID,
• the program counter and all CPU registers (including the stack pointer),
• scheduling information (priority, queue pointers),
• memory-management information (page table or segment table base),
• accounting and I/O status (open files, CPU time used).

The ready queue and the waiting queues are just linked lists of PCBs.

What is a context switch?

The CPU can only hold one process’s registers at a time. To switch from process A to process B, the kernel performs a context switch:

1. An interrupt or system call moves the CPU into kernel mode (a timer interrupt for a timeout, a system call for I/O).
2. The kernel saves A’s registers (PC, SP, general registers) into A’s PCB and sets A’s state to Ready or Waiting.
3. The scheduler picks the next process, B.
4. The kernel loads B’s saved registers from B’s PCB into the CPU and sets B’s state to Running. The memory-management registers change too, so B sees its own address space.
5. Return from interrupt: B continues exactly where it stopped, with no idea it was ever paused.

Switch the model to Context switch and watch the PCBs: P1’s PC is saved as 0x1044 and loaded back unchanged later.

Why a context switch is pure overhead

While the kernel does steps 2 to 4, no user program makes progress. The cost has two parts:

• Direct cost: copying registers and running the scheduler. Typically a few microseconds.
• Indirect cost: the new process finds the CPU caches cold (full of the old process’s data) and the TLB flushed or full of the wrong translations, so it runs slower for a while. See paging and the TLB.

That is why the quantum is a trade-off. A quantum of 1 µs would spend most of the time switching. A quantum of 10 s would make interactive programs feel frozen. Typical values are 10 to 100 ms.

Related terms

Term	Meaning
Dispatcher	The module that does steps 2 to 5. The scheduler only decides who; the dispatcher does the switch.
Dispatch latency	The time the dispatcher takes to stop one process and start another.
Mode switch	User mode ↔ kernel mode without changing the running process (a system call that returns to the same process). Cheaper than a context switch.
Thread switch	Switching between threads of the same process. No address-space change, so it is cheaper than a process switch.
Voluntary / involuntary	A switch because the process blocked or yielded (voluntary) versus because of a timer or higher priority (involuntary).

Real systems add more states. A suspended (swapped-out) process has had its memory moved to disk by the medium-term scheduler. That gives a Suspended Ready and a Suspended Waiting state. The five-state model above is the one asked most often.

Code

from collections import deque

def round_robin(procs, quantum):
    """procs maps a name to its bursts, e.g. [('cpu', 4), ('io', 3), ('cpu', 2)].
    Returns a log of (time, transition, process)."""
    bursts = {p: [list(b) for b in bs] for p, bs in procs.items()}
    ready, waiting, log = deque(procs), [], [(0, 'admit', p) for p in procs]
    t, running, used = 0, None, 0
    while running or ready or waiting:
        if running is None and ready:
            running, used = ready.popleft(), 0
            log.append((t, 'dispatch', running))
        if running is None:              # idle: jump to the next I/O completion
            step = min(bursts[p][0][1] for p in waiting)
            for p in waiting:
                bursts[p][0][1] -= step
            t += step
        else:                            # run one time unit
            bursts[running][0][1] -= 1
            used += 1
            t += 1
            for p in waiting:
                bursts[p][0][1] -= 1
        for p in [p for p in waiting if bursts[p][0][1] == 0]:
            waiting.remove(p)
            bursts[p].pop(0)
            ready.append(p)
            log.append((t, 'io-done', p))
        if running and bursts[running][0][1] == 0:
            bursts[running].pop(0)
            if bursts[running]:
                waiting.append(running)
                log.append((t, 'io-wait', running))
            else:
                log.append((t, 'exit', running))
            running = None
        elif running and used == quantum:
            ready.append(running)
            log.append((t, 'timeout', running))
            running = None
    return log

procs = {
    'P1': [('cpu', 4), ('io', 3), ('cpu', 2)],
    'P2': [('cpu', 5)],
    'P3': [('cpu', 2), ('io', 2), ('cpu', 3)],
}
for q in (2, 3, 4):
    log = round_robin(procs, q)
    switches = sum(e == 'dispatch' for _, e, _ in log)
    finish = {p: t for t, e, p in log if e == 'exit'}
    print(q, switches, finish)
# 2 9 {'P2': 13, 'P1': 15, 'P3': 16}
# 3 7 {'P2': 11, 'P3': 14, 'P1': 16}
# 4 6 {'P1': 12, 'P2': 13, 'P3': 16}
print(round_robin(procs, 3)[3:9])
# [(0, 'dispatch', 'P1'), (3, 'timeout', 'P1'), (3, 'dispatch', 'P2'),
#  (6, 'timeout', 'P2'), (6, 'dispatch', 'P3'), (8, 'io-wait', 'P3')]

Common mistakes

• Drawing a Waiting → Running arrow. After I/O the process goes to Ready and must be scheduled again.
• Mixing up Ready and Waiting. A Ready process could run if it had the CPU. A Waiting process could not run even if it had the CPU.
• Thinking only one process is “in memory”. Many processes are in memory and Ready or Waiting. Only one per CPU is Running.
• Calling a system call a context switch. A system call that returns to the same process is only a mode switch. A context switch changes which process owns the CPU.
• Counting every dispatch as a context switch. If the only ready process times out and is dispatched again at once, no other process’s registers are loaded, so exam answers usually do not count it. In this demo that never happens, so each dispatch is one switch.