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

-- Mar 21 In-class Exercise Thread

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] 3. 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 4. Hk = 1 + 1/2 = 1.5 Number of cache misses for LRU = 3 Number of cache misses for LRU > Hk

-- Mar 21 In-class Exercise Thread

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 ____ 3. 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 4. Hk = 1+ 1/2 = 1.5 Number of cache misses for LRU = 5 > Hk

-- Mar 21 In-class Exercise Thread

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 3. 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) 4. Hk = 1.5 LRU cache misses = 3 (which is > than Hk)

-- Mar 21 In-class Exercise Thread

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} 3. 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} 4. Hk = 1+1/2 = 1.5 LRU has 3 misses Number of cache misses by LRU > Hk

-- Mar 21 In-class Exercise Thread

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, ]

-- Mar 21 In-class Exercise Thread

<nowiki> 1. I = [4,5,6] round 1: 5,4,5,6, round 2: 5,4,6,5 2. 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] 3. 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 4. Hk = 1 + 1/2 + 1/3 = 1.83 Number of cache misses for LRU = 4 Number of cache misses for LRU > Hk </nowiki>

-- Mar 21 In-class Exercise Thread

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] 3. 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 4. Hk = 1.83 Cache misses for LRU > Hk

-- Mar 21 In-class Exercise Thread

1. I = [a,b,c] round 1: b,a,b,c round 2: b,a,c,b 2. 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] 3. 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 4. Therefore, H_k = 1 + 1/2 + 1/3 = 1.83 Cache misses for LRU = 4 Hence, cache misses for LRU > H_k

-- Mar 21 In-class Exercise Thread

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} 3. R1 {2,} R2 {2, 3} R3 {1, 3} miss R4 {1, 3} R1 {2,} R2 {2, 1} R3 {2, 1} R4 {2, 1} 4. Hk = 1 + 1/2 = 1.5