Question:
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}\)
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
Use best fit: pick the smallest hole that still fits the process, split off the leftover as a new smaller hole, and remove a hole completely if the process fits it exactly.
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 3
Solution and Explanation
Step 1: List the holes and understand best fit.
The memory has 8 holes of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. In the best fit method, a new process is placed in the smallest hole that is still big enough to hold it. This keeps the leftover gap as small as possible.
Step 2: Place P1 (16 KB).
We need a hole of at least 16 KB. The holes of size 20 KB, 25 KB, and 18 KB qualify. Among these, the smallest is 18 KB, so P1 goes into the 18 KB hole.
The leftover space in that hole is
\[ 18 - 16 = 2 \text{ KB} \]
So the 18 KB hole is replaced by a smaller hole of 2 KB, and the hole list becomes:
20 KB, 4 KB, 25 KB, 7 KB, 9 KB, 15 KB, 12 KB, 2 KB.
Step 3: Place P2 (9 KB).
We need a hole of at least 9 KB. The holes 20 KB, 25 KB, 9 KB, 15 KB, and 12 KB qualify. The smallest of these is exactly 9 KB, so P2 fits perfectly into the 9 KB hole with no leftover space.
That hole is fully used up and disappears from the list. The remaining holes are:
20 KB, 4 KB, 25 KB, 7 KB, 15 KB, 12 KB, 2 KB.
Step 4: Count the holes smaller than 8 KB.
Going through the final list 20 KB, 4 KB, 25 KB, 7 KB, 15 KB, 12 KB, 2 KB, the holes smaller than 8 KB are 4 KB, 7 KB, and 2 KB.
That is a total of 3 holes.
Final Answer:
The number of holes of size less than 8 KB after allocating P1 and P2 is
\[ \boxed{3} \]
The memory has 8 holes of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. In the best fit method, a new process is placed in the smallest hole that is still big enough to hold it. This keeps the leftover gap as small as possible.
Step 2: Place P1 (16 KB).
We need a hole of at least 16 KB. The holes of size 20 KB, 25 KB, and 18 KB qualify. Among these, the smallest is 18 KB, so P1 goes into the 18 KB hole.
The leftover space in that hole is
\[ 18 - 16 = 2 \text{ KB} \]
So the 18 KB hole is replaced by a smaller hole of 2 KB, and the hole list becomes:
20 KB, 4 KB, 25 KB, 7 KB, 9 KB, 15 KB, 12 KB, 2 KB.
Step 3: Place P2 (9 KB).
We need a hole of at least 9 KB. The holes 20 KB, 25 KB, 9 KB, 15 KB, and 12 KB qualify. The smallest of these is exactly 9 KB, so P2 fits perfectly into the 9 KB hole with no leftover space.
That hole is fully used up and disappears from the list. The remaining holes are:
20 KB, 4 KB, 25 KB, 7 KB, 15 KB, 12 KB, 2 KB.
Step 4: Count the holes smaller than 8 KB.
Going through the final list 20 KB, 4 KB, 25 KB, 7 KB, 15 KB, 12 KB, 2 KB, the holes smaller than 8 KB are 4 KB, 7 KB, and 2 KB.
That is a total of 3 holes.
Final Answer:
The number of holes of size less than 8 KB after allocating P1 and P2 is
\[ \boxed{3} \]
Was this answer helpful?
0
0
Top GATE CS Operating System Questions
- Processes \( P_1, P_2, P_3, P_4 \) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
- With respect to deadlocks in an operating system, which of the following statements is/are FALSE?
- Consider a system consisting of \(k\) instances of a resource \(R\), being shared by 5 processes. Assume that each process requires a maximum of two instances of resource \(R\) and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.The minimum value of \(k\) for the system to be deadlock-free is __________. (answer in integer)
- Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7. The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)
- Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.
int main () { int i; for (i = 0; i < 3; i++){ if (fork() == 0){ continue; } break; } printf("Hello!"); return 0; }The total number of times that the printf statement gets executed is ________.
View More Questions
Top GATE CS Memory Management and Virtual Memory Questions
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 ?
View More Questions