-1-

Memory Management:
Introduction:
Memory management is the act of managing computer memory. In its simpler
forms, this involves providing ways to allocate portions of memory to programs at their
request, and freeing it for reuse when no longer needed. The management of main
memory is critical to the computer system.
Virtual memory systems separate the memory addresses used by a process from
actual physical addresses, allowing separation of processes and increasing the effectively
available amount of RAM using disk swapping. The quality of the virtual memory
manager can have a big impact on overall system performance.

Basic:
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.
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.

MNM(OS)
 -2-

Role of Memory Management:

These are the following important roles of memory management in a computer
system-
 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.
 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.
 The memory manager is responsible for protecting the memory allocated to each
process from being corrupted by another process. If this is not ensured, then the
system may exhibit unpredictable behavior.
 Memory managers should enable sharing of memory space between processes.
Thus, two programs can reside at the same memory location although at different
times.

Address Binding:
The Address Binding refers to the mapping of computer instructions and
data to physical memory locations. Both logical and physical addresses are
used in computer memory. It assigns a physical memory region to a logical
pointer by mapping a physical address to a logical address known as a virtual
address. It is also a component of computer memory management that the OS
performs on behalf of applications that require memory access.
These are different types of Address Binding as follows-
Compile Time Address Binding:
It is the first type of address binding. It occurs when the compiler is responsible
for performing address binding, and the compiler interacts with the operating
system to perform the address binding. In other words, when a program is

MNM(OS)
 -3-

executed, it allocates memory to the system code of the computer. The address
binding assigns a logical address to the beginning of the memory segment to
store the object code. Memory allocation is a long-term process and may only
be modified by recompiling the program.
Load Time Address Binding:
It is another type of address binding. It is done after loading the program
in the memory, and it would be done by the operating system memory
manager, i.e., loader. If memory allocation is specified when the program is
assigned, no program in its compiled state may ever be transferred from one
computer to another. Memory allocations in the executable code may already
be in use by another program on the new system. In this case, the logical
addresses of the program are not connected to physical addresses until it is
applied and loaded into memory.
Execution Time or Dynamic Address Binding:
Execution time address binding is the most popular type of binding for
scripts that aren't compiled because it only applies to variables in the program.
When a variable in a program is encountered during the processing of
instructions in a script, the program seeks memory space for that variable. The
memory would assign the space to that variable until the program sequence
finished or unless a specific instruction within the script released the memory
address connected to a variable.

Logical and Physical Address Space:

In operating systems, logical and physical addresses are used to manage and
access memory.

MNM(OS)
 -4-

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. The process
accesses memory using logical addresses, which are translated by the operating
system into physical addresses.
Physical address: A physical address is the actual address in main memory
where data is stored. It is a location in physical memory, as opposed to a virtual
address. Physical addresses are used by the memory management unit (MMU)
to translate logical addresses into physical addresses.
The translation from logical to physical addresses is performed by the
operating system’s memory management unit. The MMU uses a page table to
translate logical addresses into physical addresses. The page table maps each
logical page number to a physical frame number.

MNM(OS)
 -5-

Overlays in Memory Management:

In memory management, overlays refer to a technique used to manage
memory efficiently by overlaying a portion of memory with another program or
data. The idea behind overlays is to only load the necessary parts of a program
into memory at a given time, freeing up memory for other tasks. The unused
portions of the program are kept on disk or other storage, and are loaded into
memory as needed. This allows programs to be larger than the available
memory, but still run smoothly.
The main problem in Fixed partitioning is the size of a process has to be
limited by the maximum size of the partition, which means a process can never
be span over another. In order to solve this problem, earlier people have used
some solution which is called as Overlays. The concept of overlays is that
whenever a process is running it will not use the complete program at the same
time, it will use only some part of it. Then overlays concept says that whatever
part you required, you load it and once the part is done, then you just unload it,
means just pull it back and get the new part you required and run it. Formally,
“The process of transferring a block of program code or other data into internal
memory, replacing what is already stored”. Sometimes it happens that compare
to the size of the biggest partition, the size of the program will be even more,
then, in that case, you should go with overlays.
So overlay is a technique to run a program that is bigger than the size of
the physical memory by keeping only those instructions and data that are
needed at any given time. Divide the program into modules in such a way that
not all modules need to be in the memory at the same time.
Advantages of using overlays include:

MNM(OS)
 -6-

 Increased memory utilization: Overlays allow multiple programs to

share the same physical memory space, increasing memory utilization
and reducing the need for additional memory.
 Reduced load time: Only the necessary parts of a program are loaded
into memory, reducing load time and increasing performance.
 Improved reliability: Overlays reduce the risk of memory overflow,
which can cause crashes or data loss.
 Reduce memory requirement
 Reduce time requirement

Fixed partition:
Fixed partitioning, also known as static partitioning is a memory
allocation technique used in operating systems to divide the physical memory
into fixed-size partitions or regions, each assigned to a specific process or user.
Each partition is typically allocated at system boot time and remains dedicated
to a specific process until it terminates or releases the partition. In fixed
partitioning, the memory is divided into fixed-size chunks, with each chunk
being reserved for a specific process. When a process requests memory, the
operating system assigns it to the appropriate partition. Each partition is of the
same size, and the memory allocation is done at system boot time.
Fixed partitioning has several advantages over other memory allocation
techniques. First, it is simple and easy to implement. Second, it is predictable,
meaning the operating system can ensure a minimum amount of memory for
each process. Third, it can prevent processes from interfering with each other’s
memory space, improving the security and stability of the system.
However, fixed partitioning also has some disadvantages. It can lead to
internal fragmentation, where memory in a partition remains unused. This can

MNM(OS)
 -7-

happen when the process’s memory requirements are smaller than the partition
size, leaving some memory unused. Additionally, fixed partitioning limits the
number of processes that can run concurrently, as each process requires a
dedicated partition.
Dynamic Partitioning:
Dynamic partitioning tries to overcome the problems caused by fixed
partitioning. In this technique, the partition size is not declared initially. It is
declared at the time of process loading.
The first partition is reserved for the operating system. The remaining
space is divided into parts. The size of each partition will be equal to the size of
the process. The partition size varies according to the need of the process so
that the internal fragmentation can be avoided.
Advantages:
No Internal Fragmentation: Given the fact that the partitions in dynamic
partitioning are created according to the need of the process, It is clear that
there will not be any internal fragmentation because there will not be any
unused remaining space in the partition.
No Limitation on the size of the process: In Fixed partitioning, the process
with the size greater than the size of the largest partition could not be executed
due to the lack of sufficient contiguous memory. Here, In Dynamic
partitioning, the process size can't be restricted since the partition size is
decided according to the process size.
Degree of multiprogramming is dynamic: Due to the absence of internal
fragmentation, there will not be any unused space in the partition hence more
processes can be loaded in the memory at the same time.

MNM(OS)
 -8-

Swapping:
To replace pages or segments of data in memory. Swapping is a useful technique
that enables a computer to execute programs and manipulate data files larger than main
memory. The operating system copies as much data as possible into main memory, and
leaves the rest on the disk.
A process must be loaded into memory in order to execute. If there is not enough
memory available to keep all running processes in memory at the same time, then some
processes that are not currently using the CPU may have their memory swapped out to a
fast local disk called the backing store.

Figure: Swapping of two processes using a disk as a backing store

 If compile-time or load-time address binding is used, then processes must be

swapped back into the same memory location from which they were swapped out.
If execution time binding is used, then the processes can be swapped back into
any available location.
 Swapping is a very slow process compared to other operations. For example- if a
user process occupied 10 MB and the transfer rate for the backing store were 40
MB per second, then it would take 1/4 second ( 250 milliseconds ) just to do the
data transfer. Adding in a latency lag of 8 milliseconds and ignoring head seek
time for the moment, and further recognizing that swapping involves moving old
data out as well as new data in, the overall transfer time required for this swap is

MNM(OS)
 -9-

512 milliseconds, or over half a second. For efficient processor scheduling the
CPU time slice should be significantly longer than this lost transfer time.
 To reduce swapping transfer overhead, it is desired to transfer as little information
as possible, which requires that the system know how much memory a
process is using, as opposed to how much it might use. Programmers can help
with this by freeing up dynamic memory that they are no longer using.
 It is important to swap processes out of memory only when they are idle, or more
to the point, only when there are no pending I/O operations. (Otherwise the
pending I/O operation could write into the wrong process's memory space.) The
solution is to either swap only totally idle processes, or do I/O operations only
into and out of OS buffers, which are then transferred to or from process's main
memory as a second step.
 Most modern OS no longer use swapping, because it is too slow and there are
faster alternatives available. (E.g. Paging.) However, some UNIX systems will
still invoke swapping if the system gets extremely full, and then discontinue
swapping when the load reduces again. Windows would use a modified version of
swapping that was somewhat controlled by the user, swapping process's out if
necessary and then only swapping them back in when the user focused on that
particular window.

Continuous Memory Allocation:

One approach to memory management is to load each process into a contiguous
space. The operating system is allocated space first, usually at either low or high memory
locations, and then the remaining available memory is allocated to processes as needed.
(The OS is usually loaded low, because that is where the interrupt vectors are located, but
on older systems part of the OS was loaded high to make more room in low memory for
user processes.)
Memory Protection (Memory Mapping and Protection):
The system shown in the following figure below allows protection against user
programs accessing areas that they should not, allows programs to be relocated to
different memory starting addresses as needed, and allows the memory space devoted to
the OS to grow or shrink dynamically as needs change.

MNM(OS)
 - 10 -

Figure: Hardware support for relocation and limit registers

Memory Allocation:
One method of allocating contiguous memory is to divide all available memory
into equal sized partitions, and to assign each process to their own partition. This restricts
both the number of simultaneous processes and the maximum size of each process, and is
no longer used.
An alternate approach is to keep a list of unused (free) memory blocks (whole),
and to find a hole of a suitable size whenever a process needs to be loaded into memory.
There are many different strategies for finding the "best" allocation of memory to
processes, including the three most commonly discussed:
 First fit: Search the list of holes until one is found that is big enough to satisfy the
request, and assign a portion of that hole to that process. Whatever fraction of the
hole not needed by the request is left on the free list as a smaller hole. Subsequent
requests may start looking either from the beginning of the list or from the point
at which this search ended.
 Best fit: Allocate the smallest hole that is big enough to satisfy the request. This
saves large holes for other process requests that may need them later, but the
resulting unused portions of holes may be too small to be of any use, and will
therefore be wasted. Keeping the free list sorted can speed up the process of
finding the right hole.
 Worst fit: Allocate the largest hole available, thereby increasing the likelihood
that the remaining portion will be usable for satisfying future requests.

MNM(OS)
 - 11 -

Note: Simulations show that either first or best fit are better than worst fit in terms of
both time and storage utilization. First and best fits are about equal in terms of storage
utilization, but first fit is faster.
Fragmentation:
 All the memory allocation strategies suffer from external fragmentation, though
first and best fits experience the problems more so than worst fit. External
fragmentation means that the available memory is broken up into lots of little
pieces, none of which is big enough to satisfy the next memory requirement,
although the sum total could.
 The amount of memory lost to fragmentation may vary with algorithm, usage
patterns, and some design decisions such as which end of a hole to allocate and
which end to save on the free list.
 Statistical analysis of first fit, for example, shows that for N blocks of allocated
memory, another 0.5 N will be lost to fragmentation.
 Internal fragmentation also occurs, with all memory allocation strategies. This is
caused by the fact that memory is allocated in blocks of a fixed size, whereas the
actual memory needed will rarely be that exact size. For a random distribution of
memory requests, on the average 1/2 block will be wasted per memory request,
because on the average the last allocated block will be only half full.
o Note that the same effect happens with hard drives, and that modern
hardware gives us increasingly larger drives and memory at the expense of
ever larger block sizes, which translates to more memory lost to internal
fragmentation.
o Some systems use variable size blocks to minimize losses due to internal
fragmentation.
 If the programs in memory are reloadable, ( using execution-time address
binding ), then the external fragmentation problem can be reduced
via compaction, i.e. moving all processes down to one end of physical memory.
This only involves updating the relocation register for each process, as all internal
work is done using logical addresses.

MNM(OS)
 - 12 -

 Another solution as we will see in upcoming sections is to allow processes to use

non-contiguous blocks of physical memory, with a separate relocation register for
each block.

Paging System:
Paging is a memory management scheme that allows processes physical memory
to be discontinuous, and which eliminates problems with fragmentation by allocating
memory in equal sized blocks known as pages. Paging eliminates most of the problems of
the other methods discussed previously, and is the predominant memory management
technique used today. The basic idea behind paging is to divide physical memory into a
number of equal sized blocks called frames, and to divide programs logical memory
space into blocks of the same size called pages.
Paging is a memory management technique the scheme removes requirement of
contagions allocation of physical memory. In paged system each process is divided into
set of pages frames of the same size. The following figure shows an example of 3
processes which have been loaded into contagious pages in the memory.

MNM(OS)
 - 13 -

In the above figure shows that there remains 3 free pages in memory which are available
for use. Suppose now that process ‘B’ terminates and release its allocation of pages. This
position is shown in the following figure ‘ B’.

Here we have now two sections of free pages. Let us assume that two more
process require to be loaded process ‘D’ needs 3 pages ‘E’ need 4 pages which are free,
this shown in following figure.

MNM(OS)
 - 14 -

E1

E2

C5

C6

Segmentation: Segmentation is a technique to break memory into logical pieces

where each piece represents a group of related information. For example, data segments
or code segment for each process, data segment for operating system and so on.
Segmentation can be implemented using or without using paging. Unlike paging,
segments are having varying sizes and thus eliminates internal fragmentation. External
fragmentation still exists but to lesser extent.

Address generated by CPU is divided into:

MNM(OS)
 - 15 -

 Segment number (s): Segment number is used as an index into a segment table
which contains base address of each segment in physical memory and a limit of
segment.

 Segment offset (o): Segment offset is first checked against limit and then is
combined with base address to define the physical memory address.

Virtual Memory: Virtual memory is a technique that allows the execution of

processes which are not completely available in memory. The main visible advantage of
this scheme is that programs can be larger than physical memory. Virtual memory is the
separation of user logical memory from physical memory. This separation allows an
extremely large virtual memory to be provided for programmers when only a smaller
physical memory is available. Following are the situations, when entire program is not
required to be loaded fully in main memory.

 User written error handling routines are used only when an error occurred in the
data or computation.
 Certain options and features of a program may be used rarely.
 Many tables are assigned a fixed amount of address space even though only a
small amount of the table is actually used.

MNM(OS)
 - 16 -

 The ability to execute a program that is only partially in memory would counter
many benefits.
 Less number of I/O would be needed to load or swap each user program into
memory.
 A program would no longer be constrained by the amount of physical memory
that is available.
 Each user program could take less physical memory, more programs could be run
the same time, with a corresponding increase in CPU utilization and throughput.

Virtual memory is commonly implemented by demand paging. It can also be

implemented in a segmentation system. Demand segmentation can also be used to
provide virtual memory.

Demand Paging: A demand paging system is quite similar to a paging system with
swapping. When we want to execute a process, we swap it into memory. Rather than
swapping the entire process into memory, however, we use a lazy swapper called pager.
When a process is to be swapped in the pager guesses which pages will be used
before the process is swapped out again? Instead of swapping in a whole process, the
pager brings only those necessary pages into memory. Thus, it avoids reading into
memory pages that will not be used in anyway, decreasing the swap time and the
amount of physical memory needed.
Hardware support is required to distinguish between those pages that are in
memory and those pages that are on the disk using the valid-invalid bit scheme. Where

MNM(OS)
 - 17 -

valid and invalid pages can be checked by checking the bit. Marking a page will have no
effect if the process never attempts to access the page. While the process executes and
accesses pages that are memory resident, execution proceeds normally.

Access to a page marked invalid causes a page-fault trap. This trap is the result of the
operating system's failure to bring the desired page into memory. But page fault can be
handled as following

Step Description
Step 1 Check an internal table for this process, to determine whether the reference was
a valid or it was an invalid memory access.
Step 2 If the reference was invalid, terminate the process. If it was valid, but page have
not yet brought in, page in the latter.

MNM(OS)
 - 18 -

Step 3 Find a free frame.

Step 4 Schedule a disk operation to read the desired page into the newly allocated
frame.
Step 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.
Step 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.
Therefore, the operating system reads the desired page into memory and restarts
the process as though the page had always been in memory.

Advantages:
1) Large virtual memory.
2) More efficient use of memory.
3) Unconstrained multiprogramming. There is no limit on degree of
multiprogramming.
Disadvantages:
 Number of tables and amount of processor overhead for handling page interrupts

are greater than in the case of the simple paged management techniques.
 Due to the lack of an explicit constraint on a job address space size.

Page Replacement Algorithm: Page replacement algorithms are the techniques

using which Operating System decides which memory pages to swap out, write to disk
when a page of memory needs to be allocated. Paging happens whenever a page fault
occurs and a free page cannot be used for allocation purpose accounting to reason that
pages are not available or the number of free pages is lower than required pages.
When the page that was selected for replacement and was paged out, is
referenced again then 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

MNM(OS)
 - 19 -

algorithm by running it on a particular string of memory reference and computing the

number of page faults.

Reference String:
The string of memory references is called reference string. Reference strings are
generated artificially or by tracing a given system and recording the address of each
memory reference. The latter choice produces a large number of data, where we note
two things.

 For a given page size we need to consider only the page number, not the entire
address.
 If we have a reference to a page p, then any immediately following references to
page p will never cause a page fault. Page p will be in memory after the first
reference; the immediately following references will not fault.
 For example, consider the following sequence of addresses -
123,215,600,1234,76,96
 If page size is 100 then the reference string is 1,2,6,12,0,0

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.

MNM(OS)
 - 20 -

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.

MNM(OS)
 - 21 -

Page Buffering algorithm:

 To get process start quickly, keep a pool of free frames.

 On page fault, select a page to be replaced.

 Write new page in the frame of free pool, mark the page table and restart the
process.
 Now write the dirty page out of disk and place the frame holding replaced page in
free pool.

Least frequently Used (LFU) algorithm:

 Page with the smallest count is the one which will be selected for replacement.

 This algorithm suffers from the situation in which a page is used heavily during
the initial phase of a process, but then is never used again.

Most frequently Used (MFU) algorithm:

 This algorithm is based on the argument that the page with the smallest count was

probably just brought in and has yet to be used.

MNM(OS)