Operating Systems Lecture 5: Scheduling Policies

Operating System Scheduling Policies

Introduction to Scheduling Policies

• The lecture focuses on various operating system scheduling policies, which are codes that determine which process to run next during a context switch.

• A CPU burst is defined as the continuous duration a process runs on the CPU before it either exits or waits for I/O.

Goals of a Scheduler

• Key goals include maximizing CPU utilization, minimizing turnaround time (the total time from creation to completion), and minimizing response time (time from arrival to first execution).

• Fairness among processes is essential, ensuring all processes eventually get their turn while also minimizing overhead associated with context switching.

First In First Out (FIFO)

• FIFO is the simplest scheduling policy where processes are queued in order of arrival. For example, if processes A, B, and C arrive at T=0, they are scheduled in that order.

• A major drawback of FIFO is the "convoy effect," where shorter processes wait behind longer ones, leading to increased turnaround times.

Shortest Job First (SJF)

• SJF aims to minimize average turnaround time by prioritizing shorter jobs over longer ones. This policy can be optimal but is non-preemptive.

• If a long process starts running before shorter ones arrive, those shorter jobs must wait until the long job completes.

Shortest Remaining Time First (SRTF)

• SRTF is a preemptive version of SJF where if a new short job arrives while a longer job is running, the scheduler will switch to the new short job.

Round Robin Scheduling

• Round Robin involves placing all processes in a queue and executing each for a fixed quantum of time. This method ensures fairness but requires careful management of quantum size.

Understanding Scheduling Policies in Operating Systems

Quantum Timeslice and Round-Robin Scheduling

• Typical quantum timeslice values are around a millisecond, which helps amortize context switching overhead. Round-robin scheduling is beneficial for response time as it allows processes to get their turn without waiting for larger processes to finish.

• In contrast, the shortest job first (SJF) scheduling can lead to high response times for processes B and C, as they must wait longer before execution begins.

• With round-robin, each process gets a small quantum slice almost immediately upon arrival, resulting in significantly reduced response times compared to SJF.

• While round-robin excels in providing good response times, it suffers from poor turnaround time due to the prolonged execution of processes taking turns.

• Each scheduling policy has its strengths; SJF is better for turnaround time while round-robin is preferable for response time. Real-life schedulers often combine multiple policies based on system goals.

Multi-Level Feedback Queues (MLFQ)

• Real-world operating systems like Linux utilize multi-level feedback queues (MLFQ), which consist of multiple queues with varying priority levels. Processes are selected from the highest priority queue available.

• If no processes exist in the highest priority queue, the scheduler moves down to lower priority queues. Within a single priority level, algorithms like round-robin can be applied.

• Priority assignment can vary; new processes may start at high priority but could have their priorities lowered if they consume excessive CPU resources over time.