Process Scheduling Policies : Part 1

Imagine you’re the manager of a bustling library, responsible for ensuring that every visitor gets access to the resources they need. Your library has a special reference section with only one seat, and you need to decide which visitor gets to use it and for how long. This scenario is not too different from what an operating system faces when it comes to process scheduling.

In the world of operating systems, processes are like library visitors, each vying for a chance to use the CPU (our metaphorical reference section seat). The operating system, acting as the library manager, needs to make crucial decisions about which process to run and for how long. These decisions are governed by scheduling policies, and today, we’re going to embark on a journey through the fascinating realm of process scheduling.

Pre-requisite : Understanding Processes

Before we dive into scheduling policies, let’s quickly recap what a process is. A process is simply a running program. It’s a dynamic entity that has its own state, uses system resources, and communicates with the operating system through system calls like fork() and exec().

The operating system creates an illusion that each process has its own CPU, even though in reality, multiple processes are sharing the same physical CPU. This illusion is maintained through a mechanism called context switching, where the OS rapidly switches between processes, giving each a slice of CPU time.

Refer my previous article for more in-dept info : The Art of Juggling Processes: Unraveling Process Virtualization Mechanisms

The Scheduling Dilemma

Now, we arrive at our central question: How does the operating system decide which process to run next when it performs a context switch? This is where scheduling policies come into play.

To make informed decisions, a scheduler ideally needs to know:

1. How many processes are waiting to run?
2. What are the characteristics of these processes?
3. How long is each process expected to run?
4. How frequently are new processes arriving?

In our library analogy, this would be equivalent to knowing how many visitors want to use the reference section, what kind of books they want to read, how long they expect to stay, and how often new visitors are coming in.

Workload Assumptions: Simplifying the Problem

To begin our exploration of scheduling policies, let’s start with some simplifying assumptions about our workload:

1. Each process runs for the same amount of time.
2. All processes arrive at the same time.
3. Once a process starts running, it runs to completion.
4. All processes only use the CPU (no I/O operations).
5. The run time of each process is known in advance.

These assumptions might seem unrealistic, but they’ll help us understand the basic principles. We’ll gradually relax these assumptions as we progress.

Measuring Success: Scheduling Metrics

Before we evaluate different scheduling policies, we need to define what makes a good schedule. We’ll use two primary metrics:

1. Turnaround Time: This is the time from when a process arrives until it completes. We calculate it as: Turnaround Time = Completion Time — Arrival Time

1. Fairness: This measures how equitably CPU time is distributed among processes. We can use Jain’s fairness index to quantify this.

It’s important to note that performance and fairness don’t always go hand in hand. Sometimes, we might need to sacrifice one for the other.

First Come, First Served (FCFS): The Simplest Approach

Let’s start with the most straightforward scheduling policy: First Come, First Served (FCFS). As the name suggests, this policy runs processes in the order they arrive.

CS3.301 Operating Systems and Networks, IIIT Hyderabad

Imagine three friends — Whatsapp (W), Skype (S), and Teams (T) — arrive at our library simultaneously, each needing 20 minutes in the reference section.

If they arrived in the order W, T, S, here’s how FCFS would schedule them:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

The average turnaround time would be (20 + 40 + 60) / 3 = 40 minutes.

This seems fair, right? Everyone gets their turn. But what happens if we relax our first assumption and allow processes to have different run times?

Let’s say Whatsapp needs 100 minutes, while Skype and Teams still need 20 minutes each:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

Now our average turnaround time skyrockets to (100 + 120 + 140) / 3 = 120 minutes!

This scenario highlights a significant problem with FCFS: the convoy effect. If a long process comes first, it holds up all the shorter processes behind it, much like being stuck in a grocery store line behind someone with a full cart when you only have one item.

Shortest Job First (SJF): Prioritizing Quick Wins

To address the convoy effect, let’s try a different approach: Shortest Job First (SJF). This policy, borrowed from operations research, prioritizes processes that can be completed quickly.

Using our previous example:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

The average turnaround time improves to (20 + 40 + 140) / 3 = 66.67 minutes, which is way better than 120 mins in FCFS.

But what if processes don’t all arrive at the same time? Let’s say Whatsapp arrives at t=0, and Skype and Teams arrive at t=20:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

SJF would complete Whatsapp before starting the shorter jobs, resulting in an average turnaround time of (100 + 100 + 120) / 3 = 106.67 minutes. We’ve regressed!

Can we do better?

Shortest Time to Completion First (STCF): Adding Preemption

To address the limitation of SJF, we introduce preemption. This new policy, Shortest Time to Completion First (STCF), checks the remaining time for all processes whenever a new process arrives and runs the one that will finish first.

Using our previous example:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

STCF preempts Whatsapp when Skype and Teams arrive, runs these shorter jobs, and then resumes Whatsapp. This improves our average turnaround time to (140 + 20 + 40) / 3 = 66.67 minutes.

Round Robin (RR): Fairness in Time Slices

While STCF optimizes turnaround time, it might not be ideal for interactive processes where responsiveness is crucial. Enter Round Robin (RR) scheduling.

RR runs each process for a small time slice, then switches to the next process in a circular fashion. This approach prioritizes fairness and responsiveness over pure efficiency.

Let’s see how RR works with a time slice of 1 time unit:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

While the turnaround time increases to (13 + 14 + 15) / 3 = 14 time units, the response time (time from arrival to first run) dramatically improves to (0 + 1 + 2) / 3 = 1 time unit.

The choice of time slice is crucial in RR scheduling. Too small, and we waste time on frequent context switches. Too large, and we lose the benefits of responsiveness.

Incorporating I/O: A New Dimension

So far, we’ve assumed processes only use the CPU. But in reality, processes often perform I/O operations. How do we handle this?

When a process initiates an I/O operation, it becomes blocked, waiting for the I/O to complete. The scheduler can use this opportunity to run another process. When the I/O completes, an interrupt is raised, and the process moves from the blocked state to the ready state.

Consider two processes: Microsoft Word (M) performing autosave every 20 seconds (involving I/O), and a C program © doing numerical computations (no I/O).

We can leverage STCF here:

CS3.301 Operating Systems and Networks, IIIT Hyderabad

Policy:

1. CPU is used by one process while the other one uses the disk.
2. Each CPU burst can be treated of as separate job.
3. Better utilization of the processor

Do we miss something?

Unknown Run Times

In all our previous examples, we assumed we knew how long each process would run. But in reality, this information isn’t available. How can we schedule effectively without this crucial piece of information?

This is where more advanced scheduling algorithms come into play, such as the Multi-Level Feedback Queue (MLFQ), which we’ll explore in future articles. These algorithms attempt to learn from the behavior of processes and make intelligent scheduling decisions based on past performance.

Conclusion: The Art of Scheduling

As we’ve seen, process scheduling is a complex balancing act. Different policies optimize for different metrics, and the best choice often depends on the specific requirements of your system.

• FCFS is simple but can lead to the convoy effect.
• SJF optimizes turnaround time but can starve long processes.
• STCF improves on SJF by adding preemption.
• RR prioritizes responsiveness and fairness.

Real-world schedulers often use hybrid approaches, combining elements from multiple policies to achieve the best overall performance.

Remember, there’s no one-size-fits-all solution in scheduling. The art lies in understanding the trade-offs and choosing the right policy (or combination of policies) for your specific needs. As you continue your journey into the world of operating systems, you’ll encounter even more sophisticated scheduling algorithms, each with its own strengths and weaknesses.

Just as a skilled library manager learns to balance the needs of all visitors, a well-designed operating system must artfully manage its processes, ensuring efficient use of resources while maintaining responsiveness and fairness. The journey through process scheduling is a testament to the intricate dance between processes and resources that occurs beneath the surface of every modern computing system.

These articles are inspired by the Operating Systems and Networks (OSN) course taught at IIIT Hyderabad.

List of articles for OS&N :

1. Introduction to Operating systems and Networks
2. Process Virtualization: Creating the Illusion
3. The Art of Juggling Processes: Unraveling Process Virtualization Mechanisms
4. Process Scheduling Policies : Part 1
5. Process Scheduling Policies : Part 2
6. Networking Fundamentals: Connecting Processes Across Machines
7. Understanding Networking from Layers to Sockets

I feel extremely happy sharing all this knowledge and do let me know if this article has helped you.

Thank you for reading, I hope this article helped you

Aditya Raghuvanshi ( IIIT Hyderabad, INDIA )

Connect me on the following :

Github | linkedin | Medium | Gmail : tanalpha.aditya@gmail.com