The Gateway to Computer Science Excellence
+19 votes

A computer installation has 1000k of main memory. The jobs arrive and finish in the following sequences.

    Job 1 requiring 200k arrives
    Job 2 requiring 350k arrives
    Job 3 requiring 300k arrives
    Job 1 finishes
    Job 4 requiring 120k arrives
    Job 5 requiring 150k arrives
    Job 6 requiring 80k arrives
  1. Draw the memory allocation table using Best Fit and First Fit algorithms

  2. Which algorithm performs better for this sequence?

in Operating System by Veteran (52.2k points)
edited by | 2.2k views

2 Answers

+24 votes
Best answer

Initial there is $1000k$ main memory available.

Then job $1$ arrive and occupied $200k$, then job $2$ arrive, occupy $350k$, after that job $3$ arrive and occupy $300k$ (assume continuous allocation ) now free memory is $1000-850(200+350+300)= 150k$ (till these jobs first fit and best fit are same)

Now, job $1$ is finished. So, that space is also free. So, here $200k$ slot and $150k$ slots are free.

Now, job $4$ arrives which is $120k$.

Case 1:

  • First fit, so it will be in $200$ k slot (free slot ) and now free is $= 200-120=80k$,
  • Now $150k$ arrive which will be in $150$ $k$ slot
  • Then, $80k$ arrive which will occupy in $80k$ slot $(200-120)$ so, all jobs will be allocated  successfully.

Case 2:

  • Best fit : $120 k$ job will occupy best fit free space which is $150k$ so, now remaining $150-120=30k$,
  • Then $150k$ job arrive it will be occupied in $200k$ slot, which is best fit for this job. So, free space $=200-150= 50$,
  • Now, job $80k$ arrive, but there is no continuous $80k$ memory free. So, it will not be allocated successfully.

So, first fit is better.

by Boss (17.1k points)
edited by
There is external fragmentation problem if we use Best fit here. Because of which 80k request is denied ...
nice eplanation @ sonam vyas
+8 votes
First fit, in best fit 80K will not be served
by Junior (883 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,151 users