Assignment 5 is an extension of Assignment
4 page replacement to investigate the effects of page replacement algorithms (Optimal,
FIFO, & LRU), locality of reference, and frame
count. due via D2L
Assignment 5due by 11:59 PM on Thursday
May 9.
I have written all the code. You must
answer questions in this linked README.Final5.txt and turn it into D2L by
the deadline. I cannot accept assignments more than 1 day
late due to
my deadlines on turning in
grades. The usual 10% per day late penalty applies.
You must turn in README.Final5.txtand
nothing else. Turning in a Word doc or other
format will lose 10
points. I need to grade these in a batch session using vim, which
I can do only with
regular text files. No Word docs, PDFS, HTMLs, or other.
FINAL EXAM TIME SLOTS -- We will go over my solution to
Assignment 4.
Noon class: Tuesday, May
7, 2024 8-10 a.m.
1:30 class:
Thursday, May 9, 2023 2-4 p.m. STUDENTS: You do not have to become statistics experts or
worry about all of the details in the graphs below to succeed with
Assignment 5. Just let the README.Final5.txt questions
focus your efforts.
WHAT HAS CHANGED SINCE ASSIGNMENT 4?
Two things have changed since Assignment 4:
1. The physical frameCount is 100 in Assignment 4 with 500
pageCount virtual pages. Assignment 5 has both 100 (same as
Assignment 4) and 200 frameCount values.
2. Assignment 4 configures the 100,000-values page
reference string using this code:
init -> readyToCompute
init()[]/@machineid, pid, tid = getid();
for i in
range(0,referencePageCount):
referencePageList.append(sample(0,pageCount-1, 'gaussian',
pageCount//2, pageCount//10));
Assignment 5 has several different
configurations of the reference string and frameCount:
init -> readyToCompute
init()[]/@machineid, pid, tid = getid(); frameCount =
frameCount * len(processor.fastio);
# ^^^ This is 100 or
200 frames. locality =
'gaussian' if (processor.contextCount == 1) else
('exponential' if (processor.contextCount == 2) else
('revexponential' if (processor.contextCount == 3) else
'uniform'));
msg("TRACE Optimal
pageCount=" + str(pageCount) + ", frameCount="
+ str(frameCount) + ", locality=" + locality);
print("TRACE Optimal
pageCount=" + str(pageCount) + ", frameCount="
+ str(frameCount) + ", locality=" + locality);
# For the normal
distribution, the values less than one standard
# deviation away from
the mean account for 68.27% of the set;
# while two standard
deviations from the mean account for 95.45%;
# and three standard
deviations account for 99.73%
# https://en.wikipedia.org/wiki/Normal_distribution
for i in
range(0,referencePageCount):
referencePageList.append( sample(0,pageCount-1, 'gaussian',
pageCount//2, pageCount//20) if (locality == 'gaussian')
else
(sample(0,pageCount-1,'uniform') if
(locality == 'uniform') else
(sample(0,pageCount-1,'exponential',pageCount//10)
if (locality == 'exponential') else sample(0,pageCount-1,'revexponential',(pageCount//10)*9))));
Here is the complete code for Assignment 5's PageReplaceOptimal.stm.
Assignment 5's
FIFO and LRU models have this same change to frameCount
and referencePageList,
configured by command-line arguments len(processor.fastio) and
processor.contextCount
that are not otherwise used in Assignment 5 or at all in
Assignment 4.
The states and transitions are identical to Assignment 4 for
Optimal, FIFO, & LRU,
which are identical to each other.
Figure 1: The state machine diagram for Optimal, FIFO, &
LRU page replacement in Assignments 4 & 5.
As in Assignment 4, the two transitions from state readyToCompute
to compute are taken a) if the currentPage is already mapped to a physical
frame (the transition on the left labeled
"cpu:0" above), or b) if a free frame is available for
mapping to the page without finding a
"victim" page for replacement (labeled "cpu:1" above). The
transition from readyToCompute
to findVictim uses the page replacement algorithm
(Optimal, FIFO, or LRU) to select the
victim page from which to take a physical frame, with this cost
going into state findVictim as
in Assignment 4:
cpu(2 if (wasModified)
else 1)
The cost measured for the simulation is SUM_findVictim,
which is the sum of time spent in the findVictim state for the single-threaded single process of
this state machine. This cost is a
minimum of 1 tick for entry into findVictim, 2 ticks if
the victim has been modified while mapped
to a frame. There are 100,000 simulated page accesses (variable referencePageCount)
in
Assignments 4 and 5. Assignment 4 uses the gaussian distribution
of page references as handed
out in Assignment 4's PageReplaceOptimal.stm and used in your
other Assignment 4 models.
Each Assignment 5 model uses one of these four page reference
distributions across pages 0..499.
Figure 2: sample(0,pageCount-1, 'gaussian', pageCount//2,
pageCount//20) for Assignment 5
68.27% of 100,000 page references = 68,270 page references within
one standard deviation of 25 on each
side of center, from page number 225 through page number 275, for
this Gaussian distribution of page references.
The dark lines above mark this one-population-standard-deviation
boundary. Max 357 - Min 140 + 1 gives a total range of 218 pages out of the pageCount of 500.
The red quantile lines above
show where 25% and 75% of the page references have accumulated,
reading
the graph LEFT-to-RIGHT. The 50% point is the median. The
remaining graphs illustrate these 25%, 50%,
and 75% is instances accumulated LEFT-to-RIGHT using similar red lines.
The most concentrated 50% of page
references in Figure 2 lie between the 25% and 75%
centile red lines, 267 - 233 + 1 gives a range of 35 pages out of the
pageCount of 500. The "+ 1" is added to include the
lower bound of the range.
Note that the above standard deviation of pageCount//20 in
Assignment 5 is only half the range of pageCount//10 in Assignment 4's Gaussian page reference
distribution. The next histogram is for
Assignment 4's Gaussian page reference distribution.
Figure 3: sample(0,pageCount-1, 'gaussian', pageCount//2,
pageCount//10) for Assignment 4
For Assignment 4, in contrast to Assignment 5's Gaussian
distribution above, 68.27% of 100,000 page
references = 68,270 page references within one standard deviation
of 50 on each side of center, from page
number 200 through page number 300. The dark lines above mark this
one-population-standard-deviation boundary.
50% of 100,000 page references = 50,000 page references range from
page 0 through median page 34,
a range of 35 pages, for this exponential distribution of page
references.The dark line above marks this
median boundary. The remaining 50% lie in the decaying region to
the right of the line up through page 498. Max 498 - Min 0 + 1 gives a total range
of 499 pages out of the pageCount of 500. The knee
value pageCount//10
in the sample call gives the mean value of 50.
The most concentrated 50% of page
references in Figure 4 lie between the minimum and
median limits,
the median equaling the 50% centile, 34 -
0 + 1 giving a range of 35 pages out of the pageCount
of 500.
This is a more focused range of page references than 69 -
14 + 1 = 56 page references from the 25% through
the 75% centile limits.
50% of 100,000 page references = 50,000 page references range from
median page 465 through page 499,
a range of 35 pages, for this exponential distribution of page
references.The dark line above marks this
median boundary. The remaining 50% lie in the decaying region to
the left of the line down through page 10. Max 499 - Min 10 + 1 gives a total range
of 490 pages out of the pageCount of 500. The knee
value (pageCount//10)*9
in the sample call gives the mean value of 450.
The most concentrated 50% of page
references in Figure 5 lie between the maximum
and median limits,
the median equaling the 50% centile, 499 - 465 +
1 giving a range of 35 pages out of the pageCount of
500.
This is a more focused range of page references than 485
- 431 + 1 = 55 page references from the 25% through
the 75% centile limits.
Figure 6: sample(0,pageCount-1,'uniform')
Finally, the uniform page distribution hits all 500 pages in the
range with no central tendency or focal point.
The mean and median values sit in the middle of this uniform
distributed range of page references.
For Figure 6 there is no focal
region for 50% of the page references as there is in the other
page reference distributions above.
The uniform distribution has no focal region.
This final histogram shows magnitude of SUM_findVictim
values for combinations of the page replacement
algorithm (Optimal, FIFO, and LRU as in
Assignment 4), frameCount (100 or 200 physical frames for
500
virtual pages as labeled in the figure), and page reference
distribution for Assignment 5 (Gaussian, exponential, revexponential, and uniform as
labeled below and as detailed in the figures above).
Figure 7: SUM_findVictim as a function of
ReplacementAlgorithm_frameCount_PageDistribution
Below is the comma-separated-value (CSV) table with the values for
this Figure 7.
Configuration
SUM_findVictim
Optimal_100_gaussian
4213
Optimal_200_gaussian
0
Optimal_100_exponential
12070
Optimal_200_exponential
1624
Optimal_100_revexponential
11655
Optimal_200_revexponential
1519
Optimal_100_uniform
54201
Optimal_200_uniform
33932
FIFO_100_gaussian
22506
FIFO_200_gaussian
0
FIFO_100_exponential
39628
FIFO_200_exponential
11533
FIFO_100_revexponential
38869
FIFO_200_revexponential
10852
FIFO_100_uniform
89334
FIFO_200_uniform
69027
LRU_100_gaussian
12118
LRU_200_gaussian
0
LRU_100_exponential
29747
LRU_200_exponential
4175
LRU_100_revexponential
28860
LRU_200_revexponential
3786
LRU_100_uniform
89295
LRU_200_uniform
68929
Table 1: SUM_findVictim as a
function of ReplacementAlgorithm_frameCount_PageDistribution
See Chapter
8 starting at slide 33 for discussions of Paging
and also the translation-lookaside-buffer (TLB), a
register set in the memory management unit (MMU), and Chapter
9 slides regarding Locality of Reference, Thrashing, Working Set, & Belady's
Anomaly in Q1-10.
Q1. Which one of the four page reference distributions in Table 1
-- gaussian, exponential, revexponential, or uniform
-- exhibits the worst Locality of
Reference in terms of SUM_findVictim cost of page
replacement?
What numeric SUM_findVictim pattern makes you
say that?
Q2. Why does the page
reference distribution you chose in Q1 exhibit the worst Locality of
Reference behavior?
Refer to one or more of
Figure 2 through 6 in your answer.
Q3. Which one of the four
page reference distributions in Table 1 -- gaussian, exponential,
revexponential, or uniform
-- exhibits the best Locality of
Reference in terms of SUM_findVictim cost of page replacement,
for a given frameCount value
of either 100 or 200? What numeric SUM_findVictim pattern makes you say that?
Q4. Why does the page
reference distribution you chose in Q3 exhibit the best Locality of Reference
behavior
for a given frameCount value?
Refer to one or more of Figure 2 through 6 and their
discussions in your answer.
Q5.
Which one of the four page reference distributions in Table
1 -- gaussian, exponential, revexponential, or uniform
-- is the least sensitive to
the page replacement algorithm used (Optimal, FIFO, or LRU)?
What numeric SUM_findVictim pattern
makes you say that?
Q6. Which one or more of the four
page reference distributions in Table 1 -- gaussian,
exponential, revexponential,
or uniform -- give
greater-than-linear improvements when the frameCount doubles
from 100 to 200?
In other words, when
frameCount doubles from 100 to 200, cost in terms of
SUM_findVictim is reduced
by more than half. Why
do it or they give greater-than-linear improvement?
Q7. Which property dominates the minimization of SUM_findVictim
for a given frameCount value, page replacement
algorithm or
locality of reference? Why? I am not looking for a
specific page
replacement algorithm like
(Optimal, FIFO,
LRU), nor locality of
reference
like (gaussian, exponential, revexponential, uniform), but
rather just "page
replacement algorithm" OR "locality
of reference". Justify your answer in terms of
Table 1
and optionally
the figures.
Q8. Do any of the frameCount increases from 100 to
200 in Table 1 exhibit Belady's Anomaly as discussed
in
Chapter 9
slides? If so, cite an example from Table 1 that
shows Belady's
Anomaly.
Q9. From what value to what value does the translation-lookaside-buffer (TLB)
register set provide a MAPPING?
Why is it
important to maintain this mapping in a register and
not just in the page table of the process?
Q10. What
status bit or bits would be added to the TLB to
support the LRU and LRUDirty page replacement
algorithms without forcing the kernel to consult the
page table on every application memory access?
