Memory Management

What is 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.
Memory Hierarchy
Memory Hierarchy
Process Address Space
• The process address space is the set of logical addresses that
a process references in its code.
• For example, when 32-bit addressing is in use, addresses can
range from 0 to 0x7fffffff; that is, 2^31 possible numbers, for a
total theoretical size of 2 gigabytes.
• The operating system takes care of mapping the logical
addresses to physical addresses at the time of memory
allocation to the program.
There are three types of addresses used in a program before and
after memory is allocated:

Memory Addresses & Description

1 Symbolic addresses
The addresses used in a source code. The variable names, constants, and instruction labels
are the basic elements of the symbolic address space.

2 Relative addresses
At the time of compilation, a compiler converts symbolic addresses into relative addresses.

3 Physical addresses
The loader generates these addresses at the time when a program is loaded into main
memory.
Base and Limit Registers
• A pair of base and limit registers define the logical
address space
• CPU must check every memory access generated in
user mode to be sure it is between base and limit
for that user
Hardware Address Protection
Swapping
• Swapping is a mechanism in which a process can be swapped
temporarily out of main memory (or move) 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
Memory management Techniques:
Contiguous Memory Allocation Types

1. Single-partition allocation
2.Multiple-partition allocation
Single-partition allocation
Low Memory
High Memory

Operating system

Process 1

Free space
Multiple Partition Allocation

• Fixed partition
• Variable partition
Operating System

Process 1

Process 2

Free space
Fixed Partition
Operating Operating
System System
Partition 1: Partition 1:
1KB 1KB
Partition2: 3KB Partition2: 1KB

Partition3: 5KB Partition3: 1KB

Partition4: 2KB Partition4: 1KB

Unequal size Equal size

Variable Partition/Dynamic Partition
Operating System

Partition 1: 1KB

Partition2: 4KB

Partition3: 2KB

Partition4: 3KB

Partition:5 5KB
Algorithms for memory allocation
• First fit
• Best fit
• Worst fit
First fit

• In the first fit, the partition is allocated which is the first

sufficient block from the top of Main Memory. It scans
memory from the beginning and chooses the first available
block that is large enough. Thus it allocates the first hole that
is large enough.
Best fit
• Allocate the process to the partition which is the first smallest
sufficient partition among the free available partition. It
searches the entire list of holes to find the smallest hole
whose size is greater than or equal to the size of the process.
Worst fit
• Allocate the process to the partition which is the largest
sufficient among the freely available partitions available in the
main memory. It is opposite to the best-fit algorithm. It
searches the entire list of holes to find the largest hole and
allocate it to process.
• Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500 KB,
300 KB and 250 KB. These partitions need to be allocated to three
processes of sizes 357 KB, 210 KB, and 468 KB in that order. Perform the
allocation of processes using-
• First Fit Algorithm
• Best Fit Algorithm
• Worst Fit Algorithm
According to question,
• The main memory has been divided into fixed size partitions as-
• First fit

• Best fit
• Worst fit

•Process P3 and Process P4 can not be allocated the memory.

•This is because no partition of size greater than or equal to the size of
process P3 and process P4 is available.
Fragmentation
• Refers to an unwanted problem that occurs in the OS in which
a process is unloaded and loaded from memory, and the free
memory space gets fragmented.
• The processes can not be assigned to the memory blocks
because of their small size. Thus the memory blocks always
stay unused
Fragmentation
Fragmentation is of two
types:
• External fragmentation
• Internal fragmentation
External Fragmentation
External fragmentation occurs whenever a method of dynamic
memory allocation happens to allocate some memory and leave a
small amount of unusable memory. The total quantity of the
memory available is reduced substantially in case there’s too much
external fragmentation. So, there’s enough memory space in order
to complete a request, and it is not contiguous. Thus, it is known
as external fragmentation.
Internal fragmentation

Whenever a memory block gets allocated with a process, and

in case the process happens to be smaller than the total
amount of requested memory, a free space is ultimately
created in this memory block. And due to this, the memory
block’s free space is unused. This is what causes internal
fragmentation.
Fragmentation (Cont.)
External fragmentation can be reduced by compaction or shuffle memory contents
to place all free memory together in one large block. To make compaction feasible,
relocation should be dynamic.

The internal fragmentation can be reduced by effectively assigning the smallest

partition but large enough for the process
Non contiguous memory allocation
techniques
• In non-contiguous memory allocation, different parts of a
process are allocated to different places in Main Memory
• There are five types of Non-Contiguous Allocation of Memory
in the Operating System:
• Paging
• Multilevel Paging
• Inverted Paging
• Segmentation
• Segmented Paging
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 noncontiguous memory though every
segment is loaded into a contiguous block of available
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.
Segmentation
• Segmentation is a memory-management scheme that
supports the programmer view of memory.
• A logical address space is a collection of segments.
• Each segment has a name and a length. The addresses specify
both the segment name and the offset within the segment.
The programmer therefore specifies each address by two
quantities: a segment name and an offset.
Logical View of Segmentation

4
1

3 2
4

user space physical memory space

User’s View of a Program
• For simplicity of implementation, segments are numbered
and are referred to by a segment number, rather than by a
segment name. Thus, a logical address consists of a two tuple:
<segment-number, offset>.
• A C compiler might create separate segments for the
following:
• 1. The code
• 2. Global variables
• 3. The heap, from which memory is allocated
• 4. The stacks used by each thread
• 5. The standard C library
•
Segmentation
The segment base
Hardware
contains the starting
physical address where
the segment resides in
memory, and
• The segment limit
specifies the length of
the segment.
Segmentation Example
• For example, segment 2 is 400 bytes long and begins at
location 4300. Thus, a reference to byte 53 of segment 2 is
mapped onto location 4300 + 53 = 4353.
• A reference to segment 3, byte 852, is mapped to 3200 (the
base of segment 3) + 852 = 4052.
• A reference to byte 1222 of segment 0 would result in a trap
to the operating system, as this segment is only 1,000 bytes
long.
Advantages of Segmentation
 No internal fragmentation
 Less overhead
 It is easier to relocate segments than entire address space.
Disadvantages
 It can have external fragmentation.
 it is difficult to allocate contiguous memory to variable sized
partition.
 Costly memory management algorithms.
Consider the following segment table-
Segment No. Base Length Calculate the physical address for the following
0 1219 700 logical address?
1.0, 430
1 2300 14 2.1, 11
3.2, 100
2 90 100

•Segment Offset must always lie in the range [0, limit-1].

•If segment offset becomes greater than or equal to the limit of segment, then trap
addressing error is produced.

1. Physical Address = 1219 + 430 = 1649, as 430 <(700-1)

2. Physical Address =2300+11=2311 as 11<(14-1)

3. In the segment table, limit of segment-2 is 100.

Thus, segment offset must always lie in the range = [0, 100-1] = [0, 99]
Since generated segment offset does not lie in the above range, so request generated is
invalid. Therefore, trap will be produced.
Assignment
Consider the following segment table:

What are the physical addresses for the following logical addresses?
Paging
• 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 that's set up to emulate the computer's
RAM.
• Paging technique plays an important role in implementing
virtual memory.
• Paging is a memory management technique in which process
address space is broken into blocks of the same size called
pages (size is power of 2, between 512 bytes and 8192
bytes). The size of the process is measured in the number of
pages.
• Similarly, main memory is divided into small fixed-sized blocks
of (physical) memory called frames and the size of a frame is
kept the same as that of a page to have optimum utilization
of the main memory and to avoid external fragmentation.
Page map table
Address Translation
Paging model of logical and physical
memory.
• If the size of the logical address space is 2^m, and a page size
is 2^n bytes, then the high-order m− n bits of a logical address
designate the page number, and the n low-order bits
designate the page offset. Thus, the logical address is as
follows:

where p is an index into the page table and d is the

displacement within the page.
Paging example for a 32-byte memory with
4-byte pages.
• Here, in the logical
address, n= 2 and m =
4. Using a page size of
4 bytes and a physical
memory of 32 bytes (8
pages),

Physical address = Fn*frame size +offset

• Logical address 0 is page 0, offset 0. Indexing into the page
table, we find that page 0 is in frame 5. Thus, logical address 0
maps to physical address 20 [= (5 × 4) +0].
• Logical address 3 (page 0, offset 3) maps to physical address
23 [= (5 × 4) +3].
• Logical address 4 is page 1, offset 0; according to the page
table, page 1 is mapped to frame 6. Thus, logical address 4
maps to physical address
24 [= (6 × 4) + 0].
• Logical address 13 maps to physical address 9.
• Assuming a 1-KB page size, what are the page numbers and
offsets for the following address references (provided as
decimal numbers):
• a. 3085
• b. 42095
• c. 215201
• d. 650000
• e. 2000001
• Page number = logical address / page size

• Offset = logical address mod page size

• page size = 1 KB = 1024 B
Page Number offset
3085/1024 = 3 3085 mod 1024 = 13
42095/1024 = 41 42095 mod 1024 = 111
2000001/1024 = 1953 2000001 mod 1024 = 129
2. Consider a logical address space of 256 pages with a 4-KB page
size,mapped onto a physical memory of 64 frames.
• a. How many bits are required in the logical address?
Logical address space (/size) = # of pages × page size
Logical address space (/size) = 256 × 4 KB
Logical address space (/size) = 256 × 4096
Logical address space (/size) = 1048576
Logical address space (/size) = 2^20

• b. How many bits are required in the physical address?

Let x be the number of physical addresses
Physical address space (/size) = 2^x
Physical address space (size) = # of frames × frame size
Physical address space (size) = 64 × 4 KB
Physical address space (size) = 64 × 4096
Physical address space (size) = 2^6 × 2^12 = 2^18
Number of required bits in the physical address=x =18 bit
Advantages and Disadvantages of Paging
• Paging reduces external fragmentation, but still suffer from
internal fragmentation.
• Paging is simple to implement and assumed as an efficient
memory management technique.
• Due to equal size of the pages and frames, swapping
becomes very easy.
• Page table requires extra memory space, so may not be good
for a system having small RAM.
• Thank you