Midterm

22C:116, Fall 1995

Douglas W. Jones
Please write your answers in the exam booklet provided. Make sure your name is on the front cover of the booklet, 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! This exam is worth 1/5 of the final grade.
  1. Background: Consider using data compression to reduce the main memory requirements of less-recently used pages of a virtual address space, as in the Macintosh-based product called RAM Doubler. Ignore the possibility of paging to backing storage and the problems of doing demand allocation, and focus entirely on the idea of compressing less recently used pages and storing the compressed images of those pages in main memory.

    Consider an application with a total memory requirement of 1 megabyte, a working set of 100 kilobytes, and pages that may be compressed to an average of 2/3 of their original size, but with considerable variance from one page to the next.

    Part A: If the heap manager used to store the (variable sized) compressed pages wastes, on average 10% of the heap to fragmentation, what minimum physical memory resources would you expect to be needed to run the application under consideration under the simplified model of RAM Doubler being considered here.

    Part B: Consider the problem of storing compressed copies of pages. Some part of the physical memory will have to be used for this. Describe how you would organize this part of the memory, answering the following questions:

  2. Background: Consider a virtual memory system where each address space consists of up to 1 million capabilities for objects that may be either pages, sealed objects, or other address spaces. Pages in the address space of the current process are directly addressable by that process using machine instructions. The seal and unseal operations for creating and using sealed objects are implemented by the system kernel, as is the move-capability operation for moving a capability from one address space to another.

    Part A: With reference to typical modern hardware, what data structures would you use to represent an address sapce, how would you handle the allocation of storage for those address spaces, and how would you handle the problem posed by the potentially large size of some address spaces?

    Part B: With reference to typical modern hardware, how would you detect and prevent attempts by users to apply conventional machine instructions to objects that are not pages?

    Part C: Describe the implementation of the Move Capability operation on typical modern hardware:

  3. Background: Consider a multiuser database system where update operations frequently require that multiple records be locked prior to the update.

    Part A: Given that all lock operatons must be completed before any record is read during a transaction, describe a simple deadlock avoidance algorithm that will prevent all deadlocks in this system.

    Part B: Given that lock operations are performed one at a time, and that, after locking each record, that record may be read to determine the next record that must be locked:

  4. Background: Consider the following process used as part of the implementation of FIFO queues in terms of semaphores and memoryless message exchange ports:
    head = 0
    tail = 0
    repeat
        receive( channel, msg )
        if msg = "enqueue"
           receive( channel, msg )
           buffer[tail] = msg
           tail = (tail + 1) mod size
        else assert msg = "dequeue"
           send( channel, buffer[head] )
           head = (head + 1) mod size
        endif
    forever
    
    Note that channel is a single memoryless channel used to communicate with both the processes doing the enqueueing and the processes doing the dequeueing.

    The Problem: Write pseudocode, at this level of detail, for the procedures the user would use to enqueue and dequeue buffers full of data on this queue. You will need to use the send and receive primitives (as illustrated in the example) to move data between processes, and you will need to use some semaphores with the wait and signal operations to control that movement. In addition to your code for enqueue and dequeue procedures, you must clearly document the number of semaphores required, and their initial values!

  5. Background: Consider a system with many concurrent processes and a moving-head disk drive. The initial implementation of the disk software for this system handled disk requests on a first-come first-served basis, and after this software was written, the sector size used was tuned to optimize the system throughput.

    After the sector size was optimized, a new improved disk scheduler was written for this system using the circular elevator algorithm.

    The Problem: Would you expect the use of the new improved disk scheduler to change the optimal sector size? If so, would the new optimal sector size be larger or smaller than the original, and how big an impact on system performance would you expect from rewriting all the applications to use this new sector size?

  6. Background: Consider the problem of implementing a file system to support very large files, some of which may span multiple disk devices.

    The Question: Would it be better to first build a large virtual disk out of multiple disk devices and then build a disk scheduler on top of this, or would it be better to insert separate disk schedulers between the large virtual disk implementation and the individual disks? Why?