CSE 120 Spring 2002 Homework 4
Solutions
Problem 1
The Unix file system supports multiple names for
a file, called links. According to the Unix documentation, a link
is:
... an additional directory
entry ... to a file or directory. Any number of links can be assigned
to a file. The
number of links does not affect
other file attributes such as size, protections, data, etc.
There are two kinds of links: hard links
and symbolic links. Again, according to the Unix documentation:
A hard link (the default) is
a standard directory entry just like the one made when the file was created.
... To
remove a file, all hard links
to it must be removed, including the name by which it
was first created; removing
the last hard link releases
the inode associated with the file.
...
A symbolic link, made with
the -s option, is a special directory entry that points
to another named file. ... In
fact, you can create a symbolic
link that points to a file that is currently absent from the file system;
removing the
file that it points to does
not affect or alter the symbolic link itself.
Why are both symbolic links and hard links useful?
Give a scenario where a hard link would be used instead of a symbolic link,
and a scenario where a symbolic link would be used instead of a hard link.
The difference (outside of soft links being able
to span volumes) is that hard links are bound when they are created and
symbolic links are boudn when they are referenced.
-
A hard link is useful for having the same file be
in different naming contexts. For example, in Project 4 having a hard link
to refs.rs means that you don't have to use an awkward file name
to reference it, such as ~/../p3/refs.rs. And, if I were to delete
the link in p3, you would still have access to the file.
-
A symbolic link is useful where there is a copy of
the file where the owner may update its contents. For example, you might
use a symbolic link to ~/../p3/rsdump rather than a hard link.
Then, if I noticed a bug, I could rename rsdump to rsdump.old
and create a new rsdump. You would transparently start using the
new copy.
Problem 2
Consider a file system that uses a FAT.
-
Explain how the FAT is modified when a block is added
to the end of a file. In particular, which entries of the FAT are changed
and which pages of the FAT are written to disk?
If b is the last block of the file and x
is the first free block, then FAT[b] is set to x and
FAT[x] is set to -1 (or whatever indicates the last block
of a file). If we used the representation in class, then x is
FAT[0], and so we would have:
FAT[b] = FAT[0];
FAT[FAT[0]] = FAT[0];
FAT[FAT[b]] = -1;
The pages of the FAT that contain FAT[0],
FAT[b], and FAT[x] are thus written to disk.
-
Does the time and the order in which modified FAT
pages are written to disk matter? In particular, consider the state of
the FAT were the computer to crash at an inopportune time.
The free block should not both be on the free block
list and linked to the file. So, FAT[0] should be written first.
Then, FAT[x] should be written next, since otherwise a failure
could lead to a confusion about which is the last block of the file. Finally,
FAT[b] is written.
Problem 3
The shell line
echo hello > foo
creates a file foo (assuming that it doesn't exist),
opens the file, writes the string "hello" to the file, and closes the file.
-
How many file blocks are directly written as a result
of this execution? Which blocks are they?
Two file blocks are written: one, for file foo, containing the string
hello, and one, for the directory ., containing the link of foo
to it's inode.
-
What metadata is modified by the execution of this
shell line? The inodes of . and foo
are modified. The free inode list and the free block list (or bitmap) is
updated.
-
Give an instance of a reliability-induced synchronous
write that will be generated during the execution of this shell line.
The file block for file foo is removed from the free block list
(or bitmap). A failure could either lead the block to be lost (neither
in an inode or in the free block list) or in both lists. The latter is
worse since such a block could be reallocated. So, after the block is removed
from the free block list, the free block list is written to disk before
the foo's inode is written to disk.
-
Explain what benefit, if any, the inode cache
gives during the execution of this shell line.
For foo, not much since it that inode is just allocated and written
to. (The file block is probably added later, and so having it cached after
it is first allocated accelerates adding the file block). The directory
. has it's inode cached as well (the working directory is open) and so
it needs not to be fetched from disk.
-
If you were designing a file system, you would need
to decide whether the close operation would flush cached data
blocks of that file. What are the benefits and drawbacks of doing so?
It would be useful if an application needs to know that once a file is
closed, the data cannot be lost. Databases need to count on this (and usually
implement their own access methods). It would make file closes quite slow,
though.
last edited 30
May 2002 by kam