## Homework 6: Solutions

### Problem 1

Consider the following toy paging system: The virtual address space is 6 bits. The actual memory has size 16. The page size is 4, so there are 16 pages and 4 frames. (Assume that the OS and the page table are stored separately from this memory.)

Suppose that the values in the page table are as follows:

[-, 12, -, -, 8, 0, -, -, -, -, -, -, 4, -, -, -]
where "-" indicates that the page is not in memory. For each of the following virtual addresses, give corresponding absolute address if there is one, or answer "page fault", if there isn't:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.
Needless to say, all indexing is 0-based.

2 - table[0]+2 - fault.
3 - table[0]+3 - fault.
5 - table[1]+2 - 13.
7 - table[1]+2 - 15.
11 - table[2]+3 - fault.
13 - table[3]+1 - fault.
17 - table[4]+1 - 9
19 - table[4]+3 - 11
23 - table[5]+3 - 3
29 - table[7]+1 - fault.
31 - table[7]+3 - fault.

### Problem 2

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. If the algorithm gives a tie between pages to replace, choose the one with the lower frame. Assume that memory is initially empty.

NRU

```Time: Events:   Action
1  Write 1.  Fault. Load into free frame 0
4  TICK
5  Write 2   No fault.
7  Read 5.   Fault. Replace page 3 = frame 2. (RM=00) Frame table [1,2,5,4]
8  TICK
10  Write 6   Fault. Replace page 5 = frame 2  (RM=00) Frame table [1,2,6,4]
11  Write 3   Fault. Replace page 4 = frame 3. (RM=00) Frame table [1,2,6,3]
12  TICK
14  Write 1   No fault.
15  Write 4   Fault. Replace page 6 = frame 2. (RM=01) Frame table [1,2,4,3]
16  TICK
17  Write 5   Fault. Replace page 1 = frame 0. (RM=01) Frame table [5,2,4,3]
18  Write 2   No fault.
```

Second chance

```Time: Events:   Action
1  Write 1.  Fault. Load into free frame 0
4  TICK
5  Write 2   No fault.
6  Read 4.   Fault. Load into free frame 3.  Frame table [1,2,3,4]
Queue: 1,2,3,4
7  Read 5.   Fault. Replace page 1 = frame 0. Frame table [5,2,3,4]
Queue: 2,3,4,5
8  TICK
9  Read 1    Fault. Replace page 2 = frame 1. Frame table [5,1,3,4]
Queue: 3,4,5,1
10  Write 6   Fault. Replace page 3 = frame 2. Frame table [5,1,6,4]
Queue: 4,5,1,6.
11  Write 3   Fault. Replace page 4 = frame 3. Frame table [5,1,6,3]
Queue: 5,1,6,3.
12  TICK
13  Read 2    Fault. Replace page 5 = frame 0.  Frame table [2,1,6,3]
Queue: 1,6,3,2
14  Write 1   No fault.
15  Write 4   Fault. Replace page 6 = frame 2.  Frame table [2,1,4,3]
Queue: 3,2,1,4
16  TICK
17  Write 5   Fault. Replace page 3 = frame 3.  Frame table [2,1,4,5]
Queue: 2,1,4,5
18  Write 2   No fault.
```

Aging

```Time: Events:   Action
1  Write 1.  Fault. Load into free frame 0
4  TICK
5  Write 2   No fault.
6  Read 4.   Fault. Load into free frame 3.  Page table: [1,2,3,4]
7  Read 5.   Fault. Replace page 1 = frame 0. (Age=010000 -- first
bit is current R bit)
Page table: [5,2,3,4]
8  TICK
9  Read 1.   Fault. Replace page 3 = frame 2 (Age = 001000)
Page table: [5,2,1,4]
10  Write 6.  Fault. Replace page 5 = frame 0 (Age = 010000)
Page table: [6,2,1,4]
11  Write 3.  Fault. Replace page 4 = frame 3 (Age = 010000)
(Note: the age of page 2 is 011000)
Page table: [6,2,1,3]
12  TICK