CPU Scheduling Concepts

CPU scheduling determines which process in the ready queue gets the CPU next. The goal is to maximize CPU utilization and system throughput while minimizing waiting time and response time.

Scheduling Criteria:

• CPU Utilization: Keep the CPU as busy as possible (maximize)
• Throughput: Number of processes completed per unit time (maximize)
• Turnaround Time: Total time from submission to completion (minimize)
• Waiting Time: Total time spent in the ready queue (minimize)
• Response Time: Time from submission to first response (minimize)

Preemptive vs Non-Preemptive:

• Non-Preemptive: Once a process gets the CPU, it keeps it until it terminates or blocks for I/O.
• Preemptive: The OS can forcibly take the CPU from a running process (e.g., when a higher-priority process arrives or time quantum expires).

FCFS - First Come First Served

Processes are executed in the order they arrive. Simple but can cause the convoy effect (short processes wait behind long ones).

Example: Processes P1(24ms), P2(3ms), P3(3ms) arrive at time 0.

Gantt Chart: | P1 (0-24) | P2 (24-27) | P3 (27-30) |

• Waiting times: P1=0, P2=24, P3=27 -> Average = 17ms
• Non-preemptive

SJF - Shortest Job First

The process with the shortest CPU burst time is scheduled next. Optimal for minimizing average waiting time, but requires knowing burst times in advance.

Non-Preemptive SJF Example: P1(6ms), P2(8ms), P3(7ms), P4(3ms) all arrive at time 0.

Order: P4(3) -> P1(6) -> P3(7) -> P2(8)

Gantt Chart: | P4 (0-3) | P1 (3-9) | P3 (9-16) | P2 (16-24) |

• Waiting times: P1=3, P2=16, P3=9, P4=0 -> Average = 7ms

Preemptive SJF (SRTF - Shortest Remaining Time First): If a new process arrives with a shorter remaining burst time than the current process, preempt the current process.

Round Robin (RR)

Each process gets a fixed time quantum (time slice). After the quantum expires, the process is preempted and moved to the back of the ready queue. Fair for all processes.

Example: P1(24ms), P2(3ms), P3(3ms), quantum=4ms

Gantt Chart: | P1(0-4) | P2(4-7) | P3(7-10) | P1(10-14) | P1(14-18) | P1(18-22) | P1(22-26) | P1(26-30) |

• Waiting times: P1=6, P2=4, P3=7 -> Average = 5.67ms
• Preemptive
• Quantum too small -> too many context switches; too large -> degenerates to FCFS

Priority Scheduling

Each process is assigned a priority. The process with the highest priority (lowest number) is scheduled first. Can be preemptive or non-preemptive.

Problem: Starvation - low-priority processes may never execute if high-priority processes keep arriving.

Solution: Aging - gradually increase the priority of waiting processes over time.

Multilevel Queue Scheduling

The ready queue is divided into multiple queues based on process type (e.g., foreground/interactive vs background/batch). Each queue has its own scheduling algorithm. Processes cannot move between queues.

Multilevel Feedback Queue: Processes can move between queues based on their behavior. CPU-bound processes move to lower-priority queues; I/O-bound processes stay in higher-priority queues. Most flexible and complex algorithm.

Scheduling Algorithm Comparison

---