Module 4 Memory

Management
Curriculum
• Basic Concepts of Memory Management: Swapping, Memory
Allocation strategy, Paging, Structure of Page Table, Segmentation,
TLB.
• Basic Concepts of Virtual Memory, Demand Paging, Copy-on Write,
Page Replacement Algorithms, Thrashing.
• While registers and cache memory are closer to the processor that a
processor can directly access, they are very expensive and thus of
very small capacity.
• They cannot accommodate either the operating system or other
programs that are executed by the processor.
• Main memory is the furthest memory unit from a processor that it
can directly access which can accommodate the OS as well as user
applications during their execution.
• Processors make all memory references with respect to this memory.
• Main memory is volatile in nature - it keeps the code and data (both
for system and application programs) as long as the computer is on.
• Both the OS and other programs need to be loaded on the main
memory from the secondary or tertiary memory after each start-up
and/or execution.
Memory Management
It is the process of controlling and organising a computer’s memory by
allocating portions, called blocks, to different executing programmes to
improve the overall system performance. It performs following
functions
• To keep track of all memory locations-free or allocated and if
allocated, to which process and how much.
• To decide the memory allocation policy i.e. which process should get
how much memory, when and where.
• To use various techniques and algorithms to allocate and de-allocate
memory locations.
Memory Image
• A memory image (RAM image or memory dump) is a file that
contains the exact state of system memory.
• It includes:
➢Running processes and their data
➢Operating system kernel data
➢Open network connections
➢Passwords or encryption keys temporarily stored in RAM
➢Stacks, heaps, and program instructions
Swapping
• Swapping in the operating system is a memory management scheme
that temporarily swaps out an idle or blocked process from the main
memory to secondary memory which ensures proper memory
utilization and memory availability for those processes which are
ready to be executed.
• Swapping is a memory management technique in which a process is
temporarily moved from main memory (RAM) to secondary storage
(disk) and vice versa. This allows the operating system to manage
limited RAM effectively and run multiple processes concurrently in a
multiprogramming environment.
Swapping
Roll Out
If a higher priority process arrives and wants service, the memory
manager can swap out the lower priority process so that it can load
higher priority process and execute it.
Roll in
When the higher priority process finishes, the lower priority process
can be swapped back in and continued.
Swapping
Swap In:
• The method of removing a process from secondary memory (Hard Drive)
and restoring it to the main memory (RAM ) for execution is known as
the Swap In method.
Swap Out:
• It is a method of bringing out a process from the main memory(RAM) and
sending it to the secondary memory(hard drive) so that the processes with
higher priority or more memory consumption will be executed known as
the Swap Out method.
• The secondary disc also known as backing store is a fast disc. It must be
large enough to accommodate copies of all memory images.
• The system maintains a ready queue of all the processes whose memory
images are on the backing store or in memory and are ready to run.
Swapping
 Advantages
• Helps in achieving the goal of Maximum CPU Utilization.
• Ensures proper memory availability for every process that needs to be executed.
• Helps avoid the problem of process starvation means a process should not take
much time for execution so that the next process should be executed.
• CPU can perform various tasks simultaneously with the help of swapping so that
processes do not have to wait much longer before execution.
• Ensures proper RAM(main memory) utilization.
• Creates a dedicated disk partition in the hard drive for swapped processes which
is called swap space.
• Is an economical process.
• Can be applied on priority-based process scheduling where a high
priority process is swapped in and a low priority process is swapped out which
improves the performance.
Disadvantages
• If the system deals with power-cut during bulky swapping activity
then the user may lose all the information which is related to the
program.
• If the swapping method uses an algorithm that is not up to the mark
then the number of page faults can be increased and therefore this
decreases the complete performance.
• There may be inefficiency in a case when there is some common
resource used by the processes that are participating in the swapping
process.
Techniques in Memory Allocation
Contiguous Memory Allocation
• It is a memory management technique that involves allocating a
process to the entire contiguous block of the main memory it requires
to execute.
• The process is loaded into a single continuous chunk of memory.
• All instructions and data of a process are stored in adjacent memory
locations.
Single Contiguous Memory Allocation
• The main memory is divided into two parts:
➢One part is reserved for the Operating System
➢The remaining part is allocated to a single user processes
• Characteristics
• Only one user process can reside in memory at a time
• The operating system occupies a fixed portion of memory
• No multiprogramming is possible
• Simple to implement and manage
Single Contiguous Memory Allocation
Advantages
• Simple memory management
• No fragmentation issues
Disadvantages
• Poor memory utilization
• No support for multitasking or multiprogramming
 Partitioned Memory Allocation
• Main memory is divided into multiple contiguous partitions, and each partition
can hold one process.
• This technique supports multiprogramming.
• It is further partitioned into:
Fixed Partition Allocation
• Memory is divided into a fixed number of partitions
• Each partition has a fixed size
• Each partition can store only one process
• Leads to internal fragmentation
• Once partitions are defined operating system keeps track of the status
of memory partitions it is done through a data structure called a partition
table.
Fixed Partition Allocation
Advantages:
• Simple to implement as all blocks are of same size. Implemented
by dividing the memory into fixed blocks and assign processes to
them.
• Easy to keep track of how many blocks of memory are left, which
in turn decides how many more processes can be given space in
the memory.
• As at a time multiple processes can be kept in the memory, this
scheme can be implemented in a system that needs
multiprogramming.
Disadvantages:
• As the size of the blocks is fixed, a process that has a greater size
than the block cannot be allocated space.
• The size of the blocks decides the degree of multiprogramming,
and only that many processes can remain in the memory at once
as the number of blocks.
• If the size of the block is greater than the size of the process, we
have no other choice but to assign the process to this block, but
this will lead to much empty space left behind in the block. This
empty space could've been used to accommodate a different
process. This is called internal fragmentation. Hence, this
technique may lead to space wastage.
Variable Partition Allocation (Dynamic Partioning)
• Memory is divided into partitions dynamically based on process size
• Reduces internal fragmentation
• Suffers from external fragmentation
• Advantages
• Supports multiprogramming
• Better memory utilization compared to single contiguous allocation
• Disadvantages
• Fragmentation issues
• Complex memory management compared to single contiguous
allocation
Solution

• External fragmentation problem can be resolved by coalescing holes

and storage compaction. Coalescing holes is process of merging
existing hole adjacent to a process that will terminate and free its
allocated space. Thus, new adjacent holes and existing holes can be
viewed as a single large hole and can be efficiently utilized.
• For utilising such scattered holes, shuffle all occupied areas of
memory to one end and leave all free memory space as a single large
block which can further be utilized. This mechanism is known as
Storage Compaction.
Advantages:
• No Internal Fragmentation
• Since the partitions present in dynamic partitioning are only created according
to the requirement of the process, there won’t be any internal fragmentation
since there won’t be any remaining unused space in the given partition.
• No Limitation on the Process Size
• In the case of fixed partitioning, the process that has a size greater than the
actual size of the largest partition couldn’t be executed because of the
shortage of sufficient contiguous memory. On the other hand, the process size
can’t be restricted in dynamic partitioning because the size of the partition is
decided in accordance with the size of the process.
• Dynamic Degree of Multiprogramming
• Since there is no internal fragmentation, there won’t be any unused,
unutilized space in the partition. Thus, more processes could be loaded at the
same time in the memory.
Disadvantages:
• External Fragmentation
• Since there is no internal fragmentation, it doesn’t mean there would be no
external fragmentation either.
• Consider three processes, i.e. P1 (1 MB), P2 (3 MB) and P3 (1 MB), that are
being loaded in their respective partitions of the main memory. P1 and P3 get
completed after some time, and the assigned space gets freed. Here, two
unused partitions are available (both 1MB) in the main memory. However,
they cannot be used to load 2MB processes in the memory because they
aren’t located contiguously.
• This rule says that a process has to be present contiguously in the main
memory so as to get executed. One needs to change this rule in order to avoid
external fragmentation.
 Limitations of storage compaction
1. It requires extra overheads in terms of
resource utilization and large response time.
2. Compaction is required frequently because
jobs terminate rapidly. This enhances system
resource consumption and makes
compaction expensive.
3. Compaction is possible only if dynamic
relocation is being used (at runtime). This is
because the memory contents that are
Compaction shuffled (i.e., relocated) and executed in new
location require all internal addresses to be
relocated.
Disadvantages:
• Complex Memory Allocation
• In the case of fixed partitioning, the overall list of partitions is
created once, and it won’t ever change. However, the deallocation
and allocation are very complex in dynamic partitioning because the
partition size would be varied every single time when it’s assigned
to any new process. The OS must keep track of all of the partitions.
• Since deallocation and allocation are very frequently done in
dynamic allocation and the size of the partition gets changed each
time, it’s always going to be absolutely difficult for the OS to
manage every single thing.
Techniques used in Contiguous Memory
Allocation
• First Fit
• Best Fit
• Worst Fit
• Next Fit
First Fit
• Allocates the first free block that is large enough.
• Stops searching once a suitable block is found.
How it works?
• Memory contains free blocks (holes) of different sizes.
• A process requests memory.
• The OS scans from the start.
• The first hole large enough is allocated.
• If the hole is bigger than needed, it is split.
 e.g. Available Memory Blocks Process Requesting Memory
Block Size Block Size
B1 100 KB P1 212 KB
B2 500 KB P2 417 KB
B3 200 KB P3 112 KB
B4 300 KB
B5 600 KB

• Allocate P1 (212KB) => B1 Too Small => B2 is large enough => Allocate P1 to B2.
Remaining 500 − 212 = 288 KB
• Allocate P2 (417KB) => B3 , B4 Too Small => B5 is large enough => Allocate P2 to B5.
Remaining 600 − 417 = 183 KB
• Allocate P3 (112 KB) => B1 Too Small => B2 288KB remaining => Allocate P3 to B2.
Best Fit
• The OS searches through the list of free blocks of memory to find the block
that is closest in size to the memory request from the process.
• Once a suitable block is found, the operating system splits the block into
two parts: the portion that will be allocated to the process, and the
remaining free block.
Advantages:
• Reduced External Fragmentation − By allocating the smallest possible
block to a process, the Best Fit Algorithm helps in reducing external
fragmentation.
• Efficient Memory Utilization − The Best Fit Algorithm ensures that memory
is utilized efficiently by minimizing the amount of wasted space after
allocation.
• Best for Small Processes − The Best Fit Algorithm is considered to be more
suitable for small processes.
Best Fit
Disadvantages:
• High Search Time − The Best Fit Algorithm requires searching the
entire memory for the smallest suitable block, which can increase
allocation time.
• Fragmentation − Even though it reduces external fragmentation, it
can cause internal fragmentation. Because processes may not fully
utilize the allocated blocks.
• Not Suitable for Large Processes − The Best Fit Algorithm may
struggle to find suitable blocks for larger processes. This leads to
more "Not Allocated" statuses.
 e.g. Available Memory Blocks Process Requesting Memory
Block Size Block Size
B1 100 KB P1 212 KB
B2 500 KB P2 417 KB
B3 200 KB P3 112 KB
B4 300 KB
B5 600 KB

• Allocate P1 (212KB) => Smallest Suitable Block B4=> Allocate P1 to B4. Remaining space =
300 − 212 = 88KB
• Allocate P2 (417KB) => Smallest Suitable Block B2=> Allocate P2 to B2. Remaining space =
500 - 417 = 83KB
• Allocate P3 (112 KB) => Smallest Suitable Block B3=> Allocate P3 to B3. Remaining space =
200 - 112 = 88KB
Worst Fit
• The worst-fit algorithm searches for the largest free partition and
allocates the process to it. This algorithm is designed to leave the
largest possible free partition for future use.
Advantages:
• Reduces Chances of Small Fragments: By allocating the largest
available block, worst fit leaves larger leftover fragments, which are
more likely to be useful for future allocations.
• Simple to Implement: The logic is straightforward: find the largest
block that can fit the process and allocate it.
• Efficient for Large Processes: It always looks for the biggest space,
large processes may find better fits compared to other strategies like
Best Fit or First Fit.
Worst Fit
Disadvantages:
• External Fragmentation: Worst-Fit Allocation can lead to
significant external fragmentation. By allocating the largest available
block, it often leaves behind many smaller, unusable fragments of
memory.
• Inefficient Memory Usage: Allocating the largest block to a process,
even if it's much larger than required, can lead to inefficient memory
usage.
• Lower Allocation Time: Worst-Fit requires the operating system to
search for the largest available block, which can be slower than
methods like First-Fit or Next-Fit, especially if there are many free
blocks.
 e.g. Available Memory Blocks Process Requesting Memory
Block Size Block Size
B1 100 KB P1 212 KB
B2 500 KB P2 417 KB
B3 200 KB P3 112 KB
B4 300 KB
B5 600 KB

• Allocate P1 (212KB) => Largest Block B5=> Allocate P1 to B5. Remaining space = 600 − 212
= 388KB
• Allocate P2 (417KB) => Largest Block B2=> Allocate P2 to B2. Remaining space = 500 - 417
= 83KB
• Allocate P3 (112 KB) => Largest Block (388KB) => Allocate P3. Remaining space = 388 - 112
= 276KB
Next Fit
• The Next Fit algorithm is a modified version of the First Fit memory
allocation technique. While the First Fit algorithm always starts searching
from the beginning of the memory block list for each new process, the
Next Fit algorithm optimizes this behavior by continuing the search from
where it last left off.
Advantages over First Fit:
• Reduces fragmentation near the beginning: Unlike First Fit, which
continuously fills the initial part of memory, Next Fit distributes allocations
more evenly across the memory space.
• Improved performance: Since it doesn’t restart the search every time, the
average time to find a free block is reduced, making it faster than First Fit
and Best Fit in many scenarios.
• Better load balancing: Memory usage gets spread more uniformly,
reducing the chances of creating too many small fragments in a specific
region.
Worst Fit
Disadvantages:
• External Fragmentation: Still susceptible to external fragmentation
• Poor Memory Utilization: Because it continues searching from the
last position, it may skip suitable free blocks earlier in memory.
• Slower Than First Fit (In Some Cases): If the last allocation point is
near the end of memory, the algorithm may need to scan a large
portion before finding a suitable block.
• Not Optimal for Large Requests: Large memory requests may fail
even when enough total memory is available — because free space is
scattered into small pieces.
 e.g. Available Memory Blocks Process Requesting Memory
Block Size Block Size
B1 100 KB P1 212 KB
B2 500 KB P2 417 KB
B3 200 KB P3 112 KB
B4 300 KB
B5 600 KB

• Allocate P1 (212KB) => B1 not suitable Block B2 is suitable => Allocate P1 to B2.
Remaining space = 500 − 212 = 288KB
• Allocate P2 (417KB) B2, B3, B4 not suitable=> Allocate P2 to B5.
Remaining space = 600 - 417 = 183KB
• Allocate P3 (112 KB) => Block B5 183KB still available Allocate P3 to remaining memory
space in B5 . Remaining space = 183 - 112 = 71KB
Non-Contiguous Memory Allocation
• In this technique a process is divided into smaller parts and these parts are
stored in different, non-adjacent locations in main memory.
• Features
➢A process can be stored in multiple memory locations
➢Improves utilization of available memory
➢Reduces external fragmentation
➢Requires address translation using hardware support (MMU)
Primary techniques
1. Paging
2. Segmentation
3. Segmentation with Paging (Paged Segmentation)
Advantages
• Better memory utilization
• Supports large programs
• Eliminates the need for contiguous free memory
Disadvantages
• More complex than contiguous allocation
• Additional overhead for address translation
• Requires extra memory for tables (page table / segment
table)
Paging
• Paging is a memory management scheme that permits the physical
address space of a process to be non contiguous.
• Physical memory is broken into fixed size blocks called frames.
• Logical memory is broken into blocks of the same size called pages.
• Paging is the process of moving parts of a program, called pages, from
secondary storage into the main memory (RAM).
• When a process is to be executed its pages are loaded into any
available memory frames from the backing store.
Paging Hardware
Paging Hardware
• Every address generated by the CPU is divided into two parts: a page
number (p) and a page offset (d).
• The page number is used as an index into a per-process page table.
• The page table contains the base address of each page in physical
memory.
• The offset is the location within the frame being referenced.
• The base address of the frame is combined with the page offset to
define the physical memory address that is sent to the memory unit.
Paging Model of logical and physical memory
Hardware Support
• Each OS has its own methods for storing page tables.
• Hardware implementation of the page table can be done in several
ways.
• 1. The page table is implemented as a set of dedicated registers.
• These registers should be built with very high-speed logic to make the
paging-address translation efficient.
• The use of registers for the page table is satisfactory if the page table
is reasonably small
Hardware Support
• 2. The page table is kept in the main memory and the Page Table Base
Register (PTBR) points to the page table.
• Disadvantage:
• Two memory accesses are needed to access a byte. One for page
table entry and other for physical memory calculation
• Solution: Use a special small fast- lookup hardware cache called
Translation Look-aside Buffer (TLB)
 Translation Look-aside Buffer (TLB)
• The TLB is associative, high-speed memory. Each entry in the TLB consists of
two parts:
• a key (or tag) and a value.
• The TLB contains only a few of the page table entries.
• When a logical address is generated by CPU, its page number is presented to
the TLB.
• If the page number is found, its frame number is immediately available and is
used to access memory. (TLB Hit)
• TLB Miss: If the page number is not in TLB, a memory reference to the page
table must be made.
• HIT Ratio: The percentage of times that the page number of interest is found
in the TLB is called the HIT ratio.
Paging Hardware with TLB
Valid /Invalid bit
Translation Look-aside Buffer in Paging
• For each process page table will be created which contains page table
entries.
• It contains information like frame number, valid / invalid bit,
protection bit etc.
• Valid/Invalid bit:
• When this bit is set to valid, the associated page is in the process’s
logical address space and is thus a legal (or valid) page.
• When the bit is set to invalid, the page is not in the process’s logical
address space. Illegal addresses are trapped by use of the valid–
invalid bit.
Translation Lookaside Buffer in Paging
• Protection bit: Memory protection in a paged environment is
accomplished by protection bits associated with each frame. One bit
can define a page to be read–write or read-only.
• Every reference to memory goes through the page table to find the
correct frame number.
• At the same time that the physical address is being computed, the
protection bits can be checked to verify that no writes are being
made to a read-only page.
• An attempt to write to a read-only page causes a hardware trap to the
operating system
Translation Lookaside Buffer in Paging
• Given a logical address, the CPU examines the TLB. If the page table
entry is present (TLB Hit), the frame number is retrieved and the real
address is formed.
• If a page table entry is not found in the TLB (TLB Miss), the page
number is used as index and matched to page table residing in the
main memory.
• If the entry is not found in the main memory also then Page Fault is
issued.
• The TLB is updated with new page table entry. If space is not
available, one of the page replacement techniques(LRU, FIFO,….) is
used
Effective Memory Access Time
• Effective Memory Access Time = h *(c + m) + (1-h) *(c +2m)
Where
h: Hit ratio of TLB
m: Memory Access Time
c: TLB Access Time
Structure of Page Table
Three most common techniques for structuring the page tables
1. Hierarchical Paging
2. Hashed Page Tables
3. Inverted Page Tables
Hierarchical Paging
• Modern computer systems support a large logical address space
• (232 to 264). In such an environment, the page table itself becomes
excessively large.
• It becomes difficult to allocate page table contiguously in main
memory.
• Solution: Divide the page table into smaller pieces.
• One way is to use a two-level paging algorithm, in which the page
table itself is also paged
Two-way Page Table
 Logical Address

Two Level 32 bit Paging architecture

Also called Forward Mapped Page Table

Hashed Page Table
• A common approach for handling address spaces larger than
32 bits is to use a hashed page table, with the hash value
being the virtual page number.
• Each entry in the hash table contains a linked list of elements
that hash to the same location (to handle collisions).
• Each element consists of three fields:
• (1) the virtual page number,
• (2) the value of the mapped page frame, and
• (3) a pointer to the next element in the linked list.
 Working
• The virtual page number in the virtual
address is hashed into the hash table.
• The virtual page number is compared
with field 1 in the first element in the
linked list.
• If there is a match, the corresponding
page frame (field 2) is used to form the
desired physical address.
• If there is no match, subsequent entries
in the linked list are searched for a
matching virtual page number.
 Inverted Page Tables

• Each page table consumes a large

amount of physical memory.
• To solve this problem, an inverted
page table can be used.
• This table has one entry for each
page (or frame) of memory.
• Each entry consists of the virtual
address of the page stored in that
real memory location, with
information about the process
that owns the page.
Advantages and Disadvantages
Advantages
• Easy to use memory management algorithm
• No need for external Fragmentation
• Swapping is easy between equal-sized pages and page frames.
Disadvantages
• May cause Internal fragmentation
• Page tables consume additional memory.
• Multi-level paging may lead to memory reference overhead.
 Segmentation
• It is a memory management scheme
that supports user view of memory.
• Logical address space is a collection of
segments.
• Each segment has a name and a length.
• The addresses specify both the
segment name and the offset within
the segment.
• The programmer therefore specifies
each address by two quantities: a
segment name and an offset.
• Segments are numbered and are referred to by a segment number,
rather than by a segment name.
• Logical address consists of a two tuple:
• <segment-number, offset>
• When a program is compiled, the compiler automatically constructs
segments reflecting the input program.
• A C compiler might create separate segments for the following:
1. The code
2. Global variables
3. The heap, from which memory is allocated
4. The stacks used by each thread
5. The standard C library
Segmentation Hardware
• Programmer can refer to objects
in the program by a two-
dimensional address, but the
actual physical memory is one-
dimensional sequence of bytes.
• An implementation to map two-
dimensional user-defined
addresses into one-dimensional
physical must be done.
• This mapping is achieved by a
segment table.
Segment Table
• Each entry in the segment table has a segment base and a segment limit.
• The segment base contains the starting physical address where the
segment resides in memory, and the segment limit specifies the length of
the segment.
• A logical address consists of two parts: a segment number, s, and an offset
into that segment, d.
• The segment number is used as an index to the segment table.
• The offset d of the logical address must be between 0 and the segment
limit.
• If it is not, we trap to the operating system (logical addressing attempt
beyond end of segment).
• When an offset is legal, it is added to the segment base to produce the
address in physical memory of the desired byte.
e.g.
Five segments numbered from 0 through
4 stored in physical memory.
The segment table has a separate entry
for each segment, giving the beginning
address of the segment in physical
memory (or base) and the length of that
segment (or limit).
For example, segment 2 is 400 bytes long
and begins at location 4300. Thus, a
reference to byte 53 of segment 2 is
mapped onto location 4300 + 53 = 4353.
Advantages of Segmentation
• Logical Program Organization: Segmentation matches the structure of
a program, making memory management more organized.
• Better Memory Protection: Each segment has its own limit and
access permissions.
• Easy Sharing of Code and Data: Segments can be shared between
processes.
• Independent Growth of Segments: Different segments can grow or
shrink independently.
• In segmentation, segments represent a portion of the program and
hence they are used in the same way.
• Some segments are instructions where as some segments are data.
• Instruction segments are read only or execute only. For this the
memory mapping hardware will check the protection bits associated
with each segment table entry to prevent illegal access to memory.
Disadvantages of Segmentation
• External Fragmentation: Memory becomes scattered into small free
spaces when segments of different sizes are allocated and removed.
• Slower Address Translation: For every memory reference, the system
must: Look up the segment table -> Check the limit -> Add base +
offset
Segmentation with Paging (Paged Segmentation)
• In Paged Segmentation, the program is first divided into segments,
and then each segment is divided into pages.
• Structure
• Program
↓
Segments
↓
Pages
↓
Frames in Main Memory
• Address Format
• Segment Number | Page Number | Offset
Segmentation with Paging (Paged Segmentation)
• Address Translation Steps
• Use Segment Number to find the segment table entry.
• The segment table points to the page table of that segment.
• Use Page Number to find the frame number.
• Add Offset to get the physical address.
• Example
• Segment 1: → Page 0 → Page 1 → Page 2
• Each segment has its own page table.
Segmented Paging (Paging with Segmentation)
• In Segmented Paging, the program is first divided into pages, and then
pages are grouped into segments.
• Structure
• Program
↓
Pages
↓
Grouped into Segments
↓
Frames in Main Memory
• Address Format
• Segment Number | Page Number | Offset
• However, the conceptual organization differs from paged segmentation.
Virtual Memory
• Virtual memory is a technique that allows the execution of processes
that are not completely in memory.
• Virtual memory is the separation of user logical memory from
physical memory.
• It makes the task of programming much easier, because the
programmer no longer needs to worry about the amount of physical
memory available.
• It allows processes to share files easily and to implement shared
memory.
• It is implemented using demand paging.
Advantages
• Programs can be larger than physical memory.
• Easy to share files and address spaces.
• Efficient mechanism for process creation.
Virtual Memory
Demand Paging
• A demand-paging system is similar to a paging system with swapping.
• Processes reside on secondary memory (which is usually a disk).
When a process is to be executed, it is swapped into memory. Rather
than swapping the entire process into memory, it swaps the required
page.
• This can be done by a lazy swapper.
• A lazy swapper never swaps a page into memory unless that page will
be needed.
• A swapper manipulates entire processes, whereas a pager is
concerned with the individual pages of a process.
 Basic Concepts
• When a process is to be swapped in, the pager brings only those necessary
pages into main memory.
• It avoids reading into memory the pages that will not be used anyway,
decreasing the swap time and the amount of physical memory needed.
• Some form of hardware support to distinguish between the pages that are in
memory and the pages that are on the disk. The valid–invalid bit scheme can
be used for this purpose.
• When this bit is set to “valid,” the associated page is both legal and in
memory.
• If the bit is set to “invalid,” the page either is not valid (that is, not in the
logical address space of the process) or is valid but is currently on the disk.
Some common Terms used in Demand Paging
• When a page references an invalid page, then it is called Page Fault. It
means that page is not in main memory.
• The CPU must look up the missing page in secondary memory. When
the number of page faults is significant, the system's effective access
time increases dramatically.
Page Table when some pages are not in the main memory
Handling page fault
 Handling page fault
1. Check an internal table for this process, to determine whether the reference
was a valid or invalid memory access.
2. If the reference was invalid, we terminate the process. If it was valid, but we
have not yet brought in that page in to memory.
3. Find a free frame (by taking one from the free-frame list).
4. Schedule a disk operation to read the desired page into the newly allocated
frame.
5. When the disk read is complete, modify the internal table kept with the
process and the page table to indicate that the page is now in memory.
6. Restart the instruction that was interrupted by the illegal address trap. The
process can now access the page as though it had always been in memory.
 Pure Demand Paging
• Pure demand paging is a specific implementation of demand paging.
• In on-demand paging only, no pages are initially loaded into memory when
the program starts and all pages are initially marked as being on disk.
• Operating systems that use pure demand paging as a memory management
strategy do so without preloading any pages into physical memory prior to
the commencement of a task.
• Demand paging loads a process's whole address space into memory one
step at a time, bringing just the parts of the process that are actively being
used into memory from disc as needed.
• The hardware to support demand paging is the same as the hardware for
paging and swapping
Hardware to support demand paging
• Page table. This table has the ability to mark an entry invalid through
a valid–invalid bit or a special value of protection bits.
• Secondary memory. This memory holds those pages that are not
present in main memory.
• The secondary memory is usually a high-speed disk.
• It is known as the swap device, and the section of disk used for this
purpose is known as swap space.
Performance of Demand Paging

• Let p be the probability of a page fault (0< p < 1). Then the effective
access time is
• Effective access time = (1 - p) x memory access time + p x page fault
time
• Three major components of the page-fault service time:
• 1. Service the page-fault interrupt.
• 2. Read in the page.
• 3. Restart the process.
Process Creation

• Two techniques are used by virtual memory to enhance performance

of creating and running processes.
1. Copy_on_Write (CoW)
2. Memory mapped files
Copy-on-Write • Copy-on-Write (COW) is a memory
management technique used in operating
systems where multiple processes share
the same memory pages until one of them
tries to modify the data. Only at that
moment does the OS create a separate
copy of the page.
• Instead of copying memory immediately,
the OS:
Shares the same memory page between
processes.
Marks the page as read-only.
When a process tries to modify it, the OS:
• Creates a new copy of that page
• Gives the process its own private copy
This process is called Copy-on-Write.
Copy-on-Write
• In UNIX OS fork() system call creates a duplicate process of the parent
process which is called as the child process.
• The idea behind CoW is that when a parent process creates a child
process, then both these processes will initially share the same pages
in memory and these shared pages will be marked as Copy-on-Write
which means that if any of these processes tries to modify the shared
pages then only a copy of these pages will be created and the
modification will be done on the copy of pages by that process and
does not affect other processes
Memory mapped files
Memory mapped files
• When a file from the disk is read using standard system calls open(), read()
and write() operation are used
• Every time a file is accessed, system call and disc access is required.
• An approach known as memory mapping allows a part of the virtual
memory space to be logically associated with the file.
• Memory mapping a file is possible by mapping a dis block to a page(s) in
memory.
• Initial access to the file proceeds using demand paging resulting in a page
fault.
• Subsequent read and write to the file are handled as routine memory
accesses.
• Closing the file results in all memory mapped data being written back to
the disc and removed from virtual memory of the process.
• Multiple processes may be allowed to map the same file into the virtual
memory of each, to allow sharing of data
Thrashing
• Thrashing in OS is a phenomenon that occurs in computer operating
systems when the system spends an excessive amount of time
swapping data between physical memory (RAM) and virtual memory
(disk storage) due to high memory demand and low available
resources.
• Thrashing can occur when there are too many processes running on a
system and not enough physical memory to accommodate them all.
As a result, the operating system must constantly swap pages of
memory between physical memory and virtual memory.
Techniques to Prevent Thrashing
• Increase the amount of physical memory
• Reduce the degree of multiprogramming
• Use an effective page replacement policy
• Optimize applications
• Monitor the system's resource usage
• Use a system monitoring tool
 Page Replacement
• Demand paging is implemented using page placement and replacement.
• During scheduling a process, the OS allocates a certain number of frames to the
process.
• The process is supposed to execute using only those frames in the memory.
• If a page referenced is not available within the frames (a page-fault) and there is no
free frame, a victim frame is selected, and its content (page) is invalidated.
• If the frame contains a modified (known by checking the dirty-bit) page, the page is
copied back to the backing store (swap space) before invalidation.
• A dirty bit is a flag in operating systems (specifically in page tables or cache)
that indicates if a memory page or block has been modified since it was loaded.
• The frame then accommodates the demanded page fetched from the secondary
memory. The frame is simply overwritten with the new page.
Page Replacement
• Selection of a free frame (Step 4) during page-fault handling needs
the following modifications:
i. selecting a victim frame
ii. checking the dirty-bit of the victim-frame
iii. if the dirty-bit is set, swap out the page in backing store (extra I/O)
iv. swap-in the demanded page in the selected frame
• In case the dirty-bit is set, demand paging must incur the cost of
loading back the page to the swap space.
• OS must select a victim frame, free the frame and replace its page. An
OS uses different algorithms to select the victim frame. They are
called page replacement algorithms.
Locality of Reference
• Locality of Reference in paging means that a program usually uses
only a small number of pages repeatedly during a short period of
execution.
• Because of this behavior, the operating system keeps those frequently
used pages in main memory to reduce page faults and improve
performance.
• Types
1. Temporal Locality (Time Locality): If a memory location is accessed,
it is likely to be accessed again soon.
2. Spatial Locality (Space Locality): If a memory location is accessed,
nearby memory locations are likely to be accessed soon.
Why Locality of Reference is Important

• Improves cache performance

• Reduces page faults
• Improves virtual memory efficiency
• Helps OS design better page replacement algorithms
Page Replacement Algorithms
• In an operating system that uses paging, a page replacement algorithm is
needed when a page fault occurs and no free page frame is available.
• In this case, one of the existing pages in memory must be replaced with
the new page.
• Common Page Replacement Techniques
• First In First Out (FIFO)
• Optimal Page replacement
• Least Recently Used (LRU)
• Most Recently Used (MRU)
 First In First Out (FIFO)
• The page that has entered in the memory earliest will be replaced first. Meaning the
oldest page in memory will be removed to make space for the new page.
• This algorithm is simple to implement using a queue data structure. The operating
system maintains a queue of pages in memory.
• When a page needs to be replaced, the page at the front of the queue (i.e., the
oldest page) is removed, and the new page is added to the back of the queue.
• The string of memory references is called reference string.
• To determine the number of page faults for a particular reference string and page
replacement algorithm, we also need to know the number of page frames available.
As the number of frames available increase, the number of page faults will decrease.
• Page Fault – A page fault happens when a running program accesses a memory
page that is mapped into the virtual address space, but not loaded in physical
memory
page reference string:
5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0
Number of Page frames = 3
1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 3 3 3 3 3 3 2 2 2 2 2 2 0 0 0 0
5 5 5 5 2 2 2 2 4 4 4 4 4 4 4 4 7 7 7 7 7
H H H H H H H H H H

Total Page Fault= 11

Number of Hit= 10
Rate of page fault = No. of page fault/No. of frames
11/3= 3.6
Beledy’s Anomaly
• Belady's Anomaly is a phenomenon in operating systems where
increasing the number of page frames in memory leads to an increase
in the number of page faults for certain page replacement algorithms.
page reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1,
2, 3, 4 with no of frame 3,
2 2 2 1 1 1 1 1 3 3
1 1 1 0 0 0 0 0 2 2 2
0 0 0 3 3 3 4 4 4 4 4 4
H H H

Page Fault= 9
page reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1,
2, 3, 4 with no of frame 3,
3 3 3 3 3 3 2 2 2
2 2 2 2 2 2 1 1 1 1
1 1 1 1 1 1 0 0 0 0 4
0 0 0 0 0 0 4 4 4 4 3 3
H H
Page Fault= 10
Advantages of FIFO
• Simplicity: Simple and easy-to-implement algorithm. It does not require
complex data structures or sophisticated calculations.
• Fairness: All pages have an equal chance of being replaced. The oldest
page is replaced first, regardless of its usage frequency or importance.
• No starvation: Does not suffer from starvation, which means that a page
will eventually be replaced if it has been in memory for a long time, even if
it is frequently used.
• Predictability: Predictable in the sense that the order in which pages are
replaced is deterministic and does not depend on the page usage patterns
or history.
• Low overhead: Minimal overhead because it only needs to maintain a
simple queue of pages in memory, making it a good choice for systems with
limited resources.
 Disadvantages of FIFO
• Poor performance: May not provide optimal performance because it does not take into account the
usage patterns or importance of the pages. It may result in frequent page faults and unnecessary disk
I/O operations, especially if the workload is complex or memory demands are high.
• Inefficient use of memory: Can lead to inefficient use of memory because it replaces the oldest page,
regardless of its usage frequency or importance. As a result, some pages that are rarely used or not
important may occupy memory for a long time, while other more critical pages may be swapped out
frequently.
• Susceptibility to thrashing: May be susceptible to thrashing, which occurs when the system spends a
significant amount of time swapping pages in and out of memory without making progress on the
actual workload. This happens when the number of pages needed by the workload exceeds the
available physical memory, and the FIFO algorithm does not efficiently manage the page swapping.
• Unfairness: May not be fair from the perspective of the workload or the user. Some pages may be
more important than others, and replacing them first can lead to degraded performance or even
application crashes.
• No consideration of future usage: Does not consider the future usage of pages, which means that it
may replace a page that will be needed again soon, leading to increased page faults and decreased
performance.
Optimal Page Replacement Algorithm

• This algorithm states that: Replace that page which will not be used
for longest period of time i.e. future knowledge of reference string is
required.
 page reference string:
5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0
Number of Page frames = 3
1 1 1 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
0 0 0 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0 0
5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 7 7
H H H H H H H H H H H H

Total Page Fault= 9

Number of Hit= 12
Rate of page fault= No. of page fault/No. of frames = 9/3= 3
 Advantages
• Optimal performance: Designed to replace the page that will not be used for the
longest time in the future. It provides the best possible performance because it
minimizes the number of page faults and maximizes the number of hits.
• Efficient use of memory: Leads to efficient use of memory because it replaces the
page that will not be used for the longest time in the future. This means that pages
that are rarely used or not important are more likely to be swapped out, freeing up
memory for more critical pages.
• No thrashing: Less susceptible to thrashing compared to FIFO or LRU because it
considers the future usage of pages. It can detect which pages are being used
frequently and which pages are likely to be used in the future, prioritizing them for
memory allocation and reducing the number of page faults and disk I/O operations.
• Fairness: Considered fair algorithm because it takes into account the future usage of
pages and replaces the page that will not be used for the longest time in the future.
This means that pages that are rarely used or not important are more likely to be
swapped out, making room for more frequently used or critical pages.
Disadvantages
• OPR is perfect, but not possible in practice as the operating system
cannot know future requests.
• Error handling is tough.
LRU (Least-Recently-Used) Page Replacement
• In this algorithm, the page that has been not used for longest period
of time is selected for replacement.
 page reference string:
5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0
Number of Page frames = 3
1 1 1 3 3 3 4 4 4 4 0 0 0 0 7 7 7 7 7
0 0 0 0 0 0 0 0 3 3 3 3 3 1 1 1 0 0 0 0
5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1
H H H H H H H H H

Total Page Fault= 12

Number of Hit= 9
Rate of page fault= No. of page fault/No. of frames = 12/3= 4
 Advantages
• Good performance: Designed to replace the page that has not been accessed for the longest time.
Takes into account the usage history of pages, and it can lead to fewer page faults and faster
application response times.
• Efficient use of memory: Efficient use of memory because it replaces the page that has not been
used for the longest time. This means that pages that are rarely used or not important are more likely
to be swapped out, freeing up memory for more critical pages.
• No thrashing: Less susceptible to thrashing compared to FIFO because it considers the usage history
of pages. It can detect which pages are being used frequently and prioritize them for memory
allocation, reducing the number of page faults and disk I/O operations.
• Fairness: Considered a fair algorithm because it takes into account the usage history of pages and
replaces the least recently used page first. This means that pages that are rarely used or not
important are more likely to be swapped out, making room for more frequently used pages.
• Good balance between complexity and performance: LRU is more complex than FIFO, but it is still
relatively simple and easy to implement compared to other algorithms like optimal page
replacement. It strikes a good balance between complexity and performance, making it a popular
choice for many operating systems.
Disadvantages

• It requires additional Data Structure to be implemented.

• Hardware assistance is high.
• In LRU error detection is difficult as compared to other algorithms.
• It has limited acceptability.
• LRU are very costly to operate.
 Virtual memory paging Vs virtual memory
segmentation
Feature Paging Segmentation
Memory division Fixed-size pages Variable-size segments
Physical memory
Based on Logical program structure
management
Address format Page number + offset Segment number + offset
Fragmentation Internal fragmentation External fragmentation
Table used Page table Segment table
Visibility to programmer Invisible Visible (logical segments)
Protection & sharing Harder Easier