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 ______.
Note: \(1\text{K}=2^{10}\)
Note: \(1\text{K}=2^{10}\)
Show Hint
Correct Answer: 3
Solution and Explanation
Best fit always picks the tightest hole, the smallest one that can still hold the incoming process. Starting holes: $20, 4, 25, 18, 7, 9, 15, 12$ (all in KB).
Step 2: Fit P1, which needs 16 KB.
Holes big enough for 16 KB are $20, 25, 18$. The tightest of these is $18$. Placing P1 there leaves a stub of $18-16=2$ KB in place of the old 18 KB hole.
Updated list: $20, 4, 25, 7, 9, 15, 12, 2$.
Step 3: Fit P2, which needs 9 KB.
Holes big enough for 9 KB are $20, 25, 9, 15, 12$. The tightest is $9$, an exact match, so this hole is used up completely and vanishes from the list.
Updated list: $20, 4, 25, 7, 15, 12, 2$.
Step 4: Sort by size and mark the small ones.
Writing the list in order: $2, 4, 7, 12, 15, 20, 25$. The values under 8 KB are $2, 4, 7$, which is $3$ holes.
\[ \boxed{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