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:

BlockSizeStatus
1100Free
250Allocated
3200Free
480Allocated
5120Free

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;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more