File Systems Practice Questions

Let's break down the calculation for wasted space due to internal fragmentation.

First, calculate the usable data space per block:
A block is $64K = 64 \times 1024 = 65536$ bytes. Since 4 bytes are reserved for the next block pointer, the usable data space is $65536 - 4 = 65532$ bytes.

Next, determine the number of blocks required for the file:
The file size is $1M = 1 \times 1024 \times 1024 = 1048576$ bytes.
The number of blocks needed is $\lceil \frac{\text{File Size}}{\text{Usable Data Space per Block}} \rceil = \lceil \frac{1048576}{65532} \rceil = \lceil 16.007 \rceil = 17$ blocks.

Now, calculate the total space allocated for these blocks:
Total allocated space = Number of blocks $\times$ Block size = $17 \times 65536 = 1114112$ bytes.

The total space used by the file, including pointers (except for the last block's NULL pointer, which is part of the 4 bytes):
Each of the 16 full blocks stores $65532$ bytes of data. The last block stores the remaining data.
Total data bytes stored = $1048576$ bytes.
Total pointer bytes stored = $16 \times 4$ bytes (for the first 16 blocks) + $4$ bytes (for the last block's NULL pointer) = $17 \times 4 = 68$ bytes.
Total bytes used by file content and pointers = $1048576 + 68 = 1048644$ bytes.

Finally, the wasted space due to internal fragmentation is:
Wasted space = Total allocated space - Total bytes used by file content and pointers
Wasted space = $1114112 - 1048644 = 65468$ bytes.

[CORRECT_OPTION: 65468]

In contiguous allocation (A), to insert a block between the 50th and 51st blocks, the subsequent 50 blocks (51 to 100) must be shifted. This requires reading these 50 blocks into memory (50 reads) and then writing them to their new positions (50 writes). An additional write is needed to place the new block. Therefore, $n_A = 50_{reads} + 50_{writes} + 1_{write} = 101$ disk accesses.

In linked allocation (B), to find the 50th block for insertion, we must traverse the file from the beginning. This requires reading each block to follow the pointer chain, resulting in 50 reads. After finding the 50th block, only two more accesses are needed: one write for the new block and one write to update the 50th block's pointer. Thus, $n_B = 50_{reads} + 1_{write} + 1_{write} = 52$ disk accesses.

The total number of accesses is $n_A + n_B = 101 + 52 = 153$.

The maximum file size is the sum of data addressable by all pointers in the inode.

• Direct pointers: 12 pointers $\times$ 4 kB/block = 48 kB.
• Single-indirect pointer: This points to a block of addresses. A 4 kB block can hold $4096 \text{ B} / 4 \text{ B/address} = 1024$ addresses. This level contributes $1024 \times 4 \text{ kB} = 4096$ kB.
• Double-indirect pointer: This adds another level of indirection, contributing $1024 \times 1024 \times 4 \text{ kB} = 4,194,304$ kB.
  The total size is approximately $48 + 4096 + 4,194,304 = 4,198,448$ kB.
  Converting to GB: $4,198,448 \text{ kB} / (1024^2 \text{ kB/GB}) \approx 4.004$ GB. Rounded to one decimal place, this is 4.0 GB.

External fragmentation occurs when there is enough total free space to satisfy a request, but it is not contiguous. Contiguous allocation can lead to external fragmentation as files are deleted and created. In contrast, linked and indexed allocation methods store file blocks in a non-contiguous manner. This flexibility allows them to use any available free block, thus eliminating the problem of external fragmentation.

The maximum file size is the total disk capacity minus the space occupied by the File Allocation Table (FAT).
First, calculate the number of entries in the FAT:
$\text{Number of entries} = \frac{\text{Disk Capacity}}{\text{Block Size}} = \frac{100 \times 10^6 \text{ bytes}}{10^3 \text{ bytes/block}} = 10^5 \text{ entries}$
Next, determine the total space consumed by the FAT:
$\text{FAT Size} = \text{Number of entries} \times \text{Entry Size} = 10^5 \text{ entries} \times 4 \text{ bytes/entry} = 4 \times 10^5 \text{ bytes} = 0.4 \times 10^6 \text{ bytes}$
Finally, calculate the maximum file size:
$\text{Maximum File Size} = \text{Disk Capacity} - \text{FAT Size} = (100 \times 10^6 \text{ bytes}) - (0.4 \times 10^6 \text{ bytes}) = 99.6 \times 10^6 \text{ bytes}$
The maximum size of a file is $99.6 \times 10^6$ bytes.

[CORRECT_OPTION: 99.55 to 99.65]

Here's a step-by-step explanation to calculate the maximum file size:

1. Direct Block Addresses: Each of the 8 direct addresses points to a 128-Byte block.
   $\text{Size (Direct)} = 8 \times 128 \text{ Bytes} = 1024 \text{ Bytes}$
2. Indirect Block Address: An indirect block stores addresses of other data blocks. The number of addresses an indirect block can hold is $\frac{\text{Block Size}}{\text{Address Size}} = \frac{128 \text{ Bytes}}{8 \text{ Bytes}} = 16$. So, one indirect address can point to $16 \times 128 \text{ Bytes} = 2048 \text{ Bytes}$.
   $\text{Size (Indirect)} = 1 \times 16 \times 128 \text{ Bytes} = 2048 \text{ Bytes}$
3. Doubly Indirect Block Address: A doubly indirect block points to blocks that contain addresses, which in turn point to data blocks. This means $16 \times 16$ data blocks.
   $\text{Size (Doubly Indirect)} = 1 \times 16 \times 16 \times 128 \text{ Bytes} = 32768 \text{ Bytes}$
4. Total Maximum File Size: Sum the sizes from direct, indirect, and doubly indirect addresses.
   $\text{Total Size} = 1024 + 2048 + 32768 \text{ Bytes} = 35840 \text{ Bytes}$
5. Convert to KBytes: Since 1 KByte = 1024 Bytes,
   $\text{Total Size} = \frac{35840}{1024} \text{ KBytes} \approx 35 \text{ KBytes}$

Increasing block size reduces the number of I/O requests required to transfer a file, minimizing overhead from disk seek time and rotational latency, which results in better disk throughput. However, larger blocks increase internal fragmentation because files rarely align perfectly with block boundaries. On average, the wasted space per file is approximately $\frac{B}{2}$, where $B$ is the block size. Consequently, a larger $B$ significantly increases internal fragmentation, leading to poorer overall disk space utilization.

Contiguous and linked allocation schemes are unsuitable for very large files due to fragmentation issues and inefficient random access. Standard indexed allocation relies on a single index block, which lacks the capacity to store pointers for files that exceed the index block size limit. Unix file systems overcome this by employing an inode structure that incorporates direct pointers, supplemented by single-indirect, double-indirect, and triple-indirect blocks. This hierarchical, multi-level approach allows the file system to scale index capacity to accommodate arbitrarily large files, making it an extension of indexed allocation.

The number of pointers that can fit in a single disk block is calculated as the block size divided by the block address size: $\frac{1 \text{ Kbyte}}{32 \text{ bits}} = \frac{2^{10} \text{ bytes}}{4 \text{ bytes}} = 2^8 = 256$. The maximum file size is primarily determined by the triple indirect pointer, which points to $(2^8)^3 = 2^{24}$ data blocks. Each data block stores $1 \text{ Kbyte} = 2^{10}$ bytes. Therefore, the maximum file size is approximately $2^{24} \times 2^{10} = 2^{34}$ bytes.

The block size $S = 1024$ bytes ($1$ KB), and each block stores $N = 128$ addresses.
The file size is determined by the sum of capacities of all pointer levels:

1. Direct: $10 \times 1 \text{ KB} = 10 \text{ KB}$
2. Single Indirect: $128^1 \times 1 \text{ KB} = 128 \text{ KB}$
3. Double Indirect: $128^2 \times 1 \text{ KB} = 16,384 \text{ KB} = 16 \text{ MB}$
4. Triple Indirect: $128^3 \times 1 \text{ KB} = 2,097,152 \text{ KB} = 2,048 \text{ MB} = 2 \text{ GB}$
   The total maximum file size is the sum of these, dominated by the triple indirect block, which is approximately $2 \text{ GB}$.

A device driver is a specialized software layer that allows the operating system ($OS$) to communicate with hardware peripherals by translating system calls into device-specific $I/O$ commands. Registers, Cache (Options A, B), and Main memory (Option C) are integral parts of the computer architecture managed directly by the $CPU$ and memory controller, bypassing the need for separate drivers. Conversely, a Disk (Option D) is an external $I/O$ device that necessitates specific driver software to facilitate communication protocols (such as SATA or NVMe) and handle data transfer requests. Thus, among the given options, the disk is the only component requiring a device driver.

I/O redirection is a command-line mechanism that allows changing the default source or destination of a program's standard input, output, or error streams. Specifically, the input redirection operator < enables a program to read data from an existing file instead of the default keyboard input (stdin). This behavior is precisely described in Option B. In contrast, Option A describes the action of renaming a file, and Option C describes "piping" (|), which is a distinct mechanism that connects two independent program streams rather than redirecting a file to a program.

To enable the operating system to mount or access a file system, it must first locate the root directory as the entry point to the directory hierarchy. Because this location cannot be dynamic, it must be established at a predefined, fixed position on the disk (e.g., at specific sector offsets or defined blocks). If the location were variable (options C and E) or resided in volatile main memory (option A), the system would fail to initialize the file tree structure upon boot. Establishing this entry point at a fixed location allows the operating system to consistently retrieve necessary file metadata. Therefore, the root directory must be placed at a fixed location on the disk.