Homework 5

22C:116, Fall 1995

Due Friday Sept. 22, 1995, in class

1. Background: All disk-based file systems must somehow record the set of disk sectors assigned to each file in some kind of data structure. In a sense, this structure is analogous to the page table in a virtual memory system that maps virtual addresses to physical locations of a page, except that the virtual address is an offset into a file, and the physical address is an address on disk. Consider the following three alternative organizations for this data structure:
   • Use a n-ary tree to index the sectors of each disk file, where each tree-node occupies one disk sector and n disk addresses fit in a node. The depth of the tree depends on how many sectors are in the file.

   • Use a second disk file to index the sectors of each disk file. The second disk file is guaranteed to be smaller than the first by a factor of n, the number of disk addresses that can be stored in a sector, so the recursion inherent in this scheme is guaranteed to terminate.

   • Use a B-tree for each file, where the key used to organize the tree is the offset into the file, and the data recovered by the key gives the disk address of the sector holding the data at that offset. As above, each tree node is a sector.

   The problem: Compare and contrast these schemes. Which would give the fastest access time? Which would give the most efficient use of disk space for the storage of sparse files (those with long runs of unused offsets between those that are used)? Which would give the most efficient storage of small files? Are any of these schemes equivalent to each other?

2. Background: Consider a system with a programmable interval timer. The interface to this has two registers. One register contains the time until next interrupt, and is constantly decremented by the hardware every microsecond. The other register is one bit, used to enable or disable the interval counter interrupt. The timer hardware attempts to request an interrupt whenever the time register is negative and interrupts are enbaled.

   The users of this system want two different timer services. First, users want to be able to issue a delayed signal to a semaphore. To issue such a signal, the user specifies a semaphore and a time interval, in microseconds, and the timer subsystem will signal that semaphore after that interval has passed. Second, users want to be able to inquire about the time and date, specified as a three word quantity, giving day number since the (arbitrarily established) beginning of time, seconds since midnight, and microseconds in the current second.

   The Problem, part A: Ignore the time and date service, and propose an implementation of the above user-level primitives in terms of the given hardware. In your answer, suggest a data structure to hold the list of pending signal operations and give detailed pseudocode for the interrupt service routine and the user-level code for the delayed-signal operation.

   The Problem, part B: Suggest an implementation for the time and date service based on your proposal in part A. This should involve minimal modification to the scheme you originally proposed, plus perhaps an auxiliary process to update the global variables holding the day and second numbers.