GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
205 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 :

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

Plz explain someone..

asked in Operating System by Veteran (87.4k points) 15 57 292 | 205 views

2 Answers

+3 votes
Best answer

Short Answer:

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:

Correct answer will be 181 KB. I have added my answer to the Gate question. Please have a look at it.


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)

 

 

answered by Loyal (4k points) 6 12 27
edited by
@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

@Srestha: Are you asking about the gate question?

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.

got it, thanks
0 votes

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. 

answered by Loyal (4.8k points) 2 18 56


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
Top Users Oct 2017
  1. Arjun

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
Notable Question Sanjay Sharma
27,262 questions
35,076 answers
83,760 comments
33,185 users