Disclaimer
⚠️ Where the Scheduler whispers, processes tremble — for it decides who runs… and who fades into starvation.
The following content ventures into the ticking heart of the OS — where time slices are bargained, queues grow restless, and scheduling algorithms silently wage war to minimize the average waiting time of every process.
Students and beginners, tread carefully — the Scheduler watches every move, counts every cycle, and never forgets who waited longest.
In this OS series, the focus remains on the Operating System (software context) components, not the hardware mechanics beneath them. (For the hardware side of CPU pipelines, caches, and context-switch machinery, refer to computer architecture.)
Special Thanks
Heartfelt gratitude to Mr. Adhakshoj Mishra Ji for his insightful session and for reviewing this blog.
A sincere thanks as well to the BreachForce Community Members for sharing their valuable notes, and to the BreachForce Community Volunteers for helping collate and refine this content.
Preface
In the last blog, we explored how Privileged Mode emerged inside our MMU — how we designed SPI, MSRs, and dedicated interrupt handlers to enforce strict control, protect critical system state, and ensure the kernel always remained safely isolated from user processes.
In this blog, we’ll uncover the depths of process scheduling by walking through a series of problems and exploring their possible solutions. As we refine each idea, we’ll naturally encounter subtle design caveats—tiny scheduling dilemmas that demand their own mini-solutions. Through these iterations, we’ll slowly sculpt and evolve our vision of what an ideal scheduler should look like.
Important Terminologies
Process: A program in execution with its own memory space.
Task: A generic term that may refer to either a process or a thread, depending on the OS design.
In this blog, the words process and task will be used interchangeably.
Job: A job is a unit of work submitted to the operating system for execution, typically representing a process before it enters the ready queue.
CPU Cycle: The smallest unit of time in which the CPU performs operations; scheduling algorithms often treat each cycle (or a group of cycles) as the basic time quantum for executing processes.
Waiting Time: The total time a process spends in the ready queue waiting before it gets CPU time for execution. It excludes actual CPU run time and I/O time
Process Queue: A data structure used by the operating system to organize and manage processes based on their current state - such as the ready, waiting/blocking, or **terminated -**allowing the scheduler to decide which process should run next.
Process Scheduling
In the 1980s, computers were extremely expensive, and computational resources were limited. The primary goal was to complete as many tasks as possible using the available hardware efficiently.
When designing an Operating System, our focus should revolve around two key aspects:
Accuracy of the Program: This responsibility lies with the developer. The program running on the CPU is assumed to be tested, verified, and trusted by users. The OS does not alter program logic; it simply executes it.
Efficiency of the Program: This refers to minimizing the total time a process takes to complete. Higher efficiency allows the CPU to perform more work in less time.
To increase efficiency, we aim to complete tasks in the shortest possible time.
To achieve this, we must minimize the waiting time of processes during scheduling and context switching, because freeing the CPU as soon as possible allows more tasks to be completed.
This is why we design a Process Scheduling Algorithm, supported by a process queue, to ensure that tasks are executed efficiently and system resources are utilized optimally.
Problem - How to reduce overhead while executing processes?
When multiple processes run concurrently, the system eventually reaches a point where it must pause accepting new processes so that the currently running ones can complete.
Beyond this saturation point, the OS can no longer accommodate new processes in the process queue without degrading performance.
Therefore, our goal is to determine a threshold - after how many processes should the scheduler temporarily stop accepting new tasks to prevent system overload.
To better understand this problem, consider the following analogy:
- Why are NEFT and RTGS transactions processed in batches, while IMPS transactions are processed instantly - even though the underlying transaction data is essentially the same?
Solution - Batch them at once
For any running process, we generally encounter two scenarios:
Case 1: The preparation time for the process is negligible (i.e., the overhead is minimal). In this case, we can process tasks immediately as they arrive.
Case 2: There is significant overhead associated with preparing or validating the process (for example, correlating data with other fields before execution).
If there is no overhead, we follow the Case (1) approach: execute processes as they come.
However, if the overhead is substantial—as in Case (2)—then whether we run 100 processes or 1000 processes, the preparation overhead remains roughly the same.
In such situations, it becomes more efficient to batch all the operations together and handle the overhead once rather than repeatedly.
This is exactly why banks use the NEFT/RTGS approach.
Batching reduces overhead, improves efficiency at scale, and prevents system overload caused by continuous individual requests.
Problem — How do we implement batching in Process Scheduling?
Before proceeding, let us assume:
We have a single computer with one CPU, one RAM module, and one storage device.
We have a list of jobs that need to be executed.
The key question is: What is the most efficient way to execute these jobs?
Solution — Implement First Come First Served (FCFS)
For the jobs we want to execute, two major scenarios arise:
Case 1: Jobs have little to no preparation overhead.
In this situation, we can execute jobs immediately as they arrive.
This approach is known as the First Come First Served (FCFS) scheduling algorithm.
Case 2: Jobs have significant preparation overhead, but the overhead does not depend on how many jobs are being processed (assuming the jobs are similar).
In this case, it is more efficient to batch the jobs and handle the overhead only once.
After batching, we can run FCFS on the batch itself.
Example: NEFT and RTGS transactions in banks — they are processed in bulk to minimize repeated overhead.
There are two ways to perform batching:
For simplicity, let us choose Method 1 (time-based batching).
Assume a batching window of 15–30 minutes.
When batching is used, the order of jobs inside the batch does not matter, because the entire batch will take the same overhead time and be processed together (e.g., a fixed 10-minute overhead).
Problem — How to Reduce Average Waiting Time?
The main challenge here is: How do we reduce the average waiting time of all jobs?
Why do we care about minimizing average waiting time?
It improves overall user experience.
It provides a competitive marketing advantage (faster systems feel better).
The end-user does not understand OS internals — they only perceive how long things “feel.”
Let us consider three jobs with the following execution times:
The question now becomes: How can we reduce the average waiting time of these three jobs?
Solution — Implement Shortest Job First (SJF)
We can reduce waiting time by reordering the jobs intelligently instead of running them in the order they arrive.
Using the earlier example, consider the following two possible orderings:
Ordering 1: J1 → J2 → J3
Waiting times
Average waiting time
- (0 + 5 + 8) / 3 = 13 / 3 ≈ 4.3 minutes → 4 minutes (approx)
Ordering 2: J2 → J3 → J1
Waiting times
Average waiting time
- (0 + 3 + 5) / 3 = 8 / 3 ≈ 2.67 minutes → 3 minutes (approx)
Notice that in both cases, the total execution time remains the same: 10 minutes.
But by simply reordering the jobs, we significantly reduce the average waiting time.
Therefore, the optimal strategy is to execute shorter jobs first.
This leads us to our second scheduling algorithm:
Shortest Job First (SJF)
- An algorithm that minimizes average waiting time by always selecting the job with the shortest execution time.
If larger jobs run first, smaller jobs end up experiencing unnecessarily long waiting times.
Reorder the jobs so that smaller jobs execute first, thereby reducing the waiting time for larger jobs. This is the essence of the Shortest Job First (SJF) algorithm.
But the Shortest Job First has some caveats. Let’s understand them one by one using a question-answer methodology.
Question 1 - When can SJF reduce the average waiting time?
Answer
In all cases except one:
When all jobs require the same amount of time, every ordering results in the same waiting time.
Otherwise, SJF always reduces the average waiting time.
Question 2 - Is there any other scheme that guarantees the shortest average waiting time?
Answer
Currently, none apart from SJF.
SJF is mathematically proven to produce the optimal (minimum possible) average waiting time.
Take-home assignment:
Prove that SJF yields the minimum average waiting time among all deterministic scheduling strategies.
Question 3 - Can we estimate waiting time without knowing the actual value?
Answer
Yes.
We can estimate execution time based on CPU cycles required by the job.
Question 4 - How do we estimate execution time beyond CPU cycles?
Answer
By counting the total number of CPU instructions the job must execute.
Question 5 - How do loops and control statements affect this estimation?
Consider two jobs, J1 and J2, both with:
How do we determine which one will take more time to execute?
Answer
We cannot know without actually running them.
This is fundamentally limited by the Halting Problem -
We cannot predict a program’s exact runtime or behavior in all cases without executing it.
Thus, runtime estimation becomes impossible for arbitrary programs.
Question 6 - Consider a simpler case:
Two jobs J1 and J2 with:
Will they take the same time? or different time? or something else will occur?
Answer
Not guaranteed.
Runtime can differ due to:
Presence of I/O instructions
Location of the file being accessed
Type of storage device (SSD, HDD, tape, RAM disk, etc.)
Storage latency and hardware constraints
In short: CPU instruction count alone is not enough to determine execution time.
Conclusion
If I/O is involved, predicting execution time becomes uncertain.
That means SJF will only be applicable on operations which are very defined for which we know how much time it will take for the job to complete.
That means for general purpose instructions where time taken to complete the job is not defined, SJF will fail.
Therefore. SJF can only be implemented on jobs where time taken to complete is fully defined.
Now for process scheduling we need new algorithm which can satisfy the following cases:
Case 1: It should not be dependent on waiting time of job.
Case 2: The overall performance of the algorithm should not be negatively impacted if a job takes too much time to execute (i.e. the waiting time of a job increases).
Only then can an OS handle general-purpose computing instead of specialized workloads.
Coming Up Next
In the next lecture, we will study the Round Robin (RR) algorithm, its caveats, and approaches to fixing them.
We will then explore how scheduling works in Modern Operating Systems, including:
Feedback loops
Priority queues
Additional Context
Processes often do not know their exact memory requirements in advance. They receive a fixed virtual address space, but must manage it carefully using:
Additionally, the OS may overcommit memory and must use mechanisms like the OOM-Killer to maintain system stability.
The primary goals are:
![Lecture 4 - Rediscovering Process Scheduling [Part - 1]](/_next/image?url=https%3A%2F%2Fcdn.hashnode.com%2Fres%2Fhashnode%2Fimage%2Fupload%2Fv1765604682888%2F80e6cf20-aded-4aac-8c75-affdd35615b2.jpeg&w=3840&q=75)
![[EXPERT] Reflected XSS with AngularJS sandbox escape without strings](/_next/image?url=https%3A%2F%2Fcdn.hashnode.com%2Fuploads%2Fcovers%2F66f6453769132feb8ba076b0%2F111ea636-bcfe-491b-b495-b6549d0ebcfe.png&w=3840&q=75)
