Process Scheduling in Operating Systems

Process scheduling is a fundamental task performed by the operating system to decide which process should run when multiple processes are ready to execute.

Introduction

The CPU scheduler selects a process from the ready queue and allocates the CPU to it. The goal is to maximize CPU utilization and ensure fair execution of all processes.

Scheduling Criteria

• CPU Utilization: Keep CPU as busy as possible
• Throughput: Number of processes completed per time unit
• Turnaround Time: Time from submission to completion
• Waiting Time: Time spent waiting in ready queue
• Response Time: Time from submission to first response

Types of Scheduling

1. Preemptive Scheduling

The OS can interrupt a running process and switch to another process.

2. Non-Preemptive Scheduling

Once a process starts executing, it runs until completion or blocks.

Scheduling Algorithms

First-Come-First-Served (FCFS)

Processes are executed in the order they arrive.

Advantages:

• Simple to implement
• No starvation

Disadvantages:

• Poor average waiting time
• Not suitable for time-sharing systems

Shortest Job First (SJF)

Process with smallest execution time runs first.

Advantages:

• Optimal average waiting time
• Minimizes waiting time

Disadvantages:

• Difficult to predict execution time
• Can cause starvation

Round Robin (RR)

Each process gets a small time quantum. If not completed, it goes back to ready queue.

Advantages:

• Fair allocation
• Good response time
• No starvation

Disadvantages:

• High overhead due to context switching
• Performance depends on time quantum

Priority Scheduling

Processes are executed based on priority. Higher priority processes run first.

Advantages:

• Important processes get CPU first
• Flexible

Disadvantages:

• Low priority processes may starve
• Priority inversion problem

Multilevel Queue Scheduling

Ready queue is partitioned into separate queues. Each queue has its own scheduling algorithm.

Multilevel Feedback Queue

Similar to multilevel queue, but processes can move between queues based on their behavior.

Real-World Examples

• Linux: Uses Completely Fair Scheduler (CFS)
• Windows: Uses priority-based preemptive scheduling
• Unix: Uses multilevel feedback queue

Performance Comparison

Implementation Considerations

• Context switching overhead
• Load balancing
• Real-time requirements
• Multi-core processors