Question

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory \texttt{foo. Which of the following operations will necessarily require a full scan of \texttt{foo} for successful completion?}

• A. Creation of a new file in \texttt{foo}
• B. Deletion of an existing file from \texttt{foo}
• C. Renaming of an existing file in \texttt{foo}
• D. Opening of an existing file in \texttt{foo}

Hint:

In linear directory implementations, any operation that must ensure file-name uniqueness requires a complete directory scan.

Answer 1

The Correct Option is A, C

Step 1: Understand linear list based directory structure.
In a linear list based directory, file entries are stored sequentially without indexing or hashing. Hence, operations that require checking all existing file names may need a complete traversal of the directory.

Step 2: Analyse creation of a new file.
While creating a new file, the system must ensure that no file with the same name already exists in \texttt{foo}. Since the directory is a linear list, this uniqueness check necessarily requires scanning all entries. Hence, a full scan is required.

Step 3: Analyse renaming of an existing file.
Renaming a file also requires checking that the new name does not clash with any other file name in the directory. This again requires comparing the new name against all directory entries, which necessitates a full scan.

Step 4: Eliminate other options.
Option (B): Deletion requires locating the file, but once found, the operation can be completed without scanning the entire directory.
Option (D): Opening a file only requires finding its entry, which may occur before reaching the end of the list, so a full scan is not mandatory.

Step 5: Conclusion.
Therefore, the operations that necessarily require a full scan of directory \texttt{foo} are creation of a new file and renaming of an existing file.