GATE CS 1996 Q2.18 — Memory Management and Virtual Memory

To find the smallest allocation request that could be denied, we need to determine the worst-case distribution of the remaining free memory that minimizes the size of the largest contiguous free block (hole).

• Total memory: $1000\text{ KB}$
• Allocated partitions: $200\text{ KB}$ and $260\text{ KB}$
• Total occupied memory: $200\text{ KB} + 260\text{ KB} = 460\text{ KB}$
• Total free memory: $1000\text{ KB} - 460\text{ KB} = 540\text{ KB}$

With two allocated partitions, the free memory can be divided into at most $3$ separate free holes (one before the first partition, one between the two partitions, and one after the second partition).

To minimize the size of the largest free hole, we distribute the $540\text{ KB}$ of free space as evenly as possible among these $3$ holes:

In this configuration, the maximum contiguous free block available is $180\text{ KB}$. Consequently, any allocation request of size $181\text{ KB}$ or more cannot be satisfied and will be denied. Thus, the smallest request that could be denied is $181\text{ KB}$.