+1 vote
298 views

Q : In variable allocation without compaction strategy of memory allocation , can we allocate the memory space to a process arbitrarily anywhere within the free space..I have a doubt on this since the allocation should comply with the standard methods like best fit , worst fit or  can we allocate arbitrarily ?.

Actually I m facing this doubt on the question having link :

https://gateoverflow.in/2747/gate1996_2-18

Plz explain someone..

First Part:

In variable partition method, in order to have better utilization of main memory, OS must use one of the placement algorithms such as best fit, first fit, next etc.

So if the OS designer chooses to assign memory to processes arbitrarily, it would lead to inefficient use of memory.

Second Part:

Explanations:

First Part:

In one of the examples given in the book by stallings, in variable partitioning (referred as dynamic partitioning in the book) :

In this example,  processes start by getting allocated one after other (which is not necessary as we'll see later), but later after few swappings have taken place, holes are created. Now OS would have used compaction to line up the free space which is a time consuming problem.

So OS would try to reduce the need of compaction by managing the allocation of holes to processes efficiently and for that uses placement algorithms such as : best fit, first fit, next fit etc. (in our case we are ignoring compaction, which we can think as reducing the need of compaction to maximum extent)

This whole thing, i.e., managing the allocation of holes to processes efficiently can be done from the beginning itself, considering whole memory as one big hole, and use placement algorithms such that the need of compaction is minimized (we can totally ignore compaction in our case)

edited
0
@pratyush @Habib

why r we creating equal length holes?

do u mean if there are equal length holes, then chance of compaction will be less?

explain plz
+1

If yes, then consider this:

say the holes and partitions are arranged like this: hole1, 200KB, hole2, 260KB, hole3

Now let's divide the remaining 540 KB to as follows: hole1=300KB, hole2=160, hole3=80

Clearly, any process requiring memory upto 300KB can be allocated.

So let's consider another arrangement hole1=200KB, hole2=170KB, hole3=170KB

In this case any process requiring memory upto 200KB can be allocated.

So, if keep reasoning this way, we see that unless hole1=hole2=hole3=180KB, there'll always be a hole > 180KB which can be allocated to a process requiring more memory than 180KB.

So if we keep the size of holes equal, incoming process has to have less than or equal to 180KB requirement, which is the minimum as we've seen.

If we have equal length holes, chance of compaction will increase in my opinion, because the size of holes don't have variation in them, so any process requiring, say 200KB can't be allocated although there is space available (540KB is available) i.e., external fragmentation, So there is a need of compaction to line up the free space contiguously. This problem is similar as in fixed partitioning with equal size partitions where we try to minimize internal fragmentation by keeping unequal size partitioning.

0
got it, thanks

the doubt is genuine . but if we will consider that question(on link) it is asking about the  smallest allocation request in Kbytes that could be denied is for ?? where we will totally focus on our intuition and that will always considered under arbitary allocation.