First Fit Algorithm In C

First Fit Algorithm:

The First Fit Algorithm is a simple memory allocation algorithm that works as follows:

✅ Many fixed-size blocks make up the memory.
✅ The technique looks for the first memory block that is big enough to hold the required memory when a process requests memory.
✅ The block is broken into two pieces if it exceeds the requested memory. The first portion is allotted to the process, while the second portion is returned to the pool of memory that is readily available.
✅ If no suitable block is found, the process is put on a waiting list until a block becomes available.
✅ When a process releases memory, the algorithm merges adjacent free blocks to form larger blocks.

C Code for First Fit Algorithm:

The upcoming code snippet demonstrates the implementation of the First Fit algorithm in C:

C Code:

Example


#include <stdio.h>

#define MEMORY_SIZE 1000
#define BLOCK_SIZE 20

int memory[MEMORY_SIZE];

void initialize_memory() {
    int i;
    for (i = 0; i < MEMORY_SIZE; i += BLOCK_SIZE) {
        memory[i] = BLOCK_SIZE;
    }
}

void print_memory() {
    int i;
    for (i = 0; i < MEMORY_SIZE; i += BLOCK_SIZE) {
        printf("%d ", memory[i]);
    }
    printf("\n");
}

void allocate_memory(int process_id, int size) {
    int i;
    for (i = 0; i < MEMORY_SIZE; i += BLOCK_SIZE) {
        if (memory[i] >= size) {
            printf("Process %d allocated block %d of size %d\n", process_id, i/BLOCK_SIZE, size);
            memory[i] -= size;
            if (memory[i] == 0) {
                printf("Block %d freed\n", i/BLOCK_SIZE);
            }
            break;
        }
    }
    if (i == MEMORY_SIZE) {
        printf("Process %d is waiting for memory\n", process_id);
    }
}

void release_memory(int process_id, int block_id) {
    int i = block_id * BLOCK_SIZE;
    int size = BLOCK_SIZE;
    while (memory[i] == 0) {
        i -= BLOCK_SIZE;
        size += BLOCK_SIZE;
    }
    printf("Block %d of size %d freed by process %d\n", i/BLOCK_SIZE, size, process_id);
    memory[i] += size;
}

int main() {
    initialize_memory();
    allocate_memory(1, 50);
    allocate_memory(2, 100);
    allocate_memory(3, 30);
    print_memory();
    release_memory(2, 2);
    print_memory();
    allocate_memory(4, 25);
    print_memory();
    return 0;
}

In the provided code snippet, the memory gets initialized through the execution of the initialize_memory function. The memory is segmented into blocks of a consistent size, and each individual block is set up with the designated block size.

The allocate_memory function is responsible for assigning memory to a process. It searches for the initial memory block that can accommodate the required memory size. Upon locating a compatible block, it divides it into two segments, with the first segment assigned to the process.

A process can free up memory that it no longer needs by utilizing the release_memory function. To form bigger blocks, it merges adjacent free blocks.

Advantages and Limitations:

The First Fit Algorithm is a simple and easy-to-implement memory allocation algorithm. It has the following advantages:

✅ It has very little processing overhead and is simple to implement.
✅ Because it ensures a rapid response time, it can be employed in real-time systems.
✅ As it looks for the first memory block that is big enough to hold the required memory, it can handle a variety of memory requests.

However, the First Fit algorithm has some limitations:

✅ It may not result in optimal memory utilization. The algorithm may leave small fragments of memory that cannot be used for any other process. This problem can be addressed using other memory allocation algorithms, such as Best Fit and Worst Fit . However, these algorithms are more complex than the First Fit algorithm .
✅ It may lead to Memory Fragmentation . As the algorithm allocates memory based on the first available block, it may result in small blocks of memory being left unused between allocated blocks. This can lead to Memory Fragmentation , which can affect the performance of the system.
✅ Process waiting times could become very long as a result.As the algorithm searches for the first available memory block, it may take longer to allocate the memory if there are no available blocks that are large enough to accommodate the requested memory.

Conclusion:

The Initial Fit Approach is a straightforward and simple memory allocation technique that is convenient to implement. It stands out as one of the most commonly employed methods for memory allocation in various operating systems. This approach locates the first available memory segment that can accommodate the required memory size. Upon identifying a suitable block, the algorithm splits it into two sections, with the initial segment being assigned to the respective process.

The article discussed the First Fit algorithm implemented in C programming language. A sample code snippet has been included for the algorithm, allowing for simple customization to meet particular needs. This code serves as a foundation for integrating the First Fit Algorithm into more extensive software projects.