University CS 321 Homework 5: Memory Management and Page Replacement

This homework assignment delves into the core concepts of operating systems, specifically focusing on memory management techniques. The solution addresses a problem involving virtual memory, page replacement algorithms, and address translation. The first part of the assignment requires the student to analyze logical addresses, convert them to binary, determine page and offset values, and trace the access to memory locations, identifying page faults and the values retrieved. The second part involves filling a table based on a given reference string and applying the PFF (Page Fault Frequency) page replacement algorithm with a time threshold (τ = 2). The student must track the resident set, identify page-ins and page-outs, and determine the number of page faults. Finally, the assignment concludes by asking the student to derive a reference string from the logical addresses presented in the initial problem.

MODULE 5 S19
1. Given the following physical addresses and value in memory:
add 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
val 16 14 12 10 36 34 32 30 0 40 35 30 28 18 24 20 32 0 40 8 *32 24 54 58
add 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
val 24 28 32 62 64 32 18 27 25 23 21 19 17 15 13 11 16 *7
2 32 0 48 *8
0 ? ?
add 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
val 8 40 35 16 14 12 12 22 24 42 17 19 21 23 25 27 16 15 13 11 9 7 0 0
Each page has 16 words.
add is the address of memory.
val is the value at that address.
The size of the page table is: 6 (indexed 0 – 5)
The ‘?’ in the value indicates a non-existent page.
The ‘*’ in the value indicates that page is not currently present in memory.
Processes P1 is running.
The page table starts at physical address 64.
Process P1 references the following logical addresses in the order given in the logical address column below:
The Access column is the value at that location.
Use ER to indicate a non-existent page.
Use PF to indicate a page fault.
Fill in the chart
logical address
in decimal
logical address in
binary page in binary offset in binary access
12 0000 0000 0000 1100 0000 0000 0001 1100 0000 0000 0100 1101 OK
15 0000 0000 0000 1111 0000 0000 0001 0100 0000 0000 0100 1111 OK
19 0000 0000 0001 0011 0000 0000 0000 1000 0000 0000 0101 0011
33 0000 0000 0010 0001 0000 0000 0010 1010 0000 0000 0110 0001
36 0000 0000 0010 0100 0000 0000 0001 1010 0000 0000 0110 0100
41 0000 0000 0010 1001 0000 0000 0000 1111 0000 0000 1001 1001
45 0000 0000 0010 1101 0000 0000 0000 0111 0000 0000 0110 1101
56 0000 0000 0011 1000 0000 0000 0001 1001 0000 0000 0111 1000
63 0000 0000 0011 1111 0000 0000 0001 1011 0000 0000 0111 1111
76 0000 0000 0100 1100 ‐ 0000 0000 1000 1100 Page
Fault
78 0000 0000 0100 1110 ‐ 0000 0000 1000 1110 Page
Fault
80 0000 0000 0101 0000 ‐ 0000 0000 1101 0000 Page
Fault
2. Fill in the table below based on the reference string (RS) shown. The resident set at time 0 is given.

Algorithm to use is: PFF with τ = 2
Time t 0 1 2 3 4 5 6 7 8 9 10 11 12 13
RS 2 3 5 3 2 1 2 3 2 4 3 4 5 3
P1 x x x x x x X x x x x x
P2 X x x x x x x x x x x x
xP3 x x x x x x x x x
xP4 x x x x x x x x x
P5 x x x x x x x x x x x
IN 2 3 3 2 2 2 4
OUT 3 1 2 4
PF 1 2 3 4 5 6 7
3. Based on the logical addresses given in problem 1 on the previous page what would that reference string be?
____________Reference string is 4 2 3 2 3 1 1 2 4 0 2__________________________________
REFERENCES
[1] B. Tanaka. (2005,October) “Monitoring Virtual Memory with
vmstat”Available:https://www.linuxjournal.com/article/8178

[2] L.A. Belady
A study of replacement algorithms for virtual storage computers
IBM Systems J., 5 (1966), pp. 78-101