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: 1K=210
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: 1K=210
Show Hint
Correct Answer: 3
Solution and Explanation
We are given 8 holes in memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB and 12 KB. Two processes P1 (16 KB) and P2 (9 KB) arrive in that order and are allocated using the best-fit strategy, which always picks the smallest hole that is still large enough to hold the process.
Step 1: Allocate P1 (16 KB).
List the holes that are \(\geq 16\) KB: 20 KB, 25 KB, 18 KB. Among these, the smallest is 18 KB, so best-fit places P1 into the 18 KB hole.
Remaining size of that hole after allocation: \(18 - 16 = 2\) KB.
Updated hole list: 20, 4, 25, 2, 7, 9, 15, 12 (all in KB).
Step 2: Allocate P2 (9 KB).
List the holes that are \(\geq 9\) KB: 20, 25, 9, 15, 12. The smallest among these is exactly 9 KB, so best-fit places P2 into this hole.
Since the hole size exactly equals the process size, \(9 - 9 = 0\) KB remains, so this hole disappears completely (no leftover fragment is created).
Updated hole list: 20, 4, 25, 2, 7, 15, 12 (all in KB) - now only 7 holes remain.
Step 3: Count holes of size less than 8 KB.
From the final list \(\{20, 4, 25, 2, 7, 15, 12\}\), the holes smaller than 8 KB are: 4 KB, 2 KB, and 7 KB.
That gives a count of 3 holes.
Final Answer: \[\boxed{3}\]
Top GATE CS Computer Science and IT Engineering Questions
- Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps? - Which ONE of the following statements is FALSE regarding the symbol table?
- Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?
Top GATE CS Memory Management and Virtual Memory Questions
Consider a system that has a cache memory unit and a memory management unit
(MMU). The address input to the cache memory is a physical address. The MMU
has a translation lookaside buffer (TLB). Assume that when a page is evicted from
the main memory, the corresponding blocks in the cache are marked as invalid.
For a given memory reference, which of the following sequences of events can
NEVER happen?A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB
reach is defined as the total amount of physical memory that can be accessed
through the TLB entries. The paging system uses pages of size 4 KB. The virtual
address space is 64 GB and physical address space is 1 GB. If each TLB entry stores
a 4-bit process id, page number, frame number, and a 2-bit control field, then the
size of the TLB (in bytes) is ___________. (answer in integer)
Note: 1K=210, 1M=220, 1G=230
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?