CPU Scheduling Algorithms Overview

Study Notes

CPU Scheduling Algorithms

Computer operating systems allocate resources such as memory, input output devices and processing time to tasks through the process of CPU scheduling. Different algorithms have been devised to optimize this allocation based on various performance metrics. Herein we discuss four common CPU scheduling algorithms: First Come First Serve (FCFS), Shortest Job Next (SJN), Priority Scheduling, and Round Robin (RR).

First Come First Serve (FCFS)

First Come First Serve is a simple scheduling algorithm where processes arrive in order of their arrival in the ready queue. It's a non-preemptive policy, meaning once a process begins execution it continues until its completion. While FCFS ensures fairness by serving requests in the order they were received, it has significant drawbacks. For example, it can result in longer waiting times for lower priority jobs, as higher priority jobs may keep pushing them back in line. A good example of an OS using FCFS is Macintosh Finder.

Shortest Job Next (SJN)

Shortest Job Next also known as Shortest Seeking Time is another non-premptive algorithm which serves the process with the shortest possible burst time first. Like FCFS, it's simple and can ensure fairness. However, like FCFS it can lead to unpredictable turnaround times and wait times due to the nature of job arrivals. The main difference between FCFS and SJN lies in the selection criteria; while FCFS serves the process arriving before others, SJN selects the one with the shortest remaining work.

Priority Scheduling

In Priority Scheduling, each task receives a priority value assigned to it from a priority list created by assignments made during task creation. Tasks are executed by assigning CPU run time to the highest priority task available. This preemptive algorithm allows for control over when tasks start executing, ensuring priority is given to more important tasks. However, it lacks a well defined measure for determining priorities, leading to potential misallocations.

Round Robin (RR)

Round Robin is the most widely used CPU scheduling algorithm. It allows multiple processes to share the CPU equally by executing each process for a fixed time unit or quantum. If a process isn't completed within the quantum, it is preempted and the CPU is handed over to the next process. While it can maintain a good level of fairness, RR may increase context switching overhead due to frequent preemption and may not be suitable for tasks with varying burst times.

Multi-Level Queue Scheduling

Multi-Level Queue Scheduling is a combination of different CPU scheduling algorithms. It divides processes into different queues based on their priorities. Each queue is handled by a different scheduling algorithm. This approach allows for customization in serving processes based on their importance. However, it can be complex to implement and may require significant overhead to maintain queue structures.

In conclusion, the choice of CPU scheduling algorithm depends on the system requirements, such as fairness, responsiveness, and efficiency. Each algorithm offers a trade-off between these aspects and must be carefully chosen to suit the specific needs of the system.

Description

Learn about common CPU scheduling algorithms including First Come First Serve (FCFS), Shortest Job Next (SJN), Priority Scheduling, Round Robin (RR), and Multi-Level Queue Scheduling. Understand the characteristics, advantages, and disadvantages of each algorithm to optimize resource allocation in computer operating systems.