Assume a process has 5 pages in its address space and is assigned to 4 physical frames in memory. The reference string below is missing every other page reference. The reference to page 5 causes the first page fault.
1 ? 2 ? 3 ? 4 5
Fill in the blanks to create a reference string that satisfies each
of the criteria listed below. Explain your answer briefly.
Sample: Complete the reference string so that when the page fault occurs, both LFU and FIFO would choose the SAME page to replace. Answer: 12233445. (Both replace page 1).(a)When the page fault occurs, LFU and FIFO would choose DIFFERENT pages to replace. Indicate which page would be selected by each algorithm.
(b)When the page fault occurs, LRU and FIFO would choose DIFFERENT pages to replace. Indicate which page would be selected by each algorithm.
(c)When the page fault occurs, LRU, LFU, and FIFO would choose the SAME pages to replace. Indicate which page would be selected.
(d)When the page fault occurs, LRU, LFU, and FIFO would choose DIFFERENT pages to replace. Indicate which page would be selected by each algorithm.
Theoreticians don't like to express definitions in informal, intuitive language (such as "LRU replaces the page that was used least recently.") Pretend(?) that you are a theoretician and express LRU, FIFO, and LFU mathematically. This means, you must define the page to be replaced in terms of known mathematical functions such as min, max, set functions, etc. and/or functions you define yourself that are mathematical. Don't forget to include tie-breaking rules and to cover all possiblities. For example:
Let r(1), r(2), r(3), ... r(t), ... r(T) be a memory reference string.The intuitive definition of "forward distance" f(t,x) at time t is the distance to the first reference to page x after time t.
The mathematical definition is:
f(t,x) = k if r(t+k) is the first occurrence of x in
r(t+1), r(t+2),...r(T)
= infinite if x is not a member of the set
{r(t+1), r(t+2), ... r(T)}
Then, a mathematical definition of OPT would be:
OPT Page Replacement:
Let S be the set of pages currently in memory.
At time t, OPT chooses page z to replace where z satisfies:
f(t,z) = max [ f(t,u) ]
u in S
If there is more than one page z1 and z2 with f(t, z1) = f(t, z2) = INFINITE,
then choose the page that is larger (Choose z1, if z1 > z2 else choose z2.)
An experiment to evaluate the performance of various page replacement algorithms has yielded the following graph. In this graph, the x-axis shows the number of pages allocated to a job, where n is the total number of pages in the job. The y-axis shows the page fault rate. A "Lookahead" algorithm is one that has the ability to know future page references and use that information to select the page to replace.
(a) How does the performance of Algorithm X compare to the performance of the non-lookahead algorithms? Why?
(b) If we wish to keep the page fault rate below .00001, what does this graph tell us must happen in terms of each job's frame allocation?
(c) Why is the page fault rate at m=1 less than 1.00?
(d) Why is the page fault rate at m=n equal to zero?
Suppose you work for a company designing a computer system which supports demand paged memory manangement. You are under very tight budget constraints and must make a decision whether to buy hardware which provides a small cache for holding page map table entries or to buy a higher speed disk for the paging device. Which would you choose given the following information and the fact that they cost the same.
- The speed of the cache memory is 1/10 * M time units, where M is the time to access main memory. The hit ratio is 80% and only pages currently in main memory can have their page table entries in the cache.
- The faster paging device is 35% faster than the cheap paging device. It takes .65 * D time units to transfer a page from the faster paging device to memory, where D is the time to transfer a page using the cheaper paging disk.
Read about thrashing and the working set model in Chapter 12.4. The definition of working set W(t, DELTA) is the set of k distinct pages referenced by the job in the last DELTA memory references. Below are some alternate definitions of working set. For each one, discuss how it could be implemented by the OS, whether the implementation is feasible, and how accurately it would approximate the true working set.
- W(t, DELTA) = the set of k distinct pages referenced in the last DELTA seconds of real time (wall clock time).
- W(t, DELTA) = the set of k distinct pages referenced in the last DELTA seconds of CPU time (time during which the job was actually using the CPU).
- W(t, DELTA) = the set of k distinct pages referenced in the last DELTA seconds of CPU time with a frequency of greater than F times per second of CPU time.