Post your solutions to the Mar 21 In-Class Exercise to this thread.

Best,

Chris

1. 1,0,1,2, 1,0,2
2. Cache = []

R1: Cache = [1,] R2: Cache = [1,0] R3: Cache = [1,0] R4: Cache = [1,2] MISS R5: Cache = [1,2] R6: Cache = [0,2] MISS R7: Cache = [0,2]

1. Cache = []

R1: Cache = [1,] R2: Cache = [1,0] R3: Cache = [1,0] R4: Cache = [1,2] MISS R5: Cache = [1,2] R6: Cache = [1,0] MISS R7: Cache = [2,0] MISS

1. Hk = 1 + 1/2 = 1.5

Number of cache misses for LRU = 3 Number of cache misses for LRU > Hk

1. let I = [I1,I2, I3] Round_1 = I2, I1,I2,I1,I3 Round_2 = I3,I3,I2,I2,I2,I2,I1
2. cache = [I1,I3] I2 - cache Miss eject I3, I1 - cache = [I1,I2] I2 - cache = [I1,I2] I1 - cache = [I1,I2] I3 - cache Miss eject I1 cache = [I2,I3]

Round 1 ----- I3 - cache = [I2,I3] I3 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I1 - cache Miss end of Round 2 ____

1. cache = [I1,I3] I2 - cache Miss eject I1, I1 - cache = [I2,I3] cache miss eject I2 I2 - cache = [I1,I3] cache miss eject I3 I1 - cache = [I1,I2] I3 - cache Miss eject I1 cache = [I2,I3]

end of Round 1 ----- I3 - cache = [I2,I3] I3 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I1 - cache Miss eject I3 end of Round 2______

LRU has 5 misses - 4 for the first sequence and 1 for the second sequence

1. Hk = 1+ 1/2 = 1.5 Number of cache misses for LRU = 5 > Hk

1. I = {1,2,3} r1 = 2 r2 = 3 r3 = 1 First round : 2, 2, 1, 1,3 Second round : 3, 3, 2, 1
2. Initial Cache = {2,1} Round 1

Cache = {2,1} for page request 2 (HIT) = {2,1} for page request 2 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 3 (MISS) = {1,3} Round 2 Cache = {1,3} for page request 3 (HIT) = {1,3} for page request 3 (HIT) = {1,3} for page request 2 (MISS) = {1,2} for page request 1 (HIT) MIN had two misses as we replaced pages looking forward on what page would be requested

1. LRU Cache = {2,1} Round 1 Cache = {2,1} for page request 2 (HIT)

= {2,1} for page request 2 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 3 (MISS) = {1,3} Round 2 Cache = {1,3} for page request 3 (HIT) = {1,3} for page request 3 (HIT) = {1,3} for page request 2 (MISS) = {3,2} for page request 1 (MISS) = {2,1} LRU had three misses(replaced least recently used page)

1. Hk = 1.5

LRU cache misses = 3 (which is > than Hk)

Itemset: {a, b, c} Cache has: {a, b}

1. Round 1: b,c,a,b Round 2: b,a,a,b
2. R1. {a,b}

R2. {a,c} Miss R3. {a,c} R4. {a,b} Miss

R1. {a,b} R2. {a,b} R3. {a,b} R4. {a,b}

1. For LRU

R1. {a,b} R2. {b,c} Miss R3. {a,c} Miss R4. {a,b} Miss

R1. {a,b} R2. {a,b} R3. {a,a} R4. {a,a}

1. Hk = 1+1/2 = 1.5

LRU has 3 misses Number of cache misses by LRU > Hk

Round 1 : 0 2 1 Round 2 : 1 1 0 2 cache - []

1 Req: [0,] ; 2 Req: [0,2,]; 3 Req: [0,1,];4 Req: [0,2,] miss; next round
1 req: [1,] ; 2 Req: [ 1,1, ]; 3 Req [1,0] MISS; 4 Req [1,0,] 5 req [0,2] MISS, 6 Req [0,1, ]

<nowiki>

1. I = [4,5,6]

round 1: 5,4,5,6, round 2: 5,4,6,5

1. initially Cache [5,4]

Cache[5,4] Cache[5,4] Cache[5,6] MISS Cache[5,6] Cache[4,6] MISS Cache[4,6] MISS Cache[5,6]

1. Cache = [5,4]

Cache = [5,4] Cache = [5,4] Cache = [5,6] MISS Cache = [5,6] Cache = [5,4] MISS Cache = [6,4] MISS Cache = [6,5] MISS

1. Hk = 1 + 1/2 + 1/3 = 1.83

Number of cache misses for LRU = 4 Number of cache misses for LRU > Hk </nowiki>

1.I = [1,2,3] round 1: 2,1,2,3 round 2: 2,1,3,2

2.Init Cache = [2,1] Cache = [2,1] Cache = [2,1] Cache = [2,3] MISS Cache = [2,3] Cache = [1,3] MISS Cache = [1,3] MISS Cache = [2,3]

1. LRU

Cache = [2,1] Cache = [2,1] Cache = [2,1] Cache = [2,3] MISS Cache = [2,3] Cache = [2,1] MISS Cache = [3,1] MISS Cache = [3,2] MISS

1. Hk = 1.83

Cache misses for LRU > Hk

1. I = [a,b,c]

round 1: b,a,b,c round 2: b,a,c,b

1. Initially, the cache would be: [b,a]

Cache[b,a] Cache[b,a] Cache[b,c] Miss Cache[b,c] Cache[a,c] Miss Cache[a,c] Miss Cache[b,c]

1. Cache = [b,a]

Cache = [b,a] Cache = [b,a] Cache = [b,c] Miss Cache = [b,c] Cache = [b,a] Miss Cache = [c,a] Miss Cache = [c,b] Miss

1. Therefore, H_k = 1 + 1/2 + 1/3 = 1.83

Cache misses for LRU = 4 Hence, cache misses for LRU > H_k

1. Round 1 = 2,3,1,3 Round 2 = 2,1,1,2
2. R1 {2,}

R2 {2, 3} R3 {2, 1} miss R4 {3, 1} miss

R1 {2,} R2 {2, 1} R3 {2, 1} R4 {2, 1}

1. R1 {2,}

R2 {2, 3} R3 {1, 3} miss R4 {1, 3}

R1 {2,} R2 {2, 1} R3 {2, 1} R4 {2, 1}

1. Hk = 1 + 1/2 = 1.5