Memory Allocation Strategy

When a program requests

memory from the operating
system (OS) — say for creating
variables, arrays, or objects —
the OS must decide where in
the memory to place this data.
This decision-making is known
as a Memory Allocation
Strategy.
In dynamic memory
allocation, main memory
(RAM) is managed in chunks
called blocks. As programs
request and release memory,
the memory space gets
fragmented into free and
occupied blocks.
So, an important task for the
OS is to find an appropriate
free block when a program
requests memory.
To manage this efficiently,
different allocation
strategies are used.
[Link] Fit Memory Allocation
Definition:
In the First Fit strategy, the OS
searches from the beginning
of memory and allocates the
first free block that is large
enough to satisfy the request.

It doesn't check all blocks.

 • As soon as a large enough
block is found, allocation
happens.
Example:
Assume free memory blocks of
sizes: 200KB, 500KB, 300KB, 600KB,
and 100KB.
If a process requests 250KB:
• The OS starts from the beginning.
• 200KB → Not enough.
• 500KB → Enough!
→ So, it allocates 250KB from
the 500KB block.
Advantages of First Fit
• Simple and Fast:
Minimal searching — as soon
as a suitable block is found,
allocate it.
• Low Overhead:
Requires less computation
compared to other strategies
(like Best Fit or Worst Fit).
• Efficient for Small Requests:
Small processes can be
accommodated quickly.
Disadvantages of First Fit
• Memory Fragmentation:
Creates many small unused
holes at the beginning, leading
to external fragmentation.
• Wasted Space:
Sometimes bigger free
blocks get unnecessarily
split early, leaving small
unusable parts.
• Slow Over Time:
As memory becomes
fragmented, finding a
suitable block might take
 longer — because many
small blocks need to be
skipped.
Implementing First Fit using a
Linked List
Why Linked List?
• We need a dynamic
structure to manage free
memory blocks.
• A linked list is ideal: each
node represents a free
memory block.
Each node contains:
 • Start address of the free
block.
• Size of the block.
• Pointer to the next free
block.

Algorithm Steps:
1. Start from the head of
the free list.
2. Traverse the list node by
node.
3. For each block:
 o Check if its size is ≥ requested
size.
o If yes:
▪ Allocate memory from
this block.
▪ Update the linked list
(shrink the block or
remove it if fully used).
▪ Stop.
4. If no suitable block is
found, the request fails (or
triggers memory
compaction, depending on
system design).
Pseudo Code:
function
first_fit_allocate(request_size)
:
current = head
previous = NULL

while current != NULL:

if [Link] >=
request_size:
allocate memory at
[Link]
 if [Link] ==
request_size:
# Perfect fit: remove
this node
if previous == NULL:
head = [Link]
else:
[Link] =
[Link]
else:
# Split the block
[Link] =
[Link] + request_size
 [Link] =
[Link] - request_size
return SUCCESS
previous = current
current = [Link]

return FAILURE # No
sufficient block found

Example
Suppose initially free memory
blocks are like this:
Memory Blocks:
+---------+ +---------+ +--------
-+ +---------+
| 200 KB | -> | 500 KB | -> |
300 KB | -> | 600 KB |
+---------+ +---------+ +--------
-+ +---------+
A process requests 250 KB.
First Fit:
• Start at 200 KB → too small.
• 500 KB → big enough!
Allocate 250 KB from 500 KB
block.
Now the memory looks like:

Memory Blocks:
+---------+ +-----------------+
+---------+ +---------+ +-----
----+
| 200 KB | -> | 250 KB
(allocated) | 250 KB (free) | ->
| 300 KB | -> | 600 KB |
+---------+ +-----------------+
+---------+ +---------+ +-----
----+
If the 500 KB block is split,
then 250 KB is allocated to the
process,
and 250 KB remains in the free
list as a new free block.
Memory Allocation Strategy:
[Link] Fit
When a program requests
memory, another way to
allocate it is the Best
Fit strategy.

What is Best Fit?

Definition:
In the Best Fit strategy, the
OS searches the entire list of
free memory blocks and
chooses the smallest
block that is large enough to
satisfy the request.
• It finds the best
matching block that
leaves the least leftover
space.
• Aims to reduce wastage of
free memory.

Example:
Suppose free blocks
are: 200KB, 500KB, 300KB, 600
KB.
A process requests 250KB:
• 200KB → too small
• 500KB → enough (wastage
250KB)
• 300KB → enough (wastage
50KB) → Better
• 600KB → enough (wastage
350KB)
Best Fit will choose 300KB, as
it leaves only 50KB unused
(least wastage).
Advantages of Best Fit
• Reduces Fragmentation:
Tries to leave larger free
blocks available for bigger
future requests.
• Efficient Space Utilization:
More memory is used
properly, less wastage
compared to First Fit.

Disadvantages of Best Fit

• Slow Allocation:
Requires searching the entire
memory list every time a
request comes.
• Creates Very Small Holes:
Sometimes tiny unusable
holes are left behind
(called small fragments).
• Overhead:
More computation time
than First Fit.
Implementing Best Fit using a
Linked List
Linked List Structure:
Same as before — each node
contains:
• Start address
• Size of free block
• Pointer to next block

Best Fit Algorithm Steps:

1. Traverse entire free list.
2. Find all blocks that are
large enough.
 3. Pick the block with the
minimum leftover
space (smallest suitable
block).
4. Allocate memory:
o If exactly matching →
remove the block.
o If larger → split the block.

Diagram
Initial Free Memory:
+---------+ +---------+ +--------
-+ +---------+
| 200 KB | -> | 500 KB | -> |
300 KB | -> | 600 KB |
+---------+ +---------+ +--------
-+ +---------+
Process requests 250KB.
Check:
• 200 → too small
• 500 → enough (250 waste)
• 300 → enough (50 waste)
→ best choice
• 600 → enough (350 waste)
Allocate from 300 KB block.
Result:

+---------+ +---------+ +--------

-+ +---------+
| 200 KB | -> | 500 KB | -> |
50 KB | -> | 600 KB |
+---------+ +---------+ +--------
-+ +---------+
Memory Allocation Strategy:
[Link] Fit
When a program requests
memory, another strategy is
the Worst Fit.

What is Worst Fit?

Definition:
In the Worst Fit strategy, the
OS searches the entire list of
free memory
blocks and allocates memory
from the largest available
block.
• The idea is to leave behind
a reasonably large free
block after allocation.
• It aims to avoid creating
many small useless
memory fragments.

Example:
Suppose free blocks
are: 200KB, 500KB, 300KB, 600
KB.
A process requests 250KB:
• 200KB → too small
• 500KB → enough
• 300KB → enough
• 600KB → enough → largest
block
Worst Fit will choose
600KB block.
After allocating 250KB:
• 600 - 250 = 350KB left.
Advantages of Worst Fit
• Reduces Very Small
Fragments:
By allocating from the
largest block, it leaves larger
remaining parts.
• Better for Large Future
Requests:
Big processes later can still
find large blocks.
Disadvantages of Worst Fit
• Slow Allocation:
Must search the entire list
to find the largest block.
• Not Always Space Efficient:
Sometimes leaves big holes
in memory that are still
wasted.
• Higher Overhead:
Searching and managing
free memory takes more
processing.
Implementing Worst Fit using
Linked List
Linked List Structure (same):
• Start address
• Size of free block
• Pointer to next block
Worst Fit Algorithm Steps:
1. Traverse entire free list.
2. Find the block with the
largest size that is still large
enough.
3. Allocate memory:
o If exact size → remove
the block.
o If larger → split the block.

Example
Initial Free Memory:
+---------+ +---------+ +--------
-+ +---------+
| 200 KB | -> | 500 KB | -> |
300 KB | -> | 600 KB |
+---------+ +---------+ +--------
-+ +---------+
Process requests 250KB.
Check:
• 200 → too small
• 500 → enough
• 300 → enough
 • 600 → enough → largest
block
Allocate from 600 KB block.
Result:

+---------+ +---------+ +--------

-+ +---------+
| 200 KB | -> | 500 KB | -> |
300 KB | -> | 350 KB |
+---------+ +---------+ +--------
-+ +---------+
 Garbage Collection and
Compaction
1. What is Garbage
Collection?
Garbage Collection is
the process of identifying and
reclaiming memory that is no
longer in use by any program.
• After a process releases
memory (explicitly or
automatically), that
memory becomes
"garbage" if not reclaimed.
 • Garbage collection frees up
this memory so that it can
be used for new
allocations.
Key idea: Automatically clean
unused memory blocks.

Example:
Suppose memory blocks are:
Block
Siz Used/Fre
Addres
e e
s
20
1000 Used
0
15
1200 Free
0
30
1350 Used
0
10
1650 Free
0
20
1750 Free
0
Garbage collection
will identify blocks at 1200,
1650, and
1750 as free memory.

2. What is Compaction?
Compaction is the process of
rearranging memory
contents so that all free
memory is combined together
into one large block.
• After garbage collection,
free blocks may
be scattered.
 • Compaction moves used
memory blocks together
and pushes free space to
one side.
Key idea: Minimize
fragmentation and maximize
continuous free memory.

Example (after
compaction):
Initially:
[Used 200][Free 150][Used
300][Free 100][Free 200]
After Compaction:

[Used 200][Used 300][Free

450]
• All free space becomes one
large block of 450 KB.

Why are Garbage

Collection and Compaction
Important?
• Avoids memory leaks.
• Ensures large memory
blocks are available.
• Improves system
performance.
• Essential in systems
like Java Virtual Machine
(JVM) and Operating
Systems.

Linked List Representation

• Each memory block = one
node.
• Fields:
o Start Address
o Size
o Status (Used or Free)
o Pointer to next block
o Pointer to previous block
Dynamic Memory Allocation
August 14, 2023

Dynamic memory allocation in

programming refers to the
ability to allocate memory for
variables or data structures
during the runtime of a
program. Unlike static memory
allocation, where memory is
assigned at compile time,
dynamic memory allocation
allows the program to request
and release memory as
needed while the program is
running.

In languages like C, C++, and

similar low-level languages,
dynamic memory allocation is
often performed using
functions provided by the
standard library, such as
malloc, calloc, realloc, and free
in the <stdlib.h> header.
Here's an overview of these
functions with examples:

malloc (Memory Allocation):

Stands for "memory
allocation."
Allocates a specified number
of bytes of memory.
Returns a pointer to the first
byte of the allocated memory.

#include <stdlib.h>
main()
{
int *arr;
int size = 5;

arr = (int*)malloc(size *
sizeof(int));

if (arr == NULL) {
// Memory allocation failed
printf("Memory allocation
failed.\n");
} else {
 // Memory allocation
successful
// Use the 'arr' pointer to
access the allocated memory
// Don't forget to free the
memory when done
free(arr);
}
}
calloc (Contiguous
Allocation):
Stands for "contiguous
allocation."
Allocates a specified number
of blocks of memory, each
with a specified number of
bytes.
Initializes the allocated
memory to zero.

#include <stdlib.h>
main()
{
int *arr;
int size = 5;

arr = (int*)calloc(size,
sizeof(int));

if (arr == NULL) {
// Memory allocation failed
printf("Memory allocation
failed.\n");
} else {
 // Memory allocation
successful
// Use the 'arr' pointer to
access the allocated memory
// Don't forget to free the
memory when done
free(arr);
}
}
realloc (Re-Allocation):
Stands for "re-allocation."
Changes the size of the
previously allocated memory
block.
Returns a pointer to the
beginning of the reallocated
memory block.

#include <stdlib.h>
main()
{
int *arr;
int size = 5;

arr = (int*)malloc(size *
sizeof(int));

// Code to use the allocated

memory

// Need more space

size = 10;
arr = (int*)realloc(arr, size *
sizeof(int));
if (arr == NULL) {
// Memory reallocation
failed
printf("Memory reallocation
failed.\n");
} else {
// Memory reallocation
successful
// Use the 'arr' pointer to
access the reallocated
memory
 // Don't forget to free the
memory when done
free(arr);
}
}
free:
Deallocates the memory
previously allocated by malloc,
calloc, or realloc.
It's essential to free
dynamically allocated memory
to prevent memory leaks.

#include <stdlib.h>
main()
{
int *arr;
int size = 5;
arr = (int*)malloc(size *
sizeof(int));

// Code to use the allocated

memory

// Free the allocated memory

when done
free(arr);
}
Remember to check if memory
allocation was successful by
verifying if the returned
pointer is NULL. Additionally,
always free the allocated
memory when it is no longer
needed to avoid memory leaks
in your program.

Dynamic memory allocation is

particularly useful when the
size of data structures is not
known at compile time or
when memory needs to be
managed more flexibly.
However, it requires careful
handling to avoid memory
leaks or accessing memory
that has already been freed
(dangling pointers). Memory
allocated dynamically should
be released using free when
it's no longer needed to avoid
memory leaks.