Homework 8

Due 3/23/2012 [start of section]

Problem 1

Suppose that I implement a FFS-like file system that stores data in 4KB blocks on disk and that uses 4-byte block IDs in its inodes and triple/double/single-indirect blocks. What is the largest disk this file system can support?

Problem 2

  1. An engineer has designed a FAT-like system and he has used 24 bits for each entry. For a 32-GB disk, what is the minimum size of a file allocation in this system? Justify your answer.

  2. Consider an index-based file system with the inode containing 64 indexes, 1 indirect index pointing to a disk block containing an array of direct indexes, and 1 2-level index in the usual way. Assume that each index takes 4 bytes.
    1. What is the maximum file size under this arrangement, if a disk block is 1024 bytes? Explain how do you compute this maximum size.
    2. How many disk accesses does it take to read one disk block at location 3000321 within a file, assuming no caching. Justify your answer.

Problem 3

Consider a very simple file system for a tiny disk. Each sector on the disk holds 2 integers, and all data blocks, indirect blocks, and inodes are 1 disk sector in size (each contains 2 integers). All files stored on disk are interpreted as directories by the file system (there are no "data files"). The file system defines the layout for the following data types on disk:
inode = 1 pointer to a data block + 1 pointer to indirect block

indirect block = 2 pointers to data blocks

directory = a regular file containing zero or more pairs of integers; the first integer of each pair is a file name and the second is the file's inumber

The value "99" signifies a null pointer when referring to a disk block address or directory name. An empty directory has one disk block with the contents "99   99". The inumber for root directory is "/" is 0.

The following data are stored on disk:

inode array:
0 1  2  3  4   5  6  7   8   9  10 11 12 13 14 15
10
6		 7
99		    8
99		       3
99		                           

disk blocks:
 0  1  2  3  4   5  6 7 8  9  10 11 12 13 14 15
   32
3		    96
1		       1
99		 99
99		 99
99		    57
6		               

  1. How many entries can appear in a maximum-sized directory? (Each entry is a pair of integers)

  2. List all directories stored on this disk (full path names) along with the names of the files stored in each directory.

    directory path name inumber indirect blocks data blocks contents (subdirectories)
    /
    		 0
    		      

  3. Modify the above data structures to add an empty directory called "87" to directory "/"

    directory path name inumber indirect blocks data blocks contents (subdirectories)
    /87
    		        

Problem 4

Consider the (tiny) disk with 64 sectors shown below, which stores a FFS-like file system. The disk reserves the first 16 sectors for its inode array. Each sector stores four 4-byte words. An inode fills a sector and contains 2 direct pointers, 1 indirect pointer, and 1 double-indirect pointer. An inumber is a 4-byte integer. In a directory, a file name is a 4-byte array of 1-byte characters. A block ID is a 4-byte integer. The root directory's inumber is 0.