Memory Allocation Scheme- First Fit , Worse Fit, Best Fit

Let’s delve into the memory allocation methods for fixed partitions: First Fit, Worst Fit, and Best Fit.

First Fit Allocation:
In this technique, the operating system searches through the list of free memory blocks, starting from the beginning, until it finds a block large enough to accommodate the memory request from a process.

Once a suitable block is found, it is split into two parts: the portion allocated to the process and the remaining free block.
Advantages:
Simple and efficient search algorithm.
Minimizes memory fragmentation.
Fast allocation of memory.
Disadvantages:
Poor performance in highly fragmented memory.
May allocate larger blocks than needed, leading to inefficient memory utilization.

Example: Consider allocating processes with sizes 212K, 417K, 112K, and 426K to memory blocks of sizes 100K, 500K, 200K, 300K, and 600K respectively:

Process 1: Allocated to Block 2 (size 212K).
Process 2: Allocated to Block 5 (size 417K).
Process 3: Allocated to Block 2 (size 112K).
Process 4: Not Allocated
Process No.     Process Size    Block no.
 1                      212                 2
 2                      417                 5
 3                      112                 2
 4                      426                 Not Allocated
Free Blocks
100->176->200->300->183->
//*********************************************************************
// C Program First Fit Implementation
//*********************************************************************
#include <stdio.h>
#include <string.h>

void firstFit(int blockSize[], int m, int processSize[], int n) {
    int allocation[n];
    memset(allocation, -1, sizeof(allocation));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (blockSize[j] >= processSize[i]) {
                allocation[i] = j;
                blockSize[j] -= processSize[i];
                break;
            }
        }
    }

    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < n; i++) {
        printf(" %d\t\t%d\t\t", i + 1, processSize[i]);
        if (allocation[i] != -1)
            printf("%d", allocation[i] + 1);
        else
            printf("Not Allocated");
        printf("\n");
    }

    printf("Free Blocks\n");
    for (int i = 0; i < m; i++) printf("%d->",blockSize[i]);
}

int main() {
    int blockSize[] = {100, 500, 200, 300, 600};
    int processSize[] = {212, 417, 112, 426};
    int m = sizeof(blockSize) / sizeof(blockSize[0]);
    int n = sizeof(processSize) / sizeof(processSize[0]);
    firstFit(blockSize, m, processSize, n);
    return 0;
}

Worst Fit Allocation:
In this method, the process traverses the entire memory and always searches for the largest available hole/partition.
The process is then placed in that hole/partition.
Advantages:
Large internal fragmentation allows other small processes to utilize leftover space.
Disadvantages:
Slow process due to traversing all partitions.
Significant internal fragmentation.

Note:If a large process claims the largest available partition, it can leave substantial unused space.

Example: Consider allocating processes with sizes 212K, 417K, 112K, and 426K to memory blocks of sizes 100K, 500K, 200K, 300K, and 600K respectively:

Process 1: Allocated to Block 5 (size 212K).
Process 2: Allocated to Block 2 (size 417K).
Process 3: Allocated to Block 5 (size 112K).
Process 4: Not Allocated
Process No.     Process Size    Block no.
 1                          212             5
 2                          417             2
 3                          112             5
 4                          426             Not Allocated
Free Blocks
100->83->200->300->276->

//*********************************************************************
// C Program Worst Fit Implementation
//*********************************************************************
#include <stdio.h>
#include <string.h>

void worstFit(int blockSize[], int m, int processSize[], int n) {
    int allocation[n];
    memset(allocation, -1, sizeof(allocation));

    for (int i = 0; i < n; i++) {
        int wstIdx = -1;
        for (int j = 0; j < m; j++) {
            if (blockSize[j] >= processSize[i]) {
                if (wstIdx == -1 || blockSize[wstIdx] < blockSize[j])
                    wstIdx = j;
            }
        }
        if (wstIdx != -1) {
            allocation[i] = wstIdx;
            blockSize[wstIdx] -= processSize[i];
        }
    }

    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < n; i++) {
        printf(" %d\t\t%d\t\t", i + 1, processSize[i]);
        if (allocation[i] != -1)
            printf("%d", allocation[i] + 1);
        else
            printf("Not Allocated");
        printf("\n");
    }
    printf("Free Blocks\n");
    for (int i = 0; i < m; i++) printf("%d->",blockSize[i]);
}

int main() {
    int blockSize[] = {100, 500, 200, 300, 600};
    int processSize[] = {212, 417, 112, 426};
    int m = sizeof(blockSize) / sizeof(blockSize[0]);
    int n = sizeof(processSize) / sizeof(processSize[0]);
    worstFit(blockSize, m, processSize, n);
    return 0;
}
   
Best Fit Allocation:
In Best Fit, the operating system searches for the block closest in size to the memory request from the process.
It allocates the process to the smallest sufficient partition among the free available partitions.
Advantages:
Minimizes wastage of memory space.
Suitable for scenarios where memory requirements vary significantly.
Disadvantages:
Time-consuming due to searching for the closest-sized block.

Example: Consider allocating processes with sizes 212K, 417K, 112K, and 426K to memory blocks of sizes 100K, 500K, 200K, 300K, and 600K respectively:

Process 1: Allocated to Block 4 (size 212K).
Process 2: Allocated to Block 2 (size 417K).
Process 3: Allocated to Block 3 (size 112K).
Process 4: Allocated to Block 5 (size 426K).

Process No.     Process Size    Block no.
 1                      212                     4
 2                      417                     2
 3                      112                     3
 4                      426                     5
Free Blocks
100->83->88->88->174->

//*********************************************************************
// C Program Best  Fit Implementation
//*********************************************************************
#include <stdio.h>
#include <string.h>

void bestFit(int blockSize[], int m, int processSize[], int n) {
    int allocation[n];
    for (int i = 0; i < n; i++)
        allocation[i] = -1;

    for (int i = 0; i < n; i++) {
        int bestIdx = -1;
        for (int j = 0; j < m; j++) {
            if (blockSize[j] >= processSize[i]) {
                if (bestIdx == -1)
                    bestIdx = j;
                else if (blockSize[bestIdx] > blockSize[j])
                    bestIdx = j;
            }
        }
        if (bestIdx != -1) {
            allocation[i] = bestIdx;
            blockSize[bestIdx] -= processSize[i];
        }
    }

    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < n; i++) {
        printf(" %d\t\t%d\t\t", i + 1, processSize[i]);
        if (allocation[i] != -1)
            printf("%d", allocation[i] + 1);
        else
            printf("Not Allocated");
        printf("\n");
    }
    printf("Free Blocks\n");
    for (int i = 0; i < m; i++) printf("%d->",blockSize[i]);
}
int main() {
    int blockSize[] = {100, 500, 200, 300, 600};
    int processSize[] = {212, 417, 112, 426};
    int m = sizeof(blockSize) / sizeof(blockSize[0]);
    int n = sizeof(processSize) / sizeof(processSize[0]);
    bestFit(blockSize, m, processSize, n);
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn. Shell Programming 1. Shell Script 2. Arithmetic Expressions 3. Special Shell Variables 4. Shell Script for getting important info 5. if and case statement 6. looping statements while,until,for 7. Menu driven Programs 8. GUI Menus 9. Functions in scripts 10. String Handling 11. Command line arguments in scripts
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh
Read more

Shared Memory Inter-Process Communication ( IPC)

Shared memory Inter-Process Communication (IPC) in Linux allows processes to communicate by sharing a region of memory. This method is efficient because it avoids the overhead of copying data between processes. Here's how shared memory IPC is typically done in Linux: Create a Shared Memory Segment: To use shared memory IPC, you need to create a shared memory segment. This is done using the shmget() system call, which allocates a new shared memory segment or obtains the identifier of an existing one. You specify the size of the shared memory segment and some permissions. Attach the Shared Memory Segment: Once you have obtained the identifier for the shared memory segment, you need to attach it to the address space of your process. This is done using the shmat() system call. This call returns the address of the shared memory segment in your process's address space. Accessing the Shared Memory: After attaching the shared memory segment to your process's address space, you c
Read more