Types of CPU Scheduling Algorithms

First-Come, First-Served (FCFS): It is one of the simplest CPU scheduling algorithms. It schedules processes in the order they arrive in the Ready queue. The key principle is that the first process to arrive gets executed first, and the CPU will not switch to another process until the current process finishes its execution. It is non-preemptive scheduling. FCFS Scheduling is simple and easy to implement but can lead to issues like the "convoy effect."


The convoy effect describes the phenomenon where a long process (or a process with a heavy burst time) causes a delay for shorter processes that arrive afterward, resulting in increased average waiting time for those shorter processes.
First Image (Long Process First): If a process with a heavy burst time is placed first, it will occupy the CPU for a long period. Shorter processes that arrive afterward will have to wait until the long process is completed, leading to a high average waiting time for the shorter processes.
If the process with the heavy burst time is placed at the end of the queue, shorter processes will be executed first. This reduces their waiting time since they get the CPU sooner. As a result, the average waiting time for all processes is reduced.
Convoy Effect: Long Process First: Causes the shorter processes to wait longer, increasing their average waiting time. Short Process First: Minimizes waiting time for shorter processes and reduces the average waiting time overall.

Shortest Job First algorithm: In this scheduling approach, the job with the smallest burst time is executed first. However, a question arises: how can we determine which job has the shortest burst time before execution, since it’s not practically possible to know this in advance? The operating system tackles this by making an informed guess, using factors like code size, historical data, or other logical indicators to estimate the burst time. These estimates are not always precise, but they provide a rough idea that helps the OS prioritize processes accordingly.
Non-preemptive Shortest Job First (SJF) can fall victim to the convoy effect. For instance, in the above example, (Non-preemptive Shortest Job First algorithm) if the first process in the queue has a burst time of 80 seconds, it would continue executing, preventing other processes from running and causing them to experience significant delays or starvation.
Preemptive SJF avoids the convoy effect because processes with lower burst times are given higher priority. The convoy effect occurs when a long-running job monopolizes the CPU, leading to the starvation of shorter processes (as shown in the above image). The biggest challenge with the Shortest Job First (SJF) algorithm is that it's practically impossible to implement perfectly, as we can't know the exact burst time of a process before execution. 

Priority scheduling: In priority scheduling, the job with the highest priority is executed first, followed by the next highest, and so on. Given below is an example of a non-preemptive version.
From the above image (preemptive version), we can see that the average wait time for the processes is 11.4 units, which is quite high. In fact, its average wait time is greater than that of the non-preemptive version. Additionally, it is susceptible to the convoy effect, as it prioritizes high-priority processes first. If these high-priority processes have long burst times, it can lead to the starvation of lower-priority jobs. Hence the biggest drawback including both preemptive and non-preemptive scheduling is that it causes extreme starvation of low-priority processes. The solution to the starvation problem is aging. Aging involves gradually increasing the priority of lower-priority jobs over time. For example, every 15 seconds, the priority of the lowest-priority job can be increased by +1. This way, the priority of these jobs will slowly rise, ensuring that they eventually get a chance to execute.

Round-Robin Scheduling algorithm:  It is a CPU scheduling algorithm that is designed to manage processes in a fair and time-efficient manner. In this algorithm, each process is assigned a fixed time slot called a time quantum (e.g., 10 milliseconds). The CPU executes each process in the order they arrive, giving each process an equal share of CPU time. If a process doesn't finish its execution within its time quantum, it is moved to the back of the queue to wait for its next turn.  Selecting an appropriate time quantum is crucial; if it's too short, there will be too many context switches; if it's too long, the system behaves like First-Come, First-Served (FCFS). 

























Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more