Explain Priority and Round Robin scheduling algorithm in detail....

Priority and Round Robin Scheduling Explained with Average Waiting Time (OS, CSE, 4th Sem)

What you will learn

How Priority Scheduling and Round Robin Scheduling work
Step-by-step scheduling for a given set of processes
Gantt charts, completion times, turnaround times, and average waiting time
Simple reference implementation (Python) for both algorithms

Given processes (all arrive at t = 0)

Process	Burst Time (μs)	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Assumptions: lower priority number = higher priority; all processes arrive at time 0; Round Robin ready-queue begins in the listed order P1, P2, P3, P4, P5; Time Quantum (RR) = 4 μs.

A. Priority Scheduling (Non-preemptive)

Idea: Always run the highest-priority process next. With all arrivals at t = 0, we simply sort by priority (1 is highest).

Scheduling order by priority: P2 (1) → P5 (2) → P1 (3) → P3 (4) → P4 (5)

Gantt chart (time in μs):

0     1     6           16         18    19
| P2 | P5  |     P1     |   P3     | P4 |

Process	Completion Time (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P2	1	1	0
P5	6	6	1
P1	16	16	6
P3	18	18	16
P4	19	19	18

Average Waiting Time (Priority): (0 + 1 + 6 + 16 + 18) / 5 = 8.2 μs

B. Round Robin Scheduling (Time Quantum = 4 μs)

Idea: Give each ready process a small CPU time slice (quantum). Rotate through the queue; if a process is not finished after its quantum, put it back at the end of the queue.

Initial queue: [P1, P2, P3, P4, P5], all at t = 0

Gantt chart (time in μs):

0         4 5   7 8        12       16 17   19
|   P1    |P2| P3|P4|  P5   |  P1    | P5 | P1 |

Process	Completion Time (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P1	19	19	9
P2	5	5	4
P3	7	7	5
P4	8	8	7
P5	17	17	12

Average Waiting Time (Round Robin, q = 4 μs): (9 + 4 + 5 + 7 + 12) / 5 = 7.4 μs

Key Takeaways

Priority Scheduling favors important jobs first; with these inputs it yields an average waiting time of 8.2 μs.
Round Robin provides fair time sharing; with a 4 μs quantum here it gives a lower average waiting time of 7.4 μs.
The initial ready-queue order and quantum size can affect Round Robin results.

Simple Implementations (Python)

# CPU Scheduling: Priority (non-preemptive) and Round Robin (q = 4 μs)
# Assumes all arrival times = 0

from collections import deque

def priority_non_preemptive(processes):
    """
    processes: list of dicts with keys: pid, burst, priority
    returns: dict with waiting times, completion times, averages
    """
    procs = sorted(processes, key=lambda p: (p["priority"], p["pid"]))
    time = 0
    results = {}
    for p in procs:
        wt = time  # since AT = 0 and no preemption
        ct = time + p["burst"]
        results[p["pid"]] = {
            "CT": ct,
            "TAT": ct,             # AT = 0
            "WT": wt
        }
        time = ct
    avg_wt = sum(r["WT"] for r in results.values()) / len(procs)
    return results, avg_wt

def round_robin(processes, q=4):
    """
    processes: list of dicts with keys: pid, burst
    q: time quantum
    returns: dict with waiting times, completion times, averages
    """
    # Maintain input order for initial ready queue
    rem = {p["pid"]: p["burst"] for p in processes}
    bt = {p["pid"]: p["burst"] for p in processes}
    order = [p["pid"] for p in processes]
    Q = deque(order)
    time = 0
    CT = {}

    while Q:
        pid = Q.popleft()
        if rem[pid] == 0:
            continue
        run = min(q, rem[pid])
        time += run
        rem[pid] -= run
        if rem[pid] == 0:
            CT[pid] = time
        else:
            Q.append(pid)

    results = {}
    for pid in order:
        tat = CT[pid]               # AT = 0
        wt = tat - bt[pid]
        results[pid] = {"CT": CT[pid], "TAT": tat, "WT": wt}
    avg_wt = sum(r["WT"] for r in results.values()) / len(order)
    return results, avg_wt

# Example data
processes = [
    {"pid": "P1", "burst": 10, "priority": 3},
    {"pid": "P2", "burst": 1,  "priority": 1},
    {"pid": "P3", "burst": 2,  "priority": 4},
    {"pid": "P4", "burst": 1,  "priority": 5},
    {"pid": "P5", "burst": 5,  "priority": 2},
]

# Run algorithms
prio_results, prio_avg = priority_non_preemptive(processes)
rr_results, rr_avg = round_robin(processes, q=4)

print("Priority (non-preemptive) average WT:", prio_avg)  # 8.2
print("Round Robin (q=4) average WT:", rr_avg)            # 7.4

Question Answer