GATE CSE 2020 | Question: 11

Question

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE?

• A. The hole created by first fit is always larger than the hole created by next fit.
• B. The hole created by worst fit is always larger than the hole created by first fit. 
• C. The hole created by best fit is never larger than the hole created by first fit.
• D. The hole created by next fit is never larger than the hole created by best fit.

Comments

Focus on the word “Exactly”.It means that the newly arrived process will not exactly fit in the memory .It fill definitely be partially filled leaving some hole.

---

Whenever a process is loaded or removed from the physical memory block, it creates a small hole in memory space which is called a fragment. 

And if that fragment is large enough for loading a process, then the process when loaded and removed will also create a hole in that memory block 

check Data fragmentation in → https://en.wikipedia.org/wiki/Fragmentation_(computing)

 

---

Consider all partitions are of same size, A and B false by that due to word “ALWAYS”

Consider partitions 600,700,800,450 and process size is 400 and initially all partitions are empty. Next fit fills in 600 leaving 200 space hole, best fit fills in 450 leaving 50 space hole D is false

Ans: C

Answer 1

Best fit will search for the smallest block which is able to accommodate the request. So, the hole created by the Best Fit is always less than or equal to the hole created using any other method.

Worst fit search for the biggest possible block which is able to accommodate the request. It might be the case that block biggest possible block may be in the first block and both worst and first fit select the same block.

So, we can't say that hole formed by worst fit is always greater than first. The size of the hole can be same too. (B) is false

Ans: (C) Hole created by the best fit is never larger than the hole created by first fit,

The hole created by the Best Fit is equal to the hole created by first fit when the first fit happens to select the smallest block which can accommodate the required size.

Comments

@srestha

The question is not about the no of holes....

Given a single request to accommodate a block and if the heap contains holes of random size, the BEST FIT always selects for the smallest sized block which will be able to accommodate the request.......so in any case the hole formed by BEST FIT is always <= hole formed by FIRST FIT.

equal sized holes might occur when the BEST FIT and FIRST FIT selects the heap block of same size to accommodate the request.

In the question you have  mentioned, we have to accommodate all the 4 requests.....that is not the case here

---

@Sachin Mittal 1 sir does the “Holes” in this question means to refer to the memory which is wasted after the allocation method ?

---

@Harshit Dubey yes, the memory which remains after the allocation method

Answer 2

first fit and last fit may result same size hole.

first fit and worst fit may result same size hole.

the hole created by next fit may be larger than best fit.

BUT best fit creates the holes which are less size or same size than any other scheme.

Option C is correct.

Comments

See here https://gateoverflow.in/2467/gate1994-1-24
Here best fit creating hole , but not first fit. So, best fit hole can be greater than first fit, is not it, in worst fit hole is large enough from any other fit

---

I also thought along the same line @Shaik

Answer 3

Memory allocation by creating holes by BEST FIT Algorithm is always smaller than or equal to the sizes of holes created by other methods  such as FIRST FIT,NEXT FIT and WORST FIT. Again we know that BEST FIT is worst performer.

Hence in this case the option C is true.

Answer 4

The hole created by best fit is never large than that of first fit,

But this does not necessarily mean that best fit is the best amongst all the algorithms

In depends on case to case.

But this condition holds true in every case.

See the image below.