Issues in acyclic graph directories.57 to 58

1. http://raj-os.blogspot.in/ 1
Recap
In the last class, you have learnt:
•How directories are deleted in a tree structure
•Advantages and disadvantages of tree structure
•Acyclic graph Directory Structure
•Its features
•Implementing shared directories and files

2. •HOME PREVIOUS TOPIC NEXT
•PREVIOUS QUESTION PAPERS FOR
OS
•CPP TUTORIALS
2http://raj-os.blogspot.in/

3. http://raj-os.blogspot.in/ 3
Objectives
On completion of this period, you would be able to
•Understand issues regarding deletion of files in an
acyclic-graph structure
•List advantages and disadvantages of acyclic-graph
structure
•Understand the structure of General Graph
Directories and problems

4. http://raj-os.blogspot.in/ 4
Issues In Acyclic Graph Directories
•A file may have multiple path names
•Consequently distinct file names may refer to the same
file
•When traversing the entire file system we may come
across shared structures more than once
Ex: when we copy all files to backup storage same
file may get copied more than once

5. http://raj-os.blogspot.in/ 5
Issues In Acyclic Graph Directories
•Another issue is deletion of shared files
•When can the space allocated to a shared file
be de allocated and reused ?
•Two approaches may be used

6. http://raj-os.blogspot.in/ 6
Approach 1
•Remove the file whenever anyone deletes the
shared file

7. http://raj-os.blogspot.in/ 7
Problems with Approach 1
•Problem is dangling pointers which point to the now-
nonexistent file
•Also, If the file pointers contain actual disk
addresses
•If the space is subsequently reused for other files,
•These dangling pointers may point into the middle of
other files

8. http://raj-os.blogspot.in/ 8
How to handle problems with Approach 1?
•Easy to handle if sharing is implemented by
symbolic links
•If anyone deletes a shared file delete only the link
•Deletion of a link does not affect the original file
•If file entry itself is deleted, then space is de
allocated, leaving the links dangling

9. http://raj-os.blogspot.in/ 9
How to handle problems with Approach 1?
•We can search for dangling links and remove them
•The search can be expensive unless a list of the
associated links is kept with each file
•Alternatively, we can leave the links until an attempt
is made to use them
•At that time, we can determine the file name given
by the symbolic link does not exist and can fail to
resolve the link name

10. http://raj-os.blogspot.in/ 10
How to handle problems with Approach 1?
In Unix
• Symbolic links are left when file is deleted
• It is up to the user to realize that the original file
is gone or has been replaced with a new file
having the same name

11. http://raj-os.blogspot.in/ 11
Approach 2
•Preserve the file until all references to it are
deleted
•To implement this approach, we need a
mechanism to determine that the last reference
is deleted
•A list of all references to a file can be kept

12. http://raj-os.blogspot.in/ 12
Approach 2
•When a link or a directory entry is established, a
new entry is added to the file-reference list
•When a link or directory entry is deleted, we
remove its entry on the list
•The file is deleted when its file-reference list is
empty

13. http://raj-os.blogspot.in/ 13
Problems with Approach 2
•Variable and potentially large size of the file-
reference list

14. http://raj-os.blogspot.in/ 14
How to handle problems with
Approach 2?
•We need not keep the entire list
•Keep only a count of number of references
•A new link or directory entry increments the
reference count
•Deleting a link or entry decrements the count
•When count is zero, the file is physically deleted

15. http://raj-os.blogspot.in/ 15
Summary
In this class, you have learnt:
•Various issues regarding acyclic graph directories
like deletion
•Different ways to handle deletion
•Advantages and disadvantages of acyclic graph
directories
•General graph directories and their disadvantages

16. http://raj-os.blogspot.in/ 16
Frequently Asked Questions
1.Explain how deletion is handled in acyclic
graph directories
2.List the advantages and disadvantages of
acyclic graph directories
3. Explain general graph directories

17. http://raj-os.blogspot.in/ 17
1.Pick the correct statement about acyclic graph
directories
a)Does not allow shared files
b)Easy to handle deletion
c)Allows shared files
d)None of the above

18. http://raj-os.blogspot.in/ 18
2. An acyclic graph can contain
a)No cycles
b)Only one cycle
c)Two cycles
d)Any number of cycles

19. http://raj-os.blogspot.in/ 19
3. In an acyclic graph directory, a shared file can
have
a)Multiple relative path names
b)Multiple absolute path names
c)Both of the above
d)None of the above

20. http://raj-os.blogspot.in/ 20
4. A dangling pointer points to
a)a valid address
b)an invalid address
c)Sometimes a valid address and sometimes an
invalid address
d)None of the above

21. http://raj-os.blogspot.in/ 21
State true or false
A link is a pointer to a file or subdirectory
True

22. http://raj-os.blogspot.in/ 22
State true or false
It is very easy to perform deletion in acyclic graph
directories
False

23. http://raj-os.blogspot.in/ 23
State true or false
Dangling pointers are desirable
False

24. http://raj-os.blogspot.in/ 24
State true or false
A zero count in a file-reference list indicates that the file
is physically removed from the system
True

25. http://raj-os.blogspot.in/ 25
State true or false
A general graph directory does not allow cycles
False

26. http://raj-os.blogspot.in/ 26
State true or false
In a general graph directory certain operations may lead
to infinite looping
True

27. Other subject materials
•Web designing
•Micro processors
•C++ tutorials
•java
home
27http://raj-os.blogspot.in/