CSE 120: Homework #5

Spring 2009

Out: 5/26
Due: 6/4

  1. This homework question will require you to gather some information on ieng6. Consider the files in the subtree rooted at /usr/include. Produce a table of percentage of disk space lost to (internal) fragmentation as a function of disk block size for all of these files. Compute fragmentation for each file (e.g., a 524 byte file with a 1KB block size has 500 bytes of internal fragmentation), but report fragmentation in the table as an overall percentage across all files: total bytes of fragmentation for all files / total bytes allocated in blocks for all files. Do not consider the directories in your computation. Assume that a file of length b > 0 bytes would be stored in ⌈b/s⌉ blocks for a block size of s bytes. A zero-length file requires no blocks. Let s range from 1K to 32K bytes in increments of 1KB.
    Number of files: ...

    Percentation of disk space lost to internal fragmentation across all files for block sizes ranging from 1-32 KB:

     1 KB...32 KB
    % Internal fragmentation   

    You can produce a list of files in this directory with the find command, e.g.:

    find /usr/include -print > ~/files.txt

    will create a file called files.txt that contains the names of the files in /usr/include. You may find it more handy to store the file names in a shell variable. For instance, using the csh or tcsh shells:

    set flist = `find /usr/include -print`

    You can then use wc with the -c switch to find the character lengths of the files, e.g.,

    foreach f ($flist)
    wc -c $f
    end
    And with bash:
    for f in `find /usr/include -print`; do wc -c $f; done

    You may need to write a simple program that computes the percentage of space lost to fragmentation. Or, if you are facile with spreadsheets, you may find them a good tool to perform this computation.

  2. (11.8)  In what situations would using memory as a RAM disk be more useful than using it as a disk cache?

  3. 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 8K bytes, and that the size of a pointer is 4 bytes. How large a file can be indexed using such an inode?

  4. 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 check information to verify file integrity).

    When the 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.

    If desired, can the file be restored into the same inode? If you don't know, think about it. Explain your answer.


The following problem is optional (not required, no points). You might find it useful as practice with synchronization for the final.



voelker@cs.ucsd.edu