Operating System
Unit:1
Concept of Process:
A process is defined as a sequence of instructions are executed in a
predefined order. In simple words, any program that is executed is termed as
a process. Processes change its state as it executes and can be either new,
ready, running, waiting or terminated.
A process is an instance of a program running in a computer. It is close in
meaning to task , a term used in some operating systems. In UNIX and some
other operating systems, a process is started when a program is initiated
(either by a user entering a shell command or by another program).
Process states:
• Process goes through different states throughout the life cycle which
are called process states. New, Ready, Running, Waiting or Block,
Terminated or Completed, Suspend ready, and Suspend wait or
blocked are different states which process might go during the life
cycle.
• This model consists of five states i.e, running, ready, blocked, new, and
exit. The model works when any new job/process occurs in the queue,
it is first admitted in the queue after that it goes in the ready state.
Now in the Ready state, the process goes in the running state.
Process Control Block
• A process control block (PCB) contains information about the process,
i.e. registers, quantum, priority, etc. The process table is an array of
PCBs that means logically contains a PCB for all of the current
processes in the system.
• 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.
• Process state – It stores the respective state of the process.
• Process number – Every process is assigned with a unique id known
as process ID or PID which stores the process identifier.
• Program counter – It stores the counter which contains the address
of the next instruction that is to be executed for the process.
• Register – These are the CPU registers which includes: accumulator,
base, registers and general purpose registers.
• Memory limits – This field contains the information about memory
management system used by operating system. This may include the
page tables, segment tables etc.
Open files list – This information includes the list of files opened for
a process
Operating System Scheduling
algorithms
A Process Scheduler schedules different processes to be assigned to the
CPU based on particular scheduling algorithms. There are six popular process
scheduling algorithms which we are going to discuss in this chapter −
First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin(RR) Scheduling
Multiple-Level Queues Scheduling
These algorithms are either non-preemptive or preemptive. Non-
preemptive algorithms are designed so that once a process enters the running
state, it cannot be preempted until it completes its allotted time, whereas the
preemptive scheduling is based on priority where a scheduler may preempt a
low priority running process anytime when a high priority process enters into a
ready state.
First Come First Serve (FCFS)
Jobs are executed on first come, first serve basis.
It is a non-preemptive, pre-emptive scheduling algorithm.
Easy to understand and implement.
Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.
Wait time of each process is as follows −
Proces
Wait Time : Service Time - Arrival Time
s
P0 0-0=0
P1 5-1=4
P2 8-2=6
P3 16 - 3 = 13
Average Wait Time: (0+4+6+13) / 4 = 5.75
Shortest Job Next (SJN)
This is also known as shortest job first, or SJF
This is a non-preemptive, pre-emptive scheduling algorithm.
Best approach to minimize waiting time.
Easy to implement in Batch systems where required CPU time is known
in advance.
Impossible to implement in interactive systems where required CPU
time is not known.
The processer should know in advance how much time process will
take.
Given: Table of processes, and their Arrival time, Execution time
Process Arrival Time Execution Time Service Time
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8
Waiting time of each process is as follows −
Proces
Waiting Time
s
P0 0-0=0
P1 5-1=4
P2 14 - 2 = 12
P3 8-3=5
Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25
Priority Based Scheduling
Priority scheduling is a non-preemptive algorithm and one of the most
common scheduling algorithms in batch systems.
Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
Processes with same priority are executed on first come first served
basis.
Priority can be decided based on memory requirements, time
requirements or any other resource requirement.
Given: Table of processes, and their Arrival time, Execution time, and priority.
Here we are considering 1 is the lowest priority.
Proces Execution Service
Arrival Time Priority
s Time Time
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5
Waiting time of each process is as follows −
Proces
Waiting Time
s
P0 0-0=0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5-3=2
Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6
Shortest Remaining Time
Shortest remaining time (SRT) is the preemptive version of the SJN
algorithm.
The processor is allocated to the job closest to completion but it can be
preempted by a newer ready job with shorter time to completion.
Impossible to implement in interactive systems where required CPU
time is not known.
It is often used in batch environments where short jobs need to give
preference.
Round Robin Scheduling
Round Robin is the preemptive process scheduling algorithm.
Each process is provided a fix time to execute, it is called a quantum.
Once a process is executed for a given time period, it is preempted and
other process executes for a given time period.
Context switching is used to save states of preempted processes.
Wait time of each process is as follows −
Proces
Wait Time : Service Time - Arrival Time
s
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11
Average Wait Time: (9+2+12+11) / 4 = 8.5
Multiple-Level Queues Scheduling
Multiple-level queues are not an independent scheduling algorithm. They
make use of other existing algorithms to group and schedule jobs with
common characteristics.
Multiple queues are maintained for processes with common
characteristics.
Each queue can have its own scheduling algorithms.
Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all I/O-
bound jobs in another queue. The Process Scheduler then alternately selects
jobs from each queue and assigns them to the CPU based on the algorithm
assigned to the queue.
Kickstart Your Career
Get certified by completing the course
