Round Robin

Process Synchronization

Deadlock Handling

Round Robin

Process Scheduling and Synchronization

Round Robin (RR) Scheduling Algorithm is a popular CPU scheduling method used in Operating Systems, especially in time-sharing systems.

What is Round Robin?

Round Robin assigns a fixed time slice called a Time Quantum (TQ) to each process in the ready queue.

Each process gets CPU for a limited time.

If it doesn't finish within that time, it is moved to the end of the queue.

The CPU cycles through processes in a circular (round-robin) manner.

Key Features

Time-sharing: Fair CPU allocation

Pre-emptive: Processes can be interrupted

Fairness: Every process gets equal chance

Working Example

Time Quantum = 2 ms

Process	Burst Time
P1	5
P2	3
P3	1

Execution Order (Gantt Chart)

P1 → P2 → P3 → P1 → P2 → P1

Time flow:

0   2   4   5   7   8   10
|P1|P2|P3|P1|P2|P1|

Advantages

Simple and easy to implement

No starvation (every process gets CPU)

Good response time for interactive systems

Disadvantages

Too small time quantum → many context switches (overhead)

Too large time quantum → behaves like FCFS

 Average waiting time can be high

Where is it used?

Operating systems like Windows, Linux (in modified form)

Time-sharing systems like Unix, Linux

 

Round Robin is a pre-emptive CPU scheduling algorithm where each process gets a fixed time slice called a Time Quantum (TQ).

 

Example

Process	Arrival Time	Burst Time
P1	0	10
P2	1	5
P3	2	8

Time Quantum (TQ) = 3

 

Step-by-Step Execution

We execute processes in a circular queue:

Execution Order:

P1 (0–3) → P2 (3–6) → P3 (6–9) → P1 (9–12) → P2 (12–14) → P3 (14–17) → P1 (17–20) → P3 (20–22)

Gantt Chart

| P1 | P2 | P3 | P1 | P2 | P3 | P1 | P3 |
0    3    6    9    12   14   17   20   22

 

Completion Time (CT)

Process	CT
P1	20
P2	14
P3	22

 

Turnaround Time (TAT)

TAT = CT - Arrival Time

Process	TAT
P1	20 - 0 = 20
P2	14 - 1 = 13
P3	22 - 2 = 20

 

Waiting Time (WT)

WT = TAT - Burst Time

Process	WT
P1	20 - 10 = 10
P2	13 - 5 = 8
P3	20 - 8 = 12

 

Final Results

Average Turnaround Time = (20 + 13 + 20) / 3 = 17.67

Average Waiting Time = (10 + 8 + 12) / 3 = 10

 

Key Points

Each process gets equal CPU time (fair scheduling)

Prevents starvation

Performance depends on Time Quantum:

Too large → behaves like FCFS

Too small → too many context switches

 

Priority Scheduling

Priority Scheduling in Operating System

Priority Scheduling is a CPU scheduling algorithm where each process is assigned a priority, and the CPU is allocated to the process with the highest priority.

What is Priority Scheduling?

Every process has a priority number.

The process with higher priority executes first.

If two processes have the same priority → FCFS (First Come First Serve) is used.

Types of Priority Scheduling

Pre-emptive Priority Scheduling

CPU is taken away if a higher-priority process arrives.

Example: A running process can be interrupted.

Non-Pre-emptive Priority Scheduling

Once a process starts, it runs till completion.

No interruption allowed.

Example

Process	Burst Time	Priority
P1	4	2
P2	3	1
P3	5	3

(Assume: Lower number = Higher priority)

 

Execution Order

P2 (Priority 1) → P1 (Priority 2) → P3 (Priority 3)

 

Gantt Chart

| P2 | P1 | P3 |
0    3    7    12

Priority Scheduling – Example (Step-by-Step)

Given Processes

Process	Arrival Time	Burst Time	Priority
P1	0	4	2
P2	1	3	1
P3	2	5	3

Assumption: Lower number = Higher priority
We’ll use Pre-emptive Priority Scheduling

 

Execution Process

Time 0: Only P1 is available → runs

Time 1: P2 arrives (higher priority than P1) → P1 is pre-empted, P2 runs

Time 2: P3 arrives (lower priority than P2) → P2 continues

Time 4: P2 finishes

Remaining: P1 (priority 2), P3 (priority 3) → P1 runs

After P1 finishes → P3 runs

 

Gantt Chart

| P1 | P2 | P1 | P3 |
0    1    4    7    12

 

Completion Time (CT)

Process	CT
P1	7
P2	4
P3	12

 

Turnaround Time (TAT)

TAT = CT − Arrival Time

Process	TAT
P1	7 − 0 = 7
P2	4 − 1 = 3
P3	12 − 2 = 10

 

Waiting Time (WT)

WT = TAT − Burst Time

Process	WT
P1	7 − 4 = 3
P2	3 − 3 = 0
P3	10 − 5 = 5

 

Final Answer

Average Waiting Time = (3 + 0 + 5) / 3 = 2.67 ms

Average Turnaround Time = (7 + 3 + 10) / 3 = 6.67 ms

 

2 Example of Priority Scheduling

Let’s consider non-pre-emptive priority scheduling (once a process starts, it runs until completion).

Given Processes:

Process	Arrival Time	Burst Time	Priority
P1	0	5	2
P2	1	3	1
P3	2	8	4
P4	3	6	3

 

Assume: Lower number = higher priority

 

Step 1: Execution Order

At time 0 → Only P1 is available → starts execution

At time 5 → P2, P3, P4 are available
→ Highest priority is P2 (priority 1)

Next → P4 (priority 3)

Last → P3 (priority 4)

Execution Order:

P1 → P2 → P4 → P3

 

Step 2: Gantt Chart

| P1 | P2 | P4 | P3 |
0    5    8    14   22

Step 3: Completion Time (CT)

Process	CT
P1	5
P2	8
P4	14
P3	22

 

Step 4: Turnaround Time (TAT)

TAT = CT - Arrival Time

Process	TAT
P1	5 - 0 = 5
P2	8 - 1 = 7
P3	22 - 2 = 20
P4	14 - 3 = 11

Step 5: Waiting Time (WT)

WT = TAT - Burst Time

Process	WT
P1	5 - 5 = 0
P2	7 - 3 = 4
P3	20 - 8 = 12
P4	11 - 6 = 5

 

Final Results

Average Turnaround Time = (5 + 7 + 20 + 11) / 4 = 10.75

Average Waiting Time = (0 + 4 + 12 + 5) / 4 = 5.25

 

Key Points

Priority scheduling can be:

Pre-emptive (higher priority can interrupt)

Non-pre-emptive (runs till completion)

May cause starvation for low-priority processes

Solution: Aging (increase priority over time)

 

Key Understanding

Higher priority process can interrupt lower priority ones

Ensures important tasks run first

May cause starvation (solved by Aging)

 

Advantages

Executes important processes first

Suitable for real-time systems

Flexible scheduling

 

Disadvantages

Starvation: Low-priority processes may never execute

Priority inversion problem

 

Solution to Starvation

Aging Technique (Aging Technique is a method used in operating systems to prevent starvation in CPU scheduling.)
Gradually increases the priority of waiting processes over time

Where is it used?

Real-time operating systems (Airline traffic control systems, multimedia playback)

Task scheduling where priority matters (e.g., system processes)

 

Short Definition (Exam Ready)

Priority Scheduling is a CPU scheduling algorithm in which processes are executed based on their priority, with higher-priority processes served before lower-priority ones.