Operating System

Partitioning Algorithm

Partitioning Algorithms

Partitioning algorithms are used to divide the memory into partitions to allocate memory to processes. There are two types of partitioning algorithms:

1. First Fit
2. Best Fit
3. Worst Fit

First Fit

In the first fit algorithm, the memory is divided into partitions and the first partition that is large enough to fit the process is allocated to the process. The process is allocated to the first partition that is large enough to fit the process.

#include <stdio.h>

void firstFit(int bSize[], int bCount, int pSize[], int pCount) {
    int bAlloc[pCount];
    int bOccupied[bCount];

    // Initialize block allocation and occupation arrays
    for (int i = 0; i < pCount; i++) {
        bAlloc[i] = -1;
    }
    for (int i = 0; i < bCount; i++) {
        bOccupied[i] = 0;
    }

    // Allocate processes to blocks
    for (int p = 0; p < pCount; p++) {
        for (int b = 0; b < bCount; b++) {
            if (!bOccupied[b] && bSize[b] >= pSize[p]) {
                bAlloc[p] = b;
                bOccupied[b] = 1;
                break;
            }
        }
    }

    // Print the allocation results
    printf("Process\tSize\tBlock\n");
    for (int p = 0; p < pCount; p++) {
        printf("%d\t%d\t", p + 1, pSize[p]);
        if (bAlloc[p] != -1) {
            printf("%d\n", bAlloc[p] + 1);
        } else {
            printf("Not Allocated\n");
        }
    }
}

int main() {
    int bSize[] = {30, 5, 10};
    int pSize[] = {10, 6, 9};
    int bCount = sizeof(bSize) / sizeof(bSize[0]);
    int pCount = sizeof(pSize) / sizeof(pSize[0]);

    firstFit(bSize, bCount, pSize, pCount);
    return 0;
}

Best Fit

In the best fit algorithm, the memory is divided into partitions and the partition that is closest in size to the process is allocated to the process. The process is allocated to the partition that is closest in size to the process.

#include <stdio.h>

void bestFit(int bSize[], int bCount, int pSize[], int pCount) {
    int bAlloc[pCount];
    int bOccupied[bCount];

    // Initialize block allocation and occupation arrays
    for (int i = 0; i < pCount; i++) {
        bAlloc[i] = -1;
    }
    for (int i = 0; i < bCount; i++) {
        bOccupied[i] = 0;
    }

    // Allocate processes to blocks using Best Fit
    for (int p = 0; p < pCount; p++) {
        int bestBlock = -1;
        for (int b = 0; b < bCount; b++) {
            if (!bOccupied[b] && bSize[b] >= pSize[p]) {
                if (bestBlock == -1 || bSize[b] < bSize[bestBlock]) {
                    bestBlock = b;
                }
            }
        }
        if (bestBlock != -1) {
            bAlloc[p] = bestBlock;
            bOccupied[bestBlock] = 1;
        }
    }

    // Print the allocation results
    printf("Process\tSize\tBlock\n");
    for (int p = 0; p < pCount; p++) {
        printf("%d\t%d\t", p + 1, pSize[p]);
        if (bAlloc[p] != -1) {
            printf("%d\n", bAlloc[p] + 1);
        } else {
            printf("Not Allocated\n");
        }
    }
}

int main() {
    int bSize[] = {30, 5, 10};
    int pSize[] = {10, 6, 9};
    int bCount = sizeof(bSize) / sizeof(bSize[0]);
    int pCount = sizeof(pSize) / sizeof(pSize[0]);

    bestFit(bSize, bCount, pSize, pCount);
    return 0;
}

Worst Fit

In the worst fit algorithm, the memory is divided into partitions and the largest partition that is large enough to fit the process is allocated to the process. The process is allocated to the largest partition that is large enough to fit the process.

#include <stdio.h>

void worstFit(int bSize[], int bCount, int pSize[], int pCount) {
    int bAlloc[pCount];
    int bOccupied[bCount];

    // Initialize block allocation and occupation arrays
    for (int i = 0; i < pCount; i++) {
        bAlloc[i] = -1;
    }
    for (int i = 0; i < bCount; i++) {
        bOccupied[i] = 0;
    }

    // Allocate processes to blocks using Worst Fit
    for (int p = 0; p < pCount; p++) {
        int worstBlock = -1;
        for (int b = 0; b < bCount; b++) {
            if (!bOccupied[b] && bSize[b] >= pSize[p]) {
                if (worstBlock == -1 || bSize[b] > bSize[worstBlock]) {
                    worstBlock = b;
                }
            }
        }
        if (worstBlock != -1) {
            bAlloc[p] = worstBlock;
            bOccupied[worstBlock] = 1;
        }
    }

    // Print the allocation results
    printf("Process\tSize\tBlock\n");
    for (int p = 0; p < pCount; p++) {
        printf("%d\t%d\t", p + 1, pSize[p]);
        if (bAlloc[p] != -1) {
            printf("%d\n", bAlloc[p] + 1);
        } else {
            printf("Not Allocated\n");
        }
    }
}

int main() {
    int bSize[] = {30, 5, 10};
    int pSize[] = {10, 6, 9};
    int bCount = sizeof(bSize) / sizeof(bSize[0]);
    int pCount = sizeof(pSize) / sizeof(pSize[0]);

    worstFit(bSize, bCount, pSize, pCount);
    return 0;
}

To compile and run the program, use the following commands(dont copy the $ sign, it represents the terminal prompt):

$ gcc partition.c -o partition
$ ./partition

This program demonstrates the first fit, best fit, and worst fit partitioning algorithms to allocate memory to processes.

Questions

What is the use of partitioning algorithms?

Partitioning algorithms are used to divide the memory into partitions to allocate memory to processes.

What is the difference between first fit, best fit, and worst fit algorithms?

• First Fit: The first partition that is large enough to fit the process is allocated to the process. - Best Fit: The partition that is closest in size to the process is allocated to the process. - Worst Fit: The largest partition that is large enough to fit the process is allocated to the process.

What is the output of the program?

The program will allocate memory to processes using first fit, best fit, and worst fit algorithms.

What is the use of processes array?

The processes array contains the processes to be allocated memory.