๐Ÿค– Process Scheduling Algorithms: A Deep Dive into Preemptive vs. Non-Preemptive

Operating SystemProcess SchedulingPreemptiveNon-preemptiveExam Prep
Read in about 5 min read
Published: 2025-07-13
Last modified: 2025-07-13
View count: 62

Summary

Master the core of operating systems: process scheduling. Understand the principles of preemptive (SRT, Round Robin) and non-preemptive (FIFO, SJF, HRN) algorithms, and sharpen your skills with practice problems on calculating average waiting and turnaround times.

๐Ÿšฆ Why Do We Need Process Scheduling?

A computer needs to handle multiple processes simultaneously. The rule that decides which process gets assigned the CPU is called process scheduling. The goal of scheduling is to use the CPU efficiently, give fair opportunities to all processes, and minimize user waiting time.

Scheduling methods are broadly divided into two types: Non-preemptive and Preemptive.

  • Non-preemptive Scheduling: Once a process is allocated the CPU, no other process can take it away until the process finishes or voluntarily releases the CPU for an I/O operation.
  • Preemptive Scheduling: The operating system can forcibly interrupt the currently running process and allocate the CPU to another process if deemed necessary. This is suitable for time-sharing systems.

๐Ÿ’ก Try calculating the average waiting time and average turnaround time yourself using the example problems provided with each algorithm description below!


๐Ÿšซ Non-preemptive Scheduling

Once allocated, no one can stop it until it's done.

1. FIFO (First-In, First-Out) or FCFS (First-Come, First-Served)

The simplest method, allocating the CPU in the order that processes arrive in the Ready Queue.

  • Pros: Easy to implement and fair.
  • Cons: If a long process arrives first, subsequent short processes have to wait indefinitely, causing the Convoy Effect.

2. SJF (Shortest Job First)

Allocates the CPU to the process with the shortest execution time.

  • Pros: The optimal algorithm for minimizing average waiting time.
  • Cons: Long processes can be indefinitely postponed by new short processes, leading to Starvation. It's also difficult to predict the exact execution time of each process in advance.

3. HRN (Highest Response-ratio Next)

Developed to compensate for the starvation problem of SJF. It dynamically determines priority by considering both waiting time and execution time.

  • Priority Calculation: (Waiting Time + Burst Time) / Burst Time
  • Characteristic: The CPU is allocated to the process with the highest value. As waiting time increases, so does the priority, thus preventing starvation.

4. Deadline

Used in real-time systems where a process must be completed within a given deadline. Processes with the nearest deadline are given higher priority.

5. Priority

The CPU is allocated based on a static priority assigned to each process. The process with the highest priority runs first. Like SJF, it can cause starvation.


๐Ÿ”„ Preemptive Scheduling

A flexible approach that can stop a running process at any time to hand the CPU over to another process.

1. SRT (Shortest Remaining Time)

A preemptive version of the SJF algorithm. If a new process arrives with a shorter execution time than the remaining time of the current process, the CPU is immediately taken away and given to the new process.

  • Pros: Can further reduce average waiting time.
  • Cons: Frequent context switching can cause overhead, and starvation can still occur.

2. Round Robin (RR)

An approach that adds a time quantum (or time slice) to FIFO. Each process uses the CPU for a fixed amount of time, and if the time is up, it moves to the back of the ready queue.

  • Pros: Suitable for interactive systems as all processes are guaranteed fair CPU time.
  • Cons: If the time quantum is too large, it becomes like FIFO. If it's too small, context switching becomes too frequent, increasing overhead. Setting an appropriate time quantum is crucial.

๐Ÿ“ Practice Problems

ProblemWhen the following processes arrive at the ready queue in order, calculate the average waiting time and average turnaround time using SJF (Non-preemptive) scheduling. | Process | Arrival Time | Burst Time | | :--- | :---: | :---: | | P1 | 0 | 6 | | P2 | 1 | 3 | | P3 | 2 | 4 | | P4 | 3 | 2 |
Your Answer
Correct AnswerReveal Answer

Solution (SJF)

  1. Determine Execution Order:

    • Time 0: P1 arrives. Executes (Burst time 6).
    • Since it's non-preemptive, P1 runs to completion (Finish time 6).
    • At time 6: P2, P3, P4 have all arrived. Compare their burst times (P2:3, P3:4, P4:2).
    • P4 executes (Burst time 2, Finish time 8).
    • P2 executes (Burst time 3, Finish time 11).
    • P3 executes (Burst time 4, Finish time 15).
    • Execution Order: P1 -> P4 -> P2 -> P3
  2. Calculate Waiting/Turnaround Time:

    • Turnaround Time = Finish Time - Arrival Time
    • Waiting Time = Turnaround Time - Burst Time
ProcessArrivalBurstFinishTurnaroundWaiting
P106660
P21311107
P32415139
P432853
Total3419
  1. Calculate Average:
    • Average Waiting Time: 19 / 4 = 4.75
    • Average Turnaround Time: 34 / 4 = 8.5
ProblemUnder the same conditions, calculate the average waiting time and average turnaround time using SRT (Preemptive) scheduling.
Your Answer
Correct AnswerReveal Answer

Solution (SRT)

  1. Determine Execution Order (Timeline):

    • 0: P1 arrives. P1 runs (Remaining time 6).
    • 1: P2 arrives (Burst 3). Shorter than P1's remaining time (5), so preempt P1. P2 runs.
    • 2: P3 arrives (Burst 4). Longer than P2's remaining time (2), so P2 continues.
    • 3: P4 arrives (Burst 2). Longer than P2's remaining time (1), so P2 continues.
    • 4: P2 finishes. Remaining processes: P1(5), P3(4), P4(2). P4 runs.
    • 6: P4 finishes. Remaining processes: P1(5), P3(4). P3 runs.
    • 10: P3 finishes. Remaining process: P1(5). P1 runs.
    • 15: P1 finishes.
    • Execution Trace: P1(1) -> P2(3) -> P4(2) -> P3(4) -> P1(5)
  2. Calculate Waiting/Turnaround Time:

    • P1: Finish 15, Arrival 0, Burst 6 -> Turnaround 15, Waiting 9
    • P2: Finish 4, Arrival 1, Burst 3 -> Turnaround 3, Waiting 0
    • P3: Finish 10, Arrival 2, Burst 4 -> Turnaround 8, Waiting 4
    • P4: Finish 6, Arrival 3, Burst 2 -> Turnaround 3, Waiting 1
ProcessArrivalBurstFinishTurnaroundWaiting
P10615159
P213430
P3241084
P432631
Total2914
  1. Calculate Average:
    • Average Waiting Time: 14 / 4 = 3.5
    • Average Turnaround Time: 29 / 4 = 7.25
ProblemUnder the same conditions, calculate the average waiting time and average turnaround time using Round Robin (RR, Time Quantum=2) scheduling.
Your Answer
Correct AnswerReveal Answer

Solution (Round Robin, Quantum=2)

  1. Determine Execution Order (Queue Changes):

    • 0: [P1] -> P1 runs (2)
    • 2: [P2, P3, P1] -> P2 runs (2)
    • 4: [P4, P1, P2] -> P4 runs (2) -> P4 finishes
    • 6: [P1, P2, P3] -> P1 runs (2)
    • 8: [P2, P3, P1] -> P2 runs (1) -> P2 finishes
    • 9: [P3, P1] -> P3 runs (2)
    • 11: [P1, P3] -> P1 runs (2) -> P1 finishes
    • 13: [P3] -> P3 runs (2) -> P3 finishes
    • Finish Order: P4(6) -> P2(9) -> P1(13) -> P3(15)
  2. Calculate Waiting/Turnaround Time:

ProcessArrivalBurstFinishTurnaroundWaiting
P10613137
P213985
P32415139
P432631
Total3722
  1. Calculate Average:
    • Average Waiting Time: 22 / 4 = 5.5
    • Average Turnaround Time: 37 / 4 = 9.25