WikiGalaxy

Personalize

CPU Scheduling Basics

Introduction:

CPU Scheduling is a critical task performed by the operating system to manage the execution of processes. It determines which process runs at any given time, optimizing CPU utilization and ensuring system efficiency.

Process Scheduling: The OS decides the order in which processes access the CPU.
Types of Scheduling: Includes preemptive and non-preemptive scheduling.
Scheduling Criteria: Important criteria include CPU utilization, throughput, turnaround time, waiting time, and response time.

First-Come, First-Served (FCFS)

Concept:

FCFS is a simple scheduling algorithm where the process that arrives first gets executed first. It's easy to implement but can lead to the "convoy effect" where short processes wait for long processes to complete.

Advantages: Simple and easy to implement.
Disadvantages: Can cause long waiting times and is not ideal for time-sharing systems.


Process Arrival Time Burst Time
  P1         0         4
  P2         1         3
  P3         2         1

// Gantt Chart
P1 | P2 | P3
0   4   7   8

Analysis:

In the FCFS example above, the waiting time for each process is calculated based on the order of arrival. While simple, this method can lead to inefficient CPU utilization if a long process blocks shorter ones.

Shortest Job First (SJF)

Concept:

SJF scheduling selects the process with the smallest burst time for execution next. It can be preemptive or non-preemptive and is optimal for minimizing average waiting time.

Advantages: Reduces average waiting time.
Disadvantages: Difficult to predict burst time accurately.


Process Arrival Time Burst Time
  P1         0         6
  P2         1         8
  P3         2         7
  P4         3         3

// Gantt Chart
P1 | P4 | P3 | P2
0   6   9  16  24

Analysis:

In SJF, processes are selected based on their burst times. This example shows how SJF can reduce the average waiting time compared to FCFS, but requires knowledge of future burst times.

Round Robin (RR)

Concept:

Round Robin scheduling assigns a fixed time unit per process and cycles through them. It's designed for time-sharing systems and ensures all processes get CPU time.

Advantages: Fair and prevents starvation.
Disadvantages: Context switching overhead can be high.


Process Arrival Time Burst Time Time Quantum
  P1         0         4         2
  P2         1         5         2
  P3         2         2         2

// Gantt Chart
P1 | P2 | P3 | P1 | P2 | P2
0   2   4   6   8  10  12

Analysis:

The Round Robin example demonstrates how each process receives a time slice, ensuring no process is left waiting indefinitely. The choice of time quantum is crucial for balancing responsiveness and context-switching overhead.

Priority Scheduling

Concept:

Priority scheduling assigns a priority level to each process. The CPU is allocated to the process with the highest priority. This can be preemptive or non-preemptive.

Advantages: Important tasks receive CPU time first.
Disadvantages: Can lead to starvation for low-priority processes.


Process Arrival Time Burst Time Priority
  P1         0         3         2
  P2         1         4         1
  P3         2         1         3

// Gantt Chart
P2 | P1 | P3
0   4   7   8

Analysis:

Priority scheduling effectively handles processes based on importance. However, it requires mechanisms like aging to prevent starvation of low-priority processes.

Multilevel Queue Scheduling

Concept:

Multilevel Queue Scheduling divides the ready queue into several separate queues, each with its own scheduling algorithm. Processes are permanently assigned to one queue based on properties such as memory size, process priority, or process type.

Advantages: Efficient for systems with distinct process types.
Disadvantages: Inflexible as processes are fixed in their queues.


// Example of Multilevel Queue Scheduling
Queue 1: System Processes (RR)
Queue 2: Interactive Processes (Priority)
Queue 3: Batch Processes (FCFS)

// Processes in Queue 2
Process Arrival Time Burst Time Priority
  P1         0         3         1
  P2         1         4         2

// Gantt Chart for Queue 2
P1 | P2
0   3   7

Analysis:

Multilevel Queue Scheduling allows different types of processes to be handled using appropriate algorithms. However, once assigned to a queue, a process cannot move between queues, which can be limiting.

Multilevel Feedback Queue Scheduling

Concept:

Multilevel Feedback Queue Scheduling allows processes to move between queues. This flexibility enables it to adjust to varying process needs and priorities dynamically.

Advantages: Highly flexible and adaptable to process behavior.
Disadvantages: Complex to implement and configure.


// Example of Multilevel Feedback Queue Scheduling
Queue 1: Time Quantum = 8 ms
Queue 2: Time Quantum = 16 ms
Queue 3: FCFS

// Initial Queue Assignment
Process Arrival Time Burst Time
  P1         0         24
  P2         1         3

// Gantt Chart
P1 | P2 | P1
0   8   11  19

Analysis:

This scheduling approach provides flexibility by allowing processes to move between queues based on their execution characteristics. It is suitable for environments where process behavior can change dynamically.

Conclusion

Summary:

CPU Scheduling is essential for optimizing CPU usage and ensuring system performance. Each scheduling algorithm has its strengths and weaknesses, making them suitable for different types of systems and workloads. Understanding these algorithms is crucial for software developers and IT professionals to design efficient systems.

Key Takeaway: Choose the right scheduling algorithm based on system requirements and workload characteristics.