COEN 283: Study Guide

Operating Systems -- winter, 2008

Prof. John Noll

Santa Clara University

1. Week 1 (January 8):
   • Course Overview; History (Read Ch. 1 & 2 for background, as necessary)
   • Organization (Ch. 3; skim Ch. 4)
2. Week 2 (January 15): Device management (Ch. 5)
   • Program 1 due (January 21, 2008).
   Study questions:
   1. What is the main advantage of interrupt-driven I/O over polling?
   2. Are interrupts required for DMA? Are they useful? Explain.
   3. What abstraction do the BSD Unix device drivers support? Why is it useful for all device drivers to support a single abstraction?
3. Week 3 (January 22): Process Management (Ch. 6 & 7) Study questions:
   1. Figure 6.11 (Page 222) in the text is missing a transition. Explain.
   2. As shown, what kind of multiprocessing (batch, multiprogramming, timesharing, other) does this Figure depict?
4. Week 4 (January 29): Synchronization and IPC (Ch. 8--9) Study questions:
   1. On page 318, Nutt describes an implementation of general semaphores using the ``test and set'' function (called TS()).
      1. Why does the statement

         while(!s.hold)
         

         appear in the V() operation?
      2. Suppose we use this implementation in the bounded buffer problem (Figure 8.18, page 312), with a producer and multiple consumers. Does the semaphore implementation allow the producer to devote its entire time slice to filling the buffer if there are empty slots? Explain.
5. Week 5 (February 5): Deadlock (Ch. 10); Memory Management (Ch. 11) Study questions:
   1. Consider the following shell script demonstrating how one might use 'ln' and 'rm' to implement critical sections:

      ---

      #!/bin/sh
      # Fill a file with monotonically increasing integers.
      # Demonstrates use of 'ln' and 'rm' to implement critical sections.
      # Usage: file-append.sh &; file-append.sh
      # John Noll Monday, March 07 2005
      
      # Create the lock file.
      [ -f file.lock ] || touch file.lock
      
      # Create a repository to hold numbers.
      [ -f numbers ] || echo 0 > numbers 
      
      # Loop, reading last number from the repository, increment it, 
      # then append next number to the repository.
      i=0
      while [ $i -lt 1000 ] ; do
        # Enter critical section.
        while [ true ] ; do  
          ln file.lock lock
          [ $? -eq 0 ] && break 
        done
      
        num=`tail -1 numbers`
        num=`expr $num + 1`
        echo $num >> numbers
      
        # Leave critical section.
        rm lock
      
        i=`expr $i + 1`
      done
      echo "$$ Done"
      

      ---

      1. If we run two copies of this script, as in

         % file-append.sh & file-append.sh 
         

         does this script work correctly? Why or why not?
      2. Is deadlock possible? Why or why not?
6. Week 6 (February 12): Virtual Memory (Ch. 12); Study questions:
   2. For the following questions, assume a machine with a 16 bit address space, 4k page size, and 32k of physical memory.
      1. How many addresses are in each page?
      2. How many pages does a process's virtual address space contain?
      3. Assume the MMU uses a single level page table. How big is the page table?
      4. How many page frames does the machine have?
      5. What is the maximum number of processes that could be resident in memory at once? (Note: the stack grows ``down'' from the highest address, while the code starts at address 0.)
      6. Suppose the kernel occupies the first 8k of memory, and there are three active (ready, running, or blocked) processes A, B, and C. Using the notation `A-r5320' to mean process A reads its logical address 5320, and `A-1' to refer to process A's first page, what would be the contents of memory (in terms of pages) if the processes reference the following addresses in the order given, and the kernel uses a global FIFO page replacement policy? A-r5320, A-r235, A-r1618, A-w64730, A-r5320, B-r112, B-r114, B-w115, B-r65500, B-w65500, B-r115, C-r640, C-r65500, C-r6720, C-r15312
7. Week 7 (February 19): File Management (Ch. 13 & 14)
   • Program 2 due (February 24, 2008).
   Study questions:
   1. An abstraction can be described as a metaphor (the abstraction concept) and a set of operations that support that metaphor (the abstraction interface). The file system provides persistent storage through a set of layered abstractions. Describe the abstraction provided to clients of each of the following layers; be both crisp and concise.
      • The stdio library.
      • The Unix file system calls (open(), read(), write(), close()).
      • The BSD Unix file system has an internal function called rwip() that translates a byte offset from the beginning of the file to a block number. What abstraction does rwip() support?
      • The BSD Unix file system also has an internal function called bmap() that translates a file block number (as calculated by rwip())into a partition block number. What abstraction does bmap() support?
      • Once bmap() calculates a partition block number, bio() takes this number and translates it into a disk block number, that could be provided directly to the controller if the disk uses logical block addressing. What abstraction does bio() support?
8. Week 8 (February 26): Networking and Remote Files (Ch. 15 & 16)
   • Program 3 due (March 3).
   Study questions:
   1. The NFS employs a stateless server. Why is this an advantage?
   2. Why does the NFS protocol specify idempotent operations?
   3. Suppose you wanted to implement an NFS server using a relational database. Describe how you would implement the lookup, read/write, and create operations. Does your implementation comply with the stateless server requirement?
   4. The file system implements a naming abstraction for files, allowing users of the file system to give meaningful names to their persistent data. In general, the naming abstraction has three operations:
      1. bind(name, object-id) - associate name with object. This is what your parents did shortly after you were born.
      2. resolve(name) -> object-id - lookup the object handle associated with a name.
      3. unbind(name) - break the association between name and the object-id to which it was previously bound.
      What NFS procedure calls implement these operations?
   5. Explain where the following ISO-OSI layers are typically implemented (hardware, kernel, user space) and why:
      1. Physical
      2. Data Link
      3. Network
      4. Transport
      5. Session
      6. Presentation
      7. Application
9. Week 9 (March 4): Distributed Systems (Ch. 17 & 18) Study questions:
   1. Suppose that we distribute each phase of the the parallel merge sort implementation we discussed in class to a different processor; this solution still does not utilize all processors equally. Explain why not.
10. Week 10 (March 11): Design Issues (Ch. 19)
    • Program 4 due (March 16, 2008).
    Study questions:
    1. For each of the following services, explain whether the service could be moved outside the kernel into a separate process. Do not consider performance issues.
       1. Process management (scheduling, etc.)
       2. Memory management.
       3. File management.
       4. Input/Output.
       5. Networking.
11. Week 11 (March 18 ): Final Exam Study questions:

Generated Thu Apr 3 12:23:18 2008