Wednesday 28 November 2012

Best fit memory management algorithm


//BEST FIT MEMORY MANAGEMENT ALGORITHM IMPLEMENTATION
#include<stdio.h>
#include<conio.h>
#define max 25

void main()
{
 int frag[max],b[max],f[max],i,j,nb,nf,temp,lowest=10000;
 static int bf[max],ff[max];
 clrscr();

 printf("\n\tMemory Management Scheme - Best Fit");
 printf("\nEnter the number of blocks:");
 scanf("%d",&nb);
 printf("Enter the number of files:");
 scanf("%d",&nf);
 printf("\nEnter the size of the blocks:-\n");
 for(i=1;i<=nb;i++) {printf("Block %d:",i);scanf("%d",&b[i]);}
 printf("Enter the size of the files :-\n");
 for(i=1;i<=nf;i++) {printf("File %d:",i);scanf("%d",&f[i]);}

 for(i=1;i<=nf;i++)
 {
  for(j=1;j<=nb;j++)
  {
   if(bf[j]!=1)
   {
    temp=b[j]-f[i];
    if(temp>=0)
    if(lowest>temp)
    {
     ff[i]=j;
     lowest=temp;
    }
   }
  }
  frag[i]=lowest;
  bf[ff[i]]=1;
  lowest=10000;
 }
 printf("\nFile_no:\tFile_size :\tBlock_no:\tBlock_size:\tFragement");
 for(i=1;i<=nf && ff[i]!=0;i++) //line edited on 23/09/2013
 printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d",i,f[i],ff[i],b[ff[i]],frag[i]);
 getch();
}
//program written by Mars. 27/11/2011. OS lab.


24 comments:

  1. plz explain this pgm

    ReplyDelete
    Replies
    1. May following explaination helps you-
      step1: include header files
      step2: start main() function
      step3: take details from user-
      ->Number of memory blocks & sizes of them
      ->Number of files require to store & sizes of them
      step4: determine best blocks for files as-
      1) for each file
      for(i=1;i<=nf;i++)
      2) to each block
      for(j=1;j<=nb;j++)
      3) check if block is empty
      if(bf[j]!=1)
      4) determine difference file vs block size
      temp=b[j]-f[i];
      5) if block size is big then file size
      if(temp>=0)
      6) find lowest temp
      [find best suitable file for a block]
      [for example file size 5or4 more suitable to block size 5]

      if(lowest>temp)
      {
      ff[i]=j;
      lowest=temp;
      }

      7) assign file to suitable block
      frag[i]=lowest;
      bf[ff[i]]=1;

      8) again set to lowest=10000;
      for other files

      Delete
  2. What does ff and bf stand for?

    ReplyDelete
    Replies
    1. In this program 5 array used-
      there max value is 10.
      b[max]: for store size of blocks
      f[max]: for store size of files
      frag[max]: for store difference b/w capacity of block and occupied space by a file

      bf[max]: to store status of the block(i.e 1 or 0) if 1: allocated 0: unallocated
      ff[max]: to store index no. of block that used by particular file

      example:
      lets file1 of size 2 is occupied by block2 of size 3
      then values of arrays
      bf[2] contains value 1 (occupied)
      ff[1] contains index of block that is 2
      frag[1] contains block2's size - file1's size = 1

      Delete
  3. hi mangilal, how can one delete a file or process in this program

    ReplyDelete
    Replies
    1. Hello Anonymous,
      So sorry for such a late reply.

      yes you can do it easily-
      1) if u want to delete file or process-
      -> Require to remove file or process from array; for this do shifting of array elements to overlap element that we going to delete
      -> After deletion again apply algorithm on arrays; for this make a function and put algorithm code from main() to that function and call.
      -> It is must be notable that again algorithm call required; without it Best fit rules are violated there.

      That's it.. very easy.
      Some times later I will try to post this program with this modification (about 1 months later).

      Delete
  4. what if we add a parameter of arrival time for the process ?

    ReplyDelete
    Replies
    1. Hello shabbir,
      So sorry for such a late reply.

      If you want to add arrival time with parameter, you can do follows-

      ->First, sort process array according arrival time of them.
      ->Then, apply algorithm.

      That's all... very easy.
      Some times later I will try to post this program with this modification (about 1 months later).

      Delete
  5. thanx for the reply about deleting a process, will be waiting for the program.
    by the way wat does lowest=1000 stand for in this program?

    ReplyDelete
    Replies
    1. this is variable to store lowest value.
      in starting it initiated with a high value so that we able to compare it with available values.

      see example:
      if an array is 2, 3, 5, 7, 19
      and required to find out a lowest value than-
      we can start a variable lowest=30
      so we able to do like following-
      if lowest>array[1] then lowest=array[1]
      and after compression in last lowest=2 become.

      Delete
  6. this is "an" try.....??correct that.
    AND the output is not the best fit for the given input.
    memory should be allocated in first block for both the files.

    ReplyDelete
    Replies
    1. Thanks for your comment. I have corrected this.

      As you told about best fit output, I have once again checked it and found that-
      Output is correct because:
      File no.1 (size:1) is 1st search most suitable block from (5,2,7) and got 2 sized block that make much small fragment.
      File no.2 (size:4) is search for most suitable block from (5,1,7) and got 5 sized block.

      Delete
    2. But if you consider my answer, no fragment is created.Could you suggest me an algorithm for such thing.HOPE you understood my query.

      Delete
    3. Actually there mainly 3 algorithms for memory management best, worst and first fit. None of them give output as-
      "For both the files (size 1 & size 4) allocation is block1(size 5)".

      Because-
      Here these algorithms suppose First come first serve scheme. For above example, 1st require to allocate block for file1 (size 1) after this we can search for file2. Its not possible to make allocation first for file2 and after file1 due to FCFS scheme.

      We can modify these algorithms as our ideas. So, if we modify this best fit algorithm, possible to get results as you want-
      "Must be both file allocate to 1st block"

      we modify as-
      ->Suppose arrival time is same
      ->Sort files according size in descending order
      ->and apply best fit algorithm

      example-
      file2 (size 4) > file1 (size 1)

      First,
      File no.2 (size:4) is search for most suitable block from (5,2,7) and got 5 sized block.

      After,
      File no.1 (size:1) is search most suitable block from (1,2,7) and got 1 sized block that make much small fragment.

      => There is no fragmentation... I think this helps you?

      Delete
    4. This comment has been removed by the author.

      Delete
  7. memory block- 4 5 5 4 5
    file size- 1 1 2 2 2 2 4 4 4 4
    according to your approach you start allocating memory from right to left.
    the output will be:-
    memory file left
    4 4 0
    4 4 0
    5 4 1
    5 4 1
    5 2 3
    ...................the answer by your method is (2,2) file sizes will be left and memory left is (1).total 8 files are allocated memory.
    but my answer should be:-
    Allocate two pairs of(2+2+1) file sizes to two (5) memory blocks,two (4) file sizes to two (4) memory blocks,allocate one last (4) file size to (5) memory block.
    In this way 1 memory fragment is created but i am able to allocate 9 files instead of 8 files in your answer.
    So i want maximum no. of files that can be stored in the given memory to be my answer.

    ReplyDelete
    Replies
    1. Nitin, solution that you want, is excellent.
      But none of the memory management scheme with any possible modification, able to allocate more than 8 files (for your example)

      But, I have got solution (It is not any currently existing memory management scheme). It's disadvantage is much time complexity and complex in implement.

      solution is-
      -> sort memory blocks in descending order
      5 5 5 4 4

      -> Now, allocate files according memory blocks-
      1) if (equivalent sized file exist in files)
      Allocate file to block.
      else
      find files those size when added they make equivalent or less than the block size. Allocate that files to block

      lets traverse this-
      block sorted: 5 5 5 4 4 4
      files: 1 1 2 2 2 4 4 4 4
      take block 5
      search for equivalent => not find
      go to else
      search for equivalent or less when adding sizes of files=>
      (I still try to think how this search implement)
      1+2+2 made 5 so allocate 1,2,2 for 5

      take block 5
      do for this

      ...continues

      NOTE: Still we require to think that how we implement intelligency for select files that makes equivalent or less (for a perticaular block).

      Delete
  8. this prgrm is not working for input
    no of blocks 3
    no of files 3
    block 1- 5
    block 2- 11
    block3- 12

    file1 - 10
    file2 - 9
    file3- 8

    please check it

    ReplyDelete
    Replies
    1. Thank you for commenting here. I have updated by correcting it.
      Change in program:
      at 5th line from bottom-
      for(i=1;i<=nf;i++) CHANGED TO for(i=1;i<=nf && ff[i]!=0;i++)

      Delete
  9. hi. how do we implement fcfs inside best fit? i did make my code but the one i make is no job is allowed to enter inside the memory list until the previous job is done

    ReplyDelete
    Replies
    1. The default best fit algorithm implementation that I had written above, is implementing "FCFS" inside "Best Fit" because here we assigning best fit block to files in FCFS manner.

      Delete
    2. oh. i made my program based on your code and i would like to add few variable. for now, based on my code, first job enter first mem block and have cpu cycle = 4. during job 1 is processed, job 2 should arrive since arrival time for job 2 = 2. My goal for now is to be able to make the job 2 enter memBlock 2 without waiting for job 1 to done. because i believe the waitingTime for job 2 will be different this way. (based on my program, waiting time for job 2 will be 2 since it wait 2 unit time until job 1 done processing). maybe you can give me hint on how to implment this to my program. thanks for the reply

      Delete
    3. i posted my problem on a forum. maybe you want to check it out to see the clear view of my problem
      i don't know if it is appropriate but here's the link
      http://www.dreamincode.net/forums/topic/399138-fcfs-in-bestfit/page__gopid__2292911&#entry2292911

      Delete
  10. Hi how to have an output for status if it is busy or free. busy if the block have been used by the file then if the block is not occupied it should display a free

    ReplyDelete

You are welcome, your comment helps me to make this blog more better.