Next Fit Algorithm in Operating System Program In C++

July 6, 2023

Next fit algorithm in C++

Introduction to Next Fit Algorithm In Operating System

The Next Fit algorithm program In C++ is a memory allocation technique used in operating systems. It is specifically designed for managing memory blocks in scenarios where the size of memory requested by a process can be variable. The Next Fit algorithm allocates memory blocks in a sequential manner, starting from the last allocated block.

In this article, we will explore the Next Fit algorithm, a popular memory allocation technique used in operating system programs, specifically focusing on its implementation in the C++ programming language.

Overview of Next Fit Algorithm

The Next Fit algorithm is a memory allocation technique that sequentially searches for the next available block of memory when allocating memory to a process. It starts the search from the last allocated block and continues until it finds a suitable block or reaches the end of the memory space. This algorithm reduces external fragmentation by placing newly allocated blocks after the last allocated block.

The Next Fit algorithm offers several advantages:

  1. Simplicity: The Next Fit algorithm is relatively easy to implement compared to other memory allocation algorithms.

  2. Efficient Memory Utilization: The algorithm maximizes memory utilization by placing newly allocated blocks after the last allocated block. This reduces external fragmentation.

  3. Quick Allocation: Next Fit performs a sequential search, which makes the allocation process faster than some other algorithms.

Despite its advantages, the Next Fit algorithm has a few limitations:

  1. Internal Fragmentation: The Next Fit algorithm can lead to internal fragmentation, where allocated memory blocks may be larger than what is required by the processes. This can result in wasted memory.

  2. Inefficient Searching: If the last allocated block is far from the end of the memory space, the Next Fit algorithm may require a longer search time, resulting in slower performance.

  3. Suboptimal Space Utilization: The Next Fit algorithm may not always find the best available block of memory. It may allocate memory in a suboptimal manner, leading to less efficient space utilization.

The Next Fit algorithm finds applications in various areas, including:

  1. Dynamic memory allocation: Next Fit is commonly used for dynamic memory allocation in operating systems.
  2. Disk scheduling: Next Fit can be applied to disk scheduling algorithms to allocate disk space efficiently.
  3. Network routing: Next Fit can be utilized for routing data packets in network systems.

Implementation of Next Fit Algorithm in C++

Step 1: Initialize Variables and Data Structures

To implement the Next Fit algorithm in C++, we need to define the necessary variables and data structures. We initialize a pointer to keep track of the last allocated block and maintain a list of available memory blocks.

#include 
#include 

struct MemoryBlock {
    int start;
    int end;
    bool allocated;
};

std::vector memory;

int lastAllocatedIndex = -1;

Step 2: Allocate Memory using Next Fit Algorithm

Next, we define a function to allocate memory to a process using the Next Fit algorithm. This function takes the size of the process as input and searches for the next available memory block starting from the last allocated block.

int allocateMemory(int size) {
    for (int i = lastAllocatedIndex + 1; i < memory.size(); i++) {
        if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    // If no suitable block is found, start the search from the beginning
    for (int i = 0; i <= lastAllocatedIndex; i++) {
        if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    return -1; // Memory allocation failed
}

Step 3: Deallocate Memory

Finally, we implement a function to deallocate memory when a process completes. This function takes the starting address of the process as input and marks the corresponding memory block as unallocated.

void deallocateMemory(int start) {
    for (int i = 0; i < memory.size(); i++) {
        if (memory[i].start == start) {
            memory[i].allocated = false;
            break;
        }
    }
}

Memory Management Introduction

Paging

Difference between Segmentation and Paging

Process Address Space

Run 
#include <iostream>
#include <vector>

struct MemoryBlock {
    int start;
    int end;
    bool allocated;
};

std::vector memory;
int lastAllocatedIndex = -1;

// Function to allocate memory using Next Fit algorithm
int allocateMemory(int size) {
    for (int i = lastAllocatedIndex + 1; i < memory.size(); i++) { if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    // If no suitable block is found, start the search from the beginning
    for (int i = 0; i <= lastAllocatedIndex; i++) { if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    return -1; // Memory allocation failed
}

// Function to deallocate memory
void deallocateMemory(int start) {
    for (int i = 0; i < memory.size(); i++) {
        if (memory[i].start == start) {
            memory[i].allocated = false;
            break;
        }
    }
}

int main() {
    // Initialize memory blocks
    memory = {
        {0, 99, false},
        {100, 199, false},
        {200, 299, false},
        {300, 399, false}
    };

    // Allocate memory for processes
    int process1 = allocateMemory(50);
    int process2 = allocateMemory(75);
    int process3 = allocateMemory(100);

    if (process1 != -1 && process2 != -1 && process3 != -1) {
        std::cout << "Memory allocation successful!\n";
        std::cout << "Process 1 allocated at address: " << process1 << std::endl;
        std::cout << "Process 2 allocated at address: " << process2 << std::endl;
        std::cout << "Process 3 allocated at address: " << process3 << std::endl;

        // Deallocate memory when processes complete
        deallocateMemory(process2);
        deallocateMemory(process1);
        deallocateMemory(process3);

        std::cout << "Memory deallocation successful!\n";
    } else {
        std::cout << "Memory allocation failed!\n";
    }

    return 0;
}

Output:
Memory allocation failed!
  • The allocateMemory function implements the Next Fit algorithm. It searches for the next available memory block, starting from the last allocated block. If a suitable block is found, it marks it as allocated and updates lastAllocatedIndex. If no suitable block is found, it restarts the search from the beginning.
  • The function returns the starting address of the allocated block or -1 if the allocation fails.
  • The deallocateMemory function deallocates memory by marking the corresponding memory block as unallocated.
  • In the main function, we initialize the memory blocks and demonstrate the allocation and deallocation of memory for processes.
  • The program prints messages to indicate the success or failure of memory allocation and deallocation.
Run 
#include <iostream>
#include <vector>

struct MemoryBlock {
    int start;
    int end;
    bool allocated;
};

std::vector memory;
int lastAllocatedIndex = -1;

// Function to allocate memory using Next Fit algorithm
int allocateMemory(int size) {
    for (int i = lastAllocatedIndex + 1; i < memory.size(); i++) { if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    // If no suitable block is found, start the search from the beginning
    for (int i = 0; i <= lastAllocatedIndex; i++) { if (!memory[i].allocated && memory[i].end - memory[i].start >= size) {
            memory[i].allocated = true;
            lastAllocatedIndex = i;
            return memory[i].start;
        }
    }

    return -1; // Memory allocation failed
}

// Function to deallocate memory
void deallocateMemory(int start) {
    for (int i = 0; i < memory.size(); i++) {
        if (memory[i].start == start) {
            memory[i].allocated = false;
            break;
        }
    }
}

// Function to display the memory blocks and their allocation status
void displayMemory() {
    std::cout << "Memory Layout:\n";
    for (const MemoryBlock& block : memory) {
        std::cout << "[" << block.start << "-" << block.end << "] ";
        if (block.allocated) {
            std::cout << "Allocated\n";
        } else {
            std::cout << "Free\n";
        }
    }
    std::cout << "\n";
}

int main() {
    // Initialize memory blocks
    memory = {
        {0, 99, false},
        {100, 199, false},
        {200, 299, false},
        {300, 399, false}
    };

    // Display initial memory layout
    std::cout << "Initial Memory Layout:\n";
    displayMemory();

    // Allocate memory for processes
    int process1 = allocateMemory(50);
    int process2 = allocateMemory(75);
    int process3 = allocateMemory(100);

    if (process1 != -1 && process2 != -1 && process3 != -1) {
        std::cout << "Memory allocation successful!\n";
        std::cout << "Process 1 allocated at address: " << process1 << std::endl;
        std::cout << "Process 2 allocated at address: " << process2 << std::endl;
        std::cout << "Process 3 allocated at address: " << process3 << std::endl;

        // Display updated memory layout after allocation
        std::cout << "Updated Memory Layout after Allocation:\n";
        displayMemory();

        // Deallocate memory when processes complete
        deallocateMemory(process2);
        deallocateMemory(process1);
        deallocateMemory(process3);

        std::cout << "Memory deallocation successful!\n";

        // Display final memory layout after deallocation
        std::cout << "Final Memory Layout after Deallocation:\n";
        displayMemory();
    } else {
        std::cout << "Memory allocation failed!\n";
    }

    return 0;
}


Output:

Initial Memory Layout:
Memory Layout:
[0-99] Free
[100-199] Free
[200-299] Free
[300-399] Free

Memory allocation failed!
  • The provided code demonstrates the Next Fit algorithm for memory allocation. It defines a MemoryBlock struct to represent memory blocks. The allocateMemory function finds an available block to allocate memory and updates the allocation status.
  • The deallocateMemory function frees up allocated memory. The displayMemory function shows the current memory layout. In the main function, memory is initialized, allocation and deallocation are performed, and the memory layout is displayed.

Conclusion

In conclusion, the Next Fit algorithm provides a simple yet effective approach to memory allocation in operating system programs. Its implementation in C++ involves initializing variables and data structures, allocating memory using a sequential search, and deallocating memory when a process completes. Understanding different memory allocation algorithms is crucial for efficient resource management in operating systems.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
OS dekstop banner

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout