What is an Operating System?

• A program that acts as an intermediary between a user

of a computer and the computer hardware
• A more common definition is that the operating system
is the one program running at all times on the
computer (usually called the kernel), with all else being
application programs.
• An operating system is concerned with the allocation
of resources and services, such as memory, processors,
devices, and information
Operating System Services
□ Operating systems provide an environment for execution of programs and
services to programs and users
□ One set of operating-system services provides functions that are
helpful to the user:
□ User interface - Almost all operating systems have a user
interface (UI).Varies between Command-Line (CLI), Graphics
User Interface (GUI),

□ Program execution - The system must be able to load a

program into memory and to run that program, end execution,
either normally or abnormally (indicating error)
□ I/O operations - A running program may require I/O, which may
involve a file or an I/O device
□ File-system manipulation - The file system is of particular interest.
Programs need to read and write files and directories, create and delete
them, search them, list file Information, permission management.
□ Communications – Processes may exchange information, on the same
computer or between computers over a network
 Communications may be via shared memory or through message
passing (packets moved by the OS)
□ Error detection – OS needs to be constantly aware of possible errors
 May occur in the CPU and memory hardware, in I/O devices, in user
program
 For each type of error, OS should take the appropriate action to
ensure correct and consistent computing
 Debugging facilities can greatly enhance the user’s and
programmer’s abilities to efficiently use the system
□ Another set of OS functions exists for ensuring the efficient operation of the
system itself via resource sharing
□ Resource allocation - When multiple users or multiple jobs running
concurrently, resources must be allocated to each of them
 Many types of resources - CPU cycles, main memory, file
storage, I/O devices.
□ Accounting - To keep track of which users use how much and what
kinds of computer resources
□ Protection and security - The owners of information stored in a
multiuser or networked computer system may want to control use of
that information, concurrent processes should not interfere with each
other
 Protection involves ensuring that all access to system resources is
controlled
 Security of the system from outsiders requires user authentication,
extends to defending external I/O devices from invalid access
attempts
 Functionality of Operating system .
Following are some of important functions of an operating
System.
• Memory Management
• Processor Management
• Device Management
• File Management
• SecurityJob accounting
• Error detecting aids
• Coordination between other software and users
 Memory Management
• Memory management refers to management of Primary Memory or
Main Memory.
• Main memory is a large array of words or bytes where each word or
byte has its own address.
• Main memory provides a fast storage that can be accessed directly by
the CPU. For a program to be executed, it must in the main memory.
An Operating System does the following activities for memory
management:
• Keeps tracks of primary memory, i.e., what part of it are in use by
whom, what part are not in use.
• In multiprogramming, the OS decides which process will get memory
when and how much.
 Processor Management
• In multiprogramming environment, the OS decides
which process gets the processor when and for how
much time. This function is called process scheduling.
An Operating System does the following activities for
processor management −
• Keeps tracks of processor and status of process. The
program responsible for this task is known as traffic
controller.
• Allocation and De-allocation of the processor (CPU) to a
process.
 File Management
• A file system is normally organized into
directories for easy navigation and usage. These
directories may contain files and other directions.
• An Operating System does the following activities
for file management:
• Keeps track of information, location, uses, status
etc. The collective facilities are often known
as file system.
 Other Important Activities
Some of the important activities that an Operating System
performs −
• Security − By means of password and similar other
techniques, it prevents unauthorized access to programs and
data.
• Job accounting − Keeping track of time and resources used by
various jobs and users.
• Error detecting aids − Production of dumps, traces, error
messages, and other debugging and error detecting aids.
• Coordination between other software's and users −
Coordination and assignment of compilers, interpreters,
assemblers and other software to the various users of the
computer systems.
TOPIC : PROCESS
 What is Process?
• A process is basically a program in execution. The
execution of a process must progress in a
sequential fashion.
• 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
• When a program is loaded into the memory and it becomes a
process, it can be divided into four sections ─ stack, heap, text
and data. The following image shows a simplified layout of a
process inside main memory
 Process Component & Description
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 states or Process Life Cycle
• When a process executes, it passes through different states.
These stages may differ in different operating systems, and the
names of these states are also not standardized.
• In general, a process can have one of the following five states at
a time.
• 1. New State
• [Link] State
• [Link] State
• [Link] State
• 5. Terminate or exit state
Process state
 Process state
1. New State
A process is said to be in new state when a program present
in the secondary memory is initiated for execution
2. Ready State-
A process moves from new state to ready state after it is
loaded into the main memory and is ready for execution.
In ready state, the process waits for its execution by the
processor.
In multiprogramming environment, many processes may be
present in the ready state.
 Process state
3. Run State-
A process moves from ready state to run state after it is
assigned the CPU for execution.
4. Block Or Wait State-
A process moves from run state to block or wait state if it
requires an I/O operation or some blocked resource during its
execution.
After the I/O operation gets completed or resource becomes
available, the process moves to the ready state.
 Process state
5. Terminate State-
A process moves from run state to terminate
state after its execution is completed.
After entering the terminate state, context (PCB)
of the process is deleted by the operating
system.
 Process Control Block (PCB)
• A Process Control Block is a data structure maintained
by the Operating System for every process.

• The PCB is identified by an integer process ID (PID).

• A PCB keeps all the information needed to keep track

of a process as listed below in the table
 Process Control Block (PCB)
Process State
• The current state of the process i.e., whether it is ready,
running, waiting, or whatever.
Process privileges
• This is required to allow/disallow access to system resources.
Process ID
• Unique identification for each of the process in the operating
system.
Pointer
• A pointer to parent process.
 Process Control Block (PCB)
Program Counter
• Program Counter is a pointer to the address of the next
instruction to be executed for this process.
CPU registers
• Various CPU registers where process need to be stored for
execution for running state.
CPU Scheduling Information
• Process priority and other scheduling information which is
required to schedule the process.
 Process Control Block (PCB)
Memory management information
• This includes the information of page table, memory limits,
Segment table depending on memory used by the operating
system.
Accounting information
• This includes the amount of CPU used for process execution,
time limits, execution ID etc.
IO status information
• This includes a list of I/O devices allocated to the process.
Process Control Block (PCB)
 Process Scheduling
• The 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 on the basis of a particular strategy.
• Process scheduling is an essential part of a
Multiprogramming operating systems.
• Such operating systems allow more than one process
to be loaded into the executable memory at a time
 Process Scheduling Queues
• The OS maintains all PCBs in Process Scheduling Queues.
• The OS maintains a separate queue for each of the process
states and PCBs of all processes in the same execution
state are placed in the same queue.
• When the state of a process is changed, its PCB is unlinked
from its current queue and moved to its new state queue.
• The Operating System maintains the following important
process scheduling queues −
 Process Scheduling Queues
The Operating System maintains the following important
process scheduling queues
Job queue − This queue keeps all the processes in the
system.
Ready queue − This queue keeps a set of all processes
residing in main memory, ready and waiting to execute.
A new process is always put in this queue.
Device queues − The processes which are blocked due to
unavailability of an I/O device constitute this queue.
Process Scheduling Queues
 Two-State Process Model
Running
• When a new process is created, it enters into the system as in
the running state.
Not Running
• Processes that are not running are kept in queue, waiting for
their turn to execute.
• Each entry in the queue is a pointer to a particular process.
Queue is implemented by using linked list.
• When a process is interrupted, that process is transferred in
the waiting queue. If the process has completed or aborted,
the process is discarded. In either case, the dispatcher then
selects a process from the queue to execute.
 Process Schedulers
• Schedulers are special system software which handle
process scheduling in various ways.
• Their main task is to select the jobs to be submitted into
the system and to decide which process to run
There are three types of Schedulers
1. Long-Term Scheduler
2. Short-Term Scheduler
3. Medium-Term Scheduler
 Long Term Scheduler
• It is also called a 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. It also controls the degree of multiprogramming.
• If the degree of multiprogramming is stable, then the
average rate of process creation must be equal to the
average departure rate of processes leaving the system.
 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.
 Medium Term Scheduler

• Medium-term scheduling is a part of swapping.

• 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.
 S.N. Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler

1 It is a job scheduler It is a CPU scheduler It is a process swapping

scheduler.

2 Speed is lesser than short term Speed is fastest among Speed is in between both
scheduler other two short and long term
scheduler.

3 It controls the degree of It provides lesser control It reduces the degree of

multiprogramming over degree of multiprogramming.
multiprogramming

4 It selects processes from pool and loads It selects those processes It can re-introduce the
them into memory for execution which are ready to process into memory and
execute execution can be
continued.
 Context Switch

• A Context Switch is the mechanism to store

and restore the state or context of a CPU in
Process Control block so that a process
execution can be resumed from the same
point at a later time.
• This is a feature of a multitasking operating
system and allows a single CPU to be shared by
multiple processes.
 Context Switch
• In the above diagram, initially Process 1 is running. Process 1 is
switched out and Process 2 is switched in because of an
interrupt or a system call.
• Context switching involves saving the state of Process 1 into
PCB1 and loading the state of process 2 from PCB2.
• After some time again a context switch occurs and Process 2 is
switched out and Process 1 is switched in again.
• This involves saving the state of Process 2 into PCB2 and
loading the state of process 1 from PCB1.
Scheduling: Strategy selection
 What is Process Scheduling?
Process Scheduling
• Process or CPU Scheduling can be defined as a set of policies
and mechanisms which controls the order in which the work
to be done is completed.
• Whenever the CPU becomes idle, it is the job of the CPU
Scheduler to select another process from the ready queue to
run next.
• The selection process will be carried out by the CPU
scheduler.
Goal of CPU Scheduling
 CPU Scheduling-Terms and Terminology

CPU Utilization : A scheduling algorithm should be designed so that CPU

remains busy as possible. It should make efficient use of CPU
Throughput :Number of processes completed per unit time.
Arrival Time: Time at which the process arrives in the ready queue.
Completion Time: Time at which process completes its execution.
Burst Time: Time required by a process for CPU execution.
Response time: The–amount of time it takes from when a request was
submitted until the first response is produced
 CPU Scheduling-Terms and Terminology
Turn Around Time: Time Difference between completion time
and arrival time.

Turn Around Time(TAT) = Completion Time(CT) – Arrival

Time(AT)

Waiting Time(W.T): Time Difference between turn around time

and burst time.

Waiting Time(WT)=Turn Around Time(TAT) – Burst Time(BT)

 Types of CPU Scheduling

1. First Come First Serve (FCFS)

2. Shortest-Job-First (SJF) Scheduling
3. Shortest Remaining Time
4. Priority Scheduling
5. Round Robin Scheduling
 Types of CPU Scheduling

1. First Come First Serve (FCFS)

2. Shortest-Job-First (SJF) Scheduling
3. Shortest Remaining Time
4. Priority Scheduling
5. Round Robin Scheduling
 1. First Come First Serve

• It is the simplest algorithm to implement. The

process which come first will use the CPU first.
• It is the non-preemptive type of scheduling.
 FCFS Scheduling-Example
Consider the following FCFS scheduling algorithm. In the
Following schedule, there are 5 processes with process ID
P0, P1, P2, P3 and P4. The processes and their respective
Arrival and Burst time are given in the following table. Find
out the average waiting time
Arrival
Process Burst Time
Time
Example: P0 0 2
P1 1 6
P2 2 4
P3 3 9
P4 4 12
 FCFS Scheduling
Gantt chart

Formula: TAT = CT – AT WT= TAT – BT

Burst
Arrival Completion Turn Around Waiting
Process Time
Time(AT) Time(CT) Time(TAT) Time(WT)
(BT)
P0 0 2 2 2 0
P1 1 6 8 7 1
P2 2 4 12 10 6
P3 3 9 21 18 9
P4 4 12 33 29 17
Total Waiting Time= 33
Average Waiting Time=33/5 = 6.6
 Shortest Job First (SJF)
• The job with the shortest burst time will get the CPU first. The
lesser the burst time, the sooner will the process get the CPU. It
is the non-preemptive type of scheduling.
• Shortest Job First (SJF) is an algorithm in which the process
having the smallest execution time is chosen for the next
execution. This scheduling algorithm also knows as Shortest Job
Next (SJN) .
• This scheduling method can be preemptive or non-preemptive.
• To successfully implement it, the burst time/duration time of
the processes should be known to the processor in advance,
which is practically not feasible all the time
• This is the best approach to minimize waiting time.
 Example-Shortest-Job-First (SJF)
Consider the following four processes with the arrival time and length of
CPU burst given in milliseconds
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
 Solutions
P1 P2 P4 P3
0 8 12 17 26
PROCESS ARRIVAL TIME BURST TIME COMPLETION TURNAROUND TIME WAITING
TIME TIME

P1 0 8 8 8 0
P2 1 4 12 11 7
P3 2 9 26 24 15
P4 3 5 17 14 9
TOTAL WAITING TIME 31

AVERAGE WAITING TIME=31/4

=7.75 ms
 Shortest Remaining Time First
It is the preemptive form of SJF. In this algorithm, the OS
schedules the Job according to the remaining time of the
execution.
Shortest Remaining Time First (SRTF), is a scheduling
method that is a preemptive version of Shortest Job First(SJF)
scheduling.
Shortest remaining time is advantageous because short
processes are handled very quickly
SRTF and Shortest Job First scheduling algorithms are
suffered by starvation problem.
 Round Robin Scheduling
• Round Robin is the preemptive process scheduling
algorithm.
• Each process is provided a fix time to execute, it is called
a time quantum(time slice).
• 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
 Priority Scheduling
• We have two types of priority scheduling (Preemptive and
Non-preemptive). Non-preemptive priority scheduling
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
 Example: Non Pre-emptive Priority
Consider the set of processes with arrival time(in milliseconds), CPU
burst time (in milliseconds), and priority(1 is the highest priority)
shown below. Process Arrival Burst Time Priority
Time
P1 0 12 2
P2 2 4 1
P3 3 6 4
P4 8 5 3
 Solutions:Non Pre-emptive Priority
P1 P2 P4 P3

0 12 16 21 27

Process Arrival Burst Time Priority Completion Turnaround Waiting Time

Time Time Time
P1 0 12 2 12 12 0
P2 2 4 1 16 14 10
P3 3 6 4 27 24 18
P4 8 5 3 21 13 8
36

Average waiting time=36/4

=9.0
 Example: Pre-emptive Priority
Consider the set of processes with arrival time(in milliseconds),
CPU burst time (in milliseconds), and priority(1 is the highest
priority) shown below.
Process Arrival Burst Time Priority
Time
P1 0 12 2
P2 2 4 1
P3 3 6 4
P4 8 5 3
 Solutions: Pre-emptive Priority
10
P1 P2 P1 P4 P3

0 2 6 16 21 27

Process Arrival Burst Time Priority Completion Turnaround Waiting Time

Time Time Time
P1 0 12 2 16 16 4
P2 2 4 1 6 4 0
P3 3 6 4 27 24 18
P4 8 5 3 21 13 8
30

Average waiting time=30/4

=7.5
 Starvation and Aging
• Starvation is the problem that occurs when high
priority processes keep executing and low priority
processes get blocked for indefinite time.
• To avoid starvation, we use the concept of Aging. In
Aging, after some fixed amount of time quantum, we
increase the priority of the low priority processes. By
doing so, as time passes, the lower priority process
becomes a higher priority process.
 Round Robin Scheduling
• Round Robin is the preemptive process scheduling
algorithm.
• Each process is provided a fix time to execute, it is called
a time quantum(time slice).
• 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
 Round Robin Scheduling
• Round Robin is the preemptive process scheduling
algorithm.
• Each process is provided a fix time to execute, it is called
a time quantum(time slice).
• 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
TOPIC : Memory Management
 What is Memory?
• Computer memory can be defined as a collection of some
data represented in the binary format.
• Computer system understands only binary language that is 0
or 1. Computer converts every data into binary language
first and then stores it into the memory.
• A computer device that is capable to store any information
or data temporally or permanently, is called storage
device(memory).
The binary representation of 10 is 1010. Here, we are considering
32 bit system therefore, the size of int is 2 bytes i.e. 16 bit. 1
memory block stores 1 bit
 Memory Management
• It is the process of controlling and coordinating computer
memory, assigning portions known as blocks to various running
programs to optimize the overall performance of the system.
• Memory management is the functionality of an operating
system which handles or manages primary memory and
moves processes back and forth between main memory and
disk during execution.
• Memory management keeps track of each and every memory
location, regardless of either it is allocated to some process or
it is free. It checks how much memory is to be allocated to
processes
 Basics of Memory Management.
• The operating system takes care of mapping the logical
addresses to physical addresses at the time of memory
allocation to the program.
• There are three types of addresses used in a program before and
after memory is allocated
1. Symbolic addresses
2. Relative addresses
3. Physical addresses
Symbolic addresses
• The addresses used in a source code. The variable names,
constants, and instruction labels are the basic elements of the
symbolic address space.
Relative addresses
• At the time of compilation, a compiler converts symbolic
addresses into relative addresses.
Physical addresses
• The loader generates these addresses at the time when a
program is loaded into main memory.
 MMU
• The set of all logical(virtual) addresses generated by a
program is referred to as a logical address space.
• The set of all physical addresses corresponding to these
logical addresses is referred to as a physical address space.
• The runtime mapping from virtual to physical address is done
by the memory management unit (MMU) which is a hardware
device
 Memory Management Technique
• Operating system uses the various memory
management mechanism.
• Memory management techniques can be classified
into two types

1. Contiguous allocation- Single contiguous allocation

and partitioned allocation

1. Non-Contiguous allocation- Paging and Segmentation

 Single Contiguous
Allocation
• It is the easiest memory management technique.
• In this method, all types of computer's memory
except a small portion which is reserved for the OS is
available for one application.
• For example, MS-DOS operating system allocates
memory in this way. An embedded system also runs
on a single application.
Single Contiguous Allocation
 Partitioned Allocation
• It divides primary memory into various memory
partitions, which is mostly contiguous areas of
memory.
• Every partition stores all the information for a
specific task or job.
• This method consists of allotting a partition to a job
when it starts & unallocated when it ends.
• There are two types of partitioned allocation
[Link] size partition 2. Variable siz partition
Fixed Partitioning & Variable Partitioning
 Partition Allocation
• In Partition Allocation, when there is more than one partition freely
available to accommodate a process’s request, a partition must be
selected. To choose a particular partition, a partition allocation method
is needed. A partition allocation method is considered better if it
avoids internal fragmentation.
• When it is time to load a process into the main memory and if there is
more than one free block of memory of sufficient size then the OS
decides which free block to allocate.
There are different Placement Algorithm:
• A. First Fit
• B. Best Fit
 1. First Fit

• In the first fit, the partition is allocated which is the first

sufficient block from the top of Main Memory. It scans
memory from the beginning and chooses the first
available block that is large enough. Thus it allocates the
First hole that is large enough.
 2. Best Fit
• Allocate the process to the partition which is the first
smallest sufficient partition among the free available
partition. It searches the entire list of holes to find the
smallest hole whose size is greater than or equal to the
size of the process.
 3. Worst Fit
•Allocate the process to the partition which is the largest
sufficient among the freely available partitions available
in the main memory. It is opposite to the best-fit
algorithm. It searches the entire list of holes to find the
largest hole and allocate it to process.
 Problem in Contiguous- Fragmentation

Processes are stored and removed from memory, which

creates free memory space, which are too small to use by
other processes, it is called Fragmentation.
Two types of Fragmentation methods are:
• External fragmentation
• Internal fragmentation
 Fragmentation
1. Internal Fragmentation
•When a process is assigned to a memory block and if that
process is smaller than the memory requested, it creates a free
space in the assigned memory block. Then the difference
between assigned and requested memory is called the internal
fragmentation.
2. External Fragmentation
• Total memory space is enough to load a process but the process
still can’t load because free blocks of memory are not contiguous.
 Diagram-Explanation
Internal Fragmentation: The 4 MB partition is used to
load only 3 MB process and the remaining 1 MB got
waste
External Fragmentation : The remaining 1 MB space of each
partition cannot be used as a unit to store a 4 MB process.
Despite of the fact that the sufficient space is available to load the
process, process will not be loaded.
Paging
Paging-Example
 Non Contiguous- Paging
• Paging is a fixed size partitioning scheme.
• In paging, secondary memory and main memory
are divided into equal fixed size partitions.
• The partitions of secondary memory are called as
pages.
• The partitions of main memory are called as
frames.
• pages are mapped to the frames in Paging, page
size needs to be as same as frame size
TOPIC : Memory Management-
Paging
Paging-Example
 Logical Address
CPU generates a logical address consisting of two parts-
• Page Number
• Page Offset

• Page Number specifies the specific page of the

process from which CPU wants to read the data.

• Page Offset specifies the specific word on the page

that CPU wants to read
 Physical Address
• The frame number combined with the page offset
forms the required physical address.
 Address Translation
• Page address is called logical address and represented by page
number and the offset.
• Logical Address = Page number + page offset Frame address is
called physical address
• Physical Address = Frame number + page offset
• A data structure called page map table is used to keep track of
the relation between a page of a process to a frame in physical
memory.
 Advantages and Disadvantages of Paging
Here is a list of advantages and disadvantages of paging −
• Paging reduces external fragmentation, but still suffer from
internal fragmentation.
• Paging is simple to implement and assumed as an efficient
memory management technique.
• Due to equal size of the pages and frames, swapping
becomes very easy.
• Page table requires extra memory space, so may not be good
for a system having small RAM.
 Segmentation
• Segmentation memory management works very similar to paging but
here segments are of variable-length where as in paging pages are of
fixed
• The operating system maintains a segment map table for every
process and a list of free memory blocks along with segment
numbers, their size and corresponding memory locations in main
memory.
• For each segment, the table stores the starting address of the segment
and the length of the segment. A reference to a memory location
includes a value that identifies a segment and an offset.
•
 Advantages of Segmentation
• No Internal fragmentation.
• Segment Table consumes less space in comparison to Page table in
paging.
• As a complete module is loaded all at once, segmentation improves
CPU utilization.
• Flexibility: Segmentation provides a higher degree of flexibility than
paging. Segments can be of variable size, and processes can be designed
to have multiple segments, allowing for more fine-grained memory
allocation.
• Sharing: Segmentation allows for sharing of memory segments
between processes. This can be useful for inter-process communication
or for sharing code libraries.
 Disadvantages of Segmentation
Fragmentation: Segmentation can lead to external
fragmentation as memory becomes divided into smaller
segments. This can lead to wasted memory and decreased
performance.

Complexity: Segmentation can be more complex to implement

and manage than paging. In particular, managing multiple
segments per process can be challenging, and the potential for
segmentation faults can increase as a result.
Paging Problems
 Paging in Operating System
Paging is a memory management scheme that eliminates the
need for contiguous allocation of physical memory. This
scheme permits the physical address space of a process to be
non – contiguous.
Logical Address or Virtual Address (represented in bits):
An address generated by the CPU
Logical Address Space or Virtual Address Space(
represented in words or bytes): The set of all logical
addresses generated by a program
Address generated by CPU is divided into
Page number(p): Number of bits required to represent the
pages in Logical Address Space or Page number
Page offset(d): Number of bits required to represent particular
word in a page or page size of Logical Address Space or word
number of a page or page offset.
Physical Address is divided into
Frame number(f): Number of bits required to represent the
frame of Physical Address Space or Frame number.
Frame offset(d): Number of bits required to represent particular
word in a frame or frame size of Physical Address Space or word
number of a frame or frame offset.
 Virtual Memory-Introduction
• Virtual Memory is a storage scheme that provides user an illusion of having
a very big main memory. This is done by treating a part of secondary
memory as the main memory
• In this scheme, User can load the bigger size processes than the available
main memory by having the illusion that the memory is available to load
the process.
• Instead of loading one big process in the main memory, the Operating
System loads the different parts of more than one process in the main
memory.
• Because of Virtual memory the degree of multiprogramming will be
increased and therefore, the CPU utilization will also be increased.
 How Virtual Memory Works?
• In Virtual memory concept whenever some pages needs to be
loaded in the main memory for the execution and the memory is
not available for those many pages.
• In that case, instead of stopping the pages from entering in the
main memory, the OS search for the RAM area that are least used
in the recent times or that are not referenced and copy that into the
secondary memory to make the space for the new pages in the
main memory.
• Since all this procedure happens automatically, therefore it makes
the computer feel like it is having the unlimited RAM.
 Demand Paging
• According to the concept of Virtual Memory, in order to execute
some process, only a part of the process needs to be present in the
main memory which means that only a few pages will only be
present in the main memory at any time.
• However, deciding, which pages need to be kept in the main
memory and which need to be kept in the secondary memory, is
going to be difficult because we cannot say in advance that a process
will require a particular page at particular time.
• Therefore, to overcome this problem, there is a concept called
Demand Paging is introduced.
 Demand Paging
• It suggests keeping all pages of the frames in the secondary
memory until they are required. In other words, it says that do not
load any page in the main memory until it is required.
• Whenever any page is referred for the first time in the main
memory, then that page will be found in the secondary memory.
• After that, it may or may not be present in the main memory
depending upon the page replacement algorithm
 Page Fault
• If the referred page is not present in the main memory
then there will be a miss and the concept is called Page
miss or page fault.
• The CPU has to access the missed page from the
secondary memory. If the number of page fault is very
high then the effective access time of the system will
become very high.
 Page Replacement Algorithm
• Page replacement algorithms help to decide which page must be
swapped out from the main memory to create a room for the
incoming page.
Types of Page Replacement Algorithm
• FIFO(First in First out) Page Replacement Algorithm(Beladys
anamoley)
• LRU (Least Recently Used) Page Replacement
Algorithm (Stack)
• Optimal Page Replacement Algorithm(Future)
 Page Replacement Algorithm
FIFO: In this algorithm, a queue is maintained. The page
which is assigned the frame first will be replaced first.
Optimal Page Replacement algorithm:
• In this algorithms replaces the page which will not be
referred for so long in future.
• Although it can not be practically implementable but it can
be used as a benchmark.
• Compare to other algorithms Optimal Page Replacement is
Produce optimum result
 Least recent used (LRU)
• In this algorithm replaces the page which has not been
referred for a long time. This algorithm is just opposite to the
optimal page replacement algorithm.
• In this, we look at the past instead of staring at future
Thrashing

• If the number of page faults is equal to the number of referred pages

or the number of page faults are so high so that the CPU remains
busy in just reading the pages from the secondary memory then the
effective access time will be the time taken by the CPU to read one
word from the secondary memory and it will be so high. The concept
is called thrashing
 Translation Look aside buffer
• A Translation look aside buffer can be defined as a memory cache which can
be used to reduce the time taken to access the page table again and again.
• It is a memory cache which is closer to the CPU and the time taken by CPU
to access TLB is lesser then that taken to access main memory.
• In other words, we can say that TLB is faster and smaller than the main
memory but cheaper and bigger than the register.
• TLB follows the concept of locality of reference which means that it contains
only the entries of those many pages that are frequently accessed by the
CPU.
 Translation Look aside buffer
• A Translation look aside buffer can be defined as a memory cache which can
be used to reduce the time taken to access the page table again and again.
• It is a memory cache which is closer to the CPU and the time taken by CPU
to access TLB is lesser then that taken to access main memory.
• In other words, we can say that TLB is faster and smaller than the main
memory but cheaper and bigger than the register.
• TLB follows the concept of locality of reference which means that it contains
only the entries of those many pages that are frequently accessed by the
CPU.
TOPIC : DISK SCHEDULING
 Introduction-Disk Scheduling
• A disk is divided into tracks, cylinders, and sectors.
 Disk scheduling and its Type
What is Disk Scheduling: Disk scheduling is a
technique used by the operating system to schedule
multiple requests for accessing the disk.
Types of Disk Scheduling Algorithm:
1) FCFS scheduling algorithm
2) SSTF (shortest seek time first) algorthim
3) SCAN scheduling
4) C-SCAN scheduling
5) LOOK Scheduling
6) C-LOOK scheduling
 1. FCFS
• FCFS stands for First Come First Serve
• It is the simplest disk scheduling algorithm
Example: Consider a disk queue with requests for I/O
to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67.
The FCFS scheduling algorithm is used. The head is
initially at cylinder number 53. The cylinders are
numbered from 0 to 199. The total head movement (in
number of cylinders) incurred while servicing these
requests is
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67. Step 1: Write the given
Disk request in the ascending order. Step 2: Always Starts from given Initial Head
Position (53)

130+142+81+108
+110+59+02=632

Total head movements

= (98 – 53) + (183 – 98) + (183 – 41) + (122 – 41) + (122 – 14)
+ (124 – 14) + (124 – 65) + (67 – 65)
= 45 + 85 + 142 + 81 + 108 + 110 + 59 + 2
= 632
 2. SSTF
• SSTF stands for Shortest Seek Time First.
• This algorithm services that request next which requires
least number of head movements from its current position
regardless of the direction.
Example: Consider a disk queue with requests for I/O to blocks
on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The SSTF scheduling
algorithm is used. The head is initially at cylinder number 53. The
cylinders are numbered from 0 to 199. The total head movement
(in number of cylinders) incurred while servicing these requests is
.
 Solutions-SSTF
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67.

12 14

Total head movements

= (65 – 53) + (67 – 65) + (67 – 41) + (41 – 14) + (98 – 14) + (122 – 98) +
(124 – 122) + (183 – 124)
= 12 + 2 + 26 + 27 + 84 + 24 + 2 + 59
= 236
 Explanation
The given sequence is
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73 Head

2 4 6 7 10 15 19 20 34 16 50 23 73

➔ (50-34)+(34-20)+(20-19)+(19-15)+(15-10)+(10-7)+(7-6)+(6-4)+(4-2)+(73-2)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms ANSWER:OPTION 4
 3. SCAN Disk Scheduling Algorithm
• As the name suggests, this algorithm scans all the
cylinders of the disk back and forth.
• Head starts from one end of the disk and move towards
the other end servicing all the requests in between.
• After reaching the other end, head reverses its
direction and move towards the starting end servicing
all the requests in between.
•SCAN Algorithm is also called as Elevator Algorithm.
NOTE: SCAN,C-SCAN, LOOK, C-LOOK algorithm
Questions must have moving directions (Towards highest,
lowest, …)
 Solutions-SCAN ALGORITHM
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67.

Total head movements:

= (199 – 53) + (199 – 14)
= 146 + 185
= 331
 Explanation:

When it completed its last given sequence from

input, it stops.
So, total disk head movement = 23+128 = 151
ANSWER:OPTION B
 4. C-SCAN Disk Scheduling Algorithm
• Circular-SCAN Algorithm is an improved
version of the SCAN Algorithm.
• Head starts from one end of the disk and move
towards the other end servicing all the requests in
between.
• After reaching the other end, head reverses its
direction.
• It then returns to the starting end without
servicing any request in between.
 Solutions: C-SCAN ALGORITHM
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67.

Total head movements

= (199 – 53) + (199 – 0) + (41 – 0)
= 146 + 199 + 41
= 386
 5. LOOK Disk Scheduling Algorithm
• Head starts from the first request at one end of the disk and
moves towards the last request at the other end servicing all
the requests in between.
• After reaching the last request at the other end, head reverses
its direction.
The main difference between SCAN Algorithm and LOOK
Algorithm is-
• SCAN Algorithm scans all the cylinders of the disk starting
from one end to the other end even if there are no requests
at the ends.
• LOOK Algorithm scans all the cylinders of the disk starting
from the first request at one end to the last request at the
other end
 Solutions: LOOK ALGORITHM
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67.

Total head movements

= (183 – 53) + (183 – 14)
= 130 + 169 = 299
 Solutions-Look

Therefore, the total seek count is calculated as:

=(176-50)+(176-11)
=126+165
=291
 6. C-LOOK Disk Scheduling Algorithm
• Circular-LOOK Algorithm is an improved version of the
LOOK Algorithm.
• Head starts from the first request at one end of the disk
and moves towards the last request at the other end
servicing all the requests in between.
• After reaching the last request at the other end, head
reverses its direction.
• It then returns to the first request at the starting end
without servicing any request in between.
 Example
• Consider a disk queue with requests for I/O to blocks
on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The C-
LOOK scheduling algorithm is used. The head is
initially at cylinder number 53 moving towards larger
cylinder numbers on its servicing pass. The cylinders
are numbered from 0 to 199. The total head
movement (in number of cylinders) incurred while
servicing these requests is .
 Solutions: C-LOOK ALGORITHM
Given Cylinder Request: 98, 183, 41, 122, 14, 124, 65, 67.

Total head movements

= (183 – 53) + (183 – 14) + (41 – 14)
= 130 + 169 + 27
= 326
 Deadlock-Introduction
• Every process needs some resources to complete its execution.
However, the resource is granted in a sequential order.
• The process requests for some resource.
• OS grant the resource if it is available otherwise let the process
waits.
• When the process completes its execution, it release the
resources.
 Deadlock-Introduction
• A Deadlock is a situation where each of the computer process
waits for a resource(I/O devices, CPU, Memory…) which is
being assigned to some another process.
• In this situation, none of the process gets executed since the
resource it needs, is held by some other process which is also
waiting for some other resource to be released.
• For example Process 1 is holding Resource 1 and waiting for
resource 2 which is acquired by process 2, and process 2 is
waiting for resource 1.
Deadlock Situation
 Deadlock-Introduction
• In the above diagram, the process 1 has resource 1 and needs
to acquire resource 2. Similarly process 2 has resource 2 and
needs to acquire resource 1. Process 1 and process 2 are in
deadlock as each of them needs the other’s resource to
complete their execution.
• In this scenario, a cycle is being formed among the two
processes. None of the process is progressing and they are all
waiting. The computer becomes unresponsive since all the
processes got blocked.
 Necessary conditions for Deadlocks
Mutual Exclusion
• A resource can only be shared in mutually exclusive manner. It implies, if two
process cannot use the same resource at the same time.
Hold and Wait
• A process waits for some resources while holding another resource at the same
time.
No preemption
• A resource cannot be taken from a process unless the process releases the
resource.
Circular Wait
• All the processes must be waiting for the resources in a cyclic manner so that
the last process is waiting for the resource which is being held by the first
process.
Strategies for handling Deadlock
 1. Deadlock Ignorance:
• Deadlock Ignorance is the most widely used approach among
all the mechanism.
• In this approach, the Operating system assumes that deadlock
never occurs. It simply ignores deadlock.
• In these types of systems, the user has to simply restart the
computer in the case of deadlock.
 2. Deadlock prevention or avoidance
• Deadlock happens only when Mutual Exclusion, hold and wait,
No preemption and circular wait holds simultaneously.
• If it is possible to violate one of the four conditions at any time
then the deadlock can never occur in the system.
• the operating system checks whether the system is in safe state or
in unsafe state at every step which the operating system performs.
• Banker’s algorithm used to avoid the deadlock situations.
 Deadlock avoidance-Bankers
algorithm
• Bankers algorithm is an algorithm which is used
for deadlock avoidance and resource allocation.
• It was established by Edsger Dijkstra. The reason behind the
name ‘banker’s algorithm’ is that it is mostly used in banking
systems.
• Banker’s algorithm helps to identify whether a loan should be
provided or not.
 Banker’s Algorithm
• Banker’s Algorithm follows the safety algorithm to check
whether the resulting state it has entered in is a safe state or
not.
• If it is a safe state, then it allocates the requested resources to
the process in actual.
• If it is an unsafe state, then it rollbacks to its previous state and
asks the process to wait long
 Data Structures used to implement the
Banker’s Algorithm
There are four types of data structures used to implement
Banker’s algorithm:
• Available
• Max
• Allocation
• Need
Topic: Process synchronization
 Introduction-PS
• Process Synchronization was introduced to handle
problems that occurs multiple process executions.
• Process is categorized into two types on the basis of
synchronization and these are given below:
1. Independent Process
2. Cooperative Process
 Introduction-PS
Independent Processes
• Two processes are said to be independent if the execution
of one process does not affect the execution of another
process.
Cooperative Processes
• Two processes are said to be cooperative if the execution
of one process affects the execution of another process.
These processes need to be synchronized so that the order
of execution can be guaranteed.
 Introduction-PS
• No two processes can have access to the same shared data
and resources.
• It is a procedure that is involved in order to preserve the
appropriate order of execution of cooperative processes.
• In order to synchronize the processes, there are various
synchronization mechanisms.
• Process Synchronization is mainly needed in a multi-
process system when multiple processes are running
together, and more than one processes try to gain access to
the same shared resource or any data at the same time.
Race condition is a situation where-
The final output produced depends on the execution order of instructions of
different processes.
 Example
The above illustration shows how inconsistent results may
be produced if multiple processes execute concurrently
without any synchronization.
• Consider-Two processes P1 and P2 are executing
concurrently.
• Both the processes share a common variable named
“count” having initial value = 5.
• Process P1 tries to increment the value of count.
• Process P2 tries to decrement the value of count.
 Race Condition
• At the time when more than one process is either
executing the same code or accessing the same memory
or any shared variable.
• In that condition, there is a possibility that the output or
the value of the shared variable is wrong so for that
purpose all the processes are doing the race to say that my
output is correct. This condition is commonly known as a
race condition.
 Critical section
• As several processes access and process the
manipulations on the same data in a concurrent manner
and due to which the outcome depends on the particular
order in which the access of data takes place.
• A race condition is a situation that may occur inside a
critical section. This happens when the result of multiple
thread execution in the critical section differs according to
the order in which the threads execute.
 Critical Section Problem
• Critical section is a code segment that can be accessed by only
one process at a time. Critical section contains shared variables
which need to be synchronized to maintain consistency of data
variables.
Any solution to the critical section problem must satisfy three
requirements:
1. Mutual Exclusion : If a process is executing in its
critical section, then no other process is allowed to
execute in the critical section.
2. Progress : If no process is executing in the critical
section and other processes are waiting outside the critical
section, then only those processes that are not executing
in their remainder section can participate in deciding
which will enter in the critical section next, and the
selection can not be postponed indefinitely.
3. Bounded Waiting : A bound must exist on the number of
times that other processes are allowed to enter their
critical sections after a process has made a request to
enter its critical section and before that request is
granted.
 Solution to critical section problem
• We have three important solutions for critical section
problems.
1. Peterson’s solution
2. TestAndSet
3. Semaphore
 1. Peterson’s Solution
• Peterson’s Solution is a classical software based solution to
the critical section problem.
• In Peterson’s solution, we have two shared variables:
• boolean flag[i] :Initialized to FALSE, initially no one is
interested in entering the critical section
• int turn : The process whose turn is to enter the critical
section.
Peterson’s Solution
 2. TestAndSet
• TestAndSet is a hardware solution to the critical section
problem(synchronization problem).
• In TestAndSet, we have a shared lock variable which can
take either of the two values, 0 or 1.
• 0 Unlock 1 Lock Before entering into the critical section,
a process inquires about the lock. If it is locked, it keeps
on waiting until it becomes free and if it is not locked, it
takes the lock and executes the critical section.
 3. Semaphore
A semaphore is a simple integer variable. It is used to provide solution to
the critical section problems or its provide synchronization among
multiple processes running concurrently.
There are mainly two types of semaphores
1. Counting Semaphores
2. Binary Semaphores
The value of counting semaphore may be positive or negative.
Wait (P) operation decrements the value of counting semaphore by 1.
Signal (V)operation increments the value of counting semaphore by 1.
 Binary Semaphores
• They can only be either 0 or 1. They are also known as mutex
locks, as the locks can provide mutual exclusion.
• All the processes can share the same mutex semaphore that is
initialized to 1. Then, a process has to wait until the lock
becomes 0.
• Then, the process can make the mutex semaphore 1 and start
its critical section.
• When it completes its critical section, it can reset the value of
mutex semaphore to 0 and some other process can enter its
critical section.
 Counting Semaphores
• The value of counting semaphore is initialized with ‘n’.
• When a process enters the critical section, the value of
counting semaphore decrements by 1(Wait (Operation)
• When a process exits the critical section, the value of
counting semaphore increments by 1(Signal Operation)
• Other names by which wait operation may be referred :
Down operation, P operation.
• Other names by which signal operation may be referred :
Up operation, V operation.
 File Management
What is a File ?
• A file can be defined as a data structure which stores the sequence of
records. Files are stored in a file system, which may exist on a disk or in
the main memory. Files can be simple (plain text) or complex (specially-
formatted).
• The collection of files is known as Directory. The collection of directories
at the different levels, is known as File System.
• Attributes of the File: Name, Identifier(extension), Size,…
• Operations on the File: Create, Write, Read, Delete(Deleting the file
will not only delete all the data stored inside the file, It also deletes all the
attributes of the file), Truncate (Truncating is simply deleting the file
except deleting attributes. The file is not completely deleted although the
information stored inside the file get replaced).
 File Allocation Methods
The allocation methods define how the files are stored in the disk
blocks. There are three main disk space or file allocation methods.
1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation
The main idea behind these methods is to provide:
• Efficient disk space utilization.
• Fast access to the file blocks.
All the three methods have their own advantages and disadvantages
as discussed below:
 1. Contiguous Allocation
• In this scheme, each file occupies a contiguous set of blocks on the
disk. For example, if a file requires n blocks and is given a block b
as the starting location, then the blocks assigned to the file will
be: b, b+1, b+2,……b+n-1. This means that given the starting
block address and the length of the file (in terms of blocks
required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
• Address of starting block
• Length of the allocated portion.
• The file ‘mail’ in the following figure starts from the block 19 with
length = 6 blocks. Therefore, it occupies 19, 20, 21, 22, 23,
24 blocks.
Contiguous Allocation -Diagram
 1. Contiguous Allocation
Advantages:
• This is extremely fast since the number of seeks are minimal
because of contiguous allocation of file blocks.
Disadvantages:
• This method suffers from both internal and external
fragmentation. This makes it inefficient in terms of memory
utilization.
• Increasing file size is difficult because it depends on the
availability of contiguous memory at a particular instance.
 2. Linked List Allocation
• In this scheme, each file is a linked list of disk blocks
which need not be contiguous. The disk blocks can be
scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the
ending file block. Each block contains a pointer to the next
block occupied by the file.
• The file ‘jeep’in following image shows how the blocks are
randomly distributed. The last block (25) contains -1
indicating a null pointer and does not point to any other block.
2. Linked List Allocation
 2. Linked List Allocation
• Advantages:
• This is very flexible in terms of file size. File size can be
increased easily since the system does not have to look for a
contiguous chunk of memory.
• Disadvantages:
• Because the file blocks are distributed randomly on the disk,
a large number of seeks are needed to access every block
individually. This makes linked allocation slower.
• Pointers required in the linked allocation incur some extra
overhead.
 3. Indexed Allocation
• In this scheme, a special block known as the Index
block contains the pointers to all the blocks occupied by a
file. Each file has its own index block. The ith entry in the
index block contains the disk address of the ith file block.
The directory entry contains the address of the index block
as shown in the image:
 Indexed Allocation
• Advantages:
• This supports direct access to the blocks occupied by the file
and therefore provides fast access to the file blocks.
• Disadvantages:
• The pointer overhead for indexed allocation is greater than
linked allocation.
• For very small files, say files that expand only 2-3 blocks, the
indexed allocation would keep one entire block (index block)
for the pointers which is inefficient in terms of memory
utilization