Operating

System
CH. 4 Services
BY DR. VEEJYA KUMBHAR
“UNIX is basically a simple operating system, but you
have to be a genius to understand the simplicity.”

Dennis Ritchie
(1941–2011)
 5 W’s of Unix Operating System
What – Unix is first multiuser, multitasking and
multithreading operating system.
When – Developed in 1969.
Where – @ AT&T’s Bell Laboratory, USA.
Who – By Dennis Richie, Kenneth Thompson
Why – to develop the operating system
designed to run on computers of all
sizes, making open systems possible.
 Ch. 4 Operating System Services
Syllabus

• Processes
• Process Structure
• Process Scheduling
• Scheduling Algorithms
• Process Synchronization & Deadlocks
• Thread Management
• Memory Management
• System Calls
• File System
 Process

Definitions:
 A process is basically a program in execution.
 The process is not as same as program code but a lot more than it.
 A process is an 'active' entity as opposed to the program which is considered
to be a 'passive' entity.
 Attributes held by the process include hardware state, memory, CPU, etc.
 E.g. .c, .cpp, .java , .py are the programs. When we double click on .exe or
type as ./a.out…the code gets occupied by some space in memory.
 Process Vs Program
Process Program
A Program is basically a collection of
The process is basically an instance of
instructions that mainly performs a
the computer program that is being
specific task when executed by the
executed.
computer.
A process has a shorter lifetime. A Program has a longer lifetime.
A Process requires resources such as A Program is stored by hard-disk and
memory, CPU, Input-Output devices. does not require any resources.
A process has a dynamic instance of A Program has static code and static
code and data data.
Basically, a process is the running On the other hand, the program is
instance of the code. the executable code.
 Process States

States of Process: A process is in one of the following states:

1. New: Newly Created Process (or) being-created process.

2. Ready: After creation process moves to Ready state, i.e. the
process is ready for execution.
3. Run: Currently running process in CPU (only one process at a time
can be under execution in a single processor).
4. Wait (or Block): When a process requests I/O access.
5. Complete (or Terminated): The process completed its execution.
6. Suspended Ready: When the ready queue becomes full, some processes
are moved to suspended ready state
7. Suspended Block: When waiting queue becomes full.
 Context Switch

The process of saving the context of one process and

loading the context of another process is known as Context
Switching.

In simple terms, it is like loading and unloading the process

from the running state to the ready state.
 When does context switching happen?

1. When a high-priority process comes to a ready state (i.e.

with higher priority than the running process)
2. An Interrupt occurs
3. User and kernel-mode switch
4. Preemptive CPU scheduling used ( Time Run Out-TRO).
 Context Switch vs Mode Switch:

A mode switch occurs when the CPU privilege level is changed, for example
when a system call is made, or a fault occurs.
The kernel works in more a privileged mode than a standard user task.
If a user process wants to access things that are only accessible to the kernel,
a mode switch must occur.
The currently executing process need not be changed during a mode switch.
A mode switch typically occurs for a process context switch to occur.
Only the kernel can cause a context switch.
 CPU-Bound vs I/O-Bound Processes

A CPU-bound process requires more CPU time or spends more time in the
running state.

An I/O-bound process requires more I/O time and less CPU time.

An I/O-bound process spends more time in the waiting state.

 Ch. 4 Operating System Services
Syllabus

• Processes ✓
• Process Structure
• Process Scheduling
• Scheduling Algorithms
• Process Synchronization & Deadlocks
• Thread Management
• Memory Management
• System Calls
• File System
Process Structure
 Process Structure

Process memory is divided into four sections for efficient working :

The Text section is made up of the compiled program code,
read in from non-volatile storage when the program is
launched.
The Data section is made up of the global and static variables,
allocated and initialized prior to executing the main.
The Heap is used for the dynamic memory allocation and is
managed via calls to new, delete, malloc, free, etc.
The Stack is used for local variables. Space on the stack is
reserved for local variables when they are declared.
 Process Control Block
There is a Process Control Block for each process, enclosing all the information
about the process. It is also known as the task control block.
It is a data structure, which contains the following:
•Process State : It can be running, waiting, etc.
•Process ID and the parent process ID.
•CPU registers and Program Counter - CPU register holds the registers required by
the program and Program Counter holds the address of the next instruction to be
executed for that process.
•CPU Scheduling information: Such as priority information and pointers to
scheduling queues.
•Memory Management information: For example, page tables or segment tables.
•Accounting information: The User and kernel CPU time consumed, account
numbers, limits, etc.
 Process Control Block

•I/O Status information: Devices allocated, open file tables, etc.

 Ch. 4 Operating System Services
Syllabus

• Processes ✓
• Process Structure ✓
• Process Scheduling
• Scheduling Algorithms
• Process Synchronization & Deadlocks
• Thread Management
• Memory Management
• System Calls
• File System
 Multiprogramming

Multiprogramming – We have many processes ready to run.

There are two types of multiprogramming:
1.Pre-emption – Process is forcefully removed from CPU.
Pre-emption is also called as time sharing or multitasking.
1.Non pre-emption – Processes are not removed until they complete the
execution.
Degree of multiprogramming – The number of processes that can reside in the
ready state at maximum decides the degree of multiprogramming,
e.g., if the degree of programming = 100, this means 100 processes can reside in
the ready state at maximum.
 Process Scheduling

➢ When there are two or more runnable processes then it is decided by the Operating
system which one to run first then it is referred to as Process Scheduling.
➢ A scheduler is used to make decisions by using some scheduling algorithm.
➢ Given below are the properties of a Good Scheduling Algorithm:
• Response time should be minimum for the users.
• The number of jobs processed per hour should be maximum i.e Good
scheduling algorithm should give maximum throughput.
• The utilization of the CPU should be 100%.
• Each process should get a fair share of the CPU.
 Process Scheduling

 Process scheduling is the activity of the process manager that handles the removal of
the running process from the CPU and the selection of another process based on a
particular strategy.
 Process scheduling is an essential part of a Multiprogramming operating system.
 Such operating systems allow more than one process to be loaded into the executable
memory at a time and the loaded process shares the CPU using time multiplexing.
 • All processes, upon entering into the system, are stored in the Job
Queue.
Scheduling Queues
• Processes in the Ready state are placed in the Ready Queue.
• Processes waiting for a device to become available are placed in Device
Queues. There are unique device queues available for each I/O device.
• A new process is initially put in the Ready queue. It waits in the ready
queue until it is selected for execution(or dispatched).
• Once the process is assigned to the CPU and is executing, one of the
following several events can occur:
• The process could issue an I/O request, and then be placed in the I/O queue.
• The process could create a new subprocess and wait for its termination.
• The process could be removed forcibly from the CPU, as a result of an interrupt,
and be put back in the ready queue.
In the first two cases, the process eventually switches from the waiting state to the ready state, and is then put back in the
ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB
and resources deallocated.
 Types of Schedulers:

1. Long term – performance – Decides about how many processes should be made to stay in
the ready state, this decides the degree of multiprogramming. Once a decision is taken it
lasts for a long time hence called long term scheduler.
2. Short term – Context switching time – Short term scheduler will decide which process to
be executed next and then it will call dispatcher. A dispatcher is a software that moves
process from ready to run and vice versa. In other words, it is context switching.
3. Medium term – Swapping time – Suspension decision is taken by medium term scheduler.
Medium term scheduler is used for swapping that is moving the process from main
memory to secondary and vice versa.
 Long Term or job scheduler:

➢ It brings the new process to the ‘Ready State’.

➢ It controls the Degree of Multi-programming, i.e., the number of processes
present in a ready state at any point in time.
➢ It is important that the long-term scheduler make a careful selection of both I/O
and CPU-bound processes.
➢ I/O-bound tasks are which use much of their time in input and output
operations while CPU-bound processes are which spend their time on the CPU.
➢ The job scheduler increases efficiency by maintaining a balance between the
two.
➢ They operate at a high level and are typically used in batch-processing systems.
 Long Term
Schedular

Long Term
Schedular
 Short-term or CPU scheduler:

It is responsible for selecting one process from the ready state for
scheduling it on the running state.
Note:
• Short-term scheduler only selects the process to schedule it doesn’t
load the process on running.
• The CPU scheduler is responsible for ensuring there is no starvation
owing to high burst time processes.
 Short-term or CPU scheduler:

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:

1. Switching context.
2. Switching to user mode.
3. Jumping to the proper location in the newly loaded program.
 Short Term
Schedular

Dispatcher

Dispatcher
 Medium-term scheduler:

❑ It is responsible for suspending and resuming the process.

❑ It mainly does swapping (moving processes from main memory to disk and
vice versa).
❑ Swapping may be necessary to improve the process mix or because a change
in memory requirements has overcommitted available memory, requiring
memory to be freed up.
❑ It is helpful in maintaining a perfect balance between the I/O bound and the
CPU bound.
❑ It reduces the degree of multiprogramming.
 Medium Term
Schedular
Medium Term
Schedular
 Other Schedulers

 I/O schedulers: I/O schedulers are in-charge of managing the execution

of I/O operations such as reading and writing to discs or networks. They
can use various algorithms to determine the order in which I/O
operations are executed, such as FCFS (First-Come, First-Served) or RR
(Round Robin).
 Real-time schedulers: In real-time systems, real-time schedulers
ensure that critical tasks are completed within a specified time frame.
They can prioritize and schedule tasks using various algorithms such as
EDF (Earliest Deadline First) or RM (Rate Monotonic).
 Ch. 4 Operating System Services
Syllabus

• Processes ✓
• Process Structure ✓
• Process Scheduling ✓
• Scheduling Algorithms
• Process Synchronization & Deadlocks
• Thread Management
• Memory Management
• System Calls
• File System
 Scheduling Algorithms

❑ FCFS (Non-pre-emptive)
❑ SJF ( Pre-emptive and Non-pre-emptive)
❑ Priority ( Pre-emptive and Non-pre-emptive)
❑ Round-Robin ( Pre-emptive)
❑ Multilevel Queue ( Pre-emptive)
❑ Multilevel Feedback Queue( Pre-emptive)
 Choosing a scheduling algorithm

❑ No algorithm is “best” all the time.

❑ Algorithms is chosen by the OS developer or programmer.
❑ It is selected on the basis of user’s requirements and algorithm strategies.
For example, Windows NT/XP/Vista uses a multilevel feedback queue, a
combination of fixed-priority preemptive scheduling, round-robin, and first in, first out
algorithms.
Process Attributes for scheduling

 Burst Time
 Every process in a computer system requires some amount of time for its execution. This
time is both the CPU time and the I/O time. The CPU time is the time taken by CPU to
execute the process. While the I/O time is the time taken by the process to perform some
I/O operation. In general, we ignore the I/O time and we consider only the CPU time for a
process. So, Burst time is the total time taken by the process for its execution on the
CPU.

 Arrival time
 Arrival time is the time when a process enters into the ready state and is ready for its
execution.
 Here in the above example, the arrival time of all the 3 processes are 0 ms, 1 ms, and 2 ms respectively.

Exit time / Completion Time

Exit time is the time when a process completes its execution and exit from the system.
Gantt Chart

 The chart/diagram/picture which shows scheduling of

processes at different time intervals.
Metrics to evaluate algorithm performance

 Response Time
 Waiting Time
 Turnaround Time
 Throughput
 CPU Utilization
Metrics to evaluate algorithm performance

 Response Time
The first response time when the process gets selected
for execution.
 Waiting Time
The total time process has spent in the system sitting idle.
Metrics to evaluate algorithm performance

 Turnaround Time
 It is the total time a process has spent in the system(including burst
time, CPU time, I/O time , waiting time etc.)

 Throughput
 It is the total no. of processes completed in one unit of time.

 CPU Utilization
 It is measured as how much time the CPU is busy in executing the
processes.
 1. First Come First Serve:

FCFS considered to be the simplest of all operating system scheduling algorithms. First
come first serve scheduling algorithm states that the process that requests the CPU
first is allocated the CPU first and is implemented by using FIFO queue.

Characteristics of FCFS:
•FCFS supports non-preemptive CPU scheduling algorithms.
•Tasks are always executed on a First-come, First-serve concept.
•FCFS is easy to implement and use.
•This algorithm is not much efficient in performance, and the wait time is quite high.
 1. First Come First Serve:

Advantages of FCFS:
• Easy to implement
• First come, first serve method

Disadvantages of FCFS:
FCFS suffers from Convoy effect.
The average waiting time is much higher than the other algorithms.
FCFS is very simple and easy to implement and hence not much efficient.
 Convoy Effect in OS

Convoy Effect is phenomenon associated with the First Come First Serve
(FCFS) algorithm, in which the whole Operating System slows down due
to few slow processes.

FCFS algorithm is non-preemptive in nature, that is, once CPU time has been
allocated to a process, other processes can get CPU time only after the current
process has finished. This property of FCFS scheduling leads to the situation
called Convoy Effect.
Ex. 1 Schedule following processes using FCFS algorithm
and Calculate response time, waiting time, turnaround
time, completion time of all the processes. Also Calculate
average turnaround time, average waiting time ,
throughput, and CPU utilization.
0 ms

P1

0 ms 8 ms

P1 P2

0 ms 8 ms 15 ms

P1 P2 P3

0 ms 8 ms 15 ms 25 ms
 Process Arrival Time Burst Time Response Time Competition Turnaround Waiting
Time Time Time
P1 0 8 0 8 8-0 = 8 8-8 = 8
P2 0 7 8 15 15-0= 15 15-7 = 8
P3 2 10 15 25 25-2 = 23 23-10 = 13
Turnaround Time = Completion Time – Arrival Time
Waiting Time = Turnaround Time – Burst Time

Avg. Turnaround Time = Total Turnaround Time / no. of processes

= 46 / 3 = 15.3 ms
Avg. Waiting Time = Total Waiting Time / no. of processes
= 29 / 3 = 9.6 ms
Throughput = no. of processes /(System Competition Time- System Start Time)
=3 / ( 25-0) = 0.08 = 8 % of a process is completed in 1 unit of time
CPU Utilization = 100 * (System Competition Time- System Start Time) / = 100*(25-0) / 25
System Completion Time = 100 %
Ex. 2 Schedule following processes using FCFS algorithm
and Calculate response time, waiting time, turnaround
time, completion time of all the processes. Also Calculate
average turnaround time, average waiting time ,
throughput, and CPU utilization.
Process Arrival Time CPU Burst Time
P0 2 6
P1 5 2
P2 1 8
P3 0 3
P4 4 4
Ex. 3 Schedule following processes using FCFS algorithm
and Calculate response time, waiting time, turnaround
time, completion time of all the processes. Also Calculate
average turnaround time, average waiting time ,
throughput, and CPU utilization.
Process Arrival Time CPU Burst Time
P0 2 1
P1 5 5
P2 5 3
P3 4 2
P4 4 7
Ex. 4 Schedule following processes using FCFS algorithm
and Calculate response time, waiting time, turnaround
time, completion time of all the processes. Also Calculate
average turnaround time, average waiting time ,
throughput, and CPU utilization.
Ex. 5 Schedule following processes using FCFS algorithm
and Calculate response time, waiting time, turnaround
time, completion time of all the processes. Also Calculate
average turnaround time, average waiting time ,
throughput, and CPU utilization.
Thank
You