Consider contiguous allocation of physical memory to processes using variable
partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB,
25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are
adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order,
and they are allocated memory using the best-fit technique. After allocating space
to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer
in integer)
Note: \(1\mathrm{K}=2^{10}\)
Consider contiguous allocation of physical memory to processes using variable
partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB,
25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are
adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order,
and they are allocated memory using the best-fit technique. After allocating space
to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer
in integer)
Note: \(1\mathrm{K}=2^{10}\)
Show Hint
Correct Answer: 3
Solution and Explanation
An alternative way to think about this problem is to track only the holes that change, rather than re-listing all of them at every step.
Initial holes (KB): 20, 4, 25, 18, 7, 9, 15, 12. Best-fit always searches for the tightest possible fit so that a process wastes the least amount of leftover space.
Allocating P1 = 16 KB: Among all holes big enough to hold 16 KB (namely 20, 25, 18), the tightest fit is 18 KB because it leaves the smallest leftover (\(18 - 16 = 2\) KB) compared to 20 KB (leftover 4 KB) or 25 KB (leftover 9 KB). So the 18 KB hole is replaced by a 2 KB hole.
Allocating P2 = 9 KB: Among all holes big enough to hold 9 KB (namely 20, 25, 9, 15, 12), the tightest possible fit is the 9 KB hole itself, since it matches exactly and leaves zero leftover. This is the ideal best-fit case - the hole is consumed entirely and vanishes from the hole list.
After both allocations, the surviving holes are: 20, 4, 25, 2, 7, 15, 12 KB (7 holes total, since the original 9 KB hole is gone and the 18 KB hole shrank to 2 KB).
Now filter for holes strictly less than 8 KB: 4 KB, 2 KB and 7 KB qualify, while 20, 25, 15 and 12 KB do not.
So the number of holes smaller than 8 KB is \(3\).
Final Answer: \(3\)
Top Questions on Memory Management and Virtual Memory
- Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string: \[ 7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 1, 5, 6, 1 \] The page fault rate, defined as the ratio of the number of page faults to the number of memory accesses (rounded off to one decimal place) is \(\underline{\hspace{1cm}}\).
- GATE CS - 2022
- Operating System
- Memory Management and Virtual Memory
- Which one of the following statements is FALSE?
- GATE CS - 2022
- Operating System
- Memory Management and Virtual Memory
- In the context of operating systems, which of the following statements is/are correct with respect to paging?
- GATE CS - 2021
- Operating System
- Memory Management and Virtual Memory
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown. The page size is 4KB and page table entry size at every level is 8 bytes. A process \( P \) is currently using 2GB virtual memory mapped to 2GB physical memory. The minimum amount of memory required for the page table of \( P \) across all levels is \(\underline{\hspace{2cm}}\) KB.
- GATE CS - 2021
- Operating System
- Memory Management and Virtual Memory
- Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems