### HomeworkSolutionsCh8

```Chapter 8 Homework Solutions
8.1, 8.3, 8.4, 8.6, 8.10, 8.15, 8.17
Problem 8.1
Virtual Page
Number
Valid
Bit
Reference
Bit
Modify
Bit
Page Frame
Number
0
1
1
0
4
1
1
1
1
7
2
0
0
0
-
3
1
0
0
2
4
0
0
0
-
5
1
0
1
0
• Page table with page size 1024
a. Describe how, in general, a virtual address generated by the CPU is
translated into a physical main memory address.
• Split the binary address into a virtual page number (VPN) and an offset
• use VPN as an index into the page table
• extract the page frame number from the page table entry
• concatenate the page frame number with the offset to get physical memory
Problem 8.1
Virtual Page
Number
Valid
Bit
Reference
Bit
Modify
Bit
Page Frame
Number
0
1
1
0
4
1
1
1
1
7
2
0
0
0
-
3
1
0
0
2
4
0
0
0
-
5
1
0
1
0
(i) 1052
1052 = 1024+ 28 = 00..01 0000011100 so VPN = 1 and offset = 28
VPN 1  Frame number 7, so the physical address = 7*1024+28 = 7196
(ii) 2221
2221 = 2 × 1024 + 173, so the VPN = 2, page fault
(iii) 5499
5499 = 5 × 1024 + 379
VPN 5  PFN 0, so physical address = 0 × 1024+379 = 379)
Problem 8.3
a. How much memory space is needed for the user page table of Fig. 8.4?
4 Mbytes
Extra credit question: Who is buried in Grant’s tomb?
Problem 8.3
b. Hashed inverted table for above, 20-bit PN  6-bit hash number.
Entry = page number, frame number, chain pointer; 3 overflow entries per
table entry. What is the inverted page table size?
• Number of rows: 26+3=256 entries.
• Each entry consist of:
20 (page number) + 20 (frame number) + 8 bits (chain index) = 48 bits = 6 bytes.
• Total: 256 × 6= 1536 bytes
• Alternate possibility: 3 overflow includes initial entry  128 × 6 = 768
Problem 8.4
Virtual Page
Number
Page
Frame
Time
Time
Referenced
R Bit
M Bit
2
0
60
161
0
1
1
1
130
160
1
0
0
2
26
162
1
0
3
3
20
163
1
1
• Time is number of ticks since process load time.
• Page fault has occurred at time 164. Which page is replaced and why:
a. FIFO
Page Frame Number (PFN) 3 since it was loaded longest ago at time 20
b. LRU
PFN 1 since it was referenced longest ago at time 160
c. Clock
Clear R in PFN 3 (oldest loaded), clear R in PFN 2 (next oldest loaded),
victim PFN is 0 since R=0
Problem 8.4
Virtual Page
Number
Page
Frame
Time
Time
Referenced
R Bit
M Bit
2
0
60
161
0
1
1
1
130
160
1
0
0
2
26
162
1
0
3
3
20
163
1
1
• Time is number of ticks since process load time.
• Page fault has occurred at time 164. Which page is replaced and why:
d. Optimal, assuming page reference string 4,0,0,0,2,4,2,1,0,3,2
Replace the page in PFN 3 since VPN 3 (in PFN 3) is used furthest in the
future
Problem 8.4
Virtual Page
Number
Page
Frame
Time
Time
Referenced
R Bit
M Bit
2
0
60
161
0
1
1
1
130
160
1
0
0
2
26
162
1
0
3
3
20
163
1
1
e. Given above (just before page fault), assume page reference string
4,0,0,0,2,4,2,1,0,3,2. How many page faults if working set policy with LRU
were used with a window size 4 and a fixed allocation?
There are 6 faults, indicated by *
Problem 8.6
Process with 8 pages of VM, fixed allocation of 4 page frames. Page trace:
1,0,2,2,1,7,6,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,72,4,2,7,3,3,2,3
a. Show the successive pages residing in the four frames using the LRU
replacement policy. Compute the hit ratio in main memory. Assume the
frames are initially empty.
Hit ratio = 16/33
PF1
PF2
PF3
PF4
1
1
F
0
1
0
F
2
1
0
2
F
2
1
0
2
-
1
1
0
2
-
7
1
0
2
7
F
6
1
6
2
7
F
7
1
6
2
7
0
1
6
0
7
F
1
1
6
0
7
2
1
2
0
7
F
0
1
2
0
7
3
1
2
0
3
F
0
1
2
0
3
4
4
2
0
3
F
5
4
5
0
3
F
1
4
5
0
1
F
5
4
5
0
1
2
4
5
2
1
F
4
4
5
2
1
5
4
5
2
1
6
4
5
2
6
F
7
4
5
7
6
F
6
4
5
7
6
7
4
5
7
6
2
2
5
7
6
F
4
2
4
7
6
F
2
2
4
7
6
7
2
4
7
6
3
2
4
7
3
F
3
2
4
7
3
2
2
4
7
3
3
2
4
7
3
Problem 8.6
Process with 8 pages of VM, fixed allocation of 4 page frames. Page trace:
1,0,2,2,1,7,6,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,72,4,2,7,3,3,2,3
a. Show the successive pages residing in the four frames using the FIFO
replacement policy. Compute the hit ratio in main memory. Assume the
frames are initially empty.
Hit ratio = 16/33
PF1
PF2
PF3
PF4
1
1
F
0
1
0
F
2
1
0
2
F
2
1
0
2
-
1
1
0
2
-
7
1
0
2
7
F
6
6
0
2
7
F
7
6
0
2
7
0
6
0
2
7
1
6
1
2
7
F
2
6
1
2
7
0
6
1
0
7
F
3
6
1
0
3
F
0
6
1
0
3
4
4
1
0
3
F
5
4
5
0
3
F
1
4
5
1
3
F
5
4
5
1
3
2
4
5
1
2
F
4
4
5
1
2
5
4
5
1
2
6
6
5
1
2
F
7
6
7
1
2
F
6
6
7
1
2
7
6
7
1
2
2
6
7
1
2
4
6
7
4
2
F
2
6
7
4
2
c. Compare the two policy’s effectiveness with respect to this trace.
The two policies are equally effective for this particular page trace.
7
6
7
4
2
3
6
7
4
3
F
3
6
7
4
3
2
2
7
4
3
3
2
7
4
3
Problem 8.10
•
•
•
•
•
•
•
•
•
•
•
Page size = 4 Kbytes; page table entry = 4 bytes; 64-bit address space;
top level page table fits into a single page.
How many levels of page tables are needed?
A one-page page table would point to
4K/4 = 1024 = 210 pages, addressing a
total of 210 × 212 = 222 bytes.
The address space however is 264 bytes.
Adding a second layer of page tables,
the top page table would point to
210 page tables, addressing a total of
232 bytes.
Continuing this process, we can see that
5 levels do not address the full 64 bit address space, so a 6th level is required.
But only 2 bits of the 6th level are required, not the entire 10 bits.
and ignore all but the 2 lowest order bits of the 6th level.
This would give you a 64 bit address.
Your top level page table then would have only 4 entries.
Yet another option is to revise the criteria that the top level page table fit into a
single physical page and instead make it fit into 4 pages.
This would save a physical page, which is not much.
Problem 8.15
• Define the mean working set size after the kth reference as
1 k
sk ()   | W (t ,) |
k t 1
and define the missing page probability after the kth reference as
1 k
mk ()   F (t ,)
k t 1
where F(t,) = 1 if a page fault occurs at virtual time t and is 0 otherwise.
• Consider the following page reference sequence:
12345213323454511325
a. Draw a diagram similar to that of Figure 8.19 for the reference sequence
for the values  = 1,2,3,4,5,6.
Problem 8.15
Problem 8.15
• Define the mean working set size after the kth reference as
1 k
sk ()   | W (t ,) |
k t 1
and define the missing page probability after the kth reference as
1 k
mk ()   F (t ,)
k t 1
where F(t,) = 1 if a page fault occurs at virtual time t and is 0 otherwise.
• Consider the following page reference sequence:
12345213323454511325
b. Plot s20() as a function of 
c. Plot w20() as a function of 
s20(Δ) is an increasing function of Δ. m20(Δ) is a nonincreasing function of Δ.
Problem 8.17
• A task is divided into four equal sized segments and the system has built an
eight-entry page descriptor table for each segment. Thus the system has a
combination of paging and segmentation. The page size is 2 Kbytes.
a. What is the maximum size of each segment?
8 × 2K = 16K
16K × 4 = 64K
c. What is the maximum physical address space for the system?
232 = 4 GBytes
Assume that an element in physical location 00021ABC is accessed by this
it?
Problem 8.17
• A task is divided into four equal sized segments and the system has built an
eight-entry page descriptor table for each segment. Thus the system has a
combination of paging and segmentation. The page size is 2 Kbytes.
c. Assume that an element in physical location 00021ABC is accessed by this
it?
Segment:
0
0
1
2
3
7
00021ABC
Page descriptor
table
Main memory
(232 bytes)
Problem 8.17
• A task is divided into four equal sized segments and the system has built an
eight-entry page descriptor table for each segment. Thus the system has a
combination of paging and segmentation. The page size is 2 Kbytes.
c. Assume that an element in physical location 00021ABC is accessed by this