Memoryallocation

13 min read2,410 words

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

FeatureFirst FitBest FitWorst Fit
SelectionFirst suitable blockSmallest suitable blockLargest block
SearchUsually fasterUsually more searchingUsually more searching
GoalFast allocationMinimize leftover in selected blockLeave large remainder
FragmentationCan occurCan create tiny holesCan waste large blocks
SimplicityVery simpleModerateModerate

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 FragmentationExternal Fragmentation
Waste inside allocated blockWaste between allocated blocks
Allocated space is larger than requiredFree space is scattered
Common with fixed-size allocationCommon with variable-size contiguous allocation
Example: 100 MB block, process needs 70 MB50 + 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy