Memory Allocation - First Fit

 

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.

First Fit Memory Allocation Strategy

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:

    • Check if its size is ≥ requested size.

    • 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 current.size >= request_size:
            allocate memory at current.start
            if current.size == request_size:
                # Perfect fit: remove this node
                if previous == NULL:
                    head = current.next
                else:
                    previous.next = current.next
            else:
                # Split the block
                current.start = current.start + request_size
                current.size = current.size - request_size
            return SUCCESS
        previous = current
        current = current.next

    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.

C Program: First Fit Memory Allocation

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

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

// Head pointer for the free list
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 free block to the end of the list
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 the 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");
}

// First Fit Allocation Function
void first_fit_allocate(int request_size) {
    struct Block* temp = head;
    struct Block* prev = NULL;

    while (temp != NULL) {
        if (temp->size >= request_size) {
            printf("\nMemory allocated at address: %d\n", temp->start_address);

            // Update block
            if (temp->size == request_size) {
                // Perfect fit: Remove block
                if (prev == NULL) {
                    head = temp->next;
                } else {
                    prev->next = temp->next;
                }
                free(temp);
            } else {
                // Split the block
                temp->start_address += request_size;
                temp->size -= request_size;
            }
            return;
        }
        prev = temp;
        temp = temp->next;
    }

    printf("\nAllocation failed: No sufficient memory block available.\n");
}

int main() {
    // Example initial memory blocks
    add_block(1000, 200); // Block 1
    add_block(1200, 500); // Block 2
    add_block(1700, 300); // Block 3
    add_block(2000, 600); // Block 4

    display_free_blocks();

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

    printf("Allocate a Process of size=100\n");
    first_fit_allocate(100);
    display_free_blocks();

    printf("Allocate a Process of size=700\n");
    first_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 a Process of size=250

Memory allocated at address: 1200

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------
Allocate a Process of size=100

Memory allocated at address: 1000

Free Memory Blocks:
----------------------------------------
Start: 1100, Size: 100 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
-----------------------------------------
Allocate a Process of size=700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
-----------------------------------
Start: 1100, Size: 100 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
-----------------------------------

✅ Doubly Linked List Version

This version:

  • Uses prev and next pointers in each block.

  • Supports:
    🔹 Adding memory blocks
    🔹 First fit allocation
    🔹 Displaying the current free memory blocks

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

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

// Head pointer for the doubly linked list
struct Block* head = NULL;

// Create a new memory 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;
}

// Add a block to the end of the list
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;
}

// Display the current 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");
}

// Allocate memory using First Fit strategy
void first_fit_allocate(int request_size) {
    struct Block* temp = head;

    while (temp != NULL) {
        if (temp->size >= request_size) {
            printf("\nMemory allocated at address: %d\n", temp->start_address);

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

                free(temp);
            } else {
                // Allocate part of the block
                temp->start_address += request_size;
                temp->size -= request_size;
            }

            return;
        }
        temp = temp->next;
    }

    printf("\nAllocation failed: No sufficient memory block available.\n");
}

// Main function to test the implementation
int main() {
    // Initial memory blocks
    add_block(1000, 200); // Block 1
    add_block(1200, 500); // Block 2
    add_block(1700, 300); // Block 3
    add_block(2000, 600); // Block 4

    display_free_blocks();

    // First allocation
    printf("\nAllocate a Process of size = 250\n");
    first_fit_allocate(250);
    display_free_blocks();

    // Second allocation
    printf("\nAllocate a Process of size = 100\n");
    first_fit_allocate(100);
    display_free_blocks();

    // Third allocation (expected to fail)
    printf("\nAllocate a Process of size = 500\n");
    first_fit_allocate(500);
    display_free_blocks();

 //  allocation (expected to fail)
    printf("\nAllocate a Process of size = 700\n");
    first_fit_allocate(700);
    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 a Process of size = 250

Memory allocated at address: 1200

Free Memory Blocks:
----------------------
Start: 1000, Size: 200 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------

Allocate a Process of size = 100

Memory allocated at address: 1000

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2000, Size: 600 KB
----------------------

Allocate a Process of size = 500

Memory allocated at address: 2000

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2500, Size: 100 KB
----------------------

Allocate a Process of size = 700

Allocation failed: No sufficient memory block available.

Free Memory Blocks:
----------------------
Start: 1100, Size: 100 KB
Start: 1450, Size: 250 KB
Start: 1700, Size: 300 KB
Start: 2500, Size: 100 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