## Solution Set 5

### Problem 1

Consider a toy paging system. There are four frames and six pages. In the sequence of events listed below, "Read I" means that an address in page I must be read; "Write I" means that an address in page I must be written to; "TICK" is a clock tick. (Keep in mind that the arguments to Read and Write are pages, not frames.) List the page faults that occur, and the frames chosen for the new pages, if the OS uses (A) the Not Recently Used (NRU) PRA; (B) the Second Chance PRA; (C) the aging PRA; (D) Belady's (optimal) algorithm. If the algorithm gives a tie between pages to replace, choose the one with the lower frame. Assume that memory is initially empty.
```               NRU                           Second Chance
Time: Events:        Page to   Pages in            Page to  Pages in       FIFO queue
replace   frames (after       replace  frames (after
replacement)                 replacement)
1  Write 1  FAULT.           1             FAULT.        1             [1]
2  Read 2   FAULT.           1,2           FAULT.        1,2           [1,2]
3  Write 3  FAULT.           1,2,3         FAULT.        1,2,3         [1,2,3]
4  Read 4   FAULT.           1,2,3,4       FAULT.        1,2,3,4       [1,2,3,4]
5  Write 5  FAULT. 2.        1,5,3,4       FAULT. 1.     5,2,3,4       [2,3,4,5]
6  TICK
8  Read 2   FAULT. 4.        1,5,3,2
8  Write 1                                 FAULT. 4.     5,2,3,1       [5,2,3,1]
9  Read 6   FAULT. 5.        1,6,3,2       FAULT. 5.     6,2,3,1       [2,3,1,6]
11  Read 4   FAULT. 6.        1,4,3,2       FAULT. 2.     6,4,3,1       [3,1,6,4]
12  TICK
14  Write 5  FAULT. 4.        1,5,3,2.      FAULT. 3.     6,4,5,1       [1,6,4,5]
15  Read 3                                  FAULT. 6.     3,4,5,1       [4,5,1,3]
16  Read 4   FAULT. 2.        1,5,3,4
18  TICK
19  Write 2  FAULT. 4.        1,5,3,2       FAULT. 4.     3,2,5,1       [5,1,3,2].

Time: Events:        Page to   Pages in            Page to  Pages in
replace   frames (after       replace  frames (after
replacement)                 replacement)
1  Write 1  FAULT.           1             FAULT.         1
2  Read 2   FAULT.           1,2           FAULT.         1,2
3  Write 3  FAULT.           1,2,3         FAULT.         1,2,3
4  Read 4   FAULT.           1,2,3,4       FAULT.         1,2,3,4
5  Write 5  FAULT. 1.        5,2,3,4       FAULT. 4.      1,2,3,5
6  TICK
8  Write 1  FAULT. 5.        1,2,3,4
9  Read 6   FAULT. 4,        1,2,3,6       FAULT. 2.      1,6,3,5
11  Read 4   FAULT. 6.        1,2,3,4       FAULT. 6.      1,4,3,5
12  TICK
14  Write 5  FAULT. 2.        1,5,3,4
18  TICK
19  Write 2  FAULT. 5.        1,2,3,4.      FAULT. 1.      2,4,3,5
20  Read 5   FAULT. 2.        1,5,3,4.
```

### Problem 2

Consider the WE 18300 hard disk described in Tanenbaum p. 301: There are 10601 cylinders, 12 tracks per cylinder, 281 sectors per track on average, 512 bytes per sector, for an overall disk capacity of 18.3 GBytes. The seek time between adjacent cylinders is 0.8 msec; the average seek time is 6.9 msec, the rotation time is 8.33 msec. Assume that the disk is not interleaved so that an entire track can be read in one rotations of the disk.
• A. How long would it take to read the entire disk from beginning to end in order? (1 digit of accuracy is enough e.g. "About 40 seconds.")

Answer: There are 12*10601 = 1.3*105 tracks, and each can be read in a rotation time of 8.3*10-3 seconds, for a total of about 103 seconds = about 17 minutes. (The seek time, which is always between adjacent cylinders, is negligible.)

• B. Suppose that the block size is 1KB, that each block consists of two consecutive sectors, and that you must read every block on the disk in random order. (As we shall see later in the course, this can happen doing a logical dump of a file system that has filled the disk.) How long would this take?

Answer: There are 10601 * 12 * 281/2 = 1.8*107 blocks (or alternatively 18.3 GBytes / 1024 Bytes per block) on the disk. To move from one block to another takes on average the average time for a seek plus half a rotation = 11.8 msec. Total time is therefore 2.1*105 seconds = 2 days, 10.5 hours.