Question:
To keep track of free blocks in a file system, one of the two approaches is generally used, using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is \(16\) GB, block size is \(2\) KB, and block numbers used are \(32\)-bit long. A single pointer of size \(4\) bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ______. (answer in integer)
Note: \(1K=2^{10}\) and \(1G=2^{30}\)
To keep track of free blocks in a file system, one of the two approaches is generally used, using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is \(16\) GB, block size is \(2\) KB, and block numbers used are \(32\)-bit long. A single pointer of size \(4\) bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ______. (answer in integer)
Note: \(1K=2^{10}\) and \(1G=2^{30}\)
Note: \(1K=2^{10}\) and \(1G=2^{30}\)
Show Hint
Each 2 KB list block loses 4 bytes to its next pointer, leaving room for 511 four byte block numbers per block.
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 16417
Solution and Explanation
Step 1: Find the total number of blocks on the disk.
The disk size is \(16\) GB and each block is \(2\) KB, so the total number of blocks is
\[ \frac{16\times2^{30}}{2\times2^{10}}=\frac{2^{34}}{2^{11}}=2^{23}=8388608 \]
In the worst case, every one of these \(2^{23}\) block numbers might need to be recorded as free, so the linked list must be able to hold up to this many \(32\) bit block numbers.
Step 2: Work out how many block numbers fit in one list block.
Each block used to store the free list is \(2\) KB \(=2048\) bytes in size. Out of this, \(4\) bytes are reserved for the pointer to the next block in the list, leaving
\[ 2048-4=2044 \text{ bytes} \]
free for storing actual block numbers. Since each block number is \(32\) bits, that is \(4\) bytes, the number of block numbers that fit in one list block is
\[ \frac{2044}{4}=511 \]
Step 3: Divide the total block numbers by the capacity of one list block.
We need enough list blocks to hold all \(8388608\) block numbers, \(511\) at a time:
\[ \frac{8388608}{511}=16416.06\ldots \]
Since a fractional block is not possible, \(16416\) full blocks alone are not quite enough.
Step 4: Check the exact remainder.
\[ 511\times16416=8388576 \]
\[ 8388608-8388576=32 \]
So after filling \(16416\) blocks completely, \(32\) block numbers are still left over, and these need one more block to hold them.
Step 5: Final answer.
\[ 16416+1=16417 \]
\[ \boxed{16417} \]
The disk size is \(16\) GB and each block is \(2\) KB, so the total number of blocks is
\[ \frac{16\times2^{30}}{2\times2^{10}}=\frac{2^{34}}{2^{11}}=2^{23}=8388608 \]
In the worst case, every one of these \(2^{23}\) block numbers might need to be recorded as free, so the linked list must be able to hold up to this many \(32\) bit block numbers.
Step 2: Work out how many block numbers fit in one list block.
Each block used to store the free list is \(2\) KB \(=2048\) bytes in size. Out of this, \(4\) bytes are reserved for the pointer to the next block in the list, leaving
\[ 2048-4=2044 \text{ bytes} \]
free for storing actual block numbers. Since each block number is \(32\) bits, that is \(4\) bytes, the number of block numbers that fit in one list block is
\[ \frac{2044}{4}=511 \]
Step 3: Divide the total block numbers by the capacity of one list block.
We need enough list blocks to hold all \(8388608\) block numbers, \(511\) at a time:
\[ \frac{8388608}{511}=16416.06\ldots \]
Since a fractional block is not possible, \(16416\) full blocks alone are not quite enough.
Step 4: Check the exact remainder.
\[ 511\times16416=8388576 \]
\[ 8388608-8388576=32 \]
So after filling \(16416\) blocks completely, \(32\) block numbers are still left over, and these need one more block to hold them.
Step 5: Final answer.
\[ 16416+1=16417 \]
\[ \boxed{16417} \]
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 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