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 ti
me.
 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. Sometimes complete program is loaded into
the memory, but some times a certain part or routine of
the program is loaded into the main memory only when
it is called by the program, this mechanism is
called Dynamic Loading, this enhance the
performance.
Also, at times one program is dependent on some other
program. In such a case, rather than loading all the
dependent programs, CPU links the dependent
programs to the main executing program when its
required. This mechanism is known as Dynamic
Linking.
Swapping
A process needs to be in memory for
execution. But sometimes there is not enough
main memory to hold all the currently active
processes in a timesharing system.
So, excess process are kept on disk and
brought in to run dynamically.
Swapping is the process of bringing in each
process in main memory, running it for a
while and then putting it back to the disk.
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 −

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.
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.
A reference to a memory location includes a value
that identifies a segment and an offset.
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.
When a context switch occurs, the operating
system does not copy any of the old program’s
pages out to the disk or any of the new
program’s pages into the main memory
Instead, it just begins executing the new
program after loading the first page and
fetches that program’s pages as they are
referenced.
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.
Disadvantages
Number of tables and the amount of processor
overhead for handling page interrupts are
greater than in the case of the simple paged
management techniques.
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 algorithm.
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 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 five page
frames and the following sequence of page
references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3.
which one of the following is true with respect to
page replacement policies First-In-First-out
(FIFO) and Least Recently Used (LRU)?
A. Both incur the same number of page faults
B. FIFO incurs 2 more page faults than LRU
C. LRU incurs 2 more page faults than FIFO
D. FIFO incurs 1 more page faults than LRU
FIFO
Strin 3 8 2 3 9 1 6 3 8 9 3 6 2 1 2
g x x x x x x x x x
Misse
s
3 6 6 6 6
8 8 3 3 3
2 2 2 8 8
9 9 9 9 2
1 1 1 1 1

Total Faults=9
LRU
Strin 3 8 2 3 9 1 6 3 8 9 3 6 2 1 2
g x x x x x x x x x
Misse
s
3 3 3 3 3
8 6 6 6 6
2 2 8 8 1
9 9 9 9 9
1 1 1 2 2

Total Faults=9
The Number of page faults in both the cases
is equal therefore the Answer is option (A).
Number of Page Faults = 9
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
Using FIFO
strin 4 7 6 1 7 6 1 2 7 2
g
miss x x x x x x

4 1 1 1
7 7 2 2
6 6 6 7
Using Optimal
strin 4 7 6 1 7 6 1 2 7 2
g
miss x x x x x

4 1 1
7 7 7
6 6 2
Using LRU
strin 4 7 6 1 7 6 1 2 7 2
g
miss x x x x x x

4 1 1 1
7 7 2 2
6 6 6 7
Number of Page Faults in Optimal Page
Replacement Algorithm = 5
Number of Page Faults in LRU = 6
Number of Page Faults in FIFO = 6
Problem 3
Consider page reference string 1, 3, 0, 3, 5, 6 with
3 page frames.Find number of page faults.
Using FIFO
Using optimal
Using LRU
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%
LIFO Page Replacement Algorithm-
As the name suggests, this algorithm works on
the principle of “Last in First out“.
It replaces the newest page that arrived at last
in the main memory.
It is implemented by keeping track of all the
pages in a stack.
Random Page Replacement Algorithm-
As the name suggests, this algorithm randomly
replaces any page.
So, this algorithm may behave like any other
algorithm like FIFO, LIFO, LRU, Optimal etc.