The Scheduler

1. Non-Preemptive

Definition: Once a process enters the CPU, it cannot be interrupted. It holds the CPU until it finishes its task or voluntarily yields.

• FCFS (First Come First Serve): Simple FIFO queue. Causes the Convoy Effect (tiny processes stuck behind massive ones).
• SJF (Shortest Job First): Scans queue and executes the shortest job. Minimizes average wait time, but large jobs can starve.

2. Preemptive Algorithms

Definition: The OS acts as a strict manager. It can forcefully interrupt a running process and swap it out for another based on priority or a time limit.

• SRTF (Shortest Remaining Time): If a new, shorter process arrives while a longer one is running, the OS pauses the current one and swaps!
• Round Robin (RR): Every process gets a strict "Time Quantum". If it doesn't finish, it's kicked out. Fair, but high context-switch overhead.

3. Real-World (Linux CFS)

• Completely Fair Scheduler: Abandons strict queues. It tracks vruntime. The CPU prioritizes whichever process has the lowest vruntime to balance the load.

4. Core Formulas

• Arrival Time (AT): Time entered queue.
• Burst Time (BT): Total CPU time needed.
• Turnaround Time: Total time in system.
  TAT = Completion Time - AT
• Waiting Time: Time spent stuck in queue.
  WT = TAT - BT
• Response Time: Time until first CPU load.
  RT = First Run Time - AT