retagged by
8,285 views
19 votes
19 votes

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 $\textsf{foo}$.

Which of the following operations will necessarily require a full scan of $\textsf{foo}$ for successful completion?

  1. Creation of a new file in $\textsf{foo}$
  2. Deletion of an existing file from $\textsf{foo}$
  3. Renaming of an existing file in $\textsf{foo}$
  4. Opening of an existing file in $\textsf{foo}$
retagged by

1 Answer

Best answer
31 votes
31 votes

Correct Options: A, C


(Note: In the question it’s given “which of the following options require a full scan of foo for successful completion” . Meaning the best algorithm scans the list entirely for each type of input to verify the correctness of the procedure and ,can’t partially scan and complete for any particular instance...)

Each File in Directory is uniquely referenced by its name. So different files must have different names!

So,

  1. Creation of a New File: For creating new file, we’ve to check whether the new name is same as the existing files. Hence, the linked list must be scanned in its entirety.
     
  2. Deletion of an Existing File: Deletion of a file doesn’t give rise to name conflicts, hence if the node representing the files is found earlier, it can be deleted without a through scan.
     
  3. Renaming a File: Can give rise to name conflicts, same reason can be given as option A.
     
  4. Opening of existing file: same reason as option B.
selected by
Answer:

Related questions

18 votes
18 votes
4 answers
2
Arjun asked Feb 18, 2021
10,529 views
Which of the following standard $C$ library functions will always invoke a system call when executed from a single-threaded process in a $\text{UNIX/Linux}$ operating sys...