Homework 2

Out: Friday Feb 9
Due: Wed Feb 21

Note: as suggested by several students, I've labelled the
difficulty of the questions below, from [easy] to [moderate]
to [intricate].

1. [easy]

   Suppose we have a system with 48 bit virtual addresses, in
   which the least-significant bits are used to indicate a 12-bit
   page offset.

   a) what is the page size in this system?

   b) how many pages would it take to cover the entire virtual
      address space?

   c) if you only bought 32MB of physical memory, how many
      page frames do you have?

   d) if page table entries are 64 bits long, how big of
      a single-level page table would you require to map
      all of virtual memory?

---

2. [easy, but lots of grunt work]

   Consider a program that generates a sequence of virtual
   address references that correspond to the following sequence
   of page references:

      1,2,3,4,1,2,5,6,1,3,1,2,7,6,3,2,1,2,3,6

   (i.e., first it references an address in page #1, then
   an address in page #2, then an address in page #3, etc.)

   Using diagrams similar to that in figures 9.8 and 9.10
   (pages 305 and 307) in Silberschatz, show how pages
   are populated in physical frames over time, and
   indicate where page faults occur, for each of the
   following cases:

   a) LRU page replacement, for each subcase of:
       i) one frame, ii) three frames, iii) 5 frames, iv) 7 frames

   b) FIFO page replacement, for each subcase of:
       i) one frame, ii) three frames, iii) 5 frames, iv) 7 frames

   c) Optimal page replacement, for each subcase of:
       i) one frame, ii) three frames, iii) 5 frames, iv) 7 frames


   Did you see an instance of Belady's anomaly?  If so, point it
   out.  For which cases do you think the system exhibited
   thrashing?

---

3.  [moderate]

    Given a flat file system (i.e., one with only a single
    directory), a reasonable design decision is to place
    the directory on the middle cylinder of the disk.

    a) why?

    b) why doesn't the UNIX FFS put all of its directories
       on the middle cylinder(s)?

---

4. [intricate]

   Consider a disk with N tracks numbered from 0 to (N-1), and
   assume that requested sectors are distributed randomly and
   evenly over the disk.  

   a.  Calculate the probability of a seek of length K.  
       
       Hint: this involves the summing over all possible
       combinations of movements of K tracks.)

   b.  Calculate the average number of tracks traversed by a
       seek.
                          i=n-1
       Hint #1:  Avg(z) =  SUM  i * (Probability that z=i)
                           i=0

       
       Hint #2:  The sum of the first Y square numbers =
                 1 + 4 + 9 + 16 + ... + Y*Y =
                 (1/6)*(n)*(n+1)*(2n+1)