Question 1:


      In a swapping system with variable partitions,  segments have probability
      
                      -s/10
      distribution ( e     / 10) where s is the segment size in kilobytes. Holes
                                        
                                         -h/5
      have  probability distribution  ( e    / 5) where h is the hole size in 
      
      kilobytes.  What  is the average fraction of wasted memory in external
     
      fragmentation?

      Answer:  Average segment size is 10k (by integration) and average hole size
      is 5k, that is 0.5 times average segment size. By the unused memory rule,
      the fraction of memory in holes is  (0.5/(0.5+2)) = 20%

      +2 If you have f=k/k+2 or avg hole size / total memory
      +3 If you explained what k is (from above).
      +3 If you used integration to find the average size for seg/hole size.


      Question 2:
      
      A computer whose processes have 1024 pages in their address spaces keeps
      its page tables in memory. The overhead required for reading a word from
      the page table is 500 nsec.  To reduce this  overhead, the computer has an
      associative  memory  which holds 32 (virtual  page,  physical  page frame)
      pairs and can do look up in 100 nsec.  What hit rate is needed  to reduce
      the mean overhead to 200 nsec?

      Answer:  The effective instruction time is 100h + 500(1-h), where h is the
      hit rate.  Set the expression equal to 200 and solve for h. We get h must
      be 0.75 (or greater).

      +4 if everything is right
      +2 if you setup the equation correctly

      Question 3:
      
      Consider the following segment table:

      segment     Base    Length
      -------     ----    ------
      
         0         219      600
         1        2300       14
         2          90      100
         3        1327      580
         4        1952       96
         
      What are the physical addresses for the following logical addresses?

      a)  0,430   b)  1,10   c)  2,500   d)  3,400  e) 4,112
       
      Answer:  a) 219+430=649  b) 2300+10=2310  c) illegal reference
               
               d) 1327+400=1727 e) illegal reference.

      +1 for each correct solution.
      for part c) and e), you get both points as long as that you recognize
      there are some sort of error.

 
      Question 4:
      Consider the following page reference string:

       1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
       
      How many page faults would occur for replaement by LRU, FIFO, optimal, for
      one, two,  three,  four,  five,  six and  seven  frames?  All  frames  are
      initially empty and first unique page reference causes a page fault.

            
      Answer:
      
       # frames    1    2    3    4     5    6    7
       
          LRU      20   18   15   10    8    7    7
          
         FIFO      20   18   16   14    10   10   7
         
       Optimal     20   15   11    8     7    7   7            


       -0.5 for each incorrect solution.  

      Question 5:
       
      Which of the following  programming  techniques and structures  are "good"
      for a demand-paged environment?

      a.  stack
     
      b.  hashed symbol table
     
      c.  sequential search
     
      d.  binary search
     
      e.  pure code
     
      f.  vector operations
     
      g.  indirection

      Answer:  a, c, e, f  good;  b, d, g  not good. 
	
      +1 for each correct solution.


      Question 6:
          
      In a demand-paged  system, the degree of  multiprogramming  is fixed at 4.
      Measurements  were made to determine the utilization of cpu and the paging
      disk.  The  result  is one of the  following.  For  each of case  a, b, c,
      state in one line what is happening?

      a.  cpu utilization 13%, disk 97%
     
      b.  cpu utilization 92%, disk 11%
     
      c.  cpu utilization 21%, disk  3%

      Answer:  a.  Thrashing   b.  okay   c.  can increase multiprogramming     

      +2 for each correct solution.
      +1 for each part if you sort of get it, but didn't quite explain it.


      Question 7:
      
      It has been  observed  that the number of  instructions  executed  between
      pagefaults is directly  proportional to the number of frames  allocated to
      the  process.  If twice the  number  of  frames  are  allocated,  the mean
      interval  between  page  faults  is also  doubled.  An  instruction  takes
      normally 1 microsec,  but with a  pagefault  it takes 2001  microsec.  The
      process  takes 60 secs to run during which it gets 15000 page faults.  How
      long would it take for the process if twice the memory were made available
      to it?

      Answer:  For 15000 page faults, the overhead at 2 msec per fault is 30 sec.
      So, out of the 60 sec, 30 went in paging overhead and 30 for processrunning.
      If the process had twice the memory, we have half, i.e., 7500 page faults
      and 15 sec  paging overhead. The total time for the process is 30+15=45sec.
      
      +3 if you have the correct equation to find the total number of
      instructions.  ie 60s = i*1ms + 15000*2ms