Memory Management in Operating System

Memory management is the process of controlling and organizing a

computer’s memory by allocating portions, called blocks, to different
executing programmes to improve the overall system performance.
✓ The most important function of an operating system is to manage
primary memory.
✓ Supports multiple processes simultaneously in memory.
✓ Protects processes from unauthorized access.
✓ Enables swapping and virtual memory efficiently.

Techniques in Memory Allocation

Used by an operating system to efficiently allocate, utilize, and manage
memory resources for processes. Various techniques help the operating
system manage memory effectively. They can be broadly categorized
into:
Swapping
Swapping is a memory management technique where processes are
temporarily moved between main memory and secondary storage to
free up memory for other processes.
✓ Allows multiple processes to run efficiently.
✓ Lower-priority processes can be swapped out for higher-priority
ones.
✓ Swapped-out processes resume when loaded back into memory.
✓ Transfer time depends on the amount of data moved.

1. Contiguous Memory Allocation

Each process is allocated a single continuous block of memory. All
instructions and data of a process are stored in adjacent memory
locations.

1) Single Contiguous Memory Allocation

Simplest form of memory management. In this technique, 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 process
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
Advantages
✓ Simple memory management
✓ No fragmentation issues
Disadvantages
✓ Poor memory utilization
✓ No support for multitasking or multiprogramming

2) Partitioned Memory Allocation

Main memory is divided into multiple contiguous partitions, and each
partition can hold one process. This technique supports
multiprogramming.
Partitioned memory allocation is further classified 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.
Variable Partition Allocation
✓ 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
2. Non-Contiguous Memory Allocation
Memory management technique in which a process is divided into
smaller parts and these parts are stored in different, non-adjacent
locations in main memory. Unlike contiguous allocation, the entire
process does not need to be placed in a single continuous block of
memory.
This technique is widely used in modern operating systems because it
improves memory utilization and reduces fragmentation problems.
Features of Non-Contiguous Memory Allocation
✓ A process can be stored in multiple memory locations
✓ Improves utilization of available memory
✓ Reduces external fragmentation
✓ Requires address translation using hardware support (MMU)
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)
Techniques Used in Non-Contiguous Memory Allocation
1. Paging: Divides a process into fixed-size pages and memory
into frames of the same size
2. Segmentation: Divides a process into logical segments of
variable size such as code, data, and stack
3. Segmentation with Paging: Combines logical segmentation
with paging to reduce fragmentation
Fragmentation in Operating System
•
Fragmentation in computing is the process in which a file, such as a
data file or an executable program, is divided into smaller fragments
that are stored in different parts of a storage medium, such as a hard
disk or RAM. When a file is fragmented, its fragments are stored in
non-contiguous blocks, meaning they are not placed next to each other.
This can lead to inefficient use of memory or storage and slower access
to files. Fragmentation occurs both in memory (RAM) and storage, and
it is a common challenge in operating systems that affects overall
system performance.
✓ Fragmentation occurs when processes repeatedly load and unload
from memory, leaving small blocks of memory unused.
✓ Programs create free spaces or "holes" in memory when they are
loaded and removed, which cannot always be used by new
processes.
✓ The memory allocation scheme of the operating system determines
how and when fragmentation occurs.
✓ Fragmented memory or storage becomes inefficient, as the
scattered blocks cannot be easily assigned to incoming processes.
✓ Accessing fragmented files can slow down the system because the
OS has to locate and assemble the scattered fragments.
✓ Defragmentation is the process of reorganizing memory or storage
to store files in contiguous blocks, improving efficiency and
access speed.
Cause of Fragmentation
✓ Fragmentation occurs when a file is too large to fit into a single
contiguous block of free space on the storage medium.
✓ It can also happen when the available free blocks on the storage
medium are too small to hold the entire file.
✓ As a result, the file is split into fragments that are stored in
different locations.
✓ The system must search for and retrieve these scattered fragments
to access the file, which can slow down file reading and
processing.
Effect of Fragmentation
✓ Fragmentation reduces overall system performance because
accessing scattered fragments takes more time.
 ✓ It makes files harder to read or access efficiently.
✓ Regular defragmentation helps reorganize the scattered data blocks
so that files are stored in contiguous blocks.
✓ Defragmenting improves access speed, memory or storage
efficiency, and overall system performance.
Types of Fragmentation
In an operating system, fragmentation mainly occurs in two different
forms based on how memory or storage space is utilized. These types
explain where and how unused space is created during memory or
storage allocation. The two main types of fragmentation are:
[Link] Fragmentation
2. External Fragmentation

1. Internal Fragmentation
✓ Internal fragmentation occurs when allocated memory contains
unused space within a block.
✓ It happens when the size of the allocated memory block is larger
than the actual memory required by a process.
✓ For example, if a system allocates a 64 KB memory block to a
process that requires only 40 KB, the remaining 24 KB remains
unused, resulting in internal fragmentation.
✓ This type of fragmentation commonly occurs in systems that use
fixed-size memory allocation techniques.
✓ The unused space inside the allocated block cannot be utilized by
other processes, leading to inefficient memory usage.
2. External Fragmentation
✓ External fragmentation occurs when free memory or storage space
is divided into many small, non-contiguous blocks.
✓ It is caused by frequent allocation and deallocation of processes or
files over time.
✓ Even if the total free space is sufficient, the system may be unable
to allocate memory because no single contiguous block is large
enough.
✓ As a result, files or processes must be stored in multiple smaller
blocks, increasing access time.
✓ External fragmentation leads to performance degradation and
inefficient use of storage or memory resources.
Fragmentation can also occur at various levels within a system. File
fragmentation, for example, can occur at the file system level, in which
a file is divided into multiple non-contiguous blocks and stored on a
storage medium. Memory fragmentation can occur at the memory
management level, where the system allocates and deallocated memory
blocks dynamically. Network fragmentation occurs when a packet of
data is divided into smaller fragments for transmission over a network.
Impact of Fragmentation on Operating System Performance
✓ Fragmentation significantly affects the overall performance and
stability of an operating system.
✓ It slows down disk read and write operations because the disk head
must move to multiple locations to access scattered file fragments.
✓ Increased disk head movement raises access time, which reduces
system speed and causes application slowdowns and lag.
✓ Fragmentation leads to inefficient disk space utilization, as
fragmented files may occupy more space than necessary.
✓ Wasted disk space can result in storage shortages, making the
system unstable and more prone to errors or crashes.
✓ In severe cases, excessive fragmentation can cause the system to run
out of disk space, increasing the risk of data loss.
✓ A highly fragmented disk increases the likelihood of system crashes
and operational errors.
✓ Fragmentation can negatively impact battery life in laptops and
mobile devices because the disk has to work harder to access
scattered data.
✓ Regular defragmentation reorganizes fragmented files into
contiguous blocks, improving disk access speed and reducing
latency.
✓ Maintaining low fragmentation ensures efficient resource usage,
stable system operation, and a smooth user experience.
Advantages
✓ Fragmentation allows better utilization of available storage space on
a hard disk or other storage media. Files can be stored in free blocks
even if those blocks are not contiguous, preventing small unused
spaces from being wasted.
✓ It enables the system to efficiently use scattered free space, which is
especially helpful when the storage medium contains many small
free blocks.
✓ Fragmentation makes it possible to store large files even when a
single contiguous block of free space is not available. The file can be
divided and stored across multiple smaller blocks.
✓ It provides flexibility in memory and storage allocation, allowing the
operating system to continue functioning without requiring large
continuous memory regions.
✓ Although fragmentation has these advantages, it is generally
recommended to minimize it because excessive fragmentation can
reduce system performance and make file access and management
more complex.
Disadvantages
✓ Fragmentation can significantly degrade system performance,
especially during file reading or access operations. The system must
locate and retrieve multiple fragments from different locations,
which takes more time than accessing a single contiguous file.
✓ It makes file management and organization more complex, as
fragmented files are stored in multiple non-contiguous blocks,
making them harder to track and access efficiently.
✓ Fragmentation can reduce the lifespan of storage devices such as
hard disks and solid-state drives. Frequent access to scattered data
increases read/write operations, leading to additional wear and tear
on the storage medium.
✓ It consumes extra storage space because the system needs to
maintain additional metadata to track the locations of each
fragment. This reduces the amount of available space for storing
other files.

Thrashing: Thrashing occurs when the system spends most of its time
swapping pages between memory and disk instead of executing
processes, causing very low CPU utilization.

Memory Allocation Strategies

1) Fixed Partition Allocation: Memory is divided into fixed-sized
partitions, and each partition can hold only one process. The OS
keeps track of free and occupied partitions using a partition table.
2) Dynamic Partition Allocation: Memory is divided into variable-
sized partitions based on the size of the processes. This helps avoid
wastage of memory but can result in fragmentation.
3) Placement Algorithms: When allocating memory, the OS uses
placement algorithms to decide which free block should be assigned
to a process:
✓ First Fit: Allocates the first available partition large enough to hold
the process.
✓ Best Fit: Allocates the smallest available partition that fits the
process, reducing wasted space.
✓ Worst Fit: Allocates the largest available partition, leaving the
largest remaining space.
✓ Next Fit: Similar to First Fit but starts searching for free memory
from the point of the last allocation.

VIRTUAL MEMORY
Virtual memory is a memory management technique that allows the
execution of processes without requiring the entire program to be
loaded into main memory (RAM) at once. It creates the illusion of a
large, contiguous memory space for each process, even when the
physical memory is limited.
By using virtual memory, an operating system can run programs that
are larger than the available physical memory, improve system
throughput, and support higher levels of multiprogramming.

Motivation for Virtual Memory

Virtual memory was introduced to overcome the limitations of physical
memory, such as:
✓ Limited size of RAM
✓ High cost of main memory
✓ Inefficient use of memory when entire programs are loaded
Without virtual memory:
✓ Only a few programs could run simultaneously
✓ Large programs would fail to execute
✓ Memory utilization would be poor
Virtual memory separates logical memory (what a process sees) from
physical memory (actual RAM).
Basic Concept of Virtual Memory
In a virtual memory system:
✓ Each process is given a virtual address space
✓ Only the currently needed parts of a process are loaded into RAM
✓ The remaining parts are stored on secondary storage (disk)
This technique is called demand loading.
Virtual Address Space: A virtual address space is the range of logical
addresses that a process can use.
Characteristics:
✓ Appears contiguous to the process
✓ Much larger than physical memory
✓ Independent of other processes
Benefits:
✓ Simplifies programming
 ✓ Enhances memory protection
✓ Supports large applications
Demand Paging
Demand paging is the most common implementation of virtual
memory.
How Demand Paging Works
✓ A process generates a virtual address
✓ The MMU checks the page table
✓ If the page is in memory → execution continues
✓ If the page is not in memory → page fault occurs
Page Fault: A page fault occurs when a process tries to access a page
that is not currently in physical memory.
Page Fault Handling Steps:
1) OS suspends the process
2) Required page is located on disk
3) A free frame is selected
4) Page is loaded into memory
5) Page table is updated
6) Process resumes execution
Page faults are normal events, not errors.
Page Table and MMU in Virtual Memory
The page table maps virtual pages to physical frames.
Each page table entry contains:
✓ Frame number
✓ Valid/invalid bit
✓ Protection bits
✓ Dirty bit
✓ Reference bit
The Memory Management Unit (MMU) performs address translation
and checks access rights.

Common Page Replacement Techniques

1) First In First Out (FIFO)
2) Optimal Page replacement
3) Least Recently Used (LRU)
 4) Most Recently Used (MRU)
1) First In First Out (FIFO)
This is the simplest page replacement algorithm. In this algorithm, the
operating system keeps track of all pages in the memory in a queue, the
oldest page is in the front of the queue. When a page needs to be
replaced page in the front of the queue is selected for removal.
Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page
frames. Find the number of page faults using FIFO Page Replacement
Algorithm.

FIFO - Page Replacement

• Initially, all slots are empty, so when 1, 3, 0 came they are
allocated to the empty slots ---> 3 Page Faults.
• When 3 comes, it is already in memory so ---> 0 Page Faults.
 • Then 5 comes, it is not available in memory, so it replaces the
oldest page slot i.e 1. ---> 1 Page Fault.
• 6 comes, it is also not available in memory, so it replaces the
oldest page slot i.e 3 ---> 1 Page Fault.
• Finally, when 3 come it is not available, so it replaces 0 1-
page fault.
2) Optimal Page Replacement
In this algorithm, pages are replaced which would not be used for the
longest duration of time in the future.
Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3,
2, 3 with 4-page frame. Find number of page fault using Optimal Page
Replacement Algorithm.

Optimal Page Replacement

✓ Initially, all slots are empty, so when 7 0 1 2 are allocated to the

empty slots ---> 4 Page faults
✓ 0 is already there so ---> 0 Page fault. when 3 came it will take
the place of 7 because it is not used for the longest duration of
time in the future---> 1 Page fault.
✓ 0 is already there so ---> 0 Page fault. 4 will takes place of 1 --->
1 Page Fault.
✓ Now for the further page reference string ---> 0 Page fault because
they are already available in the memory.
✓ Optimal page replacement is perfect, but not possible in practice as
the operating system cannot know future requests.
The use of Optimal Page replacement is to set up a benchmark so that
other replacement algorithms can be analyzed against it.
3) Least Recently Used (LRU)
In this algorithm, page will be replaced which is least recently used.
Example Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0,
3, 2, 3 with 4-page frames. Find number of page faults using LRU Page
Replacement Algorithm.

Least Recently Used - Page Replacement

✓ Initially, all slots are empty, so when 7 0 1 2 are allocated to the
empty slots ---> 4 Page faults.
✓ 0 is already there so ---> 0 Page fault. when 3 came it will take the
place of 7 because it is least recently used ---> 1 Page fault.
✓ 0 is already in memory so ---> 0 Page fault.
✓ 4 will takes place of 1 ---> 1 Page Fault.
✓ Now for the further page reference string ---> 0 Page fault because
they are already available in the memory.
4) Most Recently Used (MRU)
In this algorithm, page will be replaced which has been used recently.
Belady's anomaly can occur in this algorithm.
Example 4: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, 3 with 4-page frames. Find number of page faults using MRU
Page Replacement Algorithm.

Most Recently Used - Page Replacement

✓ Initially, all slots are empty, so when 7 0 1 2 are allocated to the
empty slots ---> 4 Page faults
✓ 0 is already their so--> 0 page fault
✓ when 3 comes it will take place of 0 because it is most recently
used ---> 1 Page fault
✓ when 0 comes it will take place of 3 ---> 1 Page fault
✓ when 4 comes it will take place of 0 ---> 1 Page fault
✓ 2 is already in memory so ---> 0 Page fault
✓ when 3 comes it will take place of 2 ---> 1 Page fault
✓ when 0 comes it will take place of 3 ---> 1 Page fault
✓ when 3 comes it will take place of 0 ---> 1 Page fault
✓ when 2 comes it will take place of 3 ---> 1 Page fault
✓ when 3 comes it will take place of 2 ---> 1 Page fault