GATE CS 2021 Set 1 Q15 — File Systems

In a linear list-based directory implementation, directory entries (nodes containing file names and metadata) are stored sequentially. To search for a file name, we must traverse the list linearly from the beginning.

Let's analyze each operation for successful completion:

1. Creation of a new file in $\textsf{foo}$
   Before creating a new file, the operating system must ensure that no other file with the same name already exists in the directory $\textsf{foo}$. To guarantee uniqueness, the entire linear list must be scanned. If the file is indeed new (successful creation), the search will reach the end of the list without finding a match. Thus, a full scan is necessarily required.
2. Deletion of an existing file from $\textsf{foo}$
   To delete an existing file, we search for its name in the list. For successful completion, the search stops as soon as the target file is found. Since the file exists, it may be found before reaching the end of the list. Thus, a full scan is not necessarily required.
3. Renaming of an existing file in $\textsf{foo}$
   Renaming a file from an old name to a new name requires two steps:
   • Finding the file with the old name (which can be a partial scan).
   • Ensuring that the new name does not already exist in the directory to prevent name collision. This uniqueness check requires searching the entire list. Since the new name must not exist for a successful rename, this check will always result in a full scan.
4. Opening of an existing file in $\textsf{foo}$
   To open an existing file, we search for its name to locate its metadata. The search terminates successfully as soon as the file is found, which does not require scanning the remainder of the list. Thus, a full scan is not necessarily required.

Therefore, only operations A and C necessarily require a full scan of the directory.