CPU Scheduling in Operating System

What is CPU Scheduling in Operating System

When you open your laptop and launch several programs, do you ever wonder how your computer decides which task to run first? How does it juggle between a music player, a browser, a game, and background updates without crashing? The magic behind this multitasking lies in CPU Scheduling.

CPU scheduling is the system used to schedule processes that wants to use CPU time. It allows one process (say P1) to use the CPU time by possibly putting other process (say P2) on hold or in waiting queue since P2 may be waiting for an additional resource like input or locked file etc.

CPU scheduling in Operating system

What is CPU Scheduling?

CPU scheduling is the process by which the operating system decides which process or task gets to use the CPU (central processing unit) and for how long.

  • Since most systems have a single CPU and multiple tasks waiting for execution, the OS needs a fair and efficient method to schedule these tasks.
  • CPU Scheduling becomes especially important in multiprogramming environments where many processes are in memory and waiting to execute.
  • We use CPU scheduling to make efficient use of CPU to increase the CPU utility and to reduce optimize time usage.
  • If the CPU gets idle, it may select a process from the ready queue using various algorithms to intelligently select the process that needs to be executed next.

Note – This is done by short term scheduler i.e. CPU scheduler.

CPU scheduling types

Why we need CPU Scheduling?

A process needs –

  • Data/File Resources
  • I/O time
  • CPU time

While in a single process system a lot of CPU time may be wasted, since the current process may have to wait for input or locked resource etc.

This causes CPU time to be wasted. To over come this we use multi-programming systems, which supports process switch if another process in running state is waiting for any resource or I/O.

In such cases, any process from the ready queue is selected based on a pre-defined logic, this is done by short term scheduler.

CPU Scheduling Parameters

Don’t worry if you don’t understand the definitions now, you will learn more about them when we discuss different types of Scheduling algorithms in detail.

CPU scheduling parameters
  • CPU Burst Time – In simple terms, the duration for which a process gets control of the CPU is the CPU burst time, and the concept of gaining control of the CPU is the CPU burst. Similarly, an I/O burst is the concept of performing I/O operations.
  • CPU Utilization – CPU utilization can be defined as the the percentage of time CPU was handling process execution to total time

Formulae –

CPU Utilization = (Total time – Total idle time)/(Total Time)

A computer with 75% CPU utilization is better than 50%, since the CPU time was better utilized to handle process execution in 75% and lesser time was wasted in idle time.

  • Waiting Time is the total amount of time spent in the ready queue to gain the access of the CPU for execution.
  • Turn Around Time – From the time the process is submitted to the time the process is completed, is defined as Turn Around Time.
  • Throughput – In a unit time the number of processes that can be completed is called the throughput.
  • Load Time – It is defined as the average number of process that are pending in the Ready Queue and waiting for execution time.
  • Response Time – can be defined as the time interval between when the process was submitted and when the first response is given to the process.

Different types of Scheduling Algorithms

Listed below are some other algorithms:

  1. Highest Response Ratio Next (HRRN)
  2. Multilevel Queue Scheduling:
  3. Multi level Feedback Queue Scheduling

Preemptive vs Non Preemptive Scheduling

Non Preemptive Scheduling

In this type of scheduling, if a process enters the CPU and gets processing time. The process will keep on executing until it has terminated or has to forcibly go to waiting state as it needs a resource that it locked by another parallel process.

Example – SJF i.e. Shortest Job First (Non Preemptive)

Preemptive Scheduling

In this type of scheduling, if a process enters the CPU and gets processing time. It can get switched by another process that have higher priority.

Priority may be forced i.e. may be assigned to each process or time based dynamic priority as in the case of SRTF algorithm. 

Example – SRTF i.e. Shortest Remaining time First (Also known as SJF – Preemptive) 

Note – This information is given wrong on Geeks4Geeks they have mentioned SRTF non preemptive.

Note – It’s okay to not to understand the above completely as of now. We suggest going through all the different scheduling algorithms and solve first and then come back here to understand it again, then it will be easy.

FAQs

CPU Scheduling is the process used by the operating system to decide which process gets to use the CPU and for how long. It’s crucial because multiple processes often compete for CPU time, and proper scheduling ensures optimal CPU utilization, reduced waiting time, and better system responsiveness. It plays a vital role in multitasking and achieving fairness among processes.

The main types of CPU Scheduling algorithms include:

  • First-Come, First-Served (FCFS)
  • Shortest Job First (SJF)
  • Round Robin (RR)
  • Priority Scheduling
  • Multilevel Queue Scheduling
  • Multilevel Feedback Queue Scheduling
  • Preemptive Scheduling allows the operating system to interrupt a currently running process in order to start or resume another process with higher priority or shorter burst time.
  • Non-Preemptive Scheduling means once a process starts executing, it runs till completion and cannot be interrupted.

Some common problems include:

  • Starvation: A low-priority process may never get CPU time.
  • Convoy Effect: In FCFS, a long process can block shorter ones behind it.
  • High Overhead: Frequent context switching in Round Robin can degrade performance.
  • Inaccurate Burst Time Estimation: SJF depends on knowing the burst time, which is often difficult to predict accurately.