GATE CSE 2021 Set 1 | Question: 15

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

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

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

Answer 1

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,

• A. 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.
   
• B. 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.
   
• C. Renaming a File: Can give rise to name conflicts, same reason can be given as option A.
   
• D. Opening of existing file: same reason as option B.

Comments

@rsonx file names have to be unique in a directory. The directory identifies a file using file name(the directory translates file names into directory entries). Two files can have same name only if they are in different directories or sub-directories because now they will have unique paths.

So why would we need unique paths you might ask, the answer lies in how file system uses a file. To use a file (read() or write()) we first need to open it, which is done via open() system call which requires path of the file as one of the argument.

https://man7.org/linux/man-pages/man2/open.2.html

The above question is only concerned with a single directory named foo. So all the file names in this directory has to be unique. 

 

---

@sauravgahlawat Probably the best answer for all the doubts

---

Those who are saying deletion will also cost the whole scanning then please read the option again. Why to check whether a file is there or not??. 

Deletion of an existing file from foo 

Answer 2

For most practical purposes, filenames within a single directory must be unique to ensure proper organization, identification, and operation of files in a computer system.

Exceptions:
Case Sensitivity: Some file systems (like Linux) are case-sensitive. So, "File.txt" and "file.txt" would be considered different files. However, within a single case-sensitive directory, you still couldn't have two filenames that are identical except for case.

Alternate Data Streams (ADS): Windows NTFS file system supports Alternate Data Streams (ADS), which allow attaching additional data to a file with a different identifier. So, you could technically have a file named "report.docx" and another with the same name but an ADS attached, although this is not a common use case.

node = metadata + pointers -> data blocks
directory[....nodes]
foo[name1,name2,name3.....]

Creation of a new file in foo: While naming a new file we have to SCAN to check wheaather name of file is not conflicting with already present files

Renaming of an existing file in foo: SAME AS ABOVE

Deletion of an existing file from foo: No need to SCAN

Opening of an existing file in foo: No need to SCAN

Option A&C