Memory management

What is Memory?
Computer memory can be defined as a
collection of some data represented in the
binary format.
On the basis of various functions, memory
can be classified into various categories:
cache memory, main memory, secondary
memory.
A computer device that is capable to store
any information or data temporally or
permanently, is called storage device.
How Data is being stored in a computer system?
In order to understand memory management,
we have to make everything clear about how
data is being stored in a computer system.
Machine understands only binary language
that is 0 or 1. Computer converts every data
into binary language first and then stores it
into the memory.
That means if we have a program line written
as int α = 10 then the computer converts it
into the binary language and then store it into
the memory blocks.
Need for Multi programming
The program always executes in main memory.
The size of main memory affects degree of
Multi programming to most of the extent.
If the size of the main memory is larger then
CPU can load more processes in the main
memory at the same time and therefore will
increase degree of Multi programming as well
as CPU utilization.
When degree of multiprogramming will
increase, CPU will get better utilized.
 Let's consider,
 Process Size = 4 MB
 Main memory size = 4 MB
 If the time for which the process does IO is P,
 Then,
 CPU utilization = (1-P)
 let's say,
 P = 70%
 CPU utilization = 30 %
 Now, increase the memory size, Let's say it is 8 MB.
 Process Size = 4 MB
 Two processes can reside in the main memory at the same time.
 Let's say the time for which, one process does its IO is P,
 Then
 CPU utilization = (1-P^2)
 let's say P = 70 %
 CPU utilization = (1-0.49) =0.51 = 51 %
Memory Management
Memory management is the functionality of an
operating system which handles or manages primary
memory and moves processes back and forth between
main memory and disk during execution.
 Memory management keeps track of each and every
memory location, regardless of either it is allocated to
some process or it is free.
It checks how much memory is to be allocated to
processes.
It decides which process will get memory at what time.
It tracks whenever some memory gets freed or
unallocated and correspondingly it updates the status.
Objectives and functions
An Operating System does the following
activities for memory management −
Keeps tracks of primary memory, i.e., what part
of it are in use by whom, what part are not in
use.
In multiprogramming, the OS decides which
process will get memory when and how much.
Allocates the memory when a process requests
it to do so.
De-allocates the memory when a process no
longer needs it or has been terminated.
Every program we execute and every file we
access must be copied from a storage device
into main memory.
All the programs are loaded in the main memory
for execution. A complete program is loaded
into the memory, this enhance the performance.
Also, sometimes one program is dependent on
some other program. In such a case, rather than
loading all the dependent programs, CPU links
the dependent programs to the main executing
program when its required. This mechanism is
known as Dynamic Linking.
Swapping
A process needs to be in memory for
execution. But sometimes there is not enough
main memory to hold all the currently active
processes in a timesharing system.
To manage limited space in RAM and it allow
the system to run more programs.
It used when data isn’t available in RAM.
Swapping is the process of bringing in each
process in main memory, running it for a while
and then putting it back to the disk. Swap out
and Swap in
Swapping is a mechanism in which a process
can be swapped temporarily out of main memory
to secondary storage (disk) and make that
memory available to other processes. At some
later time, the system swaps back the process
from the secondary storage to main memory.
Though performance is usually affected by
swapping process but it helps in running
multiple and big processes in parallel and that's
the reason Swapping is also known as a
technique for memory compaction.
Schematic View of Swapping
Fragmentation
As processes are loaded and removed from
memory, the free memory space is broken
into little pieces.
It happens after sometimes that processes
cannot be allocated to memory blocks
considering their small size and memory
blocks remains unused.
This problem is known as Fragmentation.
Fragmentation is of two types −
External fragmentation
Total memory space is enough to satisfy a
request or to reside a process in it, but it is not
contiguous, so it cannot be used.
Internal fragmentation
Memory block assigned to process is bigger.
Some portion of memory is left unused, as it
cannot be used by another process.
The following diagram shows how
fragmentation can cause waste of memory
and a compaction technique can be used to
create more free memory out of fragmented
memory −
Logical & Physical Addresses
Logical Address:
A logical address, also known as a virtual
address, is an address generated by the CPU
during program execution. It is the address
seen by the process and is relative to the
program’s address space
An address that is created by the CPU while a
program is running is known as a logical
address. Because the logical address is virtual
—that is, it doesn’t exist physically
Physical Address:
A physical address is the actual address in the
main memory where data is stored.
 Physical addresses are used by the
Memory Management Unit (MMU) to translate
logical addresses into physical addresses.
Difference Between Logical address and Physical Address

Difference bet Logical & Physical

Parameter LOGICAL ADDRESS PHYSICAL ADDRESS

Basic generated by CPU location in a memory unit

Logical Address Space is set of Physical Address is set of all

all logical addresses generated physical addresses mapped to
Address Space
by CPU in reference to a the corresponding logical
program. addresses.

User can view the logical User can never view physical
Visibility
address of a program. address of program.

Generation generated by the CPU Computed by MMU

The user can use the logical The user can indirectly access
Access address to access the physical physical address but not
address. directly.

Physical address will not

Editable Logical address can be change.
change.

Also called virtual address. real address.

Memory Management Unit
The purpose of Memory Management Unit
(MMU) is to convert the logical address into
the physical address. The logical address is
the address generated by the CPU for every
page while the physical address is the actual
address of the frame where each page will be
stored.
When a page is to be accessed by the CPU by
using the logical address, the operating
system needs to obtain the physical address
to access that page physically.
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 paging technique.
The Physical Address Space is conceptually
divided into a number of fixed-size blocks,
called frames.
The Logical address Space is also splitted
into fixed-size blocks, called pages.
Page Size = Frame Size
Address generated by CPU is divided into
 Page number(p): Number of bits required to represent
the pages in Logical Address Space or Page number
 Page offset(d): Number of bits required to represent
particular word in a page or page size of Logical Address
Space or word number of a page or page offset.
Physical Address is divided into
 Frame number(f): Number of bits required to represent
the frame of Physical Address Space or Frame number.
 Frame offset(d): Number of bits required to represent
particular word in a frame or frame size of Physical
Address Space or word number of a frame or frame
offset.
Paging
 In Operating Systems, Paging is a storage mechanism used
to retrieve processes from the secondary storage into the
main memory in the form of pages.
 The main idea behind the paging is to divide each process in
the form of pages. The main memory will also be divided in
the form of frames.
 One page of the process is to be stored in one of the frames
of the memory. The pages can be stored at the different
locations of the memory but the priority is always to find the
contiguous frames or holes.
 Pages of the process are brought into the main memory only
when they are required otherwise they reside in the
secondary storage.
 Different operating system defines different frame sizes. The
sizes of each frame must be equal. Considering the fact that
the pages are mapped to the frames in Paging, page size
needs to be as same as frame size.
Example
Let us consider the main memory size 16 Kb and
Frame size is 1 KB therefore the main memory will be
divided into the collection of 16 frames of 1 KB each.
There are 4 processes in the system that is P1, P2, P3
and P4 of 4 KB each. Each process is divided into
pages of 1 KB each so that one page can be stored in
one frame.
Initially, all the frames are empty therefore pages of
the processes will get stored in the contiguous way.
Frames, pages and the mapping between the two is
shown in the image below.
Let us consider that, P2 and P4 are moved to
waiting state after some time. Now, 8 frames
become empty and therefore other pages can
be loaded in that empty place. The process P5
of size 8 KB (8 pages) is waiting inside the
ready queue.
Given the fact that, we have 8 non contiguous
frames available in the memory and paging
provides the flexibility of storing the process
at the different places. Therefore, we can load
the pages of process P5 in the place of P2 and
P4.
A data structure called page map table is
used to keep track of the relation between a
page of a process to a frame in physical
memory.
Paging Example
Segmentation
Segmentation is a memory management technique
in which each job is divided into several segments
of different sizes, one for each module that contains
pieces that perform related functions.
Each segment is actually a different logical address
space of the program.
When a process is to be executed, its corresponding
segments are loaded into memory.
Segmentation memory management works very
similar to paging but here segments are of variable-
length where as in paging pages are of fixed size.
A program segment contains the program's
main function, utility functions, data
structures, and so on.
The operating system maintains a segment
map table for every process and a list of free
memory blocks along with segment numbers,
their size and corresponding memory
locations in main memory.
For each segment, the table stores the
starting address of the segment and the
length of the segment.

Virtual memory
A computer can address more memory than the amount
physically installed on the system.
This extra memory is actually called virtual memory and it
is a section of a hard disk that's set up to emulate the
computer's RAM.
The main visible advantage of this scheme is that programs
can be larger than physical memory.
Virtual memory serves two purposes.
First, it allows us to extend the use of physical memory by
using disk.
Second, it allows us to have memory protection, because
each virtual address is translated to a physical address.
Virtual memory is commonly implemented by demand
paging.
Modern microprocessors intended for
general-purpose use, a memory management
unit, or MMU, is built into the hardware.
The MMU's job is to translate virtual
addresses into physical addresses.
A basic example is given below −
Demand Paging

A demand paging system is

quite similar to a paging system
with swapping where processes
reside in secondary memory and
pages are loaded only on
demand, not in advance.
While executing a program, if the program
references a page which is not available in
the main memory because it was swapped out
a little ago, the processor treats this invalid
memory reference as a page fault and
transfers control from the program to the
operating system to demand the page back
into the memory.
Advantages
Large virtual memory.
More efficient use of memory.
There is no limit on degree of
multiprogramming.
Page Replacement Algorithm

Page replacement algorithms are the

techniques using which an Operating System
decides which memory pages to swap out,
write to disk when a page of memory needs to
be allocated.
When the page that was selected for
replacement and was paged out, is
referenced again, it has to read in from disk,
and this requires for I/O completion. This
process determines the quality of the page
replacement algorithm: the lesser the time
waiting for page-ins, the better is the
A page replacement algorithm looks at the
limited information about accessing the pages
provided by hardware, and tries to select
which pages should be replaced to minimize
the total number of page misses, while
balancing it with the costs of primary storage
and processor time of the algorithm itself.
There are many different page replacement
algorithms.
We evaluate an algorithm by running it on a
particular string of memory reference and
computing the number of page faults
First In First Out (FIFO) algorithm
Oldest page in main memory is the one which
will be selected for replacement.
Easy to implement, keep a list, replace pages
from the tail and add new pages at the head.
Optimal Page algorithm
An optimal page-replacement algorithm has the lowest
page-fault rate of all algorithms. An optimal page-
replacement algorithm exists, and has been called OPT or
MIN.
Replace the page that will not be used for the longest
period of time. Use the time when a page is to be used.
Least Recently Used (LRU) algorithm
Page which has not been used for the longest
time in main memory(past) is the one which
will be selected for replacement.
Easy to implement, keep a list, replace pages
by looking back into time.
Problem1
Q. Consider a main memory with three page frames
and the following sequence of page
references:7,0,1,2,0,3,0,4,2,3,0,3,1,2,0. which one
of the following is true with respect to page
replacement policies First-In-First-out (FIFO) ?
. Consider a main memory with four page frames
following sequence of page
references:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 by
using
 optimal page replacement and LRU ?
 Find Total Page Hits and Page Fault/Page
Miss?
Hit Ratio = no.of hits/no. of references
And multiply with 100
Page Fault Ratio = no. of page fault/no. of
references
Problem 2
Q. Consider a reference string: 4, 7, 6, 1, 7, 6,
1, 2, 7, 2. the number of frames in the
memory is 3. Find out the number of page
faults respective to:
Optimal Page Replacement Algorithm
FIFO Page Replacement Algorithm
LRU Page Replacement Algorithm
Number of Page Faults in Optimal Page
Replacement Algorithm = 5
Number of Page Faults in LRU = 6
Number of Page Faults in FIFO = 6
 Calculating Hit ratio-

 Total number of page hits
 = Total number of references – Total number of page misses
or page faults
 = 10 – 6
= 4

 Thus, Hit ratio
 = Total number of page hits / Total number of references
 = 4 / 10
 = 0.4 or 40%

Calculating Miss ratio-
Total number of page misses or page faults
=6
Thus, Miss ratio
= Total number of page misses / Total
number of references
= 6 / 10
= 0.6 or 60%
Alternatively,
Miss ratio
= 1 – Hit ratio
= 1 – 0.4
= 0.6 or 60%