CPU scheduling algorithms in operating systems (2023)

In this CPU planning tutorial, you will learn:

• What is CPU Scheduling?
• Types of CPU Scheduling
• Important CPU scheduling terminologies
• CPU Scheduling Criteria
• Interval Timer
• What is Dispatcher?
• Types of CPU Scheduling Algorithms
• First come, first served
• Shortest remaining time
• Priority-Based Scheduling
• Round Robin Scheduling
• Shortest job first
• Scheduling of queues at multiple levels
• The purpose of a scheduling algorithm

Types of CPU Scheduling

Here are two types of scheduling methods:

preventive planning

With preemptive scheduling, the tasks are usually assigned with their priorities. Sometimes it's important to run a higher-priority task before another lower-priority task, even if the lower-priority task is still running. The lower priority task lasts for some time and resumes when the higher priority task finishes its execution.

Non-preventive planning

With this type of scheduling method, the CPU was allocated to a specific process. The process that is keeping the CPU busy frees the CPU either by switching contexts or by terminating. It is the only method that can be used for different hardware platforms. That's because it doesn't require any special hardware (such as a timer) like preemptive scheduling.

When is planning preventive or not preemptive?

Consider these four parameters to determine whether planning is preemptive or non-preemptive:

1. A process changes from the running to the waiting state.
2. Certain processes transition from the running state to the ready state.
3. Certain processes transition from the wait state to the ready state.
4. The process has completed its execution and terminated.

Only conditions 1 and 4 apply, the scheduling is referred to as non-preemptive.

All other planning is preventive.

Important CPU scheduling terminologies

• Burst Time/Execution Time:It is a time required for the process to complete execution. It is also called run time.
• Arrival time:when a process enters a ready state
• end time:when the process completes and exits a system
• Multiprogramming:Multiple programs that can coexist in memory.
• Jobs:It's a kind of program without any kind of user interaction.
• User:It's a kind of user interaction program.
• Procedure:It is the reference used for both the job and the user.
• CPU/IO burst cycle:Characterizes process execution that alternates between CPU and I/O activity. CPU times are usually shorter than I/O times.

CPU Scheduling Criteria

A CPU scheduling algorithm tries to maximize and minimize:

Maximize:

CPU usage:CPU usage is the main task where the operating system has to ensure that the CPU stays as busy as possible. It can be between 0 and 100 percent. However, for the RTOS, it can range from 40 percent for low-level to 90 percent for the high-level system.

Throughput:The number of processes that complete their execution per unit of time is known as throughput. So when the CPU is busy executing the process, work is being done at that time, and the work completed per unit of time is called throughput.

Minimize:

Waiting period:The wait time is an amount that a given process must wait in the ready queue.

Reaction time:It is a period of time that the request has been submitted until the first response is produced.

change of sides:Turnaround time is a time it takes for a specific process to run. It is the calculation of the total time spent getting into memory, waiting in the queue, and executing on the CPU. The time between the time the process is submitted and the time it is completed is the processing time.

Interval Timer

Timer interrupt is a method closely related to preemption. When a specific process gets the CPU allocation, a timer can be set to a specific interval. Both timer interrupt and preemption force a process to return CPU before its CPU burst completes.

Most multiprogrammed operating systems use some kind of timer to prevent a process from stalling the system forever.

What is Dispatcher?

It is a module that provides control of the CPU to the process. The dispatcher should be fast so that it can run on every context switch. Dispatch latency is the time it takes for the CPU scheduler to stop one process and start another.

Functions performed by the dispatcher:

• context switch
• Switch to user mode
• Move to the right place in the newly loaded program.

Types of CPU Scheduling Algorithms

There are mainly six types of process scheduling algorithms

1. First come, first served (FCFS)
2. Shortest-Job-First (SJF) Scheduling
3. Shortest remaining time
4. priority planning
5. Round Robin Scheduling
6. Multi-level queue scheduling

First come, first served

First Come First Serve is the full form of FCFS. It is the simplest and most simplistic CPU scheduling algorithm. With this type of algorithm, the process requesting the CPU gets the CPU allocation first. This scheduling method can be managed with a FIFO queue.

When the process enters the ready queue, its PCB (Process Control Block) is connected to the end of the queue. So when the CPU becomes free, it should be allocated to the process at the front of the queue.

Properties of the FCFS method:

• It offers a non-preemptive and a preemptive scheduling algorithm.
• Jobs are always performed on a first come, first served basis
• It's easy to implement and use.
• However, this method is poorly performing and the overall latency is quite high.

Shortest remaining time

The full form of SRT is the shortest time remaining. It is also known as preemptive SJF scheduling. With this method, the process is assigned to the task that is closest to its completion. This technique prevents a newer, ready process from catching the completion of an older process.

Properties of the SRT scheduling method:

• This method is mostly used in batch environments where short jobs need to be given priority.
• This is not an ideal method to implement on a shared system where the required CPU time is unknown.
• Associate each process with the length of its next CPU burst. The operating system uses these lengths, which helps to schedule the process with the shortest possible time.

Priority-Based Scheduling

Priority scheduling is a technique for scheduling processes based on priority. In this method, the scheduler selects the tasks to be performed according to priority.

Priority scheduling also helps the operating system accommodate priority assignments. The higher priority processes should run first while jobs with the same priority run on a round robin or FCFS basis. Priority can be set based on memory requirements, time requirements, etc.

Round Robin Scheduling

Round Robin is the oldest and simplest scheduling algorithm. The name of this algorithm comes from the round robin principle, where each person in turn gets an equal share of something. It is mainly used for scheduling algorithms in multitasking. This algorithm method helps in starvation execution of processes.

Features of round robin scheduling

• Round Robin is a hybrid model that is clock controlled
• The time slice allocated to a specific task to be processed should be minimal. However, it can vary for different processes.
• It is a real-time system that responds to the event within a specified time limit.

Shortest job first

SJF is a full form of (Shortest Job First) is a scheduling algorithm designed to choose the process with the shortest execution time for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average wait time for other processes waiting to run.

Properties of SJF Scheduling

• It is assigned to each job as a unit of time for completion.
• With this method, if the CPU is available, the next process or job with the shortest execution time runs first.
• It is implemented with a non-preemptive policy.
• This algorithm method is useful for batch processing where waiting for jobs to complete is not critical.
• It improves job performance by offering shorter jobs that should be run first and tend to have a shorter turnaround time.

Scheduling of queues at multiple levels

This algorithm separates the completed queue into several separate queues. In this method, processes are assigned to a queue based on a specific property of the process, such as process priority, amount of memory, etc.

However, this is not an independent scheduling OS algorithm as it has to use other types of algorithms to schedule the jobs.

Feature of Multi-Level Queue Scheduling:

• Multiple queues should be maintained for processes with some characteristics.
• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.

The purpose of a scheduling algorithm

Here are the reasons for using a scheduling algorithm:

• The CPU uses scheduling to improve its efficiency.
• It helps you allocate resources between competing processes.
• The maximum utilization of the CPU can be achieved through multiprogramming.
• The processes to be executed are in the ready queue.

Summary:

• CPU scheduling is a process of determining which process owns the CPU to run while another process is suspended.
• With preemptive scheduling, the tasks are usually assigned with their priorities.
• With the non-preemptive scheduling method, the CPU was allocated to a specific process.
• The burst time is the time it takes for the process to complete execution. It is also called run time.
• CPU usage is the main task where the operating system has to ensure that the CPU stays as busy as possible.
• The number of processes that complete their execution per unit of time is known as throughput.
• The wait time is an amount that a given process must wait in the ready queue.
• It is the amount of time the request has been sent before the first response is produced.
• Processing time is the time it takes to complete a specific process.
• Timer interrupt is a method closely related to preemption.
• A dispatcher is a module that provides control of the CPU to the process.
• Six types of process scheduling algorithms are: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling.
• In the first-come-first-serve method, the process requesting the CPU gets the CPU allocation first.
• In the shortest time remaining, the process is assigned to the task that is closest to its completion.
• In priority scheduling, the scheduler selects the tasks to be performed according to priority.
• Round robin scheduling works on the principle that each person in turn gets an equal share of something.
• In Shortest job first, the shortest execution time should be selected for the next execution.
• The multi-level scheduling method separates the ready queue into several separate queues. With this method, processes are assigned to a queue based on a specific property.
• The CPU uses scheduling to improve its efficiency.