GATE CSE 1995 | Question: 5

Question

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

• A. Draw the memory allocation table using Best Fit and First Fit algorithms.

• B. Which algorithm performs better for this sequence?

Answer 1

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.

Comments

There is external fragmentation problem if we use Best fit here. Because of which 80k request is denied ...

---

nice eplanation @ sonam vyas

---

we dont perform compacting for external fragmentation as it takes a lot of overhead to move processes from one memory location to another.

Answer 2

First fit, in best fit 80K will not be served

Answer 3

Yes in this case First Fit algorithm will willperform better than Best Fit as in case of BEST FIT last job is not allocated due to non- availability of Contiguous memory.