Final Exam, with suggested answers

CSC 2/456, 5-2-2000

This exam consists of 8 questions, each of which is worth 10 points. If you are registered for 256 you must choose 6 questions to answer; you will be graded on a scale of 0-60. If you are registered for 456 you must choose 7 questions to answer; you will be graded on a scale of 0-70. You may answer additional question(s) if you wish; I will count these as extra credit. Students with a lot of extra credit may move up a letter grade after I have calculated the final curve for the course. Be sure to indicate on the cover of your blue book which questions are extra; if you forget to say, I'll assume they're the last one(s) in the book.

Every effort has been made to make the questions as clear and unambiguous as possible. If you are not sure what a question is asking, make some reasonable assumption and write that assumption down next to your answer. The proctor will decline to explain questions during the exam.

Please try to make your answers as brief and as neat as possible. No question should require more than one page of blue-book space. You will have two hours to finish the exam.

  1. (a) Many processor implementations attempt to predict the outcome of branch instructions in advance. Explain the need for such branch prediction.

    (b) With the proliferation of processors capable of executing instructions out of order, and of executing multiple instructions at a time, is branch prediction becoming more or less important? Explain.

    (a) In a simple pipelined machine, branch prediction serves to reduce the impact of control dependences by allowing the processor to fetch and begin to execute instructions beyond a branch. The processor must of course be able to quash the execution of such instructions if the prediction turns out to be wrong.

    (b) Branch prediction is increasingly important on superscalar, out-of-order processors. They have a bigger appetite for instructions that can be executed in parallel, and must generally fetch across multiple branches in order to keep their pipelines full.

  2. Absent future knowledge, the most desirable page-out policy is one that chooses as a victim the page that has gone unused for the longest period of time. Explain why a pure implementation of this least-recently-used (LRU) policy is not feasible. Describe a widely-used approximation.
    Pure LRU requires that the hardware keep track of the order in which pages are referenced. Real hardware doesn't do that (it's too expensive). Instead, the typical processor provides a single-bit flag that is set whenever a page is referenced. The operating system uses the bits to implement a not-used-recently (NUR) policy. Periodically the OS clears all the flag bits. Then, when it needs to find a victim, it chooses a page whose flag is still clear, indicating that the page has not been used since the last time the bit was cleared.
  3. In a log-based file system disk blocks are never re-written in place. Rather, each write operation uses the next free space on the disk in sequential order. In the background, a cleanup process "compresses out" obsolete data by moving still-live blocks to the end of the log. Describe the technological trends that argue in favor of such a file system on modern machines.
    Traditional file systems are based on the assumption that reads significantly outnumber writes, and that it is therefore important to maximize locality within files, so that multi-block reads can occur as often as possible.

    Log-based file systems reflect the recent dramatic increases in the size of main memory. On many personal computers and workstations, most reads can now be satisfied from the file system's in-core buffer cache. As a result, writes tend to dominate disk traffic. By writing sequentially, regardless of file, log-based systems maximize the performance of writes.

  4. The standard TCP Internet protocol guarantees reliable, in-order delivery of packets. UDP, by contrast, may lose packets, or deliver them out of order. Explain why many applications choose to use UDP anyway.
    Because it's faster, and because the applications can live with the errors. In some cases (e.g. for real-time transmission of voice) an occasional lost packet is more acceptable than irregular delivery rates caused by retransmissions. In other cases (e.g. for transmission of large files over a local-area network with a low loss rate) application-level error detection and recovery suffices to catch the occasional low-level error; transport-level error control merely adds unnecessary overhead. In addition to the overhead of error checking and sequencing, TCP adds the overhead of connection set-up and take-down, which UDP avoids.
  5. Several modern processors, including the MIPS, Alpha, and PowerPC, provide a pair of synchronization instructions called load-linked (LL) and store-conditional (SC). The load-linked instruction works like any other load, but saves some hidden state for the benefit of store-conditional. The store-conditional instruction works like any other store, provided that (a) the most recent load-linked instruction by the local processor was to the same location, and (b) no "interfering operation" has occurred since that load-linked. If either condition fails to hold, the SC leaves memory untouched, and sets a condition code to indicate its failure.

    (a) Explain what might constitute an "interfering operation".

    (b) Show how to use LL and SC to increment a counter, atomically.

    (a) An interfering operation is anything that might cause the loaded location to be evicted from the local cache. The most important case is a store to the same location by another processor. Other possibilities include certain classes of interrupts and, on some machines, stores by the local processor to locations that map to the same location in the cache.

    (b)

        retry:  r := LL(counter)
                r +:= 1
                SC (r, counter)
                if failed, goto retry
        
  6. Several OS designers have argued that the kernel should provide the smallest possible set of mechanisms, with as much functionality as possible implemented by user-level server processes. Among other things, a minimal kernel makes it easier for the designer to implement multiple OS "personalities", e.g. to run Windows and Unix applications on the same machine at the same time.

    What sorts of functionality must be provided in the kernel -- i.e. cannot be moved into user space? Why does a traditional kernel provide functionality beyond the bare minimum?

    All privileged instructions must by definition be executed in the kernel. Any operation required to protect one user from another (and to protect the kernel from users) must be implemented in the kernel. Any operation that requires global information that cannot safely be shared with users must be implemented in the kernel. In practice, these rules mean that the kernel must implement the creation of address spaces and processes, provide inter-process communication mechanisms, perform all I/O operations on non-virtualizable devices, and in general arbitrate access to scarce resources (memory, cycles, and I/O bandwidth).

    Most operating systems put functionality into the kernel that doesn't strictly have to be there in order to minimize the number of times that control must cross the kernel-user interface, thereby improving performance. Secondarily, they may place functionality in the kernel to improve the quality of decisions, based on global knowledge.

  7. Most operating systems have a notion of priority for processes. In a traditional Unix system, if process A has higher priority than process B, process B will never run until process A blocks, or until the priorities of the processes change. In a lottery-based system, process A is more likely to be chosen to run at any given time, but process B will occasionally be chosen as well. In Windows NT, processes A and B may both run for a fraction of each second, but A may receive a longer quantum (this isn't the only scheduling mechanism in NT, but it plays an important role). Discuss the tradeoffs among these different notions of priority.
    Lottery scheduling and the NT scheduler are both capable of granting proportional shares of the CPU based on process priority. The traditional Unix scheduler can only approximate this through a comparatively complex and unintuitive aging mechanism. Lottery scheduling has the advantage of simplicity, but provides only statistical guarantees of fairness. By adjusting priorities dynamically, the Unix scheduler does a good job of identifying interactive processes. Its strict highest-priority-first policy also does a good job of accommodating soft real-time processes.
  8. In a distributed database system, a transaction is a logically-coherent set of operations that need to occur atomically -- that is, all of the operations occur or none of them do, and they all appear to occur simultaneously from the point of view of any other process. A key feature of transaction systems is the ability of a process to abort a partially completed transaction, so that it appears never to have started. Explain the two fundamental reasons why a transaction might abort. (Hint: one has to do with two-phase locking, the other with two-phase commit.)
    A transaction may abort because of a failure (e.g. a machine crash) or because of interference from another transaction. The standard two-phase commit protocol deals with the problem of failures by tying the success of the transaction to a single log entry at the managing process. The manager doesn't create the log entry until all processes have indicated their willingness to commit; once the log entry is made, no subsequent failure can prevent commitment. The standard two-phase locking protocol deals with interference among processes. In the first phase a process only reads and decides what changes it would like to make. It then attempts to acquire locks, double-check the data it read, and make the changes. It aborts its transaction if it is unable to acquire a needed lock, or if anything has changed since the first phase.

Last Change: 12 May 2000 / scott@cs.rochester.edu