Homework 5

22C:116, Spring 1995

Due Friday Feb. 24, 1995, in class

1. Background: See the lecture notes for Feb 17 in the section on UNIX I-nodes.

   The problem: As described in the notes (any errors included!), what is the exact maximum size, in bytes, of a file under the classic UNIX file system. This number is stated causually as about 8 megabytes.

   If the I-node is modified, as suggested, to add another tree of sectors for even larger files, what is the new maximum?

2. Background: The performance of file systems can be improved by organizing the sectors of each file so they are near each other on the disk, thus minimizing the seek time. This is easily done if all sectors of a file are allocated at the same time, but it is more difficult when file space is allocated a sector at a time, as the file grows.

   Assume that your disk has a capacity of something like one gigabyte, with 4K bytes per sector, 512 cylinders and 512 sectors per cylinder, perhaps divided up over 8 recording surfaces so there are 64 sectors per track. Ideally, successive sectors of each file should be in the same cylinder as their predecessors, but it doesn't matter what track they are on withing the cylinder.

   The problem: Design a disk-resident data structure appropriate for tracking the free sectors on such a disk. Show how this structure can be used to support a reasonably efficient algorithm for allocating a new disk sector to a file, given the disk address of its predecessor.

3. Background: Most files on most systems are read and written sequentially. If a disk cache is used, this suggests that use of a pure demand-based approach to sector replacement in the cache is a mistake. In fact, least recently used replacement may be the wrong policy to use in supporting a file system!

   The Problem: Give a high level description of a reasonable policy for anticipatory fetches in such a cache, and describe what information from the file system must be available to the policy in order to correctly anticipate demands posed by the file system.

4. Background: The UNIX file system is not a pure hierarchically structured file system. A single data file under UNIX may be included in multiple directories. Arbitrary links between directories are not allowed; the UNIX directory structure is a pure tree (with back-links on each branch).

   The Problem: Why did the UNIX designers forbid arbitrary graph structures in the links between directories? Some experimental file systems have allowed arbitrary linkage between directories. What special problem must be solved when such links are allowed?