Memory Allocation
Memory allocation is the process of assigning available memory space to a process or program when it needs memory.
In simple words:
Memory allocation decides where and how much RAM should be given to a process.
For example, if a process needs 200 MB, the OS must find a suitable free region of memory and allocate it.
Process P1 Needs: 200 MB ↓ Operating System ↓ Find suitable free space ↓ Allocate 200 MB
1. Why Memory Allocation Is Needed
Suppose RAM looks like this:
+------------------+ | Operating System | +------------------+ | Process P1 | +------------------+ | FREE | +------------------+ | Process P2 | +------------------+ | FREE | +------------------+
Now a new process P3 needs memory.
The OS has to decide:
- Where should P3 be placed?
- Is there enough free memory?
- Which free block should be used?
- What happens to the remaining space?
- How can memory waste be minimized?
This is the purpose of memory allocation.
2. Basic Memory Allocation Process
Process requests memory ↓ OS checks free memory ↓ Find suitable block ↓ Allocate memory ↓ Process executes ↓ Process finishes ↓ Memory is released ↓ Block becomes FREE
3. Types of Memory Allocation
At the OS level, the traditional classification is:
Memory Allocation | +----------------------+ | | ↓ ↓ Contiguous Non-Contiguous Allocation Allocation | | ↓ ↓ One continuous Process can be memory region divided | +---------+---------+ | | ↓ ↓ Paging Segmentation
We'll first understand contiguous allocation, because First Fit, Best Fit, Worst Fit, etc. are based on it.
4. Contiguous Memory Allocation
In contiguous allocation, each process receives one continuous block of physical memory.
Example:
RAM +--------------------+ | Operating System | +--------------------+ | Process P1 | +--------------------+ | Process P2 | +--------------------+ | Process P3 | +--------------------+ | FREE | +--------------------+
Each process occupies a continuous region.
5. Fixed Partition Allocation
In fixed partitioning, memory is divided into fixed-size partitions.
Example:
RAM +------------------+ | OS | +------------------+ | Partition 1 | +------------------+ | Partition 2 | +------------------+ | Partition 3 | +------------------+ | Partition 4 | +------------------+
Each partition can hold one process.
For example:
Partition 1 = 100 MB Partition 2 = 200 MB Partition 3 = 300 MB Partition 4 = 400 MB
6. Problem with Fixed Partitions
Suppose:
Partition = 100 MB Process = 60 MB
The process gets the entire 100 MB partition.
+------------------+ | Process = 60 MB | | Unused = 40 MB | +------------------+
That unused 40 MB is internal fragmentation.
Internal fragmentation = unused space inside an allocated partition/block.
7. Variable Partition Allocation
Instead of dividing memory into fixed-size partitions, the OS creates partitions according to the process's requirement.
Suppose:
P1 = 100 MB P2 = 200 MB P3 = 150 MB
The OS can allocate approximately those amounts.
+------------------+ | OS | +------------------+ | P1 = 100 MB | +------------------+ | P2 = 200 MB | +------------------+ | P3 = 150 MB | +------------------+ | FREE | +------------------+
This reduces internal fragmentation compared with fixed partitions.
However, it can cause external fragmentation.
8. External Fragmentation
Suppose memory becomes:
+----------+ | P1 | +----------+ | Free 50 | +----------+ | P2 | +----------+ | Free 100 | +----------+ | P3 | +----------+ | Free 80 | +----------+
Total free memory:
50 + 100 + 80 = 230 MB
A new process requires:
200 MB
There is enough total free memory, but there is no single contiguous 200 MB block.
Therefore, allocation fails under this contiguous scheme.
This is external fragmentation.
9. Memory Allocation Strategies
When several free blocks are available, the OS needs an allocation strategy.
The major strategies are:
First Fit Best Fit Worst Fit Next Fit
10. First Fit
First Fit allocates the first free block that is large enough.
Suppose free blocks are:
100 MB 500 MB 200 MB 300 MB 600 MB
Process requires:
212 MB
Search from the beginning:
100 → too small 500 → suitable ✓
Therefore:
212 MB allocated from 500 MB block
Remaining:
500 - 212 = 288 MB
So:
Before: 100 | 500 | 200 | 300 | 600 After: 100 | 212+288 | 200 | 300 | 600
Advantages
- Simple
- Fast
- Usually good practical performance
- Doesn't need to search the entire list
Disadvantage
It may leave many small holes near the beginning.
11. Best Fit
Best Fit chooses the smallest free block that is large enough.
Suppose:
Free blocks: 100 MB 500 MB 200 MB 300 MB 600 MB
Process needs:
212 MB
Suitable blocks:
500 MB 300 MB 600 MB
Smallest suitable block:
300 MB
Therefore:
300 MB → Process 88 MB → Remaining
Advantage
It tries to minimize the leftover space in the selected block.
Disadvantage
It usually needs to search many or all free blocks, and can create many very small holes.
12. Worst Fit
Worst Fit chooses the largest available free block.
Free blocks:
100 MB 500 MB 200 MB 300 MB 600 MB
Request:
212 MB
Largest block:
600 MB
Allocation:
600 - 212 = 388 MB
So:
600 MB ↓ 212 MB allocated 388 MB remaining
Advantage
Leaves a relatively large remaining block.
Disadvantage
It can waste large blocks and is often less effective than other strategies.
13. Next Fit
Next Fit is similar to First Fit, but instead of starting from the beginning every time, it starts searching from where the previous search ended.
Example:
100 | 500 | 200 | 300 | 600 ↑ Previous search
The next request begins from that point rather than returning to the first block.
First Fit
Start → beginning every time
Next Fit
Start → where previous search ended
14. First Fit vs Best Fit vs Worst Fit
| Feature | First Fit | Best Fit | Worst Fit |
|---|---|---|---|
| Selection | First suitable block | Smallest suitable block | Largest block |
| Search | Usually faster | Usually more searching | Usually more searching |
| Goal | Fast allocation | Minimize leftover in selected block | Leave large remainder |
| Fragmentation | Can occur | Can create tiny holes | Can waste large blocks |
| Simplicity | Very simple | Moderate | Moderate |
15. Numerical Example
This is very important for exams.
Suppose free memory blocks are:
100 KB 500 KB 200 KB 300 KB 600 KB
Processes arrive:
P1 = 212 KB P2 = 417 KB P3 = 112 KB P4 = 426 KB
Let's calculate using First Fit.
P1 = 212 KB
First suitable block:
100 → No 500 → Yes
Allocate:
500 - 212 = 288 KB
Remaining blocks:
100 288 200 300 600
P2 = 417 KB
Search:
100 → No 288 → No 200 → No 300 → No 600 → Yes
Allocate:
600 - 417 = 183 KB
Remaining:
100 288 200 300 183
P3 = 112 KB
Search:
100 → No 288 → Yes
Allocate:
288 - 112 = 176 KB
Remaining:
100 176 200 300 183
P4 = 426 KB
Search all blocks:
100 → No 176 → No 200 → No 300 → No 183 → No
Therefore:
P4 cannot be allocated
Even though there is free memory:
100 + 176 + 200 + 300 + 183 = 959 KB
There is no single block of 426 KB.
This demonstrates external fragmentation.
16. Same Example Using Best Fit
Initial:
100, 500, 200, 300, 600
P1 = 212
Suitable:
500, 300, 600
Smallest suitable:
300
Remaining:
88
Blocks:
100, 500, 200, 88, 600
P2 = 417
Suitable:
500, 600
Best:
500
Remaining:
83
P3 = 112
Suitable:
200, 600
Best:
200
Remaining:
88
P4 = 426
Suitable:
600
Allocate 426:
600 - 426 = 174
So all four processes can be allocated in this example.
17. Compaction
External fragmentation can sometimes be reduced using compaction.
Suppose:
+--------+ | P1 | +--------+ | Free | +--------+ | P2 | +--------+ | Free | +--------+ | P3 | +--------+ | Free | +--------+
The OS can move processes together:
+--------+ | P1 | +--------+ | P2 | +--------+ | P3 | +--------+ | | | FREE | | | +--------+
Now the scattered free spaces become one large free block.
Compaction = moving allocated processes/blocks so that scattered free spaces are combined into one large free space.
Problem
Compaction can be expensive because data/processes may need to be moved.
18. Internal vs External Fragmentation
| Internal Fragmentation | External Fragmentation |
|---|---|
| Waste inside allocated block | Waste between allocated blocks |
| Allocated space is larger than required | Free space is scattered |
| Common with fixed-size allocation | Common with variable-size contiguous allocation |
| Example: 100 MB block, process needs 70 MB | 50 + 100 + 80 MB free but no 200 MB block |
Easy trick:
Internal = Inside
External = Outside
19. Static vs Dynamic Allocation
Static allocation
Memory requirements are determined before execution or remain fixed.
Example:
int arr[100];
The storage requirement is known from the declaration.
Dynamic allocation
Memory is requested during execution.
C:
int *p = malloc(100 * sizeof(int));
C++:
int *p = new int[100];
Dynamic allocation provides flexibility but requires proper memory management.
20. Allocation and Deallocation
Memory allocation:
Process ↓ Request memory ↓ OS/allocator ↓ Memory assigned
When no longer needed:
Process ↓ Release memory ↓ Memory becomes free
In C:
free(p);
In C++:
delete p;
For arrays:
delete[] p;
Modern languages such as Java and Python use automatic memory management/garbage collection mechanisms.
21. Memory Allocation vs Paging
These concepts should not be confused.
Traditional contiguous allocation
Process P1 +----------------------+ | Entire process | | in one region | +----------------------+
Paging
Process P1 Page 0 Page 1 Page 2 Page 3 ↓ Can be placed in different frames Frame 5 ← Page 0 Frame 1 ← Page 1 Frame 8 ← Page 2 Frame 3 ← Page 3
Paging allows a process to be stored non-contiguously.
22. Non-Contiguous Allocation
In non-contiguous allocation, a process doesn't have to occupy one continuous physical region.
Main techniques:
Non-Contiguous Allocation | +------ Paging | +------ Segmentation
These are important because modern operating systems use virtual-memory techniques extensively.
23. Allocation Data Structures
The OS needs information about free and allocated memory.
A simple representation:
+---------+---------+---------+ | Start | Size | Status | +---------+---------+---------+ | 1000 | 200 KB | Used | | 1200 | 100 KB | Free | | 1300 | 300 KB | Used | | 1600 | 500 KB | Free | +---------+---------+---------+
The OS can maintain free-space information using structures such as:
- Free lists
- Bitmaps
- Trees and other allocator data structures
24. Buddy System
The buddy system is another memory allocation technique.
Memory is divided into blocks whose sizes are generally powers of two.
For example:
1024 KB | +---- 512 KB | | | +---- 256 KB | +---- 256 KB | +---- 512 KB
If a process requests 200 KB, a 256 KB block may be allocated.
When memory is released, compatible neighboring "buddy" blocks can potentially be merged.
256 KB + 256 KB ↓ 512 KB
The buddy system helps make splitting and merging relatively efficient.
25. Slab Allocation
Operating systems such as Linux also use specialized allocation mechanisms such as slab/slub-style allocators for efficiently allocating frequently used kernel objects.
Conceptually:
Object type ↓ Cache of ready objects ↓ Allocate quickly
This is different from the basic First Fit/Best Fit algorithms normally taught in introductory OS courses.
26. Advantages of Good Memory Allocation
A good allocation strategy should provide:
- Efficient memory utilization
- Low fragmentation
- Fast allocation
- Fast deallocation
- Good process performance
- Scalability
- Reduced overhead
27. Important Exam Questions
Q1. What is memory allocation?
Memory allocation is the process of assigning available memory space to processes or programs according to their memory requirements.
Q2. What is First Fit?
First Fit allocates the first available memory block that is large enough for the requested process.
Q3. What is Best Fit?
Best Fit allocates the smallest available block that is large enough for the requested process.
Q4. What is Worst Fit?
Worst Fit allocates the largest available memory block to the process.
Q5. What is Next Fit?
Next Fit is a variation of First Fit that starts searching from the location where the previous search ended.
Q6. What is compaction?
Compaction is the process of rearranging allocated memory so that scattered free spaces are combined into a larger contiguous free block.
🧠 Quick Memory Trick
Remember the four major allocation algorithms:
FIRST → First suitable BEST → Smallest suitable WORST → Largest suitable NEXT → Continue from previous position
And fragmentation:
INTERNAL → waste INSIDE allocated block EXTERNAL → free space scattered OUTSIDE blocks
Overall picture
MEMORY ALLOCATION | +----------+----------+ | | Contiguous Non-Contiguous | | +-----+------+ +----+----+ | | | | Fixed Variable Paging Segmentation Partition Partition | ↓ Allocation Strategies | +------------+------------+------------+ | | | | First Fit Best Fit Worst Fit Next Fit | ↓ Fragmentation / \ Internal External | ↓ Compaction