UNIT-4

Memory Management
Memory is the important part of the computer that is used to store the data.
Its management is critical to the computer system because the amount of
main memory available in a computer system is very limited. At any time,
many processes are competing for it. Moreover, to increase performance,
several processes are executed simultaneously. For this, we must keep
several processes in the main memory, so it is even more important to
manage them effectively.

Role of Memory management

Following are the important roles of memory management in a computer
system:

o Memory manager is used to keep track of the status of memory locations,

whether it is free or allocated. It addresses primary memory by providing
abstractions so that software perceives a large memory is allocated to it.
o Memory manager permits computers with a small amount of main memory to
execute programs larger than the size or amount of available memory. It
does this by moving information back and forth between primary memory
and secondary memory by using the concept of swapping.
Memory Management Techniques:
The memory management techniques can be classified into
following main categories:

o Contiguous memory management schemes

o Non-Contiguous memory management schemes

Contiguous memory management schemes:

In a Contiguous memory management scheme, each program occupies a
single contiguous block of storage locations, i.e., a set of memory locations
with consecutive addresses.

Single contiguous memory management schemes:

The Single contiguous memory management scheme is the simplest memory

management scheme used in the earliest generation of computer systems.
In this scheme, the main memory is divided into two contiguous areas or
partitions. The operating systems reside permanently in one partition,
generally at the lower memory, and the user process is loaded into the other
partition.

Advantages of Single contiguous memory management schemes:

o Simple to implement.
 o Easy to manage and design.
o In a Single contiguous memory management scheme, once a process is
loaded, it is given full processor's time, and no other processor will interrupt
it.

Disadvantages of Single contiguous memory management schemes:

o Wastage of memory space due to unused memory as the process is unlikely

to use all the available memory space.
o The CPU remains idle, waiting for the disk to load the binary image into the
main memory.
o It can not be executed if the program is too large to fit the entire available
main memory space.
o It does not support multiprogramming, i.e., it cannot handle multiple
programs simultaneously.

Multiple Partitioning:
The single Contiguous memory management scheme is inefficient as it limits
computers to execute only one program at a time resulting in wastage in
memory space and CPU time. The problem of inefficient CPU use can be
overcome using multiprogramming that allows more than one program to
run concurrently. To switch between two processes, the operating systems
need to load both processes into the main memory. The operating system
needs to divide the available main memory into multiple parts to load
multiple processes into the main memory. Thus multiple processes can
reside in the main memory simultaneously.

ADVERTISEMENT

ADVERTISING

The multiple partitioning schemes can be of two types:

o Fixed Partitioning
o Dynamic Partitioning
Fixed Partitioning
The main memory is divided into several fixed-sized partitions in a fixed
partition memory management scheme or static partitioning. These
partitions can be of the same size or different sizes. Each partition can hold a
single process. The number of partitions determines the degree of
multiprogramming, i.e., the maximum number of processes in memory.
These partitions are made at the time of system generation and remain fixed
after that.

Advantages of Fixed Partitioning memory management schemes:

o Simple to implement.
o Easy to manage and design.

Disadvantages of Fixed Partitioning memory management schemes:

o This scheme suffers from internal fragmentation.

o The number of partitions is specified at the time of system generation.

Dynamic Partitioning
The dynamic partitioning was designed to overcome the problems of a fixed
partitioning scheme. In a dynamic partitioning scheme, each process
occupies only as much memory as they require when loaded for processing.
Requested processes are allocated memory until the entire physical memory
is exhausted or the remaining space is insufficient to hold the requesting
process. In this scheme the partitions used are of variable size, and the
number of partitions is not defined at the system generation time.

Advantages of Dynamic Partitioning memory management schemes:

o Simple to implement.
o Easy to manage and design.

Disadvantages of Dynamic Partitioning memory management

schemes:

o This scheme also suffers from internal fragmentation.

o The number of partitions is specified at the time of system segmentation.
Non-Contiguous memory management schemes:
In a Non-Contiguous memory management scheme, the program is divided
into different blocks and loaded at different portions of the memory that
need not necessarily be adjacent to one another. This scheme can be
classified depending upon the size of blocks and whether the blocks reside in
the main memory or not.

What is paging?
Paging is a technique that eliminates the requirements of contiguous
allocation of main memory. In this, the main memory is divided into fixed-
size blocks of physical memory called frames. The size of a frame should be
kept the same as that of a page to maximize the main memory and avoid
external fragmentation.

Advantages of paging:

o Pages reduce external fragmentation.

o Simple to implement.
o Memory efficient.
o Due to the equal size of frames, swapping becomes very easy.
o It is used for faster access of data.

What is Segmentation?
Segmentation is a technique that eliminates the requirements of contiguous
allocation of main memory. In this, the main memory is divided into variable-
size blocks of physical memory called segments. It is based on the way the
programmer follows to structure their programs. With segmented memory
allocation, each job is divided into several segments of different sizes, one
for each module. Functions, subroutines, stack, array, etc., are examples of
such modules.

Virtual Memory
Virtual Memory is a storage allocation scheme in which secondary
memory can be addressed as though it were part of the main
memory. The addresses a program may use to reference memory are
distinguished from the addresses the memory system uses to identify
physical storage sites and program-generated addresses are
translated automatically to the corresponding machine addresses.
The size of virtual storage is limited by the addressing scheme of the
computer system and the amount of secondary memory available not
by the actual number of main storage locations.

Demand Paging
Demand paging can be described as a memory management
technique that is used in operating systems to improve memory
usage and system performance. Demand paging is a technique used
in virtual memory systems where pages enter main memory only
when requested or needed by the CPU.
In demand paging, the operating system loads only the necessary
pages of a program into memory at runtime, instead of loading the
entire program into memory at the start. A page fault occurred when
the program needed to access a page that is not currently in memory.
The operating system then loads the required pages from the disk
into memory and updates the page tables accordingly. This process is
transparent to the running program and it continues to run as if the
page had always been in memory.
What is Page Fault?
The term “page miss” or “page fault” refers to a situation where a
referenced page is not found in the main memory.
The missed page must be accessed by the CPU from the secondary
memory. The system’s effective access time will increase significantly
if there are a lot of page faults.
Page Replacement Algorithms
Page Replacement Algorithms:

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.
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.
Belady’s anomaly proves that it is possible to have more page faults
when increasing the number of page frames while using the First in
First Out (FIFO) page replacement algorithm. For example, if we
consider reference strings 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4, and 3 slots,
we get 9 total page faults, but if we increase slots to 4, we get 10-
page faults.
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-2: 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.
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: In this algorithm, page will be replaced which
is least recently used.
Example-3: 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.
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 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.
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
thrashing

thrashing occurs when a computer's virtual memory resources are

overused, leading to a constant state of paging and page faults, inhibiting
most application-level processing. It causes the performance of the computer
to degrade or collapse. The situation can continue indefinitely until the user
closes some running applications or the active processes free up additional
virtual memory resources.

To know more clearly about thrashing, first, we need to know about page
fault and swapping.

o Page fault: We know every program is divided into some pages. A

page fault occurs when a program attempts to access data or code in
its address space but is not currently located in the system RAM.
o Swapping: Whenever a page fault happens, the operating system will
try to fetch that page from secondary memory and try to swap it with
one of the pages in RAM. This process is called swapping.

Thrashing is when the page fault and swapping happens very frequently at
a higher rate, and then the operating system has to spend more time
swapping these pages. This state in the operating system is known as
thrashing. Because of thrashing, the CPU utilization is going to be reduced or
negligible.
Memory Management in Operating
System
The term memory can be defined as a collection of data in a specific format. It
is used to store instructions and process data. The memory comprises a large
array or group of words or bytes, each with its own location.

The main memory is central to the operation of a Modern Computer. Main

Memory is a large array of words or bytes, ranging in size from hundreds of
thousands to billions. Main memory is a repository of rapidly available
information shared by the CPU and I/O devices. Main memory is the place where
programs and information are kept when the processor is effectively utilizing
them.

Logical and Physical Address Space

 Logical Address Space: An address generated by the CPU is known as a
“Logical Address”. It is also known as a Virtual address. Logical address
 space can be defined as the size of the process. A logical address can be
changed.
 Physical Address Space: An address seen by the memory unit (i.e. the one
loaded into the memory address register of the memory) is commonly known
as a “Physical Address”. A physical address is also known as a Real
address. The set of all physical addresses corresponding to these logical
addresses is known as Physical address space. A physical address is
computed by MMU. The run-time mapping from virtual to physical addresses
is done by a hardware device Memory Management Unit (MMU). The
physical address always remains constant.

Swapping

When a process is executed it must have resided in memory. Swapping is a

process of swapping a process temporarily into a secondary memory from the
main memory, which is fast compared to secondary memory. A swapping
allows more processes to be run and can be fit into memory at one time. The
main part of swapping is transferred time and the total time is directly
proportional to the amount of memory swapped.
Swapping is also known as roll-out, or roll because if a higher priority process
arrives and wants service, the memory manager can swap out the lower priority
process and then load and execute the higher priority process. After finishing
higher priority work, the lower priority process swapped back in memory and
continued to the execution process.
Logical vs Physical Address
An address generated by the CPU is commonly referred to as a logical address.
the address seen by the memory unit is known as the physical address. The
logical address can be mapped to a physical address by hardware with the help
of a base register this is known as dynamic relocation of memory references.

Contiguous Memory Allocation

The main memory should accommodate both the operating system and the
different client processes. Therefore, the allocation of memory becomes an
important task in the operating system. The memory is usually divided into two
partitions: one for the resident operating system and one for the user
processes. We normally need several user processes to reside in memory
simultaneously. Therefore, we need to consider how to allocate available
memory to the processes that are in the input queue waiting to be brought into
memory. In adjacent memory allotment, each process is contained in a single
contiguous segment of memory.
 Contiguous Memory Allocation

Memory Allocation
To gain proper memory utilization, memory allocation must be allocated efficient
manner. One of the simplest methods for allocating memory is to divide memory
into several fixed-sized partitions and each partition contains exactly one
process. Thus, the degree of multiprogramming is obtained by the number of
partitions.
 Multiple partition allocation: In this method, a process is selected from the
input queue and loaded into the free partition. When the process terminates,
the partition becomes available for other processes.
 Fixed partition allocation: In this method, the operating system maintains a
table that indicates which parts of memory are available and which are
occupied by processes. Initially, all memory is available for user processes
and is considered one large block of available memory. This available
memory is known as a “Hole”. When the process arrives and needs memory,
we search for a hole that is large enough to store this process. If the
requirement is fulfilled then we allocate memory to process, otherwise
keeping the rest available to satisfy future requests. While allocating a
memory sometimes dynamic storage allocation problems occur, which
concerns how to satisfy a request of size n from a list of free holes. There
are some solutions to this problem:
First Fit
In the First Fit, the first available free hole fulfil the requirement of the process
allocated.

First Fit

Here, in this diagram, a 40 KB memory block is the first available free hole that
can store process A (size of 25 KB), because the first two blocks did not have
sufficient memory space.
Best Fit
In the Best Fit, allocate the smallest hole that is big enough to process
requirements. For this, we search the entire list, unless the list is ordered by
size.

Best Fit

Here in this example, first, we traverse the complete list and find the last hole
25KB is the best suitable hole for Process A(size 25KB). In this method,
memory utilization is maximum as compared to other memory allocation
techniques.

Worst Fit
In the Worst Fit, allocate the largest available hole to process. This method
produces the largest leftover hole.

Worst Fit

Here in this example, Process A (Size 25 KB) is allocated to the largest

available memory block which is 60KB. Inefficient memory utilization is a major
issue in the worst fit.
Fragmentation

Fragmentation is defined as when the process is loaded and removed after

execution from memory, it creates a small free hole. These holes cannot be
assigned to new processes because holes are not combined or do not fulfill the
memory requirement of the process. To achieve a degree of multiprogramming,
we must reduce the waste of memory or fragmentation problems. In the
operating systems two types of fragmentation:
1. Internal fragmentation: Internal fragmentation occurs when memory blocks are
allocated to the process more than their requested size. Due to this some
unused space is left over and creating an internal fragmentation problem.
Example: Suppose there is a fixed partitioning used for memory allocation
and the different sizes of blocks 3MB, 6MB, and 7MB space in memory. Now
a new process p4 of size 2MB comes and demands a block of memory. It
gets a memory block of 3MB but 1MB block of memory is a waste, and it
cannot be allocated to other processes too. This is called internal
fragmentation.
2. External fragmentation: In External fragmentation, we have a free memory
block, but we cannot assign it to a process because blocks are not
contiguous. Example: Suppose (consider the above example) three
processes p1, p2, and p3 come with sizes 2MB, 4MB, and 7MB respectively.
Now they get memory blocks of size 3MB, 6MB, and 7MB allocated
respectively. After allocating the process p1 process and the p2 process left
1MB and 2MB. Suppose a new process p4 comes and demands a 3MB
block of memory, which is available, but we cannot assign it because free
memory space is not contiguous. This is called external fragmentation.
Both the first-fit and best-fit systems for memory allocation are affected by
external fragmentation. To overcome the external fragmentation problem
Compaction is used. In the compaction technique, all free memory space
combines and makes one large block. So, this space can be used by other
processes effectively.
Another possible solution to the external fragmentation is to allow the logical
address space of the processes to be noncontiguous, thus permitting a process
to be allocated physical memory wherever the latter is available.

Paging

Paging is a memory management scheme that eliminates the need for a

contiguous allocation of physical memory. This scheme permits the physical
address space of a process to be non-contiguous.
 Logical Address or Virtual Address (represented in bits): An address generated
by the CPU.
 Logical Address Space or Virtual Address Space (represented in words or
bytes): The set of all logical addresses generated by a program.
 Physical Address (represented in bits): An address actually available on a
memory unit.
 Physical Address Space (represented in words or bytes): The set of all physical
addresses corresponding to the logical addresses.
Example:
 If Logical Address = 31 bits, then Logical Address Space = 2 31 words = 2 G
words (1 G = 230)
20
 If Logical Address Space = 128 M words = 2 7 * 2 words, then Logical
Address = log2 227 = 27 bits
 If Physical Address = 22 bits, then Physical Address Space = 2 22 words = 4
M words (1 M = 220)
 If Physical Address Space = 16 M words = 2 4 * 220 words, then Physical
Address = log2 224 = 24 bits
The mapping from virtual to physical address is done by the memory
management unit (MMU) which is a hardware device and this mapping is known
as the paging technique.
 The Physical Address Space is conceptually divided into several fixed-size
blocks, called frames.
 The Logical Address Space is also split into fixed-size blocks, called pages.
 Page Size = Frame Size
Let us consider an example:
 Physical Address = 12 bits, then Physical Address Space = 4 K words
 Logical Address = 13 bits, then Logical Address Space = 8 K words
 Page size = frame size = 1 K words (assumption)
 Paging

The address generated by the CPU is divided into:

 Page Number(p): Number of bits required to represent the pages in Logical
Address Space or Page number
 Page Offset(d): Number of bits required to represent a particular word in a
page or page size of Logical Address Space or word number of a page or
page offset.
Physical Address is divided into:
 Frame Number(f): Number of bits required to represent the frame of Physical
Address Space or Frame number frame
 Frame Offset(d): Number of bits required to represent a particular word in a
frame or frame size of Physical Address Space or word number of a frame or
frame offset.
The hardware implementation of the page table can be done by using dedicated
registers. But the usage of the register for the page table is satisfactory only if
the page table is small. If the page table contains a large number of entries then
we can use TLB(translation Look-aside buffer), a special, small, fast look-up
hardware cache.
 The TLB is an associative, high-speed memory.
 Each entry in TLB consists of two parts: a tag and a value.
 When this memory is used, then an item is compared with all tags
simultaneously. If the item is found, then the corresponding value is
returned.
 Page Map Table

Main memory access time = m

If page table are kept in main memory,
Effective access time = m(for page table)
+ m(for particular page in page table)

TLB Hit and Miss

Page Replacement Algorithms in
Operating Systems
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. Since actual physical memory is much smaller than virtual memory,
page faults happen.

Page Replacement Algorithms:

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
[Link] the number of page faults.

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.
Belady’s anomaly proves that it is possible to have more page faults when
increasing the number of page frames while using the First in First Out (FIFO)
page replacement algorithm. For example, if we consider reference strings
3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4, and 3 slots, we get 9 total page faults, but if we
increase slots to 4, we get 10-page faults.
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-2: 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.

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: In this algorithm, page will be replaced which is least
recently used.
Example-3: 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.
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 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.
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