Context switching, 5-state model, MLFQ

Context switching

Context switching is the act of the CPU switching from one process (or thread) to another. The OS saves the context (program counter, CPU registers, stack pointer, memory-management information) of the current process in its PCB and loads the saved context of the next process from its PCB. It is pure overhead (no useful work is done during the switch) and its time depends on hardware speed, number of registers and memory-management support. It occurs on timer interrupts, I/O requests, and higher-priority arrivals.

Five-state model of a process

 +-----+ admit +-------+ dispatch +---------+ exit +------+
 | New |------>| Ready |--------->| Running |----->| Exit |
 +-----+       +-------+<---------+---------+      +------+
                  ^      time-out      |
                  |                    | wait for event
                  |     +---------+    |
                  +-----| Blocked |<---+
                 event  +---------+

• New: process is being created (PCB is built).
• Ready: loaded in memory and waiting for the CPU.
• Running: instructions are being executed on the CPU.
• Blocked (waiting): waiting for an event such as I/O completion.
• Terminated (exit): finished execution; resources are released.

Transitions: New→Ready (admit), Ready→Running (dispatch), Running→Ready (time-out/preemption), Running→Blocked (waits for event), Blocked→Ready (event occurs), Running→Terminated (exit).

Multilevel feedback queue scheduling

Rules assumed:

• Q1 (quantum 5 ms) has highest priority, Q2 (quantum 10 ms) next, Q3 is FCFS.
• A new process enters Q1. If it does not finish in its quantum, it moves down one queue.
• A lower queue runs only when all higher queues are empty; a new arrival in a higher queue preempts the running process, which goes to the tail of its own queue.

Trace:

• 0-5: P1 in Q1 (20 left) → moves to Q2.
• 5-12: P1 in Q2 for 7 ms (13 left); at 12 P2 arrives in Q1 and preempts P1.
• 12-17: P2 in Q1 for 5 ms (13 left) → moves to Q2. Q2 order: P1, P2.
• 17-25: P1 in Q2 for 8 ms (5 left); P3 arrives at 25 and preempts.
• 25-29: P3 (4 ms) finishes in Q1.
• 29-32: P2 runs in Q2 for 3 ms (10 left); P4 arrives at 32 and preempts.
• 32-37: P4 in Q1 for 5 ms (5 left) → Q2. Q2 order: P1, P2, P4.
• 37-42: P1 finishes (5 ms). 42-52: P2 finishes (10 ms). 52-57: P4 finishes (5 ms).

Gantt chart

| P1 | P2 | P1 | P3 | P2 | P4 | P1 | P2 | P4 |
0    12   17   25   29   32   37   42   52   57

Average waiting time = 54 / 4 = 13.5 ms

Average turnaround time = 111 / 4 = 27.75 ms

Answer: AWT = 13.5 ms, ATAT = 27.75 ms.