Write a program to implement dynamic partitioning placement algorithms i.e Best Fit, First – Fit and Worst –Fit.

Answer: In dynamic partitioning, a process is placed in a free hole that is large enough: First Fit takes the first such hole, Best Fit the smallest such hole, Worst Fit the largest hole. The unused part of the hole stays free as a smaller hole.

Logic

• Copy the block sizes into hole[] for each method.
• For every process, scan all holes with hole ≥ process size: First Fit stops at the first, Best Fit keeps the minimum, Worst Fit keeps the maximum.
• If found, hole = hole − process size; otherwise the process waits.

Program (C)

#include <stdio.h>

#define MAX 20

int nb, np, blockSize[MAX], procSize[MAX];

/* type: 1 = First Fit, 2 = Best Fit, 3 = Worst Fit */
void allocate(int type, char *name)
{
    int hole[MAX], alloc[MAX], left[MAX], i, j, pos;

    for (j = 0; j < nb; j++)
        hole[j] = blockSize[j];          /* free space left in each block */

    for (i = 0; i < np; i++) {
        pos = -1;
        for (j = 0; j < nb; j++) {
            if (hole[j] < procSize[i])
                continue;                 /* does not fit */
            if (type == 1) {              /* first hole that fits */
                pos = j;
                break;
            }
            if (pos == -1 ||
                (type == 2 && hole[j] < hole[pos]) ||   /* smallest hole */
                (type == 3 && hole[j] > hole[pos]))     /* largest hole */
                pos = j;
        }
        alloc[i] = pos;
        if (pos != -1) {
            hole[pos] -= procSize[i];     /* leftover stays as a smaller hole */
            left[i] = hole[pos];
        }
    }

    printf("\n%s\nProcess  Size  Block  Hole left\n", name);
    for (i = 0; i < np; i++) {
        if (alloc[i] != -1)
            printf("P%-7d %-5d B%-5d %d\n", i + 1, procSize[i], alloc[i] + 1, left[i]);
        else
            printf("P%-7d %-5d Not allocated (must wait)\n", i + 1, procSize[i]);
    }
}

int main()
{
    int i;

    printf("Enter number of memory blocks: ");
    scanf("%d", &nb);
    printf("Enter size of each block: ");
    for (i = 0; i < nb; i++)
        scanf("%d", &blockSize[i]);
    printf("Enter number of processes: ");
    scanf("%d", &np);
    printf("Enter size of each process: ");
    for (i = 0; i < np; i++)
        scanf("%d", &procSize[i]);

    allocate(1, "FIRST FIT");
    allocate(2, "BEST FIT");
    allocate(3, "WORST FIT");
    return 0;
}

Sample run (gcc)

Enter number of memory blocks: 5
Enter size of each block: 100 500 200 300 600
Enter number of processes: 4
Enter size of each process: 212 417 112 426

FIRST FIT
Process  Size  Block  Hole left
P1       212   B2     288
P2       417   B5     183
P3       112   B2     176
P4       426   Not allocated (must wait)

BEST FIT
Process  Size  Block  Hole left
P1       212   B4     88
P2       417   B2     83
P3       112   B3     88
P4       426   B5     174

WORST FIT
Process  Size  Block  Hole left
P1       212   B5     388
P2       417   B2     83
P3       112   B5     276
P4       426   Not allocated (must wait)

Here Best Fit places all four processes, while First Fit and Worst Fit leave the 426 KB process waiting because the large holes were already broken up.