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.
(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.
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.
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.
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.
(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
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.
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.
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.