Grade Distribution

  65 - 69:   65
  70 - 74:   70 71
  75 - 79:   75 76 79
  80 - 84:   82 82 82 83 83 84
  85 - 89:   86 86 86 87 88 88 89 89 89 89 89
  90 - 94:   90 90 93 94 94
  95 - 99:   96 96 96 97

Midterm Answers

Part I: General Questions

1. [Lec #3, Slide #1]
   How does the dispatcher gain control?
   Saving context (dispatcher code can overwrite registers before saving)

2. [Lec #3, Slide #12] and [Lec #3, Slide #24]
   FIFO: CPU-bound jobs started first before I/O-bound jobs
   RR: time-slice is too long.

3. [Appeared in old exam]
   FIFO: 10 page faults:

   A       x   E       D
     B       x   A       E
       C           B  
         D           C

   LRU: 8 page faults:

   A       x     x       E
     B       x     x      
       C       E       D
         D           C

4. [Lec #6, Slide #10], [Lec #7, Slide #16], and [Lec #12, Slide #15]
   Small page size: huge page table, more TLB misses
   Big page size: internal fragmentation
   Small block size: smaller largest file size, and more I/Os
   Big block size: internal fragmentation

5. [Lec #9, Slide #5]
   Goto TLB. If TLB hit get frame#.
   If TLB miss, goto MMU address translator, get frame# if no page fault.
   If page fault, trap to OS code to perform page replacement.

6. [Lec #13, Slide #15]
   Allocate runs of blocks of the same file within a cylinder group.
   Keep files in a directory in the same cylinder group.
   

7. [Lec #14, Slide #9]
   a) D and C before crash, and B after crash: block bitmap (B) has not been written, but there is an valid inode pointing to it (C and D). Another inode can point to the same data block #1000.
   Example: D C (crash) B ... (A, E, can be anywhere)
   b) E before crash and D after crash. inode bitmap (D) has not been written, but a valid directory entry is pointing to the inode (E), hence someone can create a file using the same inode and have a directory entry point to the same inode.
   Example: E (crash) D ... (A, B, C, can be anywhere)

8. [Lec #14, Slide #21]
   Ordered mode: write data blocks to final location, wait to completion, then write metadata to journal.
   Write A to its final location (block #1000), then wait.
   Write B C D E to the journal.
   Checkpoint B C D E to their final locations.

9. [man execvp, and covered in the discussion]
   execvp replaces the current process image with a new process image (i.e. old contents in the stack and heap are discarded, hence cannot return to the caller).

10. [Appeared in old exam]
    The final free blocks in the memory:
    First-fit: 5 30 10 (cannot allocate 35)
    Best-fit: 5 5 (all requests are successful)

Part II: Finding Design Flaws

1. [Lec #7, Slide #3, #6, #7]
   Best answer: complex because a page must store 4 inner PTs.
   Solution is to change addressing from 8/8/12 to 6/10/12.

2. [Lec #2, Slide #8]
   Forget to save P's context.
   Fine: if P runs less than the given time-slice (or faster than hardware interrupts).
   Bad: if P runs more than a time-slice. P always starts execution from the beginning.

3. [Lec #10, Slide #10]
   OS Trap on every page reference, bad!

4. [Lec #12, Slide #15]
   Pure tree is slow

Part III: Old days

1. [Lec #4, Slide #3], [Lec #3, Slide #12], and [Lec #3, Slide #23]
   No best policy.
   FIFO/FCFS: bad when convoy-effect (short job stucks waiting for long jobs).
   RR: bad when jobs have same length, and time-slice is much smaller than the job length.

2. [Lec #6, Slide #12] and [Lec #7, Slide #3]
   Segmentation: make PT small by using bounds to limit the page table size
   Multi-level paging: only allocate inner page tables for pages in use.
   Hence, no need bounds anymore.