This exam consists of 7 questions, each of which is worth 10 points. If you are registered for 256 you must choose 5 questions to answer; you will be graded on a scale of 0-50. If you are registered for 456 you must choose 6 questions to answer; you will be graded on a scale of 0-60. 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.Try to make your answers as brief and as neat as possible. You shouldn't need more than one page per question, unless you write very big. I have tried to make the questions unambiguous. If you are not sure what a question is asking, make some reasonable assumption and write that assumption down next to your answer. I will generally decline to explain questions during the exam.
- return from exception
- can be used to jump to an arbitrary virtual address, running in kernel mode; can easily crash the machine or break security.
- load TLB
- can be used to gain access to data at arbitrary physical addresses.
- change page table root pointer
- can be used to change the values fetched by the hardware on TLB misses, thereby granting access to data at arbitrary physical addresses.
- change exception vector root pointer
- can cause the machine to jump to an arbitrary virtual address on an interrupt; can easily crash the machine or break security.
- change interrupt priority level
- can lock out interrupts indefinitely, defeating timeslicing and damaging other applications or crashing the machine by causing interrupts to be lost.
(b) Today, many microprocessors have two levels of on-chip cache. Why not organize these as a single level?
(a) Twenty years ago there was barely room for a microcoded CISC processor on a chip; there wasn't room for cache. Fortunately, memory could be accessed with only a few cycles of latency. Over time, processor speed has increased much more than memory speed. Memory latency, measured in processor cycles, has therefore increased dramatically. Processors can no longer afford to wait for memory.(b) At today's densities, we can fit the better part of a megabyte of cache on-chip, but we can't access it fast enough. We create as big an L1 cache as we can without going beyond 1 or 2 cycles of access time, and make the rest L2.
Assuming that instruction and data translation misses are independent, the average instruction will perform 1.2 memory accesses (one for the instruction fetch; .2 for the loads and stores). The average instruction will then suffer 1.2 x 2% = .024 misses, for a translation overhead of .024 x 50 = 1.2 cycles. This gives us a total of 2.4 cycles per instruction: the 2% TLB miss rate has cut the performance of the machine in half.
page set reference FIFO replacement LRU replacement Belady's MIN 0 0* 0* 0* 1 01* 01* 10* 4 014* 014* 104* 2 0142* 0142* 1042* 1 0142 0421 0142 0 0142 4210 0142 3 1423* 2103* 0143* 0 4230* 2130 1430 1 2301* 2301 4301 4 3014* 3014* 3014 total 8 faults 6 faults 5 faults
Signals always occur between instructions; there is never any pipeline state to save or to restore. They provide a C-language interface, rather than an assembler interface, and occur in a process context. They automatically save the previous context in a form that can be restored simply by returning from the signal handler. Signals are never lost, even if handled slowly. There is no notion of levels: delivery of a signal blocks delivery of the same signal until the handler returns, but does not block other signals. Moreover different signals can be blocked independently, explicitly. There are reasonable default actions that happen automatically when the user does not provide a handler.
Static linking is simplest to implement, leads (usually) to the fastest program start-up times, and provides the earliest reporting of linking errors. Load-time and lazy linking economize on disk space and physical memory space. They also deliver the latest version of libraries, automatically. At the same time, they incur the overhead of indirection on all cross-module references, and thus suffer slightly slower execution and larger code size due to position independence. Load-time linking may lead to unacceptably high program start-up latency. Lazy linking is more complex, and performs the largest total amount of work when all references are followed, but has relatively fast program start-up, and avoids overhead for references that are not followed.
(a) What standard batch scheduling policy will minimize turnaround time (average time from submission to completion of a job)?
(b) Why is it difficult to implement user-level threads on top of a single traditional Unix process?
(c) Unix attempts to make the priority of a process inversely proportional to its CPU utilization. Why?
(d) What's wrong with the Banker's algorithm; why isn't it more widely used?
(e) When is busy-wait synchronization preferable to scheduler-based synchronization?
(a) Shortest job first.(b) Because any time one thread blocks in the kernel, none of the others can run.
(c) To favor interactive processes, which tend to be I/O bound.
(d) It requires up-front estimates of maximum resource utilization, and reduces concurrency by forbidding unsafe but non-deadlocked system states.
(e) When the processor has nothing better to do, the expected wait time is less than twice the context switch time, or there is no underlying scheduler (as in an interrupt handler).