CPU Scheduling Algorithms to Know for Operating Systems

CPU scheduling algorithms manage how processes get CPU time in operating systems. They ensure efficiency and fairness, impacting performance. Different methods like FCFS, SJF, and Round Robin each have unique strengths and weaknesses, shaping user experience and system responsiveness.

1. First-Come, First-Served (FCFS)

   • Processes are executed in the order they arrive in the ready queue.
   • Simple to implement and understand, resembling a queue in real life.
   • Can lead to the "convoy effect," where short processes wait for long ones to complete, increasing average wait time.

2. Shortest Job First (SJF)

   • Selects the process with the smallest execution time next.
   • Minimizes average waiting time and is optimal for minimizing total turnaround time.
   • Can lead to starvation for longer processes if shorter processes keep arriving.

3. Priority Scheduling

   • Each process is assigned a priority, and the CPU is allocated to the highest priority process.
   • Can be preemptive or non-preemptive, affecting how processes are managed.
   • Risk of starvation for low-priority processes if high-priority processes continue to arrive.

4. Round Robin (RR)

   • Each process is assigned a fixed time slice (quantum) and cycles through the ready queue.
   • Fairly distributes CPU time among processes, making it suitable for time-sharing systems.
   • Performance heavily depends on the size of the time quantum; too small can lead to high overhead, too large can behave like FCFS.

5. Multilevel Queue Scheduling

   • Divides the ready queue into several separate queues, each with its own scheduling algorithm.
   • Different queues can be prioritized based on process type (e.g., foreground vs. background).
   • Complexity increases as the system must manage multiple queues and their interactions.

6. Multilevel Feedback Queue Scheduling

   • Similar to multilevel queue scheduling but allows processes to move between queues based on their behavior and requirements.
   • Adapts to the needs of processes, promoting responsiveness for interactive tasks.
   • More complex to implement due to the need for dynamic adjustments and feedback mechanisms.

7. Shortest Remaining Time First (SRTF)

   • A preemptive version of SJF where the process with the shortest remaining time is executed next.
   • Reduces average waiting time and turnaround time significantly.
   • Can lead to starvation for longer processes, similar to SJF.

8. Longest Remaining Time First (LRTF)

   • A less common approach that prioritizes processes with the longest remaining time.
   • Can be useful in specific scenarios but generally leads to increased waiting times for shorter processes.
   • May result in starvation for shorter processes, similar to SJF and SRTF.

9. Highest Response Ratio Next (HRRN)

   • Calculates a response ratio for each process based on waiting time and service time, selecting the highest ratio next.
   • Balances the benefits of SJF and priority scheduling, reducing starvation risk.
   • More complex to calculate but can lead to better overall system performance.

10. Completely Fair Scheduler (CFS)

    • Aims to provide fair CPU time to all processes, using a red-black tree to manage scheduling.
    • Each process receives a proportion of CPU time based on its weight, ensuring fairness.
    • Designed for modern multi-core systems, optimizing for both throughput and responsiveness.