Consider a linear list based directory implementation in a file system. Each…
2021
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 foo. Which of the following operations will necessarily require a full scan of foo for successful completion?
- A.
Creation of a new file in foo
- B.
Deletion of an existing file from foo
- C.
Renaming of an existing file in foo
- D.
Opening of an existing file in foo
Attempted by 77 students.
Show answer & explanation
Correct answer: A, C
Answer summary: Creation of a new file in foo and renaming of an existing file in foo require a full scan; deletion and opening do not necessarily require a full scan.
Creation of a new file in foo: A uniqueness check for the new name must be performed against every existing entry in a linear list, so every entry must be examined and a full scan is required.
Deletion of an existing file from foo: Only requires locating the file's entry to remove it; the search can stop once the entry is found, so a full scan is not necessary in general.
Renaming of an existing file in foo: The new name must be checked against all existing names to avoid conflicts; in a linear-list directory this requires examining every entry, so a full scan is required.
Opening of an existing file in foo: Only needs to find the file's entry to read metadata or pointers; the search can stop when the entry is found, so a full scan is not required.
Key insight: Because the directory is organized as a linear list, proving the absence of a name (needed for creation or renaming) requires checking every entry; operations that only need to locate an existing entry can stop early.
A video solution is available for this question — log in and enroll to watch it.