Best-Fit Memory Allocation Strategy:

 

Best-Fit Memory Allocation Strategy:

Overview:

The Best-Fit strategy aims to minimize wasted memory by allocating the smallest available block that is large enough to satisfy a memory request. It involves searching for the smallest free block that can accommodate the incoming process.

Algorithm:

1. Initialization:

   • Create a linked list representing the memory blocks.
   • Each node in the list contains information about the size of the block, whether it is free or allocated, and a link to the next block.

2. Allocation:

   • Start from the beginning of the memory list.
   • Initialize a pointer to track the best-fit block (the smallest block that fits the process size).
   • Iterate through the list:
     • If the block is free and has a size greater than or equal to the process size:
       • If the best-fit pointer is not set or the current block is smaller than the current best-fit block, update the best-fit pointer.
   • If a best-fit block is found, allocate memory in that block.

3. Deallocation:

   • When a process is deallocated, mark the corresponding block as free.

Example: Consider the following memory blocks:

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

If a process needs 120 units is requested, the Best-Fit strategy should indeed select the smallest available block that is still large enough to accommodate the process. In this case, Block 5 with a size of 120 is the best fit, as it minimizes wasted memory.

In the Best-Fit strategy, it's not always guaranteed that the first block with enough size will be used. The algorithm considers all available free blocks and selects the one that minimizes wasted memory.

int bestFitAllocateMemory(struct MemoryBlock* head, int process_size) { struct MemoryBlock* current_block = head; struct MemoryBlock* best_fit_block = NULL; while (current_block) { if (current_block->is_free && current_block->size >= process_size) { if (best_fit_block == NULL || current_block->size < best_fit_block->size) { best_fit_block = current_block; } } current_block = current_block->next_block; } if (best_fit_block) { // Allocate memory in the best-fit block best_fit_block->is_free = 0; // Mark as allocated return 1; // Allocation successful } else { // No suitable block found return 0; // Allocation unsuccessful } }

This algorithm ensures that the smallest available block that can accommodate the process is selected for allocation.

Note: In a real-world scenario, you would need to handle additional considerations such as memory fragmentation and optimize for performance.

C program Implementation- Best Fit strategy

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

#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 bestFitAllocateMemory(int process_size) {

    struct MemoryBlock* current_block = memory_head;

    struct MemoryBlock* best_fit_block = NULL;

    while (current_block) {

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

            if (best_fit_block == NULL || current_block->size < best_fit_block->size) {

                best_fit_block = current_block;

            }

        }

        current_block = current_block->next_block;

    }

    if (best_fit_block) {

        // Allocate memory in the best-fit block

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

        best_fit_block->procsize=process_size;

        return 1;  // Allocation successful

    } else {

        // No suitable block found

        return 0;  // Allocation unsuccessful

    }

}

int main() {

    // Initialize memory blocks and printMemoryStatus

    createMemoryBlock(100);

    createMemoryBlock(50);

    createMemoryBlock(200);

    createMemoryBlock(80);

   createMemoryBlock(120);

    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 (bestFitAllocateMemory(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);

   

    // Print memory status

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

    printMemoryStatus(memory_head);

    return 0;

}