CPU Scheduling Algorithms in Operating Systems

By : Nathaniel Brooks Nathaniel Brooks
Hours Updated

⚡ Smart Summary

CPU scheduling determines which ready process the operating system runs next, keeping the processor busy and improving performance through algorithms such as First Come First Serve, Shortest Job First, Priority, and Round Robin.

  • 🔄 Definition: CPU scheduling picks a process from the ready queue whenever the CPU would otherwise sit idle.
  • ⚖️ Types: Preemptive scheduling can interrupt a running task, while non-preemptive scheduling waits for it to release the CPU.
  • 📊 Criteria: Good algorithms maximize CPU utilization and throughput while minimizing waiting, response, and turnaround time.
  • 🧮 Algorithms: FCFS, SJF, Shortest Remaining Time, Priority, Round Robin, and Multilevel Queue each suit different workloads.
  • 🚦 Dispatcher: The dispatcher performs the context switch that hands CPU control to the selected process.
  • 🤖 AI Angle: Machine learning tunes scheduling decisions, and Copilot helps code and test scheduler algorithms.
Read More

CPU Scheduling Algorithms in Operating Systems

What is CPU Scheduling?

CPU Scheduling is a process of determining which process will own the CPU for execution while another process is on hold. The main task of CPU scheduling is to make sure that whenever the CPU remains idle, the OS selects at least one of the processes available in the ready queue for execution. The selection process is carried out by the CPU scheduler, which selects one of the processes in memory that are ready for execution.

Types of CPU Scheduling

Here are two kinds of scheduling methods:

Types of CPU Scheduling

Preemptive Scheduling

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

Non-Preemptive Scheduling

In this type of scheduling method, the CPU is allocated to a specific process. The process that keeps the CPU busy will release the CPU either by switching context or terminating. It is the only method that can be used across various hardware platforms, because it does not need special hardware (for example, a timer) like preemptive scheduling.

When is Scheduling Preemptive or Non-Preemptive?

To determine whether scheduling is preemptive or non-preemptive, consider these four parameters:

  1. A process switches from the running to the waiting state.
  2. A specific process switches from the running state to the ready state.
  3. A specific process switches from the waiting state to the ready state.
  4. A process finishes its execution and terminates.

If only conditions 1 and 4 apply, the scheduling is called non-preemptive. All other scheduling situations are preemptive.

Important CPU Scheduling Terminologies

  • Burst Time/Execution Time: The time required by a process to complete execution. It is also called running time.
  • Arrival Time: The time when a process enters the ready state.
  • Finish Time: The time when a process completes and exits the system.
  • Multiprogramming: A number of programs that can be present in memory at the same time.
  • Jobs: A type of program without any kind of user interaction.
  • User: A kind of program that has user interaction.
  • Process: The reference that is used for both a job and a user.
  • CPU/IO burst cycle: Characterizes process execution, which 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 the following:

CPU Scheduling Criteria

Maximize

CPU utilization: CPU utilization is the main task in which the operating system needs to make sure that the CPU remains as busy as possible. It can range from 0 to 100 percent. However, for an RTOS, it can range from 40 percent for a low-level system to 90 percent for a high-level system.

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

Minimize

Waiting time: Waiting time is the amount of time a specific process must wait in the ready queue.

Response time: It is the amount of time from when the request was submitted until the first response is produced.

Turnaround Time: Turnaround time is the amount of time taken to execute a specific process. It is the total time spent waiting to get into memory, waiting in the queue, and executing on the CPU. The period between the time of process submission and the completion time is the turnaround time.

Interval Timer

Timer interruption is a method that is closely related to preemption. When a certain process gets the CPU allocation, a timer may be set to a specified interval. Both timer interruption and preemption force a process to return the CPU before its CPU burst is complete.

Most multi-programmed operating systems use some form of a timer to prevent a process from tying up the system forever.

What is Dispatcher?

The dispatcher 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 amount of time needed by the CPU scheduler to stop one process and start another.

Functions performed by the dispatcher:

  • Context switching.
  • Switching to user mode.
  • Moving to the correct location in the newly loaded program.

Types of CPU Scheduling Algorithms

There are mainly six types of process scheduling algorithms:

  1. 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

Scheduling Algorithms

Scheduling Algorithms

First Come First Serve

FCFS stands for First Come First Serve. It is the easiest and simplest CPU scheduling algorithm. In this type of algorithm, the process that requests the CPU gets the CPU allocation first. This scheduling method can be managed with a FIFO queue.

As a process enters the ready queue, its PCB (Process Control Block) is linked with the tail of the queue. So, when the CPU becomes free, it should be assigned to the process at the beginning of the queue.

Characteristics of the FCFS Method

  • It is a non-preemptive scheduling algorithm.
  • Jobs are always executed on a first-come, first-serve basis.
  • It is easy to implement and use.
  • However, this method is poor in performance, and the general wait time is quite high.

RELATED ARTICLES

Shortest Remaining Time

The full form of SRT is Shortest Remaining Time. It is also known as SJF preemptive scheduling. In this method, the process will be allocated to the task that is closest to its completion. This method prevents a newer ready-state process from holding up the completion of an older process.

Characteristics of the SRT Scheduling Method

  • This method is mostly applied in batch environments where short jobs need to be given preference.
  • This is not an ideal method to implement in a shared system where the required CPU time is unknown.
  • Each process is associated with the length of its next CPU burst, so the operating system uses these lengths to schedule the process with the shortest possible time.

Priority Based Scheduling

Priority Scheduling is a method of scheduling processes based on priority. In this method, the scheduler selects the tasks to work on as per their priority.

Priority scheduling also helps the OS involve priority assignments. The processes with higher priority are carried out first, whereas jobs with equal priorities are carried out on a round-robin or FCFS basis. Priority can be decided based on memory requirements, time requirements, and other factors.

Round-Robin Scheduling

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

Characteristics of Round-Robin Scheduling

  • Round robin is a hybrid model that is clock-driven.
  • The time slice assigned for a specific task to be processed should be minimal. However, it may vary for different processes.
  • It behaves like a time-sharing system that responds to each process within a specific time limit.

Shortest Job First

SJF (Shortest Job First) is a scheduling algorithm in which the process with the shortest execution time is selected for execution next. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution.

Characteristics of SJF Scheduling

  • Each job is associated with a unit of time to complete.
  • In this method, when the CPU is available, the next process or job with the shortest completion time is executed first.
  • It is implemented with a non-preemptive policy.
  • This algorithm is useful for batch-type processing, where waiting for jobs to complete is not critical.
  • It improves job output by executing shorter jobs first, which mostly have a shorter turnaround time.

Multiple-Level Queues Scheduling

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

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

Characteristics of Multiple-Level Queues Scheduling

  • Multiple queues should be maintained for processes with shared characteristics.
  • Every queue may have its own separate scheduling algorithm.
  • 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 among competing processes.
  • The maximum utilization of the CPU can be obtained with multiprogramming.
  • The processes that are to be executed are kept in the ready queue.

FAQs

There is no single best algorithm. Shortest Job First gives the lowest average waiting time and is provably optimal, but it needs known burst times and can starve long jobs. Round Robin is fairer for time-sharing systems.

Starvation happens when a process waits indefinitely because higher-priority or shorter jobs keep getting the CPU first. It is common in Priority and Shortest Job First scheduling, where long or low-priority processes may never run.

Aging is a technique that gradually raises the priority of processes that have waited a long time. This prevents starvation in priority-based scheduling, since even a low-priority process eventually reaches a high enough priority to run.

Context switching saves the state of the current process and loads another’s from its PCB, so execution can resume later. It is pure scheduling overhead handled by the dispatcher on every switch between processes.

The long-term (job) scheduler controls how many processes enter the ready queue and sets the degree of multiprogramming. The short-term (CPU) scheduler picks which ready process runs next and runs far more often.

Linux uses the EEVDF scheduler, which replaced the Completely Fair Scheduler (CFS) in kernel 6.6. Windows uses a preemptive, priority-based scheduler with round-robin time slicing within each priority level.

Machine learning models predict process burst times and tune or select scheduling policies to cut waiting time and energy use. These AI-driven schedulers are studied for data centers, cloud servers, and real-time systems.

Yes. GitHub Copilot can generate FCFS, SJF, Priority, and Round Robin code along with Gantt-chart and waiting-time calculations. Always verify edge cases, tie-breaking rules, and average-time formulas before relying on the output.

Summarize this post with: