Go Back

A Quick Abstract:

1. Introduction to Memory Allocation:

Memory allocation is a critical aspect of operating systems, where processes request and utilize memory during execution. The goal is to efficiently manage available memory space and allocate it to processes as needed.

2. First Fit Memory Allocation:

Definition:

First Fit is a memory allocation algorithm where the operating system allocates the first available block of memory that is large enough to accommodate a process.

Process:

The operating system starts from the beginning of the available memory.

It allocates the first block that is equal to or larger than the size requested by the process.

Advantages:

Simple and easy to implement.

Quick allocation of memory.

Disadvantages:

May lead to fragmentation issues over time.

Suboptimal for memory utilization.

3. Best Fit Memory Allocation:

Definition:

 Best Fit is a memory allocation algorithm where the operating system allocates the smallest available block of memory that is large enough to accommodate a process.

Process:

The operating system searches for the smallest block that can accommodate the process.

It allocates the process to this block, leaving the smallest possible remainder.

Advantages:

Reduces external fragmentation.

Can result in better memory utilization.

Disadvantages:

May be slower than First Fit due to the search for the best fit.

Fragmentation can still occur.

4. Worst Fit Memory Allocation:

Definition:

 Worst Fit is a memory allocation algorithm where the operating system allocates the largest available block of memory to a process.

Process:

The operating system searches for the largest available block.

It allocates the process to this block, leaving a potentially large remainder.

Advantages:

Reduces external fragmentation.

Can result in better memory utilization for larger processes.

Disadvantages:

May leave smaller gaps, leading to fragmentation issues.

Slower allocation process compared to First Fit.

5. Example Scenario:

Consider memory blocks A, B, C, and D with sizes 200KB, 300KB, 150KB, and 400KB, respectively. Processes P1, P2, and P3 request memory of sizes 250KB, 200KB, and 300KB.

First Fit:

P1 → A (250KB), P2 → B (200KB), P3 → D (300KB).

Best Fit:

P1 → C (250KB), P2 → A (200KB), P3 → B (300KB).

Worst Fit:

P1 → D (250KB), P2 → D (200KB), P3 → D (300KB).

6. Conclusion:

Each memory allocation algorithm has its strengths and weaknesses. First Fit is simple but can lead to fragmentation. Best Fit aims to minimize fragmentation, while Worst Fit allocates the largest available block. The choice of algorithm depends on the system's requirements and characteristics.

Notes From The Slides:

Dynamic Storage-Allocation Problem

How to satisfy a request of size n from a list of free holes?

• First-fit:  Allocate the first hole that is big enough
• Best-fit:  Allocate the smallest hole that is big enough; must search entire list, unless ordered by size  

• Produces the smallest leftover hole

• Worst-fit:  Allocate the largest hole; must also search entire list  

• Produces the largest leftover hole

First-fit and best-fit better than worst-fit in terms of speed and storage utilization

First-Fit Memory Allocation Method

Fragmentation

• External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous
• Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
• First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation

• 1/3 may be unusable -> 50-percent rule

Fragmentation (Cont.)

• Reduce external fragmentation by compaction

• Shuffle memory contents to place all free memory together in one large block
• Compaction is possible only if relocation is dynamic, and is done at execution time
• I/O problem

• Latch job in memory while it is involved in I/O
• Do I/O only into OS buffers

• Now consider that backing store has same fragmentation problems