Given that main memory is composed of three page frames for public use and that
ID: 3662818 • Letter: G
Question
Given that main memory is composed of three page frames for public use and that a program requests pages in the following order:
a, b, a, b,f, d, f, c, g, f, g, b, d, e
a. Using the FIFO page removal algorithm, perform a page trace analysis and indicate page faults with asterisks(*). Then compute the failure and success ratios.
b. Using the LRU page removal algorithm, perform a page trace analysis and compute the failure and success ratios.
c. What conclusions do you draw from this comparison of FIFO and LRU performance? Could you make general statements from this example? Explain why or why not.
Explanation / Answer
a. Using the FIFO page removal algorithm, perform a page trace analysis and indicate page faults with asterisks(*). Then compute the failure and success ratios.
Answer:
Page Request
a
b
a
b
f
d
f
c
g
f
g
b
d
e
Page Fault at start of time slice
*
*
*
*
*
*
*
*
*
Page Frame 1
a
a
a
a
a
d
d
d
d
d
d
b
b
b
Page Frame 2
b
b
b
b
b
f
f
f
f
f
f
d
d
Page Frame 3
f
c
c
c
g
g
g
g
g
e
5 page faults in 11 time steps yields:
success rate of 5/14 = 0.3571 = 35%
failure rate of 9/14 = 0.6428 = 65%
b. Using the LRU page removal algorithm, perform a page trace analysis and compute the failure and success ratios
Answer:
Page Request
a
b
a
b
f
d
f
c
g
f
g
b
d
e
Page Fault at start of time slice
*
*
*
*
*
*
*
*
*
*
Page Frame 1
a
a
a
a
a
a
a
c
c
c
c
b
b
b
Page Frame 2
b
b
b
b
d
d
d
d
f
f
f
f
e
Page Frame 3
f
f
f
f
g
g
g
g
d
d
success rate of 9/14 =65%
failure rate of 5/14 =35%
c. What conclusions do you draw from this comparison of FIFO and LRU performance? Could you make general statements from this example? Explain why or why not.
Answer:
The First-in First-out yielded a more favorable success rate than the Least-Recently-Used method.
You cannot make a general statement from just one sample.
If you assume that there is a uniform chance of any one of the pages being selected at each time step, independently of what has happened in the past, then the probability of no page fault is 75% from one step to the next step. The chance of a page fault is 25%. This is a Bernoulli trial with P(page fault) = 0.25. The chance of a specific number of page faults over a given number of time steps is distributed according to the Binomial distribution. This identified bounds on performance compared to real job streams. The more you know about the characteristics of a job stream, the better you should be able to do compared to uniform random selection
Page Request
a
b
a
b
f
d
f
c
g
f
g
b
d
e
Page Fault at start of time slice
*
*
*
*
*
*
*
*
*
Page Frame 1
a
a
a
a
a
d
d
d
d
d
d
b
b
b
Page Frame 2
b
b
b
b
b
f
f
f
f
f
f
d
d
Page Frame 3
f
c
c
c
g
g
g
g
g
e
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.