First Fit Program in C-Algorithm and Explanation

 

What is First Fit?

The First Fit memory allocation checks the empty memory blocks in a sequential manner. It means that the memory Block which found empty in the first attempt is checked for size.

But if the size is not less than the required size then it is allocated.

Advantage:

It is the fastest searching Algorithm as we not to search only first block, we do not need to search a lot.

Disadvantage:

The main disadvantage of First Fit is that the extra space cannot be used by any other processes.If the memory is allocated it creates large amount of chunks of memory space.

First Fit Memory Management Scheme:

In the First Fit Memory Management Scheme, we check the block in the sequential manner i.e we take the first process and compare its size with the first block.

If the size is less than the size of the first block then only it is allocated. Otherwise, we move to the second block and this process is continuously going on until all processes are allocated.

Algorithm of First Fit:

1 Step: START.

2 Step: At first get the no of processes and blocks.

3 Step: Allocate the process by if(size of block>=size of the process) then allocate the process else move to the next block.

4 Step: Now Display the processes with blocks and allocate to respective process.

5 Step: STOP.

We have discussed the working and the Algorithm. Now, we will see the program for First Fit in C.

1. First Fit Program in C

C

1

#include<stdio.h>

2

void main()

3

{

4

    int bsize[10], psize[10], bno, pno, flags[10], allocation[10], i, j;

5

    for(i = 0; i < 10; i++)

6

    {

7

        flags[i] = 0;

8

        allocation[i] = -1;

9

    }

10

    printf("Enter no. of blocks: ");

11

    scanf("%d", &bno);

12

    printf("\nEnter size of each block: ");

13

    for(i = 0; i < bno; i++)

14

        scanf("%d", &bsize[i]);

15

    printf("\nEnter no. of processes: ");

16

    scanf("%d", &pno);

17

    printf("\nEnter size of each process: ");

18

    for(i = 0; i < pno; i++)

19

        scanf("%d", &psize[i]);

20

    for(i = 0; i < pno; i++)         //allocation as per first fit

21

        for(j = 0; j < bno; j++)

22

            if(flags[j] == 0 && bsize[j] >= psize[i])

23

            {

24

                allocation[j] = i;

25

                flags[j] = 1;

26

                break;

27

            }

28

    //display allocation details

29

    printf("\nBlock no.\tsize\t\tprocess no.\t\tsize");

30

    for(i = 0; i < bno; i++)

31

    {

32

        printf("\n%d\t\t%d\t\t", i+1, bsize[i]);

33

        if(flags[i] == 1)

34

            printf("%d\t\t\t%d",allocation[i]+1,psize[allocation[i]]);

35

        else

36

            printf("Not allocated");

37

    }

38

}

Output:

2. First Fit Program in C++

C++

1

#include<iostream>

2

using namespace std;

3

int main()

4

{

5

    int bsize[10], psize[10], bno, pno, flags[10], allocation[10], i, j;

6

    for(i = 0; i < 10; i++)

7

    {

8

        flags[i] = 0;

9

        allocation[i] = -1;

10

    }

11

    cout<<"Enter no. of blocks: ";

12

    cin>>bno;

13

    cout<<"\nEnter size of each block: ";

14

    for(i = 0; i < bno; i++)

15

        cin>>bsize[i];

16

    cout<<"\nEnter no. of processes: ";

17

    cin>>pno;

18

    cout<<"\nEnter size of each process: ";

19

    for(i = 0; i < pno; i++)

20

        cin>>psize[i];

21

    for(i = 0; i < pno; i++)         //allocation as per first fit

22

        for(j = 0; j < bno; j++)

23

            if(flags[j] == 0 && bsize[j] >= psize[i])

24

            {

25

                allocation[j] = i;

26

                flags[j] = 1;

27

                break;

28

            }

29

    //display allocation details

30

    cout<<"\nBlock no.\tsize\t\tprocess no.\t\tsize";

31

    for(i = 0; i < bno; i++)

32

    {

33

        cout<<"\n"<< i+1<<"\t\t"<<bsize[i]<<"\t\t";

34

        if(flags[i] == 1)

35

            cout<<allocation[i]+1<<"\t\t\t"<<psize[allocation[i]];

36

        else

37

            cout<<"Not allocated";

38

    }

39

    return 0;

40

}

Output: