Home CS439

CS439: Principles of Computer Systems

Homework 10, Part 1

Due: 9:45a Thursday, November 20, 2015

Part 1 of the homeworks must be submitted electronically. Please refer to the homework turnin instructions.

  1. Consider a multi-level paging system with 128 pages and a page size of 256 bytes. The system has 1024 bytes of physical memory and is byte addressable. Assume the first-level page table holds 8 entries.
    1. How many bits are in a physical address?
    2. How many bits of the virtual address represent the first-level page table?
    3. How many bits of the virtual address represent the page number?
    4. How many bits are in the complete virtual address?
    5. What size are the page frames?
  2. Pooh Software Ltd. is selling a file system that uses a UNIX-like file system with multi-level indexing. For more reliability, the inode array is actually replicated on the disk in two different places. The intent is that if one or a group of sectors that are storing either replica of the array become bad, the system can always recover from the replica. Discuss the effect of having this replicated data structure on performance.

  3. Sun's network file system (NFS) protocol provides reliability via:
    • at-most-once semantics
    • at-least-once semantics
    • two-phase commit
    • transactions

  4. In two-phase commit, suppose the master fails after writing ``GLOBAL_COMMIT'' to disk and sending ``GLOBAL_COMMIT'' to all participating nodes but before any of the nodes receive this message. Suppose that the ``GLOBAL_COMMIT'' message reaches i of the n participants and that the participants implement a protocol in which they communicate with one another when they suspect the primary has died. What is the minimum number of participants that must receive the ``GLOBAL_COMMIT'' message to allow the participants to complete the transaction without waiting for the master to recover?

  5. Considering all the pieces of the operating system we have discussed, describe the steps the OS takes when performing a context switch. Assume that processes are waiting in the ready queue.