edited by
20,751 views
45 votes
45 votes

A $1000$ $\text{Kbyte}$ memory is managed using variable partitions but no compaction. It currently has two partitions of sizes $200$ $\text{Kbyte}$ and $260$ $\text{Kbyte}$ respectively. The smallest allocation request in $\text{Kbyte}$ that could be denied is for

  1. $151$ 
  2. $181$
  3. $231$
  4. $541$
edited by

5 Answers

Best answer
83 votes
83 votes

The answer is (B). Since the total size of the memory is $1000\textsf{ KB}$, let's assume that the partitioning for the current allocation is done in such a way that it will leave minimum free space.

Partitioning the $1000\textsf{ KB}$ as below will allow gaps of $180\textsf{ KB}$ each and hence a request of $181\textsf{ KB}$ will not be met.

$\left[180\textsf{ KB}-200\textsf{ KB}-180\textsf{ KB}-260\textsf{ KB}-180\textsf{ KB}\right]$. The reasoning is more of an intuition rather than any formula.

edited by
109 votes
109 votes

Answer is B.  181KB

Explanation:

As mentioned by @Arjun sir, to get the smallest allocation request that could be denied, we have to minimize the maximum of the hole partition (that is free memory blocks), let's see why.

First we have to note that we are using Variable Partitioning method without compaction,

Variable Partitioning:

i.  the partitions are of variable length and number, AND
ii. When a process is brought into main memory, it is allocated exactly as much memory as it requires and no more.

In compaction we realign the scattered holes to one end of memory, so that a larger hole can be created.

(Initially whole memory is a hole, i.e. free memory, then a process comes and it is allocated exactly the needed space, which creates a partition. In this question we can safely assume that the two given partitions of 200KB and 260KB are allocated to two processes, because otherwise it will all be one single hole of 1000KB and the answer to the question would be 1001KB)

Now let's see all the possible cases:

CASE 1.

If 200KB and 260KB are contiguous, from the beginning of the memory (obviously after the OS partition), then hole has a size of 540KB, so any process asking upto 540KB can be allocated.

CASE 2.

 If 200KB and 260KB are continguous but somewhere in the middle of the memory, then we have two holes left. Hole1 and Hole2 (Refer the image below). If the size of these holes are not equal, say Hole1 = 300KB and Hole2 = 240KB then processes asking for memory upto 300KB can be allocated.

But if we keep hole sizes equal, we can see that Hole 1 = Hole 2 = 270KB, thus maximum 270 KB only can be allocated.

CASE 3

Arguing in a similar manner as in case 2, we can see that size of all three holes must be equal (i.e. 180KB), otherwise we'll have a hole which will allow a process needing more than 180KB to get allocated. 

So 181 KB is the smallest allocation request that can be denied.

Wrong reasoning to get 151 KB:

Someone mentioned that if we order in the following way:

200-260-150-150-150-90 [Wrong division for variable partitions, the order looks like fixed partitions]

we can get the answer as 151KB.

The problem here is that it's given in the question that there are only two partitions, i.e., two processes are allocated space in main memory. So rest space is free memory, i.e., a hole.

So if 200 and 260 are allocated contiguously from the beginning (Or end), we have a hole of 540KB and any process needing memory upto 540 KB can be allocated.For this case the correct ordering would be: 200KB-260KB-540KB or 540KB-200KB-260KB

edited by
2 votes
2 votes
Answer Option B

Explanation :

Total Memory Size= 1000 KB

Used Space=200 KB  + 260 KB =460 KB

Free Space = 1000 KB - 460 KB = 540 KB.
-------------------------------------------------------------------------------------------
Now all options given is +1 than the partition done for free space!

(a) If we take Partition Size= 150 KB

then 540 KB free space will be Partition in three 150 KB and one 90 KB

(b) If we take Partition Size= 180 KB

then 540 KB free space will be Partition in three complete 180 KB.

(c) If we take Partition Size= 230 KB

then 540 KB free space will be Partition in two 230 KB and one 80 KB

(d) If we take Partition Size= 540 KB

then 540 KB free space will be Partition in One One 540 KB.
------------------------------------------------------------------------------------------------------------
Now as we will go for complete Partition so that we are left with option b and d.

for smallest allocation request could be denied , it will be option (b).
Answer:

Related questions

26 votes
26 votes
1 answer
1
Kathleen asked Oct 9, 2014
8,409 views
The process state transition diagram in the below figure is representative ofa batch operating systeman operating system with a preemptive scheduleran operating system wi...