Skip to content

Scheduling Algorithms

1.2.1 Systems software · Paper 1 · 6 flashcards · 1 question

Definition
Scheduling is the method by which an OS decides which processes receive CPU time and in what order. Different scheduling algorithms offer various strategies to ensure fairness and efficiency.

Round Robin

Definition
Each process is assigned a fixed time slice (quantum), rotating through the queue until each process is complete. Fair but may lead to longer completion times for some processes.

First Come First Served (FCFS)

Definition
Processes are executed in the order they arrive. Simple but can lead to inefficiencies, especially if long processes block shorter ones (convoy effect).

Shortest Job First (SJF)

Definition
Executes the shortest processes first, minimizing overall waiting time but requiring knowledge of job lengths in advance.

Shortest Remaining Time (SRT)

Definition
Similar to SJF but considers the remaining execution time, allowing the CPU to switch to shorter tasks as they arrive (preemptive).

Multi-Level Feedback Queues

Definition
Uses multiple queues with different priority levels, dynamically adjusting a process's priority based on its behavior and execution time.
Key Point
Round Robin
• Type: Preemptive
• Pros: Fair, good response time
• Cons: Context switch overhead

FCFS
• Type: Non-preemptive
• Pros: Simple, no starvation
• Cons: Convoy effect, poor for short jobs

SJF
• Type: Non-preemptive
• Pros: Optimal average waiting time
• Cons: Starvation of long jobs

SRT
• Type: Preemptive
• Pros: Responsive to short jobs
• Cons: High context switch overhead

Multi-Level
• Type: Adaptive
• Pros: Balances response and throughput
• Cons: Complex to implement