Structure of CPU scheduling algorithm and each algorithm

CPU Scheduler

The CPU scheduler assigns CPU time to threads (units of work) from processes according to a scheduling algorithm.

These algorithms aim to:

• Maximize CPU utilization
• Maximize the amount of work done in a given time
• Minimize the number of processes in the ready queue
• Minimize response time

 

---

Non-Preemptive Scheduling

In non-preemptive scheduling, a process voluntarily releases the CPU;

the OS does not forcibly stop it.

This results in less overhead from context switching.

• FCFS (First Come, First Served)
  • Processes are handled in the order they arrive.
  • Drawback: long jobs can cause others to wait too long (convoy effect).
• SJF (Shortest Job First)
  • The process with the shortest estimated execution time runs first.
  • Achieves the shortest average waiting time, but long jobs may starve.
  • Actual execution time is unknown, so estimates are based on past data.
• Priority Scheduling
  • Assigns priorities to processes.
  • To prevent starvation of low-priority (long) jobs, aging is used — increasing a process's priority the longer it waits.

---

Preemptive Scheduling

Preemptive scheduling (used by modern OSs) forcibly interrupts the running process

and assigns the CPU to another process according to the algorithm.

• Round Robin (RR)
  • Each process gets a fixed time slice.
  • If it doesn’t finish within its time slice, it goes to the back of the ready queue.
• SRF (Shortest Remaining Time First)
  • A preemptive version of SJF.
  • If a process with a shorter remaining time arrives, it interrupts the current process and runs first.
• Multilevel Queue
  • Multiple ready queues, each with its own scheduling algorithm (e.g., RR, FCFS).
  • Processes are assigned to queues based on priority.
  • Processes do not move between queues — less flexible but less overhead.