Homework 5

22C:116, Spring 1997

Due Friday Feb. 28, 1997, in class

Douglas W. Jones
  1. The problem: Write correct ANSI C code to implement the data abstraction "stack of integers" in two different ways, one using an array and a stack pointer, and the other using a linked list. Here is a main program that will test your stack implementation.
    		stack * a = arraystack();
    		stack * b = liststack();
    		int i;
    		for (i = 1; i < 10; i++)
    			(*a->push)( a, i );
    		for (i = 1; i < 10; i++)
    			(*b->push)( b, (*a->pop)( a ) );
    		for (i = 1; i < 10; i++)
    			printf( "%d\n", (*b->pop)( b ) );
    Note that the only methods are push and pop, and note that no checking for stack over and underflow is needed! The focus of this exercise is on the basic question of how polymorphic objects are implemented in non object-oriented languages.

  2. We can define a computer system as being well balanced if the rate of data processing in the CPU is exactly matched to the rate of I/O transfer, so that neither the CPU nor the I/O subsystems are ever idle waiting for the other to finish. Real systems never approach this perfect balance, but we can hope to approximate it, for example, by asking that the percent idle time of each subsystem be approximately equal.

    The problem: Describe how to compute the optimal disk sector size, that is, the sector size that will balance the system, given that the CPU can compute N bytes per second of data that must be read or written to the disk, given that the average latency time (seek plus rotation) on the disk is L seconds per I/O transfer, and given that the disk data transfer rate is T bytes per second once the transfer actually begins.

    Note that L and T are easily measured for any disk system, but that, while N depends on the CPU clock speed, it also depends on the type of computation being performed, and therefore, on the mix of programs!

  3. The Xerox Distributed File System (XDFS) used the following scheme to map disk I/O requests from sector-number relative to a particular file-number to sector-number relative to the physical disk: First, concatenate the bit patterns for the file number and sector number (32 bits each) to make a 64 bit integer, then look up this integer in a B-tree on disk in order to locate the particular sector.

    Note: B-trees are a well-known data structure for maintaining balanced trees with between N and 2N pointers per node. They are not the same as binary trees! You may want to review B-trees in a good data structures textbook.

    The low-level file system on the XDFS was quite simple: All sectors on the disk were either index sectors in the B-tree or they were data sectors in some file.

    The Problem, part A: From the user perspective, how does the XDFS low-level file system differ from the UNIX low level file system? Recall that the UNIX low level file system uses I-numbers to reference Inodes that describe files.

    The Problem, part B: What performance benefits and what performance penalties would you expect in a system that changes from the UNIX approach to the XDFS approach. Would one or the other approach deliver better performance for access to some class of file or another?

  4. One problem that confronts designers of file systems is recovery from disk failures; for example, if a system is shut off abruptly while a disk write operation is in progress, one sector (and perhaps more) on the disk will typically be corrupted. On the XDFS system, each sector of each file began with a prefix (written in the sector header, outside the data read or written by the user) that indicated the 64 bit sector-number, file-number pair used to address that sector. Thus, if a disk failure caused the B-tree to be corrupted, it could be reconstructed by a single scan of all sectors on the disk.

    The Problem: The XDFS system also set aside sector 0 of each file to hold the information needed to reconstruct the directory structure on the disk in the event that the directory was corrupted by a disk failure. What information needs to be saved in sector zero of each pair to do this? Assume a simple hierarchical tree-structured directory with no access rights or other extraneous material, where each directory is itself a file of pairs that relate textual file names to the corresponding file numbers. Assume that textual file names are always shorter than the sector size.

  5. A class of students is assigned access to a UNIX system shared with other users. Here is a reasonable access matrix listing typical resources and users in this context:
                           | assignment | gradebook | exam-file |
                Instructor |     R      |    R/W    |    R/W    |
    Users               TA |     R      |    R/W    |    ---    |
           Typical Student |    R/W     |    ---    |    ---    |
              Another User |    ---     |    ---    |    ---    |
    The problem: Given that UNIX supports a quirky special case of access control lists, where each user is a member of a group, and access control lists for files grant access to an individual, one group and the public, how can the access rights in the above matrix be enforced on a UNIX system. The variables you can control are the group memberships, ownership of each file, group of each file, and the access rights on each file's UNIX-style ACL.

    You may want to study the chmod (1), chown (8), and chgrp (1) UNIX commands, as well as the format of the group file (5). Parenthesized numbers refer to traditional sections of the Unix Programmer's Reference Manual (as in the man command).