Comparative Analysis of Traditional V/S ML based Scheduling Algorithms

Authors: Khushi Wasnik, Manas Hardikar, Arkaj Rankhambe, Rudrayani Adichwal, Yash Kate

Students of T.E Electronics and Telecommunications, Vidyalankar Institute of Technology, Wadala

Under the guidance of Dr. Amit K Nerurkar

Introduction

CPU scheduling algorithms are the basis of multi-programmed operating systems. They make computers more productive by switching between processes. Their significance lies in their ability to enhance key performance metrics such as CPU utilization, throughput, and response time, while also ensuring fair resource allocation among competing processes. Evolution of scheduling algorithms has closely paralleled the advancement of computer systems, with batch processing used in early computing days.

Though this method was suitable for the early computers with limited capabilities, the long waiting times made it far more inefficient in terms of modern day computers. In the efforts to bridge the gap between more advanced computer systems and scheduling algorithms, this led to the development of traditional scheduling algorithms that form the backbone of modern operating systems, providing improved efficiency, responsiveness, and fairness in process execution.

ML integration in operating systems is an ever growing concept. Traditional scheduling algorithms often rely on fixed rules and assumptions, which can lead to inefficiencies such as long waiting times, starvation, or suboptimal CPU utilization. By incorporating ML, operating systems can adopt a data-driven approach to scheduling, using historical patterns and real-time system metrics to predict process behavior, estimate execution times, and dynamically adjust priorities. This enables more efficient resource allocation, reduces latency, and improves overall system performance.

What is Scheduling?

Suppose you are in a store waiting for billing your order, there are multiple people before you and multiple people after you each waiting for their own task. A single worker is handling billing, so naturally, only one person can be served at a time. Now, what happens next depends on how that worker decides to manage the line. The worker might simply serve customers in the order they arrived — first come, first served. Other times, they may notice that someone with just one or two items could be processed quickly and let them go ahead. In another scenario, they might prioritize elderly customers, regardless of how many items they have. As such, in a single processor system only one process runs at a time, others wait till the CPU is free and rescheduled which mirrors with the handling of customers in our store.

• Customers in line → Processes in the ready queue
• Billing counter worker → CPU
• Waiting line → Ready queue
• Billing one customer at a time → CPU executes one process at a time (in a single-core system)

CPU Scheduling

This allocation of tasks is termed as scheduling. Multiple tasks compete for a single resource, and a scheduling policy determines fairness, efficiency, and responsiveness. Just like in the store, the choice of strategy can significantly impact waiting time, responsiveness, and overall experience.

Traditional Algorithms

Traditional algorithms can be broadly classified as preemptive and non-preemptive. Preemptive algorithms can be either priority based or depend on time sharing policy, meaning the operating system can interrupt a running algorithm and allocate the CPU to another process that it deems as more important. Meanwhile non-preemptive algorithms have no such obligations i.e once a process starts using the CPU, it runs until it finishes or moves to a waiting state. The operating system cannot interrupt the running task.

Source: https://peerdh.com/blogs/programming-insights/understanding-real-time-systems-and-their-scheduling-algorithms-in-c

Preemptive algorithms

Preemptive Shortest Job First (SRTF)

Always serves the customer with the least remaining service time; can switch if a new customer has shorter time

Customer A (5 min), B (2 min) arrives after 1 min → switch to B

Round Robin (RR)

Each customer gets a fixed time slice (quantum); rotates in line

Time quantum = 3 min; Customer A (5), B (4) → A served 3 min, B 3 min, then A finishes

Priority Preemptive

Customers have priority; higher-priority customers can interrupt lower-priority ones

Customer A (low priority, 5 min), B (high priority, 3 min) → B interrupts A

Non-Preemptive Algorithms

First-Come, First-Served (FCFS)

Serve customers in the order they arrive; no interruptions

Customer A (5 min) arrives first, B (2 min) arrives later → A served completely, then B

Non-Preemptive Shortest Job First (SJF)

Serve the customer with the shortest service time next, but once service starts, it cannot be interrupted

Customer A (5 min), B (2 min) → B served first (if B arrived before A started), then A

Priority Non-Preemptive

Serve customers based on priority; once service starts, it cannot be interrupted

Customer A (low priority, 5 min), B (high priority, 3 min) → If A is already being served, B waits; next customer chosen by priority

These traditional algorithms come at their own cost. Each algorithms has a certain set of drawbacks such as

• Long waiting time for some tasks
• Risk of starvation for low priority tasks
• Overhead due to frequent context switching
• Choosing time quantum is tricky

ML Integration

Machine learning can be broadly classified into three types: Supervised, Unsupervised and Reinforcement. Each category has its own set of algorithms that can be used to upgrade the existing scheduling algorithms. Leveraging ML models for adaptive and self optimising systems. CPU scheduling is the process of deciding which process in the ready queue gets CPU time next. Common metrics include:

Throughput: Number of processes completed per unit time.

Turnaround time: Time from submission to completion.

Waiting time: Time a process spends waiting in the ready queue.

Response time: Time from request submission to first response.

The Supervised Learning approach aims to enhance CPU scheduling efficiency. These methods use regression and classification techniques to forecast task execution times and enhance scheduling policies using historical system data. It focuses on leveraging already present data to further improve operating systems scheduling capabilities. On the other hand reinforcement learning focuses on how a CPU allocates time to different processes. From feedback based on system performance RL allows the scheduler to learn an optimal time policy.

Both of these algorithms are widely researched based on their ability to make CPU scheduling more adaptive and flexible. When traditional algorithms fail due to their fixed heuristics when used in unpredictable work cases, ML algorithms can compensate based on their ability to learn via previous data to make up for it.

But both of these have their own differences: supervised learning depends on a labelled dataset of system states and optimal actions, making it more reliable on past examples. Its main focus is to predict which process to run next based on previous examples. Reinforcement learning learns from rewards with no dependency on labelled data, making it highly adaptable for challenging dynamics. This can be used to reduce waiting time or maximize throughput.

Dig: Supervised Learning in scheduling algorithm

Dig: Reinforcement Learning

Analysis