Midterm

22C:116, Fall 1998

Douglas W. Jones
Please write your answers on the paper provided. Make sure your name is on the front page, in the same form as it appears in the official class list! Illegible and overly long answers are difficult to grade. Please leave margins around your answers!

NOTE: Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here!

This exam is worth 1/5 of the final grade (20 points; allocate 2 minutes per point).

  1. Background: Consider a 32 bit machine with the common 10-10-12 bit division of the virtual address into segment, page-in-segment and byte-in-page fields. There are 4K bytes per page, 1K pages per segment, and 1K segments in this address space.

    Part A: Consider an application with a data structures that occupy 2 megabytes. How many pages will this application require in its data segment? (1.0 point)

    Part B: Consider the same application, but note the additional information that the data structures are dynamically allocated in a heap, that the block sizes of items in the heap are random with block sizes varying by a factor of two, and that allocation and deallocation appear to be modestly random, but not so random that the application's demand on the heap varies by a great amount.

    Given this new information, what problem(s) would you expect, and how would this (these) problems change your answer to part A? Full credit is reserved for answers with reasonable quantitative estimates of the expected changes. (2.0 points)

    Part C: Ancient UNIX programming advice suggested the following scheme: Occasionally, traverse all of your data structures. For each item in the heap, allocate a block of the same size, copy the contents of the old item into the new one, and then free the old copy. This frequently led to significant performance improvements. Why? (1.5 points)

    Part D: In general, what is the impact of fragmentation on the locality exhibited by a program, and what is the impact of this on the page fault rate of the program? Your answer should be brief and qualitative. (1.5 points)

  2. Background: Consider a machine with a simple protection mechanism. In user state, the MMU is operational, and the hardware will trap any attempt to execute an I/O instruction or an instruction that would change state of the protection mechanism or MMU. In system state, the MMU is turned off, so all addressing is physical addressing, and all I/O and MMU manipulation instructions are legal. Interrupts and traps cause entry to system state, and the return-from-trap and return-from-interrupt instructions restore the protection state of the program that was interrupted.



    Part A: What feature discussed above would be appropriately to use to implement kernel calls on this machine? (1.0 point)

    Part B: What feature discussed above can be correctly described as a gate-crossing mechanism? (1.0 point)

    Part C: Suppose a user program wishes to pass an integer parameter to a kernel call. A natural way to do this would be for the user program to push the parameter on the user's stack prior to the call. Describe the problems the kernel must overcome in order to obtain a copy of this parameter. (1.5 points)

    Part D: Suppose a user program passes a pointer to the kernel call. Once the kernel gets a copy of the pointer, describe the problems the kernel must solve in order to access the object to which the pointer refers. (1.5 points)

  3. Background: The pipe() operating system service in UNIX is defined as follows:
    NAME
    pipe - create an interprocess communication channel

    SYNOPSIS
    pipe(fildes)
    int fildes[2];

    DESCRIPTION
    The pipe system call creates an I/O mechanism called a pipe. The file descriptors returned can be used in read and write operations. When the pipe is written using the descriptor fildes[1] up to 4096 bytes of data are buffered before the writing process is suspended. A read using the descriptor fildes[0] will pick up the data.

    It is assumed that after the pipe has been set up, two (or more) cooperating processes (created by subsequent fork calls) will pass data through the pipe with read and write calls.

    Part A: What fundamental problem in interprocess communication is solved by pipes? (1.0 point)

    Part B: If you were implementing the UNIX kernel, and if, inside your kernel, you had a good semaphore implementation, how many semaphores would you use to implement each pipe, and how would each semaphore be used? (1.0 point)












    Part C: A typical implementation UNIX will use each open file descriptor to locate a record that describes the open file; one format for such a record is given here:

    r: pointer to read routine for this kind of file
    w: pointer to write routine for this kind of file
    s: pointer to lseek routine for this kind of file
    c: pointer to close routine for this kind of file
    d: other data, as needed for this kind of file
    Show the data structures, but not the code, that you would expect to be allocated by the system, in the kernel's address space, in response to a call to the pipe() service. Your answer should show a minimal sufficient set of data structures for implementing the semantics of the pipe. (2.0 points)

  4. Background: Consider an operating system where each user is offered a distinct virtual address space. The disk I/O controllers move images of disk sectors to and from physical memory, but they have no knowledge of virtual memory or of the memory management unit. The sector size on the disk is exactly the same as the page size supported by the memory management unit.

    The file system software includes code to schedule disk requests and it combines all requests for the same sector so that there is never more than one read or write scheduled for a particular sector.

    For the purpose of this question, assume that the file system is entirely implemented at the user level -- that is, assume that user I/O requests are of the form (disk-address, buffer-address, direction).

    Part A: What part of the system must handle the job of translating buffer addresses from virtual to physical form? Your answer should say whether the translation is done by hardware or software, and it should say whether the translation is done before or after the requests are placed in the disk I/O request queue. (1.0 points)

    Part B: What complicating factors arise because of the fact that the user's buffer is in virtual memory, other than the simple matter of address translation? (1.0 points)

















    Part C: The UNIX manual includes a little-used kernel call:

    NAME
    readv - read input

    SYNOPSIS
    cc = readv(d, iov, iovcnt)
    int cc, d;
    struct iovec *iov;
    int iovcnt;

    struct iovec {
    caddr_t iov_base;
    int iov_len;
    };

    DESCRIPTION
    Readv attempts to read nbytes of data from the object referenced by the descriptor d into the concatenated buffers pointed to by the members of the iov array: iov[0], iov[1], ..., iov[iovcnt-1]. Other than its use of iov to refer to a series of buffers, read and readv operate identically.
    This readv mechanism is based on similar features found in the hardware of many high-end DMA controllers. Does the presence of such hardware solve any of the problems you pointed out in part B? Which one(s)? (1.5 points)

    Part D: If the operating system maintains a buffer pool, perhaps also serving as a disk cache, so that all disk output involves, first, copying from the user's buffer to the system's buffer, and then scheduling the read or write, does this solve any of the problems you pointed out in part B? Which one(s)? (1.5 points)