CPU Scheduling in Operating System (OS)

September 5, 2019

What is CPU Scheduling in Operating System

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.

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.

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

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 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:

Highest Response Ratio Next (HRRN)
Multilevel Queue Scheduling:
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.