CSE 120: Homework #4
Due: Tuesday June 6 at 11:59pm
- On a Unix-style file system, how many disk read operations are
required to open and read the first block of the file
"/usr/include/X11/Xlib.h"? Assume (1) that the superblock is in
memory, but nothing else; (2) that all directories and inodes are one
block in size; (3) that once a block is read, it is cached in memory
(and does not need to be read again); (4) inode timestamps (like last
access) do not need to be updated (the inode does not need to be
written after access).
- Consider a UNIX-style inode with 10 direct pointers, one single-
indirect pointer, and one double-indirect pointer only. Assume that
the block size is 4KB (including indirect blocks), and that the size
of a pointer is 4 bytes. How large a file can be indexed using such an
The original Berkeley Fast File System increased the Unix file system
block size from 512 bytes to 4096 bytes. Concerned about internal
fragmentation, the FFS also introduced the ability to end a file with
a small fragment. A disk block could be broken up into small
fixed-size fragments, each of which could be used to store the ends of
different files. For instance, a file of size 5000 bytes would need
two blocks (8192 bytes) to store on disk, resulting in 3192 bytes lost
to internal fragmentation. With 1024-byte fragments, though, the file
could be stored with one full-sized block (4096 bytes) and one
1024-byte fragment, requiring 5120 bytes on disk to store the file and
reducing internal fragmentation to just 120 bytes. The tradeoff is
that managing fragments increases the complexity of the file system
- My laptop has 220 (1024 * 1024) files on it. Assume the
disk block size is 4KB and the average amount of internal
fragmentation is 2KB per file. How much storage is wasted due to
internal fragmentation in the file system on my laptop?
- Assume that, with fragments, the average amount of internal
fragmentation goes down to 256 bytes per file. How much storage is
wasted due to internal fragmentation when using fragments?
- Assume that you would receive the same benefits for your laptop.
Would you want the file system to use fragments to save space? Why
or why not?
Consider a file archival system, like the programs zip or tar. Such
systems copy files into a backup file and restore files from the
backup. For example, from the zip documentation:
The zip program puts one or more compressed files into a single zip
archive, along with information about the files (name, path, date,
time of last modification, protection, and checksum information to verify
When a file is restored, it is given the same name, time of last
modification, protection, and so on. If desired, it can even be put
into the same directory in which it was originally located.
Can zip restore the file into the same inode as well? Briefly
explain your answer.
- [Silberschatz] Consider a system that supports 5000
users. Suppose that you want to allow 4990 of these users to be able
to access one file.
- How would you specify this protection scheme in Unix?
- Could you suggest another protection scheme that can be used more
conveniently for this purpose than the scheme provided by Unix?
- [Silberschatz] How does a file cache help improve performance?
Why do systems not use much larger caches if they are so useful?
- Consider a program that executes a loop that issues a read I/O to a
storage device and waits I milliseconds for the I/O to complete,
and then computes on the data returned for X milliseconds, and then
For various values of I and X, compute the
percentage of time that the program spends waiting for I/O and fill
in the following table. If I and X are both 1 ms,
for example, then the program spends 50% of its time waiting for
| || || ||X || ||
| || ||100 ms ||10 ms ||1 ms ||0.1 ms
| || 25 ms (cloud storage) || || || ||
| || 5 ms (HDD) || || || ||
|I || 0.1 ms (SSD) || || || ||
| || 0.0005 ms (NVM) || || || ||
| || 0.0001 ms (RAM) || || || ||