Process Management

Concept of Process and process state

Process is basically a program in execution. A process is defined as an entity which represents
the basic unit of work to be implemented in the system. To put it in simple terms, we write
our computer programs in a text file and when we execute this program, it becomes a process
which performs all the tasks mentioned in the program.
Process is a unit of activity characterized by a single sequential thread of execution, a current
state and an associated set of system resources.
A simple example for this, when we write a program in c or c++ and compile it, the compiler
creates s binary code. The original code and binary code are both programs. When we
actually run the binary code, it becomes a process.
 A process is an 'active' entity instead of a program, which is considered a 'passive'
entity.
 A single program can create many processes when run multiple times; for example,
when we open a .exe or binary file multiple times, multiple instances begin (multiple
processes are created).
So now what is program?
A computer program is a collection of instructions that performs a specific task when executed
by a computer. A computer program is usually written by a computer programmer in a
programming language.
For example, here is a simple program written in C programming language –

#include <stdio.h>
int main()
{
printf("Hello, World! \n");
return 0;

}
When we compare a program with a process, we can conclude that a process is a dynamic
instance of a computer program.
What is Thread?
A thread in an operating system is the smallest unit of execution within a process, often called
a “lightweight process.” Unlike a full process, threads share resources such as memory and
files with other threads in the same process, but each thread has its own program counter,
registers, and stack.
Behind the scene of process in memory
A process in memory is divided into several distinct sections, each serving a different purpose.
Here's how a process typically looks in memory.

Stack: The process Stack contains the temporary data such as method/function parameters,
return address and local variables.
Heap: This is dynamically allocated memory to a process during its run time.
Text: This includes the current activity represented by the value of Program Counter and the
contents of the processor's registers.
Data: This section contains the global and static variables.

Process Control Block(PCB)

A process has several important attributes that help the operating system manage and
control it. These attributes are stored in a structure called the Process Control Block.
A Process Control Block (PCB) is a data structure used by the operating system to keep track
of process information and manage execution. It helps the OS monitor and control process
execution.
 Each process is given a unique Process ID (PID) for identification.
 The PCB stores details such as process state, program counter, stack pointer, open
files, and scheduling info.
 During a state transition, the OS updates the PCB with the latest execution data.
 It also includes register values, CPU quantum, and process priority.

 The Process Table is an array of PCBs that maintains information for all active
processes.
Every process has its own unique PCB .
The Process Control Block (PCB) is stored as a part of OS so that normal users can't access.
This is because it holds important information about the process. Some operating systems
place the PCB at the start of the kernel stack for the process, as this is a safe and secure spot.

1) Pointer-It is a stack pointer which is required to be saved when the process is switched
from one state to another to retain the current position of the process.
2) Process ID- Every process is assigned with a unique id known as process ID or PID which
stores the process identifier.
3) Process Sate-It store the respective state of the process.
4) Program Counter-It store the counter which contains the address of the next
instruction that is to be executed for the process.
5) Register-These are the CPU registers which includes accumulator, base registers and
general purpose registers.
6) Memory’s limits-This field contains the information about memory management
system used by operating system. This may include the page tables, segment tables
etc.
7) Open files-this information includes the list of files opened for a process.
All of the above attribute of process are called context of the process.

Process Transition Diagram

New

1. New State- A program becomes a process when the OS creates a Process Control Block for
it. At this point, the process is in the New (Created) state. The OS has allocated a PCB
entry, assigned a process ID, and reserved some resources.
2. Ready-The process is loaded into main memory and waiting for CPU allocation.
3. Running-The process instructions are being executed by the CPU.
4. Wait-When a process request I/O access.
5. Complete-If the process execution is completed.
6. Suspended Ready-The process is ready to run (no I/O wait), but it has been swapped
out of main memory and placed in secondary storage.
7. Suspended Block-The process is waiting for an event (like I/O), and it has also been
swapped out of main memory.
Context Switching
Context switching is the process where the CPU stops running one process, saves its current
state, and loads the saved state of another process so that multiple processes can share the
CPU effectively.
It is like loading and unloading the process from running state to ready state.
Context switch happen when-
 When a high-priority process comes to a ready state (i.e. with higher priority than the
running process).
 An Interrupt occurs.

 User and kernel-mode switch

 Pre-emptive CPU scheduling is used.
Process Scheduling
The OS activity that removes a running process from the CPU and selects another process
based on a scheduling strategy.
The goal of process scheduling is to keep CPU busy all time and deliver minimum response
time for all the programs .
It determine which process is in the ready state and which should be move to running state.
Categories of Scheduling:
1. Non-preemptive: Here the resource cant be taken from a process until the process
completes execution. The switching of resources occurs when the running process
terminates and moves to a waiting state.
2. Preemptive: Here the OS allocates the resources to a process for a fixed amount of
time. During resource allocation, the process switches from running state to ready
state or from waiting state to ready state. This switching occurs as the CPU may give
priority to other processes and replace the process with higher priority with the
running process.

Scheduling Queues
Scheduling queues are OS data structures that manage process states—Job, Ready,
and Device—to optimize CPU utilization. They organize processes waiting for resources,
allowing the scheduler to select the next process to run based on priority or state (e.g., waiting
for I/O vs. ready to execute), ensuring efficient multitasking.

Queues help track the sequence of scheduling in operating systems. All processes of the same
execution state are placed in the same queue. Hence, after every execution, a PCB changes its
queue. There are three types of Process scheduling queues that aid scheduling in Operating
Systems-

 Job Queue- Any process that is created is placed in this queue. It stores the most
number of the processes in the system. This queue is known as the job queue, it
contains all the processes or jobs in the list that are waiting to be processed. Job: When
a job is created, it goes into the job queue and waits until it is ready for processing.
Contains all submitted jobs. Processes are stored here in a wait state until they are
ready to go to the execution stage. This is the first and most basic state that acts as a
default storage of new jobs added to a scheduling system. “Long Term Scheduler” picks
a process from Job Queue and moves to ready queue.
 Ready Queue-Processes ready for execution are stored in this queue. All processes
stored in the memory can be found on this queue. The Stand-by queue contains all the
processes ready to be fetched from the memory, for execution. When the process is initiated,
it joins the ready queue to wait for the CPU to be free. The operating system assigns a process
to the executing processor from this queue based on the scheduling algorithm it implements.
Contains processes (mainly their PCBs) waiting for the CPU to execute various
processes it contains. They are controlled using a scheduling algorithm like FCFS, SJF,
or Priority Scheduling “Short Term Scheduler” picks a process from Ready Queue and
moves the selected process to running state.
 Device Queue-This queue stores the processes whose execution is temporarily
suspended due to the requirement of I/O devices.

Process Scheduler
The process scheduler is a part of the operating system that decides which process runs at a
certain point in time. It usually has the ability to pause a running process, move it to the
back of the running queue and start a new process; such a scheduler is known as
a preemptive scheduler, otherwise it is non -preemptive scheduler.
There are three types of process scheduler-
1. Long term scheduler-It bring new process to the ready state. It control degree of
multiprogramming i.e. number of process present in the ready state at any point of
time. It is also called as job scheduler. A long-term scheduler determines which
programs are admitted to the system for processing. It selects processes from the
queue and loads them into memory for execution. Process loads into the memory for
CPU scheduling. The primary objective of the job scheduler is to provide a balanced
mix of jobs, such as I/O bound and processor bound.
 Long-term schedulers decide and control how many processes enter the system for
execution.
 It decides which jobs are to be loaded inside the system memory from the disk.
 It works at a low pace and runs when a job enters the CPU or ready state.
 It generally takes into account long term processes i,e. User jobs or batch processes.
 It affects the degree of multiprogramming inside the CPU and manages processes
between secondary storage and main memory.
 It helps in balancing the CPU Bound and I/O bound processes and helps in optimizing
system performance.

2. Short term scheduler-It is also called as CPU scheduler. Its main objective is to
increase system performance in accordance with the chosen set of criteria. It is the
change of ready state to running state of the process. CPU scheduler selects a process
among the processes that are ready to execute and allocates CPU to one of them.
Short-term schedulers, also known as dispatchers, make the decision of which process
to execute next. Short-term schedulers are faster than long-term schedulers.
 Frequently selects the next process to execute from the ready state.
 Ensures no process suffers from starvation.
 Uses various CPU scheduling algorithms to decide process order.
 Maximizes CPU utilization by keeping the processor as busy as possible.
 Calls the dispatcher, which performs the actual context switch.
 It is the fastest scheduler, since it operates very frequently (often every few
milliseconds).

Dispatcher- The dispatcher is responsible for loading the process selected by the
Short-term scheduler on the CPU (Ready to Running State). Context switching is done
by the dispatcher only. A dispatcher does the following work:
 Saving context of previously running process if not finished.
 Switching system mode to user mode.
 Jumping to the proper location in the newly loaded program.
Time taken by dispatcher is called dispatch latency or process context switch time.
 3. Medium term scheduler-The Medium-Term Scheduler (MTS) manages swapping,
which temporarily moves processes between main memory and disk. It removes the
processes from the memory. It reduces the degree of multiprogramming. The
medium-term scheduler is in-charge of handling the swapped out-processes.
 Swaps processes out of memory when they are waiting (e.g., blocked for I/O) to
reduce the degree of multiprogramming.
 Frees memory for other active processes.
 Swaps processes back into memory when they are ready to continue execution,
allowing them to resume from where they left off.
 Helps maintain an effective mix of CPU-bound and I/O-bound processes.
 It operates faster than the long-term scheduler but slower than the short-term
scheduler.
Scheduling Criteria-
1. CPU utilization: The main objective of any CPU scheduling algorithm is to keep the
CPU as busy as possible. Theoretically, CPU utilization can range from 0 to 100 but in
a real-time system, it varies from 40 to 90 percent depending on the load upon the
system.
2. Throughput: A measure of the work done by the CPU is the number of processes
being executed and completed per unit of time. This is called throughput. The
throughput may vary depending on the length or duration of the processes.
3. Turnaround Time: For a particular process, an important criterion is how long it
takes to execute that process. The time elapsed from the time of submission of a
process to the time of completion is known as the turnaround time. Turn-around
time is the sum of times spent waiting to get into memory, waiting in the ready
queue, executing in CPU and waiting for I/O.
Turn Around Time = Completion Time - Arrival Time.
4. Waiting Time: A scheduling algorithm does not affect the time required to
complete the process once it starts execution. It only affects the waiting time of a
process i.e. time spent by a process waiting in the ready queue.
Waiting Time = Turnaround Time - Burst Time.
5. Response Time: In an interactive system, turn-around time is not the best
criterion. A process may produce some output fairly early and continue computing
new results while previous results are being output to the user. Thus another
criterion is the time taken from submission of the process of the request until the
first response is produced. This measure is called response time.
Response Time = CPU Allocation Time(when the CPU was allocated for the first) -
Arrival Time
6. Completion Time: The completion time is the time when the process stops
executing, which means that the process has completed its burst time and is
completely executed.
Objective of Scheduling algorithms-
 Max CPU utilization
 Fair allocation of CPU
 Max throughput
 Min turnaround time
  Min response time
 Min waiting time

Scheduling Algorithms

Non – Primitive Scheduling Algorithm-

1 First come first serve(FCFS)
It simply queues processes in the order that they arrived in the ready queue.
Processes that come first will be executed first and next process starts only after the
previous one get fully executed
Arriving time of all process could be same or different.
Advantages-
 It is simple and easy to understand.
 It can be easily implemented using queue data structure.
 It does not lead to starvation.
Disadvantages-

 It does not consider the priority or burst time of the processes.

 It suffers from convoy effect.
Convoy effect-Consider processes with higher burst time arrived before the processes
with smaller burst time. Then, smaller processes have to wait for a long time for longer
processes to release the CPU.
Example-
Consider the set of 5 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn
around time.
Solution- We need to create a Gantt chart to solve this problem using fcfs algorithm.

A Gantt chart is a horizontal bar chart used to represent operating systems CPU
scheduling in graphical view that help to plan, coordinate and track specific CPU
utilization factor like throughput, waiting time, turnaround time etc.
 Here the exit time is completion time only

2 Shortes job first – It select the waiting process with smallest execution time. SJF is non pre-
emptive and there is pre-emptive SJF known as shortest remaining time first.

Advantages-
 SRTF is optimal and guarantees the minimum average waiting time.
 It provides a standard for other algorithms since no other algorithm performs better
than it.
Disadvantages-
 It can not be implemented practically since burst time of the processes can not be
known in advance.
 It leads to starvation for processes with larger burst time.
  Priorities can not be set for the processes.
 Processes with larger burst time have poor response time.

Example-

If the CPU scheduling policy is SJF non preemtivie, calculate the average waiting time
and average turn around time.
Solution-Grantt Chart

Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit

Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

Preemptive Scheduling Algorithm

1 Round Robin-
 CPU is assigned to the process on the basis of FCFS for a fixed amount of time.
 This fixed amount of time is called as time quantum or time slice.

 After the time quantum expires, the running process is preempted and sent to the
ready queue.

 Then, the processor is assigned to the next arrived process.

 It is always preemptive in nature.
Implementation OF Round Robin

Advantages-

 It gives the best performance in terms of average response time.

 It is best suited for time sharing system, client server architecture and interactive
system.
Disadvantages

 It leads to starvation for processes with larger burst time as they have to repeat the
cycle many times.

 Its performance heavily depends on time quantum.

 Priorities can not be set for the processes.
Example-
  Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit

 Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit

[Link] Algorithm-
A priority is associated with each process and CPU is allocated the process with highest
priority. It can be either preemptive or non preemptive.
Implementation

 Compare the priority of running process with the newly arrived one in ready queue.
 Pre-emption occur when the newly arrived process have higher priority
  A non preemptive priority schedule algorithm will simply put the new process at the
head of ready queue.
Advantages-
 It considers the priority of the processes and allows the important processes to run
first.
 Priority scheduling in preemptive mode is best suited for real time operating system.
Disadvantages-
 Processes with lesser priority may starve for CPU.

 There is no idea of response time and waiting time.

Note- Priority scheduling in preemptive and non-preemptive mode behaves exactly same
under following conditions-
 The arrival time of all the processes is same
 All the processes become available

Example

If the CPU scheduling policy is priority non-preemptive, calculate the average waiting time
and average turn around time. (Higher number represents higher priority)
Solution-
  Average Turn Around time = (4 + 14 + 10 + 6 + 7) / 5 = 41 / 5 = 8.2 unit
 Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit

[Link] remaining time first-

Shortest Remaining Time First (SRTF) is a preemptive CPU scheduling algorithm that selects
the process with the smallest remaining burst time to execute next. It minimizes average
waiting time by prioritizing shorter jobs, allowing new, faster tasks to preempt currently
running ones.

Implementation of SRTF Algorithm

Step 1: Input number of processes with arrival time and burst time.
Step 2: Initialize remaining times (burst times), current time = 0, and counters.
Step 3: At each time unit, add processes that have arrived into the ready queue.
Step 4: Select the process with the shortest remaining time (preempt if a shorter one
arrives).
Step 5: Execute the selected process for 1 unit, reduce its remaining time, and increment
current time.
Step 6: If a process completes:
 Turnaround Time = Completion Time − Arrival Time

 Waiting Time = Turnaround Time − Burst Time

Step 7: Repeat Steps 3–6 until all processes complete.
Step 8: Calculate average waiting time and turnaround time.
Step 9: Display completion, waiting, and turnaround times for each process, along with
averages.

Example-
Compute average waiting time and turn around time using SRTF algorithm.
Solution-

 Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit

 Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

Multilevel Queue Scheduling

In multilevel queue scheduling, the processes are divided into separate categories, where
category has its own distinct characteristics. In most systems, there are three types of
processes, the system processes, the foreground processes and the background processes.
The system processes are of the highest priority and need immediate attention. The
foreground processes are user processes that are interactive in nature; while the background
processes are batch processes. Since, the different categories require different response time
and priorities, they require different scheduling algorithms.
From the above diagram we find that the ready queue which is partitioned into several
separate queues each having its own characteristics and scheduling technique. When a
process enters the system, it is permanently assigned to one of the queues according to its
priority, memory size or response time. This partitioned ready queue is called multilevel
queue.

Each queue in the multilevel queue has a different scheduling algorithm. Generally, system
queue is scheduled using Preemptive Priority Scheduling; foreground queue is scheduled by
Round Robin scheduling and background queue is scheduled by First Come First Serve
scheduling.
Working of Multilevel Queue

Let there be n queues numbered from 1 to n having priorities from 1 to n. Each process is
permanently assigned to one of these queues. A queue enjoys absolute priority over the
queues having lower priorities. Each queue has its own scheduling strategy. At first, queue 1
with priority 1 is checked. If there are processes in it, they execute according to the scheduling
strategy of queue 1.
If there are no processes in it, then queue 2 is checked. If it has processes, then they are
scheduled according to its scheduling algorithm. This continues up to queue n. Thus a process
in queue x can gain access to CPU only if queue 1 to queue (x-1) are empty. If a process, say
P5, at queue x is executing and a new process, say P16, arrives at a queue having higher
priority, P16 immediately pre-empts P5 and starts to execute.
Features of Multilevel Queue Scheduling
 Multilevel Queues − The very essence of MLQ scheduling is a number of queues each
with their own priorities and response times.
 Preemption between Queues − In MLQ, when a process in a high priority queue
enters the system, it can pre-empt a running process belonging to a low priority
queue.
 Different Scheduling Strategies for Different Queues − Each of the different queues
is associated with a different scheduling strategy depending upon the characteristics
of the processes in it.
  Customized Scheduling − There are no hard and fast rules about the number of
queues to be included and assignment of their relative priorities. This paves way for
customized scheduling according to the needs of the system.
 Development of New Strategies − MLQ is basically a concept from which new
scheduling strategies may be developed. This allows researches on scheduling. With
the ever-changing scenario of process management and development of new
operating systems, scheduling strategies need to be updated. Also, no single
scheduling algorithm can cater to needs of all the processes. MLQ provides the basis
for combining different algorithms in the new systems.
Limitations of Multilevel Queue Scheduling

 A process in a low priority queue may face undefined starvation if there are many high
priority queues each having steady streams of processes. This is the main drawback of
MLQ.

 Implementation of MLQ is inherently complex. It requires proper design and

development, failing which the entire scheduling mechanism may break down.

 Assigning fixed priorities to processes makes MLQ an inflexible strategy.

 The scheduling is too much dependent on the fixed priorities, which are assigned as
soon as a process enters the system. Faulty assignment of process priorities hampers
performance in big way.

Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue Scheduling is a modification of Multilevel Queue Scheduling that
successfully overcomes the problem of starvation. It assigns the priorities dynamically to the
processes based upon their execution behaviours. Initially, all processes are assigned to the
highest priority queue. If a process takes more than the required time slot, it is demoted down
to the next priority queue. Conversely, if a process stays too long in a low priority queue, it is
promoted to a higher priority queue.