Scheduling

Overview

Scheduling is a key function of the operating system that manages how tasks (or processes) are allocated CPU time. In a multitasking environment, the OS uses scheduling algorithms to determine the order and time each task receives to ensure efficient CPU usage, fairness, and responsiveness. Effective scheduling improves system performance, balances workloads, and helps prevent issues like process starvation. Different algorithms are suited to different types of tasks, each with unique advantages and disadvantages.

Why Scheduling Is Needed

• Efficient CPU Usage: The CPU can only execute one task at a time. Scheduling maximises CPU use by switching between tasks, allowing for multitasking.
• Fairness: Scheduling ensures that each task receives fair access to the CPU, reducing the risk of any one task monopolising resources.
• Response Time: Good scheduling improves responsiveness, especially for interactive tasks, by giving priority to certain processes as needed.
• Avoiding Starvation: Scheduling algorithms can prevent specific tasks from being ignored indefinitely by ensuring that each task has a chance to execute.

Types of Scheduling Algorithms

Round Robin

• How It Works: Round Robin scheduling allocates a fixed time slice, or quantum, to each task in the queue in a cyclic order. If a task doesn't finish within its time slice, it's moved to the back of the queue.
• Benefits:
  • Fairly allocates CPU time, making it ideal for time-sharing systems.
  • Reduces process starvation, as each task gets a turn.
• Drawbacks:
  • Performance heavily depends on the length of the time slice; too long can cause delays, and too short can lead to frequent context switching, which wastes CPU time.
• Best For: Interactive or time-shared systems where response time is a priority.

First Come, First Served (FCFS)

• How It Works: Tasks are scheduled in the order they arrive. Once a task starts, it runs to completion without interruption.
• Benefits:
  • Simple to implement and easy to understand.
  • Works well for batch processing where tasks don't need quick responses.
• Drawbacks:
  • Convoy effect: A short task may get stuck behind a long one, increasing wait time for subsequent tasks.
• Best For: Batch processing systems where turnaround time isn't critical.

Multi-Level Feedback Queue

• How It Works: Uses multiple queues with different priority levels. Each task starts in a high-priority queue with a short time slice. If a task doesn't finish, it's moved to a lower-priority queue with a longer time slice. The OS can adjust priority levels based on the task's behaviour and requirements.
• Benefits:
  • Highly flexible, as it dynamically adjusts priority levels.
  • Reduces response time for shorter tasks while still accommodating longer ones.
• Drawbacks:
  • Complex to implement and requires more CPU time to manage.
• Best For: Systems that handle a mix of short, interactive tasks and longer, CPU-intensive ones, like general-purpose operating systems.

Shortest Job First (SJF)

• How It Works: SJF schedules tasks based on the shortest estimated execution time. Tasks with shorter durations are prioritised over longer tasks.
• Benefits:
  • Minimises average waiting time, making it efficient for certain workloads.
• Drawbacks:
  • Process starvation can occur if many short tasks keep arriving, delaying longer tasks indefinitely.
  • Requires the OS to know or estimate task duration, which isn't always possible.
• Best For: Batch processing where tasks have predictable and known execution times.

Shortest Remaining Time (SRT)

• How It Works: Similar to SJF, but preemptive. The OS always runs the task with the shortest remaining execution time, and it may switch tasks if a new task with a shorter time arrives.
• Benefits:
  • Minimises waiting time and turnaround time.
• Drawbacks:
  • Starvation of longer tasks is likely if short tasks keep arriving.
  • Higher overhead due to frequent context switching when new tasks arrive.
• Best For: Systems where short tasks should complete quickly, and frequent task switching is acceptable.

Examples

Round Robin

• Suppose three tasks (A, B, and C) each require 10 milliseconds to complete, and the time slice is set to 4 milliseconds.
• Task A runs for 4 ms, then Task B for 4 ms, then Task C, after which the OS returns to Task A to continue.
• This cycle continues until each task is completed.

First Come, First Served (FCFS)

• If Task A arrives first and takes 20 ms, Task B arrives next and takes 5 ms, Task C arrives last and takes 2 ms, FCFS will execute A, then B, then C, causing B and C to wait until A completes.

Multi-Level Feedback Queue

• Task A is a short task and starts in the high-priority queue.
• After completing within its time slice, it exits. Task B is longer and moves down to a lower-priority queue after it uses up its initial time slice.
• Task C enters and stays in a high-priority queue if it's short, while Task B eventually completes in the lower-priority queue.

Shortest Job First (SJF)

• Tasks A, B, and C arrive with execution times of 3 ms, 10 ms, and 2 ms, respectively.
• SJF will schedule Task C (2 ms), then Task A (3 ms), then Task B (10 ms), minimising the average wait time.

Shortest Remaining Time (SRT)

• Suppose Task A needs 6 ms, Task B needs 4 ms, and Task C needs 2 ms.
• If Task A starts first, but Task C arrives with a shorter time, Task C will preempt A, then Task B may preempt based on the shortest remaining time.

Note Summary