In this blog, we will learn about process management in Operating System and various related algorithms. Before looking into process management and how it works, let's start with the definition and various aspects of a process.
In simple words, a program in execution is called a process. It is an instance of a program that actually runs, i.e., an entity that can be assigned and executed on a processor. Two essential process elements are program code and a set of data associated with that code.
Process memory is divided into four sections:
Note: Stack and heap sections start at opposite ends of the process free space and grow towards each other. When they meet, stack overflow error will occur or a call to new memory allocation will fail due to insufficient memory available in heap section.
A program executing as a process is uniquely determined by various parameters. These parameters are stored in a Process Control Block (PCB). It is a data structure which holds the following information:
Now, we understood the process, where we defined one parameter of a process called State. Processes in the operating system can be in any of the five states: start, ready, running, wait, and terminated.
Let's understand these states and transition of a process from one state to another state:
Note: Some systems may have other states besides the ones listed here. Explore and think!
Operating system executes various activities in creating a process, which uses a process control block (PCB) to track the execution status of each process.
Process scheduling is critical for selecting and removing running process based on a particular strategy or algorithm. The main objectives of process scheduling are to keep CPU busy and deliver "acceptable" response times for all programs.
Multiprogramming operating systems allow more than one process to be loaded into the executable memory at a time, and loaded process shares CPU using time multiplexing.
Operating system has three types of process schedulers:
Long Term or Job Scheduler: This scheduler job is to bring new process to the Ready state. It determines which process is assigned to CPU for processing, selects processes from the queue, and loads them into memory for execution.
Short Term or CPU Scheduler: It is in charge of selecting one process from the ready state and scheduling it to the running state. They are also known as Dispatchers.
Medium Term Scheduler: It is in charge of swapping processes when a particular process is performing an I/O operation. If a running process makes an I/O request, it may be suspended. A process that has been suspended cannot make any progress toward completion. Suspended process is transferred to secondary storage to remove it from memory and make room for other processes. This is known as switching.
Now our next aim would be to understand CPU Scheduling concept and why we need it.
Both I/O and CPU time is used in a typical procedure. Time spent waiting for I/O in an old operating system like MS-DOS is wasted, and CPU is free during this time. In multiprogramming operating systems, one process can use CPU while another waits for I/O.
CPU Scheduling determines which process will exclusively use CPU while another is paused. The goal is to ensure that whenever CPU is idle, OS chooses at least one of the programs in the ready queue to run. Here CPU scheduler will be in charge of the selection process. It chooses from among the processes in memory that are ready to run.
There are two major types of CPU Scheduling:
Now, we will look at the overview of various scheduling algorithms involved in process management one by one. We will cover each algorithm separately in different blogs.
It is the most basic CPU scheduling algorithm, where a FIFO queue can be used to manage the scheduling strategy. The idea is simple: a process that asks first to get the CPU allocation, get access to the CPU first.
PCB (Process Control Block) of the process is linked to the tail of the queue as it enters the ready queue. As a result, whenever a CPU becomes available, it should be assigned to the process at the front of the queue.
Some important points of this method:
A simple example of this algorithm: Suppose we have five processes p1, p2, p3, p4, and p5, and the ready queue receives them at times t1, t2, t3, t4, and t5 such that t1 < t2 < t3 < t4 < t5. So p1 arrived first in the ready queue, so it will be executed first, followed by p2, p3, p4, and p5, respectively.
Convoy Effect
In FCFS (First Come, First Serve) type of algorithm, if a process with a large CPU burst time arrives before any small process, then the small process will get blocked by that large process, which is called Convoy Effect.
SJF algorithm is a non-preemptive scheduling algorithm. This policy prioritises waiting process with the shortest execution time. Among all scheduling algorithms, Shortest Job First has the advantage of having the shortest average waiting time. It first sorts all processes by arrival time, creates a pool of processes and then chooses the process with the shortest burst times. After completing the process, it again selects the process with the shortest burst time from the pool.
Some important points of this method:
It is further categorized into two types:
A simple example of this algorithm: Suppose we have five processes p1, p2, p3, p4, and p5, and the ready queue receives them at times t1, t2, t3, t4, and t5 such that t1 < t2 < t3 < t4 < t5. Now, you can assume the ready queue as the priority queue, which rearranges the incoming process based on CPU bursts time. Therefore, process with the least CPU burst time is delivered first, and so on.
Longest Job First (LJF) is non-preemptive scheduling. This algorithm keeps track of the burst time of all processes accessible at the moment of arrival and then assigns processor to the process with the longest burst time. In this algorithm, once a process begins to run, it cannot be halted in the middle of its execution.
It organise processes in ascending order of their arrival time. Then, out of all processes that have arrived up to that point, it will choose one with the longest burst time. After that, it will process it throughout the duration of the burst. Until this process completes its execution, LJF monitors if any more processes arrive.
Some important points of this method:
A simple example of this algorithm: Similar to the above example, you can assume here that the same ready queue prioritises based on a larger CPU burst time i.e. out of those five processes, the one with the largest CPU burst time will be executed first.
Round Robin is a CPU scheduling algorithm in which each process is cyclically assigned a set time slot. This looks similar to FCFS scheduling, except that it includes preemption, which allows system to transition between processes. In other words, Round Robin Strategy was created with time-sharing systems in mind.
Each process has a set amount of time assigned to it, and once that time period has passed, process is preempted and another process takes its place. As a result, all processes get an equal amount of CPU time. This algorithm performs best in terms of average response time.
Some important points of this method:
A simple example of this algorithm
Suppose we have five processes p1, p2, p3, p4, and p5, with total execution times of t1, t2, t3, t4, and t5. Now, we have one extra factor, t (a time quanta), which will ensure equal CPU time sharing for each process. Suppose the first process p1 arrives, and after t time of execution, p1 will be preempted and wait for the remaining execution of (t1 — t) time.
At this stage, p1 will move to the wait state, where it can perform its I/O operation. Now CPU is released for the next process, p2. After completing the I/O operation, process p1 is pushed to the ready queue again for its next processing cycle. The data of process p1 will be saved for its execution up till t time so that it can continue from the same state in the next cycle. The same goes for all the processes.
Priority scheduling is one of the most often used priority scheduling methods. Here priority is assigned to each process, and the highest-priority process will be executed first. On a first-come first-served basis, processes of the same priority will be executed. Note: Prioritisation can be determined by memory limitations, time constraints, or other resource constraints.
Priority scheduling does not always set the priority as the inverse of the CPU burst time and memory. Instead, it can be set internally or externally, but the scheduling is done based on process priority.
Some important points of this method:
It is also categorized into two types:
A simple example of this algorithm: Similar to the example of the FCFS algorithm, the processes are inserted in the ready queue but based on a priority now, which can be CPU burst time, memory constraints, etc., and then its execution follows similar to the FCFS algorithm.
Reference: Operating System Concepts by Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin
Thanks to Vishal Das for his contribution to creating the first version of the content. Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.