What is an Operating System?

An operating system is a software which acts as an interface between the end user and
computer hardware. Every computer must have at least one OS to run other programs.
An application like Chrome, MS Word, Games, etc needs some environment in which it
will run and perform its task.

The OS helps you to communicate with the computer without knowing how to speak the
computer's language. It is not possible for the user to use any computer or mobile
device without having an operating system.

Here is a list of Operating Systems with the latest MarketShare

OS Name Share

Windows 40.34

Android 37.95

iOS 15.44

Mac OS 4.34
Linux 0.95

Chrome OS 0.14

Windows Phone OS 0.06

History Of OS
 Operating systems were first developed in the late 1950s to manage tape
storage
 The General Motors Research Lab implemented the first OS in the early 1950s
for their IBM 701
 In the mid-1960s, operating systems started to use disks
 In the late 1960s, the first version of the Unix OS was developed
 The first OS built by Microsoft was DOS. It was built in 1981 by purchasing the
86-DOS software from a Seattle company
 The present-day popular OS Windows first came to existence in 1985 when a
GUI was created and paired with MS-DOS.

Features of Operating System

Here is a list commonly found important features of an Operating System:

 Protected and supervisor mode

 Allows disk access and file systems Device drivers Networking Security
 Program Execution
 Memory management Virtual Memory Multitasking
 Handling I/O operations
 Manipulation of the file system
 Error Detection and handling
 Resource allocation
 Information and Resource Protection
What is a Kernel?
The kernel is the central component of a computer operating systems. The only job
performed by the kernel is to the manage the communication between the software and
the hardware. A Kernel is at the nucleus of a computer. It makes the communication
between the hardware and software possible. While the Kernel is the innermost part of
an operating system, a shell is the outermost one.

Features of Kennel
  Low-level scheduling of processes
 Inter-process communication
 Process synchronization
 Context switching

Types of Kernels

There are many types of kernels that exists, but among them, the two most popular
kernels are:

[Link]

A monolithic kernel is a single code or block of the program. It provides all the required
services offered by the operating system. It is a simplistic design which creates a
distinct communication layer between the hardware and software.

2. Microkernels

Microkernel manages all system resources. In this type of kernel, services are
implemented in different address space. The user services are stored in user address
space, and kernel services are stored under kernel address space. So, it helps to
reduce the size of both the kernel and operating system.

Functions of an Operating System

Function of an Operating System

In an operating system software performs each of the function:

1. Process management:- Process management helps OS to create and delete

processes. It also provides mechanisms for synchronization and communication
among processes.
 2. Memory management:- Memory management module performs the task of
allocation and de-allocation of memory space to programs in need of this
resources.

3. File management:- It manages all the file-related activities such as organization

storage, retrieval, naming, sharing, and protection of files.

4. Device Management: Device management keeps tracks of all devices. This

module also responsible for this task is known as the I/O controller. It also
performs the task of allocation and de-allocation of the devices.

5. I/O System Management: One of the main objects of any OS is to hide the
peculiarities of that hardware devices from the user.

6. Secondary-Storage Management: Systems have several levels of storage

which includes primary storage, secondary storage, and cache storage.
Instructions and data must be stored in primary storage or cache so that a
running program can reference it.

7. Security:- Security module protects the data and information of a computer

system against malware threat and authorized access.

8. Command interpretation: This module is interpreting commands given by the

and acting system resources to process that commands.

9. Networking: A distributed system is a group of processors which do not share

memory, hardware devices, or a clock. The processors communicate with one
another through the network.

10. Job accounting: Keeping track of time & resource used by various job and
users.

11. Communication management: Coordination and assignment of compilers,

interpreters, and another software resource of the various users of the computer
systems.

Types of Operating system

 Batch Operating System
 Multitasking/Time Sharing OS
 Multiprocessing OS
 Real Time OS
 Distributed OS
 Network OS
 Mobile OS
Batch Operating System

Some computer processes are very lengthy and time-consuming. To speed the same
process, a job with a similar type of needs are batched together and run as a group.

The user of a batch operating system never directly interacts with the computer. In this
type of OS, every user prepares his or her job on an offline device like a punch card and
submit it to the computer operator.

Multi-Tasking/Time-sharing Operating systems

Time-sharing operating system enables people located at a different terminal(shell) to

use a single computer system at the same time. The processor time (CPU) which is
shared among multiple users is termed as time sharing.

Real time OS

A real time operating system time interval to process and respond to inputs is very
small. Examples: Military Software Systems, Space Software Systems.

Distributed Operating System

Distributed systems use many processors located in different machines to provide very
fast computation to its users.

Network Operating System

Network Operating System runs on a server. It provides the capability to serve to

manage data, user, groups, security, application, and other networking functions.

Mobile OS

Mobile operating systems are those OS which is especially that are designed to power
smartphones, tablets, and wearables devices.

Difference between 32-Bit vs. 64 Bit Operating

System
The advantage of using Operating System
 Allows you to hide details of hardware by creating an abstraction
 Easy to use with a GUI
 Offers an environment in which a user may execute programs/applications
 The operating system must make sure that the computer system convenient to
use
 Operating System acts as an intermediary among applications and the hardware
components
 It provides the computer system resources with easy to use format
 Acts as an intermediator between all hardware's and software's of the system

Disadvantages of using Operating System

 If any issue occurs in OS, you may lose all the contents which have been stored
in your system
 Operating system's software is quite expensive for small size organization which
adds burden on them. Example Windows
 It is never entirely secure as a threat can occur at any time

Summary
 An operating system is a software which acts as an interface between the end
user and computer hardware
 Operating systems were first developed in the late 1950s to manage tape
storage
 The kernel is the central component of a computer operating systems. The only
job performed by the kernel is to the manage the communication between the
software and the hardware
 Two most popular kernels are Monolithic and MicroKernels
 Process, Device, File, I/O, Secondary-Storage, Memory management are various
functions of an Operating System
 Batch, Multitasking/Time Sharing, Multiprocessing, Real Time, Distributed,
Network, Mobile are various types of Operating Systems

Introduction of Process Management

Program vs Process
A process is a program in execution. For example, when we write a
program in C or C++ and compile it, the compiler creates 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, as opposed to a program, which is
considered to be 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).
What does a process look like in memory?

Text Section:A Process, sometimes known as the Text Section, also

includes the current activity represented by the value of the Program
Counter.
Stack: The Stack contains the temporary data, such as function
parameters, returns addresses, and local variables.
Data Section: Contains the global variable.
Heap Section: Dynamically allocated memory to process during its
run time.
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 Switching
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 running state
to ready state.
When does context switching happen?
1. When a high-priority process comes to ready state (i.e. with higher
priority than the running process)
2. An Interrupt occurs
3. User and kernel mode switch (It is not necessary though)
4. Preemptive CPU scheduling used.
Context Switch vs Mode Switch
A mode switch occurs when 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 which 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.

Exercise:
1. Which of the following need not necessarily be saved on a context
switch between processes? (GATE-CS-2000)
(A) General purpose registers
(B) Translation lookaside buffer
(C) Program counter
(D) All of the above
Answer (B)
Explanation:
In a process context switch, the state of the first process must be
saved somehow, so that when the scheduler gets back to the
execution of the first process, it can restore this state and continue.
The state of the process includes all the registers that the process
may be using, especially the program counter, plus any other
operating system-specific data that may be necessary. A translation
look-aside buffer (TLB) is a CPU cache that memory management
hardware uses to improve virtual address translation speed. A TLB
has a fixed number of slots that contain page table entries, which map
virtual addresses to physical addresses. On a context switch, some
TLB entries can become invalid, since the virtual-to-physical mapping
is different. The simplest strategy to deal with this is to completely
flush the TLB.
2. The time taken to switch between user and kernel modes of
execution is t1 while the time taken to switch between two processes
is t2. Which of the following is TRUE? (GATE-CS-2011)
(A) t1 > t2
(B) t1 = t2
(C) t1 < t2
(D) nothing can be said about the relation between t1 and t2.
Answer: (C)
Explanation: Process switching involves mode switch. Context
switching can occur only in kernel mode.

CPU Scheduling
CPU scheduling is a process which allows one process to use the
CPU while the execution of another process is on hold(in waiting
state) due to unavailability of any resource like I/O etc, thereby making
full use of CPU. The aim of CPU scheduling is to make the system
efficient, fast and fair.
Whenever the CPU becomes idle, the operating system must select
one of the processes in the ready queue to be executed. The
selection process is carried out by the short-term scheduler (or CPU
scheduler). The scheduler selects from among the processes in
memory that are ready to execute, and allocates the CPU to one of
them.

CPU Scheduling: Dispatcher

Another component involved in the CPU scheduling function is
the Dispatcher. The dispatcher is the module that gives control of the
CPU to the process selected by the short-term scheduler. This
function involves:

 Switching context
 Switching to user mode
 Jumping to the proper location in the user program to restart that
program from where it left last time.
The dispatcher should be as fast as possible, given that it is invoked
during every process switch. The time taken by the dispatcher to stop
one process and start another process is known as the Dispatch
Latency. Dispatch Latency can be explained using the below figure:

Types of CPU Scheduling

CPU scheduling decisions may take place under the following four
circumstances:

1. When a process switches from the running state to

the waiting state(for I/O request or invocation of wait for the
termination of one of the child processes).
2. When a process switches from the running state to
the ready state (for example, when an interrupt occurs).
3. When a process switches from the waiting state to
the ready state(for example, completion of I/O).
4. When a process terminates.
In circumstances 1 and 4, there is no choice in terms of scheduling. A
new process(if one exists in the ready queue) must be selected for
execution. There is a choice, however in circumstances 2 and 3.
When Scheduling takes place only under circumstances 1 and 4, we
say the scheduling scheme is non-preemptive; otherwise the
scheduling scheme is preemptive.

Non-Preemptive Scheduling
Under non-preemptive scheduling, once the CPU has been allocated
to a process, the process keeps the CPU until it releases the CPU
either by terminating or by switching to the waiting state.
This scheduling method is used by the Microsoft Windows 3.1 and by
the Apple Macintosh operating systems.
It is the only method that can be used on certain hardware platforms,
because It does not require the special hardware(for example: a timer)
needed for preemptive scheduling.

Preemptive Scheduling
In this type of Scheduling, the tasks are usually assigned with
priorities. At times it is necessary to run a certain task that has a
higher priority before another task although it is running. Therefore,
the running task is interrupted for some time and resumed later when
the priority task has finished its execution.

CPU Scheduling: Scheduling Criteria

There are many different criterias to check when considering
the "best" scheduling algorithm, they are:
CPU Utilization
To make out the best use of CPU and not to waste any CPU cycle,
CPU would be working most of the time(Ideally 100% of the time).
Considering a real system, CPU usage should range from 40% (lightly
loaded) to 90% (heavily loaded.)
Throughput
It is the total number of processes completed per unit time or rather
say total amount of work done in a unit of time. This may range from
10/second to 1/hour depending on the specific processes.
Turnaround Time
It is the amount of time taken to execute a particular process, i.e. The
interval from time of submission of the process to the time of
completion of the process(Wall clock time).
Waiting Time
The sum of the periods spent waiting in the ready queue amount of
time a process has been waiting in the ready queue to acquire get
control on the CPU.
Load Average
It is the average number of processes residing in the ready queue
waiting for their turn to get into the CPU.
Response Time
Amount of time it takes from when a request was submitted until the
first response is produced. Remember, it is the time till the first
response and not the completion of process execution(final response).
In general CPU utilization and Throughput are maximized and other
factors are reduced for proper optimization.

Scheduling Algorithms
To decide which process to execute first and which process to
execute last to achieve maximum CPU utilisation, computer scientists
have defined some algorithms, they are:

1. First Come First Serve(FCFS) Scheduling

2. Shortest-Job-First(SJF) Scheduling
3. Priority Scheduling
4. Round Robin(RR) Scheduling
5. Multilevel Queue Scheduling

First Come First Serve

Scheduling
In the "First come first serve" scheduling algorithm, as the name
suggests, the process which arrives first, gets executed first, or we
can say that the process which requests the CPU first, gets the CPU
allocated first.

 First Come First Serve, is just like FIFO(First in First out) Queue
data structure, where the data element which is added to the
queue first, is the one who leaves the queue first.
 This is used in Batch Systems.
 It's easy to understand and implement programmatically,
using a Queue data structure, where a new process enters
through the tail of the queue, and the scheduler selects process
from the head of the queue.
 A perfect real life example of FCFS scheduling is buying tickets
at ticket counter.
Calculating Average Waiting Time
For every scheduling algorithm, Average waiting time is a crucial
parameter to judge it's performance.
AWT or Average waiting time is the average of the waiting times of the
processes in the queue, waiting for the scheduler to pick them for
execution.
Lower the Average Waiting Time, better the scheduling algorithm.
Consider the processes P1, P2, P3, P4 given in the below table,
arrives for execution in the same order, with Arrival Time 0, and
given Burst Time, let's find the average waiting time using the FCFS
scheduling algorithm.

The average waiting time will be 18.75 ms

For the above given proccesses, first P1 will be provided with the CPU
resources,
  Hence, waiting time for P1 will be 0
 P1 requires 21 ms for completion, hence waiting time for P2 will
be 21 ms
 Similarly, waiting time for process P3 will be execution time
of P1 + execution time for P2, which will be (21 + 3) ms = 24 ms.
 For process P4 it will be the sum of execution times
of P1, P2 and P3.

Problems with FCFS Scheduling

Below we have a few shortcomings or problems with the FCFS
scheduling algorithm:

1. It is Non Pre-emptive algorithm, which means the process

priority doesn't matter.

If a process with very least priority is being executed, more

like daily routine backup process, which takes more time, and
all of a sudden some other high priority process arrives,
like interrupt to avoid system crash, the high priority process
will have to wait, and hence in this case, the system will crash,
just because of improper process scheduling.

2. Not optimal Average Waiting Time.

3. Resources utilization in parallel is not possible, which leads
to Convoy Effect, and hence poor resource(CPU, I/O etc)
utilization.
What is Convoy Effect?
Convoy Effect is a situation where many processes, who need to use
a resource for short time are blocked by one process holding that
resource for a long time.
This essentially leads to poort utilization of resources and hence poor
performance.

Program for FCFS Scheduling

Here we have a simple C++ program for processes with arrival
time as 0.
In the program, we will be calculating the Average waiting
time and Average turn around time for a given array of Burst
times for the list of processes.

Shortest Job First(SJF)

Scheduling
Shortest Job First scheduling works on the process with the
shortest burst time or duration first.

 This is the best approach to minimize waiting time.

 This is used in Batch Systems.
 It is of two types:
1. Non Pre-emptive
2. Pre-emptive
  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 scheduling algorithm is optimal if all the jobs/processes are
available at the same time. (either Arrival time is 0 for all, or
Arrival time is same for all)

Non Pre-emptive Shortest Job First

Consider the below processes available in the ready queue for
execution, with arrival time as 0 for all and given burst times.

As you can see in the GANTT chart above, the process P4 will be
picked up first as it has the shortest burst time, then P2, followed
by P3 and at last P1.
Problem with Non Pre-emptive SJF
If the arrival time for processes are different, which means all the
processes are not available in the ready queue at time 0, and some
jobs arrive after some time, in such situation, sometimes process with
short burst time have to wait for the current process's execution to
finish, because in Non Pre-emptive SJF, on arrival of a process with
short duration, the existing job/process's execution is not
halted/stopped to execute the short job first.
This leads to the problem of Starvation, where a shorter process has
to wait for a long time until the current longer process gets executed.
This happens if shorter jobs keep coming, but this can be solved using
the concept of aging.

Pre-emptive Shortest Job First

In Preemptive Shortest Job First Scheduling, jobs are put into ready
queue as they arrive, but as a process with short burst time arrives,
the existing process is preempted or removed from execution, and the
shorter job is executed first.
As you can see in the GANTT chart above, as P1 arrives first, hence
it's execution starts immediately, but just after 1 ms,
process P2 arrives with a burst time of 3 ms which is less than the
burst time of P1, hence the process P1(1 ms done, 20 ms left) is
preemptied and process P2 is executed.
As P2 is getting executed, after 1 ms, P3 arrives, but it has a burst
time greater than that of P2, hence execution of P2 continues. But
after another millisecond, P4 arrives with a burst time of 2 ms, as a
result P2(2 ms done, 1 ms left) is preemptied and P4 is executed.
After the completion of P4, process P2 is picked up and finishes,
then P2 will get executed and at last P1.
The Pre-emptive SJF is also known as Shortest Remaining Time
First, because at any given point of time, the job with the shortest
remaining time is executed first.
Priority Scheduling
 Priority is assigned for each process.
 Process with highest priority is executed first and so on.
 Processes with same priority are executed in FCFS manner.
 Priority can be decided based on memory requirements, time
requirements or any other resource requirement.

Round Robin Scheduling

 A fixed time is allotted to each process, called quantum, for
execution.
 Once a process is executed for given time period that process is
preemptied and other process executes for given time period.
 Context switching is used to save states of preemptied
processes.

Multilevel Queue Scheduling

Another class of scheduling algorithms has been created for situations
in which processes are easily classified into different groups.
For example: A common division is made between foreground(or
interactive) processes and background (or batch) processes. These
two types of processes have different response-time requirements,
and so might have different scheduling needs. In addition, foreground
processes may have priority over background processes.
A multi-level queue scheduling algorithm partitions the ready queue
into several separate queues. The processes are permanently
assigned to one queue, generally based on some property of the
process, such as memory size, process priority, or process type. Each
queue has its own scheduling algorithm.
For example: separate queues might be used for foreground and
background processes. The foreground queue might be scheduled by
Round Robin algorithm, while the background queue is scheduled by
an FCFS algorithm.
In addition, there must be scheduling among the queues, which is
commonly implemented as fixed-priority preemptive scheduling. For
example: The foreground queue may have absolute priority over the
background queue.

Let us consider an example of a multilevel queue-scheduling algorithm

with five queues:

1. System Processes
2. Interactive Processes
3. Interactive Editing Processes
4. Batch Processes
5. Student Processes

Each queue has absolute priority over lower-priority queues. No process

in the batch queue, for example, could run unless the queues for system
processes, interactive processes, and interactive editing processes were
all empty. If an interactive editing process entered the ready queue while
a batch process was running, the batch process will be preempted.
Multilevel Feedback Queue
Scheduling
In a multilevel queue-scheduling algorithm, processes are
permanently assigned to a queue on entry to the system. Processes
do not move between queues. This setup has the advantage of low
scheduling overhead, but the disadvantage of being inflexible.
Multilevel feedback queue scheduling, however, allows a process to
move between queues. The idea is to separate processes with
different CPU-burst characteristics. If a process uses too much CPU
time, it will be moved to a lower-priority queue. Similarly, a process
that waits too long in a lower-priority queue may be moved to a higher-
priority queue. This form of aging prevents starvation.
In general, a multilevel feedback queue scheduler is defined by the
following parameters:

 The number of queues.

 The scheduling algorithm for each queue.
 The method used to determine when to upgrade a process to a
higher-priority queue.
 The method used to determine when to demote a process to a
lower-priority queue.
 The method used to determine which queue a process will enter
when that process needs service.

The definition of a multilevel feedback queue scheduler makes it the

most general CPU-scheduling algorithm. It can be configured to match
a specific system under design. Unfortunately, it also requires some
means of selecting values for all the parameters to define the best
scheduler. Although a multilevel feedback queue is the most general
scheme, it is also the most complex.
Introduction of Deadlock in Operating
System
A process in operating systems uses different resources and uses
resources in following way.
1) Requests a resource
2) Use the resource
2) Releases the resource

Deadlock is a situation where a set of processes are blocked because

each process is holding a resource and waiting for another resource
acquired by some other process.
Consider an example when two trains are coming toward each other
on same track and there is only one track, none of the trains can move
once they are in front of each other. Similar situation occurs in
operating systems when there are two or more processes hold some
resources and wait for resources held by other(s). For example, in the
below diagram, 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 can arise if following four conditions hold
simultaneously (Necessary Conditions)
Mutual Exclusion: One or more than one resource are non-sharable
(Only one process can use at a time)
Hold and Wait: A process is holding at least one resource and waiting
for resources.
No Preemption: A resource cannot be taken from a process unless
the process releases the resource.
Circular Wait: A set of processes are waiting for each other in circular
form.

Methods for handling deadlock

There are three ways to handle deadlock
1) Deadlock prevention or avoidance: The idea is to not let the system
into deadlock state.
One can zoom into each category individually, Prevention is done by
negating one of above mentioned necessary conditions for deadlock.
Avoidance is kind of futuristic in nature. By using strategy of
“Avoidance”, we have to make an assumption. We need to ensure that
all information about resources which process WILL need are known
to us prior to execution of the process. We use Banker’s algorithm
(Which is in-turn a gift from Dijkstra) in order to avoid deadlock.
2) Deadlock detection and recovery: Let deadlock occur, then do
preemption to handle it once occurred.
3) Ignore the problem all together: If deadlock is very rare, then let it
happen and reboot the system. This is the approach that both
Windows and UNIX take.

Introduction to Memory Management

Main Memory refers to a physical memory that is the internal memory
to the computer. The word main is used to distinguish it from external
mass storage devices such as disk drives. Main memory is also
known as RAM. The computer is able to change only data that is in
main memory. Therefore, every program we execute and every file we
access must be copied from a storage device into main memory.
All the programs are loaded in the main memeory for execution.
Sometimes complete program is loaded into the memory, but some
times a certain part or routine of the program is loaded into the main
memory only when it is called by the program, this mechanism is
called Dynamic Loading, this enhance the performance.
Also, at times one program is dependent on some other program. In
such a case, rather than loading all the dependent programs, CPU
links the dependent programs to the main executing program when its
required. This mechanism is known as Dynamic Linking.

Swapping
A process needs to be in memory for execution. But sometimes there
is not enough main memory to hold all the currently active processes
in a timesharing system. So, excess process are kept on disk and
brought in to run dynamically. Swapping is the process of bringing in
each process in main memory, running it for a while and then putting it
back to the disk.
Contiguous Memory Allocation
In contiguous memory allocation each process is contained in a single
contiguous block of memory. Memory is divided into several fixed size
partitions. Each partition contains exactly one process. When a
partition is free, a process is selected from the input queue and loaded
into it. The free blocks of memory are known as holes. The set of
holes is searched to determine which hole is best to allocate.

Memory Protection
Memory protection is a phenomenon by which we control memory
access rights on a computer. The main aim of it is to prevent a
process from accessing memory that has not been allocated to it.
Hence prevents a bug within a process from affecting other
processes, or the operating system itself, and instead results in a
segmentation fault or storage violation exception being sent to the
disturbing process, generally killing of process.

Memory Allocation
Memory allocation is a process by which computer programs are
assigned memory or space. It is of three types :

1. First Fit:

The first hole that is big enough is allocated to program.

2. Best Fit:

The smallest hole that is big enough is allocated to program.

3. Worst Fit:
 The largest hole that is big enough is allocated to program.

Fragmentation
Fragmentation occurs in a dynamic memory allocation system when
most of the free blocks are too small to satisfy any request. It is
generally termed as inability to use the available memory.
In such situation processes are loaded and removed from the
memory. As a result of this, free holes exists to satisfy a request but is
non contiguous i.e. the memory is fragmented into large no. Of small
holes. This phenomenon is known as External Fragmentation.
Also, at times the physical memory is broken into fixed size blocks and
memory is allocated in unit of block sizes. The memory allocated to a
space may be slightly larger than the requested memory. The
difference between allocated and required memory is known
as Internal fragmentation i.e. the memory that is internal to a
partition but is of no use.

Paging
A solution to fragmentation problem is Paging. Paging is a memory
management mechanism that allows the physical address space of a
process to be non-contagious. Here physical memory is divided into
blocks of equal size called Pages. The pages belonging to a certain
process are loaded into available memory frames.

Page Table
A Page Table is the data structure used by a virtual memory system in
a computer operating system to store the mapping between virtual
address and physical addresses.
Virtual address is also known as Logical address and is generated by
the CPU. While Physical address is the address that actually exists on
memory.

Segmentation
Segmentation is another memory management scheme that supports
the user-view of memory. Segmentation allows breaking of the virtual
address space of a single process into segments that may be placed
in non-contiguous areas of physical memory.

Segmentation with Paging

Both paging and segmentation have their advantages and
disadvantages, it is better to combine these two schemes to improve
on each. The combined scheme is known as 'Page the Elements'.
Each segment in this scheme is divided into pages and each segment
is maintained in a page table. So the logical address is divided into
following 3 parts :

 Segment numbers(S)
 Page number (P)
 The displacement or offset number (D)

What is Virtual Memory?

Virtual Memory is a space where large programs can store
themselves in form of pages while their execution and only the
required pages or portions of processes are loaded into the main
memory. This technique is useful as large virtual memory is provided
for user programs when a very small physical memory is there.
In real scenarios, most processes never need all their pages at once,
for following reasons :

 Error handling code is not needed unless that specific error

occurs, some of which are quite rare.
 Arrays are often over-sized for worst-case scenarios, and only a
small fraction of the arrays are actually used in practice.
 Certain features of certain programs are rarely used.

Benefits of having Virtual Memory

1. Large programs can be written, as virtual space available is huge

compared to physical memory.
2. Less I/O required, leads to faster and easy swapping of
processes.
3. More physical memory available, as programs are stored on
virtual memory, so they occupy very less space on actual
physical memory.

What is Demand Paging?

The basic idea behind demand paging is that when a process is
swapped in, its pages are not swapped in all at once. Rather they are
swapped in only when the process needs them(On demand). This is
termed as lazy swapper, although a pager is a more accurate term.
Initially only those pages are loaded which will be required the process
immediately.
The pages that are not moved into the memory, are marked as invalid
in the page table. For an invalid entry the rest of the table is empty. In
case of pages that are loaded in the memory, they are marked as
valid along with the information about where to find the swapped out
page.
When the process requires any of the page that is not loaded into the
memory, a page fault trap is triggered and following steps are
followed,

1. The memory address which is requested by the process is first

checked, to verify the request made by the process.
2. If its found to be invalid, the process is terminated.
 3. In case the request by the process is valid, a free frame is
located, possibly from a free-frame list, where the required page
will be moved.
4. A new operation is scheduled to move the necessary page from
disk to the specified memory location. ( This will usually block the
process on an I/O wait, allowing some other process to use the
CPU in the meantime. )
5. When the I/O operation is complete, the process's page table is
updated with the new frame number, and the invalid bit is
changed to valid.
6. The instruction that caused the page fault must now be restarted
from the beginning.

There are cases when no pages are loaded into the memory initially,
pages are only loaded when demanded by the process by generating
page faults. This is called Pure Demand Paging.
The only major issue with Demand Paging is, after a new page is
loaded, the process starts execution from the beginning. Its is not a
big issue for small programs, but for larger programs it affects
performance drastically.

Page Replacement
As studied in Demand Paging, only certain pages of a process are
loaded initially into the memory. This allows us to get more number of
processes into the memory at the same time. but what happens when
a process requests for more pages and no free memory is available to
bring them in. Following steps can be taken to deal with this problem :
 1. Put the process in the wait queue, until any other process
finishes its execution thereby freeing frames.
2. Or, remove some other process completely from the memory to
free frames.
3. Or, find some pages that are not being used right now, move
them to the disk to get free frames. This technique is called Page
replacement and is most commonly used. We have some great
algorithms to carry on page replacement efficiently.

Basic Page Replacement

 Find the location of the page requested by ongoing process on

the disk.
 Find a free frame. If there is a free frame, use it. If there is no
free frame, use a page-replacement algorithm to select any
existing frame to be replaced, such frame is known as victim
frame.
 Write the victim frame to disk. Change all related page tables to
indicate that this page is no longer in memory.
 Move the required page and store it in the frame. Adjust all
related page and frame tables to indicate the change.
 Restart the process that was waiting for this page.
 FIFO Page Replacement

 A very simple way of Page replacement is FIFO (First in First

Out)
 As new pages are requested and are swapped in, they are
added to tail of a queue and the page which is at the head
becomes the victim.
 Its not an effective way of page replacement but can be used for
small systems.