Assignment-10-Anderson.txt

Brian Anderson
ComS 352 - Assignment 10
4/17/2013
-------------------------

1:  In the long run, what is the maximum acceptable page-fault rate in
    order to achieve an effective access time of no more than 200 nanoseconds?

physical frames =   256
page fault time =   4ms (no write to main)
                    10ms (frame modified, 75%)
main memory time =  100ns
goal < 200ns

Using the formula from page 403: 
    effective access time = (1 − p) × ma + p × page fault time.

200ns > (1-p) * 100ns + p * (page fault time)
page fault time = (10ms*0.75) + (4ms*(1-0.75))

200ns > (1-p) * 100ns + p * (10ms*0.75) + (4ms*(1-0.75))

Solving for p...
    200ns > 100 - 100p + 7,500,000p + 1,000,000p
    200ns > 100 + 8,499,900p
    100 > 8,499,900p
    p < 0.0000117648

-------------------------------------------------------------------------

2. Given a main memory with 5 frames, how many page faults occur when 
   the LRU algorithm is run for page replacement for the following reference string?
   1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2
   Show the pages in each frame after each time a page fault has been handled.

LRU = least-recently-used (LRU) algorithm

Faults:  *  *  *  *  *           *  *  *        *           *  *        *
Access:  1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2
       +--+--+--+--+--+        +--+--+--+     +--+        +--+--+     +--+
       | 1| 1| 1| 1| 1|        | 1| 1| 1|     | 1|        | 5| 5|     | 5|
       |  | 2| 2| 2| 2|        | 6| 6| 6|     | 6|        | 6| 4|     | 4|
       |  |  | 3| 3| 3|        | 3| 3| 8|     | 8|        | 8| 8|     | 8|
       |  |  |  | 4| 4|        | 4| 4| 4|     | 9|        | 9| 9|     | 9|
       |  |  |  |  | 5|        | 5| 7| 7|     | 7|        | 7| 7|     | 2|
       +--+--+--+--+--+        +--+--+--+     +--+        +--+--+     +--+
Replaced.......................  2  5  3        4           1  6        7
Fault count = 12