Types of Scheduling

In operating systems, process scheduling plays a vital role in managing how processes access the CPU and other resources. Different scheduling algorithms are designed to meet various system goals like maximizing CPU utilization, minimizing waiting time, and preventing starvation. Below, we will explore several common types of scheduling algorithms, their characteristics, and their pros and cons.

First Come First Serve (FCFS)​

FCFS schedules processes in the order they arrive in the ready queue. The first process to request the CPU is the first one to receive CPU time.

FCFS is non-preemptive, meaning once a process starts executing, it continues until it either completes or requires I/O. This algorithm is straightforward to implement as it resembles a queue data structure.

Convoy Effect​

The convoy effect occurs when a group of shorter processes is delayed by a longer process at the front of the queue, leading to inefficient CPU utilization and increased waiting times.

Example: Convoy Effect in FCFS

Arrival Time: It is the time at which the process arrived into ready queue.

Burst Time: It is the time that process requires.

Completion Time: It is the time at which the process got completed.

Turn Around Time: It is the total time (TAT - Arrival).

Waiting Time: It is the time for which the process was in ready queue.

The average waiting time here is (0 + 19 + 21) / 3 = 13.33 units. Processes 2 and 3 are short but wait a significant amount of time due to the long first process. This is a typical example of the convoy effect.

Improving the Situation: Reducing Convoy Effect​

Example: No Convoy Effect

Here, the average waiting time is (0 + 2 + 4) / 3 = 2 units, showing better efficiency when short processes are executed before longer ones.

Shortest Job First (SJF)​

SJF is a non-preemptive scheduling algorithm that selects the process with the shortest burst time to execute next.

SJF can help minimize the convoy effect but is challenging to implement because the burst time of a process is not known in advance.

Example: SJF Scheduling

At time = 0, only 1 process was available and hence it started exceuting. Once it completed, the time was 6. At time = 6, all the processes with arrival time less than or equal to 6 were considered. Process with least burst time gets selected.

In this scheduling, the average waiting time is reduced significantly using SJF, but the challenge lies in predicting the burst time.

Shortest Remaining Time First (SRTF)​

SRTF is a preemptive version of SJF where the process with the shortest remaining burst time is given preference.

If a new process arrives with a burst time shorter than the remaining time of the current process, the current process is preempted.

Example: No Convoy Effect in SRTF

In SRTF, the processes are preempted based on remaining burst time, which prevents convoy effects and improves responsiveness. For eg: In above table, P1 starts exceuting. At time = 3, P2 comes and it's Burst time = 20 which is less than P1's burst time (60 - 3 = 57), hence, P2 starts exceuting.

Non-Preemptive Priority Scheduling​

In Non-Preemptive Priority Scheduling, each process is assigned a priority. The process with the highest priority is executed next. If two processes have the same priority, they are scheduled according to arrival order.

This method can cause convoy effects if long, high-priority processes delay shorter, lower-priority ones.

Example: Convoy Effect in Non-Preemptive Priority Scheduling

Average Waiting Time = 10.25 units. Convoy effects can occur due to long, high-priority processes.

Preemptive Priority Scheduling​

Preemptive Priority Scheduling allows a running process to be preempted if a higher-priority process arrives.

Example: Convoy Effect in Preemptive Priority Scheduling

Although preemption helps, convoy effects can still occur if no higher-priority processes interrupt long-running ones.

Problem: Indefinite Waiting (Starvation)​

Indefinite waiting happens when lower-priority processes never get executed because higher-priority ones keep arriving.

Solution: Aging​

Aging increases the priority of a process the longer it waits, ensuring that all processes eventually get CPU time.

Round Robin Scheduling​

Round Robin Scheduling is a preemptive algorithm that assigns a fixed time quantum to each process in the ready queue.

Processes are executed in a cyclic order, which helps ensure no single process monopolizes the CPU.

Example: No Convoy Effect in Round Robin Scheduling

Average Waiting Time = 4.66 units, which is better compared to FCFS. The Gantt chart below shows the sequence of execution:

| P1 | P2 | P3 | P1 | P1 | P1 | P1 |
0    4     7     10   14   18   22   26

Pros​

• Fairness: Ensures all processes get equal CPU time.

• Responsiveness: Reduces response time for each process.

• Simplicity: Easy to implement.

Cons​

• Context Switching Overhead: Frequent context switches can reduce performance.

• Time Quantum Selection: If too short, leads to high overhead; if too long, it acts like FCFS.

Multi-Level Queue Scheduling​

Processes are divided into multiple queues based on their types (e.g., system processes, interactive processes, batch processes), each with its scheduling algorithm.

Example: Different Queues with Different Scheduling

| P1 | P2 | P1 | P2 | P3 | P4 | P4 | P3 |
0    2     4      6     7      9     11    13    20

Drawback​

Lower priority queues may experience starvation if higher priority queues continuously have processes.

Multi-Level Feedback Queue Scheduling​

Similar to multi-level queue scheduling, but processes can move between queues based on their behavior and history.

How MLFQ Works​

• New Processes: Placed in a priority queue based on their nature.

• Execution and Preemption: High-priority queues are executed first. Processes that use up their time slice are moved to lower priority queues.

• Aging and Promotion: Processes that wait too long in lower-priority queues can be promoted to prevent starvation.

• I/O Bound vs. CPU Bound: I/O-bound processes stay in higher-priority queues, while CPU-bound processes move down.

This method adapts dynamically, preventing starvation and optimizing CPU usage.