First Fit memory Allocation

First-Fit Memory Allocation:

First-fit is a memory allocation strategy used in computer systems to assign memory blocks to processes. In this strategy, the operating system allocates the first available memory block that is large enough to accommodate the size of the requesting process. The search for a suitable block starts from the beginning of the memory and stops at the first block that meets the size requirements.

Implementation Using Linked List:

One common way to implement the first-fit strategy is by using a linked list data structure. The memory is represented as a linked list of blocks, where each block has information about its size, status (free or allocated), and a link to the next block in the list.

Algorithm for First-Fit Memory Allocation:

Initialization:

• Create a head node for the linked list representing the memory.
• Create list of free memory blocks

Allocation:

• Start from the head of the memory list.
• Iterate through the list until a suitable free block is found (size >= process size).
• If found, mark the block as allocated and exit the loop.
• If not found, return an error indicating insufficient memory.

Deallocation:

• Start from the head of the memory list.
• Iterate through the list until a block is found with the given process size and marked as allocated.
• If found, mark the block as free and exit the loop.
• If not found, return an error indicating that the process size was not found.

Example :Given the memory blocks:

Block	Size	Status
1	100	Free
2	50	Allocated
3	200	Free
4	80	Allocated
5	120	Free

Let's say we have a process that requests 60 units of memory using the First-Fit strategy. The algorithm will search for the first available block that is large enough to accommodate the process size.In this case it will allocate in Block1.

C program- First Fit Allocation

/*******************************************************************************/

#include <stdio.h>

#include <stdlib.h>

// Structure to represent a memory block

struct MemoryBlock {

    int size;

    int procsize;

    int is_free;

    struct MemoryBlock* next_block;

};

 struct MemoryBlock* memory_head =NULL; 

// Function to initialize a memory block

struct MemoryBlock* createMemoryBlock(int size) {

    struct MemoryBlock* block = (struct MemoryBlock*)malloc(sizeof(struct MemoryBlock));

    block->size = size;

    block->is_free = 1;  // 1 represents free, 0 represents allocated

    if ( memory_head==NULL)

       {

       block->next_block = NULL;

       memory_head=block;

       }

    else

       {

        block->next_block=memory_head;

        memory_head=block;

       }

}

   

// Function to allocate memory using the first-fit strategy

int allocateMemory(int process_size) {

    struct MemoryBlock* current_block=memory_head; 

    while (current_block) {

        if (current_block->is_free && current_block->size >= process_size) {

            // Allocate memory here

            current_block->is_free = 0;  // Mark as allocated

            current_block->procsize=process_size;

            return 1;  // Allocation successful

        }

        current_block = current_block->next_block;

    }

    // No suitable block found

    return 0;  // Allocation unsuccessful

}

// Function to deallocate memory

int deallocateMemory( int process_size) {

    struct MemoryBlock* current_block=memory_head; 

      while (current_block) {

        if (!current_block->is_free && current_block->procsize == process_size) {

            // Deallocate memory here

            current_block->is_free = 1;  // Mark as free

            current_block->procsize=0;

            return 1;  // Deallocation successful

        }

        current_block = current_block->next_block;

    }

    // Process size not found

    return 0;  // Deallocation unsuccessful

}

// Function to print the status of memory blocks

void printMemoryStatus() {

    struct MemoryBlock* current_block =memory_head;

    while (current_block) {

        printf("Block Size: %d Process Size:%d, Status: %s\n", current_block->size,current_block->procsize,(current_block->is_free ? "Free" : "Allocated"));

        current_block = current_block->next_block;

    }

}

int main() {

    // Initialize memory blocks and printMemoryStatus

    createMemoryBlock(200);

    createMemoryBlock(100);

    createMemoryBlock(300);

    createMemoryBlock(500);

    printMemoryStatus();

    int ch,size;

 do

 {

  printf("\nMenu\n----\n1.Alllocate\n2.Deallocate\n3.Display\n4.Exit\n");

  printf("\nEnter the choice:");

  scanf("%d",&ch);

  switch(ch)

  {

   case 1:

        printf("Enter the size of the process..:");

        scanf("%d",&size);

        if (allocateMemory(size)) 

            printf("Memory allocated successfully.\n");

        else 

            printf("Insufficient memory.\n");

        

        // Print memory status

         printf("Memory Status After Allocation:\n");

         printMemoryStatus(memory_head);

         break;

   case 2:

        printf("Enter the size of the process..:");

        scanf("%d",&size);

        if (deallocateMemory(size)) 

            printf("Memory deallocated successfully.\n");

        else 

            printf("Process not found.\n");

        // Print memory status after deallocation

        printf("Memory Status After Deallocation:\n");

        printMemoryStatus(memory_head);

        break;

   case 3: 

         printf("Memory Status ........:\n");

         printMemoryStatus(memory_head);

         break;

   

   case 4: 

        exit(0); 

   default:

    printf("Invalid Choice....");

  }

 }

 while(1);

   

  return 0;

}