OS Best Fit

Suppose you need to allocate memory space for 1 process. Write a program to list the various memory blocks that can be allocated for this process.
 

Input Format :

Input consists of starting and ending byte addresses until the user ends his/her input.
( Always starting address should be less than or equal to ending address ).

 

Output Format :

The output consists of the free space blocks available for holding the process. Free space list should be in ascending order with respect to starting address and continuous blocks should be merged.

[ Refer Sample Input and Output for further details ]
 

Sample Input and Output 1 :
[All text in bold corresponds to the input and the rest corresponds to output]

Enter the starting and ending addresses of the block ( enter -1 -1 to exit )

15

26

Enter the starting and ending addresses of the block ( enter -1 -1 to exit )

62

78

Enter the starting and ending addresses of the block ( enter -1 -1 to exit )

5

11

Enter the starting and ending addresses of the block ( enter -1 -1 to exit )

32

42

Enter the starting and ending addresses of the block ( enter -1 -1 to exit )

-1

-1

Free space list :

Start End

5 11

15 26

32 42

62 78

Enter the process to be allocated disk space

Enter the process ID

P2

Enter the size of the process

14

Free space available for process P2

Start End Size

62 78 17

 

Sample Input and Output 2 :

Enter the starting and ending addresses of the block  ( enter -1 -1 to exit )

23
26
Enter the starting and ending addresses of the block  ( enter -1 -1 to exit )

56
59
Enter the starting and ending addresses of the block  ( enter -1 -1 to exit )

-1
-1
Free space list :
Start End
23 26
56 59
Enter the process to be allocated disk space
Enter the process ID 

P1
Enter the size of the process

6
Free space available for process P1
Start End Size
Process P1 cannot be allocated disk space

Answer:

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n=100000;
    int count=0;
    int start[n];
    int end[n];
    int diff[n];
    while(1)
    {
        printf("Enter the starting and ending addresses of the block ( enter -1 -1 to exit )\n");
        scanf("%d",&start[count]);
        scanf("%d",&end[count]);
        if(start[count]<=end[count]){
            diff[count]=(end[count]-start[count])+1;
        }
        if(start[count]==-1 && end[count]==-1){
            break;
        }
        count++;
    }
    for(int i=0;i<count;i++)
    {
        for( int j=0;j<count-i-1;j++)
        {
            if(start[j]>start[j+1])
            {
                int temp=start[j];
                start[j]=start[j+1];
                start[j+1]=temp;
                
                temp=end[j];
                end[j]=end[j+1];
                end[j+1]=temp;
                
                temp=diff[j];
                diff[j]=diff[j+1];
                diff[j+1]=temp;
            }
        }
    }
    printf("Free space list :\n");
    printf("Start End\n");
    for(int i=0;i<count;i++)
    {
        printf("%d %d\n",start[i],end[i]);
    }
    char c[3];
    int size=0;
    printf("Enter the process to be allocated disk space\n");
    printf("Enter the process ID\n");
    scanf("%s",c);
    printf("Enter the size of the process\n");
    scanf("%d",&size);
    printf("Free space available for process %s\nStart End Size\n",c);
    int flag=0;
    for(int i=0;i<count;i++){
        if(diff[i]>=size && size!=0){
            printf("%d %d %d\n",start[i],end[i],(diff[i]));
            flag=1;
        }
    }
    if(flag==0)
    {
        printf("Process %s cannot be allocated disk space",c);
    }
    return 0;
}