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

But considering your logic for creation that same name file may be present  but if that is the case then for deletion also we have to scan the whole list as files with duplicate name may be present and similarly for opening the file also but we can create new file in the front of the list always without checking so the ans may be  B,C,D only

---

Consistency should be maintained by the file management system, each file must posses a unique name to identify it, creation requires you to verify all file names before creating it. If we create without checking all file’s name then it would become inconsistent.

---

if that is the case then for deletion and renaming also we will need full scan

---

Again as I’ve said deletion requires you to delete a file and it’s unique identifier here it’s name. Deletion from a list pf unique items doesn’t remove it’s uniqueness...

Consider a list of number where uniqueness has to be maintained…
2->5->3->4->1

If I want to insert a number say 1 & 6I’ve to search till the end of the list to check whether the item is present or not, there’s no way around this since the list isn’t sorted in which case we needn’t scan till the end.

Insertion is blocked for 1 and allowed for 6.
6->2->5->3->4->1

If we’ve delete say two files 1 & 5 we needn’t scan till the end to delete since once if we’ve found the file, there’s no need to scan, simple delete wouldn't ruin it’s uniqueness. For 1 we search till the end if it’s present for 5 once we’ve found it we simply delete it/

6->2-->3->4

---

B,C,D don’t you think

---

it is given that is follows linked list implementation,but  for linked list deletion, renaming, opening we need to search till end ,but new node can be inserted in starting.

So why not b,c,d is the answer?

---

Understand the question properly and substantiate your doubts with clear examples before commenting otherwise. Because it gives an incentive for someone to look at your doubts legitimately as worthwhile.

Don’t take it as a bad remark, Enjoy...

---

Bro, they told about necessarily, so this word clear everything

---

They should have provided more information by mentioning that no two files could have same name. A FS could be implemented that allows multiple files with same name and whenever that filename gets queried, OS will issue an error saying multiple files or return both the files. I mean there is no general rule about it.

---

@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