Midterm Exam, with suggested answers

CSC 256/456, 3-1-2000

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.

  1. Privileged machine instructions can be executed only when the processor is running in kernel mode. List three machine instructions that need to be privileged, and explain briefly why we need to prevent them from being executed in user mode.
    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.
  2. (a) Twenty years ago, microprocessors didn't have any on-chip cache. Why not?

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

  3. Suppose we have a computer that sustains an average of 1.2 cycles per instruction on some standard benchmark when all address translations hit in the TLB. Suppose further that one fifth of all instructions are loads or stores. (Instructions themselves, of course, must also be fetched from memory.) Finally, suppose that the computer requires an average of 50 cycles to resolve a TLB miss. If the TLB hit rate is really only 98\%, what will the actual number of cycles per instruction be?
    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.
  4. Suppose we have a program that uses 5 pages and that has been alloted 4 page frames in a system with local page replacement. Suppose that the program's reference string begins with 0142103014. How many page faults (including cold start faults) will result with a FIFO page replacement strategy? How many will result with an LRU strategy? How many will result with Belady's MIN?
    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
  5. One view of the job of the OS is to provide each process with a virtual machine that is easier to use than the physical machine. Unix signals can be seen in this light as a virtualization of interrupts. What characteristics of signals make them easier to use than interrupts?
    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.
  6. Summarize the comparative advantages and disadvantages of static, load-time, and lazy (fully dynamic) linking.
    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.
  7. Answer all of the following sub-questions, in one sentence each .

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


Last Change: 3 March 2000 / scott@cs.rochester.edu