Question

In: Computer Science

A process contains eight virtual pages on disk and is assigned a fixed allocation of four-page...

A process contains eight virtual pages on disk and is assigned a fixed allocation of four-page frames in the main memory. The following page trace occurs: 1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3, 4

(a) Show the successive pages residing in the four frames using the LRU replacement policy. Compute the hit ratio in the main memory. Assume that the frames are initially empty.

(b) Repeat part (a) for the FIFO replacement policy.

(c) Compare the two hit ratios and comment on the effectiveness of using FIFO to approximate LRU with respect to this particular trace.

Solutions

Expert Solution

Given page-frames in main memory for a process = 4;

(a) LRU-Page-Access:

Miss Miss Miss Hit Hit Miss Miss Hit Miss Hit Miss Hit Miss
1 0 2 2 1 7 6 7 0 1 2 0 3
1 0 0 2 1 7 6 7 0 1 2 0
1 1 0 2 1 1 6 7 0 1 2
0 2 2 1 6 7 7 1
Hit Miss Miss Miss Hit Miss Hit Hit Miss Miss Hit Hit Miss
0 4 5 1 5 2 4 5 6 7 6 7 2
3 0 4 5 1 5 2 4 5 6 7 6 7
2 3 0 4 4 1 5 2 4 5 5 5 6
1 2 3 0 0 4 1 1 2 4 4 4 5
Miss Hit Hit Miss Hit Hit Hit Hit
4 2 7 3 3 2 3 4
2 4 2 7 7 3 2 3
7 7 4 2 2 7 7 2
6 6 6 4 4 4 4 7

Total Hits: 17; Miss: 17; Total Access: 34;

Hit Ratio: Hit / Total Access = 17/34 = 0.5 = 50%

(b) FIFO-Access:

  

Miss Miss Miss Hit Hit Miss Miss Hit Hit Miss Hit Miss
1 0 2 2 2 7 6 6 6 1 1 0
1 0 0 0 2 7 7 7 6 6 1
1 1 1 0 2 2 2 7 7 6
1 0 0 0 2 2 7
Miss Hit Miss Miss Miss Hit Miss Hit Hit Miss Miss Hit Hit
3 3 4 5 1 1 2 2 2 6 7 7 7
0 0 3 4 5 5 1 1 1 2 6 6 6
1 1 0 3 4 4 5 5 5 1 2 2 2
6 6 1 0 3 3 4 4 4 5 1 1 1
Hit Miss Hit Hit Miss Hit Miss Hit Hit
7 4 4 4 3 3 2 2 2
6 7 7 7 4 4 3 3 3
2 6 6 6 7 7 4 4 4
1 2 2 2 6 6 7 7 7

Total Hit: 17; Total Miss: 17; Total Access: 34;

Hit Ratio = Hit / Total Access = 17/34 = 0.50 = 50%

(c)In this particular trace both the LRU and FIFO have same hit ratio. They perform the same.


Related Solutions

Describe scenarios when you would use a Fixed-size virutal disk, a Dynamic virtual disk, and a...
Describe scenarios when you would use a Fixed-size virutal disk, a Dynamic virtual disk, and a Differencing virtual disk.
Write an essay (2 pages + 1 reference page = 3 pages total) on your assigned...
Write an essay (2 pages + 1 reference page = 3 pages total) on your assigned patient Must have 2 or more references . Your patient is a 45year old female with a medical diagnosis of Hypertension. She has a MD order for Blood Pressure checks every 4 hours (q4h).      A. Name and describe 2 sites and 2 ways (types) to measure her Blood Pressure. (20pts)      B. What are some of the factors that affect Blood Pressure?                       (25...
1).A box contains 20 balls. Five are blue, seven are red, and eight are black. Four...
1).A box contains 20 balls. Five are blue, seven are red, and eight are black. Four balls are selected at random and with replacement. Calculate the probability that fewer than two red balls are chosen. ANSWER: .5630 2. A company recently hired 50 employees. You are given: (a) Thirty employees are from Iowa; the remaining came from New York. (b) Of the employees who are from Iowa, 30% are males and the remaining are females. (c) Of the employees who...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT