The Gateway to Computer Science Excellence
+1 vote
Consider five memory partitions of size 100 KB, 500 KB, 200 KB, 450 KB and 600 KB in same order. If sequence of requests for blocks of size 212 KB, 417 KB, 112 KB and 426 KB in same order come, then which of the following algorithm makes the efficient use of memory?




in Operating System by (197 points)
edited by | 398 views

Next Fit doesn't satisfy the order of requests

First Fit and Best Fit satisfy the order of requests but which is better utilization of Memory, i don't know how to say

Best Fit :- 500 k used by 417 ===> 83.4% used and 450 k used by 212 ====> 47% used

First Fit :- 500 k used by 212 ===> 42% used and 450 k used by 417 ====> 93% used

Both using same partitions, i mean empty partitions are same for both allocation policies

Even I got the same answer but in test series solution they are ignoring the fact that we can fill the internal fragments too if there is enough space for a request to be placed. And even I am not sure how they got next fit as the answer which is not satisfying 1 request.
@Shaik why are you saying that next fit doesnt satisfy the order of requests?Since nothing is mentioned in the question, so we need to use dynamic partitioning right?

If we use dynamic partitioning, then all the requests are satisfied
if we use dynamic partitioning then amount of memory waistage in first fit will be same as amount of memory waistage in next fit policy i.e 683KB .in this case option (D) will be correct .but in question it is not mention about   dynamic  partitioning.

But as nothing is mentioned here,so we should take dynamic partitioning. check this link once

Here as nothing is mentioned in the question, so we have assumed dynamic partitioning and solved the question.


Somoshree Datta 5  yes  you're correct if in the question they doesn't mention the term "fixed partitions"

then we always assumed dynamic partitions

and even though they're showing a partition present as one hole in that hole you could put many processes if the space permits



@Magma could you please tell me the answer for this question? first fit, best fit and next fit are all giving the same results. But the answer is given as C.

Somoshree Datta 5 yes all 3 giving the same results

jhaanuj2108 can you post the solution that's given ???


But here, they use the term "memory partitions of size"

it could be static also :3

But in the link that i have mentioned previously, there it is said "blocks of memory size"; blocks mean partitions only right? But still there we used dynamic partitioning.
i don't know why this much discussion is going on.... it is not standard question, if it is standard question then they will informs either it is fixed or variable partition.

what i observe that they are trying to say that

 two blocks of memory available of size 150K followed by a block size 350K , it means that after

the 3 process request (50K, 300K, 600K) ,  two memory block are available


but whenever they declare a partitions before hand that definitely  it's fixed partitioning

I may be wrong here :3




Shaik Masthan

hmm correct ...leave that question :3


Requests: 212,417,112,426

Best Fit :

100 500 200 450 600

                                 417                   112                          212             426

Memory wastage : (500-417) + (200-112) + (450-212) + (600-426) = 583 KB

First Fit :

100 500 200 450 600

                              212                 112                        417                     426

Memory wastage : (500-212) + (200-112) + (450-417) + (600-426) = 583 KB

Next Fit :

Next fit is a modified version of ‘first fit’. It begins as first fit to find a free partition but when called next time it starts searching from where it left off, not from the beginning. This policy makes use of a roving pointer. The pointer roves along the memory chain to search for a next fit. This helps in, to avoid the usage of memory always from the head (beginning) of the free block chain.

 I take ^ as the rover pointer

100 500 200 450 600

                                 212 ^ ...................................

                                                                                    417 ^.................


The last request cannot be fitted. But in the solution madeeasy put 426 in the last block only!

This is a fixed size partitioning technique and here a block cannot accomodate more than 1 request that is why this technique suffers from internal fragmentation. I don't know why they did like that. :/                              

What would be the answer?

Both first fit and best fit are efficient here.
Answer given is Next Fit :/

Did u get it.

Even next fit is not able to allocate last request :/
See my comment i mentioned what they did..They allocated the last request to the last block only where 112 KB is already there! :|
Its fixed partitioning only, why else they have mentioned sizes beforehand?
Since they have mentioned size of partitions it is a fixed size partioning.

Considering this,

Best Fit and First Fit leads to just internal fragmentation of 583 KB.

Next Fit leads to internal as well as external fragmentation of total 1235 KB.

1 Answer

0 votes
In this if you use dynamic allocation partition then option (d) are correct .

Both next field and best field result are same which gives total 683 space are vacent. so acording to me if there are dynamic allocation partition then answer will be d if it is static then answer will be change.
by Active (1.8k 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,374 answers
105,288 users