Assignment 6, due Oct 4

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Classical operating systems texts cover the relationship between files, file systems and disks at great length, but say little about window managers.

    The Problem: In what sense is the relationship between windows, window managers and graphical display devices similar to that between files, file systems and disks? What are the key conceptual differences, aside from the obvious difference that a file is a one dimensional string of bytes while a window is a two dimensional array of pixels and the differences that are consequences of this.

  2. Background: An open disk file can be considered as a virtual disk, where the interface between upper levels and the file system supports the exact same operations as the interface of the disk I/O driver. Assume these operations are:
    disk->post_read(buffer,sector,done)
    disk->post_write(buffer,sector,done)
    given a pointer to a buffer holding one sector, given a sector number, and given a pointer to a semaphore, read or write that sector and signal the semaphore when the transfer is completed.
    disk->get_info(buffer)
    given a pointer to a buffer, return, in that buffer, the number of sectors on this disk or in this file, the number of bytes per sector, the number of sectors per track, the number of tracks per cylinder (all useful for optimizing data layout), and perhaps other information that doesn't matter for our purposes.

    Usually, we think of disk files as being smaller than the corresponding physical disk, but this need not be the case.

    Assume your machine has a disk interface bus that allows several tens of disks to be attached, and your disk I/O driver is able to direct input or output to any of these disks.

    The problem: Your customer wants to develop software for editing motion pictures, with an expected uncompressed file size of 2 terabytes (2 hours times 24 frames per second times 4 million pixels per frame times 24 bytes per pixel). You can store such a file only on an array of disks. Describe the internal representation of an open file of this type and outline any special code you would need in the read and write routines.

  3. Background: The Xerox Distributed File System was based on the idea that each sector and file would be completely self-describing. On an XDFS disk, two words in the prolog of each disk sector were used to hold the sector number of the sector in the file and the file number of the file in the file system (analogous to an I-number). In theory, to read sector i of file j, all that was needed was to scan the entire disk for a sector with <i,j> in its prolog; in fact, the tuple <i,j> was used as a search key in a B-tree data structure that related each key to a particular sector number on disk.

    All XDFS files were self-describing, with sector -1 of each file holding the file name of the file and the file number of the directory where that file was indexed. In theory, therefore, no data needed to be stored in each directory, since these back pointers encode the entire directory tree; In fact, of course the directory stored <textual-name,file-number> tuples.

    Assume 32-bit file numbers, 32-bit sector numbers in the file, 32-bit sector numbers on disk. Assume 1K bytes per sector, and assume a disk that holds 4 Gigabytes. (All these are modern numbers; the real system had smaller numbers!)

    Part A: Given that each B-tree node is 1 disk sector, and given that the file system is half full, how many disk accesses would be expected to find the disk address of sector i of file j, assuming that sector exists!

    Part B: A power failure during a write operation corrupts the contents of a random sector on disk. Describe the computation required to recover from this loss prior to the start of normal operation. Also, what is the maximum information loss due to this system failure. (Unix systems have a similar recovery program called fsck, but it cannot recover as well as its cousin on XDFS).

  4. The problem: What are the objects in the domain of a Unix process, from the point of view of the operating system? There are several different classes represented in this domain!