Published on

Types of Scheduling in Operating Systems

Authors
  • avatar
    Name
    Balaram Shiwakoti
    Twitter

Scheduling algorithms were initially confusing during my loksewa preparation because there are so many types, each with different advantages and trade-offs. But once I understood the core principles behind each algorithm, it became much clearer. This is how I finally understood it.

Introduction to honestly, CPU Scheduling

I used to think this was complicated. CPU Scheduling is the process of determining which process gets access to the CPU and for how long. The goal is to maximize CPU utilization while providing good response time and fairness to all processes. Honestly, this took me forever to get.

I've seen this come up in multiple loksewa exams.

Here's how I understand it: Think of CPU scheduling like managing a single-lane bridge where multiple cars (processes) want to cross. Okay, the scheduler decides which car goes first and for how long, trying to minimize waiting time and maximize efficiency.

types of scheduling

1. Listen, first come first serve (fcfs)

principle: processes are executed in the order they arrive in the ready queue.

characteristics: non-preemptive: once a process starts, it runs to completion. simple implementation: uses fifo queue.

  • fair: no process is starved

algorithm:

  1. Process that arrives first gets CPU first
  2. Process runs until completion
  3. Okay, next process in queue gets cpu

example:

processes: p1(24), p2(3), p3(3)
arrival order: p1, p2, p3

gantt chart:
|  p1  |p2|p3|
0     24 27 30

waiting time:
p1: 0, p2: 24, p3: 27
average waiting time: (0+24+27)/3 = 17

advantages:

  • simple to understand and implement no starvation.
  • fair for all processes

disadvantages:

convoy effect: short processes wait for long processes.

  • poor average waiting time not suitable for interactive systems.

2. Shortest Job First (SJF)

Principle: Process with the shortest burst time is executed first.

Types:

  • Non-preemptive SJF: Process runs to completion
  • Preemptive SJF (SRTF): Can be interrupted by shorter process

Non-preemptive SJF Example:

Processes: P1(6), P2(8), P3(7), P4(3)
Arrival Time: All arrive at 0 Honestly, this took me forever to get.

Execution Order: P4(3), P1(6), P3(7), P2(8)

Gantt Chart:
|P4|  P1  | P3  |  P2  |
0  3     9    16     24

Waiting Time:
P4: 0, P1: 3, P3: 9, P2: 16
Average: (0+3+9+16)/4 = 7

Preemptive SJF (SRTF) Example:

Process | Arrival | Burst
P1      | 0       | 8
P2      | 1       | 4  
P3      | 2       | 9
P4      | 3       | 5

Gantt Chart:
|P1|P2  |P4   |P1     |P3         |
0  1    5     10      17          26

Advantages:

Optimal average waiting time. Good for batch systems.

  • Minimizes average turnaround time

Disadvantages:

  • Starvation: Long processes may never execute
  • Requires knowledge of burst time Not practical for interactive systems.

3. Priority Scheduling

Principle: Each process is assigned a priority, and CPU is allocated to the highest priority process.

Types: Non-preemptive: Higher priority process waits for current process to complete.

  • Preemptive: Higher priority process can interrupt current process

Example:

Process | Burst | Priority (lower number = higher priority)
P1      | 10    | 3
P2      | 1     | 1
P3      | 2     | 4  
P4      | 1     | 5
P5      | 5     | 2

Non-preemptive execution order: P2, P5, P1, P3, P4

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

Advantages:

  • Important processes get priority Flexible system.
  • Good for real-time systems

Disadvantages:

Starvation: Low priority processes may never execute.

  • Priority inversion: Low priority process holds resource needed by high priority Complex implementation.

Solution to Starvation:

Aging: Gradually increase priority of waiting processes

4. Round Robin (RR)

Principle: Each process gets a fixed time slice (quantum) in circular order.

Characteristics:

  • Preemptive: Process is interrupted after time quantum
  • Circular queue: Processes arranged in circular fashion Time sharing: Good for interactive systems.

Algorithm:

  1. Assign time quantum (q)
  2. Process executes for q time units
  3. If not finished, move to end of queue
  4. Next process gets CPU

Example:

Processes: P1(24), P2(3), P3(3)
Time Quantum: 4

Gantt Chart:
|P1|P2|P3|P1|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

P2 and P3 complete early, P1 continues

Advantages:

Fair to all processes.

  • Good response time for interactive systems
  • No starvation
  • Preemptive

Disadvantages:

Higher average turnaround time. Context switching overhead.

  • Performance depends on time quantum

Time Quantum Selection:

  • Too small: High context switching overhead Too large: Becomes FCFS.
  • Optimal: Usually 10-100 milliseconds

5. Multilevel Queue Scheduling

Principle: Ready queue is divided into multiple separate queues based on process characteristics.

Queue Categories:

System processes: Highest priority.

  • Interactive processes: High priority Interactive anyway, editing processes: Medium priority.
  • Batch processes: Low priority
  • Student processes: Lowest priority

Characteristics:

Each queue has its own scheduling algorithm. Fixed priority between queues.

  • No process moves between queues

Example Structure:

Queue 1 (System): RR with q=8
Queue 2 (Interactive): RR with q=16  
Queue 3 (Batch): FCFS
``` Don't overthink this one.

### **6. Multilevel Feedback Queue Scheduling**

**Principle**: Similar to multilevel queue but processes can move between queues based on behavior.

#### **Characteristics**:
- **Process migration**: Processes can move up or down queues
- **Aging**: Prevents starvation
**Adaptive**: Adjusts to process behavior.

#### **Example**:

Queue 0: RR with q=8 (highest priority) Queue 1: RR with q=16 (medium priority) Queue 2: FCFS (lowest priority) This was my weak point during prep.

Rules: New processes start in Queue 0.

  • If process uses full quantum, demote to next queue
  • If process finishes early, promote to higher queue

#### **Advantages**:
Adaptive to process behavior.
- Good response time for I/O bound processes
Prevents starvation through aging.

## **Scheduling Criteria**

### **Performance Metrics**:

#### **CPU Utilization**
- Percentage of time CPU is busy
Goal: Keep CPU as busy as possible.

#### **Throughput**
- Number of processes completed per unit time
- Goal: Maximize throughput

#### **Turnaround Time**
Time from submission to completion.
Goal: Minimize turnaround time.

#### **Waiting Time**
- Time spent waiting in ready queue
- Goal: Minimize waiting time

#### **Response Time**
- Time from submission to first response
Goal: Minimize response time (important for interactive systems). Don't overthink this one.

## **Comparison of Scheduling Algorithms**

| Algorithm | Preemptive | Starvation | Complexity | Best For |
|-----------|------------|------------|------------|----------|
| FCFS | No | No | Low | Batch systems |
| SJF | Optional | Yes | Medium | Known burst times |
| Priority | Optional | Yes | Medium | Real-time systems |
| Round Robin | Yes | No | Medium | Interactive systems |
| Multilevel | Yes | Possible | High | Mixed workloads | I found a trick that really works.

## **Real-World Applications**

### **Windows Scheduling**:
Uses multilevel feedback queue.
- 32 priority levels
- Round robin within each level

### **Linux Scheduling**:
Completely Fair Scheduler (CFS).
- Virtual runtime concept
Red-black tree for process selection.

### **Real-Time Systems**:
- Rate Monotonic Scheduling
Earliest Deadline First.

I made flashcards for this - that's how I remembered it.
- Priority-based preemptive scheduling Honestly, this took me forever to get.

## **How I Remembered This Stuff**

- **Key algorithms**: FCFS (simple), SJF (optimal waiting time), RR (fair), Priority (importance-based)
**Preemption**: Can interrupt vs must complete.
**Starvation**: SJF and Priority can starve processes.
- **Metrics**: Know how to calculate waiting time, turnaround time

### **What They Actually Ask in Exams**

During my exam prep, I noticed these questions keep showing up:

1. **"Which scheduling algorithm provides optimal average waiting time?"**
   - Answer: Shortest Job First (SJF)
   - *Tip: This is a key theoretical result*

2. **"What is the main problem with Priority scheduling?"**
   - Answer: Starvation - low priority processes may never execute
   - *Tip: Know the solution too - aging*

3. **"Calculate average waiting time for FCFS with processes P1(24), P2(3), P3(3)"**
   - Answer: (0+24+27)/3 = 17
   - *Tip: Practice these calculations*

4. **"What happens if time quantum is too small in Round Robin?"**
   - Answer: High context switching overhead reduces efficiency
   - *Tip: Know the trade-offs of quantum size*

5. **"Which scheduling algorithm is best for interactive systems?"**
   - Answer: Round Robin or Multilevel Feedback Queue
   - *Tip: Interactive systems need good response time*

**Pro tip from my experience**: When solving scheduling problems, always draw the Gantt chart first. It helps visualize the execution order and makes calculating waiting times much easier. Also, remember that each algorithm optimizes for different goals - FCFS for simplicity, SJF for efficiency, RR for fairness, and Priority for importance.