Memory Allocation - Best Fit

 

Memory Allocation Strategy: Best 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, 600KB.

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:

    • If exactly matching → remove the block.

    • 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  |
+---------+    +---------+    +---------+    +---------+

Best Fit C Program
#include <stdio.h>
#include <stdlib.h>

// Define a structure for memory block
struct Block {
    int start_address;
    int size;
    struct Block* next;
};

struct Block* head = NULL;

// Function to create a new block
struct Block* create_block(int start, int size) {
    struct Block* new_block = (struct Block*)malloc(sizeof(struct Block));
    new_block->start_address = start;
    new_block->size = size;
    new_block->next = NULL;
    return new_block;
}

// Function to add a block to the end
void add_block(int start, int size) {
    struct Block* new_block = create_block(start, size);

    if (head == NULL) {
        head = new_block;
        return;
    }

    struct Block* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = new_block;
}

// Function to display free blocks
void display_free_blocks() {
    struct Block* temp = head;
    printf("\nFree Memory Blocks:\n");
    printf("----------------------\n");
    while (temp != NULL) {
        printf("Start: %d, Size: %d KB\n", temp->start_address, temp->size);
        temp = temp->next;
    }
    printf("----------------------\n");
}

// Best Fit Allocation Function
void best_fit_allocate(int request_size) {
    struct Block* temp = head;
    struct Block* best_block = NULL;
    struct Block* best_prev = NULL;
    struct Block* prev = NULL;

    // Find the best block
    while (temp != NULL) {
        if (temp->size >= request_size) {
            if (best_block == NULL || temp->size < best_block->size) {
                best_block = temp;
                best_prev = prev;
            }
        }
        prev = temp;
        temp = temp->next;
    }

    if (best_block == NULL) {
        printf("\nAllocation failed: No sufficient memory block available.\n");
        return;
    }

    printf("\nMemory allocated at address: %d\n", best_block->start_address);

    // Allocate memory
    if (best_block->size == request_size) {
        // Perfect fit
        if (best_prev == NULL) {
            head = best_block->next;
        } else {
            best_prev->next = best_block->next;
        }
        free(best_block);
    } else {
        // Split the block
        best_block->start_address += request_size;
        best_block->size -= request_size;
    }
}

int main() {
    // Example initial blocks
    add_block(1000, 200);
    add_block(1200, 500);
    add_block(1700, 300);
    add_block(2000, 600);

    display_free_blocks();

    // Example allocations
    printf("Allocate Process of size 250\n");
    best_fit_allocate(250);
    display_free_blocks();

    printf("Allocate Process of size 100\n");
    best_fit_allocate(100);
    display_free_blocks();

    printf("Allocate Process of size 700\n");
    best_fit_allocate(700); // Should fail
    display_free_blocks();

    return 0;
}


Output

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 250

Memory allocated at address: 1700

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 100

Memory allocated at address: 1000

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------

Best Fit C Program-Doubly Linked List

#include <stdio.h>
#include <stdlib.h>

// Define a structure for memory block (doubly linked)
struct Block {
    int start_address;
    int size;
    struct Block* next;
    struct Block* prev;
};

struct Block* head = NULL;

// Function to create a new block
struct Block* create_block(int start, int size) {
    struct Block* new_block = (struct Block*)malloc(sizeof(struct Block));
    new_block->start_address = start;
    new_block->size = size;
    new_block->next = NULL;
    new_block->prev = NULL;
    return new_block;
}

// Function to add a block at the end
void add_block(int start, int size) {
    struct Block* new_block = create_block(start, size);

    if (head == NULL) {
        head = new_block;
        return;
    }

    struct Block* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = new_block;
    new_block->prev = temp;
}

// Function to display free memory blocks
void display_free_blocks() {
    struct Block* temp = head;
    printf("\nFree Memory Blocks:\n");
    printf("----------------------\n");
    while (temp != NULL) {
        printf("Start: %d, Size: %d KB\n", temp->start_address, temp->size);
        temp = temp->next;
    }
    printf("----------------------\n");
}

// Best Fit Allocation using Doubly Linked List
void best_fit_allocate(int request_size) {
    struct Block* temp = head;
    struct Block* best_block = NULL;

    // Find the best (smallest fitting) block
    while (temp != NULL) {
        if (temp->size >= request_size) {
            if (best_block == NULL || temp->size < best_block->size) {
                best_block = temp;
            }
        }
        temp = temp->next;
    }

    if (best_block == NULL) {
        printf("\nAllocation failed: No sufficient memory block available.\n");
        return;
    }

    printf("\nMemory allocated at address: %d\n", best_block->start_address);

    if (best_block->size == request_size) {
        // Perfect fit: Remove the block
        if (best_block->prev == NULL)
            head = best_block->next;
            
         
        else if (best_block->next != NULL)
            {best_block->next->prev = best_block->prev;
            best_block->prev->next = best_block->next;}
            else //last block
            {
                best_block->prev->next=NULL;
            }

        free(best_block);
    } else {
        // Split the block
        best_block->start_address += request_size;
        best_block->size -= request_size;
    }
}

int main() {
    // Initial memory blocks
    add_block(1000, 200);
    add_block(1200, 500);
    add_block(1700, 300);
    add_block(2000, 600);

    display_free_blocks();

    // Allocate processes
    printf("Allocate Process of size 250\n");
    best_fit_allocate(250);
    display_free_blocks();

    printf("Allocate Process of size 100\n");
    best_fit_allocate(100);
    display_free_blocks();

    printf("Allocate Process of size 700\n");
    best_fit_allocate(700); // Should fail
    display_free_blocks();

    return 0;
}


Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 250

Memory allocated at address: 1700

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 100

Memory allocated at address: 1000

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------
Allocate Process of size 700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1200, Size: 500 KB
Start: 1950, Size: 50 KB
Start: 2000, Size: 600 KB
----------------------

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more