CPU Scheduling in OS: Concepts, Performance Criteria & Types of Schedulers
A computer may have many processes ready to run, but the CPU cannot execute every ready process at exactly the same moment. The operating system therefore needs a way to decide which process should get the CPU next. This decision-making process is called CPU Scheduling in OS.
CPU scheduling looks difficult because students meet many terms together: ready queue, CPU burst, I/O burst, preemptive scheduling, non-preemptive scheduling, dispatcher, turnaround time, waiting time, response time, long-term scheduler, short-term scheduler and medium-term scheduler. In this chapter, we will connect all of them step by step instead of memorising separate definitions.
Many processes are ready, but the scheduler must decide who runs next.
What Is CPU Scheduling in Operating System?
CPU Scheduling in Operating System is the process of selecting one process from the ready queue and allocating the CPU to that process.
The need for CPU scheduling appears because several processes may be ready for execution at the same time. The operating system needs a policy that tells it which process should run first, which process should wait and when the CPU should move to another process.
CPU scheduling is the method used by the operating system to decide which ready process gets the CPU next.
Why Is CPU Scheduling Needed?
If CPU scheduling did not exist, the operating system would not have a proper method for choosing between ready processes.
CPU Scheduling and Multiprogramming
CPU scheduling is closely connected with multiprogramming.
A process does not use the CPU continuously from start to finish. It may use the CPU, then request input or output, then wait, and later use the CPU again.
When one process waits for I/O, the operating system can give the CPU to another ready process instead of keeping the CPU idle.
CPU Burst and I/O Burst Cycle
To understand CPU Scheduling in OS properly, you first need to understand the CPU-I/O burst cycle.
During its life, a process often moves between periods of CPU work and periods of I/O activity.
What Is CPU Burst?
A CPU burst is a period during which a process is actively executing instructions on the CPU.
What Is I/O Burst?
An I/O burst is a period during which the process is performing or waiting for input/output work instead of using the CPU.
CPU Burst = process is calculating or executing.
I/O Burst = process is dealing with input/output.
CPU-Bound vs I/O-Bound Processes
Processes do not all behave in the same way. This matters when designing a CPU scheduling policy.
I/O-Bound Process
An I/O-bound process usually performs many I/O operations and often has relatively short CPU bursts.
Examples may include programs that frequently wait for user input, disk operations or network data.
Many short CPU periods mixed with I/O activityCPU-Bound Process
A CPU-bound process spends more time performing calculations and usually has longer CPU bursts.
Examples may include heavy calculations, data processing or encoding tasks.
Longer CPU work with less frequent I/OWhat Is Ready Queue in CPU Scheduling?
The ready queue contains processes that are ready to execute and are waiting for CPU time.
The order of the ready queue depends on the CPU scheduling algorithm being used.
When Does CPU Scheduling Take Place?
CPU scheduling decisions are connected with changes in process state. The scheduler may need to act when a process changes from one state to another.
Example: process requests I/O.
Example: process is preempted.
Example: I/O finishes.
Process completes execution.
These transitions help explain the difference between preemptive and non-preemptive CPU scheduling.
Types of CPU Scheduling: Preemptive and Non-Preemptive
CPU scheduling is commonly divided into two broad approaches: preemptive scheduling and non-preemptive scheduling.
Preemptive Scheduling
In preemptive CPU scheduling, the operating system can take the CPU away from a currently running process and give it to another process.
This can happen because of a time-sharing rule, priority decision or another scheduling condition.
Notice how execution can move between processes before one process completely finishes.
Non-Preemptive Scheduling
In non-preemptive CPU scheduling, once a process gets the CPU, it normally keeps it until the process finishes its CPU burst by terminating or moving to a waiting state.
The running process is not normally forced out simply because another ready process arrives.
| Point | Preemptive Scheduling | Non-Preemptive Scheduling |
|---|---|---|
| CPU can be taken away? | Yes, according to scheduling rules. | Normally no during the current CPU burst. |
| Response | Can provide quicker response for interactive work. | A long-running job can make others wait. |
| Context-switch overhead | Can be higher because switches may happen more often. | Usually fewer forced switches. |
| Examples | Round Robin, SRTF, preemptive Priority | FCFS, SJF, non-preemptive Priority |
Types of Schedulers in Operating System
Students often confuse CPU scheduling algorithms with types of schedulers in OS.
They are not the same thing.
A scheduler is an operating-system component that makes scheduling decisions at a particular level.
1. Long-Term Scheduler in Operating System
The long-term scheduler is also called the job scheduler.
Its main job is to decide which jobs or processes should be admitted into the system for execution.
By controlling how many processes enter the active system, the long-term scheduler can influence the degree of multiprogramming.
What Is Degree of Multiprogramming?
Degree of multiprogramming means the number of processes that are present in memory and competing for system resources.
Why Is Long-Term Scheduling Important?
If too many processes are admitted, the system may become heavily loaded. If too few are admitted, resources may not be used efficiently.
In traditional descriptions, the long-term scheduler may also try to maintain a useful mix of CPU-bound and I/O-bound processes.
2. Short-Term Scheduler in Operating System
The short-term scheduler is also commonly called the CPU scheduler.
It selects one process from the ready queue and decides which process should execute on the CPU next.
Because CPU scheduling decisions happen very frequently, the short-term scheduler must make decisions quickly.
Short-term scheduler selects a process from the ready queue and chooses it for CPU execution.
3. Medium-Term Scheduler in Operating System
The medium-term scheduler helps manage processes that may be temporarily removed from active memory and later brought back.
This idea is commonly connected with suspension and swapping.
It can help reduce the number of active processes when the system needs to control memory pressure or the degree of multiprogramming.
Long-Term vs Short-Term vs Medium-Term Scheduler
| Point | Long-Term | Short-Term | Medium-Term |
|---|---|---|---|
| Another name | Job Scheduler | CPU Scheduler | Swapper / medium-term scheduling function |
| Main decision | Which jobs enter active processing | Which ready process gets CPU next | Which processes should be suspended or resumed |
| Frequency | Relatively low | Very high | As required |
| Speed requirement | Less critical than short-term scheduler | Must be very fast | Moderate / situation dependent |
| Controls | Admission and degree of multiprogramming | CPU allocation | Suspension and memory pressure |
What Is Dispatcher in CPU Scheduling?
The CPU scheduler decides which process should run next, but another component is needed to actually give control of the CPU to that process.
That component is called the dispatcher.
Makes the decision: “Run Process P2 next.”
Carries out the decision and transfers CPU control to P2.
Main Work of a Dispatcher
A dispatcher may perform tasks such as:
- performing the required context switch,
- switching execution to the proper processor mode where required,
- and transferring control to the correct instruction of the selected process.
What Is Dispatch Latency?
Dispatch latency is the time required to stop one process and start another selected process running.
Scheduler = chooses.
Dispatcher = gives control.
CPU Scheduling and Context Switching
When CPU execution moves from one process to another, the operating system may need to save the state of the old process and restore the state of the new process.
This is called a context switch.
Context switching is necessary for multitasking, but it also has overhead because the CPU spends some time changing execution context instead of doing application work.
CPU Scheduling Criteria in Operating System
Different CPU scheduling algorithms can produce different results. We therefore need performance measurements to compare them.
These measurements are called CPU scheduling criteria or CPU scheduling performance criteria.
CPU Utilization
CPU utilization tells us how much of the available processor time is being used for useful CPU work.
In general, we want to keep CPU utilization high without making the system unhealthy or unresponsive.
CPU Utilization = Busy CPU Time / Total Time × 100Throughput
Throughput means the number of processes or jobs completed during a given period of time.
Throughput = Completed Processes / Unit TimeTurnaround Time
Turnaround time is the total elapsed time from a process arriving until it finishes.
TAT = Completion Time − Arrival TimeWaiting Time
Waiting time is the total time a process spends waiting in the ready queue for CPU service.
WT = Turnaround Time − Total CPU Burst TimeResponse Time
Response time measures how long a process waits before receiving its first CPU service or first response opportunity.
RT = First CPU Start Time − Arrival TimeFairness
A scheduler should avoid allowing some processes to wait forever while other processes repeatedly receive CPU time.
Fairness has no single simple formula that fits every scheduler, but it is an important design goal.
Important CPU Scheduling Terms: AT, BT, CT, TAT, WT & RT
These short forms appear again and again in CPU scheduling numericals. Understand them before solving any Gantt chart question.
Time at which a process becomes ready and enters scheduling consideration.
Total CPU execution time required in the simplified scheduling problem.
Time at which the process finishes.
Total elapsed time from arrival to completion.
Total time spent waiting in the ready queue.
Time from arrival until the process gets CPU for the first time.
Simple CPU Scheduling Performance Example
Let us understand the formulas before moving to individual scheduling algorithms.
Arrival = 2
Burst = 5
Time = 4
Time = 9
Step 1: Turnaround Time
Step 2: Waiting Time
Step 3: Response Time
Average Waiting Time and Average Turnaround Time
When comparing CPU scheduling algorithms, questions often ask for average waiting time or average turnaround time.
Add the waiting times of all processes and divide by the number of processes.
Average Turnaround Time:
Add the turnaround times of all processes and divide by the number of processes.
Average Response Time:
Add the response times of all processes and divide by the number of processes.
What Should a Good CPU Scheduling Algorithm Try to Achieve?
However, improving one measure can sometimes make another measure worse.
That is why there is no single CPU scheduling policy that is automatically the best for every type of computer system.
CPU Scheduling Goals for Different Types of Systems
Throughput and turnaround time may be major concerns because many jobs need to be completed efficiently.
Response time becomes very important because users expect applications to react quickly.
Meeting required timing constraints or deadlines can be more important than simply minimizing an average waiting time.
Main CPU Scheduling Algorithms in Operating System
CPU scheduling algorithms define the rule used to select the next ready process. Each algorithm handles the ready queue differently.
The process that arrives first gets CPU service first. It is simple but can suffer from the convoy effect when a long job delays shorter jobs.
Usually Non-PreemptiveThe ready process with the smallest predicted CPU burst is selected first. It can produce a low average waiting time when burst lengths are known or estimated well.
Non-Preemptive VersionThis is the preemptive form of shortest-job scheduling. The process with the smallest remaining CPU time is preferred.
PreemptiveCPU selection is based on process priority. Priority scheduling can be implemented in either preemptive or non-preemptive form.
Priority BasedEvery ready process gets a limited amount of CPU time called a time quantum or time slice.
If the process does not finish during its quantum, it can return to the ready queue.
Preemptive · Time SharingProcesses are divided into separate ready queues, often according to process type or class. Different queues can use different scheduling policies.
Multiple Fixed QueuesProcesses can move between queues according to their behaviour and the rules of the scheduler. This gives the system more flexibility than fixed multilevel queues.
Dynamic QueuesHRRN uses a response ratio that considers both waiting time and service time, helping older waiting jobs gain preference.
Response Ratio BasedWhat Is Time Quantum in CPU Scheduling?
A time quantum, also called a time slice, is the limited amount of CPU time given to a process in scheduling approaches such as Round Robin.
If the time quantum is very large, Round Robin can begin to behave more like FCFS.
If the quantum is extremely small, processes may appear more responsive, but context-switch overhead can increase.
What Is Convoy Effect in CPU Scheduling?
The convoy effect can occur when a long CPU-bound process gets ahead of several short processes and makes them wait.
FCFS scheduling is commonly used to explain this problem.
Starvation and Aging in CPU Scheduling
Some scheduling policies may repeatedly favour certain processes. This can create another problem called starvation.
Starvation
A process keeps waiting for a very long time because other processes repeatedly receive preference.
Aging
Aging gradually improves the priority of a process that has been waiting for a long time, helping it eventually receive CPU service.
Starvation = process keeps waiting.
Aging = waiting process slowly gets better priority.
Fairness in CPU Scheduling
Fairness does not necessarily mean that every process receives exactly the same amount of CPU time.
Different processes can have different priorities, deadlines or scheduling classes. The main idea is that the scheduling policy should behave according to its defined goals without unnecessarily allowing eligible processes to wait forever.
Priority in CPU Scheduling
Some CPU scheduling systems assign a priority to processes. A scheduler can use this priority when deciding which process should execute next.
CPU Scheduling on Multi-Core Systems
The basic examples in this chapter often assume one CPU execution resource so that scheduling is easy to understand.
Modern systems may have several processor cores. The operating system then has additional scheduling decisions, such as deciding which runnable task should use which core and how work should be balanced.
Real operating systems can therefore use much more advanced scheduling designs than the simple classroom algorithms.
CPU Scheduling Overhead
Scheduling itself is useful, but it is not completely free.
The operating system needs time to make scheduling decisions, perform context switches and update process-management information.
Therefore, a scheduling policy should not create unnecessary switching just to improve one small performance measure.
Common Mistakes Students Make in CPU Scheduling
Scheduler selects the process. Dispatcher gives CPU control to it.
A preempted process can wait in the ready queue several times.
Turnaround ends when the process finishes. Response time only measures how long it waited for its first service.
Long-term, short-term and medium-term schedulers describe scheduling roles, while FCFS, SJF and Round Robin are scheduling policies or algorithms.
It can improve responsiveness, but it can also increase switching overhead.
The best policy depends on workload and system goals.
Complete CPU Scheduling Flow in Simple Words
CPU Scheduling in OS Exam Preparation
For a 2-Mark Question
Answer: CPU Scheduling in OS is the process of selecting one process from the ready queue and allocating the CPU to it. Its main aim is to use CPU time efficiently and improve system performance.
For a 5-Mark Question
Write:
- definition of CPU scheduling,
- need for CPU scheduling,
- ready queue,
- preemptive and non-preemptive scheduling,
- main CPU scheduling criteria.
For an 8–10 Mark Question
Explain in this order:
- meaning of CPU Scheduling in Operating System,
- need and multiprogramming connection,
- CPU-I/O burst cycle,
- CPU-bound and I/O-bound processes,
- ready queue,
- scheduling decision points,
- preemptive vs non-preemptive scheduling,
- long-term scheduler,
- short-term scheduler,
- medium-term scheduler,
- dispatcher and dispatch latency,
- CPU scheduling criteria,
- CPU utilization, throughput, turnaround, waiting and response time,
- brief overview of scheduling algorithms.
CPU Scheduling Practice Questions
CPU Scheduling Quick Revision
Frequently Asked Questions About CPU Scheduling in OS
What is CPU Scheduling in OS?
CPU Scheduling in OS is the method used by the operating system to select a ready process and allocate the CPU to it.
Why is CPU scheduling required?
CPU scheduling is required because multiple processes may be ready at the same time, while available CPU execution resources are limited. The operating system therefore needs a rule for deciding which process runs next.
What are the main types of CPU scheduling?
CPU scheduling is commonly classified as preemptive scheduling and non-preemptive scheduling.
What are the three types of schedulers in Operating System?
The three commonly taught types are long-term scheduler, short-term scheduler and medium-term scheduler.
What is a short-term scheduler?
The short-term scheduler, also called the CPU scheduler, selects a process from the ready queue for CPU execution.
What is a long-term scheduler?
The long-term scheduler or job scheduler decides which jobs should be admitted into the active system and influences the degree of multiprogramming.
What is a medium-term scheduler?
The medium-term scheduler helps temporarily suspend or later reintroduce processes, often to manage memory pressure and the degree of multiprogramming.
What is dispatcher in CPU scheduling?
The dispatcher is the operating-system component that transfers CPU control to the process selected by the CPU scheduler.
What are the main CPU scheduling criteria?
Important CPU scheduling criteria include CPU utilization, throughput, turnaround time, waiting time, response time and fairness.
What is turnaround time in CPU scheduling?
Turnaround time is the total elapsed time from process arrival to process completion. It is commonly calculated as Completion Time minus Arrival Time.
What is waiting time in CPU scheduling?
Waiting time is the total time a process spends waiting in the ready queue. In standard scheduling numericals, it can be calculated as Turnaround Time minus total CPU Burst Time.
What is response time in CPU scheduling?
Response time is the time from process arrival until the process receives CPU service for the first time.
What is CPU utilization?
CPU utilization represents the proportion of total time during which the CPU is busy performing useful execution work.
What is throughput in CPU scheduling?
Throughput is the number of processes or jobs completed during a unit of time.
What is time quantum?
Time quantum is the limited CPU time slice assigned to a process in scheduling methods such as Round Robin.
What is starvation in CPU scheduling?
Starvation occurs when a process waits for an excessively long time because other processes continue to receive scheduling preference.
What is aging in CPU scheduling?
Aging is a technique that gradually increases the priority of a process that has been waiting for a long time, helping reduce starvation.
Which CPU scheduling algorithm is best?
There is no single CPU scheduling algorithm that is best for every workload. Different systems may prioritize throughput, response time, deadlines, fairness or other goals.
Conclusion
CPU Scheduling in OS becomes much easier when you see the complete flow instead of memorising separate definitions. Several processes may wait in the ready queue. The CPU scheduler selects one of them, and the dispatcher gives CPU control to that process.
A process normally moves through CPU bursts and I/O bursts, so the operating system repeatedly gets chances to schedule other work. Depending on the scheduling policy, CPU allocation can be preemptive or non-preemptive.
The main types of schedulers in Operating System are the long-term scheduler, short-term scheduler and medium-term scheduler. They work at different levels: admitting jobs, selecting the next ready process, and controlling suspension or reintroduction of processes.
Finally, CPU scheduling performance is measured using criteria such as CPU utilization, throughput, turnaround time, waiting time and response time. Once these concepts are clear, algorithms such as FCFS, SJF, SRTF, Priority, Round Robin, Multilevel Queue and Multilevel Feedback Queue become much easier to learn.
