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?

Comments

Edit: nvm

---

First fit 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.

Answer 4

JOB 6 WILL NOT BE SCHEDULED BY BEST FIT ALGORITHM AND THERE WILL BE EXTERNAL FRAGMENTATION . 

HERE FIRST FIT PERFORMS BETTER THAN BEST FIT ALGORITHM BECAUSE IT SCHEDULES ALL THE JOBS AND THERE IS NO WASTAGE SPACE ALL THE SPACE OF 1000K UTILIZED PROPERLY. 

Answer 5

 

A. Memory Allocation Tables

 

First Fit Algorithm

Always allocates the first hole that is big enough.

 

Event	Action	Memory Layout (1000k Total)
Initial	Start	[Hole: 1000k]
Job 1 (200k)	Allocate	[Job 1: 200k] [Hole: 800k]
Job 2 (350k)	Allocate	[Job 1: 200k] [Job 2: 350k] [Hole: 450k]
Job 3 (300k)	Allocate	[Job 1: 200k] [Job 2: 350k] [Job 3: 300k] [Hole: 150k]
Job 1 finishes	Free 200k	[Hole: 200k] [Job 2: 350k] [Job 3: 300k] [Hole: 150k]
Job 4 (120k)	Allocate	[Job 4: 120k] [Hole: 80k] [Job 2: 350k] [Job 3: 300k] [Hole: 150k]
Job 5 (150k)	Allocate	[Job 4: 120k] [Hole: 80k] [Job 2: 350k] [Job 3: 300k] [Job 5: 150k]
Job 6 (80k)	Allocate	[Job 4: 120k] [Job 6: 80k] [Job 2: 350k] [Job 3: 300k] [Job 5: 150k]

 

 

---

 

Best Fit Algorithm

Allocates the smallest hole that is big enough.

 

Event	Action	Memory Layout (1000k Total)
Initial	Start	[Hole: 1000k]
Job 1 (200k)	Allocate	[Job 1: 200k] [Hole: 800k]
Job 2 (350k)	Allocate	[Job 1: 200k] [Job 2: 350k] [Hole: 450k]
Job 3 (300k)	Allocate	[Job 1: 200k] [Job 2: 350k] [Job 3: 300k] [Hole: 150k]
Job 1 finishes	Free 200k	[Hole: 200k] [Job 2: 350k] [Job 3: 300k] [Hole: 150k]
Job 4 (120k)	Allocate	[Hole: 200k] [Job 2: 350k] [Job 3: 300k] [Job 4: 120k] [Hole: 30k]
Job 5 (150k)	Allocate	[Job 5: 150k] [Hole: 50k] [Job 2: 350k] [Job 3: 300k] [Job 4: 120k] [Hole: 30k]
Job 6 (80k)	Wait	Cannot fit. Largest holes are 50k and 30k.

 

 

---

 

B. Conclusion

First Fit performs better for this sequence.

• First Fit: Successfully allocated all 6 jobs. By placing Job 4 in the first available 200k slot, it left a 150k slot at the end which was perfectly sized for Job 5.
• Best Fit: Failed to allocate Job 6. It "optimally" placed Job 4 in the 150k slot (leaving 30k) and Job 5 in the 200k slot (leaving 50k). This fragmented the memory such that the 80k required for Job 6 was not available in a single contiguous block.